Embedding an Object-Oriented Language
1. Just Enough Clojure
Clojure is a variant of Lisp, one of the oldest computer languages. You can view it as a small core surrounded by a lot of library functions. In this chapter, you’ll learn most of the core and functions you’ll need in the rest of the book.
1.1 Installing Clojure
At this moment, there seem to be two attractive choices for running Clojure. In this section, I’ll describe how to get started with either. If you have trouble, visit the installation troubleshooting page or ask for help on the mailing list.
Light Table
One simple way to install Clojure is to install the Light Table playground instead. It is something like an IDE for Clojure, with the interesting property that it evaluates expressions as you type them. You can find out more at Chris Granger’s site.
You’ll work in something Light Table calls the “Instarepl”. That’s its version of the Clojure read-eval-print loop (typically called “the repl”). You type text in the left half of the window, and the result appears in the right. It looks like this:
Light Table
The book doesn’t show input and output in the same split screen style. Instead, it shows input preceded by a prompt, and output starting on the next line:
user=> (if true 5)5
Important
As of this writing, Light Table does not automatically include all the normal repl functions. You have to manually include them with this magic incantation:
(use 'clojure.repl)
(Note the single-quote mark: it’s required.)
Leiningen
If you want to run Clojure from the command line, first install Leiningen. Go to its page and follow the installation instructions.
When you’re finished, you can type the following to your command line:
lein repl
That asks Leiningen to start the read-eval-print loop (typically called “the repl”). Don’t be alarmed if nothing happens for a few seconds: because the Java Virtual Machine is slow to start, Clojure is too.
All is well when you see something like this:
A command line repl, with a fashionable black background
From now on, I won’t use screen shots to show repl input and output. Instead, I’ll show it like this:
user=> (if true 5)5
The most important thing you need to know now is how to get out of the repl. That’s done like this:
user=> (exit)
On Unix machines, you can also use Control-D to exit.
1.2 Working with Clojure
All the exercises in this book can be done directly in the repl. However, many editors have a “clojure mode” that knows about indentation conventions, helps you avoid misparenthesizations, and helpfully colorizes Clojure code.
- Emacs: clojure-mode
- Vim: one is VimClojure
You can copy and paste Clojure text into the repl. It handles multiple lines just fine.
Many people like to follow along with the book by copying lines from the PDF version and pasting them into the repl. That’s usually safe. However, my experience is that such text is sometimes (but not always!) missing some newlines. That can cause perplexing errors when it results in source code ending up on the same line as a to-the-end-of-the-line comment. In later chapters (where there are more lines with comments), I’ll provide text files you can paste from.
If you want to use a Clojure command to load a file like (for example) solutions/add-and-make.clj
, use this:
user> (load-file "solutions/add-and-make.clj")
Watch Out!
Warning: I’m used to using load
in other languages, so I often reflexively use it instead of load-file
. That leads to this puzzling message:
user=> (load "sources/without-class-class.clj") FileNotFoundException Could not locate sources/without-class-class.clj__init.class or sources/without-class-class.clj.clj on classpath:clojure.lang.RT.load ( RT.java :432 )
The clue to my mistake is the “.clj.clj” on the next-to-last line.
1.3 The Read-Eval-Print Loop
Here’s a use of the repl:
user=> 11
More is happening than just echoing the input to output, though. This profound calculation requires three steps.
First, the reader does the usual parser thing: it separates the input into discrete tokens. In this case, there’s one token: the string "1"
. The reader knows what numbers look like, so it produces the number 1
.
The reader passes its result to the evaluator. The evaluator knows that numbers evaluate to themselves, so it does nothing.
The evaluator passes its result to the printer. The printer knows how to print numbers, so it does.
Strings, truth values, and a number of other types play the same self-evaluation game:
user=> "hi mom!""hi mom!"user=> true true
Let’s try something more exciting:
user=> *file*"NO_SOURCE_PATH"
*file*
is a symbol, which plays roughly the same role in Clojure that identifiers do in other languages. The asterisks have no special significance: Clojure allows a wider variety of names than most languages. Most importantly, Clojure allows dashes in symbols, so Clojure programmers prefer them to underscores. StudlyCaps or interCaps style is uncommon in Clojure.
Let’s step through the read-eval-print loop for this example. The reader constructs the symbol from its input characters. It gives that symbol to the evaluator. The evaluator knows that symbols do not evaluate to themselves. Instead, they are associated with (or bound to) a value. *file*
is bound to the name of the file being processed or to "NO_SOURCE_PATH"
when we’re working at the repl.
Here’s a slightly more interesting case:
user => +#<core$_PLUS_ clojure.core$_PLUS_@38a92aaa>
The value of the symbol +
is a function. (Unlike many languages, arithmetic operators are no different than any other function.) Since functions are executable code, there’s not really a good representation for them. So, as do other languages, Clojure prints a mangled representation that hints at the name.
Now let’s walk through what happens when you ask the repl to add one and two to get three:
1 user> (+ 1 2)3
In this case, the first token is a parenthesis, which tells the reader to start a list, which I’ll represent like this:
The second token represents the symbol +
. It’s put in the list:
The next two tokens represent numbers, and they are added to the list. The closing parenthesis signals that the list is complete:
The reader’s job is now done, and it gives the list to the evaluator. Lists are a case we haven’t described before. The evaluator handles them in two steps:
- It recursively evaluates each of the list elements.
- The symbol
+
evaluates to the function that adds. - As before, numbers evaluate to themselves.
- The symbol
- The first value from a list must be a function (or something that behaves like a function). The evaluator applies the function to the remaining values (its arguments). The result is the number
3
.
The printer handles 3
the same way it handled 1
.
To emphasize how seriously the evaluator expects the first element of the list to be a function, here’s what happens if it’s not:
user => (1 2 3) java.lang.ClassCastException:java.lang.Integer cannot be cast to clojure.lang.IFn(NO_SOURCE_FILE:0)
(I’m afraid that Clojure error messages are sometimes not as clear as they might be.)
1.4 A note on terminology: “value”
Since Clojure is implemented on top of the Java runtime, things like functions and numbers are Java objects. I’m going to call them values, though. In a book making distinctions between object-oriented and functional programming, using the word “object” in both contexts would be confusing. Moreover, Clojure values are (usually) used very differently than Java objects.
1.5 Functions are values
Clojure can do more than add. It can also ask questions about values. For example, here’s how you ask if a number is odd:
user> (odd? 2) false
There are other predicates that let you ask questions about what kind of value a value is:
user> ( number? 1 ) 2 true
You can ask the number?
question of a function:
user> (number? +)false
If you want to know if a value is a function, you use fn?
:
user> (fn? +)true user> (fn? 1)false
It’s important to understand that functions aren’t special. Consider these two expressions:
(+ 1 2) (fn? +)
In one case, the +
function gets called; in the other, it’s examined. But the difference between the two cases is solely due to the position of the symbol +
. In the first case, its position tells the evaluator that its function is to be executed; in the second, that the function is to be given as an argument to fn?
.
1.6 Evaluation is substitution
Let’s look in more detail at the evaluator. This may seem like overkill, but one of the core strengths of functional languages is the underlying simplicity of their evaluation strategies.
To add a little visual interest, let’s personify the evaluator as a bird. That’s appropriate because parent birds take in food, process it a little, then feed the result to their babies. The evaluator takes in data structures from the reader, processes them, and feeds the result to the printer. Here’s a picture of the evaluator at taking in a list:
An evaluator is a lazy bird, though. Whenever it sees a compound data structure, it summons other evaluators to do part of the work.
A list is a compound data structure, so (in this case) three evaluators are set to work:
The bottom two have an easy job: numbers are already digested (evaluate to themselves), so nothing need be done. The top bird must convert the symbol into the function it names.
Each of these sub-evaluators feeds its result to the original evaluator, which substitutes those values for the originals, making a list that is almost–but not quite–the same:
(The symbol has been substituted with a function.)
The original evaluator must process this list according to the rules for that data structure. That means calling the function in the first position and giving it the rest of the list as arguments. Since this is the top-level evaluator, that result is provided as nourishment to the printer:
Now consider a longer code snippet, like this:
user=> (+ 1(- 4 2 ))3
The first (top-level) evaluator is to consume this:
“Too complicated!” it thinks, and recruits three fellows for the three list elements:
The first two are happy with what they’ve been fed, but the last one has gotten another list, so it recruits three more fellows:
When the third-level birds finish, the lazy second-level bird substitutes the values they provide, so it now has this list:
It applies the -
function to 4 and 2, producing the new value 2
.
When all the second-level birds are done, they feed their values to the top-level evaluator:
The top-level evaluator substitutes them in:
It applies the function to the two arguments, yielding 3
, which it feeds to the printer:
1.7 Making functions
Suppose you type this:
user> (fn [n] (+ n n))
That’s another list handed to the evaluator, like this:
As another list headed by a symbol, this looks something like the function applications we’ve seen before. However, fn
is a special symbol, handled specially by any evaluator. There are a smallish number of special symbols in Clojure. The expressions headed by a special symbol are called special forms.
In the case of this special form, the evaluator doesn’t recruit a flock to handle the individual elements. Instead, it conjures up a new function. In this case, that function takes a single parameter 1, n
, and has as its body the list (+ n n)
. Note that the parameter list is surrounded by square brackets, not parentheses. (That makes it a bit easier to see the structure of a big block of code.)
I’ll draw function values like this:
The functions you create are just as “real” as the functions that come pre-supplied with Clojure. For example, they print just as helpfully:
user=> (fn [n] (+ n n))# <user$eval66$fn__67 user$eval66$fn__67 @ 5 ad75c47>
Once a function is made, it can be used. How? By putting it in the first position of a list:
user> ((fn [n](+ n n)) 4)________________8
(I’ve used the underlining to highlight the first position in the list.)
Although more cumbersome, the form above is conceptually no different than this:
user> (+ 1 2)3
In both cases, a function value will be applied to some arguments.
1.8 More substitution as evaluation
In ( (fn [n] (+ n n)) 4)
, our doubling function is applied to 4. How, precisely, does that work?
The whole thing is a list, so the top-level evaluator recruits two lower-level evaluators. One evaluates a list headed by the symbol fn
; the other evaluates a number. When they hand their values to the top-level evaluator, it substitutes, so it now has this:
It processes this function by substituting the actual argument, 4
, for its matching parameter, n
, anywhere in the body of the function:
Hey! Look! A list! We know how to handle a list. The list elements are evaluated by sub-evaluators, and the resulting function (the +
function value) is applied to the resulting arguments. Were the +
function value a user-written function, it would also be evaluated by substitution. So would be most of the Clojure library functions. There are some primitive functions, though, that are evaluated by Java code. (It can’t be turtles all the way down.)
Despite being tedious, this evaluation procedure has the virtue of being simple. (Of course, the real Clojure compiler does all sorts of optimizations.) But you may be thinking that it has the disadvantage that it can’t possibly work. What if the code contained an assignment statement, something like the following?
(fn [n] (assignn(+ 1 n)) (+ nn))
It doesn’t make sense to substitute a number into the left-hand side of an assignment statement. (What are you going to do, assign 4
the new value 5
?) And even if you did change n
’s value on the first line of the body, the two instances of n
on the second line have already been substituted away, something like this:
(assignn(+ 1 4))(+ 4 4))
Therefore, the assignment can’t have an effect on any following code.
Clojure avoids this problem by not having an assignment statement. With one exception that you’ll see shortly, there is no way to change the binding between a symbol and a value.
“Still,” you might object, “what if the argument is some data structure that the code modifies? If you pre-substitute the whole data structure wherever the parameter appears, changes to the data structure in one part of the function won’t be seen in other parts of the function!” Code suffering from this problem would look something like this:
(fn [tree] (replace-left-branch tree 5) (duplicate-left-branch tree))
Because of substitution, the tree on the last line that’s having its left branch duplicated is not the tree that had its left branch replaced on the previous line.
Clojure avoids this problem by not allowing you to change trees, sets, vectors, lists, hashmaps, strings, or anything at all except a few special datatypes. In Clojure, you don’t modify a tree, you create an entirely new tree containing the modifications. So the function above would look like this:
(fn [tree] (tree-with-duplicated-left-branch (tree-with-replaced-left-branchtree5)))
We’ll be discussing the details of all this in the chapter on immutability. For now, ignore your efficiency concerns–“Duplicating a million-element vector to change one element?!”–and delegate them to the language implementor. Also hold off on thinking that programming without an assignment statement has to be crazy hard–it’s part of this book’s job to show you it’s not.
1.9 Naming things
You surely don’t want to create the doubling function every time you use it. Instead, you want to create it once, then bind it to some sort of global symbol.
user> (def twice (fn [n] (+ n n)))#'user/twice
Once named, a user-defined function can be used as conveniently as a built-in function:
user=>(twice10)20
Since functions are values not essentially different than other values, you might expect that you can give names to strings, numbers, and whatnot. Indeed you can:
user> (def two 2)#'user/twouser> (twice two)4
You can use def
with a particular symbol more than once. That’s the only exception to Clojure’s “no changing a binding” rule 2. It’s useful for correcting mistakes:
user=> ( def twice ( fn [ n ] ( - n n )))user=> ( twice 10 )0 user=> ;; Darn! (This, by the way, is a Clojure comment.)user=> ( def twice ( fn [ n ] ( + n n )))user=> ( twice 10 )20
1.10 Lists
We’ve seen that lists are surrounded by parentheses. The evaluator function interprets a list as an excuse to apply a function to arguments. But lists are also a useful data structure. How do you say that you want a list to be treated as data, not as code? Like this:
user> '(1 2)(1 2)
The quote tells the evaluator not to interpret the list as a function call. That character is actually syntactic sugar for a more verbose notation:
user> (quote (1 2))(1 2)
The reader gives the evaluator this list:
The evaluator notices that the first element is the special symbol quote
. Instead of unleashing sub-evaluators, it digests the form into its single argument, which is what it feeds to the printer:
You can also create a list with a function:
user> (list 1 2 3 4) (1 2 3 4)
You can take apart lists. Here’s a way to get the first element:
user> (first '(1 2 3 4))1
Here’s a way to get everything after the first element:
user> (rest '(1 2 3 4))(2 3 4)
You can pick out an element at a particular (zero-based) position in a list:
user> (nth '(1 2 3 4) 2)3
Exercise 1: Given what you know now, can you define a function second
that returns the second element of a list? That is, fill in the blank in this:
user> (def second (fn [list] ____))
Be sure to try your solution at the repl. (When you do, you’ll notice that you’ve just overridden Clojure’s built-in second
function. Don’t worry about that.)
You can find solutions to this chapter’s exercises in solutions/just-enough-clojure.clj
.
Exercise 2: Give two implementations of third
, which returns the third element of a list.
1.11 Vectors
Lists are (roughly) the classic linked list that many of us encountered when we first learned programming. That means code has to traverse the whole list to get to the last element. Clojure’s creator cares about efficiency, so Clojure also makes it easy to use vectors, where it takes no more time to access the last element than the first.
Vectors have a literal notation, in which the elements are surrounded by square brackets:
user> [ 1 2 3 4 ][ 1 2 3 4 ]
Note that I didn’t have to quote the vector to prevent the evaluator from trying to use the value of 1
as a function. That only happens with lists.
There’s also a function-call notation for creating vectors:
user> (vector 1 2 3 4)[1 2 3 4]
The first
, rest
, and nth
functions also work with vectors. Indeed, most functions that apply to lists also apply to vectors.
1.12 Vector? List? Who cares?
Both vectors and lists are sequential datatypes.
user=> (sequential? [1 2 3])trueuser=> (sequential? '(1 2 3))true
There’s a third datatype called the lazyseq (for “lazy sequence”) that’s also sequential. That datatype won’t be relevant until we discuss laziness. I mention it because some functions that you might think produce vectors actually produce lazyseqs. For example, consider this:
user=> (rest [1 2 3])(2 3)
The first time I typed something like that, I expected the result to be the vector
[2 3]
, and the parentheses confused me. The result of
rest
is a lazyseq, which prints the same way as a list. Here’s how you can tell the difference:
user=> (list? (rest [1 2 3]))false user=> (seq? (rest [1 2 3]))trueuser=> (vector? (rest [1 2 3]))false
Such changes of type seem like they’d lead to bugs. In fact, the differences almost never matter. For example, equality doesn’t depend on the type of a sequential data structure, only on the contents. Therefore:
user=> (= [2 3] '(2 3))trueuser=> (= [2 3] (rest [1 2 3]))true
The single most obvious difference between a list and vector is that you have to quote lists.
It will never matter in this book whether you create a list or vector, so suit your fancy. I will often use “sequence” from now on when the difference is irrelevant.
seqs
The predicate seq?
doesn’t actually check specifically for a lazyseq. It responds true
for both lists and lazyseqs, and the word seq is used as an umbrella term for both types. If you really need to know the complete set of sequential types and the names that refer to them, see the table below. However, the definition of a seq will never matter for this book.
Lists | Vectors | Lazyseqs | ||
---|---|---|---|---|
sequential? | YES | YES | YES | |
seq? | YES | no | YES | |
list? | YES | no | no | |
vector? | no | YES | no | |
coll? (for “collection”) | YES | YES | YES |
1.13 More on evaluation and quoting
When the evaluator is given a list from the reader, it first evaluates each element of the list, then calls the first element as a function. When it’s given a vector, it first evaluates each element and then packages the resulting values as a (different) vector.
That means that literal vectors can (and often do) contain code snippets:
user=> [(+ 1 1)(- 1 1)][2 0]
It also means quoting is sometimes required for vectors as well as lists. Can you guess the results of these two code snippets?
[inc dec]
'[inc dec]
The first is a vector of two functions:
user=> [inc dec][#<core$inc clojure.core$inc@13ab6c1c> #<core$dec clojure.core$dec@7cdd7786>]
The second is a vector of two symbols (which happen to name functions):
=> '[inc dec][inc dec]
At first, you’re likely to be confused about when you need to quote. Basically, if you see an error like this:
java.lang.Exception:Unable to resolve symbol: foo in this context(NO_SOURCE_FILE:67)
… it probably means you forgot a quote.
Quoting doesn’t only apply to entire lists and vectors. You can quote symbols:
user=> 'aa
You can also quote individual elements of vectors:
user=> ['my 'number (+ 1 3)] [my number 4]
1.14 Conditionals
Despite the anti-if campaign, the conditional statement is one of primordial operations of the Turing Machine (that is, computer). Conditionals in Clojure look like this:
user=> (if (odd? 3) (prn "Odd!") (prn "Even!")) "Odd!"nil
The prn
function prints to the output. Unlike in some languages, if
s are expressions that produce values and can be embedded within other expressions. The value of an if
expression is the value of the “then” or “else” case (whichever is chosen). Since prn
always returns the value nil
, that’s what the repl printed in the example above. (nil
is called null
in some other languages–it’s the object that is no object, or the pointer that points to nothing, or what Tony Hoare called his billion-dollar mistake.)
1.15 Rest arguments
Clojure functions can take a variable number of arguments:
user> (add-squares 1 2)5 3 user> ( add-squares 1 2 3 ) 4 14
As with other languages, there’s a special token in a function’s parameter list to say “Take any arguments after this point and wrap them up in a sequential collection (list, vector, whatever)”. Clojure’s looks like this:
user> ((fn [& args] args) 1 2 3 4) __________________ (1 2 3 4)
That function gathers all the arguments into the list args
, which it then returns.
Note the space after the &
. It’s required.
Now that we know how to define rest arguments, here’s what add-squares
’ definition would look like:
(def add-squares (fn [ & numbers] (...something... numbers)))
What could the “something” be? The next section gives us a clue.
1.16 Explicitly applying functions
Suppose we have a vector of numbers we want to add up:
[1 4 9 16]
That is, we want to somehow turn that vector into the same value as this +
expression:
user=> (+ 1 4 9 16)30
(Notice that +
can take any number of arguments.)
The following is almost what we want, but not quite:
user=> (+ [1 4 9 16])java.lang.ClassCastException (NO_SOURCE_FILE:0)
What we need is some function that hands all the elements of the vector to +
as if they were arguments directly following it in a list. Here’s that function:
user=> (apply + [1 4 9 16])30
apply
isn’t magic; we can define it ourselves. I think of it as turning the second argument into a list, sticking the first argument at the front, and then evaluating the result in the normal way a list is evaluated. Or:
(def my-apply (fn [function sequence] (eval (cons function sequence))))
Let’s look at this in steps.
cons
(the name chosen more than 50 years ago as an abbreviation for the verb “construct”) produces a list 3 whosefirst
element iscons
’s first argument and whoserest
iscons
’s second argument:user=> (cons "the first element"[1 2 3]) ("the first element" 1 2 3)
(Notice that
cons
, likerest
earlier, takes a vector in but doesn’t produce one.)eval
is our old friend the bird-like evaluator. Inmy-apply
, it’s been given a list headed by a function, so it knows to apply the function to the arguments.
According to the substitution rule, (my-apply + [1 2 3])
is first converted to this:
(eval (cons + [1 2 3]))
After that, it is evaluated “from the inside out”, each result being substituted into an enclosing expression, finally yielding 6. 4
1.17 Loops
How do you write loops in Clojure?
You don’t (mostly).
Instead, like Ruby and other languages, Clojure encourages the use of functions that are applied to all elements of a sequence. For example, if you want to find all the odd numbers in a sequence, you’d write something like this:
user> (filter odd? [1 2 3 4])(1 3)
The filter
function applies its first argument, which should be a function, to each element of its second argument. Only those that “pass” are included in the output.
Question: How would you find the first odd element of a list?
Answer:
user> (first (filter odd? [1 2 3 4]))1
Question: Isn’t that grossly inefficient? After all, filter
produces a whole list of odd numbers, but you only want the first one. Isn’t the work of producing the rest a big fat waste of time?
Answer: No. But you’ll have to read the later discussion of laziness to find out why.
The map
function is perhaps the most common loop-like function. (If you know Ruby, it’s the same as collect
.) It applies its first argument (a function) to each element of a sequence and produces a sequence of the results. For example, Clojure has an inc
function that returns one plus its argument. So if you want to increment a whole sequence of numbers, you’d do this:
user> (map inc [0 1 2 3])(1 2 3 4)
The map
function can take more than one sequence argument. Consider this:
user> (map * [0 1 2 3] [100 200 300 400])(0 200 600 1200)
That is equivalent to this:
user=> (list (apply * [0 100]) (apply * [1 200]) (apply * [2 300]) (apply * [3 400]))
1.18 More exercises
Exercise 3: Implement add-squares
.
user=> (add-squares 1 2 5)30
Exercise 4: The range
function produces a sequence of numbers:
user=> (range 1 5)(1 2 3 4)
Using it and apply
, implement a bizarre version of factorial that uses neither iteration nor recursion.
Hint: The factorial of 5 is 1*2*3*4*5.
Exercise 5: Below, I give a list of functions that work on lists or vectors. For each one, think of a problem it could solve, and solve it. For example, we’ve already solved two problems:
user> ;; Return the odd elements of a list of numbers.user> (filter odd? [1 2 3 4])(1 3) user> ;; (One or more semicolons starts a comment.user> user> ;; Increment each element of a list of numbers,user> ;; producing a new list.user=> (map inc [ 1 2 3 4 ])(2 3 4 5)
You’ll probably need other Clojure functions to solve the problems you put to yourself. Therefore, I also describe some of them below.
Clojure has a built-in documentation tool. If you want documentation on filter
, for example, type this at the repl:
user => (doc filter) ------------------------- clojure.core / filter ([pred coll])Returns a lazy sequence of the items in coll for which (pred item) returns true. pred must be free of side-effects .
Many of the function descriptions will refer to “sequences”, “seqs”, “lazy seqs”, “colls”, or “collections”. Don’t worry about those distinctions. For now, consider all those synonyms for “either a vector or a list”.
In addition to the built-in doc
, clojuredocs.org has examples of many Clojure functions.
Functions to try
take
distinct
concat
repeat
interleave
drop
anddrop-last
flatten
partition
only the[n coll]
case, like:(partition 2 [1 2 3 4])
every?
remove
and create the function argument withfn
Other functions
(= a b)
– Equality(count sequence)
– Lengthand
,or
,not
– Boolean functions(cons elt sequence)
– Make a new sequence with theelt
on the frontinc
,dec
– Add and subtract one(empty? sequence)
– Is the sequence empty?(nth sequence index)
– Uses zero-based indexing(last sequence)
– The last element(reverse sequence)
– Reverses a sequenceprint
,println
,prn
– Print things.print
andprintln
print in a human-friendly format. For example, strings are printed without quotes.prn
prints values in the literal format you’d type to create them. For example, strings are printed with double quotes.println
andprn
add a trailing newline;print
does not. All of these can take more than one argument.pprint
– Short for “pretty print”, it prints a nicely formatted representation of its single argument.
Note
If the problems you think of are anything like the ones I think of, you’ll want to use the same sequence in more than one place, which would lead to annoying duplication. Since you don’t know how to create local variables yet, the easiest way to avoid duplication is to create and call a function:
(def solver(fn [x](... x ... ... ... ... x ... ...)))
(solver [1 2 3 4 5 6 7])
You can find my problems and solutions in solutions/just-enough-clojure.clj.
Exercise 6: Implement this function: (prefix-of? candidate sequence)
: Both arguments are sequences. Returns true
if the elements in the candidate
are the first elements in the sequence
:
user> (prefix-of? [1 2 ] [1 2 3 4])true user> (prefix-of? '(2 3) [1 2 3 4])false user> (prefix-of? '(1 2) [1 2 3 4])true
Exercise 7: Implement this function: (tails sequence)
: Returns a sequence of successively smaller subsequences of the argument.
user> (tails '(1 2 3 4))((1 2 3 4) (2 3 4) (3 4) (4) ())
To implement tails
, use range
, which produces a sequence of integers. For example, (range 4)
is (0 1 2 3)
.
This one is tricky. My solution is very much in the functional style, in that it depends on sequences being easy to create and work with. So I’ll provide some hints. Here and hereafter, I encourage you to try to finish without using the hints, but not to the point where you get frustrated. Programming is supposed to be fun.
Hint: What is the result of evaluating this?
[(drop 0 [1 2 3]) (drop 1 [1 2 3]) (drop 2 [1 2 3]) (drop 3 [1 2 3])]
Hint: map
can take more than one sequence. If you give it two sequences, it passes the first of each to its function, then the second of each, and so on.
Exercise 8: In the first exercise in the chapter, I asked you to complete this function:
(def second (fn [list] ____ ))
Notice that list
is a parameter to the function. We also know that list
is (globally), a function in its own right. That raises an interesting question. What is the result of using the following function?
user=> (def puzzle (fn [list] (list list)))user=> (puzzle '(1 2 3))????
Why does that happen?
Hint: Use the substitution rule for functions.
- I will consistently use “argument” for real values given to functions and “parameter” for symbols used to name arguments in function definitions. So
n
is a parameter, while a real number given to our doubling function would be an argument.↩ def
isn’t actually an exception. It looks like just another way of associating a symbol with a value, but it’s actually doing something different. The difference, though, is irrelevant to this book, and would just complicate your understanding to no good end, so I’m going to ignore it. If you’re curious, see the description ofVar
in the Clojure documentation or any other book on Clojure.↩- Strictly,
cons
produces a lazyseq, not a list, but the evaluator treats them the same. ↩ - The substitution as printed isn’t quite true. After it receives
(my-apply + ...)
from the reader, the evaluator processes the symbolsfunction
and+
to find function values. Therefore, in the expansion ofmy-apply
, thefunction
parameter is substituted with an argument that’s a function value. And so the list given toeval
starts with a function value, not a symbol. That’s different than what we’ve seen before. But it still works fine, because a function value self-evaluates the way a number does. I opted for the easier-to-read expansion.↩
Embedding an Object-Oriented Language
Many object-oriented languages were first implemented by embedding them into procedural languages. Objective-C was originally a C preprocessor hack. The C++ compiler originally emitted C code for the C compiler to compile. And during the gold rush phase of objects, many downright loopy object systems were written in Lisp. These embedded languages were cheap and useful ways to learn what object orientation was all about.
In this part of the book, we’ll use Clojure to implement an object system patterned after Java’s. (In the optional Part V, we’ll extend it to be more like Ruby’s.)
Before we start, though, it’s important for us to agree on what words mean. An instance is synonymous with “object”, but it’s often used to emphasize that the object has been instantiated from a class, whose role is to describe (in some sense) a lot of similar objects.
Instances contain instance variables, which are named bits of data. These variables may or may not be defined by the class. (In Java, they are. In Ruby, they are not.)
In Clojure, computation is done by applying functions to arguments. For objects, we’ll use a different metaphor: messages are sent to receivers. As a result, a method (which is, roughly, a function) is applied to the receiver and any arguments sent along with the message. Methods are defined by classes.
Messages are just names. The same name may apply to many different methods (each in a different class). A dispatch function selects one of those methods by examining the class of the receiver.
Instances are created with constructors. In some object systems, constructors are ordinary methods; in others (like Java’s), they are not.
After a short introduction describing the relationship between functions and methods, we’ll proceed in these steps:
- Creating a barely believable object that’s nothing but instance variables, a rudimentary constructor, and a vestigial class.
- Embedding methods within the constructor, making it look a bit like a class definition.
- Define methods in the class rather than in the constructor.
- Adding superclasses and inheritance.
While this section appears to be about object-oriented programming, not functional programming, it gives you the opportunity to practice programming in a functional language. That experience will make the topics in the next part of the book easier to grasp.
2. Objects as a Software-Mediated Consensual Hallucination
Cyberspace. A consensual hallucination experienced daily bybillions of legitimate operators, in every nation… A graphicrepresentation of data abstracted from the banks of everycomputer in the human system. Unthinkable complexity. Linesof light ranged in the nonspace of the mind, clusters andconstellations of data. Like city lights, receding.
— William Gibson, Neuromancer, 1984.
Sometime in the early 1980’s, I introduced Ralph Johnson to the head of the Research Division of a computer manufacturer that doesn’t exist any more. This was in the days when Smalltalk was the object-oriented language, and Ralph was an expert in Smalltalk. At one point during the discussion, the division head said, “We were doing object-oriented programming 20 years ago! In assembly language!” That comment was both:
- true, and
- irrelevant.
It was true because you certainly can do object-oriented programming in assembler. In some sense, you have to, because computer hardware doesn’t have objects. It has numbered locations that store words of data. It doesn’t have methods, either. It just has instructions that provide a limited kind of function. Object-orientation has to be built up out of that, these days usually with more than one layer of intermediate language.
It was irrelevant because doing OO in assembler is so hard that the kind of designs that flow naturally out of a good language just don’t happen.
However, it’s an important point that object-orientation is really nothing more than some conventions for using data, conventions that are both supported and hidden by the language. Consider this Java method that shifts a point by some increments:
public class Point { private int x ; private int y ;
void shift (int xinc, int yinc) { x += xinc ; y += yinc ; }}
In Python, the equivalent method would be written like this:
class Point: def shift (self, xinc, yinc) self.x += xinc self.y += yinc
The Python method has a self
parameter, whereas the Java one appears not to. Python is being more honest (though less convenient) than Java. Every Java method really does have a self
parameter (though Java calls it this
). But since that parameter must always be there, the language designers decided to make it implicit.
The Java designers also decided to change the syntax of functions to single out the first argument. In the old-fashioned math you learned at school, functions take their arguments at the right:
shift(point, xinc, yinc)reflect-across-origin(point)...
In object-oriented programming, we know we’d have a pile of functions that would always take the same kind of first argument, so OO languages use a human-friendly out-of-order syntax:
point.shift(xinc, yinc)point.reflect-across-origin
Even Python uses this syntax. But, somewhere behind the scenes, that format is converted into the old-fashioned format (so that the self
argument is in the right place).
Another way in which Java hides conventions is that it pretends that instance variables are more distinct than they are. Consider these two variants of the same method:
public class Point { private int x ; private int y ;
void shift1 (int xinc, int yinc) { x += xinc ; y += yinc ; } void shift2 (int xinc, int yinc) { this. x += xinc ; this. y += yinc ; }
The first definition makes the instance variables seem like very distinct things within the broad scope of the class. The second hints at what they really are: a single data structure that contains a mapping (or dictionary) from names to values.
So: what’s an object? It’s a clump of name->value mappings, some functions that take such clumps as their first arguments, and a dispatch function that decides which function the programmer meant to call. This reality is usefully obscured by the language so that programmers can, without thinking, do wonderful things, blissfully pretending that the pictures in their head are what the computer is really doing.
3. A Barely Believable Object
Let’s start implementing our consensual hallucination of objects.
3.1 Maps
In Clojure, the map is the data structure of choice for connecting names to values. It’s like Java’s HashMaps, Ruby’s Hashes, or Python and Smalltalk’s Dictionaries. Maps have this literal notation:
user> {:a "b" 2}{:a 1, "b" 2}
- The first, third, and following odd-numbered elements are the keys. They can be any type of object, but it’s very common to use colon-prefixed keywords because, unlike symbols, they’re self-evaluating (don’t need to be quoted).
- The second, fourth, and following even-numbered elements are the values. They can also be of any type (including nested maps).
- It’s common to use commas to separate key-value pairs. In Clojure, commas are white space: the reader ignores them.
There’s also a function that creates maps:
user> (hash-map :a 1 :b 2){:a 1, :b 2}
It’s not unusual to apply hash-map
to a sequence, like this:
user=> (apply hash-map [:a 1 :b 2]){:a 1, :b 2}
That allows something like keyword arguments:
1 user=> ( do-something-with-a-colored-point :x 1 :y 2 :color "red" )user=> ;; Arguments can be in any orderuser=> (do-something-with-a-colored-point :color "red", :x 1, :y 2)user=> (def do-something-with-a-colored-point (fn [&args] ...(apply hash-map args)...))
To retrieve a value from a map, you can use get
:
user> (get {:a 1, :b 2} :a)1
If you try to fetch the value of a key that’s not in the map, you get nil
:
user=> (get {} :x)nil
get
is actually somewhat rare in Clojure code, though. Keywords have the nice property that they act like functions when placed as the first element of a list:
1 user> (:a { :a 1, :b 2}) 1
Consider :a
in the above to mean “ get
the value using me as the key”. In this book, we’ll be using this style a lot, and we’ll often write functions like this one:
(def do-something-to-map (fn [function] (function {:a "a value", :b "b value" })))
do-something-to-map
can legitimately be given either a true function or a keyword:
user=> (do-something-to-map :a) "a value"user=> (do-something-to-map count)2
To keep from having to say “either a function or a keyword” in the rest of the book, I’ll use callable as the umbrella term for anything that behaves like a function when it’s in the first position of a evaluated list 1.
Clojure gives you no way to modify existing maps, so they’re “changed” by building new maps from old ones. To add a single element, you use assoc
:
1 user=> (assoc {:a 1, :b 2} :c 3){:c 3, :a 1, :b 2 }
You can use assoc
to add multiple key-value pairs:
1 user=> ( assoc { :a 1, :b 2 } :c 3 :d 4 :e 5 ){ :e 5,:d 4, :c 3, :a 1, :b 2}
You can also merge two or more maps:
1 user=> (merge { :a 1, :b 2} { :c 3, :d 4 } { :e 5 }){:e 5, :d 4, :c 3, :a 1, :b 2}
You can exclude key-value pairs from a map with dissoc
:
user=> (dissoc {:a 1,:b 2,:c 3} :b :c){:a 1}
Question: How do assoc
and merge
handle duplicate keys? Try it and see!
user=> (assoc {:a 1} :a 2222)????user=> (merge {:a 1,:b 2,:c 3} {:a 111, :b 222, :d 4} {:b "two"})???
3.2 I present to you an object
Let’s make a constructor for a Point
class. Here’s a minimal version:
(def Point (fn [x y] { :x x :y y }))
What do we see here? We have two instance variables x
and y
. Instance variables aren’t encapsulated, so we can access them like this:
user=> (:x (Point 1 2))1
That would be the equivalent of object.field
in Java.
In this book, we won’t implement the encapsulation rules of Smalltalk or Ruby (neither of which allow direct access to instance variables). We will often implement and use accessor (getter) methods, though. Here’s one:
(def x (fn [this] (get this :x)))user=> (x (Point 1 2))1
However, since keywords are callables, we could define x
more simply:
(def x (fn [this] (:x this)))
or even just this:
(def x :x)
3.3 The class begins as documentation
The result of (Point 1 2)
prints like this:
{:x 1, :y 2}
If that was the first line of code you saw in this book, you could probably guess it represented a mathematical point, but that’s only because you’ve already seen a million examples of them. You’d have much more trouble with other kinds of objects.
So let’s add the class. For the moment, it’ll just be used as documentation. Because it’s a kind of metadata (data about data), I’ll give it a funny name:
(def Point (fn [x y] {:x x :y y :__class_symbol__ 'Point })) ;; <<==
From Clojure’s point of view, a keyword like :__class_symbol__
is no different than any other. To us, though, this double-underscore convention will signal that a keyword is part of the workings of the object system, not something that ordinary client code would ever use. (In more polished object systems, this kind of metadata is typically inaccessible to client code.)
Now we can get an object’s class easily:
(def class-of :__class_symbol__)user=> (class-of (Point 1 2))Point
(I’m using class-of
instead of class
because Clojure already has a class
function.)
Given a large enough dose of magic mushrooms, we can hallucinate that the class-of
, x
, and y
callables are instance methods of Point
. (It requires mushrooms because we’re used to thinking of methods as being somehow attached to objects, and these are free-floating. We’ll fix that in the next chapter.)
Here’s a less boring method: shift
. It takes a particular point and shifts it according to an x-increment and a y-increment. Since Clojure doesn’t let us modify maps, shift
has to create a new Point
.
(def shift (fn [this xinc yinc] (Point (+ (x this) xinc) (+ (y this) yinc ))))user=> (shift (Point 1 200) -1 -200){:x 0, :y 0, :__class_symbol__Point}
3.4 Exercises
You can find starting Clojure code in sources/add-and-make.clj
. You can either copy-and-paste the code into the repl, or you can type the following to a repl started in the root directory of a cloned repository:
user=> (load-file "sources/add-and-make.clj")
Note that Clojure requires that you def
any name (like a function name) before you can use it. If you paste the definition of shift
(which uses Point
) before the definition of Point
, you’ll get this error:
java.lang.Exception: Unable to resolve symbol: Point in this context( NO_SOURCE_FILE :3)
You can find my solutions for these exercises in solutions/add-and-make.clj
.
Exercise 1: Implement add
.
Implement an add
function that adds two points, producing a third. First implement it without using shift
. Then implement it using shift
. (If you think of add
as an instance method, calling shift
is like using another instance method in the same class.)
Exercise 2: A new
operat Our Point
function matches the way Python constructors are called. Java would use new Point
and Ruby would use Point.new
. That suggests an alternative syntax:
(new Point 3 5)
However, Clojure reserves new
for the creation of Java objects, so we’ll use make
instead:
(make Point 1 2)
Write the function make
, assuming that the function Point
already exists.
The exercise source contains a Triangle
constructor. Does your make
work with it? For example:
(make Triangle (make Point 1 2) (make Point 1 3) (make Point 3 1))
If not, make it work.
Exercise 3: sources/add-and-make.clj
also defines three triangles: right-triangle
, equal-right-triangle
, and different-triangle
. Write a function equal-triangles?
that produces these results:
user=> ;; Identical objects user=> (equal-triangles? right-triangle right-triangle)trueuser=> ;; Not identical, but contents are equaluser=> (equal-triangles? right-triangle equal-right-triangle) trueuser=> ;; differentuser=> (equal-triangles? right-triangle different-triangle)false
It’s easier than you probably think!
Exercise 4: Change equal-triangles
so that it can compare more than two triangles:
user=> (equal-triangles? right-triangle equal-right-triangle different-triangle)false
It’s way easier than you might think!
Exercise 5: Start to write a function valid-triangle?
that takes three Points and returns either true
or false
. In this exercise, only check to see whether any of the points are duplicates. Your first thought might be to do this:
(def valid-triangle? (fn [point1 point2 point3] (and (not= point1 point2) (not= point1 point3) (not= point2 point3))))
However, that approach is prone to typos 2. You can use one of the sequence functions you explored in the previous chapter to do a more concise job.
- Vectors and maps are also callables, though we won’t use that fact in this book. If you’re curious, try
({:a 1, :b 2} :a)
and(["zero" "one"] 1)
.↩ - I once found a bug in a fairly complicated Unix kernel function. It had three “inode” parameters:
i
,ii
, andiii
. Guess what the bug was?↩
4. All the Class in a Constructor
We don’t usually think of objects having their methods scattered all over the global namespace the way shift
and add
are. We usually think of methods as somehow belonging to objects:
Let’s have our constructor embed functions in the map it returns:
(def Point (fn [x y] {;; initializing instance variables :x x :y y ;; Metadata :__class_symbol__ 'Point :__methods__ { :class :__class_symbol__ ;; Not implementing getters for `x` and `y` yet. :shift (fn [this xinc yinc] (make Point (+ (:x this) xinc) (+ (:y this) yinc)))}}))
- That’s starting to look a little like a class definition: it names instance variables and defines methods.
- Notice that I’m using the “
make Point
” style object construction that you implemented in the previous chapter’s exercises. - For tidiness’ sake, I’m not defining the methods directly alongside the instance variables. Instead, I’m isolating them inside an embedded map.
Because of the embedded map, retrieving a method is a bit complicated:
user => (: shift (: __methods__ (make Point 1 2)))#<user$Point$fn__588 user$Point$fn__588@3764f8d4>
And applying one is not exactly graceful:
user=> (def point (make Point 1 2))user=> ((:shift (:__methods__ point)) point -2 -3 )_____________________________{:x -1 , :y-1, :__class_symbol__Point,:__methods__{...}}
That clearly won’t do. Let’s add a send-to
function that looks more like a message send in a regular object-oriented language. Like this:
user=> (send-to point :shift -2 -3){:x -1, :y-1, :__class_symbol__Point,:__methods__{...}}
send-to
is easiest to implement using a feature of apply
I didn’t show you earlier. apply
can take more than a function and a sequence as arguments. It can also have one or more additional arguments between the two; those are prepended to the front of the sequence. Like this:
user=> (apply + 1 [2 3])6user=> (apply + 1 2 [ 3 ]) 6 user=> (apply + 1 2 3 [])6
That given, the definition of send-to
is this:
(def send-to (fn [object message & args] (apply (message (:__methods__ object)) object args )))
Make sure you understand send-to
, since we’ll be changing it for the rest of this part of the book.
4.1 One exercise
Change the Point constructor to add x
and y
accessors (getters). Use them in shift
. Implement add
, and have it use shift
. You can find the source for the code so far in sources/embedded-functions.clj
. My solution is insolutions/embedded-functions.clj
.
5. Moving the Class Out of the Constructor
So far, our implementation isn’t typical of object systems. It’s unusual for every single instance of a class to contain references to all of its methods, using the class itself as merely an identifying name. Instead, in most object systems the instance has a single reference to its class, and it finds its methods via that link. The methods are better thought of as belonging to the class than to the instance. In this chapter, we’ll shift over to that implementation.
First, we’ll pull out the methods from the instance into a new Point
object:
(def Point;; (fn [x y] ;; {;; initializing instance variables ;; :x x ;; :y y ;; ;; ;; Metadata ;; :__class_symbol__'Point { :__instance_methods__ { :class :__class_symbol__ :shift (fn [this xinc yinc] (make Point (+ (:x this) xinc) (+ (:y this) yinc ))) } })
I’ve changed __methods__
to __instance_methods__
to emphasize that the methods are to be used with an instance, not the class. (It is the instance that is passed to them as their this
argument.)
We have to find a replacement for what the commented-out code used to do. We no longer have a Point
constructor, but you’ve already implemented an alternative notation for us to use:
user => (make Point 1 2)
Your old implementation will have to be updated, though. Let’s pattern the revised make
after the three steps new
performs in many object-oriented languages:
- Objects usually use a contiguous block of memory to store instance variables. So that memory is first allocated.
In our case, we’ll continue to use maps, so our “allocation” will look like this:
{}
- The empty object is seeded with metadata needed by the language runtime (such as information about what its class is).
In our case, that’s easy:
(assoc allocated : __class_symbol__ 'Point)
- Finally, (what amounts to) an instance method is called to fill in the starting values of instance variables. (That’s the constructor in Java, or
initialize
in Ruby.)Since Clojure doesn’t allow modification of existing maps, the called function must create a new map with
alloc
ormerge
. To (slightly) emphasize that, I won’t call the methodinitialize
. Instead, the user-supplied function will be calledadd-instance-values
.
Before implementing make
, let’s add add-instance-values
to the class:
(def Point { :__instance_methods__ { :add-instance-values ;; <<= new (fn [this x y] (assoc this :x x :y y )) :shift (fn [this xinc yinc] (make Point (+ (:x this) xinc) (+ (:y this) yinc))) }})
We can now implement make
. Its code will be clearer if we use a new Clojure special form.
5.1 Let
One way to introduce something like a local variable is to use nested functions. Suppose we wanted to implement the following without the duplication:
user=> (* (+ 1 2) (+ 1 2) 5)45
We could do this:
user=> ((fn [name] (* name name 5)) (+ 1 2))___________________________ 45
But that’s not exactly graceful or readable. So Clojure provides an alternate way to name sub-computations. It’s called let
:
user=> (let [name (+ 1 2)] (* name name 5))45
Notice that let
expressions return a value. So you can nest them inside other expressions:
user=> (+ 1 (let [one 1] (* one one)) 3 )_________________________5
You can create more than one name with a let
:
user=> (let [one 1 two 2] (+ one two ))3
Notice that all the name-value pairs are surrounded by a single set of square brackets. That’s like the way that brackets are used to hold function parameters.
Names take effect immediately, so a later computation in a let
parameter list can use an earlier one:
user=> (let [little-map {:a 1} bigger-map (assoc little-map :b 2)] bigger-map){:b 2, :a 1}
A hint
let
expressions define a computation as a series of steps. If you find multi-step let
expressions confusing, execute each step at the repl. To show what I mean by that, here’s a silly function that operates on a map like {:a1}
:
(fn [starting-map](let [bigger-map (assoc starting-map :b 2)overridden-a (assoc bigger-map :a 33)]overridden-a))
You can puzzle out the steps like this:
user=> (def starting-map {:a 1})user=> (def bigger-map (assoc starting-map :b 2))user=> bigger-map {:b 2, :a 1}user=> (assoc bigger-map:a 33){:b 2, :a 33}
5.2 Implementing instance creation
Recall that the instance creation function has three steps: allocation, seeding with metadata, then calling the user-provided constructor-like method. So the structure for our new make
function can use a let
to give a name to each step’s result:
(def make (fn [class & args] (let [allocated {} seeded ... finished-instance ... ] finished-instance )))
The allocated
step was easy. Earlier, I said we could use code like this for seeded
:
(assoc allocated :__class_symbol__ 'Point)
But we have a problem. Where do we get 'Point
from? In the evaluation of the expression (make Point 1 2)
, the value bound to the symbol Point
will be substituted for make
’s first parameter (class
). But that value is a map, and the symbol Point
appears nowhere in it. We’ll have to add it as a new bit of metadata:
(def Point{ :__own_symbol__ 'Point ;; <== new :__instance_methods__ { ... }})
It’s annoying that Point
is bound to a map that refers straight back to Point
, but we’re stuck with that. Languages with syntactic sugar for class definitions hide such circularity from the programmer 1.
So the “seeded” instance will be created with this:
(let [allocated {}seeded (assoc allocated:__class_symbol__ (:__own_symbol__ class))
In order to create the finished instance, we have to find and apply a particular method, namely
:add-instance-values
. Finding the method looks like this:
(:add-instance-values (:__instance_methods__ class))
Let’s use let
to name that constructor:
(let [allocated {}seeded (assoc allocated:__class_symbol__ (:__own_symbol__ class))constructor (:add-instance-values ; <<<<= new(:__instance_methods__ class))
Once we have the constructor, we need only apply it to the half-finished (“seeded”) constructor and whatever arguments the user gave:
(let [allocated {}seeded (assoc allocated :__class_symbol__ (:__own_symbol__ class)) constructor (:add-instance-values(:__instance_methods__ class))](apply constructor seeded args)))) ; <<<<= new
Since the constructor returns the new map that is to be (hallucinated to be) the object, that’s the return value of make
.
All that given, the final implementation for make
looks like this:
(def make (fn [class & args](let [allocated {}seeded (assoc allocated 5 :__class_symbol__ ( :__own_symbol__ class))constructor (:add-instance-values(:__instance_methods__ class))](apply constructor seeded args))))
5.3 Message dispatch
We now need to make calls like this work:
user=> (send-to (make Point 1 2) :shift -2 -3)
Message dispatch will be similar to the last part of make
, but not identical:
:add-instance-values
isn’t the only message we can send.- Whereas
make
is given a class to work with,send-to
is given an instance and has to look up the class.
That suggests a definition something like this:
(def send-to 2 (fn [object message & args](let [class (???? object ????)method (message (:__instance_methods__ class))](apply method object args))))
The only new bit is how you go from an instance to its class. This is complicated because the instance’s :__class_symbol__
is the symbolPoint
, not the value that symbol is bound to. To make the distinction clear(er), let’s put both a symbol and its value into a map:
user=> (def SomeClass "...pretend there's a class definition here...")user=> (def some-instance {:__class_symbol__ 'SomeClass :__class__ SomeClass })user=> some-instance{ :__class_symbol__SomeClass, :__class__"...pretend there's a class definition here..."}
We got the symbol SomeClass
into the map by protecting it from evaluation with quote
. Since eval
removes quotes, it follows that we should get the class the symbol names with eval
. (We saw a similar use of eval
when we used it to define apply
.) Like this:
user=> (eval (:__class_symbol__ some-instance))"...pretend there's a class definition here..."
So that finishes send-to
:
(def send-to (fn [instance message & args ] (let [class (eval (:__class_symbol__ instance)) method (message (:__instance_methods__ class))] (apply method instance args))))
One cosmetic change
In this chapter, I wanted to explain the three-step object-creation-and-initialization process common in OO languages, but separating two of those steps is rather silly in Clojure:
(let [allocated {}seeded (assoc allocated:__class_symbol__ (:__own_symbol__ class))
It would be better to write this:
(let [seeded {:__class_symbol__ (:__own_symbol__ class)}]
This works because, as with lists and vectors, eval
recursively evaluates all the entries between literal curly-brace tokens before forming the map. So we can put arbitrary expressions inside curly braces. Here’s another example:
user=> {:two (+ 1 1)}{:two 2}
5.4 Exercises
You can find the source for make
and send-to
, as well as a definition of the Point
class, in sources/class.clj
. My solutions are insolutions/class.clj
.
Exercise 1: The last two steps of make
and send-to
are very similar. Both look up an instance method in a class, then apply that method to an object and arguments. Extract a common function apply-message-to
that takes a class, an instance, a message, and a sequence of arguments. Like this:
(def apply-message-to (fn [class instance message args]... ))(apply-message-to Point a-point :shift [1 3])
It should use the class
(a map, not a symbol) and the message
(a keyword) to find a method/function. It should apply that method to the instance
and the args
. (You may have noticed that you can get the class
from the instance
, so those two separate parameters are not strictly needed. I thought it worthwhile to give each of the key values names in the parameter list.)
Feel free to define helper functions.
Next, use apply-message-to
within both make
and send-to
.
Exercise 2: Up until now, the :class
message has returned the symbol naming the class. That was OK while an object’s class was nothing but a symbol. But now it’d be more appropriate to have class-name
return the symbol and class
return the actual class map. Implement those methods so that this code works:
user=> (def point (make Point 1 2))user=> (send-to point :class-name)Pointuser=> (send-to point :class){:__own_symbol__Point, ....}}
Exercise 3: Examine the effect of a redefined class on existing instances. Let’s suppose you desire to redefine Point
so that it has an instance method that returns the origin:
(def Point{ :__instance_methods__ { :origin (fn [this] (make Point 0 0)) ....
However, your program has already created Point
instances. What happens? To find out, do this at the repl:
user=> (def point (make Point 1 2)user=> (def Point .... your new definition ...)user=> (send-to point :origin )????
Can you explain what happened?
Exercise 4: Some languages (or development environments) make it easy to define accessor (getter or setter) methods at the same time you define instance variables. Let’s do something like that. Change apply-message-to
so that if it finds there is no matching method, it looks to see if there’s a matching instance variable and (if so) returns its value. Here’s an example:
(def Holder{ :__own_symbol__ 'Holder :__instance_methods__ { :add-instance-values (fn [this held] (assoc this :held held)) } })user> (send-to (make Holder "stuff") :held)"stuff"
Hint: What is the value of (:not-there {:a 1, :b 2})
?
Hint: What are the values of the following expressions?
user=> (and true nil)user=> (and true false)user=> (or nil 3)
Exercise 5: Having implemented the previous exercise, what do you predict is the result of the following?
user=> (send-to (make Point 1 2) :some-unknown-message)
I think you’ll agree that’s not the best possible result. However, we’re not going to keep the previous exercise’s automatic accessors going forward, so it’s not worth fixing.
- Clojure and other Lisps let you define your own special forms with macros. It’s one of their greatest strengths. The Lisp message is: “Don’t like the syntax? Make up your own! (As long as it has lots of parentheses.)” If I were really embedding this OO language in Clojure, I’d use macros to let you write something closer to the class definitions other languages provide. But attractive class definitions is not the point of this book.↩
6. Inheritance (and Recursion)
Are you a person who likes to follow along in the repl while reading the book? If so, start by either using your solution from the last chapter or using mine:
user => (load-file "sources/class.clj")user => (load-file "solutions/class.clj")
When I show longer redefinitions that have only a few lines of changes, I’ll leave parts out. You can find the full redefinitions in sources/java.clj
. That’s the implementation we’re building in this chapter.
The source is also useful when copying-and-pasting from the book’s PDF isn’t working because of missing newlines.
Our Point
class has its own class
and class-name
methods. But those methods should work with any object. So now is a good time to implement inheritance.
But first…
6.1 Assertions
As we’ve been working along, we’ve been using maps as classes and symbols to refer to classes. As our class system got more complicated during the writing of this chapter and the optional ones in Part V, I found myself sometimes passing symbols to functions that expected maps and vice-versa.
That leads to two annoying results:
- Keywords as callables are excessively tolerant. If you pass a symbol to a function that expects a map, you’re likely to execute code like this:
user=> (:__instance_methods__ 'Point)nil
I would prefer getting an exception over getting a
nil
. As it is, thenil
result tends to propagate through the code for a while before something blows up. Coupled with Clojure’s less-than-optimal stack traces, that makes debugging the problem unnecessarily hard. - Maps are self-evaluating. Therefore, these two expressions produce the same class map:
user=> (eval 'Point)user=> (eval Point)
In some sense, that’s nice: you can write the wrong code—passing a map to a function that expects a symbol—and have it still work. What I’ve found, though, is that hampers later change when a function that has been working for two chapters suddenly fails in a mysterious way.
Therefore, starting in this chapter, I’ll be adding Clojure assertions to selected helper functions. That looks like this:
(def class-from-instance (fn [instance] ( assert (map? instance)) ;; <<== New(eval (:__class_symbol__ instance))))
I recommend you do the same.
I’ve been involved in the endless debate between statically type-checked languages (like Java or Haskell) and dynamically-typed languages (like Clojure or Ruby) for almost 30 years. I started out on the static side but have found myself on the dynamic side, although in a live-and-let-live, whatever-floats-your-boat kind of way. The unpleasantness in this chapter hasn’t changed my my mind, since it’s literally the first time I’ve felt the need to add asserts
to my Clojure code.
6.2 Method dispatch
We’ll start our implementation by adding a symbol to the Point
class that names its superclass:
(def Point{ :__own_symbol__ 'Point :__superclass_symbol__ 'Anything ;; <<= New :__instance_methods__ { ... }})
I’m calling the superclass Anything
because Clojure predefines Object
to refer to the Java class of the same name.
user=> Objectjava.lang.Object
Here is Anything
:
(def Anything{ :__own_symbol__ 'Anything :__instance_methods__ { ;; default constructor :add-instance-values identity
;; these two methods have been pulled up from Point. :class-name :__class_symbol__ :class (fn [this](class-from-instance this)) }})
Notice that I gave Anything
a default constructor. That way, classes that don’t need any initialization don’t have to define their own :add-instance-values
. Since the default constructor should do nothing by default—merely return the same map it was given—I defined it with Clojure’s identity
function, which does just that (for any kind of argument). Point
’s :__superclass_symbol__
is the key that message dispatch will work with. The way I usually think of message dispatch under inheritance is as walking up the inheritance hierarchy. That is, this message send:
user> (send-to (make Point 1 2) :class-name)
… should first look in Point
’s :__instance_methods__
map. When it fails to find :class-name
there, it should move up to Anything
and look there, where it will succeed.
Since that’s so familiar, let’s implement inheritance differently. Suppose we had a function, lineage
, that produces a list of class symbols, starting at Anything
and working down:
user=> (lineage 'Point)(Anything Point)
If we also had a function, class-instance-methods
, say, that could go from a class symbol to the :__instance_methods__
map, we could get a sequence of maps. In the following example, I’ll use pprint
(short for “pretty print”) to print the maps more readably:
user=> (def maps (map class-instance-methods (lineage 'Point)))user=> ( pprint maps )({ :add-instance-values # <user$fn...> , :class-name :__class_symbol__ , :class # <user$fn...> } { :add-instance-values # <user$fn...> , :shift # <user$fn...> , :add # <user$fn...> })nil
Now let’s merge those maps together:
user=> (def merged (apply merge maps))user=> (pprint merged){:add # <user$fn> , :shift # <user$fn> , :add-instance-values # <user$fn> , :class-name :__class_symbol__ , :class # <user$fn> }
We can apply methods from the merged map, which contains elements from both classes:
user=> ((:class-name merged) (make Point 1 2))Pointuser=> ((:shift merged) (make Point 1 2) 100 200){:y 202 , :x 101 , :__class_symbol__Point}
What if the subclass overrides a method in the superclass? Do we have the right version in our merged map? Yes, because merge
resolves key clashes by picking the value from the rightmost map. We can test that with :add-instance-values
. If Point
’s version is the one in the merged map, we should see an application of that function add :x
and :y
instance values to any map it receives as its this
argument. Do we?
user=> ((:add-instance-valuesmerged) {} 1 2){:y 2, :x 1}
We do.
What follows is the process we just worked through manually put into a named function. Although we’ve been working with class names (symbols) so far, I’m going to have the function take a class as its argument. That will save some typing later.
(def method-cache(fn [class](let [class-symbol (:__own_symbol__ class)method-maps (map class-instance-methods(lineage class-symbol))](apply merge method-maps))))
I picked the rather odd name method-cache
to give me an excuse to point out that this implementation isn’t completely silly. Suppose a Java class doesn’t define toString()
. The first time anyone sends the toString
message to any object of that class, the runtime has to walk up the inheritance hierarchy. But the next time the runtime needs to find toString
for that same class, it seems wasteful to walk the hierarchy again. Instead, it might cache the results in the class (or even in the object) to make method lookup faster. As long as caches get invalidated when superclasses change, the programmer could never notice the difference.
Such a cache would be a mapping from message names to functions, and it might look very much like the results of method-cache
.
Real OO systems do a lot of caching of this sort, though I’m sure Java’s is more sophisticated than what I’ve described.
In our case, we won’t really cache the results of the merge, because showing you how you’d do that in Clojure doesn’t fit the theme of this book.
To implement method-cache
, we need to implement two functions, class-instance-methods
and lineage
. Of the two, class-instance-methods
is the easiest, because it’s a use of eval
like we saw in the previous chapter:
(def class-instance-methods (fn [class-symbol] (:__instance_methods__(eval class-symbol))))
lineage
is trickier.
6.3 Recursion
To make the explanation of lineage
clearer, I’m going to pretend that we have a subclass of
Point
called RedPoint
. Here’s a picture of our class hierarchy:
I’m drawing the classes as clouds because there’s a lot of stuff in them that’s irrelevant to calculating RedPoint
’s lineage. I’m drawing crooked lines from subclass to superclass because we don’t have a direct pointer or link; instead we have to do the now-familiar eval
trickery to move from one to the other. However, that can all be handled within a function that we can treat like a direct link:
(def class-symbol-above(fn [class-symbol](:__superclass_symbol__ (eval class-symbol))))
We’d be happy if we could use sequence functions like map
to traverse those links, but we can’t: these classes aren’t contained within sequences. That means we fall back to the functional programming equivalent of loops: recursion. A recursive function is one that calls itself. A typical recursive function does five things:
- Breaks a big problem into an easy problem and a slightly-less-big problem.
- Solves the easy problem.
- Solves the slightly-less-big problem by applying itself (the recursive function) to it (the slightly-less-big problem).
- Notices when the big problem has become so tiny it’s now an easy problem.
- Combines the solutions to all the easy problems.
But there’s a fair amount of artfulness in how you apply those steps to any given problem.
It’s perfectly possible to use recursion in object-oriented languages, but lots of OO programmers don’t have much experience with it, so they view it as something strange and hard. If that describes you, I can’t entirely erase that impression—that takes more practice 1 than this book can give you—but I’ll try to help you make some significant steps toward seeing recursion as a comfortable tool.
A first example of recursion
Since most explanations of recursion are mathematical or textual, I’m going to explain it visually. lineage
begins with a symbol that refers to a class:
(lineage 'RedPoint)
That symbol identifies a point in a class hierarchy. Let’s juxtapose the symbol and the classes above it (including its own class):
If we apply class-symbol-above
to RedPoint
, we’ll get Point
, which corresponds to a shorter class-cloud list:
If we apply class-symbol-above
to Point
, we get a single-element list:
The Anything
class has no superclass. If you evaluate class-symbol-above
for a class with no superclass, you’ll get the result nil
. We can add that to our growing diagram:
One way to think of what we’ve done is that we’ve followed the class-symbol-above
links until we couldn’t any more. Another way is that we have a compound data structure (the list of clouds) that we’re making progressively smaller until we couldn’t any more—but at each step in the process, the smaller list retains the same “shape”, so that we know we can continue processing it in the same way. This “smaller but same shape” criterion is what recursion is about.
As we’ve drawn different levels of the diagram, the names along the left formed this sequence:
RedPoint Point Anything nil
How can we turn that into the return value we desire? Well, let’s consider the last two elements. If you cons
something onto nil
, you get a one-element list:
user=> (cons 'Anything nil)(Anything)
So if we keep “consing”, we’d get this:
user=> (cons 'RedPoint (cons 'Point (cons 'Anything nil))) (RedPoint Point Anything)
That’s the reverse of what we’re looking for. (We want the most specific class on the right.) The fix is easy:
user=> (reverse (cons 'RedPoint (cons 'Point (cons 'Anything nil))))(Anything Point RedPoint)
What we’ve done here is to descend (in the direction of smaller lists), finding names as we go, and then to ascend back up the lists, collecting what we’ve found. That’s a typical pattern in recursion:
That idiomatic pattern of computation has an idiomatic shape of function that produces it. I’ll show it now and explain it in detail in the next section:
(def recursive-function (fn [something ] (if (**ending-case?** something) something (cons something (recursive-function(**smaller-structure-from** something))))))
All we have to do is find the right functions to substitute for **ending-case?**
and **smaller-structure-from**
. For our problem, we end when we find a nil
, which the nil?
predicate can tell us. We get the smaller structure from class-symbol-above
.
(def recursive-function (fn [class-symbol](if ( nil? class-symbol)nil (cons class-symbol(recursive-function (class-symbol-above class-symbol))))))
Checking the function with the substitution rule
We can hand-execute this function by applying the substitution rule. Consider (recursive-function 'RedPoint)
. When the symbol argument is substituted into the body of the function, we get a result that I’ll represent like this:
(if (nil? 'RedPoint)nil(cons 'RedPoint (recursive-function (class-symbol-above 'RedPoint))))
if
heads a special form. It evaluates its first term. Then, depending on the result, it replaces itself with either the second or third terms. In this case, RedPoint
is a symbol, which is not nil?
. So the expansion of the if
is the expansion of the cons
list:
(cons 'RedPoint (recursive-function (class-symbol-above 'RedPoint)))
Applying class-symbol-above
, we get:
(cons 'RedPoint (recursive-function 'Point))
The same process happens with Point
as with RedPoint
, yielding this:
(cons 'RedPoint (cons 'Point 3 (recursive-function (class-symbol-above 'Point))))
… and then, from the call to class-symbol-above
:
(cons 'RedPoint (cons 'Point (recursive-function 'Anything )
… which expands to:
(cons 'RedPoint (cons 'Point (cons 'Anything (recursive-function (class-symbol-above 'Anything)))))
…and then:
(cons 'RedPoint (cons 'Point (cons 'Anything (recursive-function nil))))
…and then, expanding recursive-function
one last time:
(cons 'RedPoint (cons 'Point (cons 'Anything (if (nil? nil) nil (recursive-function (class-symbol-above nil))))))
In this case, nil
really is nil?
, so the expansion becomes:
(cons 'RedPoint (cons 'Point (cons 'Anything nil)))
… which builds the structure we want. Whew! Notice the shape of the expanded code echoes the shape of our levels of clouds:
That’s not a coincidence.
A second recursion pattern
The previous pattern builds up a pattern of computation that lies in wait until the bottommost function returns:
- “When the one below me returns, I’m going to
cons
on aRedPoint
.”- “When the one below me returns, I’m going to
cons
on aPoint
.”- “When the one below me returns, I’m going to
cons
on anAnything
.”- “I’m going to return
nil
. Watch what happens!”
- “I’m going to return
- “When the one below me returns, I’m going to
- “When the one below me returns, I’m going to
Another pattern of recursion is to use a collecting parameter in addition to the structure you’re working on. Instead of putting the final answer together as it ascends the levels, it passs a partial solution down the levels and has each level improve on it:
Nothing happens as you ascend the levels: the finished solution is just passed along.
Notice that (in this case) the solution is in the right order: we don’t have to reverse it.
Here’s the pattern for recursion of this type:
(def recursive-function (fn [something so-far] (if (**ending-case?** something) so-far (recursive-function (**smaller-structure-from** something) (cons something so-far)))))
For our particular use of this pattern, the **ending-case?**
can again be nil?
, and we again make the smaller structure by using class-symbol-above
. So we can calculate the lineage like this:
(def lineage-1 (fn [class-symbol so-far] (if (nil? class-symbol) so-far (lineage-1 (class-symbol-above class-symbol) (cons class-symbol so-far)))))
Notice that I named the function lineage-1
. That’s because our original lineage
only took one argument, and this pattern uses two. I just have the real lineage
call lineage-1
with an empty sequence:
(def lineage (fn [class-symbol] (lineage-1 class-symbol[])))
(As do many languages, Clojure has a way of providing default values for omitted arguments. It’s a bit awkward for the simple cases, so I’m not using it in this book.)
Tail recursion
Let’s look at lineage-1
again:
(def lineage-1 (fn [class-symbolso-far] (if (nil? class-symbol) so-far (lineage-1(class-symbol-aboveclass-symbol) (cons class-symbolso-far)))))
Suppose we had a class hierarchy with a million classes. That will mean a million and one calls to lineage-1
. At the moment of that last call, the first call will be waiting on the second, the second will be waiting on the third, the third… …and the millionth call will be waiting on the the million-and-first. Every one of those calls will be consuming memory while waiting.
And what will the millionth call do with the result of the million-and-first? Nothing. The recursive call is the last thing it does, so it just passes the result back to its caller, which just passes it back to its caller, and so on, all the way back to the original caller.
This pattern—where the last thing a recursive function does is call itself—is called tail recursion. Tail recursion is significant because a smart compiler can abandon the substitution rule and rewrite the function into a loop. Instead of making a new call to lineage-1
, it would just cons
the current class-symbol
onto the value of so-far
, change the value of class-symbol
to the result of class-symbol-above
, jump back to the beginning of the function, and redo it with the new values. You can’t change symbol-to-value bindings, but the compiler can.
Not only do loops not risk running out of memory, they run faster.
Many functional languages detect tail recursion and turn it into loops. Because of limitations of the Java Virtual Machine, Clojure can’t do that automatically. You have to tell it when you have tail recursion. That’s done like this:
(def lineage-1 (fn [class-symbolso-far] (if (nil? class-symbol) so-far ;VVVVV next line (recur(class-symbol-aboveclass-symbol) (cons class-symbolso-far)))))
The change is only one word: not a huge price to pay.
More general recursion patterns
Above, I showed you patterns with only two choices: the **ending-case?**
function and the **smaller-structure-from**
function. You’ll need more general patterns for the exercises, ones that offer two more choices. The first applies to both patterns, and lets you choose a **combiner**
function other than cons
.
The second could apply to both patterns, but I found it added complexity in the exercises for no gain, so we’ll only use it for the first pattern. It lets you pick an **ending-value**
other than nil
.
So here are our two patterns:
(def recursive-function (fn [something] (if (**ending-case?**something) (**ending-value**something) (**combiner**something (recursive-function (**smaller-structure-from**something))))))
(def recursive-function (fn [somethingso-far] (if (**ending-case?**something) so-far (recursive-function(**smaller-structure-from**something) (**combiner**somethingso-far)))))
Notice that I made the **ending-value**
in the first pattern a function applied to the ending “something”. That gives more flexibility than a constant. In some cases, you’ll use a constant instead of a function.
6.4 Exercises
My solutions are in solutions/recursion.clj
.
Exercise 1:
The factorial
function is a classic example of recursion. To recap: factorial of 0 is 1, factorial of 1 is 1, factorial 2 is 2*1, factorial of 3 is 3*2*1, factorial of 4 is 4*3*2*1 2.
Factorial can fit our first recursive pattern, where the sequence of descending numbers is the structure to make smaller.
Here’s that pattern. Write a factorial
that follows it:
(def factorial (fn [n] (if (**ending-case?**n) (**ending-value**n) (**combiner**n (recursive-function (**smaller-structure-from**n))))))
Hint: The zero case is an annoying detail. Don’t worry about it at first.
Hint: The combining function is multiplication.
Hint: You make the “structure” smaller by decrementing n
.
Hint: The **ending-case?** is when n
is either 0 or 1.
Hint: The ending-value doesn’t have to be a function. It is the constant value 1.
Exercise 2:
Here is the second pattern:
(def recursive-function (fn [somethingso-far] (if (**ending-case?**something) so-far (recursive-function(**smaller-structure-from**something) (**combiner**somethingso-far)))))
Implement factorial
using it.
Exercise 3:
Use the second pattern to make a recursive-function
that can add a sequence of numbers. Like this:
user=> (recursive-function [1 2 3 4] 0)10
Hint: Do you remember the empty?
function from the first chapter?
Hint: What function takes a sequence and produces the same sequence except without the first element?
Exercise 4:
Now change the previous exercise’s function so that it can multiply a list of numbers. Like this:
user=> (recursive-function [1 2 3 4] 1)24
(Note that the second argument changed to a 1
.)
What is the difference between the two functions? Extract that difference, and make it the first argument to recursive-function
.
Exercise 5:
Without changingrecursive-function
, choose starting values for the two wildcard parameters below that will cause it to convert a sequence of keywords into this rather silly map:
user> (recursive-function **combiner** [:a :b :c] **starting-so-far**) {:a 0, :b 0, :c 0}
Hint: I don’t think there’s any built-in Clojure function that you can pass in. You’ll have to write your own with fn
.
A bit trickier is producing a map that associates each keyword with its position in the list:
user> (recursive-function **combiner** [:a :b :c] **starting-so-far** ){ :a 0, :b 1, :c 2}
Hint: Try applying count
to a map.
Exercise 6:
Pat yourself on the back! You have both used and implemented the built-in function reduce
, perhaps the most dreaded of all sequence functions. reduce
has a different order of arguments, but it does the same thing:
user=> (reduce + 0 [ 1 2 3 4 ]) 10 user=> (reduce * 1 [ 1 2 3 4 ])24 user=> (reduce (fn [so-far val] (assoc so-far val 0)) {} [:a :b :c]){:c 0 , :b 0 , :a 0} user=> (reduce (fn [so-far val] (assoc so-far val (count so-far))){} [:a :b :c]){:c 2 , :b 1 , :a 0}
Note: when you’re down at the pub and you hear someone mention fold
, know that they’re talking about the same function as reduce
, but they’re either not a Clojure programmer or they are but want to show off to a Haskell programmer of the appropriate sex.
6.5 Finishing up
We’ve written a method, method-cache
, that provides a message-to-method map for all the messages that an instance can accept, taking inheritance into account. That’s not yet been hooked into either send-to
or make
, though. Let’s do that.
In the exercises for the last chapter, you created a method, apply-message-to
, that applies the method named by a message to an instance and an argument list. My solution looked like this:
(def apply-message-to (fn [class instance message args] (apply (method-from-message message class) instance args)))
We can replace the use of method-from-message
by looking up the message in the method-cache
.
(def apply-message-to (fn [class instancemessageargs] (apply (message(method-cacheclass));;<<== changed instanceargs)))
Note: message
will have a keyword substituted into it, so it is used to look up a method by key in the method-cache
map.
After that, send-to
and make
will work. Their code doesn’t have to be changed from the previous chapters.
user=> (send-to (makePoint 1 2) :class-name)Pointuser=> (send-to (makePoint12) :shift 3 4){:y6, :x4 , :__class_symbol__ Point}
6.6 Choose your own adventure
The object system we have now is small, certainly inefficient, but also reasonably close to Java’s (although it doesn’t have class methods or anything like the super
keyword to call shadowed methods). By working through the exercises, you’ve learned more Clojure and also programmed in a functional style: recursion, basing code on generic, widely-useful datatypes 3 (maps) rather than on custom classes, and a resolute treatment of functions as values that you can (for example) stick deep into a map to pull out later.
That prepares you for the next part of the book, which abandons objects to concentrate on the different idioms and habits of functional programming. If, however, you’d like to learn more about object systems, I suggest first taking a side trip to Part V, where you’ll extend this Java-like model to look like Ruby’s.
- The book I usually recommend for learning recursion is The Little Schemer by Daniel P. Friedman, Matthias Felleisen, Duane Bibby, and Gerald J. Sussman (though I have not read the later editions).↩
- I’m defining the
0
and1
cases of factorial independently. You could define the1
case in terms of the0
case, but keeping them separate works better for my purposes in a chapter 14 example.↩ - “It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures.”—Alan J. Perlis↩