The CESK Machine: Control, Environment, Store, Continuation

Published Feb 18, 2026

In the first post of this series, we established continuations as the universal semantic kernel that unifies exceptions, async/await, generators, and actors. In the second post, we saw how Yin.vm makes continuations mobile by externalizing state into streams. Now we dive into the machinery that makes this possible: the CESK machine.

CESK stands for Control, Environment, Store, Continuation—the four components that fully describe the state of a running program. Unlike traditional stack‑based VMs where the call stack is an implicit, hidden runtime construct, a CESK machine makes the stack explicit as a first‑class continuation. This architectural choice enables everything that makes Yin.vm unique: queryable execution, mobile agents, and deterministic replay.

A Brief History of CESK

The CESK machine descends from the tradition of semantic semantics—the study of programming languages by constructing mathematical models of their meaning. In the 1970s, Gordon Plotkin’s LCF paper introduced the idea of a structured operational semantics (SOS), which describes program execution as a series of transitions between configurations. Later, Matthias Felleisen and Robert Hieb’s The Revised Report on the Syntactic Theory of Sequential Control and State (1992) refined the CESK machine as a concrete implementation of such semantics.

The CESK machine became a standard tool in programming‑language research because it is both simple and expressive: it can model the full lambda calculus with side effects, exceptions, and first‑class continuations. Yet for decades, CESK remained an academic formalism—a model used to prove properties, not a runtime for actual programs.

Yin.vm changes that. It takes the CESK model literally and implements it with persistent data structures, turning the abstract machine into a practical virtual machine. But Yin.vm also extends the model in a crucial way: it externalizes the state components into datom streams, making each component queryable, versionable, and mobile.

The Four Components

A CESK machine’s state is a tuple (C, E, S, K) where:

Control (C) : what is being evaluated right now—an AST node, a bytecode instruction, or a value awaiting a continuation.
Environment (E) : the current lexical bindings—a map from variable names to values (or references into the store).
Store (S) : the heap—a map from locations (addresses) to values, holding mutable data, closures, and other long‑lived objects.
Continuation (K) : the “rest of the computation”—a reified representation of the call stack, often a linked list of frames.

Together, these four components contain all the information needed to pause a computation, serialize it, move it to another machine, and resume exactly where it left off. In a stack‑based VM like the JVM or CPython, the call stack is implicit in the program counter and stack pointer; you cannot capture it without invasive instrumentation. In a CESK machine, the continuation is explicit—it’s just another piece of data.

1. Control

Control is the “what now?” of the machine. In Yin.vm’s AST‑walker backend, control is an AST map:

{:type :application,
 :operator {:type :variable, :name '+'},
 :operands [{:type :literal, :value 1}
            {:type :literal, :value 2}]}

In the register‑based backend, control is an instruction pointer (:ip) pointing into a bytecode vector. In the semantic backend, control is a datom entity ID. The key insight: control is a reference to a piece of code, not the code itself. The actual AST or bytecode lives elsewhere—in a datom stream—and control merely points to the current position.

2. Environment

Environment maps variable names to values (or store references). In Yin.vm, environments are persistent hash maps built on Clojure’s persistent data structures. When a new binding is added (let, lambda application), the environment is updated via structural sharing:

;; Initial env
env0 {}

