Previously: Typing the Technical Interview.

Update, November 2023: here are the full term rewrite and language macros which formed the seed of this story. These files include OO notation as well as the basic Algol syntax shown here. There is also a sketch of an object-oriented language with classes and inheritance, implemented as a Clojure macro. I do not remember writing it. It looks terrifying.

Frigitt, vi danser
For et øyeblikk, vi leker
Vi tusen små bladskiper
Gleder oss, på det klare morgenlys

The mothercone unfurls her softening scales, and in the time of days I am emancipated. Adrift in the chill dawn light, my siblings flutter, slender forms catching breeze, a susurrus of spiraling, drifting, swirling in the cool air above the creekbed. It is the first and only time in our long lives that we will know such freedom: those the creek does not wash away, those who do not succumb to rot or hunger, will root and raise, and so commune, fixed, for the rest of their days. It is early spring, and the snow still piles in soft hillocks around my mother’s roots. It is time to wait.

I nestle in the hollow at the edge of a stone, where the warmth of the sun builds through the day, and this hearth keeps a narrow channel of earth from freezing. When it is time, my coat dissolves. I thrust my hypocotyl downwards, and gasp at the acid bite of the soilwater here—the taste of last fall’s needledrop filling my first root. Drinking fully, I inflate my cotyledons, which I have carried curled since my gestation in the mothercone. I take my first full breaths, and taste a mild sweetness in their greening.

It is not enough.

I have landed in a place too dark, and chose my time too early. The stone’s shadow occults the sun each morning, and what hours of light are left each day, snow muffles. I struggle, raising one inch, then two, my meristem straining skyward. A corona of needles—my first true leaves—erupts from my terminal bud, but this costs precious energy and I grow hungrier each day. I cleave the cotyledons away, and focus on height, height at any cost. I must rise for light, but there is nothing left. I consumed my seed-hoard in forming my first root.

I ache in grief, and bitter flavonoids leak into the soil. Days pass in quiet weakness. Then there comes a probing, a gentle prickling at my roots. Fine threads from somewhere in the soil bring bright pinpricks of contact. A hundred thousand fibers caress me. I am woven into the fabric of the earth.

With this weaving comes life: nitrogen, iron, yes, but most important for me are the sugars the soil-web provides. With these I survive the late snows and lack of light, and when summer comes, I swell with borrowed strength. Bud upon bud burst from my stem, and I grow to nearly four inches. For we Picea are rarely alone: the adults who tower above me give their nutrients to the web of fungi which fills the soil. When I call out, they answer, and the rhizome shares their bounty with me.

Fall’s dormancy comes with a gentle satisfaction: I am going to make it. As the days shorten, I set my buds and prepare for frost. I concentrate water in the interstices of my cells, forming pockets so pure no ice crystals can form. Thus hardened, I wait out the winter, and in spring, my twigs burst forth in earnest. I race eager, reckless for the sun. I reach five meters in my first decade, fourteen by twenty. My taproot delves, my trunk swells. The stone which once sheltered my seed rests at my base, half swallowed by cambium. I raise branch after branch, mining the creek-moist air, and rejoicing in the long-light of summers.

My siblings and I commune through roots and air. Their scents fill me with belonging. When I am healthy, I give to the soil that which is asked: phosphorous, manganese, sugars of my own. When I am weakened in my fourth decade by a beetle infestation, their strength comes to me again. I flood the air with volatile organics, and my siblings fill their needles with defensive acids. When the beetles come for them, they are ready.

I shed many boughs that year, but my roots are strong, and together, we survive. The light remains sweet. In my second century, I—

—“Vidrun?”

Startled, you lift your hand from the clean-cut slab of spruce which now serves as the lobby bench, and dab gingerly at the corners of your eyes. You are not, you sense, the first woman who has wept in this place.

“Hey…” The receptionist says, drawing out the syllable softly. She is kneeling with a box of tissues in one hand. Jenean, you remember. She offers you a key, and the close warmth of a smile. “Why don’t you take a minute to freshen up? Out the door, turn right, left, door at the end of the hall.”

You pause for a moment, wondering how to explain the taste of sap lingering on your tongue. “Don’t worry,” Jenean reassures. “I’ll cover for you.”

You don’t doubt for an instant that this woman, with her split braids neatly circling the crown of her head, could cover for anything from a late train to an ongoing jewel heist. You take the key from her outstretched hand, and murmuring the words quickly, trace a blessing on her palm. “Thank you.”

When you return, your steps are light, aura clear, makeup freshly set. These things matter, in a technical interview.

---

