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 functions, and first-class functions. We’ll use that last item as our starting point.
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 interesting 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.
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 philosophy 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 programming language and views the problem of software development as the application 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:
1 Although the likely inclusion of closures in some future version of Java should go a long way toward invalidating 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.
Those of you coming from a background in Java might find the idea of creating functions 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.
Even a cursory glance at Clojure is enough to confirm that its primary unit of computation 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
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 interesting to take the idea one step further by instead proving a way to build arbitrary nth functions[2] as shown here:
2 We know that Clojure provides an nth function that works slightly differently, but in this case please indulge our obtuseness.
(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 function 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. Creating 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-parenthesis in a row like this in Clojure, but when you see it, it’s almost always because a function (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.
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 partial function is passed the arguments 100 and 200, the result is their summation plus that of the value 5 captured by partial.
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 on the other hand will return another curried function until it receives a predetermined 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).
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?).
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 reference, 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 runtime (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) ; ... ; 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.
A higher-order function is a function that does at least one of the following:
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.
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 reimplementing core functions and instead build our program from existing parts. You should strive for the same whenever possible.
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 earlier 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 subgroup 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 simple[3] in its Clojure implementation:
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.
(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 values 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:
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!
(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 extensible. 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.
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 processing. Most collection processing can be performed with some combination of the following 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.
Simply put, pure functions are regular functions that, through convention, conform to the following simple guidelines:
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.
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 transparent (the reference to the function is transparent to time). Take a look at pure function 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)))
(manip-map #(int (/ % 2)) #{:plays :loved} (plays 0))
;=> {:band "Burial", :plays 489, :loved 4}
The functions keys-apply and manip-map are both[5] 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:
5 These functions are based on a similar implementation created by Steven Gilardi.
(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 generating 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.
If a function is referentially transparent, then it can more easily be optimized using techniques such as memoization (discussed in chapter 12) and algebraic manipulations (Wadler 1989).
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 matters substantially. Imagine the confusion should you add further impure functions based on further external transient values.
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
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 mechanism coupled with the optional arguments flag &. The same function would be written using Clojure’s named arguments as in the following listing.
(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 section 3.3, allowing much richer ways to declare them.
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 preand 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.
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 Clojure, 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.
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 function 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 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.
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 themselves, 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 functions, we’ll take a step further by exploring lexical 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 mainstream 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 closure: it uses the local x that was defined outside the body of the function, and so the local and its value become a property of the function itself. The function is said to close over the local[6]x, as in the following example:
6 Locals like x in this example are sometimes called free variables. We don’t use the term because Clojure locals are immutable.
(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 something mutable, you run the risk of making your functions impure and thus more difficult to test and reason about, especially if the mutable local is shared.
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 example, we could take the earlier times-two example and generalize it to take an argument 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:
(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.
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 discussion 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 closure along to another function that will use it.
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.
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:
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.
(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 whatever 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 reuse[8] and clarity. Thankfully, in any case the performance differences among the three choices are nominal.
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.
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 handlers in a nested GUI builder. Or it may be a tidy, specifically designed bundle of values and related functions—something that can be thought of as an object.
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 direction 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 coordinates, 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 parameters, because it gets everything it needs to know from the state of the bot that it closes 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-right[9] functions, and store them right there in the object with :forward:
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.
(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 computed 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 environment 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)))})
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 particular object closures, and rightfully so. We encourage you to extrapolate from the closure 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 powerful[10] 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 Clojure’s reify macro, which we’ll cover in section 9.3.
10 ...a fact any sufficiently experienced JavaScript programmer would be able to confirm.
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.
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.
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.
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 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 solutions 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.
A classically recursive algorithm is that of calculating some base number raised to an exponent, or the pow function. A straightforward[12] way to solve this problem recursively is to multiply the base by each successively smaller value of the exponent, as implemented in the following listing.
12 Yes, we’re aware of Math/pow.
(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 problem? The answer lies in what happens when we try to call pow with a large value:
13 Typically mundane recursion is referred to as linear, or the case where the space requirements needed to perform the recursion is proportional to the magnitude of the input.
(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 solution 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.
(defn pow [base exp]
(letfn [(kapow [base exp acc]
(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 recursion 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.
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 generating lazy seqs. The implementation of lz-rec-step used mundane recursion but managed 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 recursion, because often the regular (mundane) recursive definition is the most natural and understandable.
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 consumption of a value or the accumulation of a result. Before we get deeper into implementing tail recursion, we’ll take a moment to appreciate the historical underpinnings of tail-call recursion and expound on its further role within Clojure.
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 programming 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 dealing 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?
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 call[15] 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.
15 Bear in mind that in this scenario, A and B can be different functions or the same function.
Unfortunately for Clojure, neither the Java Virtual Machine nor its bytecode provide 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 generalized tail call. In the general case, there’s currently no way to reliably optimize (Clinger 1998) tail calls.
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))
The implementation of gcd is straightforward, but you’ll notice that we used mundane recursion instead of tail recursion via recur. In a language such as Scheme containing 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.
|
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 |
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 optimize 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
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.
16 The Scala 2.8 compiler recognizes a @tailrec annotation and triggers an error whenever a marked function or method can’t be optimized.
The final benefit of recur is that it allows the forms fn and loop to act as anonymous recursion points.
Why recur indeed.
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 commands: 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 correspond 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.
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 serially. 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 (corresponding 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:
The final example won’t cause a stack overflow because the trampoline function handles 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.
Before wrapping up this chapter, we’re going to take time to talk about a style of programming not necessarily prevalent in Clojure, but moreso in the functional tradition: 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 (Friedman 2001) by viewing it in terms of up to three functions:
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.
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, can be used to make a range of functions that happen to fall into the same mold of a mathematical folding function.
Though this is potentially a powerful technique, there are a number of reasons preventing its widespread adoption in Clojure:
17 Clojure’s future and promise will be discussed in detail in chapter 11.
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 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.
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.
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.
(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.
Now that we’ve created an estimated cost function and a current cost function, we can implement a simple total-cost function for f.
(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.
Before we show the implementation of A*, we need one more auxiliary function minby, 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 determined 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.
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 corresponding 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.
(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 shrubbery at position [0 3], represented by the number 2, and see how astar navigates it.
When tracing the best path, you will see that the astar function prefers the nonshrubbery path. But what would happen if we placed a man-eating bunny along the previously safe path, represented by an ominously large number, as shown next?
As expected, the astar function picks the shrubbery path (2) path instead of the evil bunny path to reach the final destination.
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 partitioning the solution this way, we’ve enabled you to explore different heuristics.
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. Additionally, 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 certain 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.