meme.alpha.collapsar — io.github.xpojure-lang/meme-clj 0.12.0

Declarative rewrite phases with verified termination.

A language's syntactic phases — parsing, desugaring, lowering — expressed as declarative rewrite rules. Rule sets compose with verified termination. Towers of languages collapse into flat pipelines.

Self-contained: pattern matching, substitution, rewriting, head analysis, phases, pipelines, languages. No external dependencies beyond clojure.set.

Three layers: phase — a set of rules with a computed signature (consumed/produced heads) pipeline — a sequence of phases, validated: no phase raises earlier heads language — a pipeline + a target backend

Head-eliminating phases (consumed ∩ produced = ∅) terminate by construction. Non-head-eliminating phases run with bounded iteration.

apply-rule clj/s

(apply-rule rule expr)

Try to apply a single rule. Returns the rewritten expression, or nil.

apply-rules clj/s

(apply-rules rules expr)

Try each rule in order. Returns the first successful rewrite, or nil.

collapse clj/s

(collapse name & pipelines)

Collapse a tower of pipelines into a single flat pipeline. Concatenates phases, validates the result. Throws if invalid.

expr-size clj/s

(expr-size expr)

Count nodes in an expression tree. Useful as a decreasing measure.

head-eliminating? clj/s

(head-eliminating? rules)

Is this set of rules head-eliminating? consumed ∩ produced = ∅.

inspect-phase clj/s

(inspect-phase phase)

Describe a phase: signature, verification, warnings.

inspect-pipeline clj/s

(inspect-pipeline pipeline)

Describe a pipeline: phases, signatures, validity.

make-language clj/s

(make-language lang-name pipeline target)

Create a language: a named pipeline with a target backend. The target is a function (expr -> result) — eval, codegen, emission.

make-phase clj/s

(make-phase phase-name rules)

(make-phase phase-name rules opts)

Create a phase with computed signature and verification.

opts: :max-iters — iteration bound for non-head-eliminating phases (default 100) :strategy — :bottom-up (default) or :top-only :measure — optional (fn [expr] -> number), checked to decrease each pass

make-pipeline clj/s

(make-pipeline pipeline-name phases)

Create a validated pipeline. Throws if any phase raises earlier heads.

match-pattern clj/s

(match-pattern pattern expr)

(match-pattern pattern expr bindings)

Match a pattern against an expression. Returns a bindings map {symbol value} on success, nil on failure. Same variable must match the same value (consistency).

named-rule clj/s

(named-rule rule-name pattern replacement)

(named-rule rule-name pattern replacement guard)

Create a named rule.

pattern-head clj/s

(pattern-head pattern)

Extract the consumed head symbol from a rule's pattern. Returns the head symbol if the pattern is a list with a literal symbol head. Returns nil for variable heads, non-list patterns, or empty lists.

pattern-var? clj/s

(pattern-var? x)

Is x a pattern variable like ?x — matches one expression, binds to name.

phase-signature clj/s

(phase-signature rules)

Compute the aggregate signature of a phase (set of rules).

procedural-phase clj/s

(procedural-phase phase-name f)

Create a procedural phase — an opaque transformation function. Invisible to head analysis. Use for semantic phases that can't be expressed as rewrite rules.

replacement-heads clj/s

(replacement-heads replacement)

Extract all statically-known produced head symbols from a replacement.

rewrite clj/s

(rewrite rules expr)

(rewrite rules expr max-iters)

Apply rules bottom-up to fixed point, with iteration cap.

rewrite-once clj/s

(rewrite-once rules expr)

One bottom-up pass: rewrite each node, innermost first. Returns [changed? result].

rewrite-top clj/s

(rewrite-top rules expr)

(rewrite-top rules expr max-iters)

Apply rules at top level only, to fixed point.

rewrite-trace clj/s

(rewrite-trace pipeline expr)

Trace an expression through a pipeline, returning intermediate results.

rule clj/s

(rule pattern replacement)

(rule pattern replacement guard)

(rule rule-name pattern replacement guard)

Create a rule: pattern => replacement. Optional guard predicate on bindings.

rule-signature clj/s

(rule-signature rule)

Compute the signature of a single rule. Returns {:consumes #{...} :produces #{...} :dynamic-produces? bool}

run-language clj/s

(run-language lang expr)

(run-language lang expr opts)

Run an expression through a language: pipeline then target. With {:trace true}, returns full trace.

run-phase clj/s

(run-phase phase expr)

Execute a phase to fixed point. Head-eliminating phases get a high safety cap (1000). Non-head-eliminating phases use :max-iters (default 100). If :measure is set, verifies it decreases each iteration.

run-pipeline clj/s

(run-pipeline pipeline expr)

(run-pipeline pipeline expr opts)

Execute a pipeline: each phase to fixed point in sequence. With {:trace true}, returns {:result expr :trace [...]}.

splice-var? clj/s

(splice-var? x)

Is x a splice variable like ??xs — matches zero or more, binds to name.

substitute clj/s

(substitute template bindings)

Replace pattern variables in template with values from bindings. Splice variables (??xs) are spliced into the parent sequence.

valid-pipeline? clj/s

(valid-pipeline? phases)

Does this sequence of phases form a valid pipeline?

wildcard? clj/s

(wildcard? x)

Is x the wildcard _ — matches anything, no binding.