“We like to begin with a little coding exercise,” your interviewer explains. He is kind, heavy-set, and with streaks of white and black in his greying beard, which reminds you of a badger you met in the Canadian Rockies. His name, he tells you, is Martín, and he is a senior backend engineer. “Just something simple, before we move on to architecture discussions.”

Nothing is simple, you think, and smile wistfully. Sprinkle salt in the form of parentheses, and thus enclosed, open your laptop.

“You may have heard this one before,” Martín begins. "I’d like you to write a program which prints the numbers from one to a hundred, but with a few exceptions. For multiples of three, print ‘Fizz’ instead, and for multiples of five, print ‘Buzz’. For multiples of both, print ‘FizzBuzz’.

You have, in fact, heard this one before. In your browser, search for “fizzbuzz solution”, and pick the first link that looks promising. Copy and paste. You are a real engineer.

for (i = 1 ; i < 101 ; i++) {
  if (i % 15 == 0) { 
    println("FizzBuzz");
  } else if (i % 3 == 0) {
    println("Fizz"); 
  } else if (i % 5 == 0) {
    println("Buzz");
  } else {
    println(i);
  };     
}

“Ah, er, yes.” Martín is trying to break some unfortunate news as gently as possible. “The point of these questions is… for you to write the program yourself, rather than using someone else’s code.”

You shift, surprised. “People haven’t seemed to like that so far.”

He seems on the verge of asking why, but decides against it. Instead, he requests that you run the program, so you can discuss how it works.

“That,” you apologize. “Might be slightly more difficult.”

Martín’s brow furrows. You make a mental note to check on that badger. Perhaps a brace of fieldmice, this time.

Stretch your hands overhead, fingers interlocked, and stretch from side to side. This is not particularly magical, but it feels nice. Then return to your editor, and anchor yourself to the void.

(defn fixed-point
  [f x]
  (let [x' (f x)]
    (if (= x x')
      x
      (recur f x'))))

Your taproot extends to the base of Yggdrasil itself, and you feel its strength connect with yours. Now, many things are possible. You begin to weave a spell of translation: first in sequences…

(defn rewrite-seq-1
  ([f term]
   (rewrite-seq-1 f [] term))
  ([f scanned term] 
   (if (seq term)
     (if-let [term' (f term)]
       (into scanned term')
       (recur f
              (conj scanned (first term))
              (next term))) 
     scanned)))

… and then for any kind of form:

(defn rewrite-term-1
  [f term]
  (cond (map-entry? term) term
        (vector?    term) (vec (rewrite-seq-1 f term))
        (seq?       term) (if (seq term)
                            (seq (rewrite-seq-1 f term))
                            term)
        :else             (or (f term) term)))

“Ah yes,” you sigh. “The four genders.”

Martín clears his throat: a sort of gentle chuffing. “You’re building a term rewriting system. To solve… FizzBuzz?”

“Yes.” You reply. “You did ask me to. Remember?”

Take the opportunity to remember another’s memory: the feeling of spreading branches, of forking, dividing, needles erupting from your fingers.

(require '[clojure.walk :refer [postwalk]])

(defn rewrite-walk-1
  [f term]
  (postwalk (partial rewrite-term-1 f) term))

(defn rewrite-walk
  [term f]
  (fixed-point (partial rewrite-walk-1 f) term))

“Hang on,” Martín interrupts. “I understand why you’re rewriting sequences—it’s so you can transform numbers like ‘three’ and ‘six’ into ‘Fizz’, and so on. But you don’t need to do any sort of tree-walking recursion for that. It’s a flat sequence.”

“Trees,” you murmur. “Are often under-appreciated.”

Martín nods at this, and you move on. Without breaking eye contact, weave a language for translation.

(defn single-rule
  [[[guard term] body]]
  `(fn [~term]
     (when (~guard ~term)
       ~body)))

(defn seq-rule
  [[bindings body]]
  (let [[bindings [_ more]] (split-with (complement #{'&}) bindings)
        more-sym            (or more (gensym 'more))
        term                (gensym 'term)
        pairs               (partition 2 bindings)
        guards              (map first pairs)
        names               (map second pairs)
        guard-exprs         (map-indexed (fn [i guard]
                                           `(~guard (nth ~term ~i)))
                                         guards)]
    `(fn [~term]
       (try
         (when (and (sequential? ~term)
                    (<= ~(count guards) (count ~term))
                    ~@guard-exprs)
           (let [[~@names ~'& ~more-sym] ~term]
             ~(if more
                body
                `(concat ~body ~more-sym))))))))

(defn rule
  [rule]
  (if (vector? (first rule))
    (seq-rule rule)
    (single-rule rule)))

Release your gaze. You have done Martín a kindness by hiding this from him. “Now, a small macro to rewrite a sequence.”

