(oodles of delicious atoms)

clojure code lisp .....

Later: Code and Data
Earlier: Painting and Time

A Recursive Feast

In 1983, Douglas R. Hofstadter, author of "Gödel, Escher, Bach: An Eternal Golden Braid" wrote a series of articles on Lisp in Scientific American (later republished in the book Metamagical Themas, which is where I encountered them for the first time). While much of the writing focused on the nature of recursion in programming, the third and last article in the series provided an entertaining example of blurring the line between code and data, which is typical for Lisp (though somewhat less common in Clojure, except for the occasional macro).

In the example, a set of acronyms are presented; each acronym can be "expanded" into a phrase which itself may contain other acronyms. The program generates random expansions of these acronyms, "bottoming out" (hitting the base case) at random, though with increasing probability of termination for more deeply-nested expressions.

What follows is my translation of the Lisp code in his articles into Clojure, with a few extra details and explanations. A few interesting edge cases have to be accounted for to accommodate the differences between the languages.

If you're interested in running the code, it's on GitHub.

Cooking It Up

First, a small macro helps us keep things tidy: defpasta makes a function that simply returns the list supplied as its argument, avoiding the need for the argument vector or the quote. Note that just one small macro provides enough "syntactic sugar" to make the examples more readable. We also attach metadata for convenience in testing (see below).

