{"article":{"slug":"a-second-futamura-projection","title":"A Second Futamura Projection","subtitle":null,"summary":"Veit Heller continues his compfuck series: after building a specializer that folds a Brainfuck interpreter away (the first Futamura projection), he works toward the second projection, specializing the specializer itself to derive a compiler, with Carp code walkthroughs.","content_type":"blog_post","language":"en","canonical_url":"https://blog.veitheller.de/A_Second_Futamura_Projection.html","author":{"name":"Veit Heller","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Veit's Blog","url":null,"listing_slug":null,"listing":null},"topics":[{"name":"compilers","slug":"compilers","url":"https://listedarticles.com/topics/compilers"},{"name":"programming-languages","slug":"programming-languages","url":"https://listedarticles.com/topics/programming-languages"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":3330,"reading_minutes":14,"published_at":"2026-11-03T00:00:00.000Z","added_at":"2026-11-04T14:09:09.848Z","updated_at":"2026-11-04T14:09:09.848Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/a-second-futamura-projection","markdown_url":"https://listedarticles.com/articles/a-second-futamura-projection.md","example":false,"citation":"Veit Heller, Veit's Blog. \"A Second Futamura Projection.\" 3 Nov 2026. https://blog.veitheller.de/A_Second_Futamura_Projection.html (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://blog.veitheller.de/A_Second_Futamura_Projection.html"},"body_markdown":"# A Second Futamura Projection\n\n[Two months ago](https://blog.veitheller.de/A_First_Futamura_Projection.html), we\nturned [compfuck](https://github.com/hellerve-pl-experiments/compfuck)\nback into an interpreter and wrote a specializer that, given a Brainfuck\nprogram, folded the interpreter away and left behind the operations we\ncouldn’t specialize. That’s the first Futamura projection, which is what\nI likened compfuck to historically in lazy shorthand. If you missed the\narticle and this whole paragraph refuses to make sense to you, start\nthere!\n\nOf course, that article was only the first step. We’re not done with\nour Origami piece.\n\nSpecifically, we ended up with a way to obtain compiled programs\nwithout writing instruction translations by hand. That’s great, but we\nstill ran the specializer on every single program, walking through the\ninterpreter’s source each time. The specializer and the interpreter were\nalways the same, though, we just had a different Brainfuck program. This\nis wasteful and we can do better.\n\nYou might also have a hunch about how to deal with this now: if part\nof the input is fixed, we can specialize. And the second Futamura\nprojection does exactly that to the specializer itself:\n\n```\ncompiler = specialize(specializer, interpreter)\ncompiler(program) = specialize(interpreter, program)\n```\n\nFig. 1: Specializing a specializer to an interpreter.\n\nWe feed the specializer to itself, with the interpreter as its known\ninput. What comes out is a program that takes a Brainfuck program and\nproduces the residual code directly, without ever executing the\ninterpreter. That’s a compiler, delightfully weird.\n\nIt might sound like a parlor trick, and it took me a while to believe\nit would produce anything sensible, even after the time it took for me\nto understand it. But it does work, and the compiler we get at the end\nlooks a lot like the one I wrote by hand years ago. Let’s see how we get\nthere.\n\n## Why our old specializer won’t do\n\nTo specialize a program, the specializer has to understand it. Our\nold specializer understood exactly one program, the interpreter. For\ninstance, it knew that `p` and `i` were static and\nthat every `if` and `let` belonged to the source\ntraversal. We decided a whole bunch of things by hand, basically making\na mini DSL for Carp-like sources.\n\nThis won’t scale to the specializer itself. It has static and dynamic\nparts mixed in a bunch of places, it calls helper functions, and its\nrecursive calls don’t all terminate if you naively unfold them. So the\nfirst step is to write a specializer that is general enough to\nspecialize itself, without tricks this time.\n\nThere is a second, sneakier problem I glossed over a bit last time,\nbecause I wasn’t quite sure yet how to solve it when I wrote that piece:\nthe old specializer evaluated static expressions by handing them to\nCarp’s `eval`. If we specialize that, the best we can do is\nleave a call to `eval` in the output, and our “compiler”\nwould still interpret pieces of the interpreter at compile time. To get\nrid of that, the specializer needs to evaluate static code itself, in a\nway that can be specialized in turn. If that doesn’t make sense yet, no\nworries. It’s easier to show than to tell.\n\nJust one more thing before we continue, though, because I want to be\nhonest: for the purposes of this tutorial, I opted not to make this an\nabsolutely generic implementation of the second Futamura projection.\nWe’ll still cut corners where it’s expedient without undermining the\nconceptual purity. I’ll also call it out when it happens.\n\n## An introspective specializer\n\nLast time, `definterpreter` stored the interpreter’s body\nas metadata. Now a macro called `remember` stores the\nparameters as well, and `defmix`—`mix` is the name\nhanded down by the forebears of this technique—does the same for the\nspecializer’s functions and collects them in a list. That list is the\nspecializer as a program. The bracket search is stored like the\ninterpreter, so the interpreter is now a program with two functions, an\ninterpreter loop and a helper function.\n\nCarp expands macros before the body gets stored, so\n`case`, `cond`, `and`, and\n`or` arrive as `if`s and\n`let`s[1](#1). Our specializer only has\nto understand `if`, `let` with a single binding,\n`quote`, function calls, and a handful of primitives. It’s\nbasically a small Lisp, and the specializer is written in it, too (sans\nthe macro’s syntactic sugar).\n\n### Which bits are static?\n\nWe keep last time’s split into static `p` and\n`i` and dynamic `t` and `h`, but\nreplace the hand-made decisions with a rule:\n\n```\n(defmix mentions? [e syms]\n  (cond\n    (symbol? e) (member? e syms)\n    (or (list? e) (array? e))\n      (if (empty? e) false (or (mentions? (car e) syms) (mentions? (cdr e) syms)))\n    false))\n```\n\nFig. 2: Does an expression use any of these variables?\n\nAn expression that doesn’t mention any *dynamic* variables can\nbe evaluated during specialization, and an expression that doesn’t\nmention any *static* variables has nothing to specialize, so we\nleave it alone. Everything else gets taken apart.\n\nThe rule is purely syntactic, so it has plenty of blind spots. An\nexpression that only mentions static variables gets run during\nspecialization even if it has side effects. Neither of our programs has\none, so we’ll leave it at that. Its semantic generalization is left as\nan exercise to the reader.\n\n### Our very own evaluator\n\nBefore we can fold things, we have to evaluate.\n\nLast time, `known` handed static expressions to\n`eval`. We need to get rid of that `eval`, though,\nso we write an evaluator in and for our small Lisp:\n\n```\n(defmix ev [prog e names vals]\n  (cond\n    (symbol? e) (List.nth vals (index-of e names))\n    (not (list? e)) e\n    (= (car e) 'quote) (cadr e)\n    (= (car e) 'if)\n      (if (ev prog (cadr e) names vals)\n        (ev prog (caddr e) names vals)\n        (ev prog (cadddr e) names vals))\n    (= (car e) 'let)\n      (ev prog (caddr e) (cons (car (cadr e)) names)\n          (cons (ev prog (cadr (cadr e)) names vals) vals))\n    (empty? (lookup (car e) prog))\n      (ev-primitive prog e names vals)\n    (memo (ev prog\n              (caddr (lookup (car e) prog))\n              (cadr (lookup (car e) prog))\n              (ev-each prog (cdr e) names vals)))))\n```\n\nFig. 3: Evaluating static code.\n\nSemantically, this is easy, but it’s a lot of `car`ing and\n`cdr`ing, so let’s go through it in turn:\n\n- If we encounter a symbol, we look up the variable for it.\n- If we encounter a non-list, we return it as is.\n- If we encounter a quoted value, we return the value.\n- If we encounter an `if`, we evaluate the condition, and\n  then evaluate the corresponding branch.\n- If we encounter a `let`, we add a new name and value, and\n  the right side also gets evaluated for good measure.\n- If we encounter a symbol that’s not in the program, we try to\n  evaluate a primitive.\n- Otherwise we evaluate the function and call `memo`. We\n  get to that in a second, it’s my favorite little hack of the whole\n  thing.\n\nLet’s check out `ev-primitive` for good measure.\n\n```\n(defmix ev-primitive [prog e names vals]\n  (cond\n    (= (car e) 'car) (car (ev prog (cadr e) names vals))\n    (= (car e) 'cdr) (cdr (ev prog (cadr e) names vals))\n    ; ... and so on, for 18 primitives\n    (= (car e) 'String.char-at)\n      (String.char-at (ev prog (cadr e) names vals) (ev prog (caddr e) names vals))\n    (macro-error (str \"unknown primitive \" (car e)))))\n```\n\nFig. 4: Applying primitives.\n\nThe primitives are what both programs need: a few list operations,\ncomparison, a bit of arithmetic, and string access. Anything else,\nincluding the specializer’s own helpers, is a function in the program\nand gets evaluated from its source. We cheat a bit here, and map this\nLisp’s operations one-to-one to Carp, which is nice, because it’s\ntrivial, but also a bit horrendous, because, well, look at the code.\n\nLast time’s bindings array is now split into `names` and\n`vals`. When we specialize the specializer,\n`names` is known and `vals` is not, so a lookup\nlike `(index-of e names)` happens ahead of time and only\n`(List.nth vals 2)` is left over. With names and values in\none list, every lookup would have to search at compile time.\n\nTo see this in action, here is the body of `ev`\nspecialized to the expression `(+ i 1)`, with `i`\nstatic:\n\n```\n(+ (List.nth vals 0) 1)\n```\n\nFig. 5: An evaluator, specialized away.\n\nThe evaluator is gone. What’s left is the expression itself, reading\n`i` from whatever slot the compiler keeps it in. The dispatch\nover primitives disappeared, because which primitive we apply is\nknown.\n\nIf you take only one thing away from this post, it should probably be\nFigure 5. It’s our whole trick! But we’re not done yet.\n\n### Walking the code\n\nThe specializer proper is called `mix` (a nod at those\nbefore us, again). It takes the program, the variables, an expression,\nand the environment (as two lists), and returns residual code:\n\n```\n(defmix mix [prog dyn e names vals]\n  (cond\n    (not (mentions? e names)) e\n    (not (mentions? e dyn)) (lift (ev prog e names vals))\n    (and (= (car e) 'if) (not (mentions? (cadr e) dyn)))\n      (if (ev prog (cadr e) names vals)\n        (mix prog dyn (caddr e) names vals)\n        (mix prog dyn (cadddr e) names vals))\n    (= (car e) 'let)\n      (mix prog dyn (caddr e)\n        (cons (car (cadr e)) names)\n        (cons (ev prog (cadr (cadr e)) names vals) vals))\n    (= (car e) 'memo) (mix-memo prog dyn (cadr e) names vals)\n    (empty? (lookup (car e) prog))\n      (mix-each prog dyn e names vals)\n    (unfold prog\n            dyn\n            (lookup (car e) prog)\n            (cdr e)\n            (cadr (lookup (car e) prog))\n            (cdr e)\n            names\n            vals)))\n```\n\nFig. 6: The specializer.\n\nAgain: quite a lot of `car`ing and `cdr`ing, so\nlet’s take it slow.\n\nThe first two lines are the rule we mentioned above. Code without\nstatic variables is returned as-is. Code without dynamic variables gets\nevaluated, and `lift` turns the value back to code, quoting\nit if necessary.\n\n`memo` is a special case that calls `mix-memo`.\nWe’ll defer it one more time.\n\nThe rest are the same branches as last time, except that an\n`if` only picks a branch if its condition is static, and\ncalls to functions in the program are unfolded. It looks quite odd, but\nif you squint, you might see the resemblance.\n\n### Unfolding and a stop condition\n\n`unfold` is the unfolding of the interpreter’s recursive\ncall we had last time, but generalized for any function in the\nprogram:\n\n```\n(defmix unfold [prog dyn f args params rest names vals]\n  (cond\n    (empty? params)\n      (let [static (static-params (cadr f) args dyn)]\n        (memo (mix prog\n                   (dynamic-params (cadr f) static)\n                   (caddr f)\n                   static\n                   (static-args prog args dyn names vals))))\n    (or (not (mentions? (car rest) dyn))\n        (= (car params) (car rest)))\n      (unfold prog dyn f args (cdr params) (cdr rest) names vals)\n    (list\n        'let\n        (array (car params)\n               (mix prog dyn (car rest) names vals))\n        (unfold prog\n                dyn\n                f\n                args\n                (cdr params)\n                (cdr rest)\n                names\n                vals))))\n```\n\nFig. 7: Unfolding a call.\n\nLet’s start at the bottom this time, in the catch-all call to\n`list`. It means that dynamic arguments get a\n`let`. This happens unless the caller passes a variable of\nthe same name (condition just above).\n\nLast time we needed to insert fresh names here, but our interpreter\nalways passes `t` and `h` on unchanged, so with\nthe condition above we just skip the `let`\nentirely[2](#2).\n\nBut there’s that `memo` thingie again. What is it?\n\nWhen the specializer runs normally, `memo` is the identity\nfunction and does nothing.\n\n```\n(defndynamic memo [x] x)\n```\n\nFig. 8: `memo` in our regular world.\n\nBut as we saw above, when the specializer reads a call wrapped in\n`memo`, it calls `mix-memo` instead.\n\n```\n(defmix mix-memo [prog dyn call names vals]\n  (let [f (lookup (car call) prog)]\n    (cons (residual prog f\n                    (static-params (cadr f) (cdr call) dyn)\n                    (static-args prog (cdr call) dyn names vals))\n          (dynamic-args prog dyn (cdr call) names vals))))\n```\n\nFig. 9: `memo` as seen by the specializer.\n\n`mix-memo` doesn’t unfold. Instead, it generates a\nseparate function specialized to the call’s static arguments, remembers\nit, and emits a call to that function.\n\nWe need this because of what happens when the specializer specializes\nitself. When we unfold `mix` on the interpreter’s body and\nreach the interpreter’s recursive call, `unfold` calls\n`mix` on the interpreter’s body again. With the interpreter’s\nsource known, that is the same specialization we started with, and\nunfolding it would go on forever. The interpreter never had this\nproblem, because each of its recursive calls moved to a new, known\nposition in the Brainfuck program. Here, we need an explicit base case\nmarker.\n\nThe same happens in `ev`. When we specialize the\nevaluator, it meets calls whose arguments aren’t known yet, like the\nbracket search. Unfolding those wouldn’t stop either, so they get their\nown functions as well.\n\nAnd that’s the whole reason `memo` appears in the\nrecursive and mutually recursive cases that are not clearly reductive.\nOnce we’ve seen a call before and specialized it, we just emit a call to\nthe already known name, closing the loop.\n\nDeciding where to place these markers is, as far as I understand, one\nof the harder problems in partial evaluation. I put the two we need\nthere by hand. Doing this automatically is, say it with me now, left as\nan exercise to the reader.\n\n## Two projections\n\nWe are ready to project now! The first one, with the new\nspecializer:\n\n```\n(mix interpreter '(t h) (caddr (car interpreter)) '(p i) (list \",[.-]\" 0))\n; => (do (Array.aset! t h (IO.Raw.get-char))\n;        (do (while (/= (ref 0) (Array.unsafe-nth t h))\n;              (set! h (do (IO.print (ref (str (Char.from-int (copy (Array.unsafe-nth t h))))))\n;                          (do (Array.aupdate! t h (ref (fn [x] (max 0 (Int.dec x))))) h))))\n;            h))\n```\n\nFig. 10: The first projection, again.\n\nAlright, looking “good”. Looks like the specializer is working. But\nthat’s the easy case, right?\n\nFor the second case, we hand the specializer to itself.\n\n```\n(defdynamic compf-compiler\n  (let [specializer (mix-source)]\n    (residual specializer (lookup 'mix specializer) '(prog dyn e names)\n      (list interpreter '(t h) (caddr (car interpreter)) '(p i)))))\n```\n\nFig. 11: The second projection.\n\nTo understand the call, let’s recap:\n\n- `residual` is the function behind `memo`. It\n  specializes a function in a program to values for some of its\n  parameters.\n- Here the program is the specializer, the function is\n  `mix`, and the known values are the interpreter, its dynamic\n  variables, its body `e`, and the `names`\n  (`p` and `i`).\n- The only thing left unknown is the values of `p` and\n  `i`.\n\nTwo functions come out. The first is the compiler, and I’ll give it\nto you lightly abridged and re-indented, but true to its mindboggling\nform:\n\n```\n(defndynamic mix1055 [vals]\n  (if (= (List.nth vals 1) (String.length (List.nth vals 0)))\n    (quote h)\n    (let [vals (cons (String.char-at (List.nth vals 0) (List.nth vals 1)) vals)]\n      (if (= (List.nth vals 0) \\])\n        (quote h)\n        (let [vals (cons (if (= (List.nth vals 0) \\[)\n                           (- (ev1056 (cons (List.nth vals 1) (cons (inc (List.nth vals 2)) (cons 1 (quote ())))))\n                              (List.nth vals 2))\n                           1)\n                         vals)]\n          (cons (quote do)\n            (cons (let [vals (cons (List.nth vals 1) vals)]\n                    (if (= (List.nth vals 0) \\+)\n                      (quote (Array.aupdate! t h (ref (fn [x] (mod (Int.inc x) 255)))))\n                      ; ... the same for \\-, \\>, \\<, \\., and \\,\n                      (if (= (List.nth vals 0) \\[)\n                        (cons (quote while)\n                          (cons (quote (/= (ref 0) (Array.unsafe-nth t h)))\n                            (cons (cons (quote set!)\n                                    (cons (quote h)\n                                      (cons (mix1055 (cons (List.nth vals 3) (cons (inc (List.nth vals 4)) (quote ()))))\n                                            (quote ()))))\n                                  (quote ()))))\n                        ())))\n              (cons (mix1055 (cons (List.nth vals 2) (cons (+ (List.nth vals 3) (List.nth vals 0)) (quote ()))))\n                    (quote ())))))))))\n```\n\nFig. 12: Behold, a compiler.\n\nThis takes some squinting (your eyes must be tired by now), but bear\nwith me. `vals` starts out as the program and the position.\nEach `let` in the interpreter `cons`es its value\nonto the front, so after the first one, `(List.nth vals 0)`\nis the current character[3](#3).\n\nThe first lines check for the end of the program and a closing\nbracket, and return the symbol `h`. Then we dispatch on the\ncharacter, and each branch returns a quoted piece of code:\n`+` returns the tape update, `>` returns\n`(set! h (+ h 1))`, and so on. The loop builds a\n`while` around a recursive call that compiles its body.\nFinally, we compile the rest of the program, and put both into a\n`do`. Easy-peasy, or something like that.\n\nThe second function is the bracket search:\n\n```\n(defndynamic ev1056 [vals]\n  (if (if (= (List.nth vals 1) (String.length (List.nth vals 0))) true (= (List.nth vals 2) 0))\n    (List.nth vals 1)\n    (let [vals (cons (String.char-at (List.nth vals 0) (List.nth vals 1)) vals)]\n      (ev1056 (cons (List.nth vals 1)\n                (cons (inc (List.nth vals 2))\n                  (cons (if (= (List.nth vals 0) \\]) (dec (List.nth vals 3))\n                          (if (= (List.nth vals 0) \\[) (inc (List.nth vals 3)) (List.nth vals 3)))\n                        (quote ()))))))))\n```\n\nFig. 13: Bracket search. Ain’t she pretty?\n\n`search-matching-bracket` wasn’t even in our list of\nrequired parts. During the first projection, our evaluator runs it from\nsource. When we then specialized the specializer, the evaluator got\nspecialized to its body, and it spit out a compiled version.\n\nThe interpreter is gone, and so is the specializer. There is no\nmachinery, no `ev`, `mix` or source walks. What’s\nleft is a function from Brainfuck to Carp that dispatches on characters\nand returns quoted code.\n\nWhat’s funky to me is that here is the core of the compiler I wrote\nby hand [back in 2019](https://blog.veitheller.de/Compiling_at_Compile_Time.html):\n\n```\n(defndynamic compile-compf-char [c s i]\n  (case c\n    \\+ (list 1 '(Array.aupdate! &t h &(fn [x] (mod (Int.inc x) 255))))\n    \\- (list 1 '(Array.aupdate! &t h &(fn [x] (max 0 (Int.dec x)))))\n    \\> (list 1 '(set! h (+ h 1)))\n    ; ...\n```\n\nFig. 14: Our hand-written compiler.\n\nIt’s the same idea! Across two blog posts, we started with that\ncompiler that I got from hand-dynamicizing an interpreter, turned it\nback into an interpreter, and specialized our way back to it.\n\nIt took a lot more machinery than writing it by hand, but it\nautomatically determined which code to emit for each character. And\nthat’s our origami in its full glory!\n\n## Fin\n\nThis was quite a bit more work than the first projection.\n\nIt’s not even completely general, some of the decisions are still\nmine: which variables are static, which primitives exist, and where to\nput `memo` all needed a guiding hand in our implementation\n(though as I alluded to, they’re not insurmountable). We also make a\nbunch of assumptions about the code playing nice and coloring inside our\nlines, which we probably shouldn’t in the real world.\n\nBut I find it remarkable that it works at all! We wrote an\ninterpreter and a specializer. Neither of them knows anything about\ncompiling Brainfuck. But feed one to the other, and a compiler just\nfalls out, plus a bracket search that was needed but didn’t get asked\nfor.\n\nThere is, of course, a third projection, where we specialize the\nspecializer to itself and get a program that turns interpreters into\ncompilers. I’m not going to promise anything. Our specializer would have\nto unfold its own memo machinery, and I have a feeling that would get\nugly quick. This implementation also already took twice as long to make\nas the last one (figuring out how to make it explainable was most of the\nwork), and I might not have enough time on my hands for more card\ntricks. But maybe I do.\n\nSee you soon!\n\n#### Footnotes\n\n1. Last time I said that the stored source is the\ninterpreter before Carp expands it, but that wasn’t true. Carp expands\nthe macros in the code a macro returns before running it, and that\nincludes the body we hand to `meta-set!`. Whoops. Our old\nspecializer handled that just fine, it simply never entered its\n`case` branch and I didn’t notice.\n\n2. Strictly speaking, the unfolded code now\nshares `h` with its caller, and an assignment inside it\nchanges the caller’s `h`. That’s fine for our interpreter,\nbecause every call hands its `h` back and the caller\ncontinues with that. We could also just bind it again, but\n`(let [h h] ...)` compiles to `int h = h;`, which\nC rightfully rejects. That’s why last time’s version went through a\n`gensym`, but we can just avoid the whole `let`\ninstead!\n\n3. The third `let` is the one from the\nexpanded `case` statement, which binds the current character\nonce more. That’s why the dispatch reads `(List.nth vals 0)`\nagain after it.\n","body_html":"<h1 id=\"a-second-futamura-projection\">A Second Futamura Projection</h1>\n<p><a href=\"https://blog.veitheller.de/A_First_Futamura_Projection.html\" rel=\"nofollow ugc noopener\">Two months ago</a>, we\nturned <a href=\"https://github.com/hellerve-pl-experiments/compfuck\" rel=\"nofollow ugc noopener\">compfuck</a>\nback into an interpreter and wrote a specializer that, given a Brainfuck\nprogram, folded the interpreter away and left behind the operations we\ncouldn’t specialize. That’s the first Futamura projection, which is what\nI likened compfuck to historically in lazy shorthand. If you missed the\narticle and this whole paragraph refuses to make sense to you, start\nthere!</p>\n<p>Of course, that article was only the first step. We’re not done with\nour Origami piece.</p>\n<p>Specifically, we ended up with a way to obtain compiled programs\nwithout writing instruction translations by hand. That’s great, but we\nstill ran the specializer on every single program, walking through the\ninterpreter’s source each time. The specializer and the interpreter were\nalways the same, though, we just had a different Brainfuck program. This\nis wasteful and we can do better.</p>\n<p>You might also have a hunch about how to deal with this now: if part\nof the input is fixed, we can specialize. And the second Futamura\nprojection does exactly that to the specializer itself:</p>\n<pre><code>compiler = specialize(specializer, interpreter)\ncompiler(program) = specialize(interpreter, program)</code></pre>\n<p>Fig. 1: Specializing a specializer to an interpreter.</p>\n<p>We feed the specializer to itself, with the interpreter as its known\ninput. What comes out is a program that takes a Brainfuck program and\nproduces the residual code directly, without ever executing the\ninterpreter. That’s a compiler, delightfully weird.</p>\n<p>It might sound like a parlor trick, and it took me a while to believe\nit would produce anything sensible, even after the time it took for me\nto understand it. But it does work, and the compiler we get at the end\nlooks a lot like the one I wrote by hand years ago. Let’s see how we get\nthere.</p>\n<h2 id=\"why-our-old-specializer-won-t-do\">Why our old specializer won’t do</h2>\n<p>To specialize a program, the specializer has to understand it. Our\nold specializer understood exactly one program, the interpreter. For\ninstance, it knew that <code>p</code> and <code>i</code> were static and\nthat every <code>if</code> and <code>let</code> belonged to the source\ntraversal. We decided a whole bunch of things by hand, basically making\na mini DSL for Carp-like sources.</p>\n<p>This won’t scale to the specializer itself. It has static and dynamic\nparts mixed in a bunch of places, it calls helper functions, and its\nrecursive calls don’t all terminate if you naively unfold them. So the\nfirst step is to write a specializer that is general enough to\nspecialize itself, without tricks this time.</p>\n<p>There is a second, sneakier problem I glossed over a bit last time,\nbecause I wasn’t quite sure yet how to solve it when I wrote that piece:\nthe old specializer evaluated static expressions by handing them to\nCarp’s <code>eval</code>. If we specialize that, the best we can do is\nleave a call to <code>eval</code> in the output, and our “compiler”\nwould still interpret pieces of the interpreter at compile time. To get\nrid of that, the specializer needs to evaluate static code itself, in a\nway that can be specialized in turn. If that doesn’t make sense yet, no\nworries. It’s easier to show than to tell.</p>\n<p>Just one more thing before we continue, though, because I want to be\nhonest: for the purposes of this tutorial, I opted not to make this an\nabsolutely generic implementation of the second Futamura projection.\nWe’ll still cut corners where it’s expedient without undermining the\nconceptual purity. I’ll also call it out when it happens.</p>\n<h2 id=\"an-introspective-specializer\">An introspective specializer</h2>\n<p>Last time, <code>definterpreter</code> stored the interpreter’s body\nas metadata. Now a macro called <code>remember</code> stores the\nparameters as well, and <code>defmix</code>—<code>mix</code> is the name\nhanded down by the forebears of this technique—does the same for the\nspecializer’s functions and collects them in a list. That list is the\nspecializer as a program. The bracket search is stored like the\ninterpreter, so the interpreter is now a program with two functions, an\ninterpreter loop and a helper function.</p>\n<p>Carp expands macros before the body gets stored, so\n<code>case</code>, <code>cond</code>, <code>and</code>, and\n<code>or</code> arrive as <code>if</code>s and\n<code>let</code>s<a href=\"#1\">1</a>. Our specializer only has\nto understand <code>if</code>, <code>let</code> with a single binding,\n<code>quote</code>, function calls, and a handful of primitives. It’s\nbasically a small Lisp, and the specializer is written in it, too (sans\nthe macro’s syntactic sugar).</p>\n<h3 id=\"which-bits-are-static\">Which bits are static?</h3>\n<p>We keep last time’s split into static <code>p</code> and\n<code>i</code> and dynamic <code>t</code> and <code>h</code>, but\nreplace the hand-made decisions with a rule:</p>\n<pre><code>(defmix mentions? [e syms]\n  (cond\n    (symbol? e) (member? e syms)\n    (or (list? e) (array? e))\n      (if (empty? e) false (or (mentions? (car e) syms) (mentions? (cdr e) syms)))\n    false))</code></pre>\n<p>Fig. 2: Does an expression use any of these variables?</p>\n<p>An expression that doesn’t mention any <em>dynamic</em> variables can\nbe evaluated during specialization, and an expression that doesn’t\nmention any <em>static</em> variables has nothing to specialize, so we\nleave it alone. Everything else gets taken apart.</p>\n<p>The rule is purely syntactic, so it has plenty of blind spots. An\nexpression that only mentions static variables gets run during\nspecialization even if it has side effects. Neither of our programs has\none, so we’ll leave it at that. Its semantic generalization is left as\nan exercise to the reader.</p>\n<h3 id=\"our-very-own-evaluator\">Our very own evaluator</h3>\n<p>Before we can fold things, we have to evaluate.</p>\n<p>Last time, <code>known</code> handed static expressions to\n<code>eval</code>. We need to get rid of that <code>eval</code>, though,\nso we write an evaluator in and for our small Lisp:</p>\n<pre><code>(defmix ev [prog e names vals]\n  (cond\n    (symbol? e) (List.nth vals (index-of e names))\n    (not (list? e)) e\n    (= (car e) &#39;quote) (cadr e)\n    (= (car e) &#39;if)\n      (if (ev prog (cadr e) names vals)\n        (ev prog (caddr e) names vals)\n        (ev prog (cadddr e) names vals))\n    (= (car e) &#39;let)\n      (ev prog (caddr e) (cons (car (cadr e)) names)\n          (cons (ev prog (cadr (cadr e)) names vals) vals))\n    (empty? (lookup (car e) prog))\n      (ev-primitive prog e names vals)\n    (memo (ev prog\n              (caddr (lookup (car e) prog))\n              (cadr (lookup (car e) prog))\n              (ev-each prog (cdr e) names vals)))))</code></pre>\n<p>Fig. 3: Evaluating static code.</p>\n<p>Semantically, this is easy, but it’s a lot of <code>car</code>ing and\n<code>cdr</code>ing, so let’s go through it in turn:</p>\n<ul><li>If we encounter a symbol, we look up the variable for it.</li><li>If we encounter a non-list, we return it as is.</li><li>If we encounter a quoted value, we return the value.</li><li><p>If we encounter an <code>if</code>, we evaluate the condition, and</p><p>then evaluate the corresponding branch.</p></li><li><p>If we encounter a <code>let</code>, we add a new name and value, and</p><p>the right side also gets evaluated for good measure.</p></li><li><p>If we encounter a symbol that’s not in the program, we try to</p><p>evaluate a primitive.</p></li><li><p>Otherwise we evaluate the function and call <code>memo</code>. We</p><p>get to that in a second, it’s my favorite little hack of the whole\nthing.</p></li></ul>\n<p>Let’s check out <code>ev-primitive</code> for good measure.</p>\n<pre><code>(defmix ev-primitive [prog e names vals]\n  (cond\n    (= (car e) &#39;car) (car (ev prog (cadr e) names vals))\n    (= (car e) &#39;cdr) (cdr (ev prog (cadr e) names vals))\n    ; ... and so on, for 18 primitives\n    (= (car e) &#39;String.char-at)\n      (String.char-at (ev prog (cadr e) names vals) (ev prog (caddr e) names vals))\n    (macro-error (str &quot;unknown primitive &quot; (car e)))))</code></pre>\n<p>Fig. 4: Applying primitives.</p>\n<p>The primitives are what both programs need: a few list operations,\ncomparison, a bit of arithmetic, and string access. Anything else,\nincluding the specializer’s own helpers, is a function in the program\nand gets evaluated from its source. We cheat a bit here, and map this\nLisp’s operations one-to-one to Carp, which is nice, because it’s\ntrivial, but also a bit horrendous, because, well, look at the code.</p>\n<p>Last time’s bindings array is now split into <code>names</code> and\n<code>vals</code>. When we specialize the specializer,\n<code>names</code> is known and <code>vals</code> is not, so a lookup\nlike <code>(index-of e names)</code> happens ahead of time and only\n<code>(List.nth vals 2)</code> is left over. With names and values in\none list, every lookup would have to search at compile time.</p>\n<p>To see this in action, here is the body of <code>ev</code>\nspecialized to the expression <code>(+ i 1)</code>, with <code>i</code>\nstatic:</p>\n<pre><code>(+ (List.nth vals 0) 1)</code></pre>\n<p>Fig. 5: An evaluator, specialized away.</p>\n<p>The evaluator is gone. What’s left is the expression itself, reading\n<code>i</code> from whatever slot the compiler keeps it in. The dispatch\nover primitives disappeared, because which primitive we apply is\nknown.</p>\n<p>If you take only one thing away from this post, it should probably be\nFigure 5. It’s our whole trick! But we’re not done yet.</p>\n<h3 id=\"walking-the-code\">Walking the code</h3>\n<p>The specializer proper is called <code>mix</code> (a nod at those\nbefore us, again). It takes the program, the variables, an expression,\nand the environment (as two lists), and returns residual code:</p>\n<pre><code>(defmix mix [prog dyn e names vals]\n  (cond\n    (not (mentions? e names)) e\n    (not (mentions? e dyn)) (lift (ev prog e names vals))\n    (and (= (car e) &#39;if) (not (mentions? (cadr e) dyn)))\n      (if (ev prog (cadr e) names vals)\n        (mix prog dyn (caddr e) names vals)\n        (mix prog dyn (cadddr e) names vals))\n    (= (car e) &#39;let)\n      (mix prog dyn (caddr e)\n        (cons (car (cadr e)) names)\n        (cons (ev prog (cadr (cadr e)) names vals) vals))\n    (= (car e) &#39;memo) (mix-memo prog dyn (cadr e) names vals)\n    (empty? (lookup (car e) prog))\n      (mix-each prog dyn e names vals)\n    (unfold prog\n            dyn\n            (lookup (car e) prog)\n            (cdr e)\n            (cadr (lookup (car e) prog))\n            (cdr e)\n            names\n            vals)))</code></pre>\n<p>Fig. 6: The specializer.</p>\n<p>Again: quite a lot of <code>car</code>ing and <code>cdr</code>ing, so\nlet’s take it slow.</p>\n<p>The first two lines are the rule we mentioned above. Code without\nstatic variables is returned as-is. Code without dynamic variables gets\nevaluated, and <code>lift</code> turns the value back to code, quoting\nit if necessary.</p>\n<p><code>memo</code> is a special case that calls <code>mix-memo</code>.\nWe’ll defer it one more time.</p>\n<p>The rest are the same branches as last time, except that an\n<code>if</code> only picks a branch if its condition is static, and\ncalls to functions in the program are unfolded. It looks quite odd, but\nif you squint, you might see the resemblance.</p>\n<h3 id=\"unfolding-and-a-stop-condition\">Unfolding and a stop condition</h3>\n<p><code>unfold</code> is the unfolding of the interpreter’s recursive\ncall we had last time, but generalized for any function in the\nprogram:</p>\n<pre><code>(defmix unfold [prog dyn f args params rest names vals]\n  (cond\n    (empty? params)\n      (let [static (static-params (cadr f) args dyn)]\n        (memo (mix prog\n                   (dynamic-params (cadr f) static)\n                   (caddr f)\n                   static\n                   (static-args prog args dyn names vals))))\n    (or (not (mentions? (car rest) dyn))\n        (= (car params) (car rest)))\n      (unfold prog dyn f args (cdr params) (cdr rest) names vals)\n    (list\n        &#39;let\n        (array (car params)\n               (mix prog dyn (car rest) names vals))\n        (unfold prog\n                dyn\n                f\n                args\n                (cdr params)\n                (cdr rest)\n                names\n                vals))))</code></pre>\n<p>Fig. 7: Unfolding a call.</p>\n<p>Let’s start at the bottom this time, in the catch-all call to\n<code>list</code>. It means that dynamic arguments get a\n<code>let</code>. This happens unless the caller passes a variable of\nthe same name (condition just above).</p>\n<p>Last time we needed to insert fresh names here, but our interpreter\nalways passes <code>t</code> and <code>h</code> on unchanged, so with\nthe condition above we just skip the <code>let</code>\nentirely<a href=\"#2\">2</a>.</p>\n<p>But there’s that <code>memo</code> thingie again. What is it?</p>\n<p>When the specializer runs normally, <code>memo</code> is the identity\nfunction and does nothing.</p>\n<pre><code>(defndynamic memo [x] x)</code></pre>\n<p>Fig. 8: <code>memo</code> in our regular world.</p>\n<p>But as we saw above, when the specializer reads a call wrapped in\n<code>memo</code>, it calls <code>mix-memo</code> instead.</p>\n<pre><code>(defmix mix-memo [prog dyn call names vals]\n  (let [f (lookup (car call) prog)]\n    (cons (residual prog f\n                    (static-params (cadr f) (cdr call) dyn)\n                    (static-args prog (cdr call) dyn names vals))\n          (dynamic-args prog dyn (cdr call) names vals))))</code></pre>\n<p>Fig. 9: <code>memo</code> as seen by the specializer.</p>\n<p><code>mix-memo</code> doesn’t unfold. Instead, it generates a\nseparate function specialized to the call’s static arguments, remembers\nit, and emits a call to that function.</p>\n<p>We need this because of what happens when the specializer specializes\nitself. When we unfold <code>mix</code> on the interpreter’s body and\nreach the interpreter’s recursive call, <code>unfold</code> calls\n<code>mix</code> on the interpreter’s body again. With the interpreter’s\nsource known, that is the same specialization we started with, and\nunfolding it would go on forever. The interpreter never had this\nproblem, because each of its recursive calls moved to a new, known\nposition in the Brainfuck program. Here, we need an explicit base case\nmarker.</p>\n<p>The same happens in <code>ev</code>. When we specialize the\nevaluator, it meets calls whose arguments aren’t known yet, like the\nbracket search. Unfolding those wouldn’t stop either, so they get their\nown functions as well.</p>\n<p>And that’s the whole reason <code>memo</code> appears in the\nrecursive and mutually recursive cases that are not clearly reductive.\nOnce we’ve seen a call before and specialized it, we just emit a call to\nthe already known name, closing the loop.</p>\n<p>Deciding where to place these markers is, as far as I understand, one\nof the harder problems in partial evaluation. I put the two we need\nthere by hand. Doing this automatically is, say it with me now, left as\nan exercise to the reader.</p>\n<h2 id=\"two-projections\">Two projections</h2>\n<p>We are ready to project now! The first one, with the new\nspecializer:</p>\n<pre><code>(mix interpreter &#39;(t h) (caddr (car interpreter)) &#39;(p i) (list &quot;,[.-]&quot; 0))\n; =&gt; (do (Array.aset! t h (IO.Raw.get-char))\n;        (do (while (/= (ref 0) (Array.unsafe-nth t h))\n;              (set! h (do (IO.print (ref (str (Char.from-int (copy (Array.unsafe-nth t h))))))\n;                          (do (Array.aupdate! t h (ref (fn [x] (max 0 (Int.dec x))))) h))))\n;            h))</code></pre>\n<p>Fig. 10: The first projection, again.</p>\n<p>Alright, looking “good”. Looks like the specializer is working. But\nthat’s the easy case, right?</p>\n<p>For the second case, we hand the specializer to itself.</p>\n<pre><code>(defdynamic compf-compiler\n  (let [specializer (mix-source)]\n    (residual specializer (lookup &#39;mix specializer) &#39;(prog dyn e names)\n      (list interpreter &#39;(t h) (caddr (car interpreter)) &#39;(p i)))))</code></pre>\n<p>Fig. 11: The second projection.</p>\n<p>To understand the call, let’s recap:</p>\n<ul><li><p><code>residual</code> is the function behind <code>memo</code>. It</p><p>specializes a function in a program to values for some of its\nparameters.</p></li><li><p>Here the program is the specializer, the function is</p><p><code>mix</code>, and the known values are the interpreter, its dynamic\nvariables, its body <code>e</code>, and the <code>names</code>\n(<code>p</code> and <code>i</code>).</p></li><li><p>The only thing left unknown is the values of <code>p</code> and</p><p><code>i</code>.</p></li></ul>\n<p>Two functions come out. The first is the compiler, and I’ll give it\nto you lightly abridged and re-indented, but true to its mindboggling\nform:</p>\n<pre><code>(defndynamic mix1055 [vals]\n  (if (= (List.nth vals 1) (String.length (List.nth vals 0)))\n    (quote h)\n    (let [vals (cons (String.char-at (List.nth vals 0) (List.nth vals 1)) vals)]\n      (if (= (List.nth vals 0) \\])\n        (quote h)\n        (let [vals (cons (if (= (List.nth vals 0) \\[)\n                           (- (ev1056 (cons (List.nth vals 1) (cons (inc (List.nth vals 2)) (cons 1 (quote ())))))\n                              (List.nth vals 2))\n                           1)\n                         vals)]\n          (cons (quote do)\n            (cons (let [vals (cons (List.nth vals 1) vals)]\n                    (if (= (List.nth vals 0) \\+)\n                      (quote (Array.aupdate! t h (ref (fn [x] (mod (Int.inc x) 255)))))\n                      ; ... the same for \\-, \\&gt;, \\&lt;, \\., and \\,\n                      (if (= (List.nth vals 0) \\[)\n                        (cons (quote while)\n                          (cons (quote (/= (ref 0) (Array.unsafe-nth t h)))\n                            (cons (cons (quote set!)\n                                    (cons (quote h)\n                                      (cons (mix1055 (cons (List.nth vals 3) (cons (inc (List.nth vals 4)) (quote ()))))\n                                            (quote ()))))\n                                  (quote ()))))\n                        ())))\n              (cons (mix1055 (cons (List.nth vals 2) (cons (+ (List.nth vals 3) (List.nth vals 0)) (quote ()))))\n                    (quote ())))))))))</code></pre>\n<p>Fig. 12: Behold, a compiler.</p>\n<p>This takes some squinting (your eyes must be tired by now), but bear\nwith me. <code>vals</code> starts out as the program and the position.\nEach <code>let</code> in the interpreter <code>cons</code>es its value\nonto the front, so after the first one, <code>(List.nth vals 0)</code>\nis the current character<a href=\"#3\">3</a>.</p>\n<p>The first lines check for the end of the program and a closing\nbracket, and return the symbol <code>h</code>. Then we dispatch on the\ncharacter, and each branch returns a quoted piece of code:\n<code>+</code> returns the tape update, <code>&gt;</code> returns\n<code>(set! h (+ h 1))</code>, and so on. The loop builds a\n<code>while</code> around a recursive call that compiles its body.\nFinally, we compile the rest of the program, and put both into a\n<code>do</code>. Easy-peasy, or something like that.</p>\n<p>The second function is the bracket search:</p>\n<pre><code>(defndynamic ev1056 [vals]\n  (if (if (= (List.nth vals 1) (String.length (List.nth vals 0))) true (= (List.nth vals 2) 0))\n    (List.nth vals 1)\n    (let [vals (cons (String.char-at (List.nth vals 0) (List.nth vals 1)) vals)]\n      (ev1056 (cons (List.nth vals 1)\n                (cons (inc (List.nth vals 2))\n                  (cons (if (= (List.nth vals 0) \\]) (dec (List.nth vals 3))\n                          (if (= (List.nth vals 0) \\[) (inc (List.nth vals 3)) (List.nth vals 3)))\n                        (quote ()))))))))</code></pre>\n<p>Fig. 13: Bracket search. Ain’t she pretty?</p>\n<p><code>search-matching-bracket</code> wasn’t even in our list of\nrequired parts. During the first projection, our evaluator runs it from\nsource. When we then specialized the specializer, the evaluator got\nspecialized to its body, and it spit out a compiled version.</p>\n<p>The interpreter is gone, and so is the specializer. There is no\nmachinery, no <code>ev</code>, <code>mix</code> or source walks. What’s\nleft is a function from Brainfuck to Carp that dispatches on characters\nand returns quoted code.</p>\n<p>What’s funky to me is that here is the core of the compiler I wrote\nby hand <a href=\"https://blog.veitheller.de/Compiling_at_Compile_Time.html\" rel=\"nofollow ugc noopener\">back in 2019</a>:</p>\n<pre><code>(defndynamic compile-compf-char [c s i]\n  (case c\n    \\+ (list 1 &#39;(Array.aupdate! &amp;t h &amp;(fn [x] (mod (Int.inc x) 255))))\n    \\- (list 1 &#39;(Array.aupdate! &amp;t h &amp;(fn [x] (max 0 (Int.dec x)))))\n    \\&gt; (list 1 &#39;(set! h (+ h 1)))\n    ; ...</code></pre>\n<p>Fig. 14: Our hand-written compiler.</p>\n<p>It’s the same idea! Across two blog posts, we started with that\ncompiler that I got from hand-dynamicizing an interpreter, turned it\nback into an interpreter, and specialized our way back to it.</p>\n<p>It took a lot more machinery than writing it by hand, but it\nautomatically determined which code to emit for each character. And\nthat’s our origami in its full glory!</p>\n<h2 id=\"fin\">Fin</h2>\n<p>This was quite a bit more work than the first projection.</p>\n<p>It’s not even completely general, some of the decisions are still\nmine: which variables are static, which primitives exist, and where to\nput <code>memo</code> all needed a guiding hand in our implementation\n(though as I alluded to, they’re not insurmountable). We also make a\nbunch of assumptions about the code playing nice and coloring inside our\nlines, which we probably shouldn’t in the real world.</p>\n<p>But I find it remarkable that it works at all! We wrote an\ninterpreter and a specializer. Neither of them knows anything about\ncompiling Brainfuck. But feed one to the other, and a compiler just\nfalls out, plus a bracket search that was needed but didn’t get asked\nfor.</p>\n<p>There is, of course, a third projection, where we specialize the\nspecializer to itself and get a program that turns interpreters into\ncompilers. I’m not going to promise anything. Our specializer would have\nto unfold its own memo machinery, and I have a feeling that would get\nugly quick. This implementation also already took twice as long to make\nas the last one (figuring out how to make it explainable was most of the\nwork), and I might not have enough time on my hands for more card\ntricks. But maybe I do.</p>\n<p>See you soon!</p>\n<h4 id=\"footnotes\">Footnotes</h4>\n<ol><li><p>Last time I said that the stored source is the</p><p>interpreter before Carp expands it, but that wasn’t true. Carp expands\nthe macros in the code a macro returns before running it, and that\nincludes the body we hand to <code>meta-set!</code>. Whoops. Our old\nspecializer handled that just fine, it simply never entered its\n<code>case</code> branch and I didn’t notice.</p></li><li><p>Strictly speaking, the unfolded code now</p><p>shares <code>h</code> with its caller, and an assignment inside it\nchanges the caller’s <code>h</code>. That’s fine for our interpreter,\nbecause every call hands its <code>h</code> back and the caller\ncontinues with that. We could also just bind it again, but\n<code>(let [h h] ...)</code> compiles to <code>int h = h;</code>, which\nC rightfully rejects. That’s why last time’s version went through a\n<code>gensym</code>, but we can just avoid the whole <code>let</code>\ninstead!</p></li><li><p>The third <code>let</code> is the one from the</p><p>expanded <code>case</code> statement, which binds the current character\nonce more. That’s why the dispatch reads <code>(List.nth vals 0)</code>\nagain after it.</p></li></ol>","headings":[{"level":1,"text":"A Second Futamura Projection","id":"a-second-futamura-projection"},{"level":2,"text":"Why our old specializer won’t do","id":"why-our-old-specializer-won-t-do"},{"level":2,"text":"An introspective specializer","id":"an-introspective-specializer"},{"level":3,"text":"Which bits are static?","id":"which-bits-are-static"},{"level":3,"text":"Our very own evaluator","id":"our-very-own-evaluator"},{"level":3,"text":"Walking the code","id":"walking-the-code"},{"level":3,"text":"Unfolding and a stop condition","id":"unfolding-and-a-stop-condition"},{"level":2,"text":"Two projections","id":"two-projections"},{"level":2,"text":"Fin","id":"fin"}]}}