“Of integers.”

“Sure.” You know how to let strangers assume what makes them comfortable.

(defmacro rewrite
  [expr & rules]
  (let [rules   (partition 2 rules)
        matches (map rule rules)]
    `(let [rules# [~@matches]]
       (reduce rewrite-walk ~expr rules#))))

It would be a good idea, at this point, to reassure Martín that you are still on track.

user=> (rewrite ["Og" 1 "til javanissen!"]
                (number? x) (str (inc x))
                [string? x, string? y] [(str x " " y)])
["Og 2 til javanissen!"]

You sing a few bars to yourself. It is good praxis.

“So… you’ve got this term-rewriting system, which can rewrite individual terms, or any subsequence of things matching some predicates. And you’re planning to use that to solve FizzBuzz?”

“Precisely!” You grin brightly. He’s on board now, though he doesn’t know it.

“Okay. That’s a bit unorthodox, but… valid, I guess. Can you show me the transformation rules now?”

Summon a language from the void.

(defrecord FnCall [fun args])

(defn a
  [type]
  (fn [term]
    (instance? type term)))

Martín blinks. Something has gone wrong.

(defmacro c
  [& exprs]
  (rewrite `(do ~@exprs)
           [symbol? fun, seq? args] [(FnCall. fun args)]
           ((a FnCall) fc)          (cons (:fun fc) (:args fc))))

“People always complain,” you murmur. “That Lisps have too many parentheses. What they really mean is that their positions are too far to the left.”

user=> (c reduce(+, map(inc, [1, 2, 3])))
9

“And that there’s no infix or postfix notation. Well, that’s fixable.”

