I've been thinking about mutable local variables in Clojure. Hear me out.
I like Clojure's immutable values. But sometimes I'm reading an algorithm in pseudocode, Java or C, and I'd like to port it without translating its local variables into atoms or loop/recur.
Here's an example using loophole, a macro provided by my Clojure library, Blacktide. It counts inversions in a vector: pairs where an earlier element is greater than a later one.
(require '[com.tailrecursion.blacktide :refer [loophole setq 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
Clojure already offers mutable storage:
with-local-vars uses thread-local Vars, with binding lookups and boxed primitive numbers.volatile! provides a simpler mutable cell, but primitive numbers are still boxed for storage.I'd like to use ordinary JVM locals and keep primitive arithmetic where possible.
Clojure already updates JVM local-variable slots to implement loop and recur. We can use the same mechanism for our own variables.
recur evaluates its arguments, rebinds the loop locals, and starts the loop body again. Clojure's compiler emits local-variable stores and a jump. We can write assignments and jumps where we want them, then compile them into Clojure that does the updating through recur.
loophole does this for a subset of Clojure. It's a compiler inside a macro, with no atoms or changes to Clojure's compiler. Mutable locals to the people!
Let's use a smaller program so we can see the machinery:
(loophole [sum 0]
(dotimes [i 10]
(setq sum (+ sum i)))
sum)
;; => 45
loophole starts sum at zero and returns the final sum. Each setq replaces its value. First we expand dotimes and the when it introduces to expose the loop. The mutable binding and assignment remain for our compiler to handle. I've shortened the generated name and omitted clojure.core/ prefixes:
(loophole [sum 0]
(let [limit (long 10)]
(loop [i 0]
(if (< i limit)
(do
(setq sum (+ sum i))
(recur (unchecked-inc i))))))
sum)
;; => 45
With the loop exposed, we can turn the program into a control-flow graph. Each node represents a basic block: a straight-line sequence of operations ending in a jump, a conditional branch, or an exit. Each edge represents a possible transfer of control from one block to another, drawn as an arrow.
setq becomes a write inside a block, if chooses between outgoing edges, and recur leads back to the loop's test. Here is a simplified view, omitting temporary copies and the loop's discarded nil result:
flowchart TD
accTitle: Control flow of the summation loop
accDescr: Initialize sum and index to zero. While the index is below ten, add it to the sum and increment it. Otherwise return the sum.
init["sum = 0<br/>limit = long(10)<br/>i = 0"] --> test{"0: i < limit?"}
test -->|yes| body["1: sum = sum + i<br/>i = unchecked-inc(i)"]
body --> test
test -->|no| done["2: return sum"]
Now we can execute this graph with ordinary Clojure, using a loop of our own. A loop variable pc, for program counter, holds the next block's number. A case acts as the dispatcher, selecting that block.
Here is a hand-written translation, using the diagram's block numbers:
(let [limit (long 10)]
(loop [pc 0 i 0 sum 0]
(case pc
0 (if (< i limit)
(recur 1 i sum)
(recur 2 i sum))
1 (let [sum (+ sum i)
i (unchecked-inc i)]
(recur 0 i sum))
2 sum)))
;; => 45
setq is gone. In block 1, let names the updated sum and index. recur carries those values into the loop's bindings and continues at block 0. Clojure supplies the local-variable stores and the jump.
The sum is live across that jump: a later block may read it before it is overwritten. Liveness tells the compiler which values must travel between blocks. Temporaries used entirely within one block can stay in its let.
core.async's go macro also turns code into a state machine, allowing channel operations to park and resume it. Our machine implements assignment and jumps, and runs synchronously on the calling thread.
With the next block under our control, an explicit goto is a small step. Here it leaves the dotimes early:
(loophole [sum 0]
(dotimes [i 10]
(when (= i 5) (goto done))
(setq sum (+ sum i)))
(label done)
sum)
;; => 10
Here the label marks the return block. Labels belong to the region's outer statement sequence, so jumps can leave nested loops but cannot enter a nested scope halfway through its initialization. Every destination must have an explicit label.
loophole supports a bounded subset of Clojure; function creation, exception handlers and resource scopes stay outside the region. The revolution will respect cleanup.
So far, we've used setq to update a variable and discarded its result. But setq also returns the value it assigns. Put two assignments in the arguments to a function, and the first result has to survive the second write:
(loophole [x 0]
(+ (setq x 10) (setq x 20)))
;; => 30
The first argument to + is 10; the second is 20. If a transformation performs both writes and then reads x twice, it produces 40.
The first argument therefore needs a name of its own. The essential transformation looks like this, still written in the source language:
(loophole [x 0]
(let [left (setq x 10)
right (setq x 20)]
(+ left right)))
;; => 30
The compiler does this systematically before building the graph. It saves operands in evaluation order, and subsequent operations consume those saved values. This is the purpose of A-normalization: making intermediate computations and their order explicit. Matt Might's A-Normalization: Why and How explains the technique with small Scheme examples.
Introducing those temporary names brings another obligation: each binding needs its own identity, even when two locals share a name. The source recur inside dotimes must also keep its original loop target.
We've now expanded macros, preserved evaluation order, kept bindings distinct, and connected blocks. Doing all of that in one transformation would make it hard to see which step went wrong.
To keep it manageable, I use nanopass, the approach Andrew Keep and R. Kent Dybvig used to rebuild Chez Scheme's compiler. Each pass performs a small transformation between explicitly defined intermediate languages. Keep's Writing a Nanopass Compiler, from Clojure/conj, is a good introduction.
Saving operands is one of those passes. Its input language allows expressions in call arguments; its output requires references to saved locals, like left and right. Later passes can consume those arguments without having to untangle their evaluation order.
These languages describe trees of immutable Clojure maps and vectors. The nanopass machinery generates traversal code for unchanged forms and derives Typed Clojure types from the language descriptions. The type checker can reject a pass that leaves an assignment in a call argument. It runs during development, without being loaded when somebody uses loophole.
A pass can still produce a well-typed wrong answer. Saving the wrong value for left could give us 40 again.
So our generative tests build valid, bounded programs combining assignments, branches, loops, and jumps. We compare their results and recorded execution traces with an independent state model, then repeat the comparison with renamed locals, different control-flow formulations, and different ways of emitting the final Clojure. When a case fails, the generator shrinks it to a smaller valid counterexample.
The case machine gives us a general way to execute the graph. But look at the graph for our sum: test the index, update the sum, go back to the test. We've described a loop using numbered blocks. Perhaps we could just emit a loop?
That removes the need to carry a program counter and repeatedly ask case which block comes next. The test becomes an if, the backward edge becomes a recur, and the exit returns the sum. Even our added goto fits: reaching five simply takes another exit from the loop.
This is where the earlier compiler work pays off. A later pass can inspect the graph with bindings, evaluation order and jump destinations already settled. Its job is to recover ordinary loops and conditionals. It doesn't have to understand dotimes or redo assignment handling to attempt that optimization. Nanopass gives it a defined input and output, so we can improve this part without reopening every question about what the source means.
The compiler makes this choice before emitting Clojure, keeping the dispatcher when it can't safely reconstruct the control flow.
For our sum with the early exit, it emits this, with shorter local names. loop* and let* are Clojure's underlying loop and binding forms:
(loop* [sum '0 i '0]
(if (^{:param-tags [long long]} clojure.lang.Numbers/lt i '10)
(if (^{:param-tags [long long]} clojure.lang.Util/equiv i '5)
(^{:param-tags [java.lang.Object]} clojure.lang.RT/box sum)
(let* [next-sum
(^{:param-tags [long long]} clojure.lang.Numbers/add sum i)]
(recur next-sum
(^{:param-tags [long]} clojure.lang.Numbers/unchecked_inc i))))
(^{:param-tags [java.lang.Object]} clojure.lang.RT/box sum)))
Both loop variables are primitive longs. A value-analysis pass proves that each addition produces a long or throws on overflow; a separate storage pass checks that no use observes the intermediate boxes' identities. Only then does numeric lowering select the primitive overloads, spelled out here by :param-tags. The emitter gets those decisions already made.
The RT.box(Object) calls are at the exits: Clojure boxes the final long, and RT.box(Object) returns that object unchanged. The loop's arithmetic stays unboxed. Putting this boundary around the whole loop would make Clojure generate an extra function to evaluate it.
When the index reaches five, the inner if returns the sum: 10. That was our goto. We've compiled it out of existence.
Back at the inversion counter, we can write (setq n (inc n)) where the counting happens, inside the nested loops. loophole figures out the bindings and recur arguments needed to carry that value forward. Our assignment becomes the kind of update Clojure already knows how to compile.
To think, all this time, mutation was sitting inside recur, wearing a little hat that said FUNCTIONAL PROGRAMMING...
Zach Tellman’s Proteus also provides mutable locals through let-mutable and set!. It stores them in small Java objects with mutable fields, including primitive fields for longs and doubles, so it can avoid numeric boxing too. Blacktide instead transforms the control flow, carrying updated values through lexical bindings and recur.
Truth be told, this isn't my first rodeo. HyperTURBO is my earlier BASIC-inspired Clojure macro. Each numbered line becomes a function; an atom holds the program counter and variables. GOTO updates that counter, which the dispatcher consults after the line's function returns. Line numbers included at no extra charge.
To interrupt a function before it returns, you can throw something. flambard/tagbody uses this to implement Common Lisp-style tagbody: a sequence of forms with labels you can jump to. Its implementation puts each tagged section in a function. goto throws a custom Throwable carrying the destination; the dispatcher catches it and resumes there.
Farolero uses thrown signals too. A callback can jump out through intervening function calls, running finally cleanup along the way. This is a nonlocal exit. Farolero's tagbody/go implementation feeds those signals into a loop/case dispatcher and checks that an escape targets the right, still-active execution of tagbody. It also supplies block/return-from, all within a larger system of Common Lisp-style conditions and restarts: tools for reporting problems and choosing how to recover.
A jump that stays in one function gives the compiler another option. My 2020 JACL draft, §3.3.3 describes compiling Common Lisp's local GO operations into JavaScript's labeled continue. If all jumps to a TAGBODY are local, its generated try/catch disappears too. I later learned that cxxxr's Valtan already optimized local jumps, and shortened the final paper accordingly.
That's the division of labor I'd want in a fuller tagbody: use Blacktide-style compilation wherever a jump can become ordinary control flow, and reserve exception unwinding for exits through function calls. Both paths still owe us our finally blocks. Blacktide currently sticks to its compiled region.