| author | Alan Dipert
<alan@dipert.org> 2026-11-11 04:41:04 UTC |
| committer | Alan Dipert
<alan@dipert.org> 2026-11-11 04:41:04 UTC |
| parent | 962feecc4f0f3c612b2ca94f51745b349ccc1a99 |
| README.md | +0 | -4 |
| doc/compiler.md | +0 | -78 |
| doc/nanopass.md | +0 | -111 |
| doc/tutorial.md | +0 | -542 |
diff --git a/README.md b/README.md index 07f3c80..608dd15 100644 --- a/README.md +++ b/README.md @@ -38,8 +38,6 @@ The region supports a defined subset of Clojure: See the [language reference](doc/language.md) for the supported forms and their semantics. The [algorithm examples](examples/blacktide/algorithms.clj) show partitioning and parsing. Blacktide makes no general speedup guarantee. -For an executable tour of the compiler, read [Mutable Locals in Clojure, the Hard Way](doc/tutorial.md). - ## Use Requires Clojure 1.12.6 and JDK 17 or later. Clone the [public repository](https://tailrecursion.com/repos/r/blacktide.git/): @@ -77,6 +75,4 @@ To narrow or reproduce a test run: - Pass test namespace names to `clojure -M:test` for a targeted run. - At a test REPL, call a `defspec` function with a trial count and `:seed`, for example `(generated-nested-loops 1000 :seed 161803)`. -See the [compiler architecture](doc/compiler.md) and [nanopass guide](doc/nanopass.md) for implementation contracts and extension guidance. - Copyright © 2026 Alan Dipert. Distributed under the [MIT License](LICENSE). diff --git a/doc/compiler.md b/doc/compiler.md deleted file mode 100644 index 21b0ba8..0000000 --- a/doc/compiler.md +++ /dev/null @@ -1,78 +0,0 @@ -# Compiler architecture - -Blacktide represents each compiler stage as immutable Clojure data. Languages defined with `com.tailrecursion.nanopass` describe that data; passes transform it. Compiler namespaces and intermediate representations are internal. - -Typed Clojure checks production pass bodies during development. Ordinary library use does not load the checker. Namespace docstrings state each pass's contract. - -For a walkthrough with actual inputs, intermediate data and generated code, see [Mutable Locals in Clojure, the Hard Way](tutorial.md). - -## Pipeline - -- [`compiler/languages.clj`](../src/com/tailrecursion/blacktide/compiler/languages.clj): all grammars. -- [`compiler/passes/`](../src/com/tailrecursion/blacktide/compiler/passes/): transformations and their helpers. -- [`compiler.clj`](../src/com/tailrecursion/blacktide/compiler.clj): the executable pipeline and backend choice. - -| Stage | Responsibility | -| --- | --- | -| Source | Expand macros in order. Assign unique lexical identities, record source JVM facts and enforce the supported subset. Determine loop representations without repeating expansion. | -| Classification | Preserve analyzed loops without DSL effects and native keyword calls. Make lowered loop representations and primitive source-local reads explicit. | -| Normalization | Lower sequential and parallel assignments and collections. Prepare conversions and save operands in evaluation order. | -| Graph | Lower branches and case dispatch, resolve outer labels and check destinations and definite initialization before simplifying control flow. | -| Backend | Fold literal branches, compute liveness and recover structured control with shared joins. Prove numeric values, choose safe primitive storage, lower numeric operations and compact safe intermediates. Allocate the original graph for the dispatcher when structured recovery is ineligible. | -| Emission | Emit Clojure that preserves conversions and construction sites. Preserve the Object result boundary at exits without taking a tail loop out of tail position. | - -`compiler/compile-form` orchestrates source analysis and lowering: - -```text -Bound → Classified → Assigned → Collections - → Prepared → Ordered → Symbolic → CFG -``` - -The linear driver uses ordinary `->` composition of unary stages. Each tree language has a `Compilation` nonterminal: a `[supply tree]` pair containing the immutable fresh-name supply and that language's `Expr`. Stage entry points live beside their recursive processors. They use `pipeline/map-value` to preserve the supply or `apply` to pass both components to a processor that allocates names. Graph construction consumes the pair and returns a graph. - -Typed Clojure checks each stage's input and output, including the tree inside `Compilation`. Incompatible language transitions are type errors; semantic ordering constraints within the same language still require tests. Recursive processors keep their own precise arguments and results. - -The outer bindings enter as one lexical scope. `Native` contains analyzed subtrees without DSL operations. Both backends start with the validated CFG; each allocates slots for the edges it will emit: - -```text -Dispatcher: CFG → Machine → Code -Structured: CFG → Machine → Numeric → Planned → Joined - → Represented → Lexical → Compact → Code -``` - -`numeric` recognizes numeric runtime calls and implicit Java numeric conversions, retaining their original signatures. Control recovery uses that graph without numeric value proofs. Once it succeeds, `value-facts` analyzes the `Numeric` graph to produce `Analysis`: scalar facts across assignments and backedges, including long values held in boxes. `storage` combines those facts with the recovered tree to choose representations after accounting for consumers, copies and observable identity. Dispatcher fallback skips value inference. `lexical` makes loop arguments explicit. `numeric-lower` implements the proven equivalences using host operations and ordinary control flow. `compact` simplifies safe intermediates. Emission applies the Object result boundary at public exits and leaves join values internal. - -Inference and lowering share `numeric-rules`. Knowing the operands' values is insufficient: their original overload determines overflow, conversion and reference-return behavior. - -| Numeric surface | Treatment | -| --- | --- | -| Checked and unchecked arithmetic; ordered and numeric comparisons | Use primitive overloads when their semantics agree. Preserve generic subtraction's separate negation and addition. | -| Promoting arithmetic and integral division | Primitive inputs may still produce a `Number`, including BigInt or Ratio. Do not infer a fixed result width. | -| Floating division, quotient and remainder | Preserve the original NaN handling, zero checks and exception behavior. | -| `min`/`max` and `=` | Preserve selected references, signed-zero ties and NaN identity. Selected results inherit their possible input origins. | -| Bit operations | Specialize proven integral values; retain the original rejection of other numeric categories. | -| Numeric casts and Java parameters | Preserve checked/unchecked conversions, narrowing order and exception behavior. Explicitly widen numeric operands where Clojure would otherwise box them. Java parameter conversion's additional `Number` check remains required for unknown inputs. | -| `clojure.math`, primitive arrays and explicit JVM arithmetic | Keep source signatures and conversions; primitive results already participate in value inference. | -| Arbitrary precision, unknown inputs and ordinary Var calls | Keep generic operations and Var semantics. Dynamic decimal precision and rounding remain the runtime's responsibility. | - -Specialization is conservative: incompatible value classes, observable boxes and unsupported control-recovery shapes can prevent it. Literal boxes are only re-created when their identity is guaranteed by the small-Long cache. This does not promise allocation-free code or a speedup for every region. The dispatcher retains the original calls. - -Backend selection keeps its branching and shared analyses explicit. Compaction returns each simplified subtree with its free-read counts, avoiding repeated analysis of unchanged bodies. Emitters complete their compiler work before returning generated forms; quoted source data remains opaque. - -Language derivation describes how grammars relate. It does not set pass order: `Symbolic` extends `CFG`, which extends `Machine`, while lowering visits `Symbolic`, then `CFG`, then `Machine`. - -## Runtime boundaries - -Assignments, normalization and graph construction are pure. Locals become lexical bindings and loop parameters, never mutable cells. A generated `RT.box(Object)` is an identity operation that preserves an inference boundary; its appearance alone does not imply allocation. - -Control recovery must not duplicate Java method values, functional-interface adapters or keyword lookup sites. Keyword calls with effectful targets save the cache thunk before evaluating the target. - -The `runtime.KeywordSite` helper implements the native cache protocol. An internal macro allocates each site during final Clojure analysis. The helper targets JDK 17 and is bundled in JARs. - -## Extend the compiler - -1. Change the language and affected passes. Prefer a compiler-local transformation over new nanopass machinery. -2. Add coverage for the source semantics or invariant. For generated tests, use fixed seeds, shrinking and an independent model or ordinary Clojure as the reference. Backend comparisons supplement those independent checks. -3. Run `bin/check` from the repository root. - -The check runner discovers compiler source namespaces. It registers language and pass contracts from their metadata, so new files need no registration list. diff --git a/doc/nanopass.md b/doc/nanopass.md deleted file mode 100644 index 0c8a217..0000000 --- a/doc/nanopass.md +++ /dev/null @@ -1,111 +0,0 @@ -# Nanopass library - -The nanopass library defines languages and passes over immutable Clojure data. A language describes the data's shape; a pass transforms data or computes a result. Definitions use Typed Clojure syntax without loading the checker. - -## Define a language - -A nonterminal is a named grammar type, such as `Expr`. When a language is derived, references to local nonterminals are rebound recursively to the derived language: - -```clojure -(require '[com.tailrecursion.nanopass :as np] - '[typed.clojure :as-alias t]) - -(np/deflanguage Source - {Compilation (t/HVec [t/Int Expr]) - Expr (t/U (t/HMap :mandatory {:op ':literal :value t/Any} :complete? true) - (t/HMap :mandatory {:op ':negate :value Expr} :complete? true))}) - -(np/derive-language Core Source - {:remove {Expr #{:negate}} - :add {Expr [(t/HMap :mandatory {:op ':subtract :left Expr :right Expr} - :complete? true)]}}) -``` - -Language descriptions are immutable values. Derivation accepts three operations: - -| Option | Effect | -| ---------- | ------------------------------------------------- | -| `:remove` | Remove tagged productions from a nonterminal. | -| `:add` | Add tagged productions to a nonterminal. | -| `:replace` | Replace or add a complete nonterminal definition. | - -Structural types support `U`, closed keyword-field `HMap`, fixed `HVec`, `Vec`, `Map`, `Set`, and `Option`. Use explicit `HMap`/`HVec` constructors rather than quoted collection shorthand. The `clojure.core.typed` spelling is also accepted. - -Other types are opaque terminals. They cannot contain local nonterminal references. Quoted singleton data and `Val`/`Value` payloads stay untouched. Declare complex polymorphic terminal types as external aliases. - -Tagged productions require an `:op` field with a singleton keyword type. For example, `':negate` identifies the production removed above. - -## Define a pass - -Write clauses for productions that change. The library generates structural traversal for unchanged productions: - -```clojure -(np/defpass lower {:from [Source Expr] :to [Core Expr]} - [node] - :negate {:op :subtract - :left {:op :literal :value 0} - :right (lower (:value node))}) -``` - -Automatic clauses require matching fields and structural containers. Removed productions and incompatible fields need explicit code. A generated bottom-type guard lets the checker detect missing cases. Use `macroexpand-1` to inspect the generated code. - -## Pass options and recursive processors - -| Option | Meaning | -| --- | --- | -| `:from [Language Nonterminal]` | Input grammar and nonterminal. | -| `:to [Language Nonterminal]` | Output grammar and nonterminal; may instead be an explicit result type. | -| `:processors {Binding lower-binding}` | Functions that transform other nonterminals. | -| `:args [ContextType]` | Types of leading arguments, forwarded unchanged by generated traversal. | -| `:body true` | Supply one ordinary expression instead of tagged clauses. | - -Group mutually recursive processors with `np/defpasses`. Each entry uses `defpass` syntax without the macro name. See the [recursive traversal example](../test/com/tailrecursion/nanopass/passes.clj). - -Expansion produces one lexical `letfn` group. Its functions are exported with individual signatures. The checker checks every body, and the group is redefined as a unit. - -Write explicit clauses when lexical context changes. Passes may return results other than trees, including state/result tuples. - -Use qualified aliases such as `languages/Core-Expr` in `:args` and explicit result types. Aliases used only for checking need not exist as runtime Vars. - -## Compose passes - -Use ordinary `->` to compose unary stage entry points. A `Compilation` nonterminal packages auxiliary state with the tree; derivation rebinds its `Expr` to each language. Recursive processors need not share the stage interface. - -In this example, the state is an integer counter. `pipeline/map-value` adapts the existing `lower` processor, preserving the counter: - -```clojure -(require '[com.tailrecursion.nanopass.pipeline :as pipeline]) - -(np/defpass lower-stage - {:from [Source Compilation] :to [Core Compilation] :body true} - [compilation] - (pipeline/map-value lower compilation)) - -(-> [0 {:op :negate :value {:op :literal :value 7}}] - lower-stage - second) -;; => {:op :subtract :left {:op :literal :value 0} -;; :right {:op :literal :value 7}} -``` - -For a processor that consumes or updates state, the entry point can use `(apply processor compilation)`. A stage can also leave the pair representation, for example by returning a control-flow graph. Keep branching and shared analysis results explicit with ordinary `let` and `if`. - -The helper preserves distinct types for state, input and output. Register its signature with `(np/ann-passes pipeline/map-value)` when checking a client. - -## Traversal rules - -Structural traversal: - -- Preserves metadata and optional-field presence, including present nil values. -- Shares unchanged fields and leaves quoted payloads opaque. -- Treats maps and sets structurally. Use vectors and explicit clauses when order or scope has semantic significance. - -## Check languages and pass bodies - -1. In an annotation-only namespace, require `typed.clojure` and call `(np/ann-languages Source Core)`. This generates aliases `Source-Expr` and `Core-Expr` in the languages' defining namespace. -2. Register `(np/ann-passes lower lower-stage pipeline/map-value)` in the same checking-only namespace. -3. Check the implementation namespace with `typed.clojure/check-ns-clj`. - -Ordinary language loading does not register types. Generated signatures state the contracts; function bodies must also be checked. Blacktide's check runner discovers its compiler languages and passes and registers them automatically. - -Run `bin/check` from the repository root to check both bodies and contracts. diff --git a/doc/tutorial.md b/doc/tutorial.md deleted file mode 100644 index eb86858..0000000 --- a/doc/tutorial.md +++ /dev/null @@ -1,542 +0,0 @@ -# Mutable Locals in Clojure, the Hard Way - -Hey, so, I've been thinking about mutable local variables in Clojure. Is that OK? Hear me out. - -The Clojure situation has been explained to me. I'm totally down with the philosophy. Stable identities, immutable values, first-class state management. A more civilized, decomplected age. But I gotta level with you. Sometimes I have these intrusive thoughts about mutating local variables. I'll be reading an imperative algorithm in pseudocode, Java or C, and—please don't tell anyone about this—I'll think: man, it would be pretty sweet to port this directly without translating it into atoms or `loop`/`recur` and whatnot. - -I mean, under the covers, the JVM certainly has no inherent moral objection to overwriting a [local-variable slot](https://docs.oracle.com/javase/specs/jvms/se25/html/jvms-2.html#jvms-2.6.1). Clojure's own compiler even reuses those slots to _implement_ `loop` and `recur`. But I'm not allowed to assign to an ordinary lexical local myself? That heady stuff is only for the elite class of compiler writers, I guess? Is it ungrateful of me, as a mere user, to not be entirely satisfied with the privilege of supplying replacement values to approved recursion points? - -Here's an example of the kind of stuff I'd like to write on occasion. This function counts inversions in a vector: pairs where an earlier element is greater than a later one. - -```clojure -(require '[com.tailrecursion.blacktide :refer [loophole setq psetq label goto]]) - -(defn inversions [xs] - (loophole [n 0] - (dotimes [i (count xs)] - (dotimes [j i] - (when (> (nth xs j) (nth xs i)) - (setq n (inc n))))) - n)) - -(inversions [3 1 2 1]) -;; => 4 -``` - -Nothing crazy, just setting a happy little variable `n` inside nested loops. I'm still here, by the way. Nothing terrible happened. - -But if you find yourself warming to these shenanigans, then I have some good news. This is a real thing that can be done, all thanks to the `loop`/`recur` constructs I just finished griping about. You see, [`recur`](https://clojure.org/reference/special_forms#recur) evaluates its arguments, rebinds the loop locals, and starts the loop body again. In [Clojure's compiler](https://github.com/clojure/clojure/blob/clojure-1.12.6/src/jvm/clojure/lang/Compiler.java#L7156-L7227), that becomes argument evaluation followed by local-variable stores and a jump. A jump. A freaking `GOTO` of yore! We'll be wanting that too, more in a sec. - -Anyway, those local-variable stores under the hood are the keys to the kingdom. We can write assignments where we want them, then compile them into ordinary Clojure that does the updating for us, via `recur`. We can automate the mental gymnastics we usually perform when translating an imperative algorithm. - -A macro can turn our assignments and jumps into the right combination of lexical bindings, loops, and `recur` forms, and Clojure can do the rest. No atoms, arrays or other mutable reference cells to hold our locals, and no changes to Clojure's compiler. - -Doing this for a useful subset of Clojure turns out to involve writing a small compiler. Apparently I'm willing to do that. The result is Blacktide and its `loophole` macro. **Mutable local variables (and goto!) to the people!** Allow me to give you the tour. - -## The language - -The `loophole` macro introduces mutable lexical locals, with two assignment forms: - -- `setq` evaluates and assigns pairs sequentially, returning the last value. It's named after Common Lisp's `setq`, and distinct from `set!` to avoid confusion. -- `psetq` evaluates all right-hand sides before writing the targets, in pair order, and returns nil. The `p` stands for parallel, as in "parallel assignment." Also lifted from Common Lisp. - -Both work in expressions. For example: - -```clojure -(loophole [x 1 y 2] - (psetq x y y x) - [(setq x (+ x 10)) y]) -;; => [12 1] -``` - -There are also two control-flow forms: - -- `(label name)` establishes a jump target in the outer sequence of expressions. -- `(goto name)` transfers control to an explicitly written label in the same region. - -Falling through the body evaluates its final expression. To leave early, write a label and jump to it: - -```clojure -(loophole [i 0 sum 0] - (label again) - (when (= i 10) - (goto done)) - (setq sum (+ sum i) - i (inc i)) - (goto again) - (label done) - sum) -;; => 45 -``` - -## A state machine - -If you've used [core.async's `go` macro](https://clojure.org/news/2013/06/28/clojure-clore-async-channels#_go_blocks_and_ioc_threads), you've already used a compiler inside a macro. Its state-machine implementation rewrites the block so a channel operation such as `<!` can park and later resume, preserving the local values and the point where execution should continue. - -`loophole` uses the same broad technique: analyze a lexical region, rewrite its control flow, and emit Clojure. Here the purpose is assignment and jumps. `loophole` runs synchronously on the calling thread and returns the body result; `go` returns a channel. Both transformations have to preserve lexical bindings and evaluation order as they rearrange control flow. - -One way to compile the body is to turn it into a [control-flow graph](https://www.cs.cornell.edu/courses/cs4120/2026sp/notes.html?id=traces), or CFG. Its nodes are _basic blocks_: sequences of operations with one entry point and no internal branches at this level of representation. Each block ends with a _terminator_ that jumps, chooses a successor, returns, or throws. The graph's edges are the possible transfers between blocks. - -We can represent a CFG with a single `loop` and `case`. A loop binding named `pc`, our _program counter_, holds the ID of the block to execute. The other bindings carry values between blocks. The `case` is a _dispatcher_: it selects the block named by `pc`. - -Here is a hand-written dispatcher for the preceding example: - -```clojure -(loop [pc 0 i 0 sum 0] - (case pc - 0 (if (= i 10) - (recur 2 i sum) - (recur 1 i sum)) - 1 (let [sum (+ sum i) - i (inc i)] - (recur 0 i sum)) - 2 sum)) -;; => 45 -``` - -A compiler's _backend_ turns its internal description of a program into output code. Blacktide has a dispatcher backend and a _structured_ backend, which reconstructs Clojure loops and conditionals where the graph permits. It chooses between them before emitting Clojure. - -The pipeline works through these steps; we'll unpack them below: - -```text -Expand macros, resolve bindings and determine JVM types - ↓ -Rewrite assignments and make evaluation order explicit - ↓ -Control-flow graph and jump resolution - ↓ -Check initialization and decide what survives each edge - ↓ -Recover loops and conditionals, or use a dispatcher - ↓ -Ordinary Clojure → Clojure compiler → JVM -``` - -### Small passes, explicit languages - -The [pipeline](compiler.md) follows the [nanopass approach](https://nanopass.org/): many small transformations, with explicit input and output languages. In Clojure terms, a transformation pass is a function from one immutable data representation to another. An analysis pass computes facts about that data. A _language_ specifies which node shapes are allowed at a particular stage and how they can nest. - -The representations here are ordinary Clojure maps and vectors. These are _intermediate representations_, or IRs: data describing the program between source and output. Each tree node's `:op` identifies its kind; other fields hold its operands, bindings or body. - -_Lowering_ rewrites a richer construct into simpler operations. The assignment pass takes `Classified` to `Assigned`, replacing both assignment forms with individual `:write` nodes. For parallel batches, it introduces bindings to save all right-hand-side values before writing. - -Later passes can work with individual writes without understanding `setq` and `psetq`. The [language definitions](../src/com/tailrecursion/blacktide/compiler/languages.clj) express that contract: `Assigned` removes both assignment forms and adds `:write`. - -Blacktide's [nanopass library](nanopass.md) generates code to walk unchanged node kinds and derives [Typed Clojure](https://github.com/typedclojure/typedclojure) types from the language descriptions. Development checks verify pass bodies against those contracts. A pass can still produce a beautifully well-typed wrong answer, so we also need tests of the program's behavior. - -Andy Keep's [Writing a Nanopass Compiler](https://www.youtube.com/watch?v=Os7FE3J-U5Q), from Clojure/conj 2013, introduces the approach with a small Scheme-to-C compiler. His paper with R. Kent Dybvig, [A Nanopass Framework for Commercial Compiler Development](https://andykeep.com/pubs/np-preprint.pdf), describes the framework and its use in Chez Scheme. - -### Inspecting the stages - -The remaining examples use `stages` to run the pipeline and retain intermediate results, and `readable` to shorten generated names and omit internal bookkeeping from their display. All definitions are below. Evaluate them once if you're following along; otherwise, continue to the examples and their results. - -<details> -<summary>REPL definitions for inspecting the compiler</summary> - -```clojure -(require '[clojure.pprint :refer [pprint]] - '[clojure.walk :as walk] - '[com.tailrecursion.blacktide.compiler :as compiler] - '[com.tailrecursion.blacktide.compiler.passes.source :as source] - '[com.tailrecursion.blacktide.compiler.passes.boundaries :as boundaries] - '[com.tailrecursion.blacktide.compiler.passes.assignment :as assignment] - '[com.tailrecursion.blacktide.compiler.passes.collections :as collections] - '[com.tailrecursion.blacktide.compiler.passes.prepare :as prepare] - '[com.tailrecursion.blacktide.compiler.passes.order :as order] - '[com.tailrecursion.blacktide.compiler.passes.lower :as lower] - '[com.tailrecursion.blacktide.compiler.passes.transfers :as transfers] - '[com.tailrecursion.blacktide.compiler.passes.graph :as graph] - '[com.tailrecursion.blacktide.compiler.passes.emit :as emit]) - -(defn stages [form] - (let [ctx {:locals {} :macro-env {} - :markers {#'loophole :loophole #'setq :setq #'psetq :psetq #'label :label #'goto :goto} - :outer? true :transfer? true :recur nil :statement? true :tail? false - :site {:form form :file nil :line nil :column nil}} - [supply bound] (source/parse-scope {:prefix "demo" :next 0} ctx true (vec form)) - classified (boundaries/classify bound) - [supply assigned] (assignment/lower supply classified) - constructed (collections/normalize assigned) - prepared (prepare/prepare constructed) - [supply ordered] (order/normalize supply prepared) - symbolic (lower/compile-graph supply ordered) - cfg (-> symbolic transfers/resolve-program graph/validate) - machine (graph/allocate cfg)] - {:bound bound :ordered ordered :cfg cfg :machine machine - :dispatcher (emit/program-form machine) - :code (compiler/compile-program cfg)})) - -(defn readable [value] - (walk/postwalk - (fn [x] - (let [fields (when (map? x) (set (keys x)))] - (cond - (symbol? x) - (if-let [[_ n] (re-matches #"demo__(\d+)__.*" (str x))] - (with-meta (symbol (str "v" n)) (meta x)) - (if (re-matches #"pc__\d+" (str x)) 'pc x)) - - (and fields (every? fields [:site :jvm :node])) (:node x) - (and fields (every? fields [:id :mutable? :external?])) (:id x) - :else x))) value)) -``` - -</details> - -The helper assumes the form's locals are bound inside `loophole`. It can still call functions in the current namespace. Evaluate the original stage values; `readable` produces display data. Generated names may differ. - -To keep the intermediate output manageable, let's trace a smaller example: summing the numbers below ten. - -## 1. Macroexpansion - -First, save the input as `sum-form`. Quoting lets us hand it to the compiler without executing it: - -```clojure -(def sum-form - '(loophole [x 0] - (dotimes [i 10] (setq x (+ x i))) - x)) -``` - -We can inspect one [macro expansion](https://clojure.org/reference/macros) directly: - -```clojure -(pprint (macroexpand-1 '(dotimes [i 10] (setq x (+ x i))))) -``` - -```text -(clojure.core/let - [n__6111__auto__ (clojure.core/long 10)] - (clojure.core/loop - [i 0] - (clojure.core/when - (clojure.core/< i n__6111__auto__) - (setq x (+ x i)) - (recur (clojure.core/unchecked-inc i))))) -``` - -This is one expansion, so `let`, `loop` and `when` are still present. The source pass continues expanding macros as it analyzes their children. It also handles Clojure's _inline expansions_, where operations such as `+` become direct Java calls during compilation. That explains the JVM operations we'll see later. - -At first this looks like a job for `macroexpand-1` and a sufficiently enthusiastic tree walk. Then somebody names a local `when`. A lexical binding can shadow a macro name, and macros may inspect [`&env`](https://clojure.org/reference/macros#_special_variables), the map describing locals visible at the call site. Blacktide's source pass expands forms while discovering bindings, in the caller's namespace. It recognizes `setq`, `goto` and the other forms belonging to our little language before their macros can report an outside-region error. Quoted data stays data. - -Macroexpansion and lexical resolution therefore happen together. I'm separating them here to explain the jobs, not describing two independent walks over the source. - -## 2. Lexical resolution - -You already use lexical scope whenever nested `let` forms bind the same name. _Lexical resolution_ is the compiler working out which binding each use refers to; Bob Nystrom's [Resolving and Binding](https://craftinginterpreters.com/resolving-and-binding.html#static-scope) walks through the problem. Here, we record that answer with unique binding identities. - -Run the passes and keep the analyzed tree in `bound`: - -```clojure -(def compilation (stages sum-form)) -(def bound (readable (:bound compilation))) - -[(get-in bound [:bindings 0 :local]) - (get-in bound [:body :forms 0 :bindings 0 :local]) - (get-in bound [:body :forms 0 :body :forms 0 :bindings 0 :local])] -;; => [v0 v1 v3] -``` - -These are the three source bindings: - -| Display ID | Source binding | Role | -| --- | --- | --- | -| `v0` | `x` | Mutable local introduced by `loophole`. | -| `v1` | `n__6111__auto__` | Immutable limit introduced by `dotimes`. | -| `v3` | `i` | Loop binding updated by the original `recur`. | - -The loop itself has identity `v2`. Its `recur` records that target explicitly: - -```clojure -(def source-loop (get-in bound [:body :forms 0 :body :forms 0])) -(pprint (get-in source-loop [:body :forms 0 :then :forms 1 :target])) -``` - -```text -{:id v2, :bindings [v3]} -``` - -This matters because the generated program may have a different enclosing loop. Simply copying the original `recur` into the generated loop could give it the wrong target. The compiler resolves binding identities and recursion targets before lowering them into graph operations. - -The source pass also enforces label placement. Once all labels have been found, a later pass resolves each `goto` to its block. An undefined target is an error, even if the jump is in unreachable source. - -## 3. A-normal form - -I want an assignment's value to be usable inside a larger expression. Consider: - -```clojure -(loophole [x 0] - (+ (do (setq x 10) x) - (do (setq x 20) x))) -;; => 30 -``` - -The first operand's value must be saved before the second operand changes `x`. _Normalization_ rewrites code into a consistent shape for later passes. Here, _A-normalization_ makes evaluation order explicit with temporary bindings. Think of the compiler introducing `let` bindings to name intermediate results. Matt Might's [A-Normalization: Why and How](https://matt.might.net/articles/a-normalization/) gives an approachable account, with Scheme code. - -Here is the ordered tree for the addition, simplified for display by `readable`: - -```clojure -(def operands - (stages '(loophole [x 0] - (+ (do (setq x 10) x) - (do (setq x 20) x))))) -(pprint (get-in (readable (:ordered operands)) [:body :forms 0])) -``` - -```text -{:op :let, - :bindings - [{:local v1, - :init - {:op :do, - :forms - [{:op :do, - :forms [{:op :write, :target v0, :value {:op :literal, :value 10}}]} - {:op :local, :local v0}]}} - {:local v2, - :init - {:op :do, - :forms - [{:op :do, - :forms [{:op :write, :target v0, :value {:op :literal, :value 20}}]} - {:op :local, :local v0}]}}], - :body - {:op :host-call, - :operation - {:op :static, :class clojure.lang.Numbers, :member add, :tags nil}, - :args [v1 v2]}} -``` - -The sequential assignment pass has already turned `setq` into `:write`. The ordered bindings save 10 in `v1` before evaluating the expression that saves 20 in `v2`. The addition consumes those saved values. - -The nested `:do` nodes are real. Later passes simplify this intermediate representation. Nobody has promised it will be handsome at every stage. - -These temporary values need to be carried between blocks only if they're used across an edge. Two assignments in one straight-line expression do not, by themselves, require two program-counter states. - -For the original account, see Flanagan, Sabry, Duba and Felleisen's [The Essence of Compiling with Continuations](https://www.cs.rice.edu/~javaplt/411/24-spring/Readings/essence-retro.pdf#page=3). - -## 4. Control-flow graph - -Now return to the summation. We can ask the graph for its entry block and terminators: - -```clojure -(def cfg (:cfg compilation)) -(:entry cfg) -;; => 0 - -(pprint - (readable - (into (sorted-map) - (map (fn [[id block]] [id (:term block)])) - (:blocks cfg)))) -``` - -```text -{0 {:op :jump, :target 1}, - 1 {:op :branch, :test {:op :local, :id v32}, :yes 2, :no 3}, - 2 {:op :jump, :target 1}, - 3 {:op :jump, :target 4}, - 4 {:op :return, :value {:op :local, :id v0}}, - 5 {:op :jump, :target 4}} -``` - -Each basic block has operations in `:ops` and its final control transfer in `:term`. Here's how the blocks connect: - -```mermaid -flowchart TD - B0["0: initialize"] --> B1{"1: i < limit?"} - B1 -->|true| B2["2: update x and i"] - B2 --> B1 - B1 -->|false| B3["3: when result"] - B3 --> B4["4: return x"] - B5["5: after recur (unreachable)"] -.-> B4 -``` - -Block 5 represents work after the source `recur`. That remaining work is called a _continuation_. Since `recur` never returns, this block has no incoming edge. The graph retains unreachable blocks so Clojure syntax and JVM checks still apply. Being dead is no excuse for sloppy work. - -The original loop has become initialization, a condition-checking block—its _header_—and a _backedge_ returning to that header. This loop needs lowering because it assigns the outer `x`. Loops without our assignment or jump forms can remain ordinary Clojure within the compiler's representation. - -Notice that updating `x` and implementing the source `recur` both happen in block 2. Assignment doesn't inherently introduce a control-flow branch. Explicit `goto` forms also become edges; they don't need a separate kind of runtime jump. - -Nested loops that need lowering become cycles in the graph. The dispatcher follows edges without needing their original nesting. - -## 5. Liveness and state slots - -A value is _live_ at a block's entry if some path needs that value before replacing it. [Liveness analysis](https://www.cs.cornell.edu/courses/cs4120/2026sp/notes.html?id=livevar) tells the dispatcher which values must survive transitions. Unlike tenure, liveness requires evidence of future usefulness. - -```clojure -(def machine (:machine compilation)) -(pprint - (readable - (into (sorted-map) - (map (fn [[id live]] [id (vec (sort live))])) - (:live machine)))) -``` - -```text -{0 [], - 1 [v0 v1 v3], - 2 [v0 v1 v3], - 3 [v0], - 4 [v0], - 5 [v0]} -``` - -Each value that must survive gets a _state slot_: a binding in the dispatcher's generated `loop`. These are the binding IDs: - -```clojure -(readable (:slots machine)) -;; => [v0 v1 v3] -``` - -So `x`, the limit and `i` cross edges. The many operand temporaries used within blocks do not need state slots. - -One subtle problem concerns ordinary `let` bindings. Their storage may need to survive transitions, but moving their storage must not move their initialization. - -Here's a small program that enters the same scope twice: - -```clojure -(loophole [i 0 visits 0] - (label again) - (let [limit (do (println :enter visits) (+ i 2))] - (while (< i limit) - (setq i (inc i)))) - (setq visits (inc visits)) - (when (< visits 2) (goto again)) - [i visits]) -``` - -```text -:enter 0 -:enter 1 -[4 2] -``` - -Each visit evaluates the initializer once, at the original entry point. _Hoisting_ means moving something to an enclosing scope. Hoisting a binding's storage is not permission to run its initializer earlier, or to reuse its old value after reentry. Shadowed bindings must also keep distinct identities. - -## 6. Code generation - -Our `stages` function asks for dispatcher code as well as normal compiler output so we can inspect and execute each. Start with the dispatcher's loop bindings: - -```clojure -(binding [*print-meta* true] - (pprint (readable (second (:dispatcher compilation))))) -``` - -```text -[pc - (^{:param-tags [java.lang.Object]} clojure.lang.RT/box '0) - v0 - nil - v1 - nil - v3 - nil] -``` - -The slots start as nil. Block 0 performs the source initializers. The generated `loop*` and `let*` are _special forms_, built into Clojure's compiler; `loop` and `let` are macros that expand to them. - -The edge emitter—the function that turns an edge into Clojure—shows what happens on two transitions: - -```clojure -(pprint (readable (emit/edge-form (:slots machine) (:live machine) 1))) -(pprint (readable (emit/edge-form (:slots machine) (:live machine) 4))) -``` - -```text -(recur 1 v0 v1 v3) -(recur 4 v0 nil nil) -``` - -Every `recur` takes the same number of arguments: the program counter plus all three slots. Values that are not live at the destination are replaced by nil. Within a block, operations become sequential `let*` bindings. - -To see the complete dispatcher, evaluate `(pprint (readable (:dispatcher compilation)))`. It is considerably longer than the handwritten machine. I have achieved this without the assistance of a committee. The extra code preserves the source's conversions and value semantics. Some values can be JVM _primitives_, such as an unboxed `long`; others must be Java objects, including _boxed_ numbers. - -Now execute the original emitted form: - -```clojure -(eval (:dispatcher compilation)) -;; => 45 -``` - -The mutable local is represented by lexical bindings and a loop parameter. The macro introduces no mutable cell for `x`. Arithmetic may still allocate boxed values; this is not a general allocation-free guarantee. - -## 7. Recovering a loop - -Having carefully dismantled the loop, we would now like a loop. Here's the normal compiler output, with symbol [metadata](https://clojure.org/reference/metadata) visible so we can see the type hints: - -```clojure -(binding [*print-meta* true] - (pprint (readable (:code compilation)))) -``` - -```text -(loop* - [v0 '0 v3 '0] - (if - (^{:param-tags [long long]} clojure.lang.Numbers/lt v3 '10) - (let* - [v37 (^{:param-tags [long long]} clojure.lang.Numbers/add v0 v3)] - (recur - v37 - (^{:param-tags [long]} clojure.lang.Numbers/unchecked_inc v3))) - (^{:param-tags [java.lang.Object]} clojure.lang.RT/box v0))) -``` - -There is no program counter or dispatch. The constant limit is used directly; the loop carries the accumulator and index. All `recur` arguments are evaluated before either loop binding is rebound. - -The accumulator and index now use primitive longs. Numeric analysis proves that every update to `x` produces a long or throws on overflow; storage analysis establishes that no use needs the intermediate boxes' identities. The `:param-tags` select the primitive overloads explicitly. The exit's [`RT.box(Object)`](https://github.com/clojure/clojure/blob/clojure-1.12.6/src/jvm/clojure/lang/RT.java#L1037-L1039) keeps the macro's result typed as an Object. Returning the result may box it; the recurrence uses primitive arithmetic. Placing this boundary at the exit also keeps the loop in tail position: wrapping the whole loop in a call would make Clojure generate an extra function for it. - -Two terms help here: a _join_ is a point where control-flow paths meet, and a _loop invariant_ is a value or computation that stays the same across iterations. The backend's main jobs are: - -| Pass group | Purpose | -| --- | --- | -| Feasibility and numeric recognition | Select known branches and recognize audited numeric operations. | -| Join planning and structured recovery | Arrange shared paths and recover conditionals and loops. | -| Value facts, invariants and storage | Prove scalar values, remove loop parameters that only forward unchanged outer values, and choose storage without changing object identity. | -| Numeric lowering | Select proven primitive overloads; preserve other calls unchanged. | -| Compaction and emission | Remove safe intermediates and emit Clojure with an Object boundary at public exits. | - -The [architecture guide](compiler.md) covers these passes in detail. Graphs outside the structured backend's supported shapes use the dispatcher. A graph with nested cycles does not automatically get reconstructed as nested Clojure loops. - -Finally, compare the two emissions with the public macro and an ordinary Clojure reference: - -```clojure -[(reduce + (range 10)) - (eval sum-form) - (eval (:dispatcher compilation)) - (eval (:code compilation))] -;; => [45 45 45 45] -``` - -Which means the compiler has converted a perfectly reasonable four-line `dotimes` into a control-flow graph, computed liveness, allocated state slots, and recovered a perfectly reasonable loop before emitting it. - -All to avoid manually writing `loop` and `recur`. - -## Why bother? - -The algorithms I'm interested in have less regular control flow: binary parsers, codecs, in-place array algorithms, and algorithms with several nested loops or early exits. Translating them into Clojure can mean manually threading updated values through several levels of `loop` and `recur`. - -That can obscure an otherwise straightforward algorithm, particularly when translating existing C or Java code. The attraction of `loophole` is that it can preserve that source control-flow structure while representing the local state with lexical bindings and loop parameters. - -I'm not claiming this is more idiomatic Clojure. It plainly isn't. I just think there are places where direct assignment to local variables is useful, and I'd like it available without introducing mutable reference cells. - -The performance question is separate. Structured recovery removes dispatch for this example. It doesn't establish a general speedup over ordinary or hand-tuned Clojure. - -The boundaries matter. A _closure_ is a function that captures bindings from its surrounding scope. Capturing a mutable location is not generally interchangeable with capturing one iteration's loop binding. Function construction, including `letfn`, is excluded inside the region. Helpers defined outside it are ordinary Clojure functions. - -Likewise, jumps through `try`/`finally` would have to preserve cleanup, and Clojure [doesn't permit `recur` across a `try` boundary](https://github.com/clojure/clojure/blob/clojure-1.12.6/src/jvm/clojure/lang/Compiler.java#L7249-L7253). Exception and resource boundaries stay outside `loophole`; the [language reference](language.md) gives the exact rules. The revolution will respect `finally`. - -## Next steps - -Try changing the input to use fewer iterations, another accumulator, or an early exit. Run `stages` again, inspect the graph, and evaluate both emitted forms. For less artificial examples, see the [tokenizer, decimal parser and array partition](../examples/blacktide/algorithms.clj). - -If you want to change the compiler itself, the [architecture guide](compiler.md) locates the passes and the [nanopass guide](nanopass.md) explains their contracts. - -The peculiar thing about the idea is that nothing new is required from Clojure itself. The language already has a mechanism for updating local state. Blacktide lets me use that mechanism without organizing all my source code around it. - -I suppose this is the sort of thing that happens when you like Clojure enough to go to considerable trouble to avoid writing Java, but not quite enough to give up mutable locals. - ---- - -Adapted from [the original design sketch](https://gist.github.com/alandipert/0881611c54722eb4737c2b2ba7058077).