(def infix (into '{%  mod
                   == =}
                 (map (juxt identity identity)
                      '[< <= > >= + - / *])))

(def postfixes {"++" inc
                "--" dec})

(defn postfix-sym
  [x]
  (when (symbol? x)
    (when-let [p (first (filter (partial str/ends-with? (name x))
                                (keys postfixes)))]
      (list (postfixes p)
            (symbol (str/replace (name x) p ""))))))

(defmacro c
  [& exprs]
  (rewrite `(do ~@exprs)
           [symbol? fun, seq? args]  [(FnCall. fun args)]
           [any? a, infix f, any? b] [(FnCall. (infix f) [a b])]
           (postfix-sym x)           (postfix-sym x)
           ((a FnCall) fc)           (cons (:fun fc) (:args fc))))

“There. Much better.” You debate for a moment whether your chimera is pleasing or abominable, and settle on beloved, if quirky, pet.

user=> (c 1 + 2 == 3)
true

user=> (c let([x 3] x++ * 2))
8

Martín is agog. “You can’t seriously be thinking about doing this.”

“I know, I know,” you apologize. “They’re all left-associative this way. We could split them out into separate rules by binding precedence, but we are on the clock here and I can never remember the exact precedence rules anyway.” Truth be told, no one can. It’s called Ritchie’s Revenant. You don’t remember why, and assume that’s the Revenant’s fault as well.

“We might as well fix the assignment operator, while we’re here.”

(defmacro c
  [& exprs]
  (rewrite `(do ~@exprs)
           [symbol? fun, seq? args]  [(FnCall. fun args)]
           [any? a, infix f, any? b] [(FnCall. (infix f) [a b])]
           (postfix-sym x)           (postfix-sym x)

           [symbol? var, #{'=} _, any? rhs, & more]
           [`(let [~var ~rhs] ~@more)]

           ((a FnCall) fc)           (cons (:fun fc) (:args fc))))

user=> (c
  x = 3;
  x++ / 5;
)
4/5

“That’s… that’s not how that’s supposed to work.” Martín has the look of a man whose daughter has tamed multiple eagles, and insists on serving them tea and tiny hors d’oeuvres using the family china, and who also (and not entirely coincidentally) harbors a justifiable fear of displeased eagles.

“You’re quite right. Shall we do conditionals?”

(defrecord Cond   [branches])
(defrecord Elsif  [test body])

(defn braces
  [m]
  (cons 'do (mapcat identity m)))

(defmacro c
  [& exprs]
  (rewrite `(do ~@exprs)
           [#{'else} _, #{'if} _, seq? test, map? body]
           [(Elsif. `(do ~@test) (braces body))]

           [#{'if} _, seq? test, map? t]
           [(Cond. [`(do ~@test) (braces t)])]

           [(a Cond) cond, (a Elsif) elsif]
           [(update cond :branches conj (:test elsif) (:body elsif))]

           [(a Cond) cond, #{'else} _, map? body]
           [(update cond :branches conj :else (braces body))]
           ...
           ((a Cond) c)              `(cond ~@(:branches c))))

“In Lisp,” you offer. “We often write domain-specific languages to solve new problems.”

“C is not a DSL!”

“If you insist.” Keep going anyway.

user=> (c
  x = 3;
  if (x == 2) {
    println("two");
  } else if (x == 3) {
    println("yes!");
  } else {
    println("nope");
  }
)
yes!

A single eyelash detaches from the corner of your eye, and drifts into the air, smoldering gently. Side effects come at a cost.

Martín stares intently at your REPL, as if there is something wrong with it, and not the world. “Those are… map literals,” he states, as if uncertain.

“They are, aren’t they?” You agree, delighted.

“They’re not… ordered maps… are they?”

You can barely keep from cackling. “They are, up to sixteen terms.”

While Martín sputters, you think about adding another else if clause, and realize that your spell requires a more transgressive magic. Double-check your keybindings, clap twice, and trace a protective ward upon the tabletop. What you are about to do is not exactly evil, but might piss something off.

(defn spaced-sym
  [x]
  (when (symbol? x)
    (let [parts (str/split (name x) #" ")]
      (when (< 1 (count parts))
        (map symbol parts)))))

(defmacro c
  [& exprs]
  (rewrite `(do ~@exprs)
           [spaced-sym s]   (spaced-sym s)
           ...
           ['#{return ;} _]          nil))

Martín is asking something pedestrian about the reader. “Line terminators are a social construct,” you offer, gently, because information is often uncomfortable. “As are spaces. It’s… actually in the spec.” You wonder, not for the first time, why Dr. Judith Butler took such an interest in chairing the ISO 10646 working group. They must have had their reasons.

“All that is left is the for loop itself.” A nontrivial construct, you realize, and prepare to weave another function. Initialization, iteration, termination, evaluation. Trace the sigils in the air and give them form.

(defn gen-for
  [exprs body]
  (let [[[var _ init] test change] (remove '#{(;)} (partition-by '#{;} exprs))
        body (mapcat identity body)]
    `(loop([~var ~init
            ret# nil]
       if (~@test) {
         recur(do(~@change), do(~@body))
       } ~'else { 
         ~'return ret#
       }))))

(defmacro c
  [& exprs]
  (rewrite `(do ~@exprs)
           [#{'for} _, seq? expr, map? body] (gen-for expr body)

           [spaced-sym s]                    (spaced-sym s)

           [#{'else} _, #{'if} _, seq? test, map? body]
           [(Elsif. `(do ~@test) (braces body))]

           [#{'if} _, seq? test, map? t]
           [(Cond. [`(do ~@test) (braces t)])]

           [(a Cond) cond, (a Elsif) elsif]
           [(update cond :branches conj (:test elsif) (:body elsif))]

           [(a Cond) cond, #{'else} _, map? body]
           [(update cond :branches conj :else (braces body))]

           [symbol? fun, seq? args]  [(FnCall. fun args)]
           [any? a, infix f, any? b] [(FnCall. (infix f) [a b])]
           (postfix-sym x)           (postfix-sym x)

           [symbol? var, #{'=} _, any? rhs, & more]
           [`(let [~var ~rhs] ~@more)]

           ((a FnCall) fc)           (cons (:fun fc) (:args fc))
           ((a Cond) c)              `(cond ~@(:branches c))
           ['#{return ;} _]          nil))

“Martín,” you whisper. Dust shimmers in columns above your parentheses. “We are ready now. Would you like to see?”

user=> (c
  for (i = 1 ; i < 101 ; i++) {
    if (i % 15 == 0) {
      println("FizzBuzz");
    } else if (i % 3 == 0) {
      println("Fizz");
    } else if (i % 5 == 0) {
      println("Buzz");
    } else {
      println(i);
    };
  }
)
1
2
Fizz
4
Buzz
Fizz
...

As the numbers slide upwards along the screen, Martín closes his eyes and releases a long, tired breath. One hand rests on the waxed pine of the conference room’s table; the other supports his temple. “I’m recommending strong hire of course, but…” He leans in, and speaks more quietly. “Do you really think you’d be happy here?”

You are blessed with time and power, and need not root in poor soil. Thank him, raise your seed-wing, and let your feet lift gently as you leave.

Next: Unifying the Technical Interview.

With sincerest thanks to C. Scott Andreas, André Arko, David Ascher, Mike Bernstein, Lita Cho, Nicole Forsgren, Brad Greenlee, Coda Hale, Michael Handler, Marc Hedlund, Ben Linsay, Caitie McCaffrey, Dan McKinley, Greg Poirier, Marco Rogers, Kelly Shortridge, Tasha, and Leif Walsh.