actual elements, this difference in asymptotic complexity will shrink. But it’s an
extremely efficient way to determine the smallest n values in a large unsorted (Knuth
1998) sequence.
6.5
Summary
We’ve covered the topics of immutability, persistence, and laziness in this chapter. Clo-
jure’s core composite data types are all immutable and persistent by default, and
though this fact might presuppose fundamental inefficiencies, we’ve shown how Clo-
jure addresses them. The implementation of a persistent sorted binary tree demon-
strated how structural sharing eliminated the need for full copy-on-write. But
structural sharing isn’t enough to guarantee memory efficiency, and that’s where the
benefits of laziness come into the fold. The implementation of a lazy, tail-recursive
quicksort demonstrated that laziness guarantees that sequences won’t be fully realized
in memory at any given step.
In the next chapter, we’ll dive into Clojure’s notion of functional programming.
Along the way, you’ll notice that much of the shape of functional implementations in
Clojure will be influenced by the topics discussed in this chapter.
Download from Wow! eBook <www.wowebook.com>
Functional
programming
This chapter covers
Functions in all their forms
Closures
Thinking recursively
Putting it all together: A* pathfinding
At the core of functional programming is a formal system of computation known as
the lambda calculus (Pierce 2002). Clojure functions, in adherence with the lambda
calculus, are first-class—they can be both passed as arguments and returned as
results from other functions. This book isn’t about the lambda calculus. Instead
we’ll explore Clojure’s particular flavor of functional programming. We’ll cover a
vast array of useful topics, including function composition, partial evaluation,
recursion, lexical closures, pure functions, function constraints, higher-order func-
tions, and first-class functions. We’ll use that last item as our starting point.
125
Download from Wow! eBook <www.wowebook.com>
126
CHAPTER 7 Functional programming
7.1
Functions in all their forms
In chapter 5, we mentioned that most of Clojure’s composite types can be used as
functions of their elements. As a refresher, recall that vectors are functions of their
indices, so executing ([:a :b] 0) will return :a. But this can be used to greater effect
by passing the vector as a function argument:
(map [:chthon :phthor :beowulf :grendel] #{0 3})
;=> (:chthon :grendel)
In the example, we’ve used the vector as the function to map over a set of indices,
indicating its first and fourth elements by index. Clojure collections offer an interest-
ing juxtaposition, in that not only can Clojure collections act as functions, but Clojure
functions can also act as data—an idea known as first-class functions.
7.1.1
First-class functions
In a programming language such as Java, there’s no notion of a standalone function.1
Instead, every problem solvable by Java must be performed with the fundamental phi-
losophy that everything is an object. This view on writing programs is therefore rooted
in the idea that behaviors within a program must be either modeled as class instances
or attached to them—wise or not. Clojure, on the other hand, is a functional pro-
gramming language and views the problem of software development as the applica-
tion of functions to data. Likewise, functions in Clojure enjoy equal standing with
data—functions are first-class citizens. Before we start, we should define what makes
something first-class:
It can be created on demand.
It can be stored in a data structure.
It can be passed as an argument to a function.
It can be returned as the value of a function.
Those of you coming from a background in Java might find the idea of creating func-
tions on demand analogous to the practice of creating anonymous inner classes to
handle Swing events (to name only one use case). Though similar enough to start on
the way toward understanding functional programming, it’s not a concept likely to
bear fruit, so don’t draw conclusions from this analogy.
CREATING FUNCTIONS ON DEMAND USING COMPOSITION
Even a cursory glance at Clojure is enough to confirm that its primary unit of compu-
tation is the function, be it created or composed of other functions:
(def fifth (comp first rest rest rest rest))
(fifth [1 2 3 4 5])
;=> 5
1
Although the likely inclusion of closures in some future version of Java should go a long way toward invalidat-
ing this. Additionally, for those of you coming from a language such as Python, Scala, or another Lisp, the
notion of a first-class function is likely not as foreign as we make it out to be.
Download from Wow! eBook <www.wowebook.com>
Functions in all their forms
127
The function fifth wasn’t defined with fn or defn forms shown before, but instead
built from existing parts using the comp (compose) function. But it may be more inter-
esting to take the idea one step further by instead proving a way to build arbitrary nth
functions2 as shown here:
(defn fnth [n]
(apply comp
(cons first
(take (dec n) (repeat rest)))))
((fnth 5) '[a b c d e])
;=> e
The function fnth builds a list of the function rest of the appropriate length with a
final first consed onto the front. This list is then fed into the comp function via
apply, which takes a function and a sequence of things and effectively calls said func-
tion with the list elements as its arguments. At this point, there’s no longer any doubt
that the function fnth builds new functions on the fly based on its arguments. Creat-
ing new functions in this way is a powerful technique, but it takes some practice to
think in a compositional way. It’s relatively rare to see more than one open-parenthe-
sis in a row like this in Clojure, but when you see it, it’s almost always because a func-
tion (such as fnth) is creating and returning a function that’s called immediately. A
general rule of thumb is that if you need a function that applies a number of functions
serially to the return of the former, then composition is a good fit:
(map (comp keyword #(.toLowerCase %) name) '(a B C))
;=> (:a :b :c)
Splitting functions into smaller, well-defined pieces fosters composability and, as a
result, reuse.
CREATING FUNCTIONS ON DEMAND USING PARTIAL FUNCTIONS
There may be times when instead of building a new function from chains of other
functions as comp allows, you need to build a function from the partial application of
another:
((partial + 5) 100 200)
;=> 305
The function partial builds (Tarver 2008) a new function that consists of the partial
application of the single argument 5 to the addition function. When the returned par-
tial function is passed the arguments 100 and 200, the result is their summation plus
that of the value 5 captured by partial.
PARTIAL APPLICATION ISN’T CURRYING The use of partial differs from the
notion of currying in a fundamental way. A function built with partial will
attempt to evaluate whenever it’s given another argument. A curried function
2 We know that Clojure provides an nth function that works slightly differently, but in this case please indulge
our obtuseness.
Download from Wow! eBook <www.wowebook.com>
128
CHAPTER 7 Functional programming
on the other hand will return another curried function until it receives a pre-
determined number of arguments—only then will it evaluate. Because Clojure
allows functions of variable number of arguments, currying makes little sense.
We’ll discuss more about utilizing partial later in this section, but as a final point
observe that ((partial + 5) 100 200) is equivalent to (#(apply + 5 %&) 100 200).
REVERSING TRUTH WITH COMPLEMENT
One final function builder discussed here is the complement function. Simply put, this
function takes a function that returns a truthy value and returns the opposite truthy
value:
(let [truthiness (fn [v] v)]
[((complement truthiness) true)
((complement truthiness) 42)
((complement truthiness) false)
((complement truthiness) nil)])
;=> [false false true true]
((complement even?) 2)
;=> false
Note that (complement even?) is equivalent to (comp not even?).
USING FUNCTIONS AS DATA
First-class functions can not only be treated as data; they are data. Because a function is
first-class, it can be stored in a container expecting a piece of data, be it a local, a refer-
ence, collections, or anything able to store a java.lang.Object. This is a significant
departure from Java, where methods are part of a class but don’t stand alone at run-
time (Forman 2004). One particularly useful method for treating functions as data is
the way that Clojure’s testing framework clojure.test stores and validates unit tests
in the metadata of a Var holding a function. These unit tests are keyed with the :test
keyword, laid out as
(defn join
{:test (fn []
(assert
(= (join "," [1 2 3]) "1,3,3")))}
[sep s]
(apply str (interpose sep s)))
We’ve modified our old friend join by attaching some metadata containing a faulty
unit test. Of course, by that we mean that the attached unit test is meant to fail in this
case. The clojure.test/run-tests function is useful for running attached unit tests
in the current namespace:
(use '[clojure.test :as t])
(t/run-tests)
; Testing user
;
; ERROR in (join) (test.clj:646)
; ...
Download from Wow! eBook <www.wowebook.com>
Functions in all their forms
129
; actual: java.lang.AssertionError:
; Assert failed: (= (join "," [1 2 3]) "1,3,3")
; ...
As expected, the faulty unit test for join failed. Unit tests in Clojure only scratch the
surface of the boundless spectrum of examples using functions as data, but for now
they’ll do, as we move into the notion of higher-order functions.
7.1.2
Higher-order functions
A higher-order function is a function that does at least one of the following:
Takes one or more functions as arguments
Returns a function as a result
A Java programmer might be familiar with the practices of subscriber patterns or
schemes using more general-purpose callback objects. There are scenarios such as
these where Java treats objects like functions, but as with anything in Java, you’re really
dealing with objects containing privileged methods.
FUNCTIONS AS ARGUMENTS
In this book, we’ve used and advocated the use of the sequence functions map, reduce,
and filter—all of which expect a function argument that’s applied to the elements
of the sequence arguments. The use of functions in this way is ubiquitous in Clojure
and can make for truly elegant solutions. Let’s look at a simple example of a function
that takes a sequence of maps and a function working on each, and returns a
sequence sorted by the results of the function. The implementation in Clojure is
straightforward and clean:
(def plays [{:band "Burial", :plays 979, :loved 9}
{:band "Eno", :plays 2333, :loved 15}
{:band "Bill Evans", :plays 979, :loved 9}
{:band "Magma", :plays 2665, :loved 31}])
(def sort-by-loved-ratio (partial sort-by #(/ (:plays %) (:loved %))))
The function with the overly descriptive name sort-by-loved-ratio is built from the
partial application of the function sort-by and an anonymous function dividing the
:plays field by the :loved field. This is a simple solution to the problem presented,
and its usage is equally so:
(sort-by-loved-ratio plays)
;=> ({:band "Magma", :plays 2665, :loved 31}
{:band "Burial", :plays 979, :loved 9}
{:band "Bill Evans", :plays 979, :loved 9}
{:band "Eno", :plays 2333, :loved 15})
We intentionally used the additional higher-order function sort-by to avoid reimple-
menting core functions and instead build our program from existing parts. You should
strive for the same whenever possible.
Download from Wow! eBook <www.wowebook.com>
130
CHAPTER 7 Functional programming
FUNCTIONS AS RETURN VALUES
We’ve already used functions returning functions in this chapter with comp, partial,
and complement, but you could build functions that do the same. We’ll extend the ear-
lier example to provide a function that sorts rows based on some number of column
values. This is similar to the way that spreadsheets operate, in that you can sort on a
primary column while falling back on a secondary column to provide the sort order
on matching results in the primary. This behavior is typically performed along any
number of columns, cascading down from the primary column to the last; each sub-
group is sorted appropriately, as the expected result illustrates:
(sort-by (columns [:plays :loved :band]) plays)
;=> ({:band "Bill Evans", :plays 979, :loved 9}
{:band "Burial", :plays 979, :loved 9}
{:band "Eno", :plays 2333, :loved 15}
{:band "Magma", :plays 2665, :loved 31})
This kind of behavior sounds complex on the surface but is shockingly simple3 in its
Clojure implementation:
(defn columns [column-names]
(fn [row]
(vec (map row column-names))))
Running the preceding expression shows that the rows for Burial and Bill Evans
have a tertiary column sorting. The function columns returns another function
expecting a map. This return function is then supplied to sort-by to provide the
value on which the plays vector would be sorted. Perhaps you see a familiar pattern:
we apply the column-names vector as a function across a set of indices, building a
sequence of its elements at those indices. This action will return a sequence of the val-
ues of that row for the supplied column names, which is then turned into a vector so
that it can then be used as the sorting function,4 as structured here:
(vec (map (plays 0) [:plays :loved :band]))
;=> [979 9 "Burial"]
This resulting vector is then used by sort-by to provide the final ordering.
Building your programs using first-class functions in concert with higher-order
functions will reduce complexities and make your codebase more robust and exten-
sible. In the next subsection, we’ll explore pure functions, which all prior functions
in this section have been, and explain why your own applications should strive
toward purity.
3
Strictly speaking, the implementation of columns should use #(% row) instead of just row, because we can’t
always assume that the row is implemented as a map (a record might be used instead) and therefore directly
usable as a function. Records will be discussed further in chapter 8.
4
Because sort-by is higher-order, it naturally expects a function argument. As mentioned, vectors can also
be used as functions. However, as we will discuss in detail in section 10.4, all closure functions implement the
java.util.Comparator interface, which in this case is the driving force behind the sorting logic behind
sort-by!
Download from Wow! eBook <www.wowebook.com>
Functions in all their forms
131
Prefer higher-order functions when processing sequences
We mentioned in section 6.3 that one way to ensure that lazy sequences are never
fully realized in memory is to prefer (Hutton 1999) higher-order functions for process-
ing. Most collection processing can be performed with some combination of the fol-
lowing functions:
map, reduce, filter, for, some, repeatedly, sort-by, keep
take-while, and drop-while
But higher-order functions aren’t a panacea for every solution. Therefore, we’ll cover
the topic of recursive solutions deeper in section 7.3 for those cases when higher-
order functions fail or are less than clear.
7.1.3
Pure functions
Simply put, pure functions are regular functions that, through convention, conform to
the following simple guidelines:
The function always returns the same result, given some expected arguments.
The function doesn’t cause any observable side-effects.
Though Clojure is designed to minimize and isolate side-effects, it’s by no means a
purely functional language. But there are a number of reasons why you’d want to
build as much of your system as possible from pure functions, and we’ll enumerate a
few presently.
REFERENTIAL TRANSPARENCY
If a function of some arguments always results in the same value and changes no other
values within the greater system, then it’s essentially a constant, or referentially trans-
parent (the reference to the function is transparent to time). Take a look at pure func-
tion keys-apply:
(defn keys-apply [f ks m]
"Takes a function, a set of keys, and a map and applies the function
to the map on the given keys. A new map of the results of the function
applied to the keyed entries is returned."
(let [only (select-keys m ks)]
(zipmap (keys only) (map f (vals only)))))
(keys-apply #(.toUpperCase %) #{:band} (plays 0))
;=> {:band "BURIAL"}
Using another pure function manip-map, we can then manipulate a set of keys based
on a given function:
(defn manip-map [f ks m]
"Takes a function, a set of keys, and a map and applies
the function to the map on the given keys. A modified
version of the original map is returned with the results
of the function applied to each keyed entry."
(conj m (keys-apply f ks m)))
Download from Wow! eBook <www.wowebook.com>
132
CHAPTER 7 Functional programming
(manip-map #(int (/ % 2)) #{:plays :loved} (plays 0))
;=> {:band "Burial", :plays 489, :loved 4}
The functions keys-apply and manip-map are both5 pure functions, illustrated by the
fact that you can replace them in the context of a larger program with their expected
return values and not change the outcome. Pure functions exist outside the bounds of
time. But if you make either keys-apply or manip-map reliant on anything but its
arguments or generate a side-effect within, then referential transparency dissolves.
We’ll add one more function to illustrate this:
(defn halve! [ks]
(map (partial manip-map #(int (/ % 2)) ks) plays))
(halve! [:plays])
;=> ({:band "Burial", :plays 489, :loved 9}
{:band "Eno", :plays 1166, :loved 15}
{:band "Bill Evans", :plays 489, :loved 9}
{:band "Magma", :plays 1332, :loved 31})
The function halve! works against the global plays and is no longer limited to gener-
ating results solely from its arguments. Because plays could change at any moment,
there’s no guarantee that halve! would return the same value given any particular
argument.
OPTIMIZATION
If a function is referentially transparent, then it can more easily be optimized using
techniques such as memoization (discussed in chapter 12) and algebraic manipula-
tions (Wadler 1989).
TESTABILITY
If a function is referentially transparent, then it’s easier to reason about and therefore
more straightforward to test. Building halve! as an impure function forces the need
to test against the possibility that plays could change at any time, complicating mat-
ters substantially. Imagine the confusion should you add further impure functions
based on further external transient values.
7.1.4
Named arguments
Some programming languages allow functions to take named arguments; Python is
one such language, as seen here:
def slope(p1=(0,0), p2=(1,1)):
return (float(p2[1] - p1[1])) / (p2[0] - p1[0])
slope((4,15), (3,21))
#=> -6.0
slope(p2=(2,1))
#=> 0.5
slope()
#=> 1.0
5 These functions are based on a similar implementation created by Steven Gilardi.
Download from Wow! eBook <www.wowebook.com>
Functions in all their forms
133
The Python function slope calculates the slope of a line given two tuples defining
points on a line. The tuples p1 and p2 are defined as named parameters, allowing
either or both to be omitted in favor of default values, or passed in any order as a
named parameter. Clojure provides a similar feature using its destructuring mecha-
nism coupled with the optional arguments flag &. The same function would be written
using Clojure’s named arguments as in the following listing.
Listing 7.1 Named arguments in Clojure functions
(defn slope
[& {:keys [p1 p2] :or {p1 [0 0] p2 [1 1]}}]
(float (/ (- (p2 1) (p1 1))
(- (p2 0) (p1 0)))))
(slope :p1 [4 15] :p2 [3 21])
;=> -6.0
(slope :p2 [2 1])
;=> 0.5
(slope)
;=> 1.0
Clojure’s named arguments are built on the destructuring mechanism outlined in sec-
tion 3.3, allowing much richer ways to declare them.
7.1.5
Constraining functions with pre- and postconditions
Every function in Clojure can potentially be constrained on its inputs, its output, and
some arbitrary relationship between them. These constraints take the form of pre-
and postcondition vectors contained in a map defined in the function body. We can
simplify the slope function to the base case to more clearly illustrate the matter of
constraints:
(defn slope [p1 p2]
{:pre [(not= p1 p2) (vector? p1) (vector? p2)]
:post [(float? %)]}
(/ (- (p2 1) (p1 1))
(- (p2 0) (p1 0))))
The constraint map defines two entries: :pre constraining the input parameters and
:post the return value. The function calls in the constraint vectors are all expected to
return true for the constraints to pass (via logical and). In the case of the revised
slope function, the input constraints are that the points must not be equal, and they
must both be vectors. In the postcondition, the constraint is that the return result
must be a floating-point value. We run through a few scenarios in the following listing
to see how the new implementation works.
Download from Wow! eBook <www.wowebook.com>
134
CHAPTER 7 Functional programming
Listing 7.2 Testing the slope function constraints
(slope [10 10] [10 10])
Same points
; java.lang.AssertionError: Assert failed: (not= p1 p2)
(slope [10 1] '(1 20))
p2 is List
; java.lang.AssertionError: Assert failed: (vector? p2)
(slope [10 1] [1 20])
Float not returned
; java.lang.AssertionError: Assert failed: (float? %)
(slope [10.0 1] [1 20])
Any/all as floating point
;=> -2.111111111111111
Clojure also provides a simple assertion macro that can be used to emulate some pre-
and postconditions. Using assert instead of :pre is typically fairly straightforward.
But using assert instead of :post is cumbersome and awkward. On the contrary,
restricting yourself to constraint maps will cover most of the expected cases covered by
assert, which can be used to fill in the remaining holes (such as loop invariants). In
any case, constraint maps provide standard hooks into the assertion machinery of Clo-
jure, while using assert is by its nature ad hoc. Yet another advantage for :pre and
:post is that they allow the assertions to come from a different source than the body
of the function, which we’ll address next.
DECOUPLING ASSERTIONS FROM FUNCTIONS
The implementation of slope corresponds to a well-established mathematic property.
As a result, it makes perfect sense to tightly couple the constraints and the work to be
done to perform the calculation. But not all functions are as well-defined as slope,
and therefore could benefit from some flexibility in their constraints. Imagine a func-
tion that takes a map, puts some keys into it, and returns the new map, defined as
(defn put-things [m]
(into m {:meat "beef" :veggie "broccoli"}))
(put-things {})
;=> {:meat "beef", :veggie "broccoli"}
How would you add constraints to put-things? You could add them directly to the
function definition, but the consumers of the map might have differing requirements
for the entries added. Instead, observe how we can abstract the constraints into
another function:
(defn vegan-constraints [f m]
{:pre [(:veggie m)]
:post [(:veggie %) (nil? (:meat %))]}
(f m))
(vegan-constraints put-things {:veggie "carrot"})
; java.lang.AssertionError: Assert failed: (nil? (:meat %))
The vegan-constraints function applies specific constraints to an incoming function,
stating that the map coming in and going out should have some kind of veggie and
Download from Wow! eBook <www.wowebook.com>
Closures
135
should never have meat in the result. The beauty of this scheme is that you can create
contextual constraints based on the appropriate expected results, as shown next.
Listing 7.3 Menu constraints
(defn balanced-diet [f m]
{:post [(:meat %) (:veggie %)]}
Make sure there’s
(f m))
meat and veggie
(balanced-diet put-things {})
;=> {:veggie "broccoli", :meat "beef"}
(defn finicky [f m]
Never change
{:post [(= (:meat %) (:meat m))]}
the meat
(f m))
(finicky put-things {:meat "chicken"})
; java.lang.AssertionError: Assert failed: (= (:meat %) (:meat m))
By pulling out the assertions into a wrapper function, we’ve detached some domain-
specific requirements from a potentially globally useful function and isolated them in
aspects (Laddad 2003). By detaching pre- and postconditions from the functions them-
selves, you can mix in any implementation that you please, knowing that as long as it
fulfills the contract (Meyer 1991), its interposition is transparent. This is only the
beginning of the power of Clojure’s pre- and postconditions, and we’ll come back to it
a few times more to see how it can be extended and utilized.
Now that we’ve covered some of the powerful features available via Clojure’s func-
tions, we’ll take a step further by exploring lexical closures.
7.2
Closures
On his next walk with Qc Na, Anton attempted to impress his master by saying
“Master, I have diligently studied the matter, and now understand that objects are
truly a poor man’s closures.” Qc Na responded by hitting Anton with his stick,
saying “When will you learn? Closures are a poor man’s object.” At that moment,
Anton became enlightened.
—Part of a parable by Anton van Straaten
It took only 30 years, but closures (Sussman 1975) are now a key feature of main-
stream programming languages—Perl and Ruby support them, and JavaScript derives
much of what power it has from closures. So what’s a closure? In a sentence, a closure is
a function that has access to locals from a larger scope, namely the context in which it
was defined:
(def times-two
(let [x 2]
(fn [y] (* y x))))
The fn form defines a function and uses def to store it in a Var named times-two.
The let forms a lexical scope in which the function was defined, so the function gains
access to all the locals in that lexical context. That’s what makes this function a clo-
sure: it uses the local x that was defined outside the body of the function, and so the
Download from Wow! eBook <www.wowebook.com>
136
CHAPTER 7 Functional programming
local and its value become a property of the function itself. The function is said to close
over the local6 x, as in the following example:
(times-two 5)
;=> 10
This isn’t terribly interesting, but one way to make a more exciting closure is to have it
close over something mutable:
(def add-and-get
(let [ai (java.util.concurrent.atomic.AtomicInteger.)]
(fn [y] (.addAndGet ai y))))
(add-and-get 2)
;=> 2
(add-and-get 2)
;=> 4
(add-and-get 7)
;=> 11
The java.util.concurrent.atomic.AtomicInteger class simply holds an integer
value, and its .addAndGet method adds to its value, stores the result, and also returns
the result. The function add-and-get is holding onto the same instance of Atomic-
Integer, and each time it’s called, the value of that instance is modified. Unlike the
earlier times-two function, this one can’t be rewritten with the local ai defined inside
the function. If you tried, each time the function was called, it would create a new
instance with a default value of 0 to be created and stored in ai—clearly not what
should happen. A point of note about this technique is that when closing over some-
thing mutable, you run the risk of making your functions impure and thus more diffi-
cult to test and reason about, especially if the mutable local is shared.
FUNCTIONS RETURNING CLOSURES
Each of the previous examples created a single closure, but by wrapping similar code
in another function definition, you can create more closures on demand. For exam-
ple, we could take the earlier times-two example and generalize it to take an argu-
ment instead of using 2 directly:
(defn times-n [n]
(let [x n]
(fn [y] (* y x))))
We’ve covered functions returning functions before, but if you’re not already familiar
with closures, this may be a stretch. We now have an outer function stored in a Var
named times-n—note we’ve used defn instead of def. When times-n is called with an
argument, it’ll return a new closure created by the fn form and closing over the local
x. The value of x for this closure will be whatever was passed in to times-n. Thus when
we call this returned closure with an argument of its own, it’ll return the value of y
times x, as shown:
6 Locals like x in this example are sometimes called free variables. We don’t use the term because Clojure locals
are immutable.
Download from Wow! eBook <www.wowebook.com>
Closures
137
(times-n 4)
;=> #<user$times_n$fn__39 user$times_n$fn__39@427be8c2>
Viewing the function form for this closure isn’t too useful, so instead we can store it in
a Var, allowing us to call it by a friendlier name such as times-four:
(def times-four (times-n 4))
Here we’re using def again simply to store what times-n returns—a closure over the
number 4:
(times-four 10)
;=> 40
Note that when calling the closure stored in times-four, it used the local it had closed
over as well as the argument in the call.
CLOSING OVER PARAMETERS
In our definition of times-n, we created a local x using let and closed over that
instead of closing over the argument n directly. But this was only to help focus the dis-
cussion on other parts of the function. In fact, closures close over parameters of outer
functions in exactly the same way as they do over let locals. Thus times-n could be
defined without any let at all:
(defn times-n [n]
(fn [y] (* y n)))
All of the preceding examples would work exactly the same. Here’s another function
that creates and returns a closure in a similar way. Note again that the inner function
maintains access to the outer parameter even after the outer function has returned:
(defn divisible [denom]
(fn [num]
(zero? (rem num denom))))
We don’t have to store a closure in a Var, but can instead create one and call it
immediately:
((divisible 3) 6)
;=> true
((divisible 3) 7)
;=> false
Instead of storing or calling a closure, a particular need is best served by passing a clo-
sure along to another function that will use it.
PASSING CLOSURES AS FUNCTIONS
We’ve shown many examples in previous chapters of higher-order functions built in to
Clojure’s core libraries. What we’ve glossed over so far is that anywhere a function is
expected, a closure can be used instead. This has dramatic consequences for how
powerful these functions can be.
Download from Wow! eBook <www.wowebook.com>
138
CHAPTER 7 Functional programming
For example, filter takes a function (called a predicate in this case) and a sequence,
applies the predicate to each value of the sequence,7 and returns a sequence of the just
the values for which the predicate returned something truthy. A simple example of its
use would be to return only the even numbers from a sequence of numbers:
(filter even? (range 10))
;=> (0 2 4 6 8)
Note that filter only ever passes a single argument to the predicate given it. Without
closures, this might be restrictive, but with them we can simply close over the values
needed:
(filter (divisible 4) (range 10))
;=> (0 4 8)
It’s common to define a closure right on the spot where it’s used, closing over what-
ever local-context is needed, as shown:
(defn filter-divisible [denom s]
(filter (fn [num] (zero? (rem num denom))) s))
(filter-divisible 4 (range 10))
;=> (0 4 8)
This kind of on-the-spot anonymous function definition is desired frequently enough
that Clojure spends a little of its small syntax budget on the reader feature to make
such cases more succinct. This #() form was first introduced in chapter 2, and in this
case could be used to write the definition of filter-divisible as
(defn filter-divisible [denom s]
(filter #(zero? (rem % denom)) s))
(filter-divisible 5 (range 20))
;=> (0 5 10 15)
Though certainly more succinct than the extended anonymous function form and the
earlier example using a separate divisible function with filter, there’s a fine line to
balance between reuse8 and clarity. Thankfully, in any case the performance differ-
ences among the three choices are nominal.
SHARING CLOSURE CONTEXT
So far, the closures we’ve shown have stood alone, but it’s sometimes useful to have
multiple closures closing over the same values. This may take the form of an ad hoc
set of closures in a complex lexical environment, such as event callbacks or timer han-
dlers in a nested GUI builder. Or it may be a tidy, specifically designed bundle of val-
ues and related functions—something that can be thought of as an object.
7
Please don’t construe from this wording that filter always iterates through the whole input sequence. Like
most of the seq library, it’s lazy and only consumes as much of the input sequence as needed to produce the
values demanded of it.
8
By hiding divisible as an anonymous function inside filter-divisible, we reduce the reusability of this
code with no real benefit. Anonymous functions are best reserved for when the lexical context being closed
over is more complex or the body of the function too narrow in use to warrant being its own named function.
Download from Wow! eBook <www.wowebook.com>
Closures
139
To demonstrate this, we’ll build a robot object that has functions for moving it
around a grid based on its current position and bearing. For this we need a list of
coordinate deltas for compass bearings, starting with north and going clockwise:
(def bearings [{:x 0, :y 1} ; north
{:x 1, :y 0} ; east
{:x 0, :y -1} ; south
{:x -1, :y 0}]) ; west
Note that this is on a grid where y increases as you go north and x increases as you go
east—mathematical coordinate style rather than spreadsheet cells.
With this in place, it’s easy to write a function forward that takes a coordinate and
a bearing, and returns a new coordinate having moved forward one step in the direc-
tion of the bearing:
(defn forward [x y bearing-num]
[(+ x (:x (bearings bearing-num)))
(+ y (:y (bearings bearing-num)))])
Starting with a bearing of 0 (north) at 5,5 and going one step brings the bot to 5,6:
(forward 5 5 0)
;=> [5 6]
We can also try starting at 5,5 and with bearing 1 (east) or bearing 2 (south) and see
the desired results:
(forward 5 5 1)
;=> [6 5]
(forward 5 5 2)
;=> [5 4]
But we have no closures yet, so we’ll build a bot object that keeps not just its coordi-
nates, but also its bearing. In the process, we’ll move this standalone forward function
into the bot object itself. By making this a closure, we’ll also open up possibilities for
polymorphism later. So here’s a bot that knows how to move itself forward:
(defn bot [x y bearing-num]
{:coords [x y]
:bearing ([:north :east :south :west] bearing-num)
:forward (fn [] (bot (+ x (:x (bearings bearing-num)))
(+ y (:y (bearings bearing-num)))
bearing-num))})
We can create an instance of this bot and query it for its coordinates or its bearing:
(:coords (bot 5 5 0))
;=> [5 5]
(:bearing (bot 5 5 0))
;=> :north
But now that we’ve moved the forward function inside, we no longer pass in parame-
ters, because it gets everything it needs to know from the state of the bot that it closes
Download from Wow! eBook <www.wowebook.com>
140
CHAPTER 7 Functional programming
over. Instead, we use :forward to fetch the closure from inside the bot object and
then use an extra set of parentheses to invoke it with no arguments:
(:coords ((:forward (bot 5 5 0))))
;=> [5 6]
So now we have a somewhat complicated beastie but still only a single closure in the
mix. To make things more interesting, we’ll add turn-left and turn-right9 func-
tions, and store them right there in the object with :forward:
(defn bot [x y bearing-num]
{:coords [x y]
:bearing ([:north :east :south :west] bearing-num)
:forward (fn [] (bot (+ x (:x (bearings bearing-num)))
(+ y (:y (bearings bearing-num)))
bearing-num))
:turn-right (fn [] (bot x y (mod (+ 1 bearing-num) 4)))
:turn-left (fn [] (bot x y (mod (- 1 bearing-num) 4)))})
(:bearing ((:forward ((:forward ((:turn-right (bot 5 5 0))))))))
;=> :east
(:coords ((:forward ((:forward ((:turn-right (bot 5 5 0))))))))
;=> [7 5]
We won’t talk about the verbosity of using the bot object yet, and instead focus on
the features leveraged in the definition of bot itself. We’re freely mixing values com-
puted when a bot is created (such as the :bearing) and functions that create values
when called later. The functions are in fact closures, and each has full access to the
lexical environment. The fact that there are multiple closures sharing the same envi-
ronment isn’t awkward or unnatural and flows easily from the properties of closures
already shown.
We’d like to demonstrate one final feature of this pattern for building objects:
polymorphism. For example, here’s the definition of a bot that supports all of the
same usage as earlier, but this one has its wires crossed or perhaps is designed to work
sensibly in Alice’s Wonderland. When told to go forward it instead reverses, and it
turns left instead of right and vice versa:
(defn mirror-bot [x y bearing-num]
{:coords [x y]
:bearing ([:north :east :south :west] bearing-num)
:forward (fn [] (mirror-bot (- x (:x (bearings bearing-num)))
(- y (:y (bearings bearing-num)))
bearing-num))
:turn-right (fn [] (mirror-bot x y (mod (- 1 bearing-num) 4)))
:turn-left (fn [] (mirror-bot x y (mod (+ 1 bearing-num) 4)))})
9
The :turn-right function uses (+ 1 foo), even though in general (inc foo) would be more idiomatic.
Here it helps highlight to anyone reading the symmetry between turn-right and turn-left. In this case,
using + is more readable than using inc and so is preferred.
Download from Wow! eBook <www.wowebook.com>
Thinking recursively
141
By bundling the functions that operate on data inside the same structure as the data
itself, simple polymorphism is possible. Because each function is a closure, no object
state needs to be explicitly passed; instead, each function uses any locals required to
do its job.
It’s likely you cringed at the number of parentheses required to call these particu-
lar object closures, and rightfully so. We encourage you to extrapolate from the clo-
sure examples when dealing with your own applications, and see how they can solve a
variety of tricky and unusual problems. Although this kind of structure is simple and
powerful10 and may be warranted in some situations, Clojure provides other ways of
associating functions with data objects that are more flexible. In fact, the desire to
avoid a widespread need for this type of ad hoc implementation has motivated Clo-
jure’s reify macro, which we’ll cover in section 9.3.
COMPILE-TIME VERSUS RUN-TIME
When looking at code that includes a closure, it’s not immediately obvious how the
work is distributed between compile-time and run-time. In particular, when you see a
lot of code or processor-intensive work being done in a closure, you might wonder
about the cost of calling the function that creates the closure:
(defn do-thing-builder [x y z]
(fn do-thing [a b]
...
(massive-calculation x y z)
...))
But you don’t need to worry. When this whole expression is compiled, bytecode for
the bodies of do-thing and do-thing-builder are generated and stored in memory.11
In current versions of Clojure, each function definition gets its own class. But when
do-thing-builder is called, it doesn’t matter how large or slow the body of do-thing
is—all that’s done at run-time is the creation of an instance of do-thing’s class. This is
lightweight and fast. Not until the closure returned by do-thing-builder is called does
the complexity or speed of the body of that inner function matter at all.
In this section, you learned that closures are functions that close over lexical locals,
how to create them from inside other functions, how to pass them around and call
them, and even how to build lightweight objects using them. Next, we’ll take a look at
how functions and closures behave when they call themselves, a pattern lovingly
known as recursion.
7.3
Thinking recursively
You’re likely already familiar with the basics of recursion, and as a result can take heart
that we won’t force you to read a beginner’s tutorial again. But because recursive
10 ...a fact any sufficiently experienced JavaScript programmer would be able to confirm.
11 If the code is being compiled ahead of time by the compile function, the generated bytecode is also written
to disk in .class files.
Download from Wow! eBook <www.wowebook.com>
142
CHAPTER 7 Functional programming
solutions are prevalent in Clojure code, it’s important that we cover it well enough that
you can fully understand Clojure’s recursive offerings.
Recursion is often viewed as a low-level operation reserved for times when solu-
tions involving higher-order functions either fail or lead to obfuscation. Granted, it’s
fun to solve problems recursively because even for those of us who’ve attained some
level of acumen with functional programming, finding a recursive solution still injects
a bit of magic into our day. Recursion is a perfect building block for creating higher-
level looping constructs and functions, which we’ll show in this section.
7.3.1
Mundane recursion
A classically recursive algorithm is that of calculating some base number raised to an
exponent, or the pow function. A straightforward12 way to solve this problem recur-
sively is to multiply the base by each successively smaller value of the exponent, as
implemented in the following listing.
Listing 7.4 A version of pow using mundane recursion
(defn pow [base exp]
(if (zero? exp)
1
(* base (pow base (dec exp)))))
(pow 2 10)
;=> 1024
(pow 1.01 925)
;=> 9937.353723241924
We say that the recursive call is mundane 13 because it’s named explicitly rather than
through mutual recursion or implicitly with the recur special form. Why is this a prob-
lem? The answer lies in what happens when we try to call pow with a large value:
(pow 2 10000)
; java.lang.StackOverflowError
The implementation of pow is doomed to throw java.lang.StackOverflowError
because the recursive call is trapped by the multiplication operation. The ideal solu-
tion would be a tail-recursive version that uses the explicit recur form, thus avoiding
stack consumption and the resulting exception. One way to remove the mundane
recursive call is to perform the multiplication at a different point, thus freeing the
recursive call to occur in the tail position, as shown in the next listing.
Listing 7.5 A version of pow using tail recursion, accumulator, and helper function
(defn pow [base exp]
(letfn [(kapow [base exp acc]
12 Yes, we’re aware of Math/pow.
13 Typically mundane recursion is referred to as linear, or the case where the space requirements needed to per-
form the recursion is proportional to the magnitude of the input.
Download from Wow! eBook <www.wowebook.com>
Thinking recursively
143
(if (zero? exp)
acc
(recur base (dec exp) (* base acc))))]
(kapow base exp 1)))
(pow 2 10000)
;=> ... A very big number
This new version of pow uses two common techniques for converting mundane recur-
sion to tail recursion. First, it uses a helper function kapow that does the majority of
the work. Second, kapow itself uses an accumulator acc that holds the result of the
multiplication. The exponent exp is no longer used as a multiplicative value but
instead functions as a decrementing counter, eliminating a stack explosion.
REGULAR RECURSION IS FUN AGAIN WITH LAZY-SEQ
As mentioned in section 6.3, the lazy-seq recipe rule of thumb #1 states that you
should wrap your outer layer function bodies with the lazy-seq macro when generat-
ing lazy seqs. The implementation of lz-rec-step used mundane recursion but man-
aged to avoid stack overflow exceptions thanks to the use of lazy-seq. For functions
generating sequences, the use of lazy-seq might be a better choice than tail recur-
sion, because often the regular (mundane) recursive definition is the most natural
and understandable.
7.3.2
Tail calls and recur
In a language such as Clojure, where function locals are immutable, the benefit of tail
recursion is especially important for implementing algorithms that require the con-
sumption of a value or the accumulation of a result. Before we get deeper into imple-
menting tail recursion, we’ll take a moment to appreciate the historical
underpinnings of tail-call recursion and expound on its further role within Clojure.
GENERALIZED TAIL-CALL OPTIMIZATION
In the Lambda Papers, Guy L. Steele and Gerald Sussman describe their experiences
with the research and implementation of the early versions of the Scheme program-
ming language. The first versions of the interpreter served as a model for Carl
Hewitt’s Actor model (Hewitt 1973) of concurrent computation, implementing both
actors and functions. One day, while eating Ho-Hos,14 Steele and Sussman noticed
that the implementation of control flow within Scheme, implemented using actors,
always ended with one actor calling another in its tail position with the return to the
callee being deferred. Armed with their intimate knowledge of the Scheme compiler,
Steele and Sussman were able to infer that because the underlying architecture deal-
ing with actors and functions was the same, retaining both was redundant. Therefore,
actors were removed from the language and functions remained as the more general
construct. Thus, generalized tail-call optimization was thrust (Steele 1977) into the
world of computer science.
14 This isn’t true, but wouldn’t it be great if it were?
Download from Wow! eBook <www.wowebook.com>
144
CHAPTER 7 Functional programming
Generalized tail-call optimization as found in Scheme (Abelson 1996) can be
viewed as analogous to object delegation. Hewitt’s original actor model was rooted
heavily in message delegation of arbitrary depth, with data manipulation occurring at
any and all levels along the chain. This is similar to an adapter, except that there’s an
implicit resource management element involved. In Scheme, any tail call15 from a
function A to a function B results in the deallocation of all of A local resources and the
full delegation of execution to B. As a result of this generalized tail-call optimization,
the return to the original caller of A is directly from B instead of back down the call
chain through A again, as shown in figure 7.1.
Unfortunately for Clojure, neither the Java Virtual Machine nor its bytecode pro-
vide generalized tail-call optimization facilities. Clojure does provide a tail call special
form recur, but it only optimizes the case of a tail-recursive self-call and not the gener-
alized tail call. In the general case, there’s currently no way to reliably optimize
(Clinger 1998) tail calls.
TAIL RECURSION
The following function calculates the greatest common denominator of two numbers:
(defn gcd [x y]
(cond
(> x y) (gcd (- x y) y)
(< x y) (gcd x (- y x))
:else x))
no TCO
general TCO
caller
caller
(A
( )
A
(A)
(let [a 9]
(let [a 9]
(B))
(B))
dealloc A's
resources
(B)
(B)
; do stuff
; do stuff
; done
; done
de
d a
e ll
l o
l c
o
c B'
B s
'
dealloc B's
re
r s
e ou
o r
u c
r e
c s
resources
(A)
caller
; done
de
d al
a l
l o
l c
o A
'
A s
'
re
r so
s u
o r
u c
r es
e
caller
Figure 7.1 Generalized tail-call optimization: if you know that A calls B in the tail
position, then you also know that A’s resources are no longer needed, allowing
Scheme to deallocate them and defer to B for the return call instead.
15 Bear in mind that in this scenario, A and B can be different functions or the same function.
Download from Wow! eBook <www.wowebook.com>
Thinking recursively
145
The implementation of gcd is straightforward, but you’ll notice that we used mun-
dane recursion instead of tail recursion via recur. In a language such as Scheme con-
taining generalized tail-call optimization, the recursive calls will be optimized
automatically. On the other hand, because of the JVM’s lack of tail-call optimization,
the recur would be needed in order to avoid stack overflow errors.
Using the information in table 7.1, you can replace the mundane recursive calls
with the recur form, causing gcd to be optimized by Clojure’s compiler.
Table 7.1 Tail positions and recur targets
Form(s)
Tail position
recur target?
fn, defn
(fn [args] expressions tail)
Yes
loop
(loop [bindings] expressions tail)
Yes
let, letfn, binding
(let [bindings] expressions tail)
No
do
(do expressions tail)
No
if, if-not
(if test then tailelse tail)
No
when, when-not
(when test expressions tail)
No
cond
(cond test test tail ... :else else tail)
No
or, and
(or test test ... tail)
No
case
(case const const tail ... default tail)
No
WHY RECUR?
If you think that you understand why Clojure provides an explicit tail-call optimization
form rather than an implicit one, then go ahead and skip to the next section.
There’s no technical reason why Clojure couldn’t automatically detect and opti-
mize recursive tail calls—Scala does this—but there are valid reasons why Clojure
doesn’t.
First, because there’s no generalized TCO in the JVM, Clojure can only provide a
subset of tail-call optimizations: the recursive case and the mutually recursive case (see
the next section). By making recur an explicit optimization, Clojure doesn’t give the
pretense of providing full TCO.
Second, having recur as an explicit form allows the Clojure compiler to detect
errors caused by an expected tail call being pushed out of the tail position. If we
change gcd to always return an integer, then an exception is thrown because the
recur call is pushed out of the tail position:
(defn gcd [x y]
(int
(cond
(> x y) (recur (- x y) y)
(< x y) (recur x (- y x))
:else x)))
; java.lang.UnsupportedOperationException: Can only recur from tail position
Download from Wow! eBook <www.wowebook.com>
146
CHAPTER 7 Functional programming
With automatic recursive tail-call optimization, the addition of an outer int call
wouldn’t necessarily trigger (Wampler 2009)16 an error condition. But Clojure
enforces that a call to recur be in the tail position. This benefit will likely cause recur
to live on, even should the JVM acquire TCO.
The final benefit of recur is that it allows the forms fn and loop to act as anony-
mous recursion points.
Why recur indeed.
7.3.3
Don’t forget your trampoline
We touched briefly on the fact that Clojure can also optimize a mutually recursive
function relationship, but like the tail-recursive case, it’s done explicitly. Mutually
recursive functions are nice for implementing finite state machines (FSA), and in this
section we’ll show an example of a simple state machine modeling the operation of an
elevator (Mozgovoy 2009) for a two-story building. There are only four states that the
elevator FSA allows: on the first floor with the doors open or closed and on the second
floor with the door open or closed. The elevator can also take four distinct com-
mands: open doors, close doors, go up, and go down. Each command is only valid in a
certain context; for example, the close command is only valid when the elevator door
is open. Likewise, the elevator can only go up when on the first floor and only down
when on the second floor, and the door must be shut in both instances.
We can directly translate these states and transitions into a set of mutually recursive
functions by associating the states as a set of functions ff-open, ff-closed, sf-
closed, and sf-open, and the transitions :open, :close, :up, and :down, as conditions
for calling the next function. We’d like to create a function elevator that starts in the
ff-open state, takes a sequence of commands, and returns true or false if they corre-
spond to a legal schedule according to the FSA. For example, the sequence [:close
:open :done] would be legal, if not pointless, whereas [:open :open :done] wouldn’t
be legal, because an open door can’t be reopened. The function elevator could be
implemented as shown next.
Listing 7.6 Using mutually recursive functions to implement a finite state machine
(defn elevator [commands]
(letfn
Local functions
[(ff-open [[cmd & r]]
1st floor open
"When the elevator is open on the 1st floor
it can either close or be done."
#(case cmd
:close (ff-closed r)
:done true
false))
(ff-closed [[cmd & r]]
1st floor closed
"When the elevator is closed on the 1st floor
it can either open or go up."
16 The Scala 2.8 compiler recognizes a @tailrec annotation and triggers an error whenever a marked function
or method can’t be optimized.
Download from Wow! eBook <www.wowebook.com>
Thinking recursively
147
#(case cmd
:open (ff-open r)
:up (sf-closed r)
false))
(sf-closed [[cmd & r]]
2nd floor closed
"When the elevator is closed on the 2nd floor
it can either go down or open."
#(case cmd
:down (ff-closed r)
:open (sf-open r)
false))
(sf-open [[cmd & r]]
2nd floor open
"When the elevator is open on the 2nd floor
it can either close or be done"
#(case cmd
:close (sf-closed r)
:done true
false))]
(trampoline ff-open commands)))
Trampoline call
Using letfn in this way allows you to create local functions that reference each other,
whereas (let [ff-open #(...)] ...) wouldn’t, because it executes its bindings seri-
ally. Each state function contains a case macro that dispatches to the next state based
on a contextually valid command. For example, the sf-open state will transition to the
sf-closed state given a :close command, will return true on a :done command (cor-
responding to a legal schedule), or will otherwise return false. Each state is similar in
that the default case command is to return false indicating an illegal schedule. One
other point of note is that each state function returns a function returning a value
rather than directly returning the value. This is done so that the trampoline function
can manage the stack on the mutually recursive calls, thus avoiding cases where a long
schedule would blow the stack. Here’s the operation of elevator given a few example
schedules:
(elevator [:close :open :close :up :open :open :done])
;=> false
(elevator [:close :up :open :close :down :open :done])
;=> true
;; run at your own risk!
(elevator (cycle [:close :open]))
; ... runs forever
Like the recur special form, the trampoline for mutual recursion has a definitive syntactic
and semantic cost on the structure of your code. But whereas the call to recur could be
replaced by mundane recursion without too much effect, save for at the edges, the rules
for mutual recursion aren’t general. Having said that, the actual rules are simple:
1
Make all of the functions participating in the mutual recursion return a func-
tion instead of their normal result. Normally this is as simple as tacking a # onto
the front of the outer level of the function body.
2
Invoke the first function in the mutual chain via the trampoline function.
Download from Wow! eBook <www.wowebook.com>
148
CHAPTER 7 Functional programming
(elevator)
true
:done
:close
:up
:open
e
n
:close
ff-open
ff-closed
s S
f-closed
sf-open
s S
f-closed
... ff-open
2
2
Figure 7.2 Elevator trampoline: the trampoline function explicitly bounces between
mutually recursive calls.
The final example won’t cause a stack overflow because the trampoline function han-
dles the process of the self calls through the placement of the functions within a list
where each function is “bounced” back and forth explicitly, as seen in figure 7.2.
The typical use case for mutually recursive functions are state machines, of which
the elevator FSA is only a simple case.
7.3.4
Continuation-passing style
Before wrapping up this chapter, we’re going to take time to talk about a style of pro-
gramming not necessarily prevalent in Clojure, but moreso in the functional tradi-
tion: continuation-passing style. Continuation-passing style (CPS) is a hybrid between
recursion and mutual recursion, but with its own set of idioms. We won’t give you a
deep survey of CPS, but this subsection should provide a reasonable overview for
deeper exploration, should you be so inclined.
The nutshell version of CPS is that it’s a way of generalizing a computation (Fried-
man 2001) by viewing it in terms of up to three functions:
An accept function that decides when a computation should terminate
A return continuation that’s used to wrap the return values
A continuation function used to provide the next step in the computation
There’s a reason why many sources on CPS will use the factorial function as a base
example: because it’s exceptionally illustrative, as we show next.
Listing 7.7 Factorial function using continuation-passing style
(defn fac-cps [n k]
(letfn [(cont [v] (k (* v n)))]
Next continuation
(if (zero? n)
Accept function
(k 1)
Return continuation
(recur (dec n) cont))))
(defn fac [n]
(fac-cps n identity))
(fac 10)
;=> 3628800
Though this approach is definitely different than the normal functional structure, it’s
not exactly interesting in and of itself. The power of CPS is that you can extract more
generic function builders using CPS. One such builder, shown in the following listing,
Download from Wow! eBook <www.wowebook.com>
Putting it all together: A* pathfinding
149
can be used to make a range of functions that happen to fall into the same mold of a
mathematical folding function.
Listing 7.8 Continuation-passing style function generator
(defn mk-cps [accept? end-value kend kont]
(fn [n]
((fn [n k]
(let [cont (fn [v] (k (kont v n)))]
Next continuation
(if (accept? n)
Accept continuation
(k end-value)
Return continuation
(recur (dec n) cont))))
n kend)))
(def fac (mk-cps zero? 1 identity #(* %1 %2)))
Factorial fn
(fac 10)
;=> 3628800
(def tri (mk-cps zero? 1 dec #(+ %1 %2)))
Triangular fn
(tri 10)
;=> 55
Though this is potentially a powerful technique, there are a number of reasons pre-
venting its widespread adoption in Clojure:
Without generalized tail-call optimization, the number of continuation calls is
bounded by the size of the stack. If your own applications can guarantee a
bounded execution path for the CPS calls, then this may not be a problem in
practice.
In the case of exception handling, CPS can cause the point of failure to bubble
out, especially on deferred computations such as in using delay, future, or
promise.17 In the abstract this may not seem to be a problem, but if your contin-
uation function is supposed to throw the error but an outer layer function is
doing so instead, then bugs might be difficult to track down.
In a language such as Haskell that has ubiquitous lazy evaluation and pure func-
tions, it’s often not necessary to impose a strict order of execution. One way to
impose a strict order of execution is to design your programs along the
continuation-passing style. Though Clojure isn’t entirely lazy, the matter of out-
of-order execution isn’t a factor against CPS. But CPS isn’t conducive to paral-
lelization, which is antithetical to Clojure’s very nature.
7.4
Putting it all together: A* pathfinding
A* is a best-first pathfinding algorithm that maintains a set of candidate paths through
a “world” with the purpose of finding the least difficult (Bratko 2000) path to some
goal. The difficulty (or cost) of a path is garnered by the A* algorithm through the
use of a function, typically named f, that builds an estimate of the total cost from a
17 Clojure’s future and promise will be discussed in detail in chapter 11.
Download from Wow! eBook <www.wowebook.com>
150
CHAPTER 7 Functional programming
start point to the goal. The application of this cost-estimate function f is used to sort
the candidate paths (Hart 1968) in the order most likely to prove least costly.
THE WORLD
To represent the world, we’ll again use a simple 2D matrix representation:
(def world [[ 1 1 1 1 1]
[999 999 999 999 1]
[ 1 1 1 1 1]
[ 1 999 999 999 999]
[ 1 1 1 1 1]])
The world structure is made from the values 1 and 999 respectively, corresponding to
flat ground and cyclopean mountains. What would you assume is the optimal path
from the upper-left corner [0 0] to the lower-right [4 4]? Clearly the optimal (and
only) option is the Z-shaped path around the walls. Implementing an A* algorithm
should fit the bill, but first, we’ll talk a little bit about how to do so.
NEIGHBORS
For any given spot in the world, we need a way to calculate possible next steps. We can
do this brute force for small worlds, but we’d like a more general function. It turns out
if we restrict the possible moves to north, south, east, and west, then any given move is
+/-1 along the x or y axis. Taking advantage of this fact, we can use the neighbors
function from listing 5.1 as shown here:
(neighbors 5 [0 0])
;=> ([1 0] [0 1])
From the upper-left point, the only next steps are y=0, x=1 or y=1, x=0. So now that we
have that, think about how we might estimate the path cost from any given point. A
simple cost estimate turns out to be described as, “from the current point, calculate
the expected cost by assuming we can travel to the right edge, then down to the lower-
right.” An implementation of the h function estimate-cost that estimates the
remaining path cost is shown next.
Listing 7.9 A straight-line h function to estimate remaining path cost
(defn estimate-cost [step-cost-est size y x]
(* step-cost-est
(- (+ size size) y x 2)))
(estimate-cost 900 5 0 0)
;=> 7200
(estimate-cost 900 5 4 4)
;=> 0
From the y-x point [0 0] the cost of travelling 5 right and 5 down given an estimated
single-step cost step-cost-est is 9000. This is a pretty straightforward estimate based
on a straight-line path. Likewise, starting at the goal state [4 4] would cost nothing.
Still needed is the g function used to calculate the cost of the path so far, named
path-cost, which is provided in the following listing.
Download from Wow! eBook <www.wowebook.com>
Putting it all together: A* pathfinding
151
Listing 7.10 A g function used to calculate the cost of the path traversed so far
(defn path-cost [node-cost cheapest-nbr]
Add cheapest
(+ node-cost
neighbor cost,
(:cost cheapest-nbr 0)))
else 0
(path-cost 900 {:cost 1})
;=> 901
Now that we’ve created an estimated cost function and a current cost function, we can
implement a simple total-cost function for f.
Listing 7.11 f function to calculate the estimated cost of the path (+ (g ...) (h ...)) (defn total-cost [newcost step-cost-est size y x]
(+ newcost
(estimate-cost step-cost-est size y x)))
(total-cost 0 900 5 0 0)
;=> 7200
(total-cost 1000 900 5 3 4)
;=> 1900
The second example shows that if we’re one step away with a current cost of 1000,
then the total estimated cost will be 1900, which is expected. So now we have all of the
heuristic pieces in place. You may think that we’ve simplified the heuristic needs of
A*, but in fact this is all that there is to it. The actual implementation is complex,
which we’ll tackle next.
7.4.1
The A* implementation
Before we show the implementation of A*, we need one more auxiliary function min-
by, used to retrieve from a collection the minimum value dictated by some function.
The implementation of min-by would naturally be a straightforward higher-order
function, as shown:
(defn min-by [f coll]
(when (seq coll)
(reduce (fn [min this]
(if (> (f min) (f this)) this min))
coll)))
(min-by :cost [{:cost 100} {:cost 36} {:cost 9}])
;=> {:cost 9}
This function will come in handy when we want to grab the cheapest path deter-
mined by the cost heuristic. We’ve delayed enough! We’ll finally implement the A*
algorithm so that we navigate around the world. The following listing shows a tail-
recursive solution.
Download from Wow! eBook <www.wowebook.com>
152
CHAPTER 7 Functional programming
Listing 7.12 The main A* algorithm
(defn astar [start-yx step-est cell-costs]
(let [size (count cell-costs)]
(loop [steps 0
routes (vec (replicate size (vec (replicate size nil))))
work-todo (sorted-set [0 start-yx])]
Grab
(if (empty? work-todo)
Check done
first
[(peek (peek routes)) :steps steps]
route
(let [[_ yx :as work-item] (first work-todo)
Get next work item
rest-work-todo (disj work-todo work-item)
nbr-yxs (neighbors size yx)
Clear from todo
cheapest-nbr (min-by :cost
Calc least-cost
(keep #(get-in routes %)
nbr-yxs))
Calc path
newcost (path-cost (get-in cell-costs yx)
so far
cheapest-nbr)
oldcost (:cost (get-in routes yx))]
Check if new
(if (and oldcost (>= newcost oldcost))
is worse
(recur (inc steps) routes rest-work-todo)
(recur (inc steps)
Place new path
(assoc-in routes yx
in routes
{:cost newcost
:yxs (conj (:yxs cheapest-nbr [])
yx)})
(into rest-work-todo
Add estimated path
(map
to todo and recur
(fn [w]
(let [[y x] w]
[(total-cost newcost step-est size y x) w]))
nbr-yxs)))))))))
The main thrust of the astar function occurs at the check that (>= newcost oldcost).
Once we’ve calculated the newcost (the cost so far for the cheapest neighbor) and a
cost-so-far oldcost, we perform one of two actions. The first action occurs when the
newcost is greater than or equal to the oldcost and is to throw away this new path,
because it’s clearly a worse alternative. The other action is the core functionality corre-
sponding to the constant sorting of the work-todo, based on the cost of the path as
determined by the heuristic function total-cost. The soul of A* is based on the fact
that the potential paths stored in work-todo are always sorted and distinct (through
the use of a sorted set), based on the estimated path cost function. Each recursive
loop through the astar function maintains the sorted routes based on the current
cost knowledge of the path, added to the estimated total cost.
The results given by the astar function for the Z-shaped world are shown in the
next listing.
Download from Wow! eBook <www.wowebook.com>
Putting it all together: A* pathfinding
153
Listing 7.13 Running the A* algorithm on the Z World
(astar [0 0]
900
world)
;=> [{:cost 17,
:yxs [[0 0] [0 1] [0 2] [0 3] [0 4] [1 4] [2 4]
[2 3] [2 2] [2 1] [2 0] [3 0] [4 0] [4 1]
[4 2] [4 3] [4 4]]}
:steps 94]
By following the y-x indices, you’ll notice that the
astar function traverses the Z World along the path
where cost is 1, as seen in figure 7.3.
We can also build another world, as shown next,
called Shrubbery World that contains a single weakling
Figure 7.3 A graphical
shrubbery at position [0 3], represented by the num-
representation of Z World clearly
ber 2, and see how astar navigates it.
shows the optimal/only path.
Listing 7.14 The Shrubbery World
(astar [0 0]
900
[[ 1 1 1 2 1]
The shrubbery is 2
[ 1 1 1 999 1]
[ 1 1 1 999 1]
[ 1 1 1 999 1]
[ 1 1 1 1 1]])
The clear path
;=> [{:cost 9,
:yxs [[0 0] [0 1] [0 2] [1 2] [2 2] [3 2]
[4 2] [4 3] [4 4]]}
:steps 134]
When tracing the best path, you will see that the astar function prefers the nonshrub-
bery path. But what would happen if we placed a man-eating bunny along the previ-
ously safe path, represented by an ominously large number, as shown next?
Listing 7.15 The bunny world
(astar [0 0]
900
The shrubbery
[[ 1 1 1 2 1]
looks inviting
[ 1 1 1 999 1]
[ 1 1 1 999 1]
[ 1 1 1 999 1]
The bunny
[ 1 1 1 666 1]])
lies in wait
;=> [{:cost 10,
:yxs [[0 0] [0 1] [0 2] [0 3] [0 4] [1 4]
[2 4] [3 4] [4 4]]}
:steps 132]
Download from Wow! eBook <www.wowebook.com>
154
CHAPTER 7 Functional programming
As expected, the astar function picks the shrubbery path (2) path instead of the evil
bunny path to reach the final destination.
7.4.2
Notes about the A* implementation
The A* algorithm was implemented as idiomatic Clojure source code. Each of the
data structures, from the sorted set to the tail-recursive astar function, to the higher-
order function min-by, was functional in nature and therefore extensible as a result.
We encourage you to explore the vast array of possible worlds traversable by our A*
implementation and see what happens should you change the heuristic (Dijkstra
1959) functions along the way. Clojure encourages experimentation, and by partition-
ing the solution this way, we’ve enabled you to explore different heuristics.
7.5
Summary
We’ve covered a lot about Clojure’s flavor of functional programming in this chapter,
and you may have noticed that it looks like many others. Clojure favors an approach
where immutable data is transformed through the application of functions. Addition-
ally, Clojure prefers that functions be free of side-effects and referentially transparent
(pure) in order to reduce the complexities inherent in widespread data mutation.
Lexical closures provide a simple yet powerful mechanism for defining functions that
carry around with them the value context in which they were created. This allows cer-
tain information to exist beyond their lexical context, much like a poor-man’s object.
Finally, Clojure is built with this in mind, in that its primary form of iteration is
through tail recursion as a natural result of its focus on immutability.
In the next chapter, we’ll explore the feature most identified with Lisp: macros.
Download from Wow! eBook <www.wowebook.com>
Part 4
Large-scale design
Clojure is a practical language, not an academic one; and in the real
world, programs grow large, change over time, and are confronted with shifting
requirements. In this part, we’ll show how Clojure’s Lisp heritage of “code is
data” can help address these problems. We’ll demonstrate the use of macros,
how to create a fluent builder, the benefits of a language that embraces the Java
platform, and how Clojure addresses the mutability of the real world.
Download from Wow! eBook <www.wowebook.com>
Download from Wow! eBook <www.wowebook.com>
Macros
If you give someone Fortran, he has
Fortran. If you give someone Lisp, he
has any language he pleases.
—Guy Steele
This chapter covers
Data is code is data
Defining control structures
Macros combining forms
Using macros to control symbolic resolution time
Using macros to manage resources
Putting it all together: macros returning functions
Macros are where the rubber of “code is data” meets the road of making programs
simpler and cleaner. To fully understand macros, you need to understand the dif-
ferent times of Clojure, of which macros perform the bulk of their work at compile
time. We’ll start by looking at what it means for code to be data and data to be used
as code. This is the background you’ll need to understand that control structures in
Clojure are built out of macros, and how you can build your own. The mechanics of
macros are relatively simple, and before you’re halfway through this chapter you’ll
157
Download from Wow! eBook <www.wowebook.com>
158
CHAPTER 8 Macros
have learned all you technically need to write your own. Where macros get compli-
cated is when you try to bring theoretical knowledge of them into the real world, so to
help you combat that we’ll lead you on a tour of practical applications of macros.
What kinds of problems do macros solve? To start answering that question, con-
sider Clojure’s -> and ->> macros that return the result of a number of threaded
forms. To understand both versions of the arrow macros, we find it useful to think of
them as an arrow indicating the flow of data from one function to another—the form
(-> 25 Math/sqrt int list) can be read as
(-> 25
1
Take the value 25.
(Math/sqrt)
2
Feed it into the method Math/sqrt.
(i n
i t
n )
t
3
Feed that result into the function int.
l
( i
l s
i t
)
t )
4
Feed that result into the function list.
Graphically, this can be viewed as shown in
Figure 8.1 Arrow macro: each expression
figure 8.1.
is inserted into the following one at compile
time, allowing you to write the whole
It expands into the following expression:
expression inside-out when that feels
more natural.
(list (int (Math/sqrt 25)))
When viewed this way, the -> macro can be said to thread a sequence of forms into
each in turn. This threading can be done within any form and is always stitched in as
the first argument to the outermost expression. On the other hand, the ->> macro
will thread the form as the last argument. Observe how the placement of commas1
works as visual markers for the stitch point:
(-> (/ 144 12) (/ ,,, 2 3) str keyword list)
;=> (:2)
(-> (/ 144 12) (* ,,, 4 (/ 2 3)) str keyword (list ,,, :33))
;=> (:32 :33)
(->> a (+ 5 ,,,) (let [a 5] ,,,))
;=> 10
Using the arrows macro is useful when many sequential operations need to be applied
to a single object. So this is one potential use case for macros: taking one form of an
expression and transforming it into another form. In this chapter, we’ll also look at
using macros to combine forms, change forms, control evaluation and resolution of
arguments, manage resources, and build functions. But first, what does it mean that
Clojure code is data, and why should you care?
8.1
Data is code is data
You’re already familiar with textual representations of data in your programs, at least
with strings, lists, vectors, maps, and so on. Clojure, like other Lisps, takes this one
step further by having programs be made entirely out of data. Function definitions in
Clojure programs are also represented using an aggregation of the various data
1 Because commas are considered whitespace. The use here is instructive and not meant as idiomatic.
Download from Wow! eBook <www.wowebook.com>
Data is code is data
159
structures mentioned in the previous chapters. Likewise, the expressions representing
the execution of functions and the use of control structures are also data structures!
These data representations of functions and their executions represent a concept dif-
ferent from the way other programming languages operate. Typically, there’s a sharp
distinction between data structures and functions of the language. In fact, most pro-
gramming languages don’t even remotely describe the form of functions in their tex-
tual representations. With Clojure, there’s no distinction between the textual form
and the actual form of a program. When a program is the data that composes the pro-
gram, then you can write programs to write programs. This may seem like nonsense
now, but as you’ll see throughout this chapter, it’s powerful.
To start with, look at the built-in Clojure function eval, whose purpose is to take a
data structure representing a Clojure expression, evaluate it, and return the result.
This behavior can be seen in the following examples:
(eval 42)
;=> 42
(eval '(list 1 2))
;=> (1 2)
(eval (list 1 2))
; java.lang.ClassCastException: java.lang.Integer cannot be cast to clojure.
lang.IFn
Why did we get an exception for the last example? The answer to that lies in the previ-
ous example. The quote in '(list 1 2) causes eval to view it as (list 1 2), which is
the function call to create the resulting list. Likewise, for the final example eval
received a list of (1 2) and attempted to use 1 as a function, thus failing. Not very
exciting, is it? The excitement inherent in eval stems from something that we men-
tioned2 earlier—if you provide eval a list in the form expected of a function call, then
something else should happen. This something else would be the evaluation of a function
call and not of the data structure itself. Look at what happens when we try evaluating
something more complicated:
(eval (list (symbol "+") 1 2))
;=> 3
In words, the steps involved were as follows:
1
The function symbol received a string + and returned a symbol data type of +.
2
The function list received three arguments: a symbol +, the integer 1, and the
integer 2, and returned a list of these elements.
3
The eval function received a list data type of (+ 1 2), recognized it as the func-
tion call form, and executed the + function with the arguments 1 and 2, return-
ing the integer 3.
2 All the way back in section 2.5.
Download from Wow! eBook <www.wowebook.com>
160
CHAPTER 8 Macros
8.1.1
Syntax-quote, unquote, and splicing
In section 1.5.6, we mentioned quoting and its effects on evaluation, and in this chapter
we’ll expand on that theme fully as it relates to Clojure’s macro facility. But the func-
tionality of the quoting forms is orthogonal to macros, and they can be used indepen-
dently. As we show3 in listing 8.1, using quoting and unquoting in a function allows us
to create an evaluation function, contextual-eval, that takes an explicit context map.
Listing 8.1 An implementation of eval taking a local context
(defn contextual-eval [ctx expr]
(eval
Build let bindings
`(let [~@(mapcat (fn [[k v]] [k `'~v]) ctx)]
at compile-time
~expr)))
(contextual-eval {'a 1, 'b 2} '(+ a b))
;=> 3
(contextual-eval {'a 1, 'b 2} '(let [b 1000] (+ a b)))
;=> 1001
Handling nested syntax-quotes
Dealing with nested syntax-quotes can at times be complicated. But you can visualize
the way in which unquoting affects the nested structures as result of repeated eval-
uations (Steele 1990) relative to its nesting level:
(let [x 9, y '(- x)]
(println `y)
(println ``y)
(println ``~y)
(println ``~~y)
(contextual-eval {'x 36} ``~~y))
; user/y
; (quote user/y)
; user/y
; (- x)
;=> -36
The nesting of the syntax-quotes in the first two println calls takes the value of y
further up the abstraction ladder. But by including a single unquote in the third
println, we again bring it back down. Finally, by unquoting a second time, we’ve cre-
ated a structure that can then be evaluated—and doing so yields the result -36. We
had to use contextual-eval in the tail because core eval doesn’t have access to
local bindings—only Var bindings. One final note is that had we attempted to unquote
one extra time, we’d have seen the exception java.lang.IllegalStateExcep-
tion: Var clojure.core/unquote is unbound. The reason for this error is that
unquote is the way to “jump” out of a syntax-quote, and to do so more than nesting
allows will cause an error. We won’t use this technique in this chapter, and in most
cases you won’t need to utilize it unless you’re planning to create macro-defining
macros—something we won’t do until section 13.1.
3 Thanks to George Jahad for the implementation on which contextual-eval is based.
Download from Wow! eBook <www.wowebook.com>
Defining control structures
161
Rarely will you see the use of syntax-quote outside the body of a macro, but there’s
nothing preventing it from being used this way—and doing so is powerful. But the
maximum power of quoting forms is fully realized when used with macros.
Working from a model where code is data, Clojure is able to manipulate structures
into different executable forms at both runtime and compile time. We’ve already
shown how this can be done at runtime using eval and contextual-eval, but this
doesn’t serve the purpose of compile-time manipulation. It probably doesn’t need say-
ing, but because this is a book about Clojure, we will: macros are the way to achieve
this effect.
8.1.2
Macro rules of thumb
Before we begin, we should list a few rules of thumb to observe when writing macros:
Don’t write a macro if a function will do. Reserve macros to provide syntactic
abstractions or create binding forms.
Write an example usage.
Expand your example usage by hand.
Use macroexpand, macroexpand-1, and clojure.walk/macroexpand-all4 liber-
ally to understand how your implementation works.
Experiment at the REPL.
Break complicated macros into smaller functions whenever possible.
Throughout this chapter, you’ll see all of these rules to varying degrees. Obviously,
we’re trying to balance best practices, teaching, and page counts, so we may not always
adhere entirely. Even so, we’ll try to highlight those times when we do break from the
recommended heuristics. Having said that, we’ll talk first about the most ubiquitous
use of macros: creating custom control structures.
8.2
Defining control structures
Most control structures in Clojure are implemented via macros, so they provide a nice
starting point for learning how macros can be useful. Macros can be built with or with-
out using syntax-quote, so we’ll show examples of each.
In languages lacking macros, such as Haskell5 for example, the definition of control
structures relies on the use of higher-order functions such as we showed in section
7.1.2. Though this fact in no way limits the ability to create control structures in
Haskell, the approach that Lisps take to the problem is different. The most obvious
advantage of macros over higher-order functions is that the former manipulate
compile-time forms, transforming them into runtime forms. This allows your programs
4
The macroexpand-all function is a useful debugging aid, as we’ll demonstrate in this chapter. But it’s worth
knowing that unlike the other macroexpand functions, it doesn’t use exactly the same logic as the Clojure
compiler itself, and thus may in some unusual circumstances produced misleading results.
5
Although there’s a GHC extension named Template Haskell that provides a macro-like capability, this isn’t
the norm.
Download from Wow! eBook <www.wowebook.com>
162
CHAPTER 8 Macros
to be written in ways natural to your problem domain, while still maintaining runtime
efficiency. Clojure already provides a rich set of control structures, including but not
limited to doseq, while, if, if-let, and do, but in this section we’ll write a few others.
8.2.1
Defining control structures without syntax-quote
Because the arguments to defmacro aren’t evaluated before being passed to the
macro, they can be viewed as pure data structures, and manipulated and analyzed as
such. Because of this, amazing things can be done on the raw forms supplied to mac-
ros even in the absence of unquoting.
Imagine a macro named do-until that will execute all of its clauses evaluating as
true until it gets one that is falsey:
(do-until
(even? 2) (println "Even")
(odd? 3) (println "Odd")
(zero? 1) (println "You never see me")
:lollipop (println "Truthy thing"))
; Even
; Odd
;=> nil
A good example of this type of macro is Clojure’s core macro cond, which with some
minor modifications can be made to behave differently:
(defmacro do-until [& clauses]
(when clauses
(list `when (first clauses)
(if (next clauses)
(second clauses)
(throw (IllegalArgumentException.
"do-until requires an even number of forms")))
(cons 'do-until (nnext clauses)))))
The first expansion of do-until illustrates how this macro operates:
(macroexpand-1 '(do-until true (prn 1) false (prn 2)))
;=> (when true (prn 1) (do-until false (prn 2)))
do-until recursively expands into a series of when calls, which themselves expand into
a series of if expressions:
(require '[clojure.walk :as walk])
(walk/macroexpand-all '(do-until true (prn 1) false (prn 2)))
;=> (if true (do (prn 1) (if false (do (prn 2) nil))))
(do-until true (prn 1) false (prn 2))
; 1
;=> nil
Now you could write out the nested if structure manually and achieve the same
result, but the beauty of macros lies in the fact that they can do so on your behalf
while presenting a lightweight and intuitive form. In cases where do-until can be
used, it removes the need to write and maintain superfluous boilerplate code. This
Download from Wow! eBook <www.wowebook.com>
Defining control structures
163
idea can be extended to macros in general and their propensity to reduce unneeded
boilerplate for a large category of circumstances, as the programmer desires. One
thing to note about do-until is that it’s meant to be used only for side effects, because
it’s designed to always return nil. Macros starting with do tend to act the same.
8.2.2
Defining control structures using syntax-quote and unquoting
Not all control structures will be as simple as do-until. Instead, there will be times
when you’ll want to selectively evaluate macro arguments, structures, or substructures.
In this section, we’ll explore one such macro named unless, implemented using
unquote and unquote-splice.
Ruby provides a control structure named unless that reverses the sense (Olsen
2007) of a when statement, executing the body of a block when a given condition eval-
uates to false:
(unless (even? 3) "Now we see it...")
;=> "Now we see it..."
(unless (even? 2) "Now we don't.")
;=> nil
The maverick implementation6 of unless as demonstrated previously and as shown in
the following listing is straightforward.
Listing 8.2 A Clojure Implementation of unless
(defmacro unless [condition & body]
`(if (not ~condition)
Unquote condition
(do ~@body)))
Splice body
(defn from-end [s n]
Use our unless
(let [delta (dec (- (count s) n))]
(unless (neg? delta)
Return nil
(nth s delta))))
if negative
(from-end (range 1 101) 10)
;=> 90
The body of the unless implementation uses three features first shown in section
1.5.6: syntax-quote (written as a single back-quote), unquote (written as ~), and
unquote-splice (written as ~@). Syntax-quote allows the if form to act as a template for
the expression that any use of the macro becomes when expanded. The unquote and
splicing-unquote provide the “blanks” where the values for the parameters condition
and body will be inserted.
Because unless relies on the result of a condition for its operation, it’s imperative
that it evaluate the condition part using unquote. If we didn’t use unquote in this
instance, then instead of evaluating a function (even? 3), it would instead attempt to
resolve a namespace Var named condition that may not exist —and if it does exist, it
6 The proper way to define unless is either (defmacro unless [& args] `(when-not ~@args)) or even
(clojure.contrib.def/defalias unless when-not)—or just use when-not from the start.
Download from Wow! eBook <www.wowebook.com>
164
CHAPTER 8 Macros
might be arbitrarily truthy at the time of the macro call. Some of the unintended con-
sequences of this mistake are shown in the next listing.
Listing 8.3 Name capture in unless
(macroexpand `(if (not condition) "got it"))
Missing ~
;=> (if (clojure.core/not user/condition) "got it")
resolves to Var
(eval `(if (not condition) "got it"))
; java.lang.Exception: No such var: user/condition
(def condition false)
Undesired result
(eval `(if (not condition) "got it"))
when bound
;=> "got it"
Clearly this isn’t the desired behavior. Instead, by unquoting the condition local, we
ensure that the function call is used instead. It’s easy to forget to add an unquote to
the body of a macro, and depending on the condition of your runtime environment,
the problem may not be immediately obvious.
8.3
Macros combining forms
Macros are often used for combining a number of forms and actions into one consis-
tent view. This behavior could be seen in the previous section with the do-until
macro, but it’s more general. In this section, we’ll show how macros can be used to
combine a number of tasks in order to simplify an API. Clojure’s defn macro is an
instance of this type of macro because it aggregates the processes of creating a func-
tion, including
Creating the corresponding function object using fn
Checking for and attaching a documentation string
Building the :arglists metadata
Binding the function name to a Var
Attaching the collected metadata
You could perform all of these steps over and over again every time you wanted to cre-
ate a new function, but thanks to macros you can instead use the more convenient
defn form. Regardless of your application domain and its implementation, program-
ming language boilerplate code inevitably occurs. But identifying these repetitive tasks
and writing macros to simplify and reduce or eliminate the tedious copy-paste-tweak
cycle can work to reduce the incidental complexities inherent in a project. Where mac-
ros differ from techniques familiar to proponents of Java’s object-oriented style—
including hierarchies, frameworks, inversion of control, and the like—is that they’re
treated no differently by the language itself. Clojure macros work to mold the language
into the problem space rather than forcing you to mold the problem space into the
constructs of the language. There’s a specific term for this, domain-specific language, but
in Lisp the distinction between DSL and API is thin to the point of transparency.
Envision a scenario where you want to be able to define Vars that call a function
whenever their root bindings change. You could do this using the add-watch function
Download from Wow! eBook <www.wowebook.com>
Using macros to change forms
165
that allows for the attachment of a watcher to a reference type that’s called whenever a
change occurs within. The add-watch function itself takes three arguments: a refer-
ence, a watch function key, and a watch function called whenever a change occurs.
You could enforce that every time someone wants to define a new Var, they must fol-
low these steps:
1
Define the Var.
2
Define a function (maybe inline to save a step) that will be the watcher.
3
Call add-watch with the proper values.
A meager three steps isn’t too cumbersome a task to remember in a handful of uses,
but over the course of a large project it’s easy to forget and/or morph one of these
steps when the need to perform them many times occurs. Therefore, perhaps a better
approach is to define a macro to perform all of these steps for you, as the following
definition does:
(defmacro def-watched [name & value]
`(do
(def ~name ~@value)
(add-watch (var ~name)
:re-bind
(fn [~'key ~'r old# new#]
(println old# " -> " new#)))))
Ignoring symbol resolution and auto-gensym, which we’ll cover in upcoming sections,
the macro called as (def-watched x 2) expands into roughly the following:
(do (def x 2)
(add-watch (var x)
:re-bind
(fn [key r old new]
(println old " -> " new))))
The results of def-watched are thus
(def-watched x (* 12 12))
x
;=> 144
(def x 0)
; 144 -> 0
Lisp programs in general (and Clojure programs specifically) use macros of this sort
to vastly reduce the boilerplate needed to perform common tasks. Throughout this
chapter, you’ll see macros that combine forms, so there’s no need to dwell on the mat-
ter here. Instead, we’ll move on to a macro domain that does just that, with the added
bonus of performing some interesting transformations in the process.
8.4
Using macros to change forms
One way to design macros is to start by writing out example code that you wish
worked—code that has the minimal distance between what you must specify and the
Download from Wow! eBook <www.wowebook.com>
166
CHAPTER 8 Macros
specific application domain in which you’re working. Then, with the goal of making
this code work, you begin writing macros and functions to fill in the missing pieces.
For example, when designing software systems, it’s often useful to identify the
“things” comprising your given application domain, including their logical groupings.
The level of abstraction at this point in the design is best kept high (Rosenberg 2005)
and shouldn’t include details about implementation. Imagine that you want to
describe a simple domain of the ongoing struggle between humans and monsters:
Man versus monster
People
Men (humans)
Name
Have beards?
Monsters
Chupacabra
Eats goats?
Though this is a simple format, it needs work to be programmatically useful. There-
fore, the goal of this section is to write macros performing the steps to get from this
simple representation to the one more conducive to processing. One such structure is
a tree composed of individual generic nodes, each taking a form similar to that shown
in the next listing.
Listing 8.4 Domain DSL’s underlying form
{:tag <node form>,
Domain, grouping
:attrs {},
Name people
:content [<nodes>]}
Properties
You’d never say this is a beautiful format, but it does present practical advantages over
the original format—it’s a tree, it’s composed of simple types, it’s regular, and it’s rec-
ognizable to some existing libraries.
CLOJURE APHORISM Clojure is a design language where the conceptual
model is also Clojure.
We’ll start with the outer-level element, domain:
(defmacro domain [name & body]
`{:tag :domain,
:attrs {:name (str '~name)},
:content [~@body]})
The body of domain is fairly straightforward in that it sets the domain-level tree node
and splices the body of the macro into the :content slot. After domain expands, you’d
expect its body to be composed of a number of grouping forms, which are then han-
dled by the aptly named macro:
Download from Wow! eBook <www.wowebook.com>
Using macros to change forms
167
(declare handle-things)
(defmacro grouping [name & body]
`{:tag :grouping,
:attrs {:name (str '~name)},
:content [~@(handle-things body)]})
Similarly to domain, grouping expands into a node with its body spliced into the :con-
tent slot. But grouping differs from domain in that it splices in the result of the call to
a function handle-things:
(declare grok-attrs grok-props)
(defn handle-things [things]
(for [t things]
{:tag :thing,
:attrs (grok-attrs (take-while (comp not vector?) t))
:content (if-let [c (grok-props (drop-while (comp not vector?) t))]
[c]
[])})))
Because the body of a thing is fairly simple and regular, we can simplify the implemen-
tation of handle-things by again splitting it into two functions. The first function
grok-attrs handles everything within the body of a thing that’s not a vector, and the
other grok-props handles properties that are. In both cases, these leaf-level functions
return specifically formed maps:
(defn grok-attrs [attrs]
(into {:name (str (first attrs))}
(for [a (rest attrs)]
(cond
(list? a) [:isa (str (second a))]
(string? a) [:comment a]))))
The implementation of grok-attrs may seem overly complex, especially given that
the example domain model DSL only allows for a comment attribute and an optional
isa specification. But by laying out this way, we can easily expand the function to han-
dle a richer set of attributes later. Likewise with grok-props, we provide a more com-
plicated function to pull apart the vector representing a property so that it’s more
conducive to expansion:
(defn grok-props [props]
(when props
{:tag :properties, :attrs nil,
:content (apply vector (for [p props]
{:tag :property,
:attrs {:name (str (first p))},
:content nil}))}))
Now that we’ve created the pieces, take a look at the new DSL in action in the follow-
ing listing.
Download from Wow! eBook <www.wowebook.com>
168
CHAPTER 8 Macros
Listing 8.5 Exploring the domain DSL results
(def d
(domain man-vs-monster
(grouping people
Group of people
(Human "A stock human")
One kind of person
(Man (isa Human)
Another kind of person
"A man, baby"
[name]
[has-beard?]))
(grouping monsters
Group of monsters
(Chupacabra
One kind of monster
"A fierce, yet elusive creature"
[eats-goats?]))))
(:tag d)
;=> :domain
(:tag (first (:content d)))
;=> :grouping
Maybe that’s enough to prove to you that we’ve constructed the promised tree, but
probably not. Therefore, we can pass a tree into a function that expects one of that
form7 and see what comes out on the other end:
(use '[clojure.xml :as xml])
(xml/emit d)
Performing this function call will print out the corresponding XML representation,
minus the pretty printing, shown here.
Listing 8.6 An XML transformation of the domain DSL structure
<?xml version='1.0' encoding='UTF-8'?>
<domain name='man-vs-monster'>
(Domain ...)
<grouping name='people'>
(Grouping ...)
<thing name='Human' comment='A stock human'>
(Human ...)
<properties></properties>
</thing>
<thing name='Man' isa='Human' comment='A man, baby'>
(Man ...)
<properties>
<property name='name'/>
<property name='has-beard?'/>
</properties>
</thing>
</grouping>
(Grouping ...)
<grouping name='monsters'>
<thing name='Chupacabra' comment='A fierce, yet elusive creature'>
<properties>
<property name='eats-goats?'/>
</properties>
7
The namespace clojure.contrib.json in the Clojure contrib library also contains some functions that
would be able to handle the domain DSL structure seamlessly. Additionally, Enlive (http://mng.bz/8Hh6)
should also recognize the resultant structure.
Download from Wow! eBook <www.wowebook.com>
Using macros to control symbolic resolution time
169
</thing>
</grouping>
</domain>
Our approach was to define a single macro entry point domain, intended to build the
top-level layers of the output data structure and instead pass the remainder on to aux-
iliary functions for further processing. In this way, the body of the macro expands into
a series of function calls, each taking some subset of the remaining structure and
returning some result that’s spliced into the final result. This functional composition
approach is fairly common when defining macros. The entirety of the domain descrip-
tion could’ve been written within one monolithic macro, but by splitting the responsi-
bilities, you can more easily extend the representations for the constituent parts.
Macros take data and return data, always. It so happens that in Clojure, code is
data and data is code.
8.5
Using macros to control symbolic resolution time
Whereas functions accept and return values that are meaningful to your application
at runtime, macros accept and return code forms that are meaningful at compile
time. Any symbol has some subtleties depending on whether it’s fully qualified or not,
its resolution time, and its lexical context. These factors can be controlled in any par-
ticular case by the appropriate use of quoting and unquoting, which we explore in
this section.
Clojure macros are mostly safe from name capture, in that the use of syntax-quote
in macros is encouraged and idiomatic, and it’ll resolve symbols at macro-expansion
time. This strategy reduces complexity by ensuring that symbols refer to those avail-
able at a known instance rather than to those unknown in the execution context.
For example, consider one of the simplest possible macros: