UnifyWeaver Architecture

Core Concept

UnifyWeaver compiles Prolog predicates into efficient bash scripts, treating Prolog as a declarative specification language and bash as the execution target. The system analyzes predicate structure and recursion patterns to generate optimized streaming implementations.

Module Organization

src/unifyweaver/
├── core/
│   ├── template_system.pl
│   ├── stream_compiler.pl
│   ├── recursive_compiler.pl
│   ├── constraint_analyzer.pl
│   ├── semantic_compiler.pl
│   ├── optimizer.pl
│   ├── firewall.pl
│   ├── preferences.pl
│   └── advanced/
│       ├── advanced_recursive_compiler.pl
│       ├── call_graph.pl
│       ├── scc_detection.pl
│       ├── pattern_matchers.pl
│       ├── tail_recursion.pl
│       ├── linear_recursion.pl
│       ├── tree_recursion.pl
│       ├── mutual_recursion.pl
│       ├── multicall_linear_recursion.pl
│       └── direct_multi_call_recursion.pl
├── runtime/
│   └── wam_runtime.pl
└── targets/
    ├── r_target.pl
    ├── go_target.pl
    ├── rust_target.pl
    ├── python_target.pl
    ├── csharp_target.pl
    └── wam_target.pl

template_system.pl

Provides a flexible template rendering engine with file-based, cached, and generated source strategies.

stream_compiler.pl

Compiles non-recursive predicates into bash streaming pipelines.

recursive_compiler.pl

Acts as the main dispatcher. It analyzes a predicate, classifies its recursion pattern, and delegates compilation to the appropriate module (either stream_compiler or advanced_recursive_compiler). It also orchestrates the control plane logic.

semantic_compiler.pl

Generic semantic search compilation interface. Provides declare_semantic_provider/2 for registering provider configurations and compile_semantic_call/4 for dispatching to target-specific code generators via multifile semantic_dispatch/5 hooks. Supports per-target provider selection, hardware-aware device fallback, and a fallback provider mechanism.

constraint_analyzer.pl

Manages predicate constraints (e.g., unique, unordered) and determines the required deduplication strategy.

firewall.pl

Enforces security policies for backend and service usage. It validates compilation requests against defined rules.

preferences.pl

Manages layered configuration preferences, guiding the compiler on which implementation to choose from permitted options.

advanced_recursive_compiler.pl

Orchestrates the compilation of complex recursion patterns. It uses a priority-based strategy, attempting to compile with the most specific pattern first (tail -> linear -> mutual).

Compilation Pipeline

┌──────────────────┐
│ Prolog Predicate │
└────────┬─────────┘
         │
         ▼
┌──────────────────┐
│ Get Preferences  │ (preferences.pl)
└────────┬─────────┘
         │
         ▼
┌──────────────────┐
│ Get Firewall     │ (firewall.pl)
└────────┬─────────┘
         │
         ▼
┌──────────────────┐
│ Validate Request │ (firewall.pl)
└────────┬─────────┘
         │
         ▼
┌──────────────────┐
│ Classify Pattern │ (recursive_compiler.pl)
└────────┬─────────┘
         │
         ▼
┌──────────────────────────────────┐
│ Optimize Goals (Codd Phase)      │ (optimizer.pl)
└────────────────┬─────────────────┘
                 │
         ├────────────────────────┐
         │                        │
         ▼                        ▼
┌──────────────────┐      ┌───────────────────────────┐
│ Non-Recursive    │      │ Recursive                 │
│ (stream_compiler)│      │ (advanced_recursive_compiler) │
└────────┬─────────┘      └───────────┬───────────────┘
         │                            │
         │                            ▼
         │                  ┌───────────────────────────┐
         │                  │   Try Advanced Patterns   │
         │                  │  (tail -> linear -> multicall -> direct_multi_call -> fold -> tree -> mutual -> general) │
         │                  └───────────┬───────────────┘
         │                              │
         └───────────────┬──────────────┘
                         │
                         ▼
┌──────────────────────────────────┐
│ Analyze Constraints & Options    │ (constraint_analyzer.pl)
└────────────────┬─────────────────┘
                 │
                 ▼
┌──────────────────────────────────┐
│ Select & Render Template         │ (template_system.pl)
└────────────────┬─────────────────┘
                 │
                 ▼
        ┌──────────────────────────────┐
        │  Target Code (bash/R/etc.)   │
        └──────────────────────────────┘

