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

Implementation Notes (flowlog.c)

This document summarizes the main internal components of the Flowlog engine in flowlog.c.

Parser and program representation

• Source is parsed into a pl_program containing:
  • Clauses grouped by predicate indicator (name/arity)
  • Operator overrides (op/3) stored as pl_op_overrides
  • Per-program Prolog flags (ISO flags + Flowlog’s non-ISO parallel flags)

The parser supports ISO term syntax, quoted atoms, lists, operators, and the ISO read_term/3 / write_term/3 option set used by tests.

Operator parsing follows a small disambiguation rule that matters for some control constructs:

• Op(...) (no whitespace) is parsed as a functor call.
• Op (...) (with whitespace) is parsed as a prefix operator applied to a grouped term/goal.

For example, \+ (A -> B) parses as negation of an if-then goal, while \+(A -> B) is treated as a functor call and requires extra parentheses around A -> B.

Program loading is deterministic:

• The CLI and REPL both load a complete program into an in-memory pl_program.
• The solver runs queries against a snapshot of that program state (with controlled updates via the ISO dynamic database predicates).

Terms and environments

Flowlog represents terms as a tagged union:

• atoms
• integers
• floats
• variables (scoped)
• compound terms (functor + arity + args)

Bindings live in a persistent environment structure (pl_env) with parent links (copy-on-write style) so backtracking can cheaply fork environments.

To keep variable dereferencing fast even with parent-linked environments, each clause-instantiation frame records the “introduced scope”, and variable lookup stops once that scope is reached (older frames cannot contain bindings for a scope that did not yet exist). The unifier also opportunistically caches deep ancestor bindings into the current env frame to reduce repeated parent-chain scans in pure recursive workloads.

Flowlog also maintains a small amount of call metadata (predicate indicator, depth, flags) used for:

• stack traces (debug)
• SIGINFO status reporting
• parallelism heuristics (depth cutoffs, OR-par nesting)

Unification

• Standard ISO unification with optional occurs-check (controlled by occurs_check flag).
• Term comparison and variant checking are implemented for:
  • indexing
  • bagof/3 / setof/3 grouping
  • tabling (call-by-variant)

Execution engines

Flowlog provides three execution engines that share the same parser, program representation, built-ins, error model, and indexing. The default engine is wamvm.

1) Interpreter (interp / tree)

The interpreter is a direct solver (closer to a “tree-walking” engine than a compilation pipeline):

• Parsing produces term trees and a pl_program containing predicates and their clauses (plus operator overrides and flags).
• A query is represented as a list of goal terms.
• The solver walks goals left-to-right:
  • built-ins dispatch directly (with a cached built-in id stored on parsed terms for common cases)
  • user predicates select candidate clauses (using indexing when available), then:
    1. standardize-apart / instantiate the clause into fresh variables
    2. unify the call with the clause head
    3. solve the clause body goals
• Backtracking is implemented by exploring candidate clauses and alternatives explicitly; environments are persistent so branching can cheaply fork.

This engine supports the full feature set, including:

• dynamic database updates (assert*/1, retract/1, …)
• tabling
• occurs-check mode
• conservative AND-parallelism (when enabled)

2) WAM-lite (wam)

The WAM-lite engine is a fast fallback/alternative engine and is intended to reduce per-goal overhead for common pure/static ISO code.

In broad terms it:

• Executes goals using a compact WAM-like machine state (trail + per-scope variable cells).
• Uses the same program indexing to choose candidate clauses quickly.
• Handles backtracking by unwinding a trail of bindings rather than cloning persistent environments.

The interpreter remains available as a reference engine and for debugging, but the WAM-lite engine aims to execute the full feature set directly (including dynamic database predicates, tabling, and occurs-check).

To detect what engine actually ran a query from within Prolog, use:

?- current_prolog_flag(flowlog_engine_active, Engine).

Parallelism and the engines

• OR-parallelism is implemented for all engines: each worker runs the chosen engine on an independent alternative chunk/job.
• Conservative AND-parallelism is implemented by the interpreter and WAM-lite engines (as a conservative “safe prefix” scheduler). The WAMVM engine currently does not schedule AND-par inside compiled bodies.

3) WAM-VM (wamvm)