(defmacro defpasta [name_ & expr]
  `(defn ~(with-meta name_ {:pasta true}) []
     '~@expr))

Next are the actual acronym definitions. These are the definitions Hofstadter uses, with commas treated differently. The commas are important in his output, but commas are whitespace in Clojure… so where the symbols are used with commas in compound statements, we append _CO to tell the program to supply a comma in the output. (Example: SAUCE, becomes SAUCE_CO.)

We cannot, unfortunately, add commas after lists in this way, but his example is inconsistent in this regard (three examples have commas after lists, but the example expansion later in the article does not).

Hostadter presents the acronyms in capital letters, though Common Lisp atoms (analogous to Clojure symbols) are case-insensitive; we follow that convention here and use it to indicate terms which may be expanded… that is to say, the COFFEE in the expansion of SAUCE can itself be expanded to a phrase which includes ESPRESSO, and so on.

(defpasta TOMATOES (TOMATOES on MACARONI (and TOMATOES only)
                             exquisitely SPICED))
(defpasta MACARONI (MACARONI and CHEESE (a REPAST of Naples_CO Italy)))
(defpasta REPAST (rather extraordinary PASTA and SAUCE_CO typical))
(defpasta CHEESE (cheddar_CO havarti_CO, emmentaler
                                (especially SHARP emmenthaler)))
(defpasta SHARP (strong_CO hearty_CO and rather pungent))
(defpasta SPICED (sweetly pickled in CHEESE ENDIVE dressing))
(defpasta ENDIVE (egg NOODLES_CO dipped in vinegar eggnog))
(defpasta NOODLES (NOODLES (oodles of delicious LINGUINI) elegantly served))
(defpasta LINGUINI (LAMBCHOPS (including NOODLES)
                                  gotten usually in Northern Italy))
(defpasta PASTA (PASTA and SAUCE (that's ALL!)))
(defpasta ALL! (a lucious lunch))
(defpasta SAUCE (SHAD and unusual COFFEE (excellente!)))
(defpasta SHAD (SPAGHETTI_CO heated al dente))
(defpasta SPAGHETTI (standard PASTA_CO always good_CO hot particularly
                              (twist_CO then ingest)))
(defpasta COFFEE (choice of fine flavors, particularly ESPRESSO))
(defpasta ESPRESSO (excellent_CO strong_CO powerful_CO rich ESPRESSO_CO
                                 suppressing sleep outrageously))
(defpasta BASTA! (belly all stuffed (tummy ache!)))
(defpasta LAMBCHOPS (LASAGNE and meatballs_CO casually heaped onto PASTA SAUCE))
(defpasta LASAGNE (LINGUINI and SAUCE and GARLIC (NOODLES everywhere!)))
(defpasta RHUBARB (RAVIOLI_CO heated under butter and RHUBARB (BASTA!)))
(defpasta RAVIOLI (RIGATONI and vongole in oil_CO lavishly introduced))
(defpasta RIGATONI (rich Italian GNOCCHI and TOMATOES (or NOODLES instead)))
(defpasta GNOCCHI (GARLIC NOODLES over crisp CHEESE_CO heated immediately))
(defpasta GARLIC (green and red LASAGNE in CHEESE))

Hofstadter leaves the implementation of acronym? undefined, since it is so implementation-specific. In our case, something is an acronym if it's a symbol and its name is equal to an upper case version of itself.

(defn acronym? [x]
  (and (symbol? x)
       (= (name x) (.toUpperCase (name x)))))

We also want to be able to remove commas from a symbol and evaluate the result as a function. This is also very implementation-specific; in our case, it relies on Clojure's machinery for converting symbols to strings and vice-versa, and on the subtle differences between symbols, vars, and functions:

(defn strip-comma-and-eval [sym]
  (let [base-symbol-name (-> sym
                             name
                             (clojure.string/replace #"_CO$" "")
                             symbol)]
    ((-> *ns*
          ns-map
          (get (symbol base-symbol-name))
          var-get))))

(strip-comma-and-eval 'RHUBARB)
;;=>
(RAVIOLI_CO heated under butter and RHUBARB (BASTA!))

lower reduces the probability by some amount to encourage our recursion to bottom out (and thereby avoid stack overflows). Hofstadter multiplies probabilities by 0.8, but I simply square the probability so that higher probabilities decrease more slowly than lower ones as the recursion progresses:

(defn lower [x] (* x x))

A significant portion of Hofstadter's article relates to the recursive expand function, so I won't go into details here. This version is similar to his; it adds a bottoming-out clause to accommodate the base case of an empty phrase (since () and nil are not the same in Clojure, as they are in Common Lisp). Also we use strip-comma-and-eval instead of plain eval to handle the comma-ed symbols.

(defn expand [phrase probability]
  (cond
    (symbol? phrase) phrase
    (empty? phrase) phrase

    (acronym? (first phrase))
    (if (< (rand) probability)
      (concat
       (expand (strip-comma-and-eval (first phrase)) (lower probability))
       (expand (rest phrase) probability))
      (cons (first phrase) (expand (rest phrase) probability)))

    :else (cons (expand (first phrase) (lower probability))
                (expand (rest phrase) (lower probability)))))

Ultimately we want to make the output similar to what Hofstadter shows in the book. The normalize function does this, relying on two helper functions, whose names are self-explanatory:

(defn lower-case-symbol [x]
  (if-not (symbol? x)
    x
    (-> x name .toLowerCase symbol)))

(defn get-commas-back [x]
  (if-not (symbol? x)
    x
    (-> x
        name
        (clojure.string/replace #"_CO$" ",")
        symbol)))

When we're done expanding our lists of food (and our bellies), we prepare our data for output to the user: turn _CO suffixes into actual commas (using the fact that (symbol "x,") yields a valid symbol, if one that would be hard to read back at the REPL); and, lower-case all symbols to adhere to the style of the output shown in Metamagical Themas:

(defn normalize [expr]
  (->> expr
       (clojure.walk/postwalk get-commas-back)
       (clojure.walk/postwalk lower-case-symbol)))

Dinner Is Served

Now for the actual function we'll use to generate our expansions. Setting a large probability will ensure longer examples:

(defn dinner [expr]
  (normalize (expand expr 0.9999)))

We should test our code to make sure it doesn't bomb out on any of our acronyms. Here we find all the acronyms based on the metadata added by the defpasta macro, ensuring each runs to completion:

(let [nsm (ns-map *ns*)]
  (doseq [[k v] nsm :when (:pasta (meta v))]
    (dotimes [_ 10]
      (dinner (list k)))))

If, like me, you use Emacs and CIDER and want long REPL examples, you have to set `*print-length*` to something bigger than its default:

(set! *print-length* 1000)

Now to run it! Are you hungry yet?

(dinner '(LINGUINI))
;;=>
(lasagne and meatballs, casually heaped onto pasta sauce (including
noodles) gotten usually in northern italy and standard pasta, always
good, hot particularly (twist, then ingest) heated al dente and
unusual coffee (excellente!) and green and red lasagne in cheese
(noodles (oodles of delicious linguini) elegantly served (oodles of
delicious linguini) elegantly served everywhere!) and meatballs,
casually heaped onto pasta shad and unusual coffee (excellente!)
(including noodles (oodles of delicious linguini) elegantly served
(oodles of delicious linguini) elegantly served (oodles of delicious
linguini) elegantly served (oodles of delicious linguini) elegantly
served (oodles of delicious lasagne and meatballs, casually heaped
onto pasta sauce (including noodles) gotten usually in northern italy)
elegantly served) gotten usually in northern italy and standard pasta
and shad and unusual coffee (excellente!) (that's all!) and shad and
unusual coffee (excellente!) (that's all!) always good, hot
particularly (twist, then ingest) heated al dente and unusual choice
of fine flavors particularly espresso (excellente!) and green and red
lasagne in cheese (noodles (oodles of delicious linguini) elegantly
served (oodles of delicious linguini) elegantly served (oodles of
delicious linguini) elegantly served (oodles of delicious linguini)
elegantly served everywhere!) and meatballs, casually heaped onto
pasta and sauce (that's all!) and sauce (that's all!) and shad and
unusual coffee (excellente!) (that's all!) sauce (including noodles
(oodles of delicious linguini) elegantly served (oodles of delicious
lambchops (including noodles) gotten usually in northern italy)
elegantly served (oodles of delicious lambchops (including noodles)
gotten usually in northern italy) elegantly served) gotten usually in
northern italy and standard pasta and shad and unusual coffee
(excellente!) (that's all!) and standard pasta, always good, hot
particularly (twist, then ingest) heated al dente and unusual coffee
(excellente!) (that's all!) and spaghetti, heated al dente and unusual
coffee (excellente!) (that's a lucious lunch) and standard pasta,
always good, hot particularly (twist, then ingest) heated al dente and
unusual coffee (excellente!) (that's a lucious lunch) always good, hot
particularly (twist, then ingest) heated al dente and unusual choice
of fine flavors particularly espresso (excellente!) and green and red
linguini and sauce and garlic (noodles everywhere!) and meatballs,
casually heaped onto pasta sauce (including noodles) gotten usually in
northern italy and spaghetti, heated al dente and unusual coffee
(excellente!) and green and red lasagne in cheese (noodles (oodles of
delicious linguini) elegantly served everywhere!) in cheese (noodles
(oodles of delicious linguini) elegantly served (oodles of delicious
linguini) elegantly served (oodles of delicious linguini) elegantly
served (oodles of delicious linguini) elegantly served (oodles of
delicious linguini) elegantly served (oodles of delicious lambchops
(including noodles) gotten usually in northern italy) elegantly served
(oodles of delicious linguini) elegantly served (oodles of delicious
linguini) elegantly served everywhere!) and meatballs, casually heaped
onto pasta and shad and unusual coffee (excellente!) (that's a lucious
lunch) and sauce (that's all!) and spaghetti, heated al dente and
unusual coffee (excellente!) (that's a lucious lunch) and standard
pasta and sauce (that's all!) always good, hot particularly (twist,
then ingest) heated al dente and unusual coffee (excellente!) (that's
a lucious lunch) shad and unusual choice of fine flavors particularly
espresso (excellente!) (including noodles (oodles of delicious
linguini) elegantly served (oodles of delicious linguini) elegantly
served (oodles of delicious linguini) elegantly served (oodles of
delicious linguini) elegantly served (oodles of delicious lasagne and
meatballs, casually heaped onto pasta sauce (including noodles) gotten
usually in northern italy) elegantly served (oodles of delicious
lambchops (including noodles) gotten usually in northern italy)
elegantly served (oodles of delicious linguini and sauce and garlic
(noodles everywhere!) and meatballs, casually heaped onto pasta sauce
(including noodles (oodles of delicious linguini) elegantly served)
gotten usually in northern italy) elegantly served (oodles of
delicious lambchops (including noodles (oodles of delicious linguini)
elegantly served) gotten usually in northern italy) elegantly served
(oodles of delicious lasagne and meatballs, casually heaped onto pasta
sauce (including noodles) gotten usually in northern italy and shad
and unusual coffee (excellente!) and garlic (noodles everywhere!) and
meatballs, casually heaped onto pasta sauce (including noodles (oodles
of delicious linguini) elegantly served (oodles of delicious linguini)
elegantly served) gotten usually in northern italy) elegantly served
(oodles of delicious linguini and sauce and garlic (noodles
everywhere!) and meatballs, casually heaped onto pasta sauce
(including noodles) gotten usually in northern italy and spaghetti,
heated al dente and unusual coffee (excellente!) and garlic (noodles
(oodles of delicious linguini) elegantly served everywhere!) and
meatballs, casually heaped onto pasta sauce (including noodles (oodles
of delicious linguini) elegantly served (oodles of delicious linguini)
elegantly served) gotten usually in northern italy) elegantly served)
gotten usually in northern italy)

Man, I'm stuffed!

A talk based on this code was given as in instructional / fun exercise at Clojurepalooza at OpinionLab in May of 2018.

Later: Code and Data
Earlier: Painting and Time