^ ^                 ^ ^
=(o.o)=  ~byakuren  =(o.o)=
  m m                 m m

WAM Roadmap

This document is a plan for evolving the Flowlog engine (flowlog.c) towards a fuller WAM/bytecode-style execution model without giving up Flowlog’s parallel OR/AND execution model.

Status note:

• Flowlog defaults to flowlog_engine=wamvm (bytecode VM for compiled clause bodies).
• Flowlog also includes a WAM-lite execution path (selected by flowlog_engine=wam), used as a fallback and for features not yet implemented in the VM (notably tabling).
• The WAM-lite engine also supports conservative prefix AND-parallelism (flowlog_parallel_and=on) by running safe, disjoint deterministic goals concurrently and then merging their bindings left-to-right.
• The wamvm engine:
  • runs compiled clause bodies on a small bytecode VM (currently CALL/PROCEED) with an explicit frame stack and choicepoint stack
  • still shares the WAM-lite term representation, unifier, built-ins, and indexing
  • intended to grow toward fuller WAM-style compilation (notably head matching/unification bytecode)
  • passes the INRIA ISO suite in VM-only mode (FLOWLOG_WAMVM_REQUIRE_VM=1 / make test-inria-wamvm-vmonly)
• The interpreter (flowlog_engine=interp/tree) remains the “full feature” reference engine.
• This roadmap focuses on expanding WAM-lite coverage and improving compiled/VM execution while preserving parallel semantics.

Goals

• Keep ISO-visible semantics (left-to-right, depth-first) in the default “ordered” mode.
• Preserve Flowlog’s parallel profiles:
  • ordered OR-par (classic solution order)
  • unordered OR-par (fastest “any order” answers)
  • conservative AND-par (safe overlap of independent deterministic goals)
• Improve “single core” efficiency so parallelism compounds (good per-core speed and multicore scaling).

Constraints

• Single-file build remains supported (flowlog.c).
• Must interoperate with existing ISO built-ins and error handling.
• Must keep dynamic database semantics correct (asserta/z, retract, abolish, clause/2), potentially by routing dynamic predicates through the interpreter path until a compiled dynamic representation exists.

Execution model (target shape)

The intended end-state is a bytecode VM with:

• Per-thread machine state:
  • registers (X registers)
  • environment stack (Y variables / frames)
  • trail (for undoing bindings on backtracking)
  • choicepoint stack
  • heap (for structured terms; optional early phase can continue using the existing term representation)
• Per-predicate compiled code:
  • head matching/unification instructions
  • body call sequence (call, execute, proceed)
  • indexing metadata for quick clause selection

Built-ins remain “native” C functions, invoked via a fast dispatch from a call_builtin instruction.

OR-parallelism on WAM

Two viable approaches:

1. Alternative-splitting at clause entry (coarse OR-par):
   • Keep Flowlog’s existing “parallelize a choicepoint by splitting clause alternatives into jobs”.
   • Each job starts execution at a clause entry point with its own VM state, derived from a shared prefix state.
   • This is simpler and matches today’s job model, but only parallelizes at call boundaries.
2. Stack-copying choicepoint splitting (fine OR-par):
   • When a WAM choicepoint is created, allow workers to “steal” unexplored alternatives.
   • Requires copying (or incrementally copying) VM stacks to the thief.
   • Enables deeper, more automatic OR-par.

Flowlog’s flowlog_parallel_profile=fast (unordered) maps naturally to the second model (commit as soon as found). Ordered mode needs extra coordination to preserve classic answer order.

AND-parallelism on WAM

Flowlog’s conservative AND-par analysis can be preserved on WAM states:

Status: implemented in the WAM-lite engine as a conservative “safe prefix” scheduler:

• It selects a safe prefix of deterministic goals whose free-variable sets are disjoint.
• Each goal runs in an isolated cloned WAM state (in parallel jobs/workers).
• Results are merged back into the main WAM state in left-to-right goal order.
• Tabled predicates are treated as AND-par unsafe.

Incremental milestones

Milestone 1: compiled clause skeleton

• Introduce a pl_bc_pred representation (bytecode per predicate).
• Add a “compiled or interpreted” dispatch point:
  • compiled predicates run in the VM
  • others fall back to the current interpreter

Status: implemented in the wamvm engine for clause bodies (CALL/PROCEED), with a conservative support check that falls back to wam when unsupported goals are used.

Milestone 2: expand WAM-lite for common pure code

• Implement enough instructions to run common pure code:
  • call, execute, proceed
  • get_structure, unify_variable, unify_value
  • get_constant, get_integer, get_float
  • put_* instructions for argument setup

Milestone 3: backtracking + multi-clause predicates

• Implement choicepoints (try_me_else, retry_me_else, trust_me style).
• Hook into existing predicate indexing to select the initial clause quickly.

Status: implemented in wamvm via an explicit choicepoint stack (predicate-clause continuation, ;/2, repeat/0, catch/3, retract/1, and the select1/3 generator used by benchmarks). This is not yet a classic WAM try/retry/trust instruction stream.

Milestone 4: ISO integration and correctness

• Ensure:
  • cuts interact correctly with OR-par cancellation
  • exceptions propagate correctly
  • attributed variables are either unsupported (explicitly) or handled deliberately (non-ISO extension)

Milestone 5: OR-par on VM states

• Start with coarse clause-level splitting (approach #1).
• Add stack-copying splitting (approach #2) once the VM is stable.

Testing strategy

• Keep running:
  • the regression tests
  • the INRIA ISO suite
• Add focused VM tests that compare:
  • compiled vs interpreted results for the same predicate
  • ordered vs unordered answer sets where order is not observable (e.g., findall/3 with ground template)