Standard programming languages assume a linear timeline. A function calls a subroutine, pushing an execution frame onto a call stack; when the subroutine finishes, its frame is popped and destroyed forever. This Last-In, First-Out (LIFO) model works beautifully for deterministic, predictable applications.
However, artificial intelligence tasks—such as logical deduction, natural language parsing, and probabilistic modeling—rarely follow a straight line. They require exploring multiple paths, pausing to wait for new information, or backtracking when a choice hits a dead end. In a traditional linear stack, backtracking forces the programmer to either manually manage complex state variables or completely unwind and re-execute code from scratch.
The core insight of this research direction is to reify the execution state—turning the call stack and variable bindings from opaque, ephemeral runtime machinery into first-class data structures that can be frozen, copied, and resumed at will.
From Linear Stacks to Tree-Structured Environments
To understand why this approach works, we must look at how the rigid, linear stack was dismantled. In early AI applications, deterministic execution was too limiting. Daniel G. Bobrow proposed a unified formal model that replaced the linear stack with a tree of frames. By separating the access environment (how a program finds its variables) from the control flow (where the program goes next), Bobrow demonstrated that multiple execution paths could safely branch from a single parent frame without destroying local data.
Linear Stack (Standard) Tree-Structured Stack (Non-Linear)
[ Frame C ] [ Frame A ]
| / \
[ Frame B ] [ Frame B ] [ Frame C ]
| | |
[ Frame A ] (Suspended) (Active)
This architectural shift meant that when a search path was suspended, its local data remained perfectly preserved in the tree, ready to be re-entered. L. Peter Deutsch implemented a single, tree-structured stack in MicroLISP to manage both control flow and variable bindings efficiently, allowing execution frames to persist and branch as needed. Carlo Montangero et al. formalized this concept in MAGMA-Lisp, treating the entire control state and variable binding environment as a persistent snapshot. This snapshot could be frozen and resumed to implement custom, non-deterministic search policies without the rigidity of built-in backtracking.
Encapsulating the Future via Continuations
If the execution state is a tree, how do we manipulate it cleanly within a programming language? The answer lies in closures and continuations. A continuation represents "the rest of the computation" from a given point onward. In Continuation-Passing Style (CPS), functions never return in the traditional sense; instead, they accept an explicit function (the continuation) and invoke it with their result.
Erik Sandewall showed that procedure closures could encapsulate variable bindings and execution states when a logical deduction process was interrupted. These closures could be handed to a central supervisor, turning non-deterministic search branches into discrete data objects.
This mechanism allows logic and procedural code to communicate natively. As demonstrated by Chris Mellish et al., backtracking can be implemented within a procedural framework by passing a continuation representing the remaining computation to each procedure. If a goal succeeds, the continuation is invoked; if it fails, the procedure simply returns to the previous choice point. In natural language parsing, the authors of Augmenting ATNST similarly showed that saving and restoring control and variable environments is crucial for exploring alternative parsing paths when handling complex syntax.
By treating the future of a program as a function, entirely different domains can intercept and manipulate execution paths:
- Probabilistic Programming: David Tolpin et al. used CPS to intercept probabilistic operations in the Anglican language, allowing inference algorithms to pause execution and manage particles or samples.
- Automatic Differentiation: Jeffrey Mark Siskind et al. leveraged CPS to pause, serialize, and resume execution states into portable capsules, enabling sublinear-memory checkpointing during the backward pass of automatic differentiation.
Delimited Control: Slicing the Stack
While full continuations capture the entire remaining execution of a program, they can be heavy and difficult to optimize. Modern research refines this idea through delimited continuations, which capture only a specific segment of the execution stack between two boundaries: a marker (reset) and an invocation (shift).
Think of reset as establishing a boundary for a computation branch, and shift as pausing execution, slicing out the stack up to the nearest reset, and packaging that slice into a callable data structure.
[ Stack Base ] -> [ reset marker ] -> [ Frame 1 ] -> [ Frame 2 ] -> [ shift ]
\________________________/
Captured Stack Slice
Benoit Desouter et al. demonstrated the immense power of this paradigm by implementing tabling—a technique that prevents infinite loops in logic programming by memoizing intermediate results—in pure Prolog. Instead of rewriting the underlying C engine, the authors used reset and shift to gracefully pause a recursive goal when a duplicate call was detected, yielding control back to the system until new facts became available.
To make these patterns accessible in languages without native continuation support, James Koppel et al. introduced "thermometer continuations." They showed that delimited control can be simulated by replaying a computation from the beginning along a recorded execution path using standard exceptions and mutable state, lowering the barrier to entry for advanced control flow. Even in resource-constrained environments like the Internet of Things, Bruce Belson et al. noted that developers turn to macro-based control flow to simulate state persistence and non-local jumps when native compiler support is absent.
Native Virtual Machine Support
To eliminate the performance overhead of whole-program compiler transformations or macro hacks, modern runtimes introduce native primitives for stack manipulation. By treating execution states as explicit, reified data structures rather than opaque closures, a system gains the transparency required for procedural introspection, as argued by Robert Ghislanzoni et al.
This push for native efficiency has reached low-level web standards. Donald Pinckney et al. introduced Wasm/k, adding native delimited continuations to WebAssembly. By providing explicit instructions to copy or delete captured execution states, it allows high-level features like green threads and coroutines to run without massive binary bloat.
Expanding on this, Luna Phipps-Costin et al. proposed WasmFX, which uses effect handlers alongside delimited continuations. By introducing three simple instructions—cont.new (to create independent execution stacks), suspend (to capture state), and resume—the authors created a unified framework for managing diverse non-local control flows directly in the virtual machine. This evolution proves that whether implemented via 1970s Lisp frame trees or modern WebAssembly effect handlers, treating the execution stack as a manipulatable data structure remains a foundational strategy for managing complex search and control.
Key Foundational Work
Conversion of Predicate-Calculus Axioms, Viewed as Non-Deterministic Programs, to Corresponding Deterministic Programs (1973) — contributed 2 concept elements to this direction.
A Model for Control Structures for Artificial Intelligence Programming Languages (1973) — contributed 2 concept elements to this direction.
Conversion of Predicate-Calculus Axioms, Viewed as Non-Deterministic Programs, to Corresponding Deterministic Programs (1973) — contributed 2 concept elements to this direction.