Reifying Program Execution for Search and Inference

This direction is split into other directions: closure-based search state management. Its last version stays readable and citable here.

Version 1 of 131 papers40 conceptsfrozen 2026-10-04

Standard computer programs are typically executed as a linear sequence of operations managed by a call stack. While efficient for deterministic tasks, this "one-way street" of execution is a prison for Artificial Intelligence. To search for solutions, reason about uncertainty, or plan in complex environments, an agent must be able to pause, backtrack, and explore multiple futures simultaneously.

The core insight across decades of research—from early AI languages to modern probabilistic frameworks—is that we can escape the stack by reifying control flow. By transforming procedural code into a manipulatable data structure, such as a tree of continuations or a state machine, we allow an external controller to treat a running program as a searchable object.

Decoupling State from Control

The journey toward flexible AI control began with the realization that the "stack" model conflates two different things: where the program is (control) and what it knows (environment). In A Model for Control Structures for Artificial Intelligence Programming Languages, Daniel G. Bobrow proposed moving beyond simple stacks to a tree-like structure of "frames." By decoupling variable access from control transfers, Bobrow showed that a program's execution state could be frozen and resumed, enabling coroutines and backtracking within a single unified framework.

This idea was formalized in MAGMA-LISP: A "Machine Language" For Artificial Intelligence, where Carlo Montangero and colleagues treated the entire control state as a persistent snapshot. In this "machine language," the execution continuation is a first-class object. This allows researchers to implement sophisticated search policies without being restricted by the language's built-in execution logic.

Turning Programs into Search Trees

How do we practically turn a linear script into a searchable tree? The most common mechanism is Continuation-Passing Style (CPS). In CPS, functions never "return" in the traditional sense; instead, they take an extra argument—a "continuation"—representing the rest of the computation.

This transformation is powerful because it makes the future of the program explicit. As Oleg Kiselyov and Chung-chieh Shan demonstrate in Monolingual Probabilistic Programming Using Generalized Coroutines, using delimited continuations allows a program to be reified into a search tree. When the program hits a stochastic choice, it suspends. An external inference engine can then capture that state and resume it multiple times with different values, effectively exploring the probabilistic state space.

This mechanism is the engine behind modern Probabilistic Programming Languages (PPLs). As explained in An Introduction to Probabilistic Programming by Jan-Willem van de Meent and colleagues, CPS allows a "forward" simulator to be transformed into an "inverse" reasoning engine. By pausing at every random choice, the program provides a standardized interface for an inference controller to manage its state.

Scaling Through Selective Transformation

While powerful, full CPS transformation is computationally expensive due to constant closure allocations. Recent work has focused on making this reification more efficient. Daniel Lundén and David Broman introduced selective continuation-passing style, which uses static analysis to identify only the specific program points that require suspension (like resampling). This allows the majority of the code to run at native speeds while still providing the "hooks" necessary for complex inference.

This efficiency is critical for domain-specific applications. For instance, TreePPL uses partial CPS to allow evolutionary biologists to define phylogenetic models as programs, where the compiler automatically generates the machinery for branching and execution checkpoints. Similarly, the EnCompass framework by Zhening Li and Armando Solar-Lezama applies CPS to Python-based AI agents, enabling them to perform tree searches over their own execution paths with minimal developer overhead.

Flattening into State Machines

In some contexts—such as logic programming, robotics, or encrypted computation—the goal isn't just to branch, but to transform complex recursive logic into a format that a restricted "solver" can understand. This often involves "flattening" the program into a Finite State Machine (FSM).

Malcolm Ryan demonstrated in Efficiently Implementing GOLOG with Answer Set Programming that compiling high-level robot control logic into an FSM prevents the "computational explosion" of recursive grounding. By replacing nested logical terms with simple state transitions, the planning process becomes orders of magnitude faster.

This flattening is also essential for Verifiable Computation and Fully Homomorphic Encryption (FHE). In these domains, programs must be represented as static arithmetic circuits. Riad S. Wahby and colleagues showed in Buffet that nested loops and dynamic control flow can be unrolled into a flat state machine, allowing C-style logic to run within the rigid constraints of a circuit. Similarly, Christopher W. Fletcher used path levelization to decouple the call stack from operations, enabling recursive algorithms to run on encrypted data in Compilation Techniques for Efficient Encrypted Computation.

Why It Works

The common thread across these papers is the shift from execution as a process to execution as a data structure. Whether it is Chris Mellish using CPS to implement Prolog backtracking or Christopher H. Lin mapping procedural code to POMDPs for optimal planning, the mechanism remains the same:

  1. Capture: Use CPS or state-machine compilation to "freeze" the program's progress and environment.
  2. Reify: Represent that frozen state as a first-class object (a continuation or a state).
  3. Manipulate: Allow an external algorithm (a searcher, a solver, or an inference engine) to decide when and how to resume those states.

By reifying execution, we transform a rigid script into a flexible map, allowing AI systems to navigate the vast space of possible computations.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_reifying_program_execution_for_search_an_c2b68a99,
  title = {Reifying Program Execution for Search and Inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/reifying-program-execution-for-search-and-inference/rdr_c2b68a994d7c4a1ea94dad0d77510a58},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_reifying_program_execution_for_search_an_c2b68a99_v1,
  title = {Reifying Program Execution for Search and Inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/reifying-program-execution-for-search-and-inference/rdr_c2b68a994d7c4a1ea94dad0d77510a58/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}