Clojure may be a new language, but Lisp has a long history.
Translating Scheme and Common Lisp classics into Clojure is always an
interesting exercise, and often illuminates the differences and
comparative advantages of various Lisp-y languages. (For more
Lisp-to-Clojure resources see this
list.
Or, if you’d like to try porting some Scheme, consider helping
translate SICP).
This weekend, I spent some time with Paul Graham’s classic On
Lisp.
In Chapter 6, Graham shows how to use
closures
to model nodes in a network, representing a 20 questions game as a self-traversing binary
tree. Here’s his original code, and my best attempts at Clojure translations.
The most obvious model for a set of connected nodes is a nested data
structure, like a map of maps. In Common Lisp, Graham uses a mutable
hashmap of structured
types,
each pointing to their neighbors in the network:
A simple map seems like a sufficient replacement in Clojure. A single
node looks like this:
1
{:people{:contents"Is the person a man?", :yes:male, :no:female}}
And the full tree looks like the following. Each node’s :yes or :no keyword
points to the next node in the tree:
123456
{:penny{:contents"Abraham Lincoln.", :yesnil, :nonil},
:coin{:contents"Is the coin a penny?", :yes:penny, :no:other-coin},
:USA{:contents"Is he on a coin?", :yes:coin, :no:no-coin},
:dead{:contents"Was he from the USA?", :yes:USA, :no:elsewhere},
:male{:contents"Is he living?", :yes:live, :no:dead},
:people{:contents"Is the person a man?", :yes:male, :no:female}}
Here’s my first draft for defining nodes in Clojure. Since the Common
Lisp version used a mutable variable, I used a Clojure atom to store
network state:
123456789101112
(def nodes(atom{}))(defn defnode[name contents&[yesno]](swap!nodesassoc name {:contentscontents:yesyes:nono}))(defn make-nodes[](defnode:people"Is the person a man?":male:female)(defnode:male"Is he living?":live:dead)(defnode:dead"Was he from the USA?":USA:elsewhere)(defnode:USA"Is he on a coin?":coin:no-coin)(defnode:coin"Is the coin a penny?":penny:other-coin)(defnode:penny"Abraham Lincoln."))
Traversing the network is simple: get a node, print the associated
question, prompt for input, get the next node, and repeat. Here’s the original Common Lisp:
Of course, there’s no reason to bother swapping and dereferencing an
atom as long as the tree won’t need to change at runtime. This
immutable version works just as well:
1234567891011121314151617181920212223242526
(defn defnode[nodesname contents&[yesno]](assoc nodesname {:contentscontents:yesyes:nono}))(defn make-nodes[](-> {}(defnode:people"Is the person a man?":male:female)(defnode:male"Is he living?":live:dead)(defnode:dead"Was he from the USA?":USA:elsewhere)(defnode:USA"Is he on a coin?":coin:no-coin)(defnode:coin"Is the coin a penny?":penny:other-coin)(defnode:penny"Abraham Lincoln.")))(def nodes(make-nodes))(defn run-node[nodesname](let [node (nodesname)contents(node :contents)yes(node :yes)no(node :no)](if yes(do(println contents)(if (= "yes"(read-line))(run-nodenodesyes)(run-nodenodesno)))(println contents))))
Using a closure rolls the data structure and traversal code into one,
by associating the yes and no fields with anonymous functions that
handle the same logic as run-node. Here’s Graham’s CL version:
And here’s mine in Clojure. The double-parens around (@nodes yes)
and (@nodes no) call the anonymous function, instead of just
returning it.
1234567891011121314151617181920
(def nodes(atom{}))(defn defclosure[name contents&[yesno]](swap!nodesassoc name(if yes(fn [](println contents)(if (= "yes"(read-line))((@nodesyes))((@nodesno))))(fn [](println contents)))))(defn make-nodes[](defclosure:people"Is the person a man?":male:female)(defclosure:male"Is he living?":live:dead)(defclosure:dead"Was he from the USA?":USA:elsewhere)(defclosure:USA"Is he on a coin?":coin:no-coin)(defclosure:coin"Is the coin a penny?":penny:other-coin)(defclosure:penny"Abraham Lincoln."))
Now, traversing the tree is as simple as calling:
1
((nodes:people))
And watching the tree traverse itself. You can find my code from this
post here. For more on closures in Lisp,
check out the rest of Chapter 6.