Prolog Predicate: The process starts with the Prolog predicate you want to compile (e.g., ancestor/2).
Get Preferences: The system retrieves and merges preferences (runtime, rule-specific, global defaults) to determine the desired compilation strategy.
Get Firewall: The system retrieves the firewall policy for the specific predicate.
Validate Request: The compilation request (target backend, services, options) is validated against the firewall policy. If validation fails, compilation is halted.
Pattern Analysis: The main recursive_compiler inspects the predicate to classify its pattern (non-recursive, simple recursion, or a candidate for advanced compilation).
Goal Optimization (The "Codd" Phase): The optimizer module reorders rule bodies to prioritize ground unifications and filters (comparisons). This ensures that generators are constrained as early as possible, minimizing intermediate result sets. This phase is only active if the unordered(true) constraint is satisfied (which is the default).
Strategy Selection & Dispatch:
- If the predicate is non-recursive, it is handed off to the stream_compiler.
- If the predicate is recursive, it is passed to the advanced_recursive_compiler.
Advanced Pattern Matching: The advanced compiler attempts to match the predicate against its known patterns in priority order: tail recursion, linear recursion, multi-call linear recursion, direct multi-call recursion (clause-analysis approach), fold pattern, tree recursion, mutual recursion (via SCC detection), and finally general recursion (with visited-set cycle detection).
Constraint Analysis: The compiler queries the constraint_analyzer to fetch any constraints for the predicate (e.g. unique(true)).
Template Rendering: Based on the analysis, the compiler selects an appropriate Bash code template and uses the template_system to generate the final script.
Bash Script: The final output is a complete, executable Bash script or function.

Control Plane

The Control Plane is a new architectural layer that provides declarative control over the compiler's behavior, separating critical security policy from flexible implementation choice.

Firewall

The Firewall enforces hard security and policy boundaries. It uses rules to define:

Allowed Execution Backends: Which primary target languages (e.g., bash, python) can be used.
Allowed Services: Which external services (e.g., sql, llm) can be invoked.
Denied Backends/Services: Explicitly forbidden options.

Preferences

The Preference system guides the compiler on which implementation to choose from the options permitted by the Firewall. It allows developers to specify:

Preferred Order: The order in which to try different backends or services.
Optimization Goals: Hints like speed or memory to influence code generation.
Service Mode: Whether to use embedded or remote services.

For more detailed information, refer to the CONTROL_PLANE.md document.

Generated Code Structure

For Facts (Binary Predicates)

declare -A parent_data=(
    ["alice:bob"]=1
    ["bob:charlie"]=1
)

parent() {
    local key="$1:$2"
    [[ -n "${parent_data[$key]}" ]] && echo "$key"
}

parent_stream() {
    for key in "${!parent_data[@]}"; do
        echo "$key"
    done
}

For Simple Rules

grandparent() {
    parent_stream | parent_join | sort -u
}

parent_join() {
    while IFS= read -r input; do
        IFS=":" read -r a b <<< "$input"
        for key in "${!parent_data[@]}"; do
            IFS=":" read -r c d <<< "$key"
            [[ "$b" == "$c" ]] && echo "$a:$d"
        done
    done
}

For Transitive Closures

ancestor_all() {
    local start="$1"
    declare -A visited
    local queue_file="/tmp/ancestor_queue_$$"
    
    echo "$start" > "$queue_file"
    visited["$start"]=1
    
    while [[ -s "$queue_file" ]]; do
        > "$next_queue"
        while IFS= read -r current; do
            parent_stream | grep "^$current:" | while IFS=":" read -r from to; do
                if [[ -z "${visited[$to]}" ]]; then
                    visited["$to"]=1
                    echo "$to" >> "$next_queue"
                    echo "$start:$to"
                fi
            done
        done < "$queue_file"
        mv "$next_queue" "$queue_file"
    done
}

Design Principles

1. Stream Everything

Data flows through pipelines rather than materializing in memory.

2. Bash Associative Arrays

Fast O(1) lookups for facts and visited tracking.

3. BFS over DFS

Prevents stack overflow and enables cycle detection in transitive closures.

4. Template Separation

Bash generation logic separated from Prolog analysis logic.

5. Composition

Generated bash functions can be sourced and composed in larger scripts.

6. Multifile Target Delegation

Each advanced recursion module declares a multifile predicate for code generation (e.g., compile_tree_pattern/6, compile_tail_pattern/9). The core module contains only pattern detection and the bash code generator clause. Target plugins (e.g., r_target.pl) register their own clauses for the multifile predicate, keeping target-specific code out of the core. This pattern allows adding new targets without modifying core modules.

