| author | Alan Dipert
<alan@dipert.org> 2026-11-07 03:42:54 UTC |
| committer | Alan Dipert
<alan@dipert.org> 2026-11-07 03:42:54 UTC |
| parent | a6ce1167eab7b71881c4e1444462a3895e0f005d |
| doc/tutorial.md | +152 | -128 |
| examples/blacktide/tutorial.clj | +0 | -60 |
| test/com/tailrecursion/blacktide/backend_test.clj | +0 | -18 |
diff --git a/doc/tutorial.md b/doc/tutorial.md index 2d2b7cf..41988aa 100644 --- a/doc/tutorial.md +++ b/doc/tutorial.md @@ -1,18 +1,36 @@ # Mutable Locals in Clojure, the Hard Way -I've been thinking about mutable local variables in Clojure. +Hey, so, I've been thinking about mutable local variables in Clojure. Is that OK? Hear me out. -Clojure has explained the situation to us. Immutable values. Persistent data structures. A more civilized age. I like this philosophy. I would also like to increment a local variable. +The Clojure situation has been explained to me. I'm down with the philosophy. Immutable values. Persistent data structures. A more civilized, decomplected age. But 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` or monads or whatever. -The JVM has no 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 reuses those slots to implement `loop` and `recur`. You may not assign to an ordinary lexical local yourself. You may submit a complete set of replacement values to an approved recursion point. This is an important philosophical distinction. +The JVM 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). I mean, jeez, it does this for a living. Clojure's own compiler even reuses those slots to _implement_ `loop` and `recur`. But you better not dare assign to an ordinary lexical local yourself! Compiler writers only! As a mere user, you may submit a complete set of replacement values to an approved recursion point. You're welcome. Then there's functional programming's dirtiest implementation secret: wanton manipulation of that giant mutable variable otherwise known as "the stack." On the JVM it's [one per thread](https://docs.oracle.com/javase/specs/jvms/se25/html/jvms-2.html#jvms-2.5.2), with mutable frames pushed and popped as methods run. We have outsourced the sin. But I digress. -Mutable local variables to the people! +**Mutable local variables to the people!** -`loop` and `recur` work well for most iterative algorithms. The inconvenience is that `recur` can only appear in tail position, and every value that changes has to be passed explicitly to the recursion point. +`loop` and `recur` work well for most iterative algorithms. The inconvenience is that `recur` can only appear in _tail position_, where there is no further work to do in that iteration. Every loop binding needs a replacement argument, even when its value stays the same. -I would like to write this: +<details> +<summary>Try the examples in a REPL</summary> + +From a checkout: + +```sh +clojure -T:build compile-java +clojure -M -r +``` + +Load the public macros, then evaluate the Clojure blocks below in order: + +```clojure +(require '[com.tailrecursion.blacktide :refer [loophole setq psetq label goto]]) +``` + +</details> + +I would like to write stuff like this: ```clojure (loophole [x 0] @@ -22,44 +40,16 @@ I would like to write this: ;; => 45 ``` -There are several good ways to write this in Clojure already. I'm aware of them. What interests me is whether mutable locals can be implemented entirely as a macro, without storing them in atoms, arrays or other mutable reference cells, and without changing Clojure's compiler. +Huh. So Clojure already performs the assignments needed for `loop` and `recur`. Could we generalize that trick? Write assignments where we want them, then compile them into ordinary Clojure that does the updating for us? Automate the mental gymnastics I usually perform when translating an imperative algorithm? Then we could mutate our _own_ variables! -This brings us back to our earlier observation: Clojure already knows how to update JVM locals. [`recur`](https://clojure.org/reference/special_forms#recur) evaluates its arguments, rebinds the loop locals, and transfers control back to the loop header. 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. +The mechanism is already there: [`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. -If I can arrange for control-flow edges to become appropriate `recur` forms, I can carry updated values along those edges. Straight-line assignments can become sequential lexical bindings between transfers. +If a macro can turn our assignments and jumps into the right combination of lexical bindings, loops and `recur` forms, 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's `loophole` macro. This walkthrough uses the compiler that's in the repository, including its intermediate data and generated code. -## Follow along - -From a checkout, with Clojure 1.12.6 and JDK 17 or later: - -```sh -clojure -T:build compile-java -clojure -M -i examples/blacktide/tutorial.clj -r -``` - -Then enter the example namespace: - -```clojure -(in-ns 'blacktide.tutorial) -``` - -The [companion file](../examples/blacktide/tutorial.clj) imports the public macros and provides two inspection functions: - -| Function | What it does | -| --- | --- | -| `stages` | Runs the internal pipeline on a quoted, closed `loophole` form in the current namespace. Returns the bound tree, ordered tree, graph, allocated machine, dispatcher code and normal compiler output. | -| `readable` | Produces a display-only projection: generated locals become `v0`, `v1`, etc.; expression source/type wrappers are omitted and local descriptors become their IDs. | - -The compiler represents the trees and graphs below with ordinary Clojure data, mostly maps and vectors. These are _intermediate representations_, or IRs: data that passes can inspect and transform on the way from source to output. An `:op` key identifies a node's kind; its other fields describe the operands, bindings or destinations that kind needs. - -The examples were run with Clojure 1.12.6 on JDK 25. Outputs are pretty-printed; `pprint`'s trailing nil return is omitted. Generated names and internal data can change as the compiler evolves. Evaluate the original stage values, which retain all metadata, rather than copying the display projections back into the compiler. - -The helper uses an empty enclosing lexical environment. It is enough for these closed examples; the public macro also receives the caller's `&env`. - ## The language The macro is called `loophole`. It introduces mutable lexical locals, with two assignment forms: @@ -78,7 +68,7 @@ Both work in expressions. For example: There are also two control-flow forms: -- `(label name)` establishes a jump target in the outer statement sequence. +- `(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: @@ -96,9 +86,9 @@ Falling through the body evaluates its final expression. To leave early, write a ;; => 45 ``` -Labels belong to `loophole`; there is no additional body form around them. A jump can leave a nested statement body, but cannot target the inside of a lexical scope. Labels are restricted to the outer statement sequence, including transparent `do` forms. Jumps are forbidden anywhere inside operands or initializers. +Labels belong to the outer sequence of expressions in `loophole`; wrapping them in `do` doesn't change that. A jump can leave a nested `let` or loop body, but cannot enter a lexical scope such as the body of a `let`. Jumps are forbidden inside expressions supplying values to other operations—_operands_—or computing initial values for bindings—_initializers_. -The interesting part is that the body can contain ordinary Clojure constructs, including macros like `dotimes`, `when` and `while`. I don't want to implement those again. Their expansions must fit the [supported subset](language.md). Functions, `letfn`, `try` and resource-management forms belong outside the region. Calling an external function from inside it is fine. +The interesting part is that the body can contain ordinary Clojure constructs, including macros like `dotimes`, `when` and `while`. I don't want to implement those again. Their expansions must fit the [supported subset](language.md). Creating functions, using `letfn`, and handling exceptions or resources belong outside the region. Calling an external function from inside it is fine. ## A state machine @@ -106,7 +96,9 @@ If you've used [core.async's `go` macro](https://clojure.org/news/2013/06/28/clo `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), then emit a single `loop` and `case`. The graph's nodes are blocks of straight-line work; its edges describe possible transfers between them. Loop bindings hold the state; another binding, `pc`, identifies the block to execute next. +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 this 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`. Before looking at the compiler's output, here is that idea written by hand: @@ -125,29 +117,31 @@ Before looking at the compiler's output, here is that idea written by hand: This is ordinary Clojure. The program counter and state are loop bindings. No mutable reference object is needed to hold `sum`. -The current compiler has this dispatcher backend, but it can also recover structured control and emit ordinary lexical bindings and loops. It chooses a backend before emitting Clojure; it doesn't generate a dispatcher and then rewrite that generated source. +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 outline is: +The pipeline works through these steps; we'll unpack them below: ```text -Source analysis: macroexpansion, lexical resolution, JVM facts +Expand macros, resolve bindings and determine JVM types ↓ -Assignment and expression normalization +Rewrite assignments and make evaluation order explicit ↓ Control-flow graph and jump resolution ↓ -Initialization checks, liveness, state-slot allocation +Check initialization and decide what survives each edge ↓ -Structured recovery when eligible; dispatcher otherwise +Recover loops and conditionals, or use a dispatcher ↓ Ordinary Clojure → Clojure compiler → JVM ``` ### Small passes, explicit languages -The real [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 [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. -For example, assignment lowering takes two passes: +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. For example, assignment lowering takes two passes: | Pass | Input → output language | What the next pass can rely on | | --- | --- | --- | @@ -156,25 +150,89 @@ For example, assignment lowering takes two passes: Later passes can work with individual writes without having to understand the two assignment forms again. The [language definitions](../src/com/tailrecursion/blacktide/compiler/languages.clj) record that progression: `Sequential` removes `:setq` and adds `:write`; `Assigned` then removes `:psetq`. These are contracts the machinery can use. -Blacktide's [nanopass library](nanopass.md) generates traversal for matching, unchanged productions and derives Typed Clojure aliases from the language descriptions. Development checks verify pass bodies against those contracts; ordinary macro use does not load the type checker. A pass can still produce a beautifully well-typed wrong answer, so we also need semantic tests. +Blacktide's [nanopass library](nanopass.md) generates code to walk unchanged node kinds and derives Typed Clojure 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.source-values :as source-values] + '[com.tailrecursion.blacktide.compiler.passes.assignment :as assignment] + '[com.tailrecursion.blacktide.compiler.passes.cases :as cases] + '[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] + '[com.tailrecursion.blacktide.compiler.passes.host-emit :as host]) + +(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) + values (source-values/expression classified) + sequential (assignment/sequential values) + [supply assigned] (assignment/parallel supply sequential) + selected (cases/normalize assigned) + constructed (collections/normalize selected) + prepared (prepare/prepare constructed) + [supply ordered] (order/normalize supply prepared) + symbolic (lower/compile-graph supply ordered) + cfg (transfers/resolve-program symbolic) + machine (graph/analyze cfg)] + {:bound bound :ordered ordered :cfg cfg :machine machine + :dispatcher (host/box-form (emit/program-form machine)) + :code (host/box-form (compiler/compile-program machine))})) + +(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. + I'll walk through the original `dotimes` example to see what the important steps do. ## 1. Macroexpansion -The companion file defines the quoted input as `sum-form`. Quoting lets us hand it to the compiler without executing it first: +First, save the input as `sum-form`. Quoting lets us hand it to the compiler without executing it: ```clojure -(pprint sum-form) -``` - -```text -(loophole [x 0] (dotimes [i 10] (setq x (+ x i))) x) +(def sum-form + '(loophole [x 0] + (dotimes [i 10] (setq x (+ x i))) + x)) ``` -We can inspect one ordinary [macro expansion](https://clojure.org/reference/macros) directly: +We can inspect one [macro expansion](https://clojure.org/reference/macros) directly: ```clojure (pprint (macroexpand-1 '(dotimes [i 10] (setq x (+ x i))))) @@ -191,9 +249,9 @@ We can inspect one ordinary [macro expansion](https://clojure.org/reference/macr (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 recognizes Clojure's inline arithmetic expansions, which explains the JVM operations we'll see later. +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. -A naive recursive application of `macroexpand-1` isn't sufficient. A lexical binding can shadow a macro name, and macros may inspect [`&env`](https://clojure.org/reference/macros#_special_variables). Blacktide's source pass expands forms while discovering bindings, in the caller's namespace. It recognizes the DSL markers before they can expand into their outside-region errors. Quoted data stays data. +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. @@ -201,7 +259,7 @@ Macroexpansion and lexical resolution therefore happen together. I'm separating 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 actual passes and keep their results: +Run the passes and keep the analyzed tree in `bound`: ```clojure (def compilation (stages sum-form)) @@ -221,22 +279,10 @@ These are the three source bindings: | `v1` | `n__6111__auto__` | Immutable limit introduced by `dotimes`. | | `v3` | `i` | Loop binding updated by the original `recur`. | -Why no `v2`? The loop itself has an identity too: +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 (select-keys source-loop [:op :id :bindings])) -``` - -```text -{:op :loop, - :id v2, - :bindings [{:local v3, :init {:op :literal, :value 0}}]} -``` - -The source `recur` records that target explicitly: - -```clojure (pprint (get-in source-loop [:body :forms 0 :then :forms 1 :target])) ``` @@ -244,13 +290,13 @@ The source `recur` records that target explicitly: {:id v2, :bindings [v3]} ``` -This matters because the generated program may have a different enclosing loop. Leaving a source `recur` in flattened code would give it the wrong target. The compiler resolves binding identities and recursion targets before lowering them into graph operations. +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 assignment to work inside expressions, not just in statement position. Consider: +I want an assignment's value to be usable inside a larger expression. Consider: ```clojure (loophole [x 0] @@ -259,9 +305,9 @@ I want assignment to work inside expressions, not just in statement position. Co ;; => 30 ``` -The first operand's value must be saved before the second operand changes `x`. A-normalization makes that ordering 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. +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 actual ordered tree for the addition, with the source/type wrappers removed by `readable`: +Here is the ordered tree for the addition, simplified for display by `readable`: ```clojure (def operands @@ -297,15 +343,15 @@ Here is the actual ordered tree for the addition, with the source/type wrappers 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. This is an intermediate representation, before later compaction. Nobody has promised it will be handsome at every stage. +The nested `:do` nodes are real. Later passes simplify this intermediate representation. Nobody has promised it will be handsome at every stage. -A value saved this way only needs a machine state slot if it must survive a control-flow edge. Two assignments in one straight-line expression do not, by themselves, require two program-counter states. +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. -The classic paper is [The Essence of Compiling with Continuations](https://www.cs.rice.edu/~javaplt/411/24-spring/Readings/essence-retro.pdf#page=3), by Flanagan, Sabry, Duba and Felleisen. The linked copy includes the authors' later retrospective, followed by the original paper. +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 actual graph for its entry block and terminators: +Now return to the summation. We can ask the graph for its entry block and terminators: ```clojure (def cfg (:cfg compilation)) @@ -328,23 +374,7 @@ Now return to the summation. We can ask the actual graph for its entry block and 5 {:op :jump, :target 4}} ``` -A block has sequential operations in `:ops` and exactly one terminator in `:term`. The operations include saved operands and conversions, so there are more of them than a hand-drawn algorithm would suggest: - -```clojure -(into (sorted-map) - (map (fn [[id block]] [id (count (:ops block))])) - (:blocks cfg)) -;; => {0 7, 1 17, 2 23, 3 1, 4 1, 5 1} -``` - -| Block | Work | Next step | -| --- | --- | --- | -| 0 | Initialize `x`, the `dotimes` limit and `i`. | Jump to 1. | -| 1 | Read and convert operands; compare `i` with the limit. | True to 2, false to 3. | -| 2 | Add `i` to `x`, then compute and install the next `i`. | Jump to 1. | -| 3 | Supply nil as the completed `when` result. | Jump to 4. | -| 4 | Read and return `x`. | Return. | -| 5 | Unreachable continuation created after the source `recur`. | Jump to 4. | +Each basic block has operations in `:ops` and its final control transfer in `:term`. Here's how the blocks connect: ```mermaid flowchart TD @@ -353,22 +383,20 @@ flowchart TD B2 --> B1 B1 -->|false| B3["3: when result"] B3 --> B4["4: return x"] - B5["5: unreachable continuation"] -.-> B4 + B5["5: after recur (unreachable)"] -.-> B4 ``` -Block 5 has no incoming edge. The graph retains unreachable blocks so native Clojure syntax and JVM checks are not silently skipped. Being dead is no excuse for sloppy work. +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. -Structured recovery can omit harmless dead copies like this one; it falls back when doing so would lose required validation. - -The original `loop*` has become initialization, a header and a backward edge. This loop needs lowering because it assigns the outer `x`. Loops without DSL effects can instead remain native Clojure subtrees. +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. Their source nesting is no longer needed by the dispatcher, although reconstructing structured control from the graph is a separate problem. +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. +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)) @@ -388,14 +416,14 @@ A value is live at a block's entry if some path needs that value before replacin 5 [v0]} ``` -The allocated state slots are: +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 persistent state slots. Liveness is already part of the compiler, not an optimization left for later. The analysis includes retained unreachable blocks; only reachable paths undergo definite-initialization checks. +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. @@ -418,13 +446,11 @@ Here's a small program that enters the same scope twice: [4 2] ``` -Each visit evaluates the initializer once, at the original entry point. Hoisting storage is not permission to run an initializer earlier, or to reuse its old value after reentry. Shadowed bindings must also keep distinct identities. +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 -The companion file asks the dispatcher emitter for code even though this example is eligible for structured recovery. That lets us inspect and execute both paths. - -The generated dispatcher loop's binding vector is: +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] @@ -442,9 +468,9 @@ The generated dispatcher loop's binding vector is: nil] ``` -The slots start as nil. Block 0 performs the source initializers. The generated `loop*` and `let*` are Clojure special forms, rather than the macros that expand to them. +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 actual edge emitter shows what happens on two transitions: +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))) @@ -456,9 +482,9 @@ The actual edge emitter shows what happens on two transitions: (recur 4 v0 nil nil) ``` -Every `recur` has the same arity: the PC plus all three slots. Values that are not live at the destination are replaced by nil. Within a block, operations become sequential `let*` bindings. +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. It also preserves the source's JVM conversions and value semantics instead of assuming everything is a primitive long. I have achieved this without the assistance of a committee. +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: @@ -471,7 +497,7 @@ The mutable local is represented by lexical bindings and a loop parameter. The m ## 7. Recovering a loop -The normal compiler output for this example is more interesting. Here it is with symbol [metadata](https://clojure.org/reference/metadata) visible, since those hints participate in compilation: +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] @@ -502,18 +528,18 @@ The normal compiler output for this example is more interesting. Here it is with There is no program counter or dispatch. The limit lives outside the loop; the loop carries the accumulator and index. All `recur` arguments are evaluated before either loop binding is rebound. -This is actual output, not the ideal form I'd like the compiler to produce. The casts and Object boundaries are still there. In particular, [`RT.box(Object)`](https://github.com/clojure/clojure/blob/clojure-1.12.6/src/jvm/clojure/lang/RT.java#L1037-L1039) is an identity operation used to preserve an inference boundary; its appearance does not itself imply allocation. The accumulator keeps reference semantics, while the index can use primitive storage. +The casts and `Object` hints are still there. In particular, [`RT.box(Object)`](https://github.com/clojure/clojure/blob/clojure-1.12.6/src/jvm/clojure/lang/RT.java#L1037-L1039) returns its argument unchanged. Its `Object` return type keeps Clojure from treating that result as a primitive; the call itself doesn't allocate a box. The accumulator preserves object identity, while the index can use primitive storage. -The backend's main jobs are: +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 value facts | Fold literal branches and determine conservative value representations. | -| Join planning and structured recovery | Recover acyclic control or a single-header loop, subject to validation and duplication limits. | -| Invariants and storage | Move safe loop invariants out and select proven primitive storage. | -| Compaction and emission | Remove safe intermediates and emit lexical Clojure. | +| Feasibility and value facts | Select branches with known tests; determine which values can safely use primitive storage. | +| Join planning and structured recovery | Arrange shared paths and recover conditionals and loops. | +| Invariants and storage | Move safe computations whose results don't depend on the iteration out of loops; choose storage types. | +| Compaction and emission | Remove unnecessary intermediate bindings and emit Clojure. | -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. +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: @@ -531,17 +557,15 @@ All to avoid manually writing `loop` and `recur`. ## Why bother? -The example is intentionally simple. It demonstrates the transformation, not the motivation. - 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 dispatcher also shares the frontend with the structured backend, so agreement between them is useful evidence, not an independent correctness oracle. The test suite additionally uses ordinary Clojure and independent models. +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 over a mutable location is not generally interchangeable with a closure over one iteration's loop binding. Function construction, including `letfn`, is excluded inside the region. Helpers defined outside it are ordinary Clojure functions. +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`. @@ -549,7 +573,7 @@ Likewise, jumps through `try`/`finally` would have to preserve cleanup, and Cloj 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 language descriptions and type checks constrain the shapes of intermediate data. Semantic tests still have to establish evaluation order, binding behavior and the meaning of those shapes. +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. diff --git a/examples/blacktide/tutorial.clj b/examples/blacktide/tutorial.clj deleted file mode 100644 index e6c7d60..0000000 --- a/examples/blacktide/tutorial.clj +++ /dev/null @@ -1,60 +0,0 @@ -(ns blacktide.tutorial - "Inspect the closed examples in doc/tutorial.md using the internal pipeline. - Stage values are unchanged; readable produces display-only projections." - (:require [clojure.pprint :refer [pprint]] - [clojure.walk :as walk] - [com.tailrecursion.blacktide :refer [loophole setq psetq label goto]] - [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.source-values :as source-values] - [com.tailrecursion.blacktide.compiler.passes.assignment :as assignment] - [com.tailrecursion.blacktide.compiler.passes.cases :as cases] - [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] - [com.tailrecursion.blacktide.compiler.passes.host-emit :as host])) - -(def sum-form - '(loophole [x 0] - (dotimes [i 10] (setq x (+ x i))) - x)) - -(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) - values (source-values/expression classified) - sequential (assignment/sequential values) - [supply assigned] (assignment/parallel supply sequential) - selected (cases/normalize assigned) - constructed (collections/normalize selected) - prepared (prepare/prepare constructed) - [supply ordered] (order/normalize supply prepared) - symbolic (lower/compile-graph supply ordered) - cfg (transfers/resolve-program symbolic) - machine (graph/analyze cfg)] - {:bound bound :ordered ordered :cfg cfg :machine machine - :dispatcher (host/box-form (emit/program-form machine)) - :code (host/box-form (compiler/compile-program machine))})) - -(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)) diff --git a/test/com/tailrecursion/blacktide/backend_test.clj b/test/com/tailrecursion/blacktide/backend_test.clj index 746e463..19e0309 100644 --- a/test/com/tailrecursion/blacktide/backend_test.clj +++ b/test/com/tailrecursion/blacktide/backend_test.clj @@ -1,7 +1,6 @@ (ns com.tailrecursion.blacktide.backend-test "Backend decisions, primitive storage, reference identity and conversion order." (:require [clojure.test :refer [deftest is]] - [blacktide.tutorial :as tutorial] [clojure.test.check :as tc] [clojure.test.check.generators :as gen] [clojure.test.check.properties :as prop] @@ -19,23 +18,6 @@ [com.tailrecursion.blacktide.compiler.passes.lower :as lower] [com.tailrecursion.blacktide.machine-test :as m])) -(deftest tutorial-pipeline - (binding [*ns* (the-ns 'blacktide.tutorial)] - (doseq [[form expected trace] - [[tutorial/sum-form 45 ""] - ['(loophole [x 0] (+ (do (setq x 10) x) (do (setq x 20) x))) 30 ""] - ['(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]) [4 2] ":enter 0\n:enter 1\n"]]] - (let [{:keys [dispatcher code]} (tutorial/stages form)] - (doseq [compiled [form dispatcher code]] - (let [out (java.io.StringWriter.) value (binding [*out* out] (eval compiled))] - (is (= [expected trace] [value (str out)]) (pr-str form)))))))) - (defn compile-program [form mode] (binding [*ns* (the-ns 'com.tailrecursion.blacktide.backend-test)] (with-redefs [compiler/compile-program (if (= mode :dispatcher)