;; After (let [x 1] ...)
env1 (assoc env0 'x 1)

;; After nested let
env2 (assoc env1 'y 2)

Because environments are immutable, they can be shared across continuations. A closure captures the environment at its creation point, but that environment never changes—new bindings create new environment maps, leaving the old ones intact for other closures.

3. Store

Store is the heap—where mutable data lives. In traditional CESK machines, the store is a mutable map updated in‑place. Yin.vm’s store is also a persistent map, but it’s rarely used directly. Instead, mutable state is represented as datom streams in DaoDB. The store becomes a local cache of stream references, not the authoritative source of truth.

This is a key departure from classic CESK: Yin.vm externalizes the store into a stream of immutable facts. A “mutation” is the addition of a new datom; the store map is just a materialized view of the stream’s current state. This makes time‑travel trivial: to roll back a mutation, you simply revert to an earlier prefix of the stream.

4. Continuation

Continuation is the reified call stack. In Yin.vm’s AST‑walker, a continuation is a linked list of frames:

{:type :eval-operator,
 :frame {:operator {:type :variable, :name '+'},
         :operands [{:type :literal, :value 1}
                    {:type :literal, :value 2}],
         :operator-evaluated? false},
 :parent nil}

Each frame records what remains to be done: evaluate an operator, evaluate an operand, evaluate a test, etc. The :parent pointer chains back to the previous continuation, forming a stack. Because continuations are immutable data structures, capturing a continuation is just taking a reference to the current continuation—no copying, no serialization overhead.

The CESK Transition Function

A CESK machine advances via a transition function δ(C, E, S, K) → (C′, E′, S′, K′). Yin.vm implements this function in each backend (AST‑walker, register, stack, semantic). Here’s a simplified version of the AST‑walker’s transition function:

(defn- cesk-transition
  [state ast]
  (let [{:keys [control environment continuation store primitives]} state
        {:keys [type], :as node} (or ast control)]
    (case type
      :literal
        (assoc state :value (:value node) :control nil)
      :variable
        (let [val (if-let [pair (find environment (:name node))]
                    (val pair)
                    (if-let [pair (find store (:name node))]
                      (val pair)
                      (or (get primitives (:name node))
                          (module/resolve-symbol (:name node)))))]
          (assoc state :value val :control nil))
      :application
        (let [frame {:operator (:operator node),
                     :operands (:operands node),
                     :operator-evaluated? false}]
          (assoc state
            :control nil
            :continuation {:type :eval-operator
                           :frame frame
                           :parent continuation}))
      ;; ... many more cases
      )))

The transition function pattern‑matches on the control node’s type and produces a new state. Notice how the continuation is extended or shrunk: for an application, we push an :eval-operator frame; when a value is produced, we pop the frame and continue with the next step.

This explicit, functional transition is what makes the CESK machine deterministic and replayable. Given the same initial state and the same transition function, execution will always follow the same path—a property that enables time‑travel debugging and secure auditing.

How Yin.vm’s CESK Differs from the Classic Model

The classic CESK machine described in academic papers assumes that all four components live together in a single machine’s memory. Yin.vm externalizes them:

Component	Classic CESK	Yin.vm CESK
Control	AST node in memory	Reference into datom stream (AST or bytecode)
Environment	Mutable map, copied on closure creation	Persistent map, structurally shared across continuations
Store	Mutable heap, updated in‑place	Materialized view of immutable datom stream
Continuation	Linked list of frames in memory	Immutable linked list; frames reference stream entities

This externalization turns the CESK machine from a self‑contained interpreter into a stream processor. The machine’s state is not the authoritative truth; the datom stream is. The CESK components become caches, projections of the stream optimized for fast stepping.

Why CESK Matters for Mobile Agents

As explained in Computation Moves, Data Stays, mobile agents need lightweight continuations. If a continuation had to carry the entire heap, migration would be prohibitively expensive. Yin.vm’s externalized store solves this: the continuation carries only references to stream positions; the data stays behind, accessible via the stream protocol.

Similarly, because environments are persistent, a closure can reference an environment that lives on another node without copying it. The environment is just a map—if the remote node needs a value, it can fetch it lazily from the stream. This is the essence of “computation moves, data stays.”

CESK in Other Continuation Machines

The previous post compared Yin.vm with Gambit Scheme and Ribbit. Gambit implements first‑class continuations via stack copying—a different technique that still captures the implicit call stack, but copies it wholesale. Ribbit’s portable VM uses a heap‑allocated stack segment. Neither adopts the explicit CESK model, which is why their continuations are heavier and harder to introspect.

The CESK model is not the only way to implement first‑class continuations, but it is the most transparent: every piece of state is exposed as data, not hidden in runtime structures.

Querying CESK State with Datalog

Because Yin.vm’s CESK components are built from datoms, you can query them with Datalog. Want to know which variables are currently in scope?

[:find ?name ?value
 :where
 [?e :env/name ?name]
 [?e :env/value ?value]]

Want to see the entire continuation chain?

[:find ?frame ?type
 :where
 [?frame :continuation/type ?type]
 [?frame :continuation/parent ?parent]]

This queryability turns debugging into a data‑exploration problem. Instead of setting breakpoints and stepping, you can ask “show me all environments where variable total is greater than 100” or “list all function calls that haven’t returned yet.”

Conclusion

The CESK machine is more than an academic curiosity; it’s a blueprint for building virtual machines that are transparent, mobile, and introspectable. Yin.vm’s implementation—externalizing control, environment, store, and continuation into datom streams—transforms the blueprint into a practical runtime that supports distributed agents, time‑travel debugging, and semantic tooling.

With CESK as the foundation, the next posts in this series will explore capability‑based security (how to secure mobile continuations) and continuation migration (how to move a running computation across the network).

Learn More

Why Continuations Are the Universal Semantic Kernel – the series starter
Computation Moves, Data Stays – how Yin.vm keeps continuations lightweight
Three Continuation Machines: Yin.vm/Yang, Gambit Scheme, and Ribbit – comparative context
Yin VM documentation – includes a section on CESK
The Revised Report on the Syntactic Theory of Sequential Control and State (PDF) – the classic CESK paper
Continuation‑passing style – the transformation that makes CESK explicit