^ ^                 ^ ^
=(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.

Navigation: flowlog.c uses SECTION NN and SUBSECTION NN.N headings. When you want to jump to the implementation of a topic described here, search for the corresponding section heading. The full section map lives in DEVELOPMENT.md.

Code references (section markers in flowlog.c):

• Parser and operators: SECTION 10
• Term representation and packed strings: SECTION 05 and SECTION 11
• Unification and term equality: SECTIONS 12/14/15
• Integers and arithmetic core: SUBSECTION 15.2
• Term ordering: SECTION 16
• Builtins and solver dispatch: SECTIONS 22/23/24
• WAMVM bytecode model and VM runtime: SECTIONS 18/24
• Tabling: SECTION 20
• Parallel runtime and jobs: SECTIONS 07/21

Parser and program representation

• Source is parsed into a pl_program containing (SECTION 10 and SECTION 05.4):
  • 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 (SUBSECTIONS 10.4/10.5):

• 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 (SECTION 25):

• 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 (SUBSECTION 05.2):

• atoms
• integers
• floats
• variables (scoped)
• compound terms (functor + arity + args)
• packed strings (PSTR): internal compact list-of-chars representation (see PACKED_STRINGS.md) (SECTION 11)

Integers and arithmetic

Flowlog uses a two-tier integer representation to keep small arithmetic fast while supporting unbounded ISO integers:

• Small integers live directly in pl_term as SLO (machine word).
• When parsing or arithmetic overflows SLO, values promote to pl_bigint (heap-allocated, base-2^32 limbs).
• Bigints are normalized (no leading zero limbs; sign in -1/0/+1) and canonicalized back to small ints when they fit.
• Bigint multiplication uses schoolbook for small limb counts and Karatsuba for larger operands; exponentiation uses exponentiation-by-squaring with a specialized squaring fast path (switching to Karatsuba at large sizes).

This makes current_prolog_flag(bounded,false) true without penalizing common small-integer code paths. For the full layout and algorithm notes, see ARITHMETIC.md.

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

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 (SECTION 14).

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

• 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) (SECTIONS 14/15).
• Term comparison and variant checking are implemented for (SECTIONS 16/20):
  • 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 (SECTIONS 22/23/24). The default engine is wamvm (SECTION 25).

1) Interpreter (interp / tree)

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

• Parsing produces term trees and a pl_program containing predicates and their clauses (plus operator overrides and flags) (SECTIONS 10/25 and SECTION 05.4).
• 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 (SECTIONS 13/20/14):

• 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 (SECTION 23).

In broad terms it:

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

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 (SECTIONS 22/23/24):

?- 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 (SECTION 21).
• 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 (SECTION 23).

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) (SECTIONS 18/24; default in SECTION 25).

In broad terms:

• Clause bodies are compiled to a compact instruction stream (currently CALL and PROCEED) (SECTION 18).
• 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) (SECTION 24).
• The VM shares Flowlog’s existing term representation, unifier, built-ins, indexing, and dynamic database machinery with wam (SECTIONS 05/11/12/13/14/15).

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 (SECTION 24).
• 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) (SECTION 21).
• 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) (SECTION 24).
• OR-par worker threads reuse VM scratch buffers (frame/choicepoint/snapshot arrays) to reduce malloc/free overhead across many chunk executions (SECTION 24).

Fallbacks:

• When flowlog_engine=wamvm, Flowlog first checks whether the loaded program/query is supported by the VM (SECTION 24).
• 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 (SECTION 24 and SECTION 20).
• For low-overhead VM profiling, set FLOWLOG_PROFILE_WAMVM=1 to print snapshot/call counters at the end of a query (SECTION 24).

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 inria-wamvm-vmonly.

Predicate selection and indexing

Flowlog uses multiple indexing layers (SECTION 13):

• 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 (SECTION 13).

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 (SECTION 13):

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

Tabling

Flowlog supports call-by-variant tabling for declared predicates (SECTION 20):

:- 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 (SECTION 20 and SECTION 21). Tabled predicates are also treated as AND-par unsafe (they can create observable search/answer effects) (SECTION 20 and SECTION 23).

OR-parallelism (choicepoints)

OR-parallelism runs independent alternative ranges concurrently (SECTION 21):

• 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 (SECTION 21).

I/O:

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

AND-parallelism (safe goal subsets)

AND-parallelism is used for limited “safe” cases (SECTION 23):

• 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 (SECTION 23).

REPL and terminal I/O

The REPL is implemented directly in flowlog.c (SECTION 26):

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