wamvm is the default engine mode and runs user-defined clause bodies on a small bytecode VM (see WAM_ROADMAP.md).

In broad terms:

• Clause bodies are compiled to a compact instruction stream (currently CALL and PROCEED).
• Execution uses an explicit frame stack and an explicit choicepoint stack (used for ;/2, multi-clause predicates, and a few key generators such as select1/3).
• The VM shares Flowlog’s existing term representation, unifier, built-ins, indexing, and dynamic database machinery with wam.

Performance notes:

• For deep search workloads that create many small nondeterministic choicepoints (e.g. n-queens), wamvm keeps select1/3 nondeterminism inside the VM (as a choicepoint) in the non-OR-par path, avoiding per-alternative continuation reconstruction.
• Wide choicepoints still use Flowlog’s OR-par chunk/job splitting for multicore scaling (and allow ordered vs unordered commits depending on the parallel profile).
• In OR-par mode, WAMVM select1/3 chunks are executed via an internal generator goal ($select1_range/5) so each chunk runs as a single VM invocation, and chunk jobs reuse the already-compiled WAMVM program code (no per-chunk rebuild).
• OR-par worker threads reuse VM scratch buffers (frame/choicepoint/snapshot arrays) to reduce malloc/free overhead across many chunk executions.

Fallbacks:

• When flowlog_engine=wamvm, Flowlog first checks whether the loaded program/query is supported by the VM.
• If unsupported features are present, Flowlog falls back to the WAM-lite engine (unless FLOWLOG_WAMVM_REQUIRE_VM=1 is set, in which case it errors instead). This includes tabling (:- table/1) and any goals not yet supported by the VM’s conservative support check.
• For low-overhead VM profiling, set FLOWLOG_PROFILE_WAMVM=1 to print snapshot/call counters at the end of a query.

Conformance note:

• The current WAMVM engine passes the INRIA ISO suite in VM-only mode (FLOWLOG_WAMVM_REQUIRE_VM=1). A dedicated target exists to keep this true: make test-inria-wamvm-vmonly.

Predicate selection and indexing

Flowlog uses multiple indexing layers:

• predicate-level lookup by functor/arity
• first-argument indexing for common shapes
• deeper indexing for selected structures where beneficial

Indexing is designed to be safe under dynamic database updates by using epoching and snapshots.

Indexing is a performance feature, not a semantic one:

• Clause order and logical meaning remain the same; indexing only accelerates candidate selection.
• When in doubt (dynamic predicates, complex patterns), Flowlog can fall back to clause scanning.

Dynamic database

ISO database predicates (including asserta/1, assertz/1, retract/1, abolish/1, clause/2) are implemented with:

• reader/writer coordination
• predicate snapshotting for safe concurrent enumeration

Tabling

Flowlog supports call-by-variant tabling for declared predicates:

:- table(path/2).

Internally, each tabled predicate maintains:

• subgoals keyed by variant
• answer tries/vectors
• completion state per SCC

Tabling runs under both engines. While tabling is active, OR-parallelism is currently disabled to keep the table state single-threaded. Tabled predicates are also treated as AND-par unsafe (they can create observable search/answer effects).

OR-parallelism (choicepoints)

OR-parallelism runs independent alternative ranges concurrently:

• Workers claim “chunks” of alternatives from a shared work object.
• Ordered mode commits results in classic order.
• Unordered mode commits results as soon as they are available.

Cancellation:

• Cuts and uncaught exceptions propagate a cancellation flag so sibling workers can stop early.

I/O:

• In ordered mode, Flowlog can delay committing output from parallel chunks to reduce interleaving.
• In unordered mode, output can arrive out of order (by design).

AND-parallelism (safe goal subsets)

AND-parallelism is used for limited “safe” cases:

• deterministic goals
• disjoint variable sets
• no visible I/O or global state

Flowlog performs a conservative analysis and only parallelizes when it can preserve ISO-visible semantics.

REPL and terminal I/O

The REPL is implemented directly in flowlog.c:

• When stdin/stdout are TTYs, it enables a small line editor using termios raw mode.
• History is persisted to ~/.flowlog_history by default (configurable via FLOWLOG_HISTORY_FILE).
• Ctrl‑C interrupts the current query without exiting the process.
• Ctrl‑T prints a status report (BSD SIGINFO).