% In core module (e.g., tree_recursion.pl):
:- multifile compile_tree_pattern/6.
compile_tree_pattern(bash, ...) :- generate_bash_code(...).

% In target plugin (e.g., r_target.pl):
:- multifile tree_recursion:compile_tree_pattern/6.
tree_recursion:compile_tree_pattern(r, ...) :- generate_r_code(...).

Testing

Each core module includes built-in tests:

?- test_template_system.
?- test_stream_compiler.
?- test_recursive_compiler.

Tests generate example scripts in output/ directory that can be executed directly.

Future Extensions

Implemented

Mutual recursion via SCC detection
Tail recursion optimization to loops
Multiple backend support (R, Go, Rust, Python, C#, WAM) via multifile target delegation
Tree recursion, multi-call linear recursion, and direct multi-call recursion patterns
WAM Hub: Symbolic abstract machine target for complex unification and backtracking fallback

Planned

External template file support (currently templates are auto-generated)

Under Consideration

Static analysis for optimization hints
Parallel execution strategies
Incremental compilation
Query planning for complex joins

Constraint System

Overview

UnifyWeaver uses a constraint annotation system to control deduplication behavior for compiled predicates. The system supports two orthogonal constraint dimensions:

unique - Whether to eliminate duplicate results
unordered - Whether result order matters

Defaults

Explicit defaults: unique=true, unordered=true

Rationale:

Most Prolog queries don't care about duplicate order
Matches typical Prolog behavior where result order is implementation-dependent
Efficient: allows use of sort -u instead of hash tables
Easy to override for temporal/ordered data

Constraint Declaration Syntax

Pragma-style (recommended):

:- constraint(grandparent/2, [unique, unordered]).
:- constraint(temporal_query/2, [unique, ordered]).
:- constraint(allow_duplicates/2, [unique(false)]).

Programmatic:

declare_constraint(grandparent/2, [unique, unordered]).
declare_constraint(temporal_query/2, [unordered(false)]).

Shorthand:

unique expands to unique(true)
unordered expands to unordered(true)
ordered expands to unordered(false)

Deduplication Strategies

The compiler selects the deduplication strategy based on constraints:

unique	unordered	Strategy	Bash Implementation
true	true	`sort -u`	`...
true	false	Hash dedup	`declare -A seen` with order-preserving loop
false	*	No dedup	Direct pipeline output

Sort -u (unique + unordered):

grandparent() {
    parent_stream | parent_join | sort -u
}

Hash dedup (unique + ordered):

temporal_query() {
    declare -A seen
    base_pipeline | while IFS= read -r line; do
        if [[ -z "${seen[$line]}" ]]; then
            seen[$line]=1
            echo "$line"
        fi
    done
}

No dedup (unique=false):

allow_duplicates() {
    base_pipeline
}

Runtime Overrides

Runtime options take precedence over declared constraints:

% Declare as unordered
declare_constraint(my_pred/2, [unique, unordered]).

% Override at runtime to be ordered
compile_predicate(my_pred/2, [unordered(false)], Code).
% Result: Uses hash-based deduplication

Changing Global Defaults

% Change defaults to preserve order
set_default_constraints([unique(true), unordered(false)]).

% All undeclared predicates now use hash dedup by default
compile_predicate(new_pred/2, [], Code).

Implementation

Module: constraint_analyzer.pl

Manages constraint declarations
Provides constraint queries
Determines deduplication strategy

Integration: stream_compiler.pl

Queries constraints for each predicate
Merges with runtime options
Generates appropriate bash code

Tests:

constraint_analyzer.pl:test_constraint_analyzer/0 - Unit tests
test_constraints.pl:test_constraints/0 - Integration tests

Examples

Default behavior (sort -u):

% No declaration needed - uses defaults
compile_predicate(grandparent/2, [], Code).
% Generates: ... | sort -u

Temporal/ordered data:

:- constraint(event_sequence/2, [unique, ordered]).
compile_predicate(event_sequence/2, [], Code).
% Generates: declare -A seen with order-preserving dedup

Allow duplicates:

:- constraint(all_paths/2, [unique(false)]).
compile_predicate(all_paths/2, [], Code).
% Generates: no deduplication

In Progress / Known Gaps

References

Stream Processing: Unix pipeline philosophy
BFS for Graphs: Standard graph algorithm adapted for transitive closure
Template Rendering: Mustache-style interpolation
Prolog Semantics: SLD resolution adapted to procedural execution

FilesExpand file tree

ARCHITECTURE.md

Latest commit

History