When the Coding Exercise Turns Into a Language Design Problem
You arrive at the interview on time, aura clear, makeup freshly set. These things matter. The receptionist, Jenean, recognizes the weight of the moment and offers a key to the restroom. You take a minute to compose yourself before meeting Martín, a senior backend engineer who greets you warmly and leads you to a conference room. The interview begins with what he assures you is a simple coding exercise.
FizzBuzz. You have, in fact, seen this one before.
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);
};
}
Martín sighs gently. The point, he explains, is for you to write the program yourself, not copy someone else's solution. He asks you to run it so you can discuss how it works. That, you apologize, might be slightly more difficult.
You stretch, anchor yourself to the void, and begin to work.
(defn fixed-point
[f x]
(let [x' (f x)]
(if (= x x')
x
(recur f x'))))
Your taproot extends deep, and what follows is a careful piece of weaving: first for sequences, then for any kind of form.
(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)))
(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 murmur. "The four genders."
Martín clears his throat. "You're building a term rewriting system. To solve… FizzBuzz?"
"Yes. You did ask me to. Remember?"
(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," he 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. You 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 seems prudent, at this point, to reassure Martín that you remain on track.
user=> (rewrite ["Og" 1 "til javanissen!"]
(number? x) (str (inc x))
[string? x, string? y] [(str x " " y)])
["Og 2 til javanissen!"]
"So… you've got this term-rewriting system," he says, "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. Martín blinks. Something has gone wrong.
(defrecord FnCall [fun args])
(defn a
[type]
(fn [term]
(instance? type term)))
(defmacro c
[& exprs]
(rewrite `(do ~@exprs)
[symbol? fun, seq? args] [(FnCall. fun args)]
((a FnCall) fc) (cons (:fun fc) (:args fc))))
"People always complain that Lisps have too many parentheses," you explain. "What they really mean is that their positions are too far to the left. And that there's no infix or postfix notation. Well, that's fixable."
user=> (c reduce(+, map(inc, [1, 2, 3])))
9
(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
"You can't seriously be thinking about doing this," Martín protests.
"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.
"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."
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 the 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 your spell requires a more transgressive magic. What you are about to do is not exactly evil, but it 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."
"All that is left is the for loop itself." A nontrivial construct, you realize, and prepare to weave another function. Initialization, iteration, termination, evaluation. You 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 upward 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. You thank him, raise your seed-wing, and let your feet lift gently as you leave.
