This guide aims to introduce newcomers and experienced programmers alike to the beauty of functional programming, starting with the simplest building blocks of software. You’ll need a computer, basic proficiency in the command line, a text editor, and an internet connection. By the end of this series, you’ll have a thorough command of the Clojure programming language.
Science, technology, engineering, and mathematics are deeply rewarding fields, yet few women enter STEM as a career path. Still more are discouraged by a culture which repeatedly asserts that women lack the analytic aptitude for writing software, that they are not driven enough to be successful scientists, that it’s not cool to pursue a passion for structural engineering. Those few with the talent, encouragement, and persistence to break in to science and tech are discouraged by persistent sexism in practice: the old boy’s club of tenure, being passed over for promotions, isolation from peers, and flat-out assault. This landscape sucks. I want to help change it.
Women Who Code, PyLadies, Black Girls Code, RailsBridge, Girls Who Code, Girl Develop It, and Lambda Ladies are just a few of the fantastic groups helping women enter and thrive in software. I wholeheartedly support these efforts.
In addition, I want to help in my little corner of the technical community–functional programming and distributed systems–by making high-quality educational resources available for free. The Jepsen series has been, in part, an effort to share my enthusiasm for distributed systems with beginners of all stripes–but especially for women, LGBT folks, and people of color.
As technical authors, we often assume that our readers are white, that our readers are straight, that our readers are traditionally male. This is the invisible default in US culture, and it’s especially true in tech. People continue to assume on the basis of my software and writing that I’m straight, because well hey, it’s a statistically reasonable assumption.
But I’m not straight. I get called faggot, cocksucker, and sinner. People say they’ll pray for me. When I walk hand-in-hand with my boyfriend, people roll down their car windows and stare. They threaten to beat me up or kill me. Every day I’m aware that I’m the only gay person some people know, and that I can show that not all gay people are effeminate, or hypermasculine, or ditzy, or obsessed with image. That you can be a manicurist or a mathematician or both. Being different, being a stranger in your culture, comes with all kinds of challenges. I can’t speak to everyone’s experience, but I can take a pretty good guess.
At the same time, in the technical community I’ve found overwhelming warmth and support, from people of all stripes. My peers stand up for me every day, and I’m so thankful–especially you straight dudes–for understanding a bit of what it’s like to be different. I want to extend that same understanding, that same empathy, to people unlike myself. Moreover, I want to reassure everyone that though they may feel different, they do have a place in this community.
So before we begin, I want to reinforce that you can program, that you can do math, that you can design car suspensions and fire suppression systems and spacecraft control software and distributed databases, regardless of what your classmates and media and even fellow engineers think. You don’t have to be white, you don’t have to be straight, you don’t have to be a man. You can grow up never having touched a computer and still become a skilled programmer. Yeah, it’s harder–and yeah, people will give you shit, but that’s not your fault and has nothing to do with your ability or your right to do what you love. All it takes to be a good engineer, scientist, or mathematician is your curiosity, your passion, the right teaching material, and putting in the hours.
There’s nothing in this guide that’s just for lesbian grandmas or just for mixed-race kids; bros, you’re welcome here too. There’s nothing dumbed down. We’re gonna go as deep into the ideas of programming as I know how to go, and we’re gonna do it with everyone on board.
No matter who you are or who people think you are, this guide is for you.
This book is about how to program. We’ll be learning in Clojure, which is a modern dialect of a very old family of computer languages, called Lisp. You’ll find that many of this book’s ideas will translate readily to other languages; though they may be expressed in different ways.
We’re going to explore the nature of syntax, metalanguages, values, references, mutation, control flow, and concurrency. Many languages leave these ideas implicit in the language construction, or don’t have a concept of metalanguages or concurrency at all. Clojure makes these ideas explicit, first-class language constructs.
At the same time, we’re going to defer or omit any serious discussion of static type analysis, hardware, and performance. This is not to say that these ideas aren’t important; just that they don’t fit well within this particular narrative arc. For a deep exploration of type theory I recommend a study in Haskell, and for a better understanding of underlying hardware, learning C and an assembly language will undoubtedly help.
In more general terms, Clojure is a well-rounded language. It offers broad library support and runs on multiple operating systems. Clojure performance is not terrific, but is orders of magnitude faster than Ruby, Python, or Javascript. Unlike some faster languages, Clojure emphasizes safety in its type system and approach to parallelism, making it easier to write correct multithreaded programs. Clojure is concise, requiring very little code to express complex operations. It offers a REPL and dynamic type system: ideal for beginners to experiment with, and well-suited for manipulating complex data structures. A consistently designed standard library and full-featured set of core datatypes rounds out the Clojure toolbox.
Finally, there are some drawbacks. As a compiled language, Clojure is much slower to start than a scripting language; this makes it unsuitable for writing small scripts for interactive use. Clojure is also not well-suited for high-performance numeric operations. Though it is possible, you have to jump through hoops to achieve performance comparable with Java. I’ll do my best to call out these constraints and shortcomings as we proceed through the text.
With that context out of the way, let’s get started by installing Clojure!
First, you’ll need a Java Virtual Machine, or JVM, and its associated development tools, called the JDK. This is the software which runs a Clojure program. If you’re on Windows, install Oracle JDK 1.7. If you’re on OS X or Linux, you may already have a JDK installed. In a terminal, try:
If you see something like
Then you’re good to go. If you don’t see any output from that command, install the appropriate Oracle JDK 1.7 for your operating system, or whatever JDK your package manager has available.
When you have a JDK, you’ll need Leiningen, the Clojure build tool. If you’re on a Linux or OS X computer, the instructions below should get you going right away. If you’re on Windows, see the Leiningen page for an installer. If you get stuck, you might want to start with a primer on command line basics.
mkdir -p ~/bin
cd ~/bin
curl -O https://raw.githubusercontent.com/technomancy/leiningen/stable/bin/lein
chmod a+x leinLeiningen automatically handles installing Clojure, finding libraries from the internet, and building and running your programs. We’ll create a new Leiningen project to play around in:
cd
lein new scratchThis creates a new directory in your homedir, called scratch. If you see command not found instead, it means the directory ~/bin isn’t registered with your terminal as a place to search for programs. To fix this, add the line
export PATH="$PATH":~/binto the file .bash_profile in your home directory, then run source ~/.bash_profile. Re-running lein new scratch should work.
Let’s enter that directory, and start using Clojure itself:
cd scratch
lein replWhen you type lein repl at the terminal, you’ll see something like this:
aphyr@waterhouse:~/scratch$ lein repl
nREPL server started on port 45413
REPL-y 0.2.0
Clojure 1.5.1
Docs: (doc function-name-here)
(find-doc "part-of-name-here")
Source: (source function-name-here)
Javadoc: (javadoc java-object-or-class-here)
Exit: Control+D or (exit) or (quit)
user=>This is an interactive Clojure environment called a REPL, for “Read, Evaluate, Print Loop”. It’s going to read a program we enter, run that program, and print the results. REPLs give you quick feedback, so they’re a great way to explore a program interactively, run tests, and prototype new ideas.
Let’s write a simple program. The simplest, in fact. Type “nil”, and hit enter.
nil is the most basic value in Clojure. It represents emptiness, nothing-doing, not-a-thing. The absence of information.
true and false are a pair of special values called Booleans. They mean exactly what you think: whether a statement is true or false. true, false, and nil form the three poles of the Lisp logical system.
This is the number zero. Its numeric friends are 1, -47, 1.2e-4, 1/3, and so on. We might also talk about strings, which are chunks of text surrounded by double quotes:
nil, true, 0, and "hi there!" are all different types of values; the nouns of programming. Just as one could say “House.” in English, we can write a program like "hello, world" and it evaluates to itself: the string "hello world". But most sentences aren’t just about stating the existence of a thing; they involve action. We need verbs.
user=> inc
#<core$inc clojure.core$inc@6f7ef41c>This is a verb called inc–short for “increment”. Specifically, inc is a symbol which points to a verb: #<core$inc clojure.core$inc@6f7ef41c> – just like the word “run” is a name for the concept of running.
There’s a key distinction here–that a signifier, a reference, a label, is not the same as the signified, the referent, the concept itself. If you write the word “run” on paper, the ink means nothing by itself. It’s just a symbol. But in the mind of a reader, that symbol takes on meaning; the idea of running.
Unlike the number 0, or the string “hi”, symbols are references to other values. when Clojure evaluates a symbol, it looks up that symbol’s meaning. Look up inc, and you get #<core$inc clojure.core$inc@6f7ef41c>.
Can we refer to the symbol itself, without looking up its meaning?
Yes. The single quote ' escapes a sentence. In programming languages, we call sentences expressions or statements. A quote says “Rather than evaluating this expression’s text, simply return the text itself, unchanged.” Quote a symbol, get a symbol. Quote a number, get a number. Quote anything, and get it back exactly as it came in.
A new kind of value, surrounded by parentheses: the list. LISP originally stood for LISt Processing, and lists are still at the core of the language. In fact, they form the most basic way to compose expressions, or sentences. A list is a single expression which has multiple parts. For instance, this list contains three elements: the numbers 1, 2, and 3. Lists can contain anything: numbers, strings, even other lists:
A list containing two elements: the number 1, and a second list. That list contains two elements: the number 2, and another list. That list contains two elements: 3, and an empty list.
You could think of this structure as a tree–which is a provocative idea, because languages are like trees too: sentences are comprised of clauses, which can be nested, and each clause may have subjects modified by adjectives, and verbs modified by adverbs, and so on. “Lindsay, my best friend, took the dog which we found together at the pound on fourth street, for a walk with her mother Michelle.”
Took
Lindsay
my best friend
the dog
which we found together
at the pound
on fourth street
for a walk
with her mother
MichelleBut let’s try something simpler. Something we know how to talk about. “Increment the number zero.” As a tree:
We have a symbol for incrementing, and we know how to write the number zero. Let’s combine them in a list:
A basic sentence. Remember, since it’s quoted, we’re talking about the tree, the text, the expression, by itself. Absent interpretation. If we remove the single-quote, Clojure will interpret the expression:
Incrementing zero yields one. And if we wanted to increment that value?
A sentence in Lisp is a list. It starts with a verb, and is followed by zero or more objects for that verb to act on. Each part of the list can itself be another list, in which case that nested list is evaluated first, just like a nested clause in a sentence. When we type
Clojure first looks up the meanings for the symbols in the code:
Then evaluates the innermost list (inc 0), which becomes the number 1:
Finally, it evaluates the outer list, incrementing the number 1:
Every list starts with a verb. Parts of a list are evaluated from left to right. Innermost lists are evaluated before outer lists.
That’s it.
The entire grammar of Lisp: the structure for every expression in the language. We transform expressions by substituting meanings for symbols, and obtain some result. This is the core of the Lambda Calculus, and it is the theoretical basis for almost all computer languages. Ruby, Javascript, C, Haskell; all languages express the text of their programs in different ways, but internally all construct a tree of expressions. Lisp simply makes it explicit.
We started by learning a few basic nouns: numbers like 5, strings like "cat", and symbols like inc and +. We saw how quoting makes the difference between an expression itself and the thing it evaluates to. We discovered symbols as names for other values, just like how words represent concepts in any other language. Finally, we combined lists to make trees, and used those trees to represent a program.
With these basic elements of syntax in place, it’s time to expand our vocabulary with new verbs and nouns; learning to represent more complex values and transform them in different ways.
We’ve learned the basics of Clojure’s syntax and evaluation model. Now we’ll take a tour of the basic nouns in the language.
We’ve seen a few different values already – for instance, nil, true, false, 1, 2.34, and "meow". Clearly all these things are different values, but some of them seem more alike than others.
For instance, 1 and 2 are very similar numbers; both can be added, divided, multiplied, and subtracted. 2.34 is also a number, and acts very much like 1 and 2, but it’s not quite the same. It’s got decimal points. It’s not an integer. And clearly true is not very much like a number. What is true plus one? Or false divided by 5.3? These questions are poorly defined.
We say that a type is a group of values which work in the same way. It’s a property that some values share, which allows us to organize the world into sets of similar things. 1 + 1 and 1 + 2 use the same addition, which adds together integers. Types also help us verify that a program makes sense: that you can only add together numbers, instead of adding numbers to porcupines.
Types can overlap and intersect each other. Cats are animals, and cats are fuzzy too. You could say that a cat is a member (or sometimes “instance”), of the fuzzy and animal types. But there are fuzzy things like moss which aren’t animals, and animals like alligators that aren’t fuzzy in the slightest.
Other types completely subsume one another. All tabbies are housecats, and all housecats are felidae, and all felidae are animals. Everything which is true of an animal is automatically true of a housecat. Hierarchical types make it easier to write programs which don’t need to know all the specifics of every value; and conversely, to create new types in terms of others. But they can also get in the way of the programmer, because not every useful classification (like “fuzziness”) is purely hierarchical. Expressing overlapping types in a hierarchy can be tricky.
Every language has a type system; a particular way of organizing nouns into types, figuring out which verbs make sense on which types, and relating types to one another. Some languages are strict, and others more relaxed. Some emphasize hierarchy, and others a more ad-hoc view of the world. We call Clojure’s type system strong in that operations on improper types are simply not allowed: the program will explode if asked to subtract a dandelion. We also say that Clojure’s types are dynamic because they are enforced when the program is run, instead of when the program is first read by the computer.
We’ll learn more about the formal relationships between types later, but for now, keep this in the back of your head. It’ll start to hook in to other concepts later.
Let’s find the type of the number 3:
So 3 is a java.lang.Long, or a “Long”, for short. Because Clojure is built on top of Java, many of its types are plain old Java types.
Longs, internally, are represented as a group of sixty-four binary digits (ones and zeroes), written down in a particular pattern called signed two’s complement representation. You don’t need to worry about the specifics–there are only two things to remember about longs. First, longs use one bit to store the sign: whether the number is positive or negative. Second, the other 63 bits represent the size of the number. That means the biggest number you can represent with a long is 2^63 - 1 (the minus one is because of the number 0), and the smallest long is -2^63.
How big is 2^63 - 1?
That’s a reasonably big number. Most of the time, you won’t need anything bigger, but… what if you did? What happens if you add one to the biggest Long?
user=> (inc Long/MAX_VALUE)
ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)An error occurs! This is Clojure telling us that something went wrong. The type of error was an ArithmeticException, and its message was “integer overflow”, meaning “this type of number can’t hold a number that big”. The error came from a specific place in the source code of the program: Numbers.java, on line 1388. That’s a part of the Clojure source code. Later, we’ll learn more about how to unravel error messages and find out what went wrong.
The important thing is that Clojure’s type system protected us from doing something dangerous; instead of returning a corrupt value, it aborted evaluation and returned an error.
If you do need to talk about really big numbers, you can use a BigInt: an arbitrary-precision integer. Let’s convert the biggest Long into a BigInt, then increment it:
Notice the N at the end? That’s how Clojure writes arbitrary-precision integers.
There are also smaller numbers.
user=> (type (int 0))
java.lang.Integer
user=> (type (short 0))
java.lang.Short
user=> (type (byte 0))
java.lang.ByteIntegers are half the size of Longs; they store values in 32 bits. Shorts are 16 bits, and Bytes are 8. That means their biggest values are 2^31-1, 2^15-1, and 2^7-1, respectively.
To represent numbers between integers, we often use floating-point numbers, which can represent small numbers with fine precision, and large numbers with coarse precision. Floats use 32 bits, and Doubles use 64. Doubles are the default in Clojure.
Floating point math is complicated, and we won’t get bogged down in the details just yet. The important thing to know is floats and doubles are approximations. There are limits to their correctness:
To represent fractions exactly, we can use the ratio type:
The exact behavior of mathematical operations in Clojure depends on their types. In general, though, Clojure aims to preserve information. Adding two longs returns a long; adding a double and a long returns a double.
3 and 3.0 are not the same number; one is a long, and the other a double. But for most purposes, they’re equivalent, and Clojure will tell you so:
= asks whether all the things that follow are equal. Since floats are approximations, = considers them different from integers. == also compares things, but a little more loosely: it considers integers equivalent to their floating-point representations.
We can also subtract with -, multiply with *, and divide with /.
Putting the verb first in each list allows us to add or multiply more than one number in the same step:
Subtraction with more than 2 numbers subtracts all later numbers from the first. Division divides the first number by all the rest.
By extension, we can define useful interpretations for numeric operations with just a single number:
We can also add or multiply a list of no numbers at all, obtaining the additive and multiplicative identities, respectively. This might seem odd, especially coming from other languages, but we’ll see later that these generalizations make it easier to reason about higher-level numeric operations.
Often, we want to ask which number is bigger, or if one number falls between two others. <= means “less than or equal to”, and asserts that all following values are in order from smallest to biggest.
< means “strictly less than”, and works just like <=, except that no two values may be equal.
Their friends > and >= mean “greater than” and “greater than or equal to”, respectively, and assert that numbers are in descending order.
Also commonly used are inc and dec, which add and subtract one to a number, respectively:
One final note: equality tests can take more than 2 numbers as well.
We saw that strings are text, surrounded by double quotes, like "foo". Strings in Clojure are, like Longs, Doubles, and company, backed by a Java type:
We can make almost anything into a string with str. Strings, symbols, numbers, booleans; every value in Clojure has a string representation. Note that nil’s string representation is ""; an empty string.
user=> (str "cat")
"cat"
user=> (str 'cat)
"cat"
user=> (str 1)
"1"
user=> (str true)
"true"
user=> (str '(1 2 3))
"(1 2 3)"
user=> (str nil)
""str can also combine things together into a single string, which we call “concatenation”.
To look for patterns in text, we can use a regular expression, which is a tiny language for describing particular arrangements of text. re-find and re-matches look for occurrences of a regular expression in a string. To find a cat:
That #"..." is Clojure’s way of writing a regular expression.
With re-matches, you can extract particular parts of a string which match an expression. Here we find two strings, separated by a :. The parentheses mean that the regular expression should capture that part of the match. We get back a list containing the part of the string that matched the first parentheses, followed by the part that matched the second parentheses.
Regular expressions are a powerful tool for searching and matching text, especially when working with data files. Since regexes work the same in most languages, you can use any guide online to learn more. It’s not something you have to master right away; just learn specific tricks as you find you need them. For a deeper guide, try Fitzgerald’s Introducing Regular Expressions.
Everything in Clojure has a sort of charge, a truth value, sometimes called “truthiness”. true is positive and false is negative. nil is negative, too.
Every other value in Clojure is positive.
user=> (boolean 0)
true
user=> (boolean 1)
true
user=> (boolean "hi there")
true
user=> (boolean str)
trueIf you’re coming from a C-inspired language, where 0 is considered false, this might be a bit surprising. Likewise, in much of POSIX, 0 is considered success and nonzero values are failures. Lisp allows no such confusion: the only negative values are false and nil.
We can reason about truth values using and, or, and not. and returns the first negative value, or the last value if all are truthy.
Similarly, or returns the first positive value.
And not inverts the logical sense of a value:
We’ll learn more about Boolean logic when we start talking about control flow; the way we alter evaluation of a program and express ideas like “if I’m a cat, then meow incessantly”.
We saw symbols in the previous chapter; they’re bare strings of characters, like foo or +.
Symbols can have either short or full names. The short name is used to refer to things locally. The fully qualified name is used to refer unambiguously to a symbol from anywhere. If I were a symbol, my name would be “Kyle”, and my full name “Kyle Kingsbury.”
Symbol names are separated with a /. For instance, the symbol str is also present in a family called clojure.core; the corresponding full name is clojure.core/str.
When we talked about the maximum size of an integer, that was a fully-qualified symbol, too.
The job of symbols is to refer to things, to point to other values. When evaluating a program, symbols are looked up and replaced by their corresponding values. That’s not the only use of symbols, but it’s the most common.
Closely related to symbols and strings are keywords, which begin with a :. Keywords are like strings in that they’re made up of text, but are specifically intended for use as labels or identifiers. These aren’t labels in the sense of symbols: keywords aren’t replaced by any other value. They’re just names, by themselves.
As labels, keywords are most useful when paired with other values in a collection, like a map. Keywords can also be used as verbs to look up specific values in other data types. We’ll learn more about keywords shortly.
A collection is a group of values. It’s a container which provides some structure, some framework, for the things that it holds. We say that a collection contains elements, or members. We saw one kind of collection–a list–in the previous chapter.
Remember, we quote lists with a ' to prevent them from being evaluated. You can also construct a list using list:
Lists are comparable just like every other value:
You can modify a list by conjoining an element onto it:
We added 4 to the list–but it appeared at the front. Why? Internally, lists are stored as a chain of values: each link in the chain is a tiny box which holds the value and a connection to the next link. This data structure, called a linked list, offers immediate access to the first element.
But getting to the second element requires an extra hop down the chain
and the third element a hop after that, and so on.
nth gets the element of an ordered collection at a particular index. The first element is index 0, the second is index 1, and so on.
This means that lists are well-suited for small collections, or collections which are read in linear order, but are slow when you want to get arbitrary elements from later in the list. For fast access to every element, we use a vector.
Vectors are surrounded by square brackets, just like lists are surrounded by parentheses. Because vectors aren’t evaluated like lists are, there’s no need to quote them:
You can also create vectors with vector, or change other structures into vectors with vec:
conj on a vector adds to the end, not the start:
Our friends first, second, and nth work here too; but unlike lists, nth is fast on vectors. That’s because internally, vectors are represented as a very broad tree of elements, where each part of the tree branches into 32 smaller trees. Even very large vectors are only a few layers deep, which means getting to elements only takes a few hops.
In addition to first, you’ll often want to get the remaining elements in a collection. There are two ways to do this:
rest and next both return “everything but the first element”. They differ only by what happens when there are no remaining elements:
rest returns logical true, next returns logical false. Each has their uses, but in almost every case they’re equivalent–I interchange them freely.
We can get the final element of any collection with last:
And figure out how big the vector is with count:
Because vectors are intended for looking up elements by index, we can also use them directly as verbs:
user=> ([:a :b :c] 1)
:bSo we took the vector containing three keywords, and asked “What’s the element at index 1?” Lisp, like most (but not all!) modern languages, counts up from zero, not one. Index 0 is the first element, index 1 is the second element, and so on. In this vector, finding the element at index 1 evaluates to :b.
Finally, note that vectors and lists containing the same elements are considered equal in Clojure:
In almost all contexts, you can consider vectors, lists, and other sequences as interchangeable. They only differ in their performance characteristics, and in a few data-structure-specific operations.
Sometimes you want an unordered collection of values; especially when you plan to ask questions like “does the collection have the number 3 in it?” Clojure, like most languages, calls these collections sets.
Sets are surrounded by #{...}. Notice that though we gave the elements :a, :b, and :c, they came out in a different order. In general, the order of sets can shift at any time. If you want a particular order, you can ask for it as a list or vector:
Or ask for the elements in sorted order:
conj on a set adds an element:
Sets never contain an element more than once, so conjing an element which is already present does nothing. Conversely, one removes elements with disj:
The most common operation with a set is to check whether something is inside it. For this we use contains?.
Like vectors, you can use the set itself as a verb. Unlike contains?, this expression returns the element itself (if it was present), or nil.
You can make a set out of any other collection with set.
The last collection on our tour is the map: a data structure which associates keys with values. In a dictionary, the keys are words and the definitions are the values. In a library, keys are call signs, and the books are values. Maps are indexes for looking things up, and for representing different pieces of named information together. Here’s a cat:
Maps are surrounded by braces {...}, filled by alternating keys and values. In this map, the three keys are :name, :color, and :weight, and their values are "mittens", "black", and 9, respectively. We can look up the corresponding value for a key with get:
get can also take a default value to return instead of nil, if the key doesn’t exist in that map.
Since lookups are so important for maps, we can use a map as a verb directly:
And conversely, keywords can also be used as verbs, which look themselves up in maps:
You can add a value for a given key to a map with assoc.
user=> (assoc {:bolts 1088} :camshafts 3)
{:camshafts 3 :bolts 1088}
user=> (assoc {:camshafts 3} :camshafts 2)
{:camshafts 2}Assoc adds keys if they aren’t present, and replaces values if they’re already there. If you associate a value onto nil, it creates a new map.
You can combine maps together using merge, which yields a map containing all the elements of all given maps, preferring the values from later ones.
Finally, to remove a value, use dissoc.
All these collections and types can be combined freely. As software engineers, we model the world by creating a particular representation of the problem in the program. Having a rich set of values at our disposal allows us to talk about complex problems. We might describe a person:
{:name "Amelia Earhart"
:birth 1897
:death 1939
:awards {"US" #{"Distinguished Flying Cross" "National Women's Hall of Fame"}
"World" #{"Altitude record for Autogyro" "First to cross Atlantic twice"}}}Or a recipe:
{:title "Chocolate chip cookies"
:ingredients {"flour" [(+ 2 1/4) :cup]
"baking soda" [1 :teaspoon]
"salt" [1 :teaspoon]
"butter" [1 :cup]
"sugar" [3/4 :cup]
"brown sugar" [3/4 :cup]
"vanilla" [1 :teaspoon]
"eggs" 2
"chocolate chips" [12 :ounce]}}Or the Gini coefficients of nations, as measured over time:
{"Afghanistan" {2008 27.8}
"Indonesia" {2008 34.1 2010 35.6 2011 38.1}
"Uruguay" {2008 46.3 2009 46.3 2010 45.3}}In Clojure, we compose data structures to form more complex values; to talk about bigger ideas. We use operations like first, nth, get, and contains? to extract specific information from these structures, and modify them using conj, disj, assoc, dissoc, and so on.
We started this chapter with a discussion of types: groups of similar objects which obey the same rules. We learned that bigints, longs, ints, shorts, and bytes are all integers, that doubles and floats are approximations to decimal numbers, and that ratios represent fractions exactly. We learned the differences between strings for text, symbols as references, and keywords as short labels. Finally, we learned how to compose, alter, and inspect collections of elements. Armed with the basic nouns of Clojure, we’re ready to write a broad array of programs.
I’d like to conclude this tour with one last type of value. We’ve inspected dozens of types so far–but what what happens when you turn the camera on itself?
What is this type thing, exactly? What are these verbs we’ve been learning, and where do they come from? This is the central question of chapter three: functions.
We left off last chapter with a question: what are verbs, anyway? When you evaluate (type :mary-poppins), what really happens?
To understand how type works, we’ll need several new ideas. First, we’ll expand on the notion of symbols as references to other values. Then we’ll learn about functions: Clojure’s verbs. Finally, we’ll use the Var system to explore and change the definitions of those functions.
We know that symbols are names for things, and that when evaluated, Clojure replaces those symbols with their corresponding values. +, for instance, is a symbol which points to the verb #<core$_PLUS_ clojure.core$_PLUS_@12992c>.
When you try to use a symbol which has no defined meaning, Clojure refuses:
user=> cats
CompilerException java.lang.RuntimeException: Unable to resolve symbol: cats in this context, compiling:(NO_SOURCE_PATH:0:0)But we can define a meaning for a symbol within a specific expression, using let.
The let expression first takes a vector of bindings: alternating symbols and values that those symbols are bound to, within the remainder of the expression. “Let the symbol cats be 5, and construct a string composed of "I have ", cats, and " cats".
Let bindings apply only within the let expression itself. They also override any existing definitions for symbols at that point in the program. For instance, we can redefine addition to mean subtraction, for the duration of a let:
But that definition doesn’t apply outside the let:
We can also provide multiple bindings. Since Clojure doesn’t care about spacing, alignment, or newlines, I’ll write this on multiple lines for clarity.
user=> (let [person "joseph"
num-cats 186]
(str person " has " num-cats " cats!"))
"joseph has 186 cats!"When multiple bindings are given, they are evaluated in order. Later bindings can use previous bindings.
So fundamentally, let defines the meaning of symbols within an expression. When Clojure evaluates a let, it replaces all occurrences of those symbols in the rest of the let expression with their corresponding values, then evaluates the rest of the expression.
We saw in chapter one that Clojure evaluates lists by substituting some other value in their place:
inc takes any number, and is replaced by that number plus one. That sounds an awful lot like a let:
If we bound x to 5 instead of 1, this expression would evaluate to 6. We can think about inc like a let expression, but without particular values provided for the symbols.
We can’t actually evaluate this program, because there’s no value for x yet. It could be 1, or 4, or 1453. We say that x is unbound, because it has no binding to a particular value. This is the nature of the function: an expression with unbound symbols.
Does the name of that function remind you of anything?
Almost all verbs in Clojure are functions. Functions represent unrealized computation: expressions which are not yet evaluated, or incomplete. This particular function works just like inc: it’s an expression which has a single unbound symbol, x. When we invoke the function with a particular value, the expressions in the function are evaluated with x bound to that value.
We say that x is this function’s argument, or parameter. When Clojure evaluates (inc 2), we say that inc is called with 2, or that 2 is passed to inc. The result of that function invocation is the function’s return value. We say that (inc 2) returns 3.
Fundamentally, functions describe the relationship between arguments and return values: given 1, return 2. Given 2, return 3, and so on. Let bindings describe a similar relationship, but with a specific set of values for those arguments. let is evaluated immediately, whereas fn is evaluated later, when bindings are provided.
There’s a shorthand for writing functions, too: #(+ % 1) is equivalent to (fn [x] (+ x 1)). % takes the place of the first argument to the function. You’ll sometime see %1, %2, etc. used for the first argument, second argument, and so on.
user=> (let [burrito #(list "beans" % "cheese")]
(burrito "carnitas"))
("beans" "carnitas" "cheese")Since functions exist to defer evaluation, there’s no sense in creating and invoking them in the same expression as we’ve done here. What we want is to give names to our functions, so they can be recombined in different ways.
Compare that expression to an equivalent, expanded form:
The name twice is gone, and in its place is the same sort of computation – (* 2 something) – written twice. While we could represent our programs as a single massive expression, it’d be impossible to reason about. Instead, we use functions to compact redundant expressions, by isolating common patterns of computation. Symbols help us re-use those functions (and other values) in more than one place. By giving the symbols meaningful names, we make it easier to reason about the structure of the program as a whole; breaking it up into smaller, understandable parts.
This is core pursuit of software engineering: organizing expressions. Almost every programming language is in search of the right tools to break apart, name, and recombine expressions to solve large problems. In Clojure we’ll see one particular set of tools for composing programs, but the underlying ideas will transfer to many other languages.
We’ve used let to define a symbol within an expression, but what about the default meanings of +, conj, and type? Are they also let bindings? Is the whole universe one giant let?
Well, not exactly. That’s one way to think about default bindings, but it’s brittle. We’d need to wrap our whole program in a new let expression every time we wanted to change the meaning of a symbol. And moreover, once a let is defined, there’s no way to change it. If we want to redefine symbols for everyone–even code that we didn’t write–we need a new construct: a mutable variable.
def defines a type of value we haven’t seen before: a var. Vars, like symbols, are references to other values. When evaluated, a symbol pointing to a var is replaced by the var’s corresponding value:
def also binds the symbol cats (and its globally qualified equivalent user/cats) to that var.
When we said in chapter one that inc, list, and friends were symbols that pointed to functions, that wasn’t the whole story. The symbol inc points to the var #'inc, which in turn points to the function #<core$inc clojure.core$inc@16bc0b3c>. We can see the intermediate var with resolve:
user=> 'inc
inc ; the symbol
user=> (resolve 'inc)
#'clojure.core/inc ; the var
user=> (eval 'inc)
#<core$inc clojure.core$inc@16bc0b3c> ; the valueWhy two layers of indirection? Because unlike the symbol, we can change the meaning of a Var for everyone, globally, at any time.
user=> (def astronauts [])
#'user/astronauts
user=> (count astronauts)
0
user=> (def astronauts ["Sally Ride" "Guy Bluford"])
#'user/astronauts
user=> (count astronauts)
2Notice that astronauts had two distinct meanings, depending on when we evaluated it. After the first def, astronauts was an empty vector. After the second def, it had one entry.
If this seems dangerous, you’re a smart cookie. Redefining names in this way changes the meaning of expressions everywhere in a program, without warning. Expressions which relied on the value of a Var could suddenly take on new, possibly incorrect, meanings. It’s a powerful tool for experimenting at the REPL, and for updating a running program, but it can have unexpected consequences. Good Clojurists use def to set up a program initially, and only change those definitions with careful thought.
Totally redefining a Var isn’t the only option. There are safer, controlled ways to change the meaning of a Var within a particular part of a program, which we’ll explore later.
Armed with def, we’re ready to create our own named functions in Clojure.
Creating a function and binding it to a var is so common that it has its own form: defn, short for def fn.
Functions don’t have to take an argument. We’ve seen functions which take zero arguments, like (+).
But if we try to use our earlier form with one argument, Clojure complains that the arity – the number of arguments to the function–is incorrect.
user=> (half 10)
ArityException Wrong number of args (1) passed to: user$half clojure.lang.AFn.throwArity (AFn.java:437)To handle multiple arities, functions have an alternate form. Instead of an argument vector and a body, one provides a series of lists, each of which starts with an argument vector, followed by the body.
Multiple arguments work just like you expect. Just specify an argument vector of two, or three, or however many arguments the function takes.
Some functions can take any number of arguments. For that, Clojure provides &, which slurps up all remaining arguments as a list:
user=> (defn vargs
[x y & more-args]
{:x x
:y y
:more more-args})
#'user/vargs
user=> (vargs 1)
ArityException Wrong number of args (1) passed to: user$vargs clojure.lang.AFn.throwArity (AFn.java:437)
user=> (vargs 1 2)
{:x 1, :y 2, :more nil}
user=> (vargs 1 2 3 4 5)
{:x 1, :y 2, :more (3 4 5)}Note that x and y are mandatory, though there don’t have to be any remaining arguments.
To keep track of what arguments a function takes, why the function exists, and what it does, we usually include a docstring. Docstrings help fill in the missing context around functions, to explain their assumptions, context, and purpose to the world.
(defn launch
"Launches a spacecraft into the given orbit by initiating a
controlled on-axis burn. Does not automatically stage, but
does vector thrust, if the craft supports it."
[craft target-orbit]
"OK, we don't know how to control spacecraft yet.")Docstrings are used to automatically generate documentation for Clojure programs, but you can also access them from the REPL.
user=> (doc launch)
-------------------------
user/launch
([craft target-orbit])
Launches a spacecraft into the given orbit by initiating a
controlled on-axis burn. Does not automatically stage, but
does vector thrust, if the craft supports it.
nildoc tells us the full name of the function, the arguments it accepts, and its docstring. This information comes from the #'launch var’s metadata, and is saved there by defn. We can inspect metadata directly with the meta function:
(meta #'launch)
{:arglists ([craft target-orbit]), :ns #<Namespace user>, :name launch, :column 1, :doc "Launches a spacecraft into the given orbit.", :line 1, :file "NO_SOURCE_PATH"}
There’s some other juicy information in there, like the file the function was
defined in and which line and column it started at, but that’s not particularly
useful since we’re in the REPL, not a file. However, this *does* hint at a way to
answer our motivating question: how does the `type` function work?We know that type returns the type of an object:
And that type, like all functions, is a kind of object with its own unique type:
user=> type
#<core$type clojure.core$type@39bda9b9>
user=> (type type)
clojure.core$type
```
This tells us that `type` is a particular *instance*, at memory address `39bda9b9`,
of the type `clojure.core$type`. `clojure.core` is a namespace which defines the
fundamentals of the Clojure language, and `$type` tells us that it’s named `type`
in that namespace. None of this is particularly helpful, though. Maybe we can
find out more about the `clojure.core$type` by asking what its *supertypes* are:
```clojure
user=> (supers (type type))
#{clojure.lang.AFunction clojure.lang.IMeta java.util.concurrent.Callable clojure.lang.Fn clojure.lang.AFn java.util.Comparator java.lang.Object clojure.lang.RestFn clojure.lang.IObj java.lang.Runnable java.io.Serializable clojure.lang.IFn}
```
This is a set of all the types that include `type`. We say that `type` is an
*instance* of `clojure.lang.AFunction`, or that it *implements* or *extends*
`java.util.concurrent.Callable`, and so on. Since it’s a member of
`clojure.lang.IMeta` it has metadata, and since it’s a member of
`clojure.lang.AFn`, it’s a function. Just to double check, let’s confirm that
`type` is indeed a function:
```clojure
user=> (fn? type)
true
```
What about its documentation?
```clojure
user=> (doc type)
-------------------------
clojure.core/type
([x])
Returns the :type metadata of x, or its Class if none
nil
```
Ah, that’s helpful. `type` can take a single argument, which it calls `x`. If it
has `:type` metadata, that’s what it returns. Otherwise, it returns the class of
x. Let’s take a deeper look at `type`‘s metadata for more clues.
```clojure
user=> (meta #'type)
{:ns #<Namespace clojure.core>, :name type, :arglists ([x]), :column 1, :added "1.0", :static true, :doc "Returns the :type metadata of x, or its Class if none", :line 3109, :file "clojure/core.clj"}Look at that! This function was first added to Clojure in version 1.0, and is defined in the file clojure/core.clj, on line 3109. We could go dig up the Clojure source code and read its definition there–or we could ask Clojure to do it for us:
user=> (source type)
(defn type
"Returns the :type metadata of x, or its Class if none"
{:added "1.0"
:static true}
[x]
(or (get (meta x) :type) (class x)))
nilAha! Here, at last, is how type works. It’s a function which takes a single argument x, and returns either :type from its metadata, or (class x).
We can delve into any function in Clojure using these tools:
user=> (source +)
(defn +
"Returns the sum of nums. (+) returns 0. Does not auto-promote
longs, will throw on overflow. See also: +'"
{:inline (nary-inline 'add 'unchecked_add)
:inline-arities >1?
:added "1.2"}
([] 0)
([x] (cast Number x))
([x y] (. clojure.lang.Numbers (add x y)))
([x y & more]
(reduce1 + (+ x y) more)))
nilAlmost every function in a programming language is made up of other, simpler functions. +, for instance, is defined in terms of cast, add, and reduce1. Sometimes functions are defined in terms of themselves. + uses itself twice in this definition; a technique called recursion.
At the bottom, though, are certain fundamental constructs below which you can go no further. Core axioms of the language. Lisp calls these “special forms”. def and let are special forms (well–almost: let is a thin wrapper around let*, which is a special form) in Clojure. These forms are defined by the core implementation of the language, and are not reducible to other Clojure expressions.
Some Lisps are written entirely in terms of a few special forms, but Clojure is much less pure. Many functions bottom out in Java functions and types, or, for CLJS, in terms of Javascript. Any time you see an expression like (. clojure.lang.Numbers (add x y)), there’s Java code underneath. Below Java lies the JVM, which might be written in C or C++, depending on which one you use. And underneath C and C++ lie more libraries, the operating system, assembler, microcode, registers, and ultimately, electrons flowing through silicon.
A well-designed language isolates you from details you don’t need to worry about, like which logic gates or registers to use, and lets you focus on the task at hand. Good languages also need to allow escape hatches for performance or access to dangerous functionality, as we saw with Vars. You can write entire programs entirely in terms of Clojure, but sometimes, for performance or to use tools from other languages, you’ll rely on Java. The Clojure code is easy to explore with doc and source, but Java can be more opaque–I usually rely on the java source files and online documentation.
We’ve seen how let associates names with values in a particular expression, and how Vars allow for mutable bindings which apply universally. and whose definitions can change over time. We learned that Clojure verbs are functions, which express the general shape of an expression but with certain values unbound. Invoking a function binds those variables to specific values, allowing evaluation of the function to proceed.
Functions decompose programs into simpler pieces, expressed in terms of one another. Short, meaningful names help us understand what those functions (and other values) mean.
Finally, we learned how to introspect Clojure functions with doc and source, and saw the definition of some basic Clojure functions. The Clojure cheatsheet gives a comprehensive list of the core functions in the language, and is a great starting point when you have to solve a problem but don’t know what functions to use.
We’ll see a broad swath of those functions in Chapter 4: Sequences.
My thanks to Zach Tellman, Kelly Sommers, and Michael R Bernstein for reviewing drafts of this chapter.
In Chapter 3, we discovered functions as a way to abstract expressions; to rephrase a particular computation with some parts missing. We used functions to transform a single value. But what if we want to apply a function to more than one value at once?
For example, we know that (inc 2) increments the number 2. What if we wanted to increment every number in the vector [1 2 3], producing [2 3 4]?
user=> (inc [1 2 3])
ClassCastException clojure.lang.PersistentVector cannot be cast to java.lang.Number clojure.lang.Numbers.inc (Numbers.java:110)Clearly inc can only work on numbers, not on vectors. We need a different kind of tool.
Let’s think about the problem in concrete terms. We want to increment each of three elements: the first, second, and third. We know how to get an element from a sequence by using nth, so let’s start with the first number, at index 0:
So there’s the first element incremented. Now we can do the second:
And it should be straightforward to combine these into a vector…
Success! We’ve incremented each of the numbers in the list! How about a list with only two elements?
user=> (def numbers [1 2])
#'user/numbers
user=> [(inc (nth numbers 0)) (inc (nth numbers 1)) (inc (nth numbers 2))]
IndexOutOfBoundsException clojure.lang.PersistentVector.arrayFor (PersistentVector.java:107)Shoot. We tried to get the element at index 2, but couldn’t, because numbers only has indices 0 and 1. Clojure calls that “index out of bounds”.
We could just leave off the third expression in the vector; taking only elements 0 and 1. But the problem actually gets much worse, because we’d need to make this change every time we wanted to use a different sized vector. And what of a vector with 1000 elements? We’d need 1000 (inc (nth numbers …)) expressions! Down this path lies madness.
Let’s back up a bit, and try a slightly smaller problem.
What if we just incremented the first number in the vector? How would that work? We know that first finds the first element in a sequence, and rest finds all the remaining ones.
So there’s the pieces we’d need. To glue them back together, we can use a function called cons, which says “make a list beginning with the first argument, followed by all the elements in the second argument”.
OK so we can split up a sequence, increment the first part, and join them back together. Not so hard, right?
(defn inc-first [nums]
(cons (inc (first nums))
(rest nums)))
user=> (inc-first [1 2 3 4])
(2 2 3 4)Hey, there we go! First element changed. Will it work with any length list?
user=> (inc-first [5])
(6)
user=> (inc-first [])
NullPointerException clojure.lang.Numbers.ops (Numbers.java:942)Shoot. We can’t increment the first element of this empty vector, because it doesn’t have a first element.
user=> (first [])
nil
user=> (inc nil)
NullPointerException clojure.lang.Numbers.ops (Numbers.java:942)So there are really two cases for this function. If there is a first element in nums, we’ll increment it as normal. If there’s no such element, we’ll return an empty list. To express this kind of conditional behavior, we’ll use a Clojure special form called if:
user=> (doc if)
-------------------------
if
(if test then else?)
Special Form
Evaluates test. If not the singular values nil or false,
evaluates and yields then, otherwise, evaluates and yields else. If
else is not supplied it defaults to nil.
Please see http://clojure.org/special_forms#ifTo confirm our intuition:
Seems straightforward enough.
(defn inc-first [nums]
(if (first nums)
; If there's a first number, build a new list with cons
(cons (inc (first nums))
(rest nums))
; If there's no first number, just return an empty list
(list)))
user=> (inc-first [])
()
user=> (inc-first [1 2 3])
(2 2 3)Success! Now we can handle both cases: empty sequences, and sequences with things in them. Now how about incrementing that second number? Let’s stare at that code for a bit.
Hang on. That list–(rest nums)–that’s a list of numbers too. What if we… used our inc-first function on that list, to increment its first number? Then we’d have incremented both the first and the second element.
(defn inc-more [nums]
(if (first nums)
(cons (inc (first nums))
(inc-more (rest nums)))
(list)))
user=> (inc-more [1 2 3 4])
(2 3 4 5)Odd. That didn’t just increment the first two numbers. It incremented all the numbers. We fell into the complete solution entirely by accident. What happened here?
Well first we… yes, we got the number one, and incremented it. Then we stuck that onto (inc-first [2 3 4]), which got two, and incremented it. Then we stuck that two onto (inc-first [3 4]), which got three, and then we did the same for four. Only that time around, at the very end of the list, (rest [4]) would have been empty. So when we went to get the first number of the empty list, we took the second branch of the if, and returned the empty list.
Having reached the bottom of the function calls, so to speak, we zip back up the chain. We can imagine this function turning into a long string of cons calls, like so:
(cons 2 (cons 3 (cons 4 (cons 5 '()))))
(cons 2 (cons 3 (cons 4 '(5))))
(cons 2 (cons 3 '(4 5)))
(cons 2 '(3 4 5))
'(2 3 4 5)This technique is called recursion, and it is a fundamental principle in working with collections, sequences, trees, or graphs… any problem which has small parts linked together. There are two key elements in a recursive program:
Incrementing the elements of an empty list returns the empty list. This is our base case: the ground to build on. Our inductive case, also called the recurrence relation, is how we broke the problem up into incrementing the first number in the sequence, and incrementing all the numbers in the rest of the sequence. The if expression bound these two cases together into a single function; a function defined in terms of itself.
Once the initial step has been taken, every step can be taken.
This is the beauty of a recursive function; folding an unbounded stream of computation over and over, onto itself, until only a single step remains.
We set out to increment every number in a vector, but nothing in our solution actually depended on inc. It just as well could have been dec, or str, or keyword. Let’s parameterize our inc-more function to use any transformation of its elements:
(defn transform-all [f xs]
(if (first xs)
(cons (f (first xs))
(transform-all f (rest xs)))
(list)))Because we could be talking about any kind of sequence, not just numbers, we’ve named the sequence xs, and its first element x. We also take a function f as an argument, and that function will be applied to each x in turn. So not only can we increment numbers…
…but we can turn strings to keywords…
user=> (transform-all keyword ["bell" "hooks"])
(:bell :hooks)
…or wrap every element in a list:
user=> (transform-all list [:codex :book :manuscript])
((:codex) (:book) (:manuscript))In short, this function expresses a sequence in which each element is some function applied to the corresponding element in the underlying sequence. This idea is so important that it has its own name, in mathematics, Clojure, and other languages. We call it map.
You might remember maps as a datatype in Clojure, too–they’re dictionaries that relate keys to values.
The function map relates one sequence to another. The type map relates keys to values. There is a deep symmetry between the two: maps are usually sparse, and the relationships between keys and values may be arbitrarily complex. The map function, on the other hand, usually expresses the same type of relationship, applied to a series of elements in fixed order.
Recursion can do more than just map. We can use it to expand a single value into a sequence of values, each related by some function. For instance:
Our base case is x itself, followed by the sequence beginning with (f x). That sequence in turn expands to (f (f x)), and then (f (f (f x))), and so on. Each time we call expand, we count down by one using dec. Once the count is zero, the if returns nil, and evaluation stops. If we start with the number 0 and use inc as our function:
Clojure has a more general form of this function, called iterate.
Since this sequence is infinitely long, we’re using take to select only the first 10 elements. We can construct more complex sequences by using more complex functions:
Or build up strings:
iterate is extremely handy for working with infinite sequences, and has some partners in crime. repeat, for instance, constructs a sequence where every element is the same.
user=> (take 10 (repeat :hi))
(:hi :hi :hi :hi :hi :hi :hi :hi :hi :hi)
user=> (repeat 3 :echo)
(:echo :echo :echo)And its close relative repeatedly simply calls a function (f) to generate an infinite sequence of values, over and over again, without any relationship between elements. For an infinite sequence of random numbers:
user=> (rand)
0.9002678382322784
user=> (rand)
0.12375594203332863
user=> (take 3 (repeatedly rand))
(0.44442397843046755 0.33668691162169784 0.18244875487846746)Notice that calling (rand) returns a different number each time. We say that rand is an impure function, because it cannot simply be replaced by the same value every time. It does something different each time it’s called.
There’s another very handy sequence function specifically for numbers: range, which generates a sequence of numbers between two points. (range n) gives n successive integers starting at 0. (range n m) returns integers from n to m-1. (range n m step) returns integers from n to m, but separated by step.
user=> (range 5)
(0 1 2 3 4)
user=> (range 2 10)
(2 3 4 5 6 7 8 9)
user=> (range 0 100 5)
(0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95)To extend a sequence by repeating it forever, use cycle:
Given a sequence, we often want to find a related sequence. map, for instance, applies a function to each element–but has a few more tricks up its sleeve.
user=> (map (fn [n vehicle] (str "I've got " n " " vehicle "s"))
[0 200 9]
["car" "train" "kiteboard"])
("I've got 0 cars" "I've got 200 trains" "I've got 9 kiteboards")If given multiple sequences, map calls its function with one element from each sequence in turn. So the first value will be (f 0 “car”), the second (f 200 “train”), and so on. Like a zipper, map folds together corresponding elements from multiple collections. To sum three vectors, column-wise:
If one sequence is bigger than another, map stops at the end of the smaller one. We can exploit this to combine finite and infinite sequences. For example, to number the elements in a vector:
user=> (map (fn [index element] (str index ". " element))
(iterate inc 0)
["erlang" "ruby" "haskell"])
("0. erlang" "1. ruby" "2. haskell")Transforming elements together with their indices is so common that Clojure has a special function for it: map-indexed:
user=> (map-indexed (fn [index element] (str index ". " element))
["erlang" "ruby" "haskell"])
("0. erlang" "1. ruby" "2. haskell")You can also tack one sequence onto the end of another, like so:
Another way to combine two sequences is to riffle them together, using interleave.
And if you want to insert a specific element between each successive pair in a sequence, try interpose:
To reverse a sequence, use reverse.
Strings are sequences too! Each element of a string is a character, written You can rejoin those characters into a string with apply str:
user=> (apply str (reverse "woolf"))
"floow"
…and break strings up into sequences of chars with seq.
user=> (seq "sato")
(\s \a \t \o)To randomize the order of a sequence, use shuffle.
We’ve already seen take, which selects the first n elements. There’s also drop, which removes the first n elements.
user=> (range 10)
(0 1 2 3 4 5 6 7 8 9)
user=> (take 3 (range 10))
(0 1 2)
user=> (drop 3 (range 10))
(3 4 5 6 7 8 9)And for slicing apart the other end of the sequence, we have take-last and drop-last:
take-while and drop-while work just like take and drop, but use a function to decide when to cut.
In general, one can cut a sequence in twain by using split-at, and giving it a particular index. There’s also split-with, which uses a function to decide when to cut.
(split-at 4 (range 10))
[(0 1 2 3) (4 5 6 7 8 9)]
user=> (split-with number? [1 2 3 :mark 4 5 6 :mark 7])
[(1 2 3) (:mark 4 5 6 :mark 7)]Notice that because indexes start at zero, sequence functions tend to have predictable numbers of elements. (split-at 4) yields four elements in the first collection, and ensures the second collection begins at index four. (range 10) has ten elements, corresponding to the first ten indices in a sequence. (range 3 5) has two (since 5 - 3 is two) elements. These choices simplify the definition of recursive functions as well.
We can select particular elements from a sequence by applying a function. To find all positive numbers in a list, use filter:
filter looks at each element in turn, and includes it in the resulting sequence only if (f element) returns a truthy value. Its complement is remove, which only includes those elements where (f element) is false or nil.
Finally, one can group a sequence into chunks using partition, partition-all, or partition-by. For instance, one might group alternating values into pairs:
Or separate a series of numbers into negative and positive runs:
After transforming a sequence, we often want to collapse it in some way; to derive some smaller value. For instance, we might want the number of times each element appears in a sequence:
Or to group elements by some function:
user=> (pprint (group-by :first [{:first "Li" :last "Zhou"}
{:first "Sarah" :last "Lee"}
{:first "Sarah" :last "Dunn"}
{:first "Li" :last "O'Toole"}]))
{"Li" [{:last "Zhou", :first "Li"} {:last "O'Toole", :first "Li"}],
"Sarah" [{:last "Lee", :first "Sarah"} {:last "Dunn", :first "Sarah"}]}Here we’ve taken a sequence of people with first and last names, and used the :first keyword (which can act as a function!) to look up those first names. group-by used that function to produce a map of first names to lists of people–kind of like an index.
In general, we want to combine elements together in some way, using a function. Where map treated each element independently, reducing a sequence requires that we bring some information along. The most general way to collapse a sequence is reduce.
user=> (doc reduce)
-------------------------
clojure.core/reduce
([f coll] [f val coll])
f should be a function of 2 arguments. If val is not supplied,
returns the result of applying f to the first 2 items in coll, then
applying f to that result and the 3rd item, etc. If coll contains no
items, f must accept no arguments as well, and reduce returns the
result of calling f with no arguments. If coll has only 1 item, it
is returned and f is not called. If val is supplied, returns the
result of applying f to val and the first item in coll, then
applying f to that result and the 2nd item, etc. If coll contains no
items, returns val and f is not called.That’s a little complicated, so we’ll start small. We need a function, f, which combines successive elements of the sequence. (f state element) will return the state for the next invocation of f. As f moves along the sequence, it carries some changing state with it. The final state is the return value of reduce.
reduce begins by calling (+ 1 2), which yields the state 3. Then it calls (+ 3 3), which yields 6. Then (+ 6 4), which returns 10. We’ve taken a function over two elements, and used it to combine all the elements. Mathematically, we could write:
So another way to look at reduce is like sticking a function between each pair of elements. To see the reducing process in action, we can use reductions, which returns a sequence of all the intermediate states.
Oftentimes we include a default state to start with. For instance, we could start with an empty set, and add each element to it as we go along:
Reducing elements into a collection has its own name: into. We can conj [key value] vectors into a map, for instance, or build up a list:
Because elements added to a list appear at the beginning, not the end, this expression reverses the sequence. Vectors conj onto the end, so to emit the elements in order, using reduce, we might try:
Which brings up an interesting thought: this looks an awful lot like map. All that’s missing is some kind of transformation applied to each element.
(defn my-map [f coll]
(reduce (fn [output element]
(conj output (f element)))
[]
coll))
user=> (my-map inc [1 2 3 4])
[2 3 4 5]Huh. map is just a special kind of reduce. What about, say, take-while?
(defn my-take-while [f coll]
(reduce (fn [out elem]
(if (f elem)
(conj out elem)
(reduced out)))
[]
coll))We’re using a special function here, reduced, to indicate that we’ve completed our reduction early and can skip the rest of the sequence.
reduce really is the uberfunction over sequences. Almost any operation on a sequence can be expressed in terms of a reduce–though for various reasons, many of the Clojure sequence functions are not written this way. For instance, take-while is actually defined like so:
user=> (source take-while)
(defn take-while
"Returns a lazy sequence of successive items from coll while
(pred item) returns true. pred must be free of side-effects."
{:added "1.0"
:static true}
[pred coll]
(lazy-seq
(when-let [s (seq coll)]
(when (pred (first s))
(cons (first s) (take-while pred (rest s)))))))There’s a few new pieces here, but the structure is essentially the same as our initial attempt at writing map. When the predicate matches the first element, cons the first element onto take-while, applied to the rest of the sequence. That lazy-seq construct allows Clojure to compute this sequence as required, instead of right away. It defers execution to a later time.
Most of Clojure’s sequence functions are lazy. They don’t do anything until needed. For instance, we can increment every number from zero to infinity:
That function returned immediately. Because it hasn’t done any work yet, we say the sequence is unrealized. It doesn’t increment any numbers at all until we ask for them:
Lazy sequences also remember their contents, once evaluated, for faster access.
We’ve seen how recursion generalizes a function over one thing into a function over many things, and discovered a rich landscape of recursive functions over sequences. Now let’s use our knowledge of sequences to solve a more complex problem: find the sum of the products of consecutive pairs of the first 1000 odd integers.
First, we’ll need the integers. We can start with 0, and work our way up to infinity. To save time printing an infinite number of integers, we’ll start with just the first 10.
Now we need to find only the ones which are odd. Remember, filter pares down a sequence to only those elements which pass a test.
For consecutive pairs, we want to take [1 3 5 7 …] and find a sequence like ([1 3] [3 5] [5 7] …). That sounds like a job for partition:
Not quite right–this gave us non-overlapping pairs, but we wanted overlapping ones too. A quick check of (doc partition) reveals the step parameter:
Now we need to find the product for each pair. Given a pair, multiply the two pieces together… yes, that sounds like map:
user=> (take 3 (map (fn [pair] (* (first pair) (second pair)))
(partition 2 1 (filter odd? (iterate inc 0)))))
(3 15 35)Getting a bit unwieldy, isn’t it? Only one final step: sum all those products. We’ll adjust the take to include the first 1000, not the first 3, elements.
user=> (reduce +
(take 1000
(map (fn [pair] (* (first pair) (second pair)))
(partition 2 1
(filter odd?
(iterate inc 0)))))
1335333000The sum of the first thousand products of consecutive pairs of the odd integers starting at 0. See how each part leads to the next? This expression looks a lot like the way we phrased the problem in English–but both English and Lisp expressions are sort of backwards, in a way. The part that happens first appears deepest, last, in the expression. In a chain of reasoning like this, it’d be nicer to write it in order.
user=> (->> 0
(iterate inc)
(filter odd?)
(partition 2 1)
(map (fn [pair]
(* (first pair) (second pair))))
(take 1000)
(reduce +))
1335333000Much easier to read: now everything flows in order, from top to bottom, and we’ve flattened out the deeply nested expressions into a single level. This is how object-oriented languages structure their expressions: as a chain of function invocations, each acting on the previous value.
But how is this possible? Which expression gets evaluated first? (take 1000) isn’t even a valid call–where’s its second argument? How are any of these forms evaluated?
What kind of arcane function is ->>?
All these mysteries, and more, in Chapter 5: Macros.
In Chapter 1, I asserted that the grammar of Lisp is uniform: every expression is a list, beginning with a verb, and followed by some arguments. Evaluation proceeds from left to right, and every element of the list must be evaluated before evaluating the list itself. Yet we just saw, at the end of Sequences, an expression which seemed to violate these rules.
Clearly, this is not the whole story.
There is another phase to evaluating an expression; one which takes place before the rules we’ve followed so far. That process is called macro-expansion. During macro-expansion, the code itself is restructured according to some set of rules–rules which you, the programmer, can define.
(defmacro ignore
"Cancels the evaluation of an expression, returning nil instead."
[expr]
nil)
user=> (ignore (+ 1 2))
nildefmacro looks a lot like defn: it has a name, an optional documentation string, an argument vector, and a body–in this case, just nil. In this case, it looks like it simply ignored the expr (+ 1 2) and returned nil–but it’s actually deeper than that. (+ 1 2) was never evaluated at all.
def should have defined x to be 2 no matter what–but that never happened. At macroexpansion time, the expression (ignore (+ 1 2)) was replaced by the expression nil, which was then evaluated to nil. Where functions rewrite values, macros rewrite code.
To see these different layers in play, let’s try a macro which reverses the order of arguments to a function.
This macro, named rev, takes one mandatory argument: a function. Then it takes any number of arguments, which are collected in the list args. It constructs a new list, starting with the function, and followed by the arguments, in reverse order.
First, we macro-expand:
So the rev macro took str as the function, and “hi” and (+ 1 2) as the arguments; then constructed a new list with the same function, but the arguments reversed. When we evaluate that expression, we get:
macroexpand takes an expression and returns that expression with all macros expanded. eval takes an expression and evaluates it. When you type an unquoted expression into the REPL, Clojure macroexpands, then evaluates. Two stages–the first transforming code, the second transforming values.
Some languages have a metalanguage: a language for extending the language itself. In C, for example, macros are implemented by the C preprocessor, which has its own syntax for defining expressions, matching patterns in the source code’s text, and replacing that text with other text. But that preprocessor is not C–it is a separate language entirely, with special limitations. In Clojure, the metalanguage is Clojure itself–the full power of the language is available to restructure programs. This is called a procedural macro system. Some Lisps, like Scheme, use a macro system based on templating expressions, and still others use more powerful models like f-expressions–but that’s a discussion for a later time.
There is another key difference between Lisp macros and many other macro systems: in Lisp, the macros operate on expressions: the data structure of the code itself. Because Lisp code is written explicitly as a data structure, a tree made out of lists, this transformation is natural. You can see the structure of the code, which makes it easy to reason about its transformation. In the C preprocessor, macros operate only on text: there is no understanding of the underlying syntax. Even in languages like Scala which have syntactic macros, the fact that the code looks nothing like the syntax tree makes it cumbersome to truly restructure expressions.
When people say that Lisp’s syntax is “more elegant”, or “more beautiful”, or “simpler”, this is part of what they they mean. By choosing to represent the program directly as a a data structure, we make it much easier to define complex transformations of code itself.
What kind of transformations are best expressed with macros?
Most languages encode special syntactic forms–things like “define a function”, “call a function”, “define a local variable”, “if this, then that”, and so on. In Clojure, these are called special forms. if is a special form, for instance. Its definition is built into the language core itself; it cannot be reduced into smaller parts.
Or in Javascript:
In Javascript, Ruby, and many other languages, these special forms are fixed. You cannot define your own syntax. For instance, one cannot define or in a language like JS or Ruby: it must be defined for you by the language author.
In Clojure, or is just a macro.
user=> (source or)
(defmacro or
"Evaluates exprs one at a time, from left to right. If a form
returns a logical true value, or returns that value and doesn't
evaluate any of the other expressions, otherwise it returns the
value of the last expression. (or) returns nil."
{:added "1.0"}
([] nil)
([x] x)
([x & next]
`(let [or# ~x]
(if or# or# (or ~@next)))))
nilThat ` operator–that’s called syntax-quote. It works just like regular quote–preventing evaluation of the following list–but with a twist: we can escape the quoting rule and substitute in regularly evaluated expressions using unquote (~), and unquote-splice (~@). Think of a syntax-quoted expression like a template for code, with some parts filled in by evaluated forms.
user=> (let [x 2] `(inc x))
(clojure.core/inc user/x)
user=> (let [x 2] `(inc ~x))
(clojure.core/inc 2)See the difference? ~x substitutes the value of x, instead of using x as an unevaluated symbol. This code is essentially just shorthand for something like
… where we explicitly constructed a new list with the quoted symbol ’inc and the current value of x. Syntax quote just makes it easier to read the code, since the quoted and expanded expressions have similar shapes.
The ~@ unquote splice works just like ~, except it explodes a list into multiple expressions in the resulting form:
~@ is particularly useful when a function or macro takes an arbitrary number of arguments. In the definition of or, it’s used to expand (or a b c) recursively.
user=> (pprint (macroexpand '(or a b c d)))
(let*
[or__3943__auto__ a]
(if or__3943__auto__ or__3943__auto__ (clojure.core/or b c d)))We’re using pprint (for “pretty print”) to make this expression easier to read. (or a b c d) is defined in terms of if: if the first element is truthy we return it; otherwise we evaluate (or b c d) instead, and so on.
The final piece of the puzzle here is that weirdly named symbol: or__3943auto. That variable was automatically generated by Clojure, to prevent conflicts with an existing variable name. Because macros rewrite code, they have to be careful not to interfere with local variables, or it could get very confusing. Whenever we need a new variable in a macro, we use gensym to generate a new symbol.
Each symbol is different! If we tack on a # to the end of a symbol in a syntax-quoted expression, it’ll be expanded to a particular gensym:
Note that you can always escape this safety feature if you want to override local variables. That’s called symbol capture, or an anaphoric or unhygenic macro. To override local symbols, just use ~’foo instead of foo#.
With all the pieces on the board, let’s compare the or macro and its expansion:
(defmacro or
"Evaluates exprs one at a time, from left to right. If a form
returns a logical true value, or returns that value and doesn't
evaluate any of the other expressions, otherwise it returns the
value of the last expression. (or) returns nil."
{:added "1.0"}
([] nil)
([x] x)
([x & next]
`(let [or# ~x]
(if or# or# (or ~@next)))))
user=> (pprint (clojure.walk/macroexpand-all
'(or (mossy? stone) (cool? stone) (wet? stone))))
(let*
[or__3943__auto__ (mossy? stone)]
(if
or__3943__auto__
or__3943__auto__
(let*
[or__3943__auto__ (cool? stone)]
(if or__3943__auto__ or__3943__auto__ (wet? stone)))))See how the macro’s syntax-quoted (let … has the same shape as the resulting code? or# is expanded to a variable named or__3943auto, which is bound to the expression (mossy? stone). If that variable is truthy, we return it. Otherwise, we (and here’s the recursive part) rebind or__3943__auto__ to (cool? stone) and try again. If that fails, we fall back to evaluating (wet? stone)–thanks to the base case, the single-argument form of the or macro.
We’ve seen that or is a macro written in terms of the special form if–and because of the way the macro is structured, it does not obey the normal execution order. In (or a b c), only a is evaluated first–then, only if it is false or nil, do we evaluate b. This is called short-circuiting, and it works for and as well.
Changing the order of evaluation in a language is called control flow, and lets programs make decisions based on varying circumstances. We’ve already seen if:
if takes a predicate and two expressions, and only evaluates one of them, depending on whether the predicate evaluates to a truthy or falsey value. Sometimes you want to evaluate more than one expression in order. For this, we have do.
user=> (if (pos? -5)
(prn "-5 is positive")
(do
(prn "-5 is negative")
(prn "Who would have thought?")))
"-5 is negative"
"Who would have thought?"
nilprn is a function which has a side effect: it prints a message to the screen, and returns nil. We wanted to print two messages, but if only takes a single expression per branch–so in our false branch, we used do to wrap up two prns into a single expression, and evaluate them in order. do returns the value of the final expression, which happens to be nil here.
When you only want to take one branch of an if, you can use when:
user=> (when false
(prn :hi)
(prn :there))
nil
user=> (when true
(prn :hi)
(prn :there))
:hi
:there
nilBecause there is only one path to take, when takes any number of expressions, and evaluates them only when the predicate is truthy. If the predicate evaluates to nil or false, when does not evaluate its body, and returns nil.
Both when and if have complementary forms, when-not and if-not, which simply invert the sense of their predicate.
Often, you want to perform some operation, and if it’s truthy, re-use that value without recomputing it. For this, we have when-let and if-let. These work just like when and let combined.
while evaluates an expression so long as its predicate is truthy. This is generally useful only for side effects, like prn or def; things that change the state of the world.
cond (for “conditional”) is like a multiheaded if: it takes any number of test/expression pairs, and tries each test in turn. The first test which evaluates truthy causes the following expression to be evaluated; then cond returns that expression’s value.
user=> (cond
#_=> (= 2 5) :nope
#_=> (= 3 3) :yep
#_=> (= 5 5) :cant-get-here
#_=> :else :a-default-value)
:yepIf you find yourself making several similar decisions based on a value, try condp, for “cond with predicate”. For instance, we might categorize a number based on some ranges:
(defn category
"Determines the Saffir-Simpson category of a hurricane, by wind speed in meters/sec"
[wind-speed]
(condp <= wind-speed
70 :F5
58 :F4
49 :F3
42 :F2
:F1)) ; Default value
user=> (category 10)
:F1
user=> (category 50)
:F3
user=> (category 100)
:F5condp generates code which combines the predicate <= with each number, and the value of wind-speed, like so:
(if (<= 70 wind-speed) :F5
(if (<= 58 wind-speed) :F4
(if (<= 49 wind-speed) :F3
(if (<= 42 wind-speed) :F2
:F1))))Specialized macros like condp are less commonly used than if or when, but they still play an important role in simplifying repeated code. They clarify the meaning of complex expressions, making them easier to read and maintain.
Finally, there’s case, which works a little bit like a map of keys to values–only the values are code, to be evaluated. You can think of case like (condp = …), trying to match an expression to a particular branch for which it is equal.
(defn with-tax
"Computes the total cost, with tax, of a purchase in the given state."
[state subtotal]
(case state
:WA (* 1.065 subtotal)
:OR subtotal
:CA (* 1.075 subtotal)
; ... 48 other states ...
subtotal)) ; a default caseUnlike cond and condp, case does not evaluate its tests in order. It jumps immediately to the matching expression. This makes case much faster when there are many branches to take–at the cost of reduced generality.
Previously, we defined recursive functions by having those functions call themselves explicitly.
(defn sum [numbers]
(if-let [n (first numbers)]
(+ n (sum (rest numbers)))
0))
user=> (sum (range 10))
45But this approach breaks down when we have the function call itself deeply, over and over again.
Every time you call a function, the arguments for that function are stored in memory, in a region called the stack. They remain there for as long as the function is being called–including any deeper function calls.
In order to add n and (sum (rest numbers)), we have to call sum first–while holding onto the memory for n and numbers. We can’t re-use that memory until every single recursive call has completed. Clojure complains, after tens of thousands of stack frames are in use, that it has run out of space in the stack and can allocate no more.
But consider this variation on sum:
(defn sum
([numbers]
(sum 0 numbers))
([subtotal numbers]
(if-let [n (first numbers)]
(recur (+ subtotal n) (rest numbers))
subtotal)))
user=> (sum (range 100000))
4999950000We’ve added an additional parameter to the function. In its two-argument form, sum now takes an accumulator, subtotal, which represents the count so far. In addition, recur has taken the place of sum. Notice, however, that the final expression to be evaluated is not +, but sum (viz recur) itself. We don’t need to hang on to any of the variables in this function any more, because the final return value won’t depend on them. recur hints to the Clojure compiler that we don’t need to hold on to the stack, and can re-use that space for other things. This is called a tail-recursive function, and it requires only a single stack frame no matter how deep the recursive calls go.
Use recur wherever possible. It requires much less memory and is much faster than the explicit recursion.
You can also use recur within the context of the loop macro, where it acts just like an unnamed recursive function with initial values provided. Think of it, perhaps, like a recursive let.
user=> (loop [i 0
nums []]
(if (< 10 i)
nums
(recur (inc i) (conj nums i))))
[0 1 2 3 4 5 6 7 8 9 10]In chapter 4 we mentioned that most of the sequences in Clojure, like map, filter, iterate, repeatedly, and so on, were lazy: they did not evaluate any of their elements until required. This too is provided by a macro, called lazy-seq.
This sequence does not terminate; it is infinitely recursive. Yet it returned instantaneously. lazy-seq interrupted that recursion and restructured it into a sequence which constructs elements only when they are requested.
When using lazy-seq and its partner lazy-cat, you don’t have to use recur–or even be tail-recursive. The macros interrupt each level of recursion, preventing stack overflows.
You can also delay evaluation of some expressions until later, using delay and deref.
user=> (def x (delay
(prn "computing a really big number!")
(last (take 10000000 (iterate inc 0)))))
#'user/x ; Did nothing, returned immediately
user=> (deref x)
"computing a really big number!" ; Now we have to wait!
9999999Combining recursion and laziness is the list comprehension macro, for. In its simplest form, for works like map:
Like let, for takes a vector of bindings. Unlike let, however, for binds its variables to each possible combination of elements in their corresponding sequences.
“For each x in the sequence [1 2 3], and for each y in the sequence [:a :b], find all [x y] pairs.” Note that the rightmost variable y iterates the fastest.
Like most sequence functions, the for macro yields lazy sequences. You can filter them with take, filter, et al like any other sequence. Or you can use :while to tell for when to stop, or :when to filter out combinations of elements.
(for [x (range 5)
y (range 5)
:when (and (even? x) (odd? y))]
[x y])
([0 1] [0 3] [2 1] [2 3] [4 1] [4 3])Clojure includes a rich smörgåsbord of control-flow constructs; we’ll meet new ones throughout the book.
Sometimes you want to thread a computation through several expressions, like a chain. Object-oriented languages like Ruby or Java are well-suited to this style:
Start with the range 0 to 10, then call select on that range, with the function odd?. Finally, take that sequence of numbers, and reduce it with the + function.
The Clojure threading macros do the same by restructuring a sequence of expressions, inserting each expression as the first (or final) argument in the next expression.
user=> (pprint (clojure.walk/macroexpand-all
'(->> (range 10) (filter odd?) (reduce +))))
(reduce + (filter odd? (range 10)))
user=> (->> (range 10) (filter odd?) (reduce +))
25->> took (range 10) and inserted it at the end of (filter odd?), forming (filter odd? (range 10)). Then it took that expression and inserted it at the end of (reduce +). In essence, ->> flattens and reverses a nested chain of operations.
->, by contrast, inserts each form in as the first argument in the following expression.
user=> (pprint (clojure.walk/macroexpand-all
'(-> {:proton :fermion} (assoc :photon :boson) (assoc :neutrino :fermion))))
(assoc (assoc {:proton :fermion} :photon :boson) :neutrino :fermion)
user=> (-> {:proton :fermion}
(assoc :photon :boson)
(assoc :neutrino :fermion))
{:neutrino :fermion, :photon :boson, :proton :fermion}Clojure isn’t just function-oriented in its syntax; it can be object-oriented, and stack-oriented, and array-oriented, and so on–and mix all of these styles freely, in a controlled way. If you don’t like the way the language fits a certain problem, you can write a macro which defines a new language, specifically for that subproblem.
cond, condp and case, for example, express a language for branching based on predicates. ->, ->>, and doto express object-oriented and other expression-chaining languages.
We’ll see a plethora of macros, from simple to complex, through the course of this book. Each one shares the common pattern of simplifying code; reducing tangled or verbose expressions into something more concise, more meaningful, better suited to the problem at hand.
While it’s important to be aware of the purpose and behavior of the macro system, you don’t need to write your own macros to be productive with Clojure. For now, you’ll be just fine writing code which uses the existing macros in the language. When you do need to delve deeper, come back to this guide and experiment. It’ll take some time to sink in.
First, know that writing macros is tricky, even for experts. It requires you to think at two levels simultaneously, and to be mindful of the distinction between expression and underlying evaluation. Writing a macro is essentially extending the language, the compiler, the syntax and evaluation model of Clojure, by restructuring arbitrary expressions into ones the evaluation system understands. This is hard, and it’ll take practice to get used to.
In addition, Clojure macros come with some important restrictions. Because they’re expanded prior to evaluation, macros are invisible to functions. They can’t be composed functionally–you can’t (map or …), for instance.
So in general, if you can solve a problem without writing a macro, don’t write one. It’ll be easier to debug, easier to understand, and easier to compose later. Only reach for macros when you need new syntax, or when performance demands the code be transformed at compile time.
When you do write a macro, consider its scope carefully. Keep the transformation simple; and do as much in normal functions as possible. Provide an escape hatch where possible, by doing most of the work in a function, and writing a small wrapper macro which calls that function. Finally, remember the distinction between code and what that code evaluates to. Use let whenever a value is to be re-used, to prevent it being evaluated twice by accident.
For a deeper exploration of Clojure macros in a real-world application, try Language Power.
In Chapter 4, deeply nested expressions led to the desire for a simpler, more direct expression of a chain of sequence operations. We learned that the Clojure compiler first expands expressions before evaluating them, using macros–special functions which take code and return other code. We used macros to define the short-circuiting or operator, and followed that with a tour of basic control flow, recursion, laziness, list comprehensions, and chained expressions. Finally, we learned a bit about when and how to write our own macros.
Throughout this chapter we’ve brushed against the idea of side effects: things which change the outside world. We might change a var with def, or print a message to the screen with prn. Real languages must model a continually shifting universe, which leads us to Chapter Six: Side effects and state.
+, -, *, or / to force the use of ratios instead of floating-point numbers. (* 2452.45 100) returns 245244.99999999997, but (exact (* 2452.45 100)) should return 245245N.Most programs encompass change. People grow up, leave town, fall in love, and take new names. Engines burn through fuel while their parts wear out, and new ones are swapped in. Forests burn down and their logs become nurseries for new trees. Despite these changes, we say “She’s still Nguyen”, “That’s my motorcycle”, “The same woods I hiked through as a child.”
Identity is a skein we lay across the world of immutable facts; a single entity which encompasses change. In programming, identities unify different values over time. Identity types are mutable references to immutable values.
In this chapter, we’ll move from immutable references to complex concurrent transactions. In the process we’ll get a taste of concurrency and parallelism, which will motivate the use of more sophisticated identity types. These are not easy concepts, so don’t get discouraged. You don’t have to understand this chapter fully to be a productive programmer, but I do want to hint at why things work this way. As you work with state more, these concepts will solidify.
The references we’ve used in let bindings and function arguments are immutable: they never change.
The expression (inc x) did not alter x: x remained 1. The same applies to strings, lists, vectors, maps, sets, and most everything else in Clojure:
user=> (let [x [1 2]]
(prn (conj x :a))
(prn (conj x :b)))
[1 2 :a]
[1 2 :b]Immutability also extends to let bindings, function arguments, and other symbols. Functions remember the values of those symbols at the time the function was constructed.
(defn present
[gift]
(fn [] gift))
user=> (def green-box (present "clockwork beetle"))
#'user/green-box
user=> (def red-box (present "plush tiger"))
#'user/red-box
user=> (red-box)
"plush tiger"
user=> (green-box)
"clockwork beetle"The present function creates a new function. That function takes no arguments, and always returns the gift. Which gift? Because gift is not an argument to the inner function, it refers to the value from the outer function body. When we packaged up the red and green boxes, the functions we created carried with them a memory of the gift symbol’s value.
This is called closing over the gift variable; the inner function is sometimes called a closure. In Clojure, new functions close over all variables except their arguments–the arguments, of course, will be provided when the function is invoked.
Because functions close over their arguments, they can be used to defer evaluation of expressions. That’s how we introduced functions originally–like let expressions, but with a number (maybe zero!) of symbols missing, to be filled in at a later time.
user=> (do (prn "Adding") (+ 1 2))
"Adding"
3
user=> (def later (fn [] (prn "Adding") (+ 1 2)))
#'user/later
user=> (later)
"Adding"
3Evaluating (def later …) did not evaluate the expressions in the function body. Only when we invoked the function later did Clojure print “Adding” to the screen, and return 3. This is the basis of concurrency: evaluating expressions outside their normal, sequential order.
This pattern of deferring evaluation is so common that there’s a standard macro for it, called delay:
user=> (def later (delay (prn "Adding") (+ 1 2)))
#'user/later
user=> later
#<Delay@2dd31aac: :pending>
user=> (deref later)
"Adding"
3Instead of a function, delay creates a special type of Delay object: an identity which refers to expressions which should be evaluated later. We extract, or dereference, the value of that identity with deref. Delays follow the same rules as functions, closing over lexical scope–because delay actually macroexpands into an anonymous function.
user=> (source delay)
(defmacro delay
"Takes a body of expressions and yields a Delay object that will
invoke the body only the first time it is forced (with force or deref/@), and
will cache the result and return it on all subsequent force
calls. See also - realized?"
{:added "1.0"}
[& body]
(list 'new 'clojure.lang.Delay (list* `^{:once true} fn* [] body)))Why the Delay object instead of a plain old function? Because unlike function invocation, delays only evaluate their expressions once. They remember their value, after the first evaluation, and return it for every successive deref.
By the way, there’s a shortcut for (deref something): the wormhole operator @:
Remember how map returned a sequence immediately, but didn’t actually perform any computation until we asked for elements? That’s called lazy evaluation. Because delays are lazy, we can avoid doing expensive operations until they’re really needed. Like an IOU, we use delays when we aren’t ready to do something just yet, but when someone calls in the favor, we’ll make sure it happens.
What if we wanted to opportunistically defer computation? Modern computers have multiple cores, and operating systems let us share a core between two tasks. It would be great if we could use that multitasking ability to say, “I don’t need the result of evaluating these expressions yet, but I’d like it later. Could you start working on it in the meantime?”
Enter the future: a delay which is evaluated in parallel. Like delays, futures return immediately, and give us an identity which will point to the value of the last expression in the future–in this case, the value of (+ 1 2).
Notice how the future printed “hi” right away. That’s because futures are evaluated in a new thread. On multicore computers, two threads can run in parallel, on different cores the same time. When there are more threads than cores, the cores trade off running different threads. Both parallel and non-parallel evaluation of threads are concurrent because expressions from different threads can be evaluated out of order.
Five threads running at once. Notice that the thread printing 1 didn’t even get to move to a new line before 4 showed up–then both threads wrote new lines at the same time. There are techniques to control this concurrent execution so that things happen in some well-defined sequence, like agents and locks, but we’ll discuss those later.
Just like delays, we can deref a future as many times as we want, and the expressions are only evaluated once.
Futures are the most generic parallel construct in Clojure. You can use futures to do CPU-intensive computation faster, to wait for multiple network requests to complete at once, or to run housekeeping code periodically.
Delays defer evaluation, and futures parallelize it. What if we wanted to defer something we don’t even have yet? To hand someone an empty box and, later, before they open it, sneak in and replacing its contents with an actual gift? Surely I’m not the only one who does birthday presents this way.
This box is pending a value. Like futures and delays, if we try to open it, we’ll get stuck and have to wait for something to appear inside:
But unlike futures and delays, this box won’t be filled automatically. Hold the Control key and hit c to give up on trying to open that package. Nobody else is in this REPL, so we’ll have to buy our own presents.
user=> (deliver box :live-scorpions!)
#<core$promise$reify__6310@1d7762e: :live-scorpions!>
user=> (deref box)
:live-scorpions!Wow, that’s a terrible gift. But at least there’s something there: when we dereference the box, it opens immediately and live scorpions skitter out. Can we get a do-over? Let’s try a nicer gift.
Like delays and futures, there’s no going back on our promises. Once delivered, a promise always refers to the same value. This is a simple identity type: we can set it to a value once, and read it as many times as we want. promise is also a concurrency primitive: it guarantees that any attempt to read the value will wait until the value has been written. We can use promises to synchronize a program which is being evaluated concurrently–for instance, this simple card game:
user=> (def card (promise))
#'user/card
user=> (def dealer (future
(Thread/sleep 5000)
(deliver card [(inc (rand-int 13))
(rand-nth [:clubs :spades :hearts :diamonds])])))
#'user/dealer
user=> (deref card)
[5 :diamonds]In this program, we set up a dealer thread which waits for five seconds (5000 milliseconds), then delivers a random card. While the dealer is sleeping, we try to deref our card–and have to wait until the five seconds are up. Synchronization and identity in one package.
Where delays are lazy, and futures are parallel, promises are concurrent without specifying how the evaluation occurs. We control exactly when and how the value is delivered. You can think of both delays and futures as being built atop promises, in a way.
So far the identities we’ve discussed have referred (eventually) to a single value, but the real world needs names that refer to different values at different points in time. For this, we use vars.
We’ve touched on vars before–they’re transparent mutable references. Each var has a value associated with it, and that value can change over time. When a var is evaluated, it is replaced by its present value transparently–everywhere in the program.
user=> (def x :mouse)
#'user/x
user=> (def box (fn [] x))
#'user/box
user=> (box)
:mouse
user=> (def x :cat)
#'user/x
user=> (box)
:catThe box function closed over x–but calling (box) returned different results depending on the current value of x. Even though the var x remained unchanged throughout this example, the value associated with that var did change!
Using mutable vars allows us to write programs which we can redefine as we go along.
user=> (defn decouple [glider]
#_=> (prn "bolts released"))
#'user/decouple
user=> (defn launch [glider]
#_=> (decouple glider)
#_=> (prn glider "away!"))
#'user/launch
user=> (launch "albatross")
"bolts released"
"albatross" "away!"
nil
user=> (defn decouple [glider]
#_=> (prn "tether released"))
#'user/decouple
user=> (launch "albatross")
"tether released"
"albatross" "away!"A reference which is the same everywhere is called a global variable, or simply a global. But vars have an additional trick up their sleeve: with a dynamic var, we can override their value only within the scope of a particular function call, and nowhere else.
^:dynamic tells Clojure that this var can be overridden in one particular scope. By convention, dynamic variables are named with asterisks around them–this reminds us, as programmers, that they are likely to change. Next, we define a function that uses that dynamic var:
Note that cut closes over the var board, but not the value :maple. Every time the function is invoked, it looks up the current value of board.
user=> (cut)
"sawing through" :maple
nil
user=> (binding [*board* :cedar] (cut))
"sawing through" :cedar
nil
user=> (cut)
"sawing through" :mapleLike let, the binding macro assigns a value to a name–but where fn and let create immutable lexical scope, binding creates dynamic scope. The difference? Lexical scope is constrained to the literal text of the fn or let expression–but dynamic scope propagates through function calls.
Within the binding expression, and in every function called from that expression, and every function called from those functions, and so on, board has the value :cedar. Outside the binding expression, the value is still :maple. This safety property holds even when the program is executed in multiple threads: only the thread which evaluated the binding expression uses that value. Other threads are unaffected.
While we use def all the time in the REPL, in real programs you should only mutate vars sparingly. They’re intended for naming functions, important bits of global data, and for tracking the environment of a program–like where to print messages with prn, which database to talk to, and so on. Using vars for mutable program state is a recipe for disaster, as we’re about to see.
Vars can be read, set, and dynamically bound–but they aren’t easy to evolve. Imagine building up a set of integers:
user=> (def xs #{})
#'user/xs
user=> (dotimes [i 10] (def xs (conj xs i)))
user=> xs
#{0 1 2 3 4 5 6 7 8 9}For each number from 0 to 9, we take the current set of numbers xs, add a particular number i to that set, and redefine xs as the result. This is a common idiom in imperative language like C, Ruby, Javascript, or Java–all variables are mutable by default.
It seems straightforward enough, but there are serious problems lurking here. Specifically, this program is not thread safe.
user=> (def xs #{})
user=> (dotimes [i 10] (future (def xs (conj xs i))))
#'user/xs
nil
user=> xs
#{1 4 5 7}This program runs 10 threads in parallel, and each reads the current value of xs, adds its particular number, and defines xs to be that new set of numbers. This read-modify-update process assumed that all updates would be consecutive–not concurrent. When we allowed the program to do two read-modify-updates at the same time, updates were lost.
This interleaving of operations allowed the number 2 to slip through the cracks. We need something stronger–an identity which supports safe transformation from one state to another. Enter atoms.
The initial value of this atom is #{}. Unlike vars, atoms are not transparent. When evaluated, they don’t return their underlying values–but notice that when printed, the current value is hiding inside. To get the current value out of an atom, we have to use deref or @.
Like vars, atoms can be set to a particular value–but instead of def, we use reset!. The exclamation point (sometimes called a bang) is there to remind us that this function modifies the state of its arguments–in this case, changing the value of the atom.
Unlike vars, atoms can be safely updated using swap!. swap! uses a pure function which takes the current value of the atom and returns a new value. Under the hood, Clojure does some tricks to ensure that these updates are linearizable, which means:
The first swap! reads the value 0, calls (inc 0) to obtain 1, and writes 1 back to the atom. Each call to swap! returns the value that was just written.
We can pass additional arguments to the function swap! calls. For instance, (swap! x + 5 6) will call (+ x 5 6) to find the new value. Now we have the tools to correct our parallel program from earlier:
user=> (def xs (atom #{}))
#'user/xs
user=> (dotimes [i 10] (future (swap! xs conj i)))
nil
user=> @xs
#{0 1 2 3 4 5 6 7 8 9}Note that the function we use to update an atom must be pure–must not mutate any state–because when resolving conflicts between multiple threads, Clojure might need to call the update function more than once. Clojure’s reliance on immutable datatypes, immutable variables, and pure functions enables this approach to linearizable mutability. Languages which emphasize mutable datatypes need to use other constructs.
Atoms are the workhorse of Clojure state. They’re lightweight, safe, fast, and flexible. You can use atoms with any immutable datatype–for instance, a map to track complex state. Reach for an atom whenever you want to update a single thing over time.
Atoms are a great way to represent state, but they are only linearizable individually. Updates to an atom aren’t well-ordered with respect to other atoms, so if we try to update more than one atom at once, we could see the same kinds of bugs that we did with vars.
For multi-identity updates, we need a stronger safety property than single-atom linearizability. We want serializability: a global order. For this, Clojure has an identity type called a Ref.
Like all identity types, refs are dereferencable:
But where atoms are updated individually with swap!, refs are updated in groups using dosync transactions. Just as we reset! an atom, we can set refs to new values using ref-set–but unlike atoms, we can change more than one ref at once.
user=> (def x (ref 0))
user=> (def y (ref 0))
user=> (dosync
(ref-set x 1)
(ref-set y 2))
2
user=> [@x @y]
[1 2]The equivalent of swap!, for a ref, is alter:
user=> (def x (ref 1))
user=> (def y (ref 2))
user=> (dosync
(alter x + 2)
(alter y inc))
3
user=> [@x @y]
[3 3]All alter operations within a dosync take place atomically–their effects are never interleaved with other transactions. If it’s OK for an operation to take place out of order, you can use commute instead of alter for a performance boost:
These updates are not guaranteed to take place in the same order–but if all our transactions are equivalent, we can relax the ordering constraints. x + 2 + 3 is equal to x + 3 + 2, so we can do the additions in either order. That’s what commutative means: the same result from all orders. It’s a weaker, but faster kind of safety property.
Finally, if you want to read a value from one ref and use it to update another, use ensure instead of deref to perform a strongly consistent read–one which is guaranteed to take place in the same logical order as the dosync transaction itself. To add y’s current value to x, use:
Refs are a powerful construct, and make it easier to write complex transactional logic safely. However, that safety comes at a cost: refs are typically an order of magnitude slower to update than atoms.
Use refs only where you need to update multiple pieces of state independently–specifically, where different transactions need to work with distinct but partly overlapping pieces of state. If there’s no overlap between updates, use distinct atoms. If all operations update the same identities, use a single atom to hold a map of the system’s state. If a system requires complex interlocking state spread throughput the program–that’s when to reach for refs.
We moved beyond immutable programs into the world of changing state–and discovered the challenges of concurrency and parallelism. Where symbols provide immutable and transparent names for values objects, Vars provide mutable transparent names. We also saw a host of anonymous identity types for different purposes: delays for lazy evaluation, futures for parallel evaluation, and promises for arbitrary handoff of a value. Updates to vars are unsafe, so atoms and refs provide linearizable and serializable identities where transformations are safe.
Where reading a symbol or var is transparent–they evaluate directly to their current values–reading these new identity types requires the use of deref. Delays, futures, and promises block: deref must wait until the value is ready. This allows synchronization of concurrent threads. Atoms and refs, by contrast, can be read immediately at any time–but updating their values should occur within a swap! or dosync transaction, respectively.
| Type | Mutability | Reads | Updates | Evaluation | Scope |
|---|---|---|---|---|---|
| Symbol | Immutable | Transparent | Lexical | ||
| Var | Mutable | Transparent | Unrestricted | Global/Dynamic | |
| Delay | Mutable | Blocking | Once only | Lazy | |
| Future | Mutable | Blocking | Once only | Parallel | |
| Promise | Mutable | Blocking | Once only | ||
| Atom | Mutable | Nonblocking | Linearizable | ||
| Ref | Mutable | Nonblocking | Serializable |
State is undoubtedly the hardest part of programming, and this chapter probably felt overwhelming! On the other hand, we’re now equipped to solve serious problems. We’ll take a break to apply what we’ve learned through practical examples, in Chapter Seven: Logistics.
Finding the sum of the first 10000000 numbers takes about 1 second on my machine:
user=> (defn sum [start end] (reduce + (range start end)))
user=> (time (sum 0 1e7))
"Elapsed time: 1001.295323 msecs"
49999995000000And the sum will be a ref as well:
Write a function which, in a dosync transaction, removes the first number in work and adds it to sum. Then, in two futures, call that function over and over again until there’s no work left. Verify that @sum is 4999950000. Experiment with different combinations of alter and commute–if both are correct, is one faster? Does using deref instead of ensure change the result?
Previously, we covered state and mutability.
Up until now, we’ve been programming primarily at the REPL. However, the REPL is a limited tool. While it lets us explore a problem interactively, that interactivity comes at a cost: changing an expression requires retyping the entire thing, editing multi-line expressions is awkward, and our work vanishes when we restart the REPL–so we can’t share our programs with others, or run them again later. Moreover, programs in the REPL are hard to organize. To solve large problems, we need a way of writing programs durably–so they can be read and evaluated later.
In addition to the code itself, we often want to store ancillary information. Tests verify the correctness of the program. Resources like precomputed databases, lookup tables, images, and text files provide other data the program needs to run. There may be documentation: instructions for how to use and understand the software. A program may also depend on code from other programs, which we call libraries, packages, or dependencies. In Clojure, we have a standardized way to bind together all these parts into a single directory, called a project.
We created a project at the start of this book by using Leiningen, the Clojure project tool.
$ lein new scratchscratch is the name of the project, and also the name of the directory where the project’s files live. Inside the project are a few files.
$ cd scratch; ls
doc project.clj README.md resources src target testproject.clj defines the project: its name, its version, dependencies, and so on. Notice the name of the project (scratch) comes first, followed by the version (0.1.0-SNAPSHOT). -SNAPSHOT versions are for development; you can change them at any time, and any projects which depend on the snapshot will pick up the most recent changes. A version which does not end in -SNAPSHOT is fixed: once published, it always points to the same version of the project. This allows projects to specify precisely which projects they depend on. For example, scratch’s project.clj says scratch depends on org.clojure/clojure version 1.5.1.
(defproject scratch "0.1.0-SNAPSHOT"
:description "FIXME: write description"
:url "http://example.com/FIXME"
:license {:name "Eclipse Public License"
:url "http://www.eclipse.org/legal/epl-v10.html"}
:dependencies [[org.clojure/clojure "1.5.1"] ])README.md is the first file most people open when they look at a new project, and Lein generates a generic readme for you to fill in later. We call this kind of scaffolding or example a “stub”; it’s just there to remind you what sort of things to write yourself. You’ll notice the readme includes the name of the project, some notes on what it does and how to use it, a copyright notice where your name should go, and a license, which sets the legal terms for the use of the project. By default, Leiningen suggests the Eclipse Public License, which allows everyone to use and modify the software, so long as they preserve the license information.
The doc directory is for documentation; sometimes hand-written, sometimes automatically generated from the source code. resources is for additional files, like images. src is where Clojure code lives, and test contains the corresponding tests. Finally, target is where Leiningen stores compiled code, built packages, and so on.
Every lein project starts out with a stub namespace containing a simple function. Let’s take a look at that namespace now–it lives in src/scratch/core.clj:
The first part of this file defines the namespace we’ll be working in. The ns macro lets the Clojure compiler know that all following code belongs in the scratch.core namespace. Remember, scratch is the name of our project. scratch.core is for the core functions and definitions of the scratch project. As projects expand, we might add new namespaces to separate our work into smaller, more understandable pieces. For instance, Clojure’s primary functions live in clojure.core, but there are auxiliary functions for string processing in clojure.string, functions for interoperating with Java’s input-output system in clojure.java.io, for printing values in clojure.pprint, and so on.
def, defn, and peers always work in the scope of a particular namespace. The function foo in scratch.core is different from the function foo in scratch.pad.
scratch.foo=> (ns scratch.core)
nil
scratch.core=> (def foo "I'm in core")
#'scratch.core/foo
scratch.core=> (ns scratch.pad)
nil
scratch.pad=> (def foo "I'm in pad!")
#'scratch.pad/fooNotice the full names of these vars are different: scratch.core/foo vs scratch.pad/foo. You can always refer to a var by its fully qualified name: the namespace, followed by a slash /, followed by the short name.
Inside a namespace, symbols resolve to variables which are defined in that namespace. So in scratch.pad, foo refers to scratch.pad/foo.
Namespaces automatically include clojure.core by default; which is where all the standard functions, macros, and special forms come from. let, defn, filter, vector, etc: all live in clojure.core, but are automatically included in new namespaces so we can refer to them by their short names.
Notice that the values for foo we defined in scratch.pad and scratch.core aren’t available in other namespaces, like user.
scratch.pad=> (ns user)
nil
user=> foo
CompilerException java.lang.RuntimeException: Unable to resolve symbol: foo in this context, compiling:(NO_SOURCE_PATH:1:602)To access things from other namespaces, we have to require them in the namespace definition.
The :require part of the ns declaration told the compiler that the user namespace needed access to scratch.core. We could then refer to the fully qualified name scratch.core/foo.
Often, writing out the full namespace is cumbersome–so you can give a short alias for a namespace like so:
The :as directive indicates that anywhere we write c/something, the compiler should expand that to scratch.core/something. If you plan on using a var from another namespace often, you can refer it to the local namespace–which means you may omit the namespace qualifier entirely.
You can refer functions into the current namespace by listing them: [foo bar …]. Alternatively, you can suck in every function from another namespace by saying :refer :all:
Namespaces control complexity by isolating code into more understandable, related pieces. They make it easier to read code by keeping similar things together, and unrelated things apart. By making dependencies between namespaces explicit, they make it clear how groups of functions relate to one another.
If you’ve worked with Erlang, Modula-2, Haskell, Perl, or ML, you’ll find namespaces analogous to modules or packages. Namespaces are often large, encompassing hundreds of functions; and most projects use only a handful of namespaces.
By contrast, object-oriented programming languages like Java, Scala, Ruby, and Objective C organize code in classes, which combine names and state in a single construct. Because all functions in a class operate on the same state, object-oriented languages tend to have many classes with fewer functions in each. It’s not uncommon for a typical Java project to define hundreds or thousands of classes containing only one or two functions each. If you come from an object-oriented language, it can feel a bit unusual to combine so many functions in a single scope–but because functional programs isolate state differently, this is normal. If, on the other hand, you move to an object-oriented language after Clojure, remember that OO languages compose differently. Objects with hundreds of functions are usually considered unwieldy and should be split into smaller pieces.
It’s perfectly fine to test small programs in the REPL. We’ve written and refined hundreds of functions that way: by calling the function and seeing what happens. However, as programs grow in scope and complexity, testing them by hand becomes harder and harder. If you change the behavior of a function which ten other functions rely on, you may have to re-test all ten by hand. In real programs, a small change can alter thousands of distinct behaviors, all of which should be verified.
Wherever possible, we want to automate software tests–making the test itself another program. If the test suite runs in a matter of seconds, we can make changes freely–re-running the tests continuously to verify that everything still works.
As a simple example, let’s write and test a single function in src/scratch/core.clj. How about exponentiation–raising a number to the given power?
(ns scratch.core)
(defn pow
"Raises base to the given power. For instance, (pow 3 2) returns three squared, or nine."
[base power]
(apply * (repeat base power)))So we repeat the base power times, then call * with that sequence of bases to multiply them all together. Seems straightforward enough. Now we need to test it.
By default, all lein projects come with a simple test stub. Let’s see it in action by running lein test.
aphyr@waterhouse:~/scratch$ lein test
lein test scratch.core-test
lein test :only scratch.core-test/a-test
FAIL in (a-test) (core_test.clj:7)
FIXME, I fail.
expected: (= 0 1)
actual: (not (= 0 1))
Ran 1 tests containing 1 assertions.
1 failures, 0 errors.
Tests failed.A failure is when a test returns the wrong value. An error is when a test throws an exception. In this case, the test named a-test, in the file core_test.clj, on line 7, failed. That test expected zero to be equal to one–but found that 0 and 1 were (in point of fact) not equal. Let’s take a look at that test, in test/scratch/core_test.clj.
(ns scratch.core-test
(:require [clojure.test :refer :all]
[scratch.core :refer :all]))
(deftest a-test
(testing "FIXME, I fail."
(is (= 0 1))))These tests live in a namespace too! Notice that namespaces and file names match up: scratch.core lives in src/scratch/core.clj, and scratch.core-test lives in test/scratch/core_test.clj. Dashes (-) in namespaces correspond to underscores (_) in filenames, and dots (.) correspond to directory separators (/).
The scratch.core-test namespace is responsible for testing things in scratch.core. Notice that it requires two namespaces: clojure.test, which provides testing functions and macros, and scratch.core, which is the namespace we want to test.
Then we define a test using deftest. deftest takes a symbol as a test name, and then any number of expressions to evaluate. We can use testing to split up tests into smaller pieces. If a test fails, lein test will print out the enclosing deftest and testing names, to make it easier to figure out what went wrong.
Let’s change this test so that it passes. 0 should equal 0.
(deftest a-test
(testing "Numbers are equal to themselves, right?"
(is (= 0 0))))
aphyr@waterhouse:~/scratch$ lein test
lein test scratch.core-test
Ran 1 tests containing 1 assertions.
0 failures, 0 errors.Wonderful! Now let’s test the pow function. I like to start with a really basic case and work my way up to more complicated ones. 11 is 1, so:
(deftest pow-test
(testing "unity"
(is (= 1 (pow 1 1)))))
aphyr@waterhouse:~/scratch$ lein test
lein test scratch.core-test
Ran 1 tests containing 1 assertions.
0 failures, 0 errors.Excellent. How about something harder?
(deftest pow-test
(testing "unity"
(is (= 1 (pow 1 1))))
(testing "square integers"
(is (= 9 (pow 3 2)))))
aphyr@waterhouse:~/scratch$ lein test
lein test scratch.core-test
lein test :only scratch.core-test/pow-test
FAIL in (pow-test) (core_test.clj:10)
square integers
expected: (= 9 (pow 3 2))
actual: (not (= 9 8))
Ran 1 tests containing 2 assertions.
1 failures, 0 errors.
Tests failed.That’s odd. 32 should be 9, not 8. Let’s double-check our code in the REPL. base was 3, and power was 2, so…
Ah, there’s the problem. We’re mis-using repeat. Instead of repeating 3 twice, we repeated 2 thrice.
Returns a lazy (infinite!, or length n if supplied) sequence of xs. Let’s redefine pow with the correct arguments to repeat:
(defn pow
"Raises base to the given power. For instance, (pow 3 2) returns three
squared, or nine."
[base power]
(apply * (repeat power base)))How about 00? By convention, mathematicians define 00 as 1.
(deftest pow-test
(testing "unity"
(is (= 1 (pow 1 1))))
(testing "square integers"
(is (= 9 (pow 3 2))))
(testing "0^0"
(is (= 1 (pow 0 0)))))
aphyr@waterhouse:~/scratch$ lein test
lein test scratch.core-test
Ran 1 tests containing 3 assertions.
0 failures, 0 errors.Hey, what do you know? It works! But why?
What happens when we call * with an empty list of arguments?
Remember when we talked about how the zero-argument forms of +, and * made some definitions simpler? This is one of those times. We didn’t have to define a special exception for zero powers because (*) returns the multiplicative identity 1, by convention.
The last bit of logistics we need to talk about is working with other people’s code. Clojure projects, like most modern programming environments, are built to work together. We can use libraries to parse data, solve mathematical problems, render graphics, perform simulations, talk to robots, or predict the weather. As a quick example, I’d like to imagine that you and I are public-health researchers trying to identify the best location for an ad campaign to reduce drunk driving.
The FBI’s Uniform Crime Reporting database tracks the annual tally of different types of arrests, broken down by county–but the data files provided by the FBI are a mess to work with. Helpfully, Matt Aliabadi has helpfully organized the UCR’s somewhat complex format into nice, normalized files in a data format called JSON, and made them available on Github. Let’s download the most recent year’s normalized data, and save it in the scratch directory.
What’s in this file, anyway? Let’s take a look at the first few lines using head:
aphyr@waterhouse:~/scratch$ head 2008.json
[
{
"icpsr_study_number": null,
"icpsr_edition_number": 1,
"icpsr_part_number": 1,
"icpsr_sequential_case_id_number": 1,
"fips_state_code": "01",
"fips_county_code": "001",
"county_population": 52417,
"number_of_agencies_in_county": 3,This is a data format called JSON, and it looks a lot like Clojure’s data structures. That’s the start of a vector on the first line, and the second line starts a map. Then we’ve got string keys like “icpsr_study_number”, and values which look like null (nil), numbers, or strings. But in order to work with this file, we’ll need to parse it into Clojure data structures. For that, we can use a JSON parsing library, like Cheshire.
Cheshire, like most Clojure libraries, is published on an internet repository called Clojars. To include it in our scratch project, all we have to do is add open project.clj in a text editor, and add a line specifying that we want to use a particular version of Cheshire.
(defproject scratch "0.1.0-SNAPSHOT"
:description "Just playing around"
:url "http://example.com/FIXME"
:license {:name "Eclipse Public License"
:url "http://www.eclipse.org/legal/epl-v10.html"}
:dependencies [[org.clojure/clojure "1.5.1"]
[cheshire "5.3.1"]])Now we’ll exit the REPL with Control+D (^D), and restart it with lein repl. Leiningen, the Clojure package manager, will automatically download Cheshire from Clojars and make it available in the new REPL session.
Now let’s figure out how to parse the JSON file. Looking at Cheshire’s README shows an example that looks helpful:
So Cheshire includes a parse-string function which can take a string and return a data structure. How can we get a string out of a file? Using slurp:
Woooow, that’s a lot of data! Let’s chop it down to something more manageable. How about the first entry?
user=> (first (parse-string (slurp "2008.json")))
{"syntheticdrug_salemanufacture" 1, "all_other_offenses_except_traffic" 900, "arson" 3, ...}
user=> (-> "2008.json" slurp parse-string first)It’d be nicer if this data used keywords instead of strings for its keys. Let’s use the second argument to Chesire’s parse-string to convert all the keys in maps to keywords.
user=> (first (parse-string (slurp "2008.json") true))
{:other_assaults 288, :gambling_all_other 0, :arson 3, ... :drunkenness 108}Since we’re going to be working with this dataset over and over again, let’s bind it to a variable for easy re-use.
Now we’ve got a big long vector of counties, each represented by a map–but we’re just interested in the DUIs of each one. What does that look like? Let’s map each county to its :driving_under_influence.
What’s the most any county has ever reported?
45056 counts in one year? Wow! What about the second-worst county? The easiest way to find the top n counties is to sort the list, then look at the final elements.
user=> (->> data (map :driving_under_influence) sort (take-last 10))
(8589 10432 10443 10814 11439 13983 17572 18562 26235 45056)So the top 10 counties range from 8549 counts to 45056 counts. What’s the most common count? Clojure comes with a built-in function called frequencies which takes a sequence of elements, and returns a map from each element to how many times it appeared in the sequence.
user=> (->> data (map :driving_under_influence) frequencies)
{0 227, 1024 1, 45056 1, 32 15, 2080 1, 64 12 ...Now let’s take those [drunk-driving, frequency] pairs and sort them by key to produce a histogram. sort-by takes a function to apply to each element in the collection–in this case, a key-value pair–and returns something that can be sorted, like a number. We’ll choose the key function to extract the key from each key-value pair, effectively sorting the counties by number of reported incidents.
user=> (->> data (map :driving_under_influence) frequencies (sort-by key) pprint)
([0 227]
[1 24]
[2 17]
[3 20]
[4 17]
[5 24]
[6 23]
[7 23]
[8 17]
[9 19]
[10 29]
[11 20]
[12 18]
[13 21]
[14 25]
[15 13]
[16 18]
[17 16]
[18 17]
[19 11]
[20 8]
...So a ton of counties (227 out of 3172 total) report no drunk driving; a few hundred have one incident, a moderate number have 10-20, and it falls off from there. This is a common sort of shape in statistics; often a hallmark of an exponential distribution.
How about the 10 worst counties, all the way out on the end of the curve?
user=> (->> data (map :driving_under_influence) frequencies (sort-by key) (take-last 10) pprint)
([8589 1]
[10432 1]
[10443 1]
[10814 1]
[11439 1]
[13983 1]
[17572 1]
[18562 1]
[26235 1]
[45056 1])So it looks like 45056 is high, but there are 8 other counties with tens of thousands of reports too. Let’s back up to the original dataset, and sort it by DUIs:
user=> (->> data (sort-by :driving_under_influence) (take-last 10) pprint)
({:other_assaults 3096,
:gambling_all_other 3,
:arson 106,
:have_stolen_property 698,
:syntheticdrug_salemanufacture 0,
:icpsr_sequential_case_id_number 220,
:drug_abuse_salemanufacture 1761,
...What we’re looking for is the county names, but it’s a little hard to read these enormous maps. Let’s take a look at just the keys that define each county, and see which ones might be useful. We’ll take this list of counties, map each one to a list of its keys, and concatenate those lists together into one big long list. mapcat maps and concatenates in a single step. We expect the same keys to show up over and over again, so we’ll remove duplicates by merging all those keys into a sorted-set.
user=> (->> data (sort-by :driving_under_influence) (take-last 10) (mapcat keys) (into (sorted-set)) pprint)
#{:aggravated_assaults :all_other_offenses_except_traffic :arson
:auto_thefts :bookmaking_horsesport :burglary :county_population
:coverage_indicator :curfew_loitering_laws :disorderly_conduct
:driving_under_influence :drug_abuse_salemanufacture
:drug_abuse_violationstotal :drug_possession_other
:drug_possession_subtotal :drunkenness :embezzlement
:fips_county_code :fips_state_code :forgerycounterfeiting :fraud
:gambling_all_other :gambling_total :grand_total
:have_stolen_property :icpsr_edition_number :icpsr_part_number
:icpsr_sequential_case_id_number :icpsr_study_number :larceny
:liquor_law_violations :marijuana_possession
:marijuanasalemanufacture :multicounty_jurisdiction_flag :murder
:number_of_agencies_in_county :numbers_lottery
:offenses_against_family_child :opiumcocaine_possession
:opiumcocainesalemanufacture :other_assaults :otherdang_nonnarcotics
:part_1_total :property_crimes :prostitutioncomm_vice :rape :robbery
:runaways :sex_offenses :suspicion :synthetic_narcoticspossession
:syntheticdrug_salemanufacture :vagrancy :vandalism :violent_crimes
:weapons_violations}Ah, :fips_county_code and :fips_state_code look promising. Let’s compact the dataset to just drunk driving and those codes, using select-keys.
user=> (->> data (sort-by :driving_under_influence) (take-last 10) (map #(select-keys % [:driving_under_influence :fips_county_code :fips_state_code])) pprint)
({:fips_state_code "06",
:fips_county_code "067",
:driving_under_influence 8589}
{:fips_state_code "48",
:fips_county_code "201",
:driving_under_influence 10432}
{:fips_state_code "32",
:fips_county_code "003",
:driving_under_influence 10443}
{:fips_state_code "06",
:fips_county_code "065",
:driving_under_influence 10814}
{:fips_state_code "53",
:fips_county_code "033",
:driving_under_influence 11439}
{:fips_state_code "06",
:fips_county_code "071",
:driving_under_influence 13983}
{:fips_state_code "06",
:fips_county_code "059",
:driving_under_influence 17572}
{:fips_state_code "06",
:fips_county_code "073",
:driving_under_influence 18562}
{:fips_state_code "04",
:fips_county_code "013",
:driving_under_influence 26235}
{:fips_state_code "06",
:fips_county_code "037",
:driving_under_influence 45056})Now we’re getting somewhere–but we need a way to interpret these state and county codes. Googling for “FIPS” led me to Wikipedia’s account of the FIPS county code system, and the NOAA’s ERDDAP service, which has a table mapping FIPS codes to state and county names. Let’s save that file as fips.json.
Now we’ll slurp that file into the REPL and parse it, just like we did with the crime dataset.
Let’s take a quick look at the structure of this data:
user=> (keys fips)
(:table)
user=> (keys (:table fips))
(:columnNames :columnTypes :rows)
user=> (->> fips :table :columnNames)
["FIPS" "Name"]Great, so we expect the rows to be a list of FIPS code and Name.
user=> (->> fips :table :rows (take 3) pprint)
(["02000" "AK"]
["02013" "AK, Aleutians East"]
["02016" "AK, Aleutians West"])Perfect. Now that’s we’ve done some exploratory work in the REPL, let’s shift back to an editor. Create a new file in src/scratch/crime.clj:
(ns scratch.crime
(:require [cheshire.core :as json]))
(def fips
"A map of FIPS codes to their county names."
(->> (json/parse-string (slurp "fips.json") true)
:table
:rows
(into {})))We’re just taking a snippet we wrote in the REPL–parsing the FIPS dataset–and writing it down for use as a part of a bigger program. We use (into {}) to convert the sequence of [fips, name] pairs into a map, just like we used into (sorted-set) to merge a list of keywords into a set earlier. into works just like conj, repeated over and over again, and is an incredibly useful tool for building up collections of things.
Back in the REPL, let’s check if that worked:
Remember, maps act like functions in Clojure, so we can use the fips map to look up the names of counties efficiently.
We also have to load the UCR crime file–so let’s split that load-and-parse code into its own function:
(defn load-json
"Given a filename, reads a JSON file and returns it, parsed, with keywords."
[file]
(json/parse-string (slurp file) true))
(def fips
"A map of FIPS codes to their county names."
(->> "fips.json"
load-json
:table
:rows
(into {})))Now we can re-use load-json to load the UCR crime file.
(defn most-duis
"Given a JSON filename of UCR crime data for a particular year, finds the
counties with the most DUIs."
[file]
(->> file
load-json
(sort-by :driving_under_influence)
(take-last 10)
(map #(select-keys % [:driving_under_influence
:fips_county_code
:fips_state_code]))))
user=> (use 'scratch.crime :reload) (pprint (most-duis "2008.json"))
nil
({:fips_state_code "06",
:fips_county_code "067",
:driving_under_influence 8589}
{:fips_state_code "48",
:fips_county_code "201",
:driving_under_influence 10432}
{:fips_state_code "32",
:fips_county_code "003",
:driving_under_influence 10443}
{:fips_state_code "06",
:fips_county_code "065",
:driving_under_influence 10814}
{:fips_state_code "53",
:fips_county_code "033",
:driving_under_influence 11439}
{:fips_state_code "06",
:fips_county_code "071",
:driving_under_influence 13983}
{:fips_state_code "06",
:fips_county_code "059",
:driving_under_influence 17572}
{:fips_state_code "06",
:fips_county_code "073",
:driving_under_influence 18562}
{:fips_state_code "04",
:fips_county_code "013",
:driving_under_influence 26235}
{:fips_state_code "06",
:fips_county_code "037",
:driving_under_influence 45056})Almost there. We need to join together the state and county FIPS codes into a single string, because that’s how fips represents the county code:
(defn fips-code
"Given a county (a map with :fips_state_code and :fips_county_code keys),
returns the five-digit FIPS code for the county, as a string."
[county]
(str (:fips_state_code county) (:fips_county_code county)))Let’s write a quick test in test/scratch/crime_test.clj to verify that function works correctly:
(ns scratch.crime-test
(:require [clojure.test :refer :all]
[scratch.crime :refer :all]))
(deftest fips-code-test
(is (= "12345" (fips-code {:fips_state_code "12" :fips_county_code "345"}))))
aphyr@waterhouse:~/scratch$ lein test scratch.crime-test
lein test scratch.crime-test
Ran 1 tests containing 1 assertions.
0 failures, 0 errors.Great. Note that lein test some-namespace runs only the tests in that particular namespace. For the last step, let’s take the most-duis function and, using fips and fips-code, construct a map of county names to DUI reports.
(defn most-duis
"Given a JSON filename of UCR crime data for a particular year, finds the
counties with the most DUIs."
[file]
(->> file
load-json
(sort-by :driving_under_influence)
(take-last 10)
(map (fn [county]
[(fips (fips-code county))
(:driving_under_influence county)]))
(into {})))
user=> (use 'scratch.crime :reload) (pprint (most-duis "2008.json"))
nil
{"CA, Orange" 17572,
"CA, San Bernardino" 13983,
"CA, Los Angeles" 45056,
"CA, Riverside" 10814,
"NV, Clark" 10443,
"WA, King" 11439,
"AZ, Maricopa" 26235,
"CA, San Diego" 18562,
"TX, Harris" 10432,
"CA, Sacramento" 8589}Our question is, at least in part, answered: Los Angeles and Maricopa counties, in California and Arizona, have the most reports of drunk driving out of any counties in the 2008 Uniform Crime Reporting database. These might be good counties for a PSA campaign. California has either lots of drunk drivers, or aggressive enforcement, or both! Remember, this only tells us about reports of crimes; not the crimes themselves. Numbers vary based on how the state enforces the laws!
(ns scratch.crime
(:require [cheshire.core :as json]))
(defn load-json
"Given a filename, reads a JSON file and returns it, parsed, with keywords."
[file]
(json/parse-string (slurp file) true))
(def fips
"A map of FIPS codes to their county names."
(->> "fips.json"
load-json
:table
:rows
(into {})))
(defn fips-code
"Given a county (a map with :fips_state_code and :fips_county_code keys),
returns the five-digit FIPS code for the county, as a string."
[county]
(str (:fips_state_code county) (:fips_county_code county)))
(defn most-duis
"Given a JSON filename of UCR crime data for a particular year, finds the
counties with the most DUIs."
[file]
(->> file
load-json
(sort-by :driving_under_influence)
(take-last 10)
(map (fn [county]
[(fips (fips-code county))
(:driving_under_influence county)]))
(into {})))In this chapter, we expanded beyond transient programs written in the REPL. We learned how projects combine static resources, code, and tests into a single package, and how projects can relate to one another through dependencies. We learned the basics of Clojure’s namespace system, which isolates distinct chunks of code from one another, and how to include definitions from one namespace in another via require and use. We learned how to write and run tests to verify our code’s correctness, and how to move seamlessly between the repl and code in .clj files. We made use of Cheshire, a Clojure library published on Clojars, to parse JSON–a common data format. Finally, we brought together our knowledge of Clojure’s basic grammar, immutable data structures, core functions, sequences, threading macros, and vars to explore a real-world problem.
Until this point in the book, we’ve dealt primarily in specific details: what an expression is, how math works, which functions apply to different data structures, and where code lives. But programming, like speaking a language, painting landscapes, or designing turbines, is about more than the nuts and bolts of the trade. It’s knowing how to combine those parts into a cohesive whole–and this is a skill which is difficult to describe formally. In this part of the book, I’d like to work with you on an integrative tour of one particular problem: modeling a rocket in flight.
We’re going to reinforce our concrete knowledge of the standard library by using maps, sequences, and math functions together. At the same time, we’re going to practice how to represent a complex system; decomposing a problem into smaller parts, naming functions and variables, and writing tests.
First, we need a representation of a craft. The obvious properties for a rocket are its dry mass (how much it weighs without fuel), fuel mass, position, velocity, and time. We’ll create a new file in our scratch project–src/scratch/rocket.clj–to talk about spacecraft.
For starters, let’s pattern our craft after an Atlas V launch vehicle. We’ll represent everything in SI units–kilograms, meters, newtons, etc. The Atlas V carries 627,105 lbs of LOX/RP-1 fuel, and a total mass of 334,500 kg gives only 50,050 kg of mass which isn’t fuel. It develops 4152 kilonewtons of thrust and runs for 253 seconds, with a specific impulse (effectively, exhaust velocity) of 3.05 kilometers/sec. Real rockets develop varying amounts of thrust depending on the atmosphere, but we’ll pretend it’s constant in our simulation.
(defn atlas-v
[]
{:dry-mass 50050
:fuel-mass 284450
:time 0
:isp 3050
:max-fuel-rate (/ 284450 253)
:max-thrust 4.152e6})How heavy is the craft?
What about the position and velocity? We could represent them in Cartesian coordinates–x, y, and z–or we could choose spherical coordinates: a radius from the planet and angle from the pole and 0 degrees longitude. I’ve got a hunch that spherical coordinates will be easier for position, but accelerating the craft will be simplest in in x, y, and z terms. The center of the planet is a natural choice for the coordinate system’s origin (0, 0, 0). We’ll choose z along the north pole, and x and y in the plane of the equator.
Let’s define a space center where we launch from–let’s say it’s initially on the equator at y=0. To figure out the x coordinate, we’ll need to know how far the space center is from the center of the earth. The earth’s equatorial radius is ~6378 kilometers.
How fast is the surface moving? Well the earth’s day is 86,400 seconds long,
which means a given point on the equator has to go 2 * pi * equatorial radius meters in earth-day seconds:
(def earth-equatorial-speed
"How fast points on the equator move, relative to the center of the earth,
in meters/sec."
(/ (* 2 Math/PI earth-equatorial-radius)
earth-day))So our space center is on the equator (z=0), at y=0 by choice, which means x is the equatorial radius. Since the earth is spinning, the space center is moving at earth-equatorial-speed in the y direction–and not changing at all in x or z.
(def initial-space-center
"The initial position and velocity of the launch facility"
{:time 0
:position {:x earth-equatorial-radius
:y 0
:z 0}
:velocity {:x 0
:y earth-equatorial-speed
:z 0}}):position and :velocity are both vectors, in the sense that they describe a position, or a direction, in terms of x, y, and z components. This is a different kind of vector than a Clojure vector, like [1 2 3]. We’re actually representing these logical vectors as Clojure maps, with :x, :y, and :z keys, corresponding to the distance along the x, y, and z directions, from the center of the earth. Throughout this chapter, I’ll mainly use the term coordinates to talk about these structures, to avoid confusion with Clojure vectors.
Now let’s create a function which positions our craft on the launchpad at time 0. We’ll just merge the spacecraft’s with the initial space center, overwriting the craft’s time and space coordinates.
(defn prepare
"Prepares a craft for launch from an equatorial space center."
[craft]
(merge craft initial-space-center))Gravity continually pulls the spacecraft towards the center of the Earth, accelerating it by 9.8 meters/second every second. To figure out what direction is towards the Earth, we’ll need the angles of a spherical coordinate system. We’ll use the trigonometric functions from java.lang.Math.
(defn magnitude
"What's the radius of a given set of cartesian coordinates?"
[c]
; By the Pythagorean theorem...
(Math/sqrt (+ (Math/pow (:x c) 2)
(Math/pow (:y c) 2)
(Math/pow (:z c) 2))))
(defn cartesian->spherical
"Converts a map of Cartesian coordinates :x, :y, and :z to spherical coordinates :r, :theta, and :phi."
[c]
(let [r (magnitude c)]
{:r r
:theta (Math/acos (/ (:z c) r))
:phi (Math/atan (/ (:y c) (:x c)))}))
(defn spherical->cartesian
"Converts spherical to Cartesian coordinates."
[c]
{:x (* (:r c) (Math/sin (:theta c)) (Math/cos (:phi c)))
:y (* (:r c) (Math/sin (:theta c)) (Math/sin (:phi c)))
:z (* (:r c) (Math/cos (:phi c)))})With those angles in mind, computing the gravitational acceleration is easy. We just take the spherical coordinates of the spacecraft, and replace the radius with the total force due to gravity. Then we can transform that spherical force back into Cartesian coordinates.
(def g "Acceleration of gravity in meters/s^2" -9.8)
(defn gravity-force
"The force vector, each component in Newtons, due to gravity."
[craft]
; Since force is mass times acceleration...
(let [total-force (* g (mass craft))]
(-> craft
; Now we'll take the craft's position
:position
; in spherical coordinates,
cartesian->spherical
; replace the radius with the gravitational force...
(assoc :r total-force)
; and transform back to Cartesian-land
spherical->cartesian)))Rockets produce thrust by consuming fuel. Let’s say the fuel consumption is always the maximum, until we run out:
(defn fuel-rate
"How fast is fuel, in kilograms/second, consumed by the craft?"
[craft]
(if (pos? (:fuel-mass craft))
(:max-fuel-rate craft)
0))Now that we know how much fuel is being consumed, we can compute the force the rocket engine develops. That force is simply the mass consumed per second times the exhaust velocity–which is the specific impulse :isp. We’ll ignore atmospheric effects.
(defn thrust
"How much force, in newtons, does the craft's rocket engines exert?"
[craft]
(* (fuel-rate craft) (:isp craft)))Cool. What about the direction of thrust? Just for grins, let’s keep the rocket pointing entirely along the x axis.
(defn engine-force
"The force vector, each component in Newtons, due to the rocket engine."
[craft]
(let [t (thrust craft)]
{:x t
:y 0
:z 0}))The total force on a craft is just the sum of gravity and thrust. To sum these maps together, we’ll need a way to sum the x, y, and z components independently. Clojure’s merge-with function combines common fields in maps using a function, so this is surprisingly straightforward.
(defn total-force
"Total force on a craft."
[craft]
(merge-with + (engine-force craft)
(gravity-force craft)))The acceleration of a craft, by Newton’s second law, is force divided by mass. This one’s a little trickier; given {:x 1 :y 2 :z 4} we want to apply a function–say, multiplication by a factor, to each number. Since maps are sequences of key/value pairs…
… and we can build up new maps out of key/value pairs using into…
… we can write a function map-values which works like map, but affects the values of a map data structure.
(defn map-values
"Applies f to every value in the map m."
[f m]
(into {}
(map (fn [pair]
[(key pair) (f (val pair))])
m)))And that allows us to define a scale function which scales a set of coordinates by some factor:
(defn scale
"Multiplies a map of x, y, and z coordinates by the given factor."
[factor coordinates]
(map-values (partial * factor) coordinates))What’s that partial thing? It’s a function which takes a function, and some arguments, and returns a new function. What does the new function do? It calls the original function, with the arguments passed to partial, followed by any arguments passed to the new function. In short, (partial * factor) returns a function that takes any number, and multiplies it by factor.
So to divide each component of the force vector by the mass of the craft:
(defn acceleration
"Total acceleration of a craft."
[craft]
(let [m (mass craft)]
(scale (/ m) (total-force craft))))Note that (/ m) returns 1/m. Our scale function can do double-duty as both multiplication and division.
With the acceleration and fuel consumption all figured out, we’re ready to apply those changes over time. We’ll write a function which takes the rocket at a particular time, and returns a version of it dt seconds later.
(defn step
[craft dt]
(assoc craft
; Time advances by dt seconds
:t (+ dt (:t craft))
; We burn some fuel
:fuel-mass (- (:fuel-mass craft) (* dt (fuel-rate craft)))
; Our position changes based on our velocity
:position (merge-with + (:position craft)
(scale dt (:velocity craft)))
; And our velocity changes based on our acceleration
:velocity (merge-with + (:velocity craft)
(scale dt (acceleration craft)))))OK. Let’s save the rocket.clj file, load that code into the REPL, and fire it up.
use is like a shorthand for (:require … :refer :all). We’re passing :reload because we want the REPL to re-read the file. Notice that in ns declarations, the namespace name scratch.rocket is unquoted–but when we call use or require at the repl, we quote the namespace name.
user=> (atlas-v)
{:dry-mass 50050, :fuel-mass 284450, :time 0, :isp 3050, :max-fuel-rate 284450/253, :max-thrust 4152000.0}Let’s prepare the rocket. We’ll use pprint to print it in a more readable form.
user=> (-> (atlas-v) prepare pprint)
{:velocity {:x 0, :y 463.8312116386399, :z 0},
:position {:x 6378137, :y 0, :z 0},
:dry-mass 50050,
:fuel-mass 284450,
:time 0,
:isp 3050,
:max-fuel-rate 284450/253,
:max-thrust 4152000.0}Great; there it is on the launchpad. Wow, even “standing still”, it’s moving at 463 meters/sec because of the earth’s rotation! That means you and I are flying through space at almost half a kilometer every second! Let’s step forward one second in time.
user=> (-> (atlas-v) prepare (step 1) pprint)
NullPointerException clojure.lang.Numbers.ops (Numbers.java:942)In evaluating this expression, Clojure reached a point where it could not continue, and aborted execution. We call this error an exception, and the process of aborting throwing the exception. Clojure backs up to the function which called the function that threw, then the function which called that function, and so on, all the way to the top-level expression. The REPL finally intercepts the exception, prints an error to the console, and stashes the exception object in a special variable *e.
In this case, we know that the exception in question was a NullPointerException, which occurs when a function received nil unexpectedly. This one came from clojure.lang.Numbers.ops, which suggests some sort of math was involved. Let’s use pst to find out where it came from.
user=> (pst *e)
NullPointerException
clojure.lang.Numbers.ops (Numbers.java:942)
clojure.lang.Numbers.add (Numbers.java:126)
scratch.rocket/step (rocket.clj:125)
user/eval1478 (NO_SOURCE_FILE:1)
clojure.lang.Compiler.eval (Compiler.java:6619)
clojure.lang.Compiler.eval (Compiler.java:6582)
clojure.core/eval (core.clj:2852)
clojure.main/repl/read-eval-print--6588/fn--6591 (main.clj:259)
clojure.main/repl/read-eval-print--6588 (main.clj:259)
clojure.main/repl/fn--6597 (main.clj:277)
clojure.main/repl (main.clj:277)
clojure.tools.nrepl.middleware.interruptible-eval/evaluate/fn--589 (interruptible_eval.clj:56)This is called a stack trace: the stack is the context of the program at each function call. It traces the path the computer took in evaluating the expression, from the bottom to the top. At the bottom is the REPL, and Clojure compiler. Our code begins at user/eval1478–that’s the compiler’s name for the expression we just typed. That function called scratch.rocket/step, which in turn called Numbers.add, and that called Numbers.ops. Let’s start by looking at the last function we wrote before calling into Clojure’s standard library: the step function, in rocket.clj, on line 125.
Ah; we named the time field :time earlier, not :t. Let’s replace :t with :time, save the file, and reload.
user=> (use 'scratch.rocket :reload)
nil
user=> (-> (atlas-v) prepare (step 1) pprint)
{:velocity {:x 0.45154055666826215, :y 463.8312116386399, :z -9.8},
:position {:x 6378137, :y 463.8312116386399, :z 0},
:dry-mass 50050,
:fuel-mass 71681400/253,
:time 1,
:isp 3050,
:max-fuel-rate 284450/253,
:max-thrust 4152000.0}Look at that! Our position is unchanged (because our velocity was zero), but our velocity has shifted. We’re now moving… wait, -9.8 meters per second south? That can’t be right. Gravity points down, not sideways. Something must be wrong with our spherical coordinate system. Let’s write a test in test/scratch/rocket_test.clj to explore.
(ns scratch.rocket-test
(:require [clojure.test :refer :all]
[scratch.rocket :refer :all]))
(deftest spherical-coordinate-test
(let [pos {:x 1 :y 2 :z 3}]
(testing "roundtrip"
(is (= pos (-> pos cartesian->spherical spherical->cartesian))))))
aphyr@waterhouse:~/scratch$ lein test
lein test scratch.core-test
lein test scratch.rocket-test
lein test :only scratch.rocket-test/spherical-coordinate-test
FAIL in (spherical-coordinate-test) (rocket_test.clj:8)
roundtrip
expected: (= pos (-> pos cartesian->spherical spherical->cartesian))
actual: (not (= {:z 3, :y 2, :x 1} {:x 1.0, :y 1.9999999999999996, :z 1.6733200530681513}))
Ran 2 tests containing 4 assertions.
1 failures, 0 errors.
Tests failed.Definitely wrong. Looks like something to do with the z coordinate, since x and y look OK. Let’s try testing a point on the north pole:
(deftest spherical-coordinate-test
(testing "spherical->cartesian"
(is (= (spherical->cartesian {:r 2
:phi 0
:theta 0})
{:x 0.0 :y 0.0 :z 2.0})))
(testing "roundtrip"
(let [pos {:x 1.0 :y 2.0 :z 3.0}]
(is (= pos (-> pos cartesian->spherical spherical->cartesian))))))
That checks out OK. Let’s try some values in the repl.
user=> (cartesian->spherical {:x 0.00001 :y 0.00001 :z 2.0})
{:r 2.00000000005, :theta 7.071068104411588E-6, :phi 0.7853981633974483}
user=> (cartesian->spherical {:x 1 :y 2 :z 3})
{:r 3.7416573867739413, :theta 0.6405223126794245, :phi 1.1071487177940904}
user=> (spherical->cartesian (cartesian->spherical {:x 1 :y 2 :z 3}))
{:x 1.0, :y 1.9999999999999996, :z 1.6733200530681513}
user=> (cartesian->spherical {:x 1 :y 2 :z 0})
{:r 2.23606797749979, :theta 1.5707963267948966, :phi 1.1071487177940904}
user=> (cartesian->spherical {:x 1 :y 1 :z 0})
{:r 1.4142135623730951, :theta 1.5707963267948966, :phi 0.7853981633974483}Oh, wait, that looks odd. {:x 1 :y 1 :z 0} is on the equator: phi–the angle from the pole–should be pi/2 or ~1.57, and theta–the angle around the equator–should be pi/4 or 0.78. Those coordinates are reversed! Double-checking our formulas with Wolfram MathWorld shows that we mixed up phi and theta! Let’s redefine cartesian->polar correctly.
(defn cartesian->spherical
"Converts a map of Cartesian coordinates :x, :y, and :z to spherical
coordinates :r, :theta, and :phi."
[c]
(let [r (Math/sqrt (+ (Math/pow (:x c) 2)
(Math/pow (:y c) 2)
(Math/pow (:z c) 2)))]
{:r r
:phi (Math/acos (/ (:z c) r))
:theta (Math/atan (/ (:y c) (:x c)))}))
aphyr@waterhouse:~/scratch$ lein test
lein test scratch.core-test
lein test scratch.rocket-test
Ran 2 tests containing 5 assertions.
0 failures, 0 errors.Great. Now let’s check the rocket trajectory again.
user=> (-> (atlas-v) prepare (step 1) pprint)
{:velocity
{:x 0.45154055666826204,
:y 463.8312116386399,
:z -6.000769315822031E-16},
:position {:x 6378137, :y 463.8312116386399, :z 0},
:dry-mass 50050,
:fuel-mass 71681400/253,
:time 1,
:isp 3050,
:max-fuel-rate 284450/253,
:max-thrust 4152000.0}This time, our velocity is increasing in the +x direction, at half a meter per second. We have liftoff!
We have a function that can move the rocket forward by one small step of time, but we’d like to understand the rocket’s trajectory as a whole; to see all positions it will take. We’ll use iterate to construct a lazy, infinite sequence of rocket states, each one constructed by stepping forward from the last.
(defn trajectory
[dt craft]
"Returns all future states of the craft, at dt-second intervals."
(iterate #(step % 1) craft))
user=> (->> (atlas-v) prepare (trajectory 1) (take 3) pprint)
({:velocity {:x 0, :y 463.8312116386399, :z 0},
:position {:x 6378137, :y 0, :z 0},
:dry-mass 50050,
:fuel-mass 284450,
:time 0,
:isp 3050,
:max-fuel-rate 284450/253,
:max-thrust 4152000.0}
{:velocity
{:x 0.45154055666826204,
:y 463.8312116386399,
:z -6.000769315822031E-16},
:position {:x 6378137, :y 463.8312116386399, :z 0},
:dry-mass 50050,
:fuel-mass 71681400/253,
:time 1,
:isp 3050,
:max-fuel-rate 284450/253,
:max-thrust 4152000.0}
{:velocity
{:x 0.9376544222659078,
:y 463.83049896253056,
:z -1.200153863164406E-15},
:position
{:x 6378137.451540557,
:y 927.6624232772798,
:z -6.000769315822031E-16},
:dry-mass 50050,
:fuel-mass 71396950/253,
:time 2,
:isp 3050,
:max-fuel-rate 284450/253,
:max-thrust 4152000.0})Notice that each map is like a frame of a movie, playing at one frame per second. We can make the simulation more or less accurate by raising or lowering the framerate–adjusting the parameter fed to trajectory. For now, though, we’ll stick with one-second intervals.
How high above the surface is the rocket?
(defn altitude
"The height above the surface of the equator, in meters."
[craft]
(-> craft
:position
cartesian->spherical
:r
(- earth-equatorial-radius)))Now we can explore the rocket’s path as a series of altitudes over time:
user=> (->> (atlas-v) prepare (trajectory 1) (map altitude) (take 10) pprint)
(0.0
0.016865378245711327
0.519002066925168
1.540983198210597
3.117615718394518
5.283942770212889
8.075246102176607
11.52704851794988
15.675116359256208
20.555462017655373)The million dollar question, though, is whether the rocket breaks orbit.
(defn above-ground?
"Is the craft at or above the surface?"
[craft]
(<= 0 (altitude craft)))
(defn flight
"The above-ground portion of a trajectory."
[trajectory]
(take-while above-ground? trajectory))
(defn crashed?
"Does this trajectory crash into the surface before 100 hours are up?"
[trajectory]
(let [time-limit (* 100 3600)] ; 1 hour
(not (every? above-ground?
(take-while #(<= (:time %) time-limit) trajectory)))))
(defn crash-time
"Given a trajectory, returns the time the rocket impacted the ground."
[trajectory]
(:time (last (flight trajectory))))
(defn apoapsis
"The highest altitude achieved during a trajectory."
[trajectory]
(apply max (map altitude trajectory)))
(defn apoapsis-time
"The time of apoapsis"
[trajectory]
(:time (apply max-key altitude (flight trajectory))))If the rocket goes below ground, we know it crashed. If the rocket stays in orbit, the trajectory will never end. That makes it a bit tricky to tell whether the rocket is in a stable orbit or not, because we can’t ask about every element, or the last element, of an infinite sequence: it’ll take infinite time to evaluate. Instead, we’ll assume that the rocket should crash within the first, say, 100 hours; if it makes it past that point, we’ll assume it made orbit successfully. With these functions in hand, we’ll write a test in test/scratch/rocket_test.clj to see whether or not the launch is successful:
(deftest makes-orbit
(let [trajectory (->> (atlas-v)
prepare
(trajectory 1))]
(when (crashed? trajectory)
(println "Crashed at" (crash-time trajectory) "seconds")
(println "Maximum altitude" (apoapsis trajectory)
"meters at" (apoapsis-time trajectory) "seconds"))
; Assert that the rocket eventually made it to orbit.
(is (not (crashed? trajectory)))))
aphyr@waterhouse:~/scratch$ lein test scratch.rocket-test
lein test scratch.rocket-test
Crashed at 982 secondsMaximum altitude 753838.039645385 meters at 532 seconds
lein test :only scratch.rocket-test/makes-orbit
FAIL in (makes-orbit) (rocket_test.clj:26)
expected: (not (crashed? trajectory))
actual: (not (not true))
Ran 2 tests containing 3 assertions.
1 failures, 0 errors.
Tests failed.We made it to an altitude of 750 kilometers, and crashed 982 seconds after launch. We’re gonna need a bigger boat.
The Atlas V isn’t big enough to make it into orbit on its own. It carries a second stage, the Centaur), which is much smaller and uses more efficient engines.
(defn centaur
"The upper rocket stage.
http://en.wikipedia.org/wiki/Centaur_(rocket_stage)
http://www.astronautix.com/stages/cenaurde.htm"
[]
{:dry-mass 2361
:fuel-mass 13897
:isp 4354
:max-fuel-rate (/ 13897 470)})The Centaur lives inside the Atlas V main stage. We’ll re-write atlas-v to take an argument: its next stage.
(defn atlas-v
"The full launch vehicle. http://en.wikipedia.org/wiki/Atlas_V"
[next-stage]
{:dry-mass 50050
:fuel-mass 284450
:isp 3050
:max-fuel-rate (/ 284450 253)
:next-stage next-stage})Now, in our tests, we’ll construct the rocket like so:
When we exhaust the fuel reserves of the primary stage, we’ll de-couple the main booster from the Centaur. In terms of our simulation, the Atlas V will be replaced by its next stage, the Centaur. We’ll write a function stage which separates the vehicles when ready:
(defn stage
"When fuel reserves are exhausted, separate stages. Otherwise, return craft
unchanged."
[craft]
(cond
; Still fuel left
(pos? (:fuel-mass craft))
craft
; No remaining stages
(nil? (:next-stage craft))
craft
; Stage!
:else
(merge (:next-stage craft)
(select-keys craft [:time :position :velocity]))))We’re using cond to handle three distinct cases: where there’s fuel remaining in the craft, where there is no stage to separate, and when we’re ready for stage separation. Separation is easy: we simply return the next stage of the current craft, with the current craft’s time, position, and velocity merged in.
Finally, we’ll have to update our step function to take into account the possibility of stage separation.
(defn step
[craft dt]
(let [craft (stage craft)]
(assoc craft
; Time advances by dt seconds
:time (+ dt (:time craft))
; We burn some fuel
:fuel-mass (- (:fuel-mass craft) (* dt (fuel-rate craft)))
; Our position changes based on our velocity
:position (merge-with + (:position craft)
(scale dt (:velocity craft)))
; And our velocity changes based on our acceleration
:velocity (merge-with + (:velocity craft)
(scale dt (acceleration craft))))))Same as before, only now we call stage prior to the physics simulation. Let’s try a launch.
aphyr@waterhouse:~/scratch$ lein test scratch.rocket-test
lein test scratch.rocket-test
Crashed at 2415 secondsMaximum altitude 4598444.289945109 meters at 1446 seconds
lein test :only scratch.rocket-test/makes-orbit
FAIL in (makes-orbit) (rocket_test.clj:27)
expected: (not (crashed? trajectory))
actual: (not (not true))
Ran 2 tests containing 3 assertions.
1 failures, 0 errors.
Tests failed.Still crashed–but we increased our apoapsis from 750 kilometers to 4,598 kilometers. That’s plenty high, but we’re still not making orbit. Why? Because we’re going straight up, then straight back down. To orbit, we need to move sideways, around the earth.
Our spacecraft is shooting upwards, but in order to remain in orbit around the earth, it has to execute a second burn: an orbital injection maneuver. That injection maneuver is also called a circularization burn because it turns the orbit from an ascending parabola into a circle (or something roughly like it). We don’t need to be precise about circularization–any trajectory that doesn’t hit the planet will suffice. All we have to do is burn towards the horizon, once we get high enough.
To do that, we’ll need to enhance the rocket’s control software. We assumed that the rocket would always thrust in the +x direction; but now we’ll need to thrust in multiple directions. We’ll break up the engine force into two parts: thrust (how hard the rocket motor pushes) and orientation (which determines the direction the rocket is pointing.)
(defn unit-vector
"Scales coordinates to magnitude 1."
[coordinates]
(scale (/ (magnitude coordinates)) coordinates))
(defn engine-force
"The force vector, each component in Newtons, due to the rocket engine."
[craft]
(scale (thrust craft) (unit-vector (orientation craft))))We’re taking the orientation of the craft–some coordinates–and scaling it to be of length one with unit-vector. Then we’re scaling the orientation vector by the thrust, returning a thrust vector.
As we go back and redefine parts of the program, you might see an error like
Exception in thread "main" java.lang.RuntimeException: Unable to resolve symbol: unit-vector in this context, compiling:(scratch/rocket.clj:69:11)
at clojure.lang.Compiler.analyze(Compiler.java:6380)
at clojure.lang.Compiler.analyze(Compiler.java:6322)This is a stack trace from the Clojure compiler. It indicates that in scratch/rocket.clj, on line 69, column 11, we used the symbol unit-vector–but it didn’t have a meaning at that point in the program. Perhaps unit-vector is defined below that line. There are two ways to solve this.
Organize your functions so that the simple ones come first, and those that depend on them come later. Read this way, namespaces tell a story, progressing from smaller to bigger, more complex problems.
Sometimes, ordering functions this way is impossible, or would put related ideas too far apart. In this case you can (declare unit-vector) near the top of the namespace. This tells Clojure that unit-vector isn’t defined yet, but it’ll come later.
Now that we’ve broken up engine-force into thrust and orientation, we have to control the thrust properly for our two burns. We’ll start by defining the times for the initial ascent and circularization burn, expressed as vectors of start and end times, in seconds.
(def ascent
"The start and end times for the ascent burn."
[0 3000])
(def circularization
"The start and end times for the circularization burn."
[4000 1000])Now we’ll change the thrust by adjusting the rate of fuel consumption. Instead of burning at maximum until running out of fuel, we’ll execute two distinct burns.
(defn fuel-rate
"How fast is fuel, in kilograms/second, consumed by the craft?"
[craft]
(cond
; Out of fuel
(<= (:fuel-mass craft) 0)
0
; Ascent burn
(<= (first ascent) (:time craft) (last ascent))
(:max-fuel-rate craft)
; Circularization burn
(<= (first circularization) (:time craft) (last circularization))
(:max-fuel-rate craft)
; Shut down engines otherwise
:else 0))We’re using cond to express four distinct possibilities: that we’ve run out of fuel, executing either of the two burns, or resting with the engines shut down. Because the comparison function <= takes any number of arguments and asserts that they occur in order, expressing intervals like “the time is between the first and last times in the ascent” is easy.
Finally, we need to determine the direction to burn in. This one’s gonna require some tricky linear algebra. You don’t need to worry about the specifics here–the goal is to find out what direction the rocket should burn to fly towards the horizon, in a circle around the planet. We’re doing that by taking the rocket’s velocity vector, and flattening out the velocity towards or away from the planet. All that’s left is the direction the rocket is flying around the earth.
(defn dot-product
"Finds the inner product of two x, y, z coordinate maps.
See http://en.wikipedia.org/wiki/Dot_product."
[c1 c2]
(+ (* (:x c1) (:x c2))
(* (:y c1) (:y c2))
(* (:z c1) (:z c2))))
(defn projection
"The component of coordinate map a in the direction of coordinate map b.
See http://en.wikipedia.org/wiki/Vector_projection."
[a b]
(let [b (unit-vector b)]
(scale (dot-product a b) b)))
(defn rejection
"The component of coordinate map a *not* in the direction of coordinate map
b."
[a b]
(let [a' (projection a b)]
{:x (- (:x a) (:x a'))
:y (- (:y a) (:y a'))
:z (- (:z a) (:z a'))}))With the mathematical underpinnings ready, we’ll define the orientation control software:
(defn orientation
"What direction is the craft pointing?"
[craft]
(cond
; Initially, point along the *position* vector of the craft--that is
; to say, straight up, away from the earth.
(<= (first ascent) (:time craft) (last ascent))
(:position craft)
; During the circularization burn, we want to burn *sideways*, in the
; direction of the orbit. We'll find the component of our velocity
; which is aligned with our position vector (that is to say, the vertical
; velocity), and subtract the vertical component. All that's left is the
; *horizontal* part of our velocity.
(<= (first circularization) (:time craft) (last circularization))
(rejection (:velocity craft) (:position craft))
; Otherwise, just point straight ahead.
:else (:velocity craft)))For the ascent burn, we’ll push straight away from the planet. For circularization, we use the rejection function to find the part of the velocity around the planet, and thrust in that direction. By default, we’ll leave the rocket pointing in the direction of travel.
With these changes made, the rocket should execute two burns. Let’s re-run the tests and see.
aphyr@waterhouse:~/scratch$ lein test scratch.rocket-test
lein test scratch.rocket-test
Ran 2 tests containing 3 assertions.
0 failures, 0 errors.We finally did it! We’re rocket scientists!
(ns scratch.rocket)
;; Linear algebra for {:x 1 :y 2 :z 3} coordinate vectors.
(defn map-values
"Applies f to every value in the map m."
[f m]
(into {}
(map (fn [pair]
[(key pair) (f (val pair))])
m)))
(defn magnitude
"What's the radius of a given set of cartesian coordinates?"
[c]
; By the Pythagorean theorem...
(Math/sqrt (+ (Math/pow (:x c) 2)
(Math/pow (:y c) 2)
(Math/pow (:z c) 2))))
(defn scale
"Multiplies a map of x, y, and z coordinates by the given factor."
[factor coordinates]
(map-values (partial * factor) coordinates))
(defn unit-vector
"Scales coordinates to magnitude 1."
[coordinates]
(scale (/ (magnitude coordinates)) coordinates))
(defn dot-product
"Finds the inner product of two x, y, z coordinate maps. See
http://en.wikipedia.org/wiki/Dot_product"
[c1 c2]
(+ (* (:x c1) (:x c2))
(* (:y c1) (:y c2))
(* (:z c1) (:z c2))))
(defn projection
"The component of coordinate map a in the direction of coordinate map b.
See http://en.wikipedia.org/wiki/Vector_projection."
[a b]
(let [b (unit-vector b)]
(scale (dot-product a b) b)))
(defn rejection
"The component of coordinate map a *not* in the direction of coordinate map
b."
[a b]
(let [a' (projection a b)]
{:x (- (:x a) (:x a'))
:y (- (:y a) (:y a'))
:z (- (:z a) (:z a'))}))
;; Coordinate conversion
(defn cartesian->spherical
"Converts a map of Cartesian coordinates :x, :y, and :z to spherical
coordinates :r, :theta, and :phi."
[c]
(let [r (magnitude c)]
{:r r
:phi (Math/acos (/ (:z c) r))
:theta (Math/atan (/ (:y c) (:x c)))}))
(defn spherical->cartesian
"Converts spherical to Cartesian coordinates."
[c]
{:x (* (:r c) (Math/cos (:theta c)) (Math/sin (:phi c)))
:y (* (:r c) (Math/sin (:theta c)) (Math/sin (:phi c)))
:z (* (:r c) (Math/cos (:phi c)))})
;; The earth
(def earth-equatorial-radius
"Radius of the earth, in meters"
6378137)
(def earth-day
"Length of an earth day, in seconds."
86400)
(def earth-equatorial-speed
"How fast points on the equator move, relative to the center of the earth, in
meters/sec."
(/ (* 2 Math/PI earth-equatorial-radius)
earth-day))
(def g "Acceleration of gravity in meters/s^2" -9.8)
(def initial-space-center
"The initial position and velocity of the launch facility"
{:time 0
:position {:x earth-equatorial-radius
:y 0
:z 0}
:velocity {:x 0
:y earth-equatorial-speed
:z 0}})
;; Craft
(defn centaur
"The upper rocket stage.
http://en.wikipedia.org/wiki/Centaur_(rocket_stage)
http://www.astronautix.com/stages/cenaurde.htm"
[]
{:dry-mass 2361
:fuel-mass 13897
:isp 4354
:max-fuel-rate (/ 13897 470)})
(defn atlas-v
"The full launch vehicle. http://en.wikipedia.org/wiki/Atlas_V"
[next-stage]
{:dry-mass 50050
:fuel-mass 284450
:isp 3050
:max-fuel-rate (/ 284450 253)
:next-stage next-stage})
;; Flight control
(def ascent
"The start and end times for the ascent burn."
[0 300])
(def circularization
"The start and end times for the circularization burn."
[400 1000])
(defn orientation
"What direction is the craft pointing?"
[craft]
(cond
; Initially, point along the *position* vector of the craft--that is
; to say, straight up, away from the earth.
(<= (first ascent) (:time craft) (last ascent))
(:position craft)
; During the circularization burn, we want to burn *sideways*, in the
; direction of the orbit. We'll find the component of our velocity
; which is aligned with our position vector (that is to say, the vertical
; velocity), and subtract the vertical component. All that's left is the
; *horizontal* part of our velocity.
(<= (first circularization) (:time craft) (last circularization))
(rejection (:velocity craft) (:position craft))
; Otherwise, just point straight ahead.
:else (:velocity craft)))
(defn fuel-rate
"How fast is fuel, in kilograms/second, consumed by the craft?"
[craft]
(cond
; Out of fuel
(<= (:fuel-mass craft) 0)
0
; Ascent burn
(<= (first ascent) (:time craft) (last ascent))
(:max-fuel-rate craft)
; Circularization burn
(<= (first circularization) (:time craft) (last circularization))
(:max-fuel-rate craft)
; Shut down engines otherwise
:else 0))
(defn stage
"When fuel reserves are exhausted, separate stages. Otherwise, return craft
unchanged."
[craft]
(cond
; Still fuel left
(pos? (:fuel-mass craft))
craft
; No remaining stages
(nil? (:next-stage craft))
craft
; Stage!
:else
(merge (:next-stage craft)
(select-keys craft [:time :position :velocity]))))
;; Dynamics
(defn thrust
"How much force, in newtons, does the craft's rocket engines exert?"
[craft]
(* (fuel-rate craft) (:isp craft)))
(defn mass
"The total mass of a craft."
[craft]
(+ (:dry-mass craft) (:fuel-mass craft)))
(defn gravity-force
"The force vector, each component in Newtons, due to gravity."
[craft]
; Since force is mass times acceleration...
(let [total-force (* g (mass craft))]
(-> craft
; Now we'll take the craft's position
:position
; in spherical coordinates,
cartesian->spherical
; replace the radius with the gravitational force...
(assoc :r total-force)
; and transform back to Cartesian-land
spherical->cartesian)))
(declare altitude)
(defn engine-force
"The force vector, each component in Newtons, due to the rocket engine."
[craft]
; Debugging; useful for working through trajectories in detail.
; (println craft)
; (println "t " (:time craft) "alt" (altitude craft) "thrust" (thrust craft))
; (println "fuel" (:fuel-mass craft))
; (println "vel " (:velocity craft))
; (println "ori " (unit-vector (orientation craft)))
(scale (thrust craft) (unit-vector (orientation craft))))
(defn total-force
"Total force on a craft."
[craft]
(merge-with + (engine-force craft)
(gravity-force craft)))
(defn acceleration
"Total acceleration of a craft."
[craft]
(let [m (mass craft)]
(scale (/ m) (total-force craft))))
(defn step
[craft dt]
(let [craft (stage craft)]
(assoc craft
; Time advances by dt seconds
:time (+ dt (:time craft))
; We burn some fuel
:fuel-mass (- (:fuel-mass craft) (* dt (fuel-rate craft)))
; Our position changes based on our velocity
:position (merge-with + (:position craft)
(scale dt (:velocity craft)))
; And our velocity changes based on our acceleration
:velocity (merge-with + (:velocity craft)
(scale dt (acceleration craft))))))
;; Launch and flight
(defn prepare
"Prepares a craft for launch from an equatorial space center."
[craft]
(merge craft initial-space-center))
(defn trajectory
[dt craft]
"Returns all future states of the craft, at dt-second intervals."
(iterate #(step % 1) craft))
;; Analyzing trajectories
(defn altitude
"The height above the surface of the equator, in meters."
[craft]
(-> craft
:position
cartesian->spherical
:r
(- earth-equatorial-radius)))
(defn above-ground?
"Is the craft at or above the surface?"
[craft]
(<= 0 (altitude craft)))
(defn flight
"The above-ground portion of a trajectory."
[trajectory]
(take-while above-ground? trajectory))
(defn crashed?
"Does this trajectory crash into the surface before 10 hours are up?"
[trajectory]
(let [time-limit (* 10 3600)] ; 10 hours
(not (every? above-ground?
(take-while #(<= (:time %) time-limit) trajectory)))))
(defn crash-time
"Given a trajectory, returns the time the rocket impacted the ground."
[trajectory]
(:time (last (flight trajectory))))
(defn apoapsis
"The highest altitude achieved during a trajectory."
[trajectory]
(apply max (map altitude (flight trajectory))))
(defn apoapsis-time
"The time of apoapsis"
[trajectory]
(:time (apply max-key altitude (flight trajectory))))As written here, our first non-trivial program tells a story–though a different one than the process of exploration and refinement that brought the rocket to orbit. It builds from small, abstract ideas: linear algebra and coordinates; physical constants describing the universe for the simulation; and the basic outline of the spacecraft. Then we define the software controlling the rocket; the times for the burns, how much to thrust, in what direction, and when to separate stages. Using those control functions, we build a physics engine including gravity and thrust forces, and use Newton’s second law to build a basic Euler Method solver. Finally, we analyze the trajectories the solver produces to answer key questions: how high, how long, and did it explode?
We used Clojure’s immutable data structures–mostly maps–to represent the state of the universe, and defined pure functions to interpret those states and construct new ones. Using iterate, we projected a single state forward into an infinite timeline of the future–evaluated as demanded by the analysis functions. Though we pay a performance penalty, immutable data structures, pure functions, and lazy evaluation make simulating complex systems easier to reason about.
Had we written this simulation in a different language, different techniques might have come into play. In Java, C++, or Ruby, we would have defined a hierarchy of datatypes called classes, each one representing a small piece of state. We might define a Craft type, and created subtypes Atlas and Centaur. We’d create a Coordinate type, subdivided into Cartesian and Spherical, and so on. The types add complexity and rigidity, but also prevent mis-spellings, and can prevent us from interpreting, say, coordinates as craft or vice-versa.
To move the system forward in a language emphasizing mutable data structures, we would have updated the time and coordinates of a single craft in-place. This introduces additional complexity, because many of the changes we made depended on the current values of the craft. To ensure the correct ordering of calculations, we’d scatter temporary variables and explicit copies throughout the code, ensuring that functions didn’t see inconsistent pictures of the craft state. The mutable approach would likely be faster, but would still demand some copying of data, and sacrifice clarity.
More imperative languages place less emphasis on laziness, and make it harder to express ideas like map and take. We might have simulated the trajectory for some fixed time, constructing a history of all the intermediate results we needed, then analyzed it by moving explicitly from slot to slot in that history, checking if the craft had crashed, and so on.
Across all these languages, though, some ideas remain the same. We solve big problems by breaking them up into smaller ones. We use data structures to represent the state of the system, and functions to alter that state. Comments and docstrings clarify the story of the code, making it readable to others. Tests ensure the software is correct, and allow us to work piecewise towards a solution.
We know the spacecraft reached orbit, but we have no idea what that orbit looks like. Since the trajectory is infinite in length, we can’t ask about the entire history using max–but we know that all orbits have a high and low point. At the highest point, the difference between successive altitudes changes from increasing to decreasing, and at the lowest point, the difference between successive altitudes changes from decreasing to increasing. Using this technique, refine the apoapsis function to find the highest point using that inflection in altitudes–and write a corresponding periapsis function that finds the lowest point in the orbit. Display both periapsis and apoapsis in the test suite.
We assumed the force of gravity resulted in a constant 9.8 meter/second/second acceleration towards the earth, but in the real world, gravity falls off with the inverse square law. Using the mass of the earth, mass of the spacecraft, and Newton’s constant, refine the gravitational force used in this simulation to take Newton’s law into account. How does this affect the apoapsis?
We ignored the atmosphere, which exerts drag on the craft as it moves through the air. Write a basic air-density function which falls off with altitude. Make some educated guesses as to how much drag a real rocket experiences, and assume that the drag force is proportional to the square of the rocket’s velocity. Can your rocket still reach orbit?
Notice that the periapsis and apoapsis of the rocket are different. By executing the circularization burn carefully, can you make them the same–achieving a perfectly circular orbit? One way to do this is to pick an orbital altitude and velocity of a known satellite–say, the International Space Station–and write the control software to match that velocity at that altitude.
Writing software can be an exercise in frustration. Useless error messages, difficult-to-reproduce bugs, missing stacktrace information, obscure functions without documentation, and unmaintained libraries all stand in our way. As software engineers, our most useful skill isn’t so much knowing how to solve a problem as knowing how to explore a problem that we haven’t seen before. Experience is important, but even experienced engineers face unfamiliar bugs every day. When a problem doesn’t bear a resemblance to anything we’ve seen before, we fall back on general cognitive strategies to explore–and ultimately solve–the problem.
There’s an excellent book by the mathematician George Polya: How to Solve It, which tries to catalogue how successful mathematicians approach unfamiliar problems. When I catch myself banging my head against a problem for more than a few minutes, I try to back up and consider his principles. Sometimes, just taking the time to slow down and reflect can get me out of a rut.
Understand the problem.
Well obviously there’s a problem, right? The program failed to compile, or a test spat out bizarre numbers, or you hit an unexpected exception. But try to dig a little deeper than that. Just having a careful description of the problem can make the solution obvious.
Our audit program detected that users can double-withdraw cash from their
accounts.What does your program do? Chances are your program is large and complex, so try to isolate the problem as much as possible. Find preconditions where the error holds.
The problem occurs after multiple transfers between accounts.Identify specific lines of code from the stacktrace that are involved, specific data that’s being passed around. Can you find a particular function that’s misbehaving?
The balance transfer function sometimes doesn’t increase or decrease the
account values correctly.What are that function’s inputs and outputs? Are the inputs what you expected? What did you expect the result to be, given those arguments? It’s not enough to know “it doesn’t work” – you need to know exactly what should have happened. Try to find conditions where the function works correctly, so you can map out the boundaries of the problem.
Trying to transfer $100 from A to B works as expected, as does a transfer of
$50 from B to A. Running a million random transfers between accounts,
sequentially, results in correct balances. The problem only seems to happen in
production.If your function–or functions it calls–uses mutable state, like an agent, atom, or ref, the value of those references matters too. This is why you should avoid mutable state wherever possible: each mutable variable introduces another dimension of possible behaviors for your program. Print out those values when they’re read, and after they’re written, to get a description of what the function is actually doing. I am a huge believer in sprinkling (prn x) throughout one’s code to print how state evolves when the program runs.
Each balance is stored in a separate atom. When two transfers happen at the
same time involving the same accounts, the new value of one or both atoms may
not reflect the transfer correctly.Look for invariants: properties that should always be true of a program. Devise a test to look for where those invariants are broken. Consider each individual step of the program: does it preserve all the invariants you need? If it doesn’t, what ensures those invariants are restored correctly?
The total amount of money in the system should be constant–but sometimes changes!Draw diagrams, and invent a notation to talk about the problem. If you’re accessing fields in a vector, try drawing the vector as a set of boxes, and drawing the fields it accesses, step by step on paper. If you’re manipulating a tree, draw one! Figure out a way to write down the state of the system: in letters, numbers, arrows, graphs, whatever you can dream up.
Transferring $5 from A to B in transaction 1, and $5 from B to A in transaction 2:
Transaction | A | B
-------------+-----+-----
txn1 read | 10 | 10 ; Transaction 1 sees 10, 10
txn1 write A | 5 | 10 ; A and B now out-of-sync
txn2 read | 5 | 10 ; Transaction 2 sees 5, 10
txn1 write B | 5 | 15 ; Transaction 1 completes
txn2 write A | 10 | 15 ; Transaction 2 writes based on out-of-sync read
txn2 write B | 5 | 5 ; Should have been 10, 10!This doesn’t solve the problem, but helps us explore the problem in depth. Sometimes this makes the solution obvious–other times, we’re just left with a pile of disjoint facts. Even if things look jumbled-up and confusing, don’t despair! Exploring gives the brain the pieces; it’ll link them together over time.
Armed with a detailed description of the problem, we’re much better equipped to solve it.
Our brains are excellent pattern-matchers, but not that great at tracking abstract logical operations. Try changing your viewpoint: rotating the problem into a representation that’s a little more tractable for your mind. Is there a similar problem you’ve seen in the past? Is this a well-known problem?
Make sure you know how to check the solution. With the problem isolated to a single function, we can write a test case that verifies the account balances are correct. Then we can experiment freely, and have some confidence that we’ve actually found a solution.
Can you solve a related problem? If only concurrent transfers trigger the problem, could we solve the issue by ensuring transactions never take place concurrently–e.g. by wrapping the operation in a lock? Could we solve it by logging all transactions, and replaying the log? Is there a simpler variant of the problem that might be tractable–maybe one that always overcounts, but never undercounts?
Consider your assumptions. We rely on layers of abstraction in writing software–that changing a variable is atomic, that lexical variables don’t change, that adding 1 and 1 always gives 2. Sometimes, parts of the computer fail to guarantee those abstractions hold. The CPU might–very rarely–fail to divide numbers correctly. A library might, for supposedly valid input, spit out a bad result. A numeric algorithm might fail to converge, and spit out wrong numbers. To avoid questioning everything, start in your own code, and work your way down to the assumptions themselves. See if you can devise tests that check the language or library is behaving as you expect.
Can you avoid solving the problem altogether? Is there a library, database, or language feature that does transaction management for us? Is integrating that library worth the reduced complexity in our application?
We’re not mathematicians; we’re engineers. Part theorist, yes, but also part mechanic. Some problems take a more abstract approach, and others are better approached by tapping it with a wrench and checking the service manual. If other people have solved your problem already, using their solution can be much simpler than devising your own.
Can you think of a way to get more diagnostic information? Perhaps we could log more data from the functions that are misbehaving, or find a way to dump and replay transactions from the live program. Some problems disappear when instrumented; these are the hardest to solve, but also the most rewarding.
Combine key phrases in a Google search: the name of the library you’re using, the type of exception thrown, any error codes or log messages. Often you’ll find a StackOverflow result, a mailing list post, or a Github issue that describes your problem. This works well when you know the technical terms for your problem–in our case, that we’re performing a atomic, transactional transfer between two variables. Sometimes, though, you don’t know the established names for your problem, and have to resort to blind queries like “variables out of sync” or “overwritten data”–which are much more difficult.
When you get stuck exploring on your own, try asking for help. Collect your description of the problem, the steps you took, and what you expected the program to do. Include any stacktraces or error messages, log files, and the smallest section of source code required to reproduce the problem. Also include the versions of software used–in Clojure, typically the JVM version (java -version), Clojure version (project.clj), and any other relevant library versions.
If the project has a Github page or public issue tracker, like Jira, you can try filing an issue there. Here’s a particularly well-written issue filed by a user on one of my projects. Note that this user included installation instructions, the command they ran, and the stacktrace it printed. The more specific a description you provide, the easier it is for someone else to understand your problem and help!
Sometimes you need to talk through a problem interactively. For that, I prefer IRC–many projects have a channel on the Freenode IRC network where you can ask basic questions. Remember to be respectful of the channel’s time; there may be hundreds of users present, and they have to sort through everything you write. Paste your problem description into a pastebin like Gist, then mention the link in IRC with a short–say a few sentences–description of the problem. I try asking in a channel devoted to a specific library or program first, then back off to a more general channel, like #clojure. There’s no need to ask “Can I ask a question” first–just jump in.
Since the transactional problem we’ve been exploring seems like a general issue with atoms, I might ask in #clojure
aphyr > Hi! Does anyone know the right way to change multiple atoms at the same time?
aphyr > This function and test case (http://gist.github.com/...) seems to double-
or under-count when invoked concurrently.Finally, you can join the project’s email list, and ask your question there. Turnaround times are longer, but you’ll often find a more in-depth response to your question via email. This applies especially if you and the maintainer are in different time zones, or if they’re busy with life. You can also ask specific problems on StackOverflow or other message boards; users there can be incredibly helpful.
Remember, other engineers are taking time away from their work, family, friends, and hobbies to help you. It’s always polite to give them time to answer first–they may have other priorities. A sincere thank-you is always appreciated–as is paying it forward by answering other users’ questions on the list or channel!
Sadly, some women, LGBT people, and so on experience harassment on IRC or in other discussion circles. They may be asked inappropriate personal questions, insulted, threatened, assumed to be straight, to be a man, and so on. Sometimes other users will attack questioners for inexperience. Exclusion can be overt (“Read the fucking docs, faggot!”) or more subtle (“Hey dudes, what’s up?”). It only takes one hurtful experience this to sour someone on an entire community.
If this happens to you, place your own well-being first. You are not obligated to fix anyone else’s problems, or to remain in a social context that makes you uncomfortable.
That said, be aware the other people in a channel may not share your culture. English may not be their main language, or they may have said something hurtful without realizing its impact. Explaining how the comment made you feel can jar a well-meaning but unaware person into reconsidering their actions.
Other times, people are just mean–and it only takes one to ruin everybody’s day. When this happens, you can appeal to a moderator. On IRC, moderators are sometimes identified by an @ sign in front of their name; on forums, they may have a special mark on their username or profile. Large projects may have an official policy for reporting abuse on their website or in the channel topic. If there’s no policy, try asking whoever seems in charge for help. Most projects have a primary maintainer or community manager with the power to mute or ban malicious users.
Again, these ways of dealing with abuse are optional. You have no responsibility to provide others with endless patience, and it is not your responsibility to fix a toxic culture. You can always log off and try something else. There are many communities which will welcome and support you–it may just take a few tries to find the right fit.
If you don’t find community, you can build it. Starting your own IRC channel, mailing list, or discussion group with a few friends can be a great way to help each other learn in a supportive environment. And if trolls ever come calling, you’ll be able to ban them personally.
Now, back to problem-solving.
Sometimes we can make a quick fix in the codebase, test it by hand, and move on. But for more serious problems, we’ll need a more involved process. I always try to get a reproducible test suite–one that runs in a matter of seconds–so that I can continually check my work.
Persist. Many problems require grinding away for some time. Mix blind experimentation with sitting back and planning. Periodically re-evaluate your work–have you made progress? Identified a sub-problem that can be solved independently? Developed a new notation?
If you get stuck, try a new tack. Save your approach as a comment or using git stash, and start fresh. Maybe using a different concurrency primitive is in order, or rephrasing the data structure entirely. Take a reading break and review the documentation for the library you’re trying to use. Read the source code for the functions you’re calling–even if you don’t understand exactly what it does, it might give you clues to how things work under the hood.
Bounce your problem off a friend. Grab a sheet of paper or whiteboard, describe the problem, and work through your thinking with that person. Their understanding of the problem might be totally off-base, but can still give you valuable insight. Maybe they know exactly what the problem is, and can point you to a solution in thirty seconds!
Finally, take a break. Go home. Go for a walk. Lift heavy, run hard, space out, drink with your friends, practice music, read a book. Just before sleep, go over the problem once more in your head; I often wake up with a new algorithm or new questions burning to get out. Your unconscious mind can come up with unexpected insights if given time away from the problem!
Some folks swear by time in the shower, others by hiking, or with pen and paper in a hammock. Find what works for you! The important thing seems to be giving yourself away from struggling with the problem.
Chances are you’ll know as soon as your solution works. The program compiles, transactions generate the correct amounts, etc. Now’s an important time to solidify your work.
Bolster your tests. You may have made the problem less likely, but not actually solved it. Try a more aggressive, randomized test; one that runs for longer, that generates a broader class of input. Try it on a copy of the production workload before deploying your change.
Identify why the new system works. Pasting something in from StackOverflow may get you through the day, but won’t help you solve similar problems in the future. Try to really understand why the program went wrong, and how the new pieces work together to prevent the problem. Is there a more general underlying problem? Could you generalize your technique to solve a related problem? If you’ll encounter this type of issue frequently, could you build a function or library to help build other solutions?
Document the solution. Write down your description of the problem, and why your changes fix it, as comments in the source code. Use that same description of the solution in your commit message, or attach it as a comment to the resources you used online, so that other people can come to the same understanding.
With these general strategies in mind, I’d like to talk specifically about the debugging Clojure code–especially understanding its stacktraces. Consider this simple program for baking cakes:
(ns scratch.debugging)
(defn bake
"Bakes a cake for a certain amount of time, returning a cake with a new
:tastiness level."
[pie temp time]
(assoc pie :tastiness
(condp (* temp time) <
400 :burned
350 :perfect
300 :soggy)))And in the REPL
user=> (bake {:flavor :blackberry} 375 10.25)
ClassCastException java.lang.Double cannot be cast to clojure.lang.IFn scratch.debugging/bake (debugging.clj:8)This is not particularly helpful. Let’s print a full stacktrace using pst:
user=> (pst)
ClassCastException java.lang.Double cannot be cast to clojure.lang.IFn
scratch.debugging/bake (debugging.clj:8)
user/eval1223 (form-init4495957503656407289.clj:1)
clojure.lang.Compiler.eval (Compiler.java:6619)
clojure.lang.Compiler.eval (Compiler.java:6582)
clojure.core/eval (core.clj:2852)
clojure.main/repl/read-eval-print--6588/fn--6591 (main.clj:259)
clojure.main/repl/read-eval-print--6588 (main.clj:259)
clojure.main/repl/fn--6597 (main.clj:277)
clojure.main/repl (main.clj:277)
clojure.tools.nrepl.middleware.interruptible-eval/evaluate/fn--591 (interruptible_eval.clj:56)
clojure.core/apply (core.clj:617)
clojure.core/with-bindings* (core.clj:1788)The first line tells us the type of the error: a ClassCastException. Then there’s some explanatory text: we can’t cast a java.lang.Double to a clojure.lang.IFn. The indented lines show the functions that led to the error. The first line is the deepest function, where the error actually occurred: the bake function in the scratch.debugging namespace. In parentheses is the file name (debugging.clj) and line number (8) from the code that caused the error. Each following line shows the function that called the previous line. In the REPL, our code is invoked from a special function compiled by the REPL itself–with an automatically generated name like user/eval1223, and that function is invoked by the Clojure compiler, and the REPL tooling. Once we see something like Compiler.eval at the repl, we can generally skip the rest.
As a general rule, we want to look at the deepest (earliest) point in the stacktrace that we wrote. Sometimes an error will arise from deep within a library or Clojure itself–but it was probably invoked by our code somewhere. We’ll skim down the lines until we find our namespace, and start our investigation at that point.
Our case is simple: bake.clj, on line 8, seems to be the culprit.
Now let’s consider the error itself: ClassCastException: java.lang.Double cannot be cast to clojure.lang.IFn. This implies we had a Double and tried to cast it to an IFn–but what does “cast” mean? For that matter, what’s a Double, or an IFn?
A quick google search for java.lang.Double reveals that it’s a class (a Java type) with some basic documentation. “The Double class wraps a value of the primitive type double in an object” is not particularly informative–but the “class hierarchy” at the top of the page shows that a Double is a kind of java.lang.Number. Let’s experiment at the REPL:
Indeed: decimal numbers in Clojure appear to be doubles. One of the expressions in that condp call was probably a decimal. At first we might suspect the literal values 300, 350, or 400–but those are Longs, not Doubles. The only Double we passed in was the time duration 10.25–which appears in condp as (* temp time). That first argument was a Double, but should have been an IFn.
What the heck is an IFn? Its source code has a comment:
IFn provides complete access to invoking any of Clojure’s API’s. You can also access any other library written in Clojure, after adding either its source or compiled form to the classpath.
So IFn has to do with invoking Clojure’s API. Ah–Fn probably stands for function–and this class is chock full of things like invoke(Object arg1, Object arg2). That suggests that IFn is about calling functions. And the I? Google suggests it’s a Java convention for an interface–whatever that is. Remember, we don’t have to understand everything–just enough to get by. There’s plenty to explore later.
Let’s check our hypothesis in the repl:
user=> (instance? clojure.lang.IFn 2.5)
false
user=> (instance? clojure.lang.IFn conj)
true
user=> (instance? clojure.lang.IFn (fn [x] (inc x)))
trueSo Doubles aren’t IFns–but Clojure built-in functions, and anonymous functions, both are. Let’s double-check the docs for condp again:
user=> (doc condp)
-------------------------
clojure.core/condp
([pred expr & clauses])
Macro
Takes a binary predicate, an expression, and a set of clauses.
Each clause can take the form of either:
test-expr result-expr
test-expr :>> result-fn
Note :>> is an ordinary keyword.
For each clause, (pred test-expr expr) is evaluated. If it returns
logical true, the clause is a match. If a binary clause matches, the
result-expr is returned, if a ternary clause matches, its result-fn,
which must be a unary function, is called with the result of the
predicate as its argument, the result of that call being the return
value of condp. A single default expression can follow the clauses,
and its value will be returned if no clause matches. If no default
expression is provided and no clause matches, an
IllegalArgumentException is thrown.cljThat’s a lot to take in! No wonder we got it wrong! We’ll take it slow, and look at the arguments.
Our pred was (* temp time) (a Double), and our expr was the comparison function <. For each clause, (pred test-expr expr) is evaluated, so that would expand to something like
Which evaluates to something like
But this isn’t a valid Lisp program! It starts with a number, not a function. We should have written (< 123.45 400). Our arguments are backwards!
(defn bake
"Bakes a cake for a certain amount of time, returning a cake with a new
:tastiness level."
[pie temp time]
(assoc pie :tastiness
(condp < (* temp time)
400 :burned
350 :perfect
300 :soggy)))
user=> (use 'scratch.debugging :reload)
nil
user=> (bake {:flavor :chocolate} 375 10.25)
{:tastiness :burned, :flavor :chocolate}
user=> (bake {:flavor :chocolate} 450 0.8)
{:tastiness :perfect, :flavor :chocolate}Mission accomplished! We read the stacktrace as a path to a part of the program where things went wrong. We identified the deepest part of that path in our code, and looked for a problem there. We discovered that we had reversed the arguments to a function, and after some research and experimentation in the REPL, figured out the right order.
An aside on types: some languages have a stricter type system than Clojure’s, in which the types of variables are explicitly declared in the program’s source code. Those languages can detect type errors–when a variable of one type is used in place of another, incompatible, type–and offer more precise feedback. In Clojure, the compiler does not generally enforce types at compile time, which allows for significant flexibility–but requires more rigorous testing to expose these errors.
The stacktrace shows us a path through the program, moving downwards through functions. However, that path may not be straightforward. When data is handed off from one part of the program to another, the stacktrace may not show the origin of an error. When functions are handed off from one part of the program to another, the resulting traces can be tricky to interpret indeed.
For instance, say we wanted to make some picture frames out of wood, but didn’t know how much wood to buy. We might sketch out a program like this:
(defn perimeter
"Given a rectangle, returns a vector of its edge lengths."
[rect]
[(:x rect)
(:y rect)
(:z rect)
(:y rect)])
(defn frame
"Given a mat width, and a photo rectangle, figure out the size of the frame
required by adding the mat width around all edges of the photo."
[mat-width rect]
(let [margin (* 2 rect)]
{:x (+ margin (:x rect))
:y (+ margin (:y rect))}))
(def failure-rate
"Sometimes the wood is knotty or we screw up a cut. We'll assume we need a
spare segment once every 8."
1/8)
(defn spares
"Given a list of segments, figure out roughly how many of each distinct size
will go bad, and emit a sequence of spare segments, assuming we screw up
`failure-rate` of them."
[segments]
(->> segments
; Compute a map of each segment length to the number of
; segments we'll need of that size.
frequencies
; Make a list of spares for each segment length,
; based on how often we think we'll screw up.
(mapcat (fn [ [segment n]]
(repeat (* failure-rate n)
segment)))))
(def cut-size
"How much extra wood do we need for each cut? Let's say a mitred cut for a
1-inch frame needs a full inch."
1)
(defn total-wood
[mat-width photos]
"Given a mat width and a collection of photos, compute the total linear
amount of wood we need to buy in order to make frames for each, given a
2-inch mat."
(let [segments (->> photos
; Convert photos to frame dimensions
(map (partial frame mat-width))
; Convert frames to segments
(mapcat perimeter))]
; Now, take segments
(->> segments
; Add the spares
(concat (spares segments))
; Include a cut between each segment
(interpose cut-size)
; And sum the whole shebang.
(reduce +))))
(->> [{:x 8
:y 10}
{:x 10
:y 8}
{:x 20
:y 30}]
(total-wood 2)
(println "total inches:"))Running this program yields a curious stacktrace. We’ll print the full trace (not the shortened one that comes with pst) for the last exception *e with the .printStackTrace function.
user=> (.printStackTrace *e)
java.lang.ClassCastException: clojure.lang.PersistentArrayMap cannot be cast to java.lang.Number, compiling:(scratch/debugging.clj:73:23)
at clojure.lang.Compiler.load(Compiler.java:7142)
at clojure.lang.RT.loadResourceScript(RT.java:370)
at clojure.lang.RT.loadResourceScript(RT.java:361)
at clojure.lang.RT.load(RT.java:440)
at clojure.lang.RT.load(RT.java:411)
...
at java.lang.Thread.run(Thread.java:745)
Caused by: java.lang.ClassCastException: clojure.lang.PersistentArrayMap cannot be cast to java.lang.Number
at clojure.lang.Numbers.multiply(Numbers.java:146)
at clojure.lang.Numbers.multiply(Numbers.java:3659)
at scratch.debugging$frame.invoke(debugging.clj:26)
at clojure.lang.AFn.applyToHelper(AFn.java:156)
at clojure.lang.AFn.applyTo(AFn.java:144)
at clojure.core$apply.invoke(core.clj:626)
at clojure.core$partial$fn__4228.doInvoke(core.clj:2468)
at clojure.lang.RestFn.invoke(RestFn.java:408)
at clojure.core$map$fn__4245.invoke(core.clj:2557)
at clojure.lang.LazySeq.sval(LazySeq.java:40)
at clojure.lang.LazySeq.seq(LazySeq.java:49)
at clojure.lang.RT.seq(RT.java:484)
at clojure.core$seq.invoke(core.clj:133)
at clojure.core$map$fn__4245.invoke(core.clj:2551)
at clojure.lang.LazySeq.sval(LazySeq.java:40)
at clojure.lang.LazySeq.seq(LazySeq.java:49)
at clojure.lang.RT.seq(RT.java:484)
at clojure.core$seq.invoke(core.clj:133)
at clojure.core$apply.invoke(core.clj:624)
at clojure.core$mapcat.doInvoke(core.clj:2586)
at clojure.lang.RestFn.invoke(RestFn.java:423)
at scratch.debugging$total_wood.invoke(debugging.clj:62)
...First: this trace has two parts. The top-level error (a CompilerException) appears first, and is followed by the exception that caused the CompilerException: a ClassCastException. This makes the stacktrace read somewhat out of order, since the deepest part of the trace occurs in the first line of the last exception. We read C B A then F E D. This is an old convention in the Java language, and the cause of no end of frustration.
Notice that this representation of the stacktrace is less friendly than (pst). We’re seeing the Java Virtual Machine (JVM)’s internal representation of Clojure functions, which look like clojure.corepartialfn__4228.doInvoke. This corresponds to the namespace clojure.core, in which there is a function called partial, inside of which is an anonymous function, here named fn__4228. Calling a Clojure function is written, in the JVM, as .invoke or .doInvoke.
So: the root cause was a ClassCastException, and it tells us that Clojure expected a java.lang.Number, but found a PersistentArrayMap. We might guess that PersistentArrayMap is something to do with the map data structure, which we used in this program:
And we’d be right. We can also tell, by reading down the stacktrace looking for our scratch.debugging namespace, where the error took place: scratch.debugging$frame, on line 26.
There’s our multiplication operation *, which we might assume expands to clojure.lang.Numbers.multiply. But the path to the error is odd.
In total-wood, we call (map (partial frame mat-width) photos) right away, so we’d expect the stacktrace to go from total-wood to map to frame. But this is not what happens. Instead, total-wood invokes something called RestFn–a piece of Clojure plumbing–which in turn calls mapcat.
at clojure.core$mapcat.doInvoke(core.clj:2586)
at clojure.lang.RestFn.invoke(RestFn.java:423)
at scratch.debugging$total_wood.invoke(debugging.clj:62)Why doesn’t total-wood call map first? Well it did–but map doesn’t actually apply its function to anything in the photos vector when invoked. Instead, it returns a lazy sequence–one which applies frame only when elements are asked for.
Inside each LazySeq is a box containing a function. When you ask a LazySeq for its first value, it calls that function to return a new sequence–and that’s when frame gets invoked. What we’re seeing in this stacktrace is the LazySeq internal machinery at work–mapcat asks it for a value, and the LazySeq asks map to generate that value.
at clojure.core$partial$fn__4228.doInvoke(core.clj:2468)
at clojure.lang.RestFn.invoke(RestFn.java:408)
at clojure.core$map$fn__4245.invoke(core.clj:2557)
at clojure.lang.LazySeq.sval(LazySeq.java:40)
at clojure.lang.LazySeq.seq(LazySeq.java:49)
at clojure.lang.RT.seq(RT.java:484)
at clojure.core$seq.invoke(core.clj:133)
at clojure.core$map$fn__4245.invoke(core.clj:2551)
at clojure.lang.LazySeq.sval(LazySeq.java:40)
at clojure.lang.LazySeq.seq(LazySeq.java:49)
at clojure.lang.RT.seq(RT.java:484)
at clojure.core$seq.invoke(core.clj:133)
at clojure.core$apply.invoke(core.clj:624)
at clojure.core$mapcat.doInvoke(core.clj:2586)
at clojure.lang.RestFn.invoke(RestFn.java:423)
at scratch.debugging$total_wood.invoke(debugging.clj:62)In fact we pass through map’s laziness twice here: a quick peek at (source mapcat) shows that it expands into a map call itself, and then there’s a second map: the one we created in in total-wood. Then an odd thing happens–we hit something called clojure.corepartialfn__4228.
The frame function takes two arguments: a mat width and a photo. We wanted a function that takes just one argument: a photo. (partial frame mat-width) took mat-width and generated a new function which takes one arg–call it photo–and calls (frame mad-width photo). That automatically generated function, returned by partial, is what map uses to generate new elements of its sequence on demand.
user=> (partial + 1)
#<core$partial$fn__4228 clojure.core$partial$fn__4228@243634f2>
user=> ((partial + 1) 4)
5That’s why we see control flow through clojure.corepartialfn__4228 (an anonymous function defined inside clojure.core/partial) on the way to frame.
Caused by: java.lang.ClassCastException: clojure.lang.PersistentArrayMap cannot be cast to java.lang.Number
at clojure.lang.Numbers.multiply(Numbers.java:146)
at clojure.lang.Numbers.multiply(Numbers.java:3659)
at scratch.debugging$frame.invoke(debugging.clj:26)
at clojure.lang.AFn.applyToHelper(AFn.java:156)
at clojure.lang.AFn.applyTo(AFn.java:144)
at clojure.core$apply.invoke(core.clj:626)
at clojure.core$partial$fn__4228.doInvoke(core.clj:2468)And there’s our suspect! scratch.debugging/frame, at line 26. To return to that line again:
(defn frame
"Given a mat width, and a photo rectangle, figure out the size of the frame
required by adding the mat width around all edges of the photo."
[mat-width rect]
(let [margin (* 2 mat-width)]
{:x (+ margin (:x rect))
:y (+ margin (:y rect))}))I believe we’ve fixed the bug, then. Let’s give it a shot!
The unbearable lightness of nil There’s one more bug lurking in this program. This one’s stacktrace is short.
user=> (use 'scratch.debugging :reload)
CompilerException java.lang.NullPointerException, compiling:(scratch/debugging.clj:73:23)
user=> (pst)
CompilerException java.lang.NullPointerException, compiling:(scratch/debugging.clj:73:23)
clojure.lang.Compiler.load (Compiler.java:7142)
clojure.lang.RT.loadResourceScript (RT.java:370)
clojure.lang.RT.loadResourceScript (RT.java:361)
clojure.lang.RT.load (RT.java:440)
clojure.lang.RT.load (RT.java:411)
clojure.core/load/fn--5066 (core.clj:5641)
clojure.core/load (core.clj:5640)
clojure.core/load-one (core.clj:5446)
clojure.core/load-lib/fn--5015 (core.clj:5486)
clojure.core/load-lib (core.clj:5485)
clojure.core/apply (core.clj:626)
clojure.core/load-libs (core.clj:5524)
Caused by:
NullPointerException
clojure.lang.Numbers.ops (Numbers.java:961)
clojure.lang.Numbers.add (Numbers.java:126)
clojure.core/+ (core.clj:951)
clojure.core.protocols/fn--6086 (protocols.clj:143)
clojure.core.protocols/fn--6057/G--6052--6066 (protocols.clj:19)
clojure.core.protocols/seq-reduce (protocols.clj:27)
clojure.core.protocols/fn--6078 (protocols.clj:53)
clojure.core.protocols/fn--6031/G--6026--6044 (protocols.clj:13)
clojure.core/reduce (core.clj:6287)
scratch.debugging/total-wood (debugging.clj:69)
scratch.debugging/eval1560 (debugging.clj:81)
clojure.lang.Compiler.eval (Compiler.java:6703)On line 69, total-wood calls reduce, which dives through a series of functions from clojure.core.protocols before emerging in +: the function we passed to reduce. Reduce is trying to combine two elements from its collection of wood segments using +, but one of them was nil. Clojure calls this a NullPointerException. In total-wood, we constructed the sequence of segments this way:
(let [segments (->> photos
; Convert photos to frame dimensions
(map (partial frame mat-width))
; Convert frames to segments
(mapcat perimeter))]
; Now, take segments
(->> segments
; Add the spares
(concat (spares segments))
; Include a cut between each segment
(interpose cut-size)
; And sum the whole shebang.
(reduce +))))Where did the nil value come from? The stacktrace doesn’t say, because the sequence reduce is traversing didn’t have any problem producing the nil. reduce asked for a value and the sequence happily produced a nil. We only had a problem when it came time to combine the nil with the next value, using +.
A stacktrace like this is something like a murder mystery: we know the program died in the reducer, that it was shot with a +, and the bullet was a nil–but we don’t know where the bullet came from. The trail runs cold. We need more forensic information–more hints about the nil’s origin–to find the culprit.
Again, this is a class of error largely preventable with static type systems. If you have worked with a statically typed language in the past, it may be interesting to consider that almost every Clojure function takes Option[A] and does something more-or-less sensible, returning Option[B]. Whether the error propagates as a nil or an Option, there can be similar difficulties in localizing the cause of the problem.
Let’s try printing out the state as reduce goes along:
(->> segments
; Add the spares
(concat (spares segments))
; Include a cut between each segment
(interpose cut-size)
; And sum the whole shebang.
(reduce (fn [acc x] (prn acc x) (+ acc x))))))
user=> (use 'scratch.debugging :reload)
12 1
13 14
27 1
28 nil
CompilerException java.lang.NullPointerException, compiling:(scratch/debugging.clj:73:56) Not every value is nil! There’s a 14 there which looks like a plausible segment for a frame, and two one-inch buffers from cut-size. We can rule out interpose because it inserts a 1 every time, and that 1 reduces correctly. But where’s that nil coming from? Is from segments or (spares segments)?
(let [segments (->> photos
; Convert photos to frame dimensions
(map (partial frame mat-width))
; Convert frames to segments
(mapcat perimeter))]
(prn :segments segments)
user=> (use 'scratch.debugging :reload)
:segments (12 14 nil 14 14 12 nil 12 24 34 nil 34)It is present in segments. Let’s trace it backwards through the sequence’s creation. It’d be handy to have a function like prn that returned its input, so we could spy on values as they flowed through the ->> macro.
(defn spy
[& args]
(apply prn args)
(last args))
(let [segments (->> photos
; Convert photos to frame dimensions
(map (partial frame mat-width))
(spy :frames)
; Convert frames to segments
(mapcat perimeter))]
user=> (use 'scratch.debugging :reload)
:frames ({:x 12, :y 14} {:x 14, :y 12} {:x 24, :y 34})
:segments (12 14 nil 14 14 12 nil 12 24 34 nil 34)Ah! So the frames are intact, but the perimeters are bad. Let’s check the perimeter function:
(defn perimeter
"Given a rectangle, returns a vector of its edge lengths."
[rect]
[(:x rect)
(:y rect)
(:z rect)
(:y rect)])Spot the typo? We wrote :z instead of :x. Since the frame didn’t have a :z field, it returned nil! That’s the origin of our NullPointerException. With the bug fixed, we can re-run and find:
Whallah!
As we solve more and more problems, we get faster at debugging–at skipping over irrelevant log data, figuring out exactly what input was at fault, knowing what terms to search for, and developing a network of peers and mentors to ask for help. But when we encounter unexpected bugs, it can help to fall back on a family of problem-solving tactics.
We explore the problem thoroughly, localizing it to a particular function, variable, or set of inputs. We identify the boundaries of the problem, carving away parts of the system that work as expected. We develop new notation, maps, and diagrams of the problem space, precisely characterizing it in a variety of modes.
With the problem identified, we search for extant solutions–or related problems others have solved in the past. We trawl through issue trackers, mailing list posts, blogs, and forums like Stackoverflow, or, for more theoretical problems, academic papers, Mathworld, and Wikipedia, etc. If searching reveals nothing, we try rephrasing the problem, relaxing the constraints, adding debugging statements, and solving smaller subproblems. When all else fails, we ask for help from our peers, or from the community in IRC, mailing lists, and so on, or just take a break.
We learned to explore Clojure stacktraces as a trail into our programs, leading to the place where an error occurred. But not all paths are linear, and we saw how lazy operations and higher-order functions create inversions and intermediate layers in the stacktrace. Then we learned how to debug values that were distant from the trace, by adding logging statements and working our way closer to the origin.
Programming languages and us, their users, are engaged in a continual dialogue. We may speak more formally, verbosely, with many types and defensive assertions–or we may speak quickly, generally, in fuzzy terms. The more precise we are with the specifications of our program’s types, the more the program can assist us when things go wrong. Conversely, those specifications harden our programs into strong but rigid forms, and rigid structures are harder to bend into new shapes.
In Clojure we strike a more dynamic balance: we speak in generalities, but we pay for that flexibility. Our errors are harder to trace to their origins. While the Clojure compiler can warn us of some errors, like mis-spelled variable names, it cannot (without a library like core.typed) tell us when we have incorrectly assumed an object will be of a certain type. Even very rigid languages, like Haskell, cannot identify some errors, like reversing the arguments to a subtraction function. Some tests are always necessary, though types are a huge boon.
No matter what language we write in, we use a balance of types and tests to validate our assumptions, both when the program is compiled and when it is run.
The errors that arise in compilation or runtime aren’t rebukes so much as hints. Don’t despair! They point the way towards understanding one’s program in more detail–though the errors may be cryptic. Over time we get better at reading our language’s errors and making our programs more robust.
In this chapter, we’ll discuss some of Clojure’s mechanisms for polymorphism: writing programs that do different things depending on what kind of inputs they receive. We’ll show ways to write open functions, which can be extended to new conditions later on, without changing their original definitions. Along the way, we’ll investigate Clojure’s type system in more detail–discussing interfaces, protocols, how to construct our own datatypes, and the relationships between types which let us write flexible programs.
Thus far, our functions have taken one type of input. For example:
(defn append
"Adds an element x to the end of a vector v."
[v x]
(conj v x))
scratch.polymorphism=> (append [1 2] 3)
[1 2 3]But we might want to append to more than vectors. What if we wanted to append something to the end of a list?
Since conj prepends to lists, our append function doesn’t work correctly here. We could redefine append in a way that works for both vectors and lists–for instance, using concat:
(defn append-concat
"Adds an element x to the end of a collection coll by concatenating a
single-element list (x) to the end of coll."
[coll x]
(concat coll (list x)))But this is less than ideal: concat produces a wrapper object every time we call append-concat, which introduces unnecessary overhead when working with vectors. What we would like is a function which does different things to different types of inputs. This is the heart of polymorphism.
We have a function type which returns the type of an object. What if append asked for the type of collection it was being asked to append to, and did different things based on that type? Let’s check the types of lists and vectors:
Okay, so we could try checking whether the type of our collection is a PersistentVector, and if so, use conj to append an element efficiently!
(defn append
"Adds an element x to the end of a collection coll. Coll may be either a
vector or a list."
[coll x]
(condp = (type coll)
clojure.lang.PersistentVector
(conj coll x)
clojure.lang.PersistentList
(concat coll (list x))))As an aside: we’re using condp = instead of case, even though case might seem like the obvious solution here. That’s because case uses optimizations which require that each case is a a compile-time constant, and classes like clojure.lang.PersistentVector aren’t actually constant in that sense. Don’t worry too much about this—it’s not important for understanding this chapter. The important question is: does this approach of checking the type at runtime work? Can we append to both vectors and lists?
It does! We’ve written a polymorphic function which can take two different kinds of input, and does different things depending on what type of input was provided. Just to confirm, let’s try an empty list:
scratch.polymorphism=> (append '() 3)
IllegalArgumentException No matching clause: class
clojure.lang.PersistentList$EmptyList scratch.polymorphism/append
(polymorphism.clj:7)Oh shoot. Are empty lists… a different type?
Indeed, they are. Empty lists have a special type in Clojure: clojure.lang.PersistentList is not the same type as clojure.lang.PersistentList$EmptyList. Why, then, are they mostly interchangeable? What is it that lets () and (1 2 3) behave as if they were both the same type of thing?
Most languages have a notion of a relationship between types. The exact nature of these relationships is complex and language-specific, but informally, most languages have a way to express that type A is a subtype of type B, and conversely, B is a supertype of A. For instance, type Cat might be a subtype of type Animal. This allows us to write functions which depend only on properties of Animal, in such a way that they work automatically on Cats, Dogs, Fish, and so on. This is another form of polymorphism!
Some languages organize their types into a tree, such that each type is a subtype of exactly one other type ( except for a single “all-inclusive” type, often called Top or Object). We might say, for instance, that Cats are Animals, AlarmClocks are Electronics, and both Animals and Electronics are Objects.
This sounds straightforward enough, but types rarely fall into this kind of tree-like hierarchy neatly. For instance, both Cats and AlarmClocks can yowl at you when you’d really prefer to be sleeping. Perhaps both should be subtypes of Noisemaker! But not all Animals are Noisemakers, nor are all Noisemakers Animals. Down this path lies madness! For this reason, most type systems allow a type to have multiple supertypes: a Cat can be both a Noisemaker and an Animal. In the JVM—the program which underlies Clojure—there are (and I speak very loosely here: we’re going to ignore primitives and smooth over all kinds of internal details) two kinds of types, and both of these kinds of relationships are in play.
The types of JVM values—things like java.lang.Long, java.lang.String, clojure.lang.PersistentVector, etc. — are called classes. If you have a value like 2 or ["foo" :bar] in Clojure, that value’s type is a class. Each class is a subtype of exactly one other class, except for Object, the JVM’s Top class.
The other kind of JVM type is called an interface (or an abstract class — we’ll use “interface” to refer to both throughout this chapter) and it defines the behavior for a type. In essence, an interface defines a collection of functions which take an instance of that interface as their first argument. Both classes and interfaces can be a subtype of any number of interfaces. Clojure uses interfaces to define the behavior of things like “a list” or “something you can look up values in”, and provides a variety of classes, each optimized for a different kind of work, which are subtypes of those interfaces. These shared interfaces are why we can have two types of lists which work the same way.
We can see these relationships between types in Clojure with the supers function, which returns the supertypes of a given type:
scratch.polymorphism=> (supers clojure.lang.PersistentList$EmptyList)
#{clojure.lang.Obj clojure.lang.IPersistentCollection clojure.lang.IMeta
clojure.lang.IObj clojure.lang.Sequential java.lang.Iterable
java.io.Serializable clojure.lang.IPersistentStack java.lang.Object
clojure.lang.IHashEq clojure.lang.IPersistentList clojure.lang.Seqable
clojure.lang.ISeq clojure.lang.Counted java.util.List java.util.Collection}
scratch.polymorphism=> (supers clojure.lang.PersistentList) #{clojure.lang.Obj
clojure.lang.IPersistentCollection clojure.lang.IReduce clojure.lang.IMeta
clojure.lang.IObj clojure.lang.Sequential java.lang.Iterable
java.io.Serializable clojure.lang.IPersistentStack java.lang.Object
clojure.lang.IHashEq clojure.lang.IPersistentList clojure.lang.Seqable
clojure.lang.ISeq clojure.lang.ASeq clojure.lang.Counted java.util.List
java.util.Collection clojure.lang.IReduceInit}A few of these types, like java.lang.Object, are actual classes. The rest are interfaces. Note that these sets are almost identical: empty and non-empty lists share almost all their supertypes. Both, for example, are subtypes of clojure.lang.Counted, which means that they keep track of how many elements they contain — the count function uses Counted to count collections efficiently. Both are clojure.lang.Seqable, which means they can be interpreted as a sequence of objects — that’s why we can call map, filter, and so on over lists. Most relevant for our purposes, both are kinds of clojure.lang.IPersistentList, which defines the core of how lists work: using cons to prepend elements. Let’s change our append function to use the IPersistentList type instead, and see if it lets us append to empty lists.
(defn append
"Adds an element x to the end of a collection coll. Coll may be either a
vector or a list."
[coll x]
(condp = (type coll)
clojure.lang.PersistentVector
(conj coll x)
clojure.lang.IPersistentList
(concat coll (list x))))
scratch.polymorphism=> (append '() 1)
IllegalArgumentException No matching clause: class
clojure.lang.PersistentList$EmptyList scratch.polymorphism/append
(polymorphism.clj:7)Ah, of course. We’re asking if the types of coll is equal to clojure.lang.IPersistentList, but they’re not actually the same type. What we want to know is if the type of coll is a subtype of clojure.lang.IPersistentList. Let’s check if any of coll‘s supertypes match as well:
(defn append
"Adds an element x to the end of a collection coll. Coll may be either a
vector or a list."
[coll x]
(let [t (type coll)
types (conj (supers t) t)]
(cond (types clojure.lang.PersistentVector)
(conj coll x)
(types clojure.lang.IPersistentList)
(concat coll (list x))
true (str "Sorry, I don't know how to append to a "
(type coll) ", which has supertypes " types))))
scratch.polymorphism=> (append '() 1)
(1)We’ve generalized our function from depending on specific types to depending on a type or its supertypes. What about… a lazy sequence, like the ones returned by map?
scratch.polymorphism=> (append (map inc [1 2 3]) 5) "Sorry, I don't know how to
append to a class clojure.lang.LazySeq, which has supertypes #{java.util.List
clojure.lang.IHashEq java.io.Serializable clojure.lang.IObj
clojure.lang.IPersistentCollection clojure.lang.ISeq java.util.Collection
java.lang.Iterable clojure.lang.Seqable clojure.lang.IPending
clojure.lang.Sequential java.lang.Object clojure.lang.IMeta clojure.lang.Obj}"We could add another clause for LazySeq to our definition of append—but would it actually be any different from how we append to lists? If we plan to concat for both, perhaps we should search for a type that sequences and lists have in common.
``clojure (require ’[clojure.set :as set]) scratch.polymorphism=> (set/intersection (supers clojure.lang.IPersistentList) (supers clojure.lang.LazySeq)) #{clojure.lang.IPersistentCollection clojure.lang.Seqable clojure.lang.Sequential} ```
These types have three supertypes in common. One is IPersistentCollection, which defines how any Clojure collection works, including sets, maps, etc. Another is Seqable, which means that the collection can be interpreted as a sequence of values—this too applies to sets and maps. The final type in common is Sequential, which applies only to collections with a well-defined order: lists and vectors, but not sets and maps. If we think of append as operating only over ordered collections, we should define it in terms of Sequential, rather than Seqable.
(defn append
"Adds an element x to the end of any sequential collection--faster for vectors."
[coll x]
(let [t (type coll)
types (conj (supers t) t)]
(cond (types clojure.lang.PersistentVector)
(conj coll x)
(types clojure.lang.Seqable)
(concat coll (list x))
true (str "Sorry, I don't know how to append to a "
(type coll) ", which has supertypes " types))))
scratch.polymorphism=> (append (map inc [1 2 3]) 5)
(2 3 4 5)Now our function is even more general: it can accept vectors, lists, and lazy sequences of all kinds, while being smart about it: for vectors, it efficiently adds elements to the end using conj, and for other Sequential types, it falls back to using concat.
This idea—checking a value’s type and supertypes—is so useful that there’s a special function for it. We say that a value v is an instance of type T if v’s type, or any of its supertypes, is T. We can use the instance? function to ask if this is so!
scratch.polymorphism=> (instance? clojure.lang.PersistentVector [])
true
scratch.polymorphism=> (instance? clojure.lang.PersistentVector (list))
falseThanks to the instance? function, we don’t need to compute the set of types and supertypes ourselves.
(defn append
"Adds an element x to the end of any sequential collection--faster for
vectors."
[coll x]
(cond (instance? clojure.lang.PersistentVector coll)
(conj coll x)
(instance? clojure.lang.IPersistentList coll)
(concat coll (list x))
true (str "Sorry, I don't know how to append to a "
(type coll))))Wonderful! The supertype machinery disappears, and we’re left with something that asks succinctly about how a value might behave.
This is a perfectly valid way to write a polymorphic function, but it has an important limitation. Whenever someone finds or creates a new type they’d like to append to, they have to edit the append function to add support for that type. This is one half of a classic dilemma in programming languages known as the expression problem. It would be nice if we could define functions piece by piece, so that we could add support for different types without changing the original definition of the function. This is the motivation behind Clojure’s multimethods.
A multimethod is a special kind of function. Instead of a function body, it has a dispatch function, which takes the arguments to the function and tells us not what to return, but how to find a particular implementation of that function. We define the implementations (essentially, the function bodies) separately.
To define a multimethod, use defmulti:
Here, we’re defining an append function. This will overwrite our append function from earlier, so you can rename or delete the original to avoid the conflict, if you like. Like defn, we provide a docstring. Unlike defn, we follow that with a dispatch function, which takes two arguments (coll and x) and returns the type of coll. The return value of the dispatch function is how Clojure decides which implementation to use. All together, this defmulti says “the behavior of append, a function of two arguments, depends on the type of its first argument.”
Next, we need to provide an implementation of the append function. We do this with defmethod:
When append’s dispatch function returns clojure.lang.PersistentVector, we take the arguments coll and x, and use conj to append x to coll. This is the same implementation as our original polymorphic function for vectors, but we’ve decoupled the plumbing from the implementation: one function decides which implementation to run, and the implementation does the work. This decoupling means we can add additional implementations (again using defmethod) without changing our existing implementation!
This implementation of append takes a clojure.lang.Sequential as its first argument, and uses concat to add x to the end. Now our append function can take either a vector or any sequential object:
scratch.polymorphism=> (append [1 2] 3)
[1 2 3]
scratch.polymorphism=> (append (map inc [1 2]) 4)
(2 3 4)That’s odd! We dispatched using (type coll), which, for (map inc …), would have been a LazySeq. But we didn’t define any method for LazySeq. Why… why did this work?
The answer is that Clojure doesn’t compare multimethod dispatch values via =. It compares them using a function we haven’t seen before: isa?.
scratch.polymorphism=> (doc isa?)
-------------------------
clojure.core/isa?
([child parent] [h child parent])
Returns true if (= child parent), or child is directly or indirectly derived from
parent, either via a Java type inheritance relationship or a
relationship established via derive. h must be a hierarchy obtained
from make-hierarchy, if not supplied defaults to the global
hierarchySo isa? tells us whether two things are equal (using =), or whether child is related to parent via Java types, or via “a relationship established via derive”, whatever that is. The fact that isa? knows about Java type relationships means that we can use a supertype (e.g. Sequential) rather than listing every specific type (e.g. PersistentList, LazySeq, etc).
scratch.polymorphism=> (isa? clojure.lang.PersistentList clojure.lang.Counted)
true
scratch.polymorphism=> (isa? clojure.lang.PersistentList clojure.lang.PersistentVector)
falseisa? has another trick up its sleeve–it says it can use relationships defined via derive. What does that do?
scratch.polymorphism=> (doc derive)
-------------------------
clojure.core/derive
([tag parent] [h tag parent])
Establishes a parent/child relationship between parent and
tag. Parent must be a namespace-qualified symbol or keyword and
child can be either a namespace-qualified symbol or keyword or a
class. h must be a hierarchy obtained from make-hierarchy, if not
supplied defaults to, and modifies, the global hierarchy.Huh. So this lets us establish relationships between symbols or keywords. And classes, too—though classes can only be children. Let’s give that a shot.
(derive ::milk ::dairy)
(derive ::dairy ::grocery)
scratch.polymorphism=> (isa? ::milk ::milk)
true
scratch.polymorphism=> (isa? ::milk ::furniture)
false
scratch.polymorphism=> (isa? ::milk ::dairy)
true
scratch.polymorphism=> (isa? ::milk ::grocery)
trueWith these derive statements, we’ve built a web of relationships between these keywords. Now isa? not only knows that milk is a kind of dairy, but also (because dairy is a kind of grocery) that milk is a kind of grocery. And we know that milk is not furniture—I’m pretty sure that’s true. Note that we’re using qualified keywords here (beginning with a ::), which prevents us from accidentally changing the relationships in other namespaces.
We’re not limited to defining 1:1 relationships. Milk can be a grocery and refrigerated. Apples can also be groceries.
(derive ::milk ::refrigerated)
(derive ::apples ::grocery)
scratch.polymorphism=> (isa? ::milk ::grocery)
true
scratch.polymorphism=> (isa? ::milk ::refrigerated)
true
scratch.polymorphism=> (isa? ::apples ::grocery)
trueWe can see the all the things that milk is by using the parents function. That’s kind of like supertypes, only these aren’t types: they’re just plain old keywords.
scratch.polymorphism=> (parents ::milk)
#{:scratch.polymorphism/refrigerated :scratch.polymorphism/dairy}And we can see all the things that are refrigerated using descendents. That’s kind of like subtypes:
scratch.polymorphism=> (descendants ::grocery)
#{:scratch.polymorphism/milk :scratch.polymorphism/apples :scratch.polymorphism/dairy}Now imagine we represented our groceries as maps. Something like {:item-type ::milk, :size :gallon}. When we get home from running errands, we’d like a function to put those grocery maps away—but how they’re stored should depend on the :item-type of the grocery item. We could write:
This takes advantage of the fact that keywords are functions: :item-type will look up the type of the item, and use that to choose an implementation.
In general, we can put groceries in the pantry, and refrigerated items, we’ll put in the fridge.
(defmethod put-away ::grocery
[item]
(println "Putting a" (name (:size item)) "of" (name (:item-type item))
"in the pantry"))
(defmethod put-away ::refrigerated
[item]
(println "Storing a" (name (:size item)) "of" (name (:item-type item))
"in the fridge"))Now we can store some apples, and see them go into the pantry.
Putting a large-bag of apples in the pantry
How about milk?
scratch.polymorphism=> (put-away {:item-type ::milk, :size :gallon})
IllegalArgumentException Multiple methods in multimethod 'put-away' match
dispatch value: :scratch.polymorphism/milk -> :scratch.polymorphism/grocery and
:scratch.polymorphism/refrigerated, and neither is preferred
clojure.lang.MultiFn.findAndCacheBestMethod (MultiFn.java:178)Ah, that’s interesting. Since milk is both a grocery and refrigerated, either of these implementations could apply to it. We can tell Clojure how to resolve the ambiguity using prefer-method:
(prefer-method put-away ::refrigerated ::grocery)
scratch.polymorphism=> (put-away {:item-type ::milk, :size :gallon})
Storing a gallon of milk in the fridgeVery good! We’ve established that the ::refrigerated item type takes precedence over the ::grocery item type. It’s important to prevent spoilage!
You can use multimethods wherever you need to extend a function’s behavior later. This is especially useful when you intend your code to be used by other people—if someone else were to use our grocery-storage system, they could define new types of items, and be able to tell put-away exactly how to handle those new item types. We didn’t talk about garbage bags, pencils, or medication here, but because put-away is a multimethod, someone else could define something like {:item-type ::medication}, and extend put-away to store it correctly.
Throughout this example, we’ve talked about “item types”, but… we used keywords, like ::apples, to represent those types. These aren’t types in the sense of Clojure’s type system, but we could use them like types. In a very real sense, what we’ve done here is define our own tiny language, with its own itty bitty type system, completely separate from Clojure’s. The core ideas are the same: we use subtype relationships to write code which depends only on general things (e.g. “refridgerated things”) automatically cover more specific things (e.g. “milk”).
Multimethods are powerful and general thanks to their dispatch functions. However, because those dispatch functions get involved in every call to a multimethod, they’re a bit slower than regular function calls. When performance matters, we turn to interfaces and protocols.
The idea of a polymorphic function which decides what to do based on the type of its arguments is so common, and so useful, that most languages provide special facilities for it. We call this “type dispatch”: the type of the value being passed chooses which particular code the language invokes. We wrote a version of type dispatch using multimethods and the type function. Many languages, such as Haskell and Java, build type dispatch into every function—types are attached to each argument, and used to decide between alternative implementations.
To support this feature in Java, the JVM has a fast, built-in mechanism for type dispatch using interfaces. We aren’t limited to using the interfaces given to us by Clojure and the JVM. We can define our own interfaces, and use them to get extra-speedy type dispatch, using the definterface macro.
We’ve defined a new type: specifically, an interface. The name of our interface is IAppend. We’ve also stated that if a value coll is an instance of type IAppend, then there must be a method, named append. These methods are (and I know this is confusing) not the multimethods we discussed earlier. These methods are JVM methods: a sort of primitive function. Methods take arguments, evaluate code, and return results, like functions. Unlike Clojure’s functions, they aren’t values: you can’t ask them for docstrings, or pass them around to map or filter. We’ve provided only a single method here, but if we liked, we could define several in the same definterface.
The append method we defined takes two arguments. Yes, two. Interfaces always take a first argument, which in this case must be an instance of IAppend. Since the first argument is mandatory, definterface doesn’t ask us to write it down. This is a bit weird, and contradicts how function definitions work everywhere else, but we’re stuck with this behavior for historical reasons. Long story short: (append [x] tells us that our first argument is an IAppend, and our second argument is some object called x. And that’s it! Like a multimethod, there’s no function body: we provide that later. Unlike a multimethod, there’s no dispatch function. The JVM will always dispatch based on the type of the first argument.
“All right”, you might say. “It’s great that we have type to express that something is appendable, and an append… method, whatever that is, exists. But how do we make an appendable thing?”
For this, we need new tools.
We have an interface, IAppend, and we’d like to make an instance of that type. The quickest way to make an object of some type is to use a macro called reify: a fancy philosophical word that means “make a concrete thing out of an abstract concept.” In Clojure, reify takes interfaces, and definitions for how the methods in those interfaces should work, and returns an object which is an instance of those interfaces. For instance, perhaps we want an object to keep track of a grocery list:
(defn grocery-list
"Creates an appendable grocery list. Takes a vector of
groceries to buy."
[to-buy]
(reify IAppend
(append [this x]
(grocery-list (conj to-buy x)))))There are two parts here: the first is a function, grocery-list, which we’re going to call when we want to make a new grocery list. The second is the (reify IAppend …), which constructs a value. That value will be an instance of type IAppend; at compile time, reify summons a new, anonymous class from the void, and makes sure that class is a subtype of IAppend. Each call to this (reify …) constructs a new instance of that anonymous class.
Inside the reify, we’ve provided definitions for how to handle IAppend’s methods: when someone calls the append method with this (some value which this reify constructed) and x, we add x to the end of the to-buy vector using conj, and call grocery-list to make a new GroceryList out of it. That way we can keep appending more things later.
An interesting thing to note: like fn, reify can use variables, like to-buy, from the surrounding code. When grocery-list returns, the object constructed by reify remembers the value of to-buy, and can use it later. We say that reify, like fn, closes over those variables: reify and fn are closures. That’s a fancy bit of programming jargon you can use to get strangers to stop talking to you at parties.
Let’s try it out:
scratch.polymorphism=> (grocery-list [:eggs])
#object[scratch.polymorphism$grocery_list$reify__1950 0x70e02b5 "scratch.polymorphism$grocery_list$reify__1950@70e02b5"]This is not a particularly helpful representation of a grocery list. If you squint, you can see the namespace (scratch.polymorphism) and function (grocery_list) in there, and also reify, since we used reify to make this value. The _1950 is a unique number that helps the computer tell this particular reify apart from others. In fact, this whole first part is the automatically generated class which reify defined for us. 0x70e02b5 is a number that identifies where this particular instance of that class lives in memory. Unhelpfully, nothing here tells us about the to-buy list we provided ([:eggs]).
One thing we do know, though, is that this is something we can append to.
scratch.polymorphism=> (supers (type (grocery-list [:eggs])))
#{clojure.lang.IObj scratch.polymorphism.IAppend java.lang.Object clojure.lang.IMeta}Remember how many types were in (supers clojure.lang.PersistentVector)? Objects made with reify are far simpler. There’s IAppend: that’s the interface type we defined earlier. There’s java.lang.Object, of course. clojure.lang.IObj and IMeta mean that our reify object has metadata. Wait—what is this thing’s metadata anyway?
Huh! That’s the line and column number, of the reify expression which made this object. But what about appending? How do we use append with this thing?
scratch.polymorphism=> (append (grocery-list [:eggs]) :tofu)
"Sorry, I don't know how to append to a class scratch.polymorphism$grocery_list$reify__1491"Oh, wait, hang on—that’s our append function from before. We wanted to call the append method we defined using definterface: methods and functions are different things, even if they have the same name. To make a method call, we put a . in front of the method name:
scratch.polymorphism=> (.append (grocery-list [:eggs]) :tofu)
#object[scratch.polymorphism$grocery_list$reify__1950 0x40eb00f0 "scratch.polymorphism$grocery_list$reify__1950@40eb00f0"]If we wanted a function for append, we could write one which calls the method. We might call this a wrapper function, since it wraps the append method up in a nice functional package. This version of append we can use with reduce or partial, and so on.
Moving on: we’ve called our append method, and it gave us… another unhelpful grocery-list. It’d be great if we had a more reasonable way to print these lists to the console. In the JVM, the Object class defines a method called toString. That’s how str (typically) makes strings out of things. Let’s expand our reify to define a different toString method:
(defn grocery-list
"Creates an appendable (via IAppend) grocery list. Takes a vector of
groceries to buy."
[to-buy]
(reify
IAppend
(append [this x]
(grocery-list (conj to-buy x)))
Object
(toString [this]
(str "To buy: " to-buy))))In general, reify takes a type followed by method definitions for that particular type, then another type, and any number of methods for that type, and so on. Our grocery lists were already Object before, and they were given simple, default definitions for all of Object’s methods–that’s how the REPL was able to show us #object[scratch.polymorphismgrocerylistreify__1950 …]. But now our call to reify states explicitly: when interpreted as an Object, here’s how the toString method works.
Let’s see it in action!
Hey, that’s more helpful! This is another kind of polymorphism at work: the toString method (and by extension, the str function) does different things depending on the type of object it’s given. And what’s neat is that unlike our initial polymorphic function append—where we had a single function definition which had to know about all the types we wanted to call… we didn’t have to change toString or str’s definitions. The plumbing—looking up what code to evaluate—is handled automatically. As with multimethods, we’re free to define behaviors for new types without having to change the definitions for other types.
Let’s try out our append method again and see if it works:
Hey, that’s great! We can see the results of appending to our grocery list. What about appending to lists and vectors, though? Can we use .append with them?
scratch.polymorphism=> (.append [1 2] 3)
IllegalArgumentException No matching method found: append for class
clojure.lang.PersistentVector clojure.lang.Reflector.invokeMatchingMethod
(Reflector.java:53)The reflector is a part of Clojure which figures out what definition of a method to use for a given type. It failed to find a matching method for append, given a clojure.lang.PersistentVector—which makes sense, because we haven’t made clojure.lang.PersistentVector a subtype of IAppend. Let’s do that next!
I have terrible news: we can’t do this. Interfaces are a one-way street: when we define a new type (as we did with reify), we can say how that type works with any number of interfaces. But when we define an interface, we don’t get to say how it works with existing types. That’s just how the JVM’s type system works.
“But this is awful!” You might exclaim. “The whole reason we defined an interface was so that we could write polymorphic functions like append, which could append to many kinds of objects. Instead, we’re limited to polymorphism only over types which we ourselves define!”
This is the other half of the expression problem we mentioned earlier: existing (regular) functions can’t be extended to new types, and existing types can’t be extended to new interfaces. We solved the function-extension problem with multimethods and interfaces… but how do we solve the interface-extension problem?
In Clojure, a protocol is like an interface which can be extended to existing types. It defines a named type, together with functions whose first argument is an instance of that type. Where interfaces are built into the JVM, protocols are a Clojure-specific construct. To define a protocol, we use defprotocol:
(defprotocol Append
"This protocol lets us add things to the end of a collection."
(append [coll x]
"Appends x to the end of collection coll."))If you still have the append function we wrote earlier, this append function will replace it; you’ll see a message like Warning: protocol #’scratch.polymorphism/Append is overwriting function append at the REPL. You can delete or rename the original append function if you like.
We’ve named our protocol Append (not to be confused with the interface IAppend), and given it a bit of documentation to remind us what it’s for. It has one function, named append, which takes two arguments: coll and x. We can give a docstring for the append function too. Like an interface, we don’t define how the function works: we’re simply saying it exists. Unlike interfaces, these are real functions, not methods. Their first arguments are explicit, they have docstrings, we don’t need to use a . to call them, and they can be passed around to other functions.
We can ask for our protocol’s documentation at the repl, just like we can for functions and namespaces:
scratch.polymorphism=> (doc Append)
-------------------------
scratch.polymorphism/Append
This protocol lets us add things to the end of a collection.And likewise, functions defined in defprotocol can be inspected, just like those made with defn.
scratch.polymorphism=> (doc append)
-------------------------
scratch.polymorphism/append
([coll x])
Appends x to the end of collection coll.If we try to use the append function with a grocery list, it’s going to fail: the grocery list reify is a subtype of the interface IAppend, but we haven’t told it how the protocol Append works yet:
scratch.polymorphism=> (append (grocery-list [:eggs]) :tomatoes)
IllegalArgumentException No implementation of method: :append of protocol:
#'scratch.polymorphism/Append found for class:
scratch.polymorphism$grocery_list$reify__1758 clojure.core/-cache-protocol-fn
(core_deftype.clj:568)This error tells us that the append function doesn’t have an implementation (a function body) for the type scratch.polymorphismgrocerylistreify__1758. We can fix that by changing our reify to use the Append protocol, instead of the IAppend interface. This is a one-character change: protocol functions and interface methods are defined in reify in exactly the same way.
(defn grocery-list
"Creates an appendable (via IAppend) grocery list. Takes a vector of
groceries to buy."
[to-buy]
(reify
Append
(append [this x]
(grocery-list (conj to-buy x)))
Object
(toString [this]
(str "To buy: " to-buy))))Now we can use our append function with grocery lists!
So far, we’ve done exactly what we did with interfaces. In fact, when we called defprotocol, it not only defined a protocol: it also defined an interface as well. But unlike interfaces, we can extend our protocol to cover existing types. To do this, we use extend-protocol:
This expresses that the Append protocol’s functions (i.e. append) can now be used on anything which is an IPersistentVector. When we call (append v x) with a vector v, we return the result of (conj v x). Let’s try it out:
Fantastic! What about other sequential collections?
(extend-protocol Append
clojure.lang.IPersistentVector
(append [v x]
(conj v x))
clojure.lang.Sequential
(append [v x]
(concat v (list x))))extend-protocol can take several types, and the function definitions for each of them. Here, we’re extending Append over both IPersistentVector and Sequential—and providing definitions for how append works in each case. If you want to extend a single type to multiple protocols, use extend-type. Both extend-protocol and extend-type can be called as often as you like: all their definitions get merged together.
We can even extend a protocol over nil! We could add this to the existing extend-protocol, or write it separately. This is another advantage of protocols over interfaces.
We’ve used reify to make an object which satisfies some interfaces or protocols. Like an anonymous function (fn [x] …), reify creates an anonymous type. Because the reify type has no (predictable) name, we can’t extend protocols to it later. How do we make a type with a name–like clojure.lang.PersistentVector, or clojure.lang.LazySeq?
There are two tools at our disposal here: deftype and defrecord. Both define new named types—classes, to be exact. The deftype macro produces a very basic datatype, whereas defrecord defines a type which behaves, in many respects, like a Clojure map. First, deftype:
(deftype GroceryList [to-buy]
Append
(append [this x]
(GroceryList. (conj to-buy x)))
Object
(toString [this]
(str "To buy: " to-buy)))We’re defining a new type, named GroceryList. Objects of this type keep track of a single variable, called to-buy. Just as with reify, we provide a sequence of types we’d like GroceryLists to be a subtype of, and provide implementations for their functions or methods. The only difference is that in append, we construct a new grocery list using (GroceryList. to-buy). We use the name of the class followed by a period . to make a new instance of Grocerylist.
Let’s try creating one of these GroceryLists.
scratch.polymorphism=> (GroceryList. [:eggs])
#object[scratch.polymorphism.GroceryList 0x370dbd33 "To buy: [:eggs]"]Voilà! An instance of GroceryList. We’ve got the full name of the type: GroceryList, preceded by the namespace scratch.polymorphism. There’s a memory address, and then our string representation. Can we append to it?
scratch.polymorphism=> (append (GroceryList. [:eggs]) :spinach)
#object[scratch.polymorphism.GroceryList 0x3c612037 "To buy: [:eggs :spinach]"]Indeed we can. What else can we do with a GroceryList?
scratch.polymorphism=> (supers GroceryList)
#{clojure.lang.IType scratch.polymorphism.Append java.lang.Object}Not much. There’s clojure.lang.IType, which just means “this thing is a Clojure datatype”. There’s our Append protocol, and java.lang.Object, of course—almost everything is a subtype of Object. As it turns out, deftype is pretty bare-bones.
We do get a few things for free with deftype. We can access the fields by using .some-field-name, like so:
And we also get a function that takes a to-buy list and builds a new GroceryList. These “constructor functions” take one argument for each field in the deftype.
scratch.polymorphism=> (->GroceryList [:strawberries])
#object[scratch.polymorphism.GroceryList 0x44cc69b3 "To buy: [:strawberries]"]This is a small wrapper around (GroceryList. to-buy). It’s there because GroceryList., like a method, isn’t a full-fledged Clojure function. Like methods, we can’t use GroceryList. with map or apply, or other things that expect functions. But we can use ->GroceryList in these contexts!
scratch.polymorphism=> (map GroceryList. [[:twix] [:kale :bananas]])
CompilerException java.lang.ClassNotFoundException: GroceryList.,
compiling:(/tmp/form-init2122621676255621718.clj:1:1)
scratch.polymorphism=> (map ->GroceryList [[:twix] [:kale :bananas]])
(#object[scratch.polymorphism.GroceryList 0x552db723 "To buy: [:twix]"]
#object[scratch.polymorphism.GroceryList 0x4d81eefd "To buy: [:kale
:bananas]"])The types constructed by deftype are so basic that they lack properties we’ve taken for granted so far—like equality:
The only thing a GroceryList is equal to is itself.
This is Clojure being conservative—it doesn’t know if, say, two GroceryLists with the same to-buy list can really be considered equivalent. It’s up to us to define that by providing an implementation for the equals method—another part of Object.
(deftype GroceryList [to-buy]
Append
(append [this x]
(GroceryList. (conj to-buy x)))
Object
(toString [this]
(str "To buy: " to-buy))
(equals [this other]
(and (= (type this) (type other))
(= to-buy (.to-buy other)))))
scratch.polymorphism=> (= (GroceryList. [:cheese]) (GroceryList. [:cheese]))
trueWant to make all grocery lists equal? Go wild!
(deftype GroceryList [to-buy]
Append
(append [this x]
(GroceryList. (conj to-buy x)))
Object
(toString [this]
(str "To buy: " to-buy))
(equals [this other]
(= (type this) (type other))))
scratch.polymorphism=> (= (GroceryList. [:ketchup]) (GroceryList. [:mayo]))
trueSo, deftype gives us the power to construct our own, primitive types. But most of the time, we don’t want this degree of control: defining exactly how to print our values, how to compare two values together, and so on. After all, plain old maps are a great way to model data. They’re easy to print and easy to manipulate. It’d be nice if we could create a type—to take advantage of protocols—but have it still work like a map. Clojure calls this kind of type a record.
The defrecord macro looks almost exactly like deftype: it takes the name of the type we’re defining, the names of the fields each instance will keep track of, and then a series of types with method implementations. As with deftype, we can construct instances of our GroceryList type using GroceryList. or the ->GroceryList function.
Unlike deftype, we get a nice, concise string representation for free. The first part shows the type name, and after that it looks just like a map, showing the fields of this GroceryList and their corresponding values.
We don’t have to define our own equality either: two records are equal if they’re of the same type, and their fields are equal.
scratch.polymorphism=> (= (GroceryList. [:beans]) (GroceryList. [:beans]))
true
scratch.polymorphism=> (= (GroceryList. [:beans]) {:to-buy [:beans]})
falseA GroceryList works like a map, but it’s not the same type: records aren’t equal to maps, even if they have the same keys and values.
Like deftype, we can access the fields of a record using .to-buy:
But since records work like maps, we can also access them using get, or by using keywords as functions:
scratch.polymorphism=> (get (GroceryList. [:bread]) :to-buy)
[:bread]
scratch.polymorphism=> (:to-buy (GroceryList. [:bread]))
[:bread]And we can alter those fields using assoc and update, just like maps. Let’s replace our shopping list with onions:
scratch.polymorphism=> (-> (GroceryList. [:chicken])
(assoc :to-buy [:onion]))
#scratch.polymorphism.GroceryList{:to-buy [:onion]}… and add some beets:
scratch.polymorphism=> (-> (GroceryList. [:chicken])
(assoc :to-buy [:onion])
(update :to-buy conj :beets))
#scratch.polymorphism.GroceryList{:to-buy [:onion :beets]}Just as with maps, these updates are immutable: they don’t alter the original GroceryList. Instead, they create copies with our requested changes. We aren’t limited to the fields we explicitly defined in the defrecord, either. Let’s tack on a :note to our grocery list:
scratch.polymorphism=> (assoc (GroceryList. [:cherries]) :note "Tart cherries if possible!")
#scratch.polymorphism.GroceryList{:to-buy [:cherries], :note "Tart cherries if possible!"}This is possible because records (unlike deftypes) always carry around an extra map—just in case they need to store additional fields we didn’t define up front. The assoc function tries to update a field if it can, and if there’s no field by that name, it stores it in the record’s extra map.
Both deftype and defrecord produce named types, which means we can extend protocols over them after the fact. Let’s add a new protocol for printing out things nicely to the console—something we could use to print our grocery list and the items on it.
Now we can define how to print a GroceryList. Let’s add a basic print-out function that works on any object, while we’re at it:
(extend-protocol Printable
GroceryList
(print-out [gl]
(println "GROCERIES")
(println "---------")
(doseq [item (:to-buy gl)]
(print "[ ] ")
(print-out item)
(println)))
Object
(print-out [x]
(print x)))Like we saw earlier, we can use (:to-buy gl) to get the items on the grocery list. We go through each one in turn using doseq, and call that particular item item. With that item, we print out a pair of brackets “[ ]”. Then we do something a bit strange: we call print-out again, but this time, with the item in question. The Object implementation takes over from there.
scratch.polymorphism=> (print-out (GroceryList. [:cilantro :carrots :pork :baguette]))
GROCERIES
---------
[ ] :cilantro
[ ] :carrots
[ ] :pork
[ ] :baguetteNice! This actually looks like a real grocery list. What if we wanted to keep track of how many carrots to buy? We could introduce a new type to keep track of things that come in a certain quantity:
(defrecord CountedItem [thing quantity]
Printable
(print-out [this]
(print-out thing)
(print (str " (" quantity "x)"))))We’ve defined how to print out a counted item: first we print out the thing, then the quantity in parentheses. Let’s give that a shot:
scratch.polymorphism=> (print-out (GroceryList. [:cilantro (CountedItem. :carrots 2) :pork :baguette]))
GROCERIES
---------
[ ] :cilantro
[ ] :carrots (2x)
[ ] :pork
[ ] :baguetteNeat! We didn’t have to change GroceryList at all to get this behavior. Because it used the polymorphic protocol function print-out, it automatically knew how to work with our new CountedItem type.
If you’re coming from an object-oriented language (e.g. Ruby, Java), or a typed language with algebraic datatypes (e.g. Haskell, ML), you might see defprotocol, deftype, and defrecord, and think: “Ah, finally. Here are the tools I’ve been waiting for.” You might start by wanting to model a person, and immediately jump to (defrecord Person [name pronouns age]). While this is valid, you should take a step back, and ask: do I need polymorphism here? Are there going to be functions that take people and animals? Or do I simply want to keep track of some data?
If you don’t need polymorphism, there’s a good chance your data can be modeled in Clojure as plain old maps, sets, vectors, and so on. Need to represent a person? How about:
{:name "Morgan"
:pronouns [:they :them]
:age 56}No defrecord required. Sticking to maps keeps your data in a shape that can be easily manipulated using standard Clojure functions. It’s easy to store this data on disk, or send it across the network. It’s easier to share this kind of data with other people. And it’s more concise to print at the console, which makes debugging your programs easier.
Conversely, you’ll want to use defrecord and deftype when maps aren’t sufficient: when you need polymorphism, when you need to participate in existing protocols or interfaces, or when multimethod performance is too slow. Records are often faster and more memory-efficient than maps, so even if you don’t need the polymorphism, it can be worthwhile to define a record or so when map performance bogs you down. This is something you’ll want to find out by measuring your code, though, rather than simply assuming.
If you’re reaching for records for type safety: it’s not going to be as helpful as you’d like. Functions like assoc work equally well across all kinds of records, and the compiler won’t warn you about using the wrong keyword. Sticking to methods eliminates some of those risks, but it’s nothing like the type guardrails in Java or Haskell. Clojure programs generally rely more on tests and contracts to prevent these type errors. There are also static type systems like core.typed, which we’ll discuss later.
When a function’s behavior depends on the type of values it is provided, we call that function polymorphic. Many of Clojure’s core functions, like conj or reduce, are polymorphic: we can conj into maps, vectors, sets, and lists, and each does something different. Often, our own code is implicitly polymorphic by virtue of using other polymorphic functions: (defn add-bird [coll] (conj coll :bird)) can add birds to lots of different things.
When we need a function whose behavior explicitly depends on its arguments, we can use ad-hoc approaches, like if, cond, or case. The instance?, type, and supers functions let us choose what to do based on the type of the value.
When we need an open function—one whose behavior can be extended to new things later—we use a multimethod, an interface, or a protocol. Multimethods are the most general approach: they use a dispatch function, which receives the function’s arguments and decides which implementation to call. They’re not limited to dispatching by argument type: they can use arbitrary values and relationships between keywords, defined with derive. They also offer fine-grained control when that dispatch would be ambiguous. This flexibility comes with a performance penalty: Clojure has to evaluate the dispatch function every time the multimethod is called.
When a function’s behavior depends on the type of the first argument, use protocols or interfaces. Interfaces can’t be extended to existing types; protocols can. Protocols have some ergonomic advantages: they define regular functions, rather than methods, and come with documentation—though there’s nothing stopping you from writing your own documented wrapper functions, or using definterface+, which does so automatically. Interfaces are slightly faster; prefer them when performance matters.
To create instances of a new type, we have reify. Like (fn [x] …), reify generates an anonymous type—it can have interfaces and protocols as supertypes, and provides implementations for those types, but has no (predictable, meaningful) name. When we want to name our types—perhaps so that other people can extend them later—we use deftype and defrecord. Most of the time, defrecord is most useful: they work like maps out of the box. However, deftype is available should we need to construct bare-bones types with unusual behaviors.
We haven’t talked about the details of classes or inheritance in this discussion. These are important for Java interop, but we don’t use these concepts often in Clojure. A topic for later discussion!
Write a sorted function that uses cond and instance? to convert lists to sorted lists (using (sort …)), and sets to sorted sets (using (into (sorted-set) …)).
Rewrite sorted as a multimethod. Using defmethod, extend sorted to handle maps.
Add a checked-off field to the GroceryList type, and use it to store a set of items that are already in the cart. Write a check-off function that takes a grocery list and checks off an item on it, by adding that item to the checked-off set: (check-off my-list eggs)
Write a remaining function which takes a GroceryList and returns the items that haven’t been checked off yet.
Change the definition of print-out for GroceryList to take the checked-off set into account, printing an [x] in front of checked-off items.
Imagine Clojure had no built-in sets. Make up a Set protocol with some basic operations, like add-element, has-element?, and remove-element.
Using a vector or list to store your elements, write a basic implementation of your Set protocol. Experiment to make sure adding the same item twice doesn’t add two copies.
Try making larger and larger sets–say, with ten, a thousand, and a hundred thousand elements. Use (time (has-element? some-set 123)) to see how your set performance changes with size. Why is this?
Write a different implementation of a Set, which uses a map to store its elements. Compare its performance to your list-based set.
The deref function uses an interface called clojure.lang.IDeref to return the current value of a container type. Using deftype, define your own container type. Try @(MyContainer :hi) to verify that you can get the value of your container (:hi) back.
[advanced] So far, we’ve worked only with immutable types. deftype lets us define mutable types by tagging a field with ^:unsynchronized-mutable, like so: (deftype DangerBox [^:unsynchronized-mutable value] …). Design a Mutable protocol with a (write! box value) function to overwrite the value of a mutable container. Using (set! field value), build your own mutable container type which supports both Mutable and IDeref. Confirm that you can change its value using write!, and read it back using @.
[advanced] Use your mutable container as a counter by reading its current state and writing back a value one greater–e.g. via (write! box (inc @box)). Using dotimes, perform many updates in a row, and verify that the final value of the counter is the same as the number you passed to dotimes.
[advanced] Run this dotimes increment loop in two threads at once, using future. Is the final counter value what you expected? Why? How does this compare to using an (atom) with swap!?