CEK Machine
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A CEK Machine is an abstract machine invented by Matthias Felleisen and Daniel P. Friedman that implements left-to-right call by value. It is generally implemented as an interpreter for functional programming languages, but can also be used to implement simple imperative programming languages. A state in a CEK machine includes a control statement, environment and continuation. The control statement is the term being evaluated at that moment, the environment is (usually) a map from variable names to values, and the continuation stores another state, or a special halt case. It is a simplified form of another abstract machine called the SECD machine. The CEK machine builds on the SECD machine by replacing the dump (call stack) with the more advanced continuation, and putting parameters directly into the environment, rather than pushing them on to the parameter stack first. Other modifications can be made which creates a whole family of related machines. For example, the CESK machine has the environment map variables to a pointer on the store, which is effectively a heap. This allows it to model mutable state better than the ordinary CEK machine. The CK machine has no environment, and can be used for simple calculi without variables.
A CEK Machine is an abstract machine invented by Matthias Felleisen and Daniel P. Friedman that implements left-to-right call by value. It is generally implemented as an interpreter for functional programming languages, but can also be used to implement simple imperative programming languages. A state in a CEK machine includes a control statement, environment and continuation. The control statement is the term being evaluated at that moment, the environment is (usually) a map from variable names to values, and the continuation stores another state, or a special halt case. It is a simplified form of another abstract machine called the SECD machine. The CEK machine builds on the SECD machine by replacing the dump (call stack) with the more advanced continuation, and putting parameters directly into the environment, rather than pushing them on to the parameter stack first. Other modifications can be made which creates a whole family of related machines. For example, the CESK machine has the environment map variables to a pointer on the store, which is effectively a heap. This allows it to model mutable state better than the ordinary CEK machine. The CK machine has no environment, and can be used for simple calculi without variables. \langle \epsilon, \emptyset, \text{ret}(F) \gg \text{arg}(N, \text{E}) \gg \text{K} \rangle &\mapsto \langle N, \text{E}, \text{app}(F) \gg K \rangle \quad &F = \lambda x . M \\ \langle \epsilon, \emptyset, \text{ret}(V) \gg \text{app}(F) \gg \text{K} \rangle &\mapsto \langle M, \text{E}[x \mapsto V], K \rangle \quad &F = \lambda x . M\\ \end{align} where \gg is a monadic bind on the continuations, \text{E}[x \mapsto V] is an environment extended with a new binding. For example, the term (\lambda x . x + 1) \, 5 is evaluated using the following steps: \begin{align} &\langle (\lambda x . x + 1) \, 5, \text{E}, \text{K} \rangle \\ \mapsto \quad &\langle (\lambda x . x + 1), \text{E}, \text{arg}(5, \text{E}) \gg \text{K} \rangle \\ \mapsto \quad &\langle \epsilon, \emptyset, \text{ret}((\lambda x . x + 1, \text{E})) \gg \text{arg}(5, \text{E}) \gg \text{K} \rangle \\ \mapsto \quad &\langle 5, \text{E}, \text{app}((\lambda x . x + 1, \text{E})) \gg \text{K} \rangle \\ \mapsto \quad &\langle \epsilon, \emptyset, \text{ret}(5) \gg \text{app}((\lambda x . x + 1, \text{E})) \gg \text{K} \rangle \\ \mapsto \quad &\langle x + 1, \text{E}[x \mapsto 5], K \rangle \\ \vdots \\ \mapsto \quad &\langle \epsilon, \emptyset, \text{ret}(6) \gg K \rangle \\ \end{align} where the calculus is extended to numbers and addition (even though both numbers and addition can be encoded entirely in the lambda calculus). type term = IND of int (* de Bruijn index *) | ABS of term | APP of term * term Values are closures, as invented by Peter Landin: type value = CLO of term * value list type cont = C2 of term * value list * cont | C1 of value * cont | C0 let rec continue (c : cont) (v : value) : value = match c, v with C2 (t1, e, k), v0 -> eval t1 e (C1 (v0, k)) | C1 (v0, k), v1 -> apply v0 v1 k | C0, v -> v and eval (t : term) (e : value list) (k : cont) : value = match t with IND n -> continue k (List.nth e n) | ABS t' -> continue k (CLO (t', e)) | APP (t0, t1) -> eval t0 e (C2 (t1, e, k)) and apply (v0 : value) (v1 : value) (k : cont) = let (CLO (t, e)) = v0 in eval t (v1 :: e) k let main (t : term) : value = eval t [] C0 This implementation is in defunctionalized form, with cont and continue as the first-order representation of a continuation. Here is its refunctionalized counterpart: let rec eval (t : term) (e : value list) (k : value -> 'a) : 'a = match t with IND n -> k (List.nth e n) | ABS t' -> k (CLO (t', e)) | APP (t0, t1) -> eval t0 e (fun v0 -> eval t1 e (fun v1 -> apply v0 v1 k)) and apply (v0 : value) (v1 : value) (k : value -> 'a) : 'a = let (CLO (t, e)) = v0 in eval t (v1 :: e) k let main (t : term) : value = eval t [] (fun v -> v) This implementation is in left-to-right continuation-passing style, where the domain of answers is polymorphic, i.e., is implemented with a type variable. This continuation-passing implementation is mapped back to direct style as follows: let rec eval (t : term) (e : value list) : value = match t with IND n -> List.nth e n | ABS t' -> CLO (t', e) | APP (t0, t1) -> let v0 = eval t0 e and v1 = eval t1 e in apply v0 v1 and apply (v0 : value) (v1 : value) : value = let (CLO (t, e)) = v0 in eval t (v1 :: e) let main (t : term) : value = eval t [] This direct-style implementation is also in defunctionalized form, or more precisely in closure-converted form. Here is the result of closure-unconverting it: type value = FUN of (value -> value) let rec eval (t : term) (e : value list) : value = match t with IND n -> List.nth e n | ABS t' -> FUN (fun v -> eval t' (v :: e)) | APP (t0, t1) -> let v0 = eval t0 e and v1 = eval t1 e in apply v0 v1 and apply (v0 : value) (v1 : value) : value = let (FUN f) = v0 in f v1 let main (t : term) : value = eval t [] The resulting implementation is compositional. It is the usual Scott-Tarski definitional self-interpreter where the domain of values is reflexive (Scott) and where syntactic functions are defined as semantic functions and syntactic applications are defined as semantic applications (Tarski). This derivation mimics Danvy's rational deconstruction of Landin's SECD machine. The converse derivation (closure conversion, CPS transformation, and defunctionalization) is documented in John Reynolds's article "Definitional Interpreters for Higher-Order Programming Languages", which is the origin of the CEK machine and was subsequently identified as a blueprint for transforming compositional evaluators into abstract machines as well as vice versa.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1340505274 under CC BY-SA 4.0; modifications have been made.