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:

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:

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:

The most important thing you need to know now is how to get out of the repl. That’s done like this:

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:

1.3 The Read-Eval-Print Loop

Here’s a use of the repl:

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:

Let’s try something more exciting:

*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:

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:

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:

1. It recursively evaluates each of the list elements.
   • The symbol + evaluates to the function that adds.
   • As before, numbers evaluate to themselves.
2. 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:

(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:

There are other predicates that let you ask questions about what kind of value a value is:

You can ask the number? question of a function:

If you want to know if a value is a function, you use fn?:

It’s important to understand that functions aren’t special. Consider these two expressions:

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:

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:

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 ¹, 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:

Once a function is made, it can be used. How? By putting it in the first position of a list:

(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:

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?

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:

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:

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:

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.

Once named, a user-defined function can be used as conveniently as a built-in function:

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:

You can use def with a particular symbol more than once. That’s the only exception to Clojure’s “no changing a binding” rule ². It’s useful for correcting mistakes:

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:

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:

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:

You can take apart lists. Here’s a way to get the first element:

Here’s a way to get everything after the first element:

You can pick out an element at a particular (zero-based) position in a list:

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:

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:

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:

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.

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:

The first time I typed something like that, I expected the result to be the vector

, and the parentheses confused me. The result of

is a lazyseq, which prints the same way as a list. Here’s how you can tell the difference:

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:

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.

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:

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:

The second is a vector of two symbols (which happen to name functions):

At first, you’re likely to be confused about when you need to quote. Basically, if you see an error like this:

… it probably means you forgot a quote.

Quoting doesn’t only apply to entire lists and vectors. You can quote symbols:

You can also quote individual elements of vectors:

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:

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:

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:

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:

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:

That is, we want to somehow turn that vector into the same value as this + expression:

(Notice that + can take any number of arguments.)

The following is almost what we want, but not quite:

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:

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:

Let’s look at this in steps.

1. cons (the name chosen more than 50 years ago as an abbreviation for the verb “construct”) produces a list ³ whose first element is cons ’s first argument and whose rest is cons ’s second argument:

   user=> (cons "the first element"[1 2 3]) ("the first element" 1 2 3)

   (Notice that cons, like rest earlier, takes a vector in but doesn’t produce one.)

2. eval is our old friend the bird-like evaluator. In my-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:

After that, it is evaluated “from the inside out”, each result being substituted into an enclosing expression, finally yielding 6. ⁴

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:

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:

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:

The map function can take more than one sequence argument. Consider this:

That is equivalent to this:

1.18 More exercises

Exercise 3: Implement add-squares.

Exercise 4: The range function produces a sequence of numbers:

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:

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:

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 and drop-last
• flatten
• partition only the [n coll] case, like: (partition 2 [1 2 3 4])
• every?
• remove and create the function argument with fn

Other functions

• (= a b) – Equality
• (count sequence) – Length
• and, or, not – Boolean functions
• (cons elt sequence) – Make a new sequence with the elt on the front
• inc, 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 sequence
• print, println, prn – Print things. print and println 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 and prn 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.

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:

Exercise 7: Implement this function: (tails sequence): Returns a sequence of successively smaller subsequences of the argument.

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?

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:

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?

Why does that happen?

Hint: Use the substitution rule for functions.

1. 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.↩
2. 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 of Var in the Clojure documentation or any other book on Clojure.↩
3. Strictly, cons produces a lazyseq, not a list, but the evaluator treats them the same. ↩
4. The substitution as printed isn’t quite true. After it receives (my-apply + ...) from the reader, the evaluator processes the symbols function and + to find function values. Therefore, in the expansion of my-apply, the function parameter is substituted with an argument that’s a function value. And so the list given to eval 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:

1. Creating a barely believable object that’s nothing but instance variables, a rudimentary constructor, and a vestigial class.
2. Embedding methods within the constructor, making it look a bit like a class definition.
3. Define methods in the class rather than in the constructor.
4. 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:

In Python, the equivalent method would be written like this:

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:

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:

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:

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:

• 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:

It’s not unusual to apply hash-map to a sequence, like this:

That allows something like keyword arguments:

To retrieve a value from a map, you can use get:

If you try to fetch the value of a key that’s not in the map, you get 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:

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:

do-something-to-map can legitimately be given either a true function or a keyword:

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 ¹.

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:

You can use assoc to add multiple key-value pairs:

You can also merge two or more maps:

You can exclude key-value pairs from a map with dissoc:

Question: How do assoc and merge handle duplicate keys? Try it and see!

3.2 I present to you an object

Let’s make a constructor for a Point class. Here’s a minimal version:

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:

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:

However, since keywords are callables, we could define x more simply:

or even just this:

3.3 The class begins as documentation

The result of (Point 1 2) prints like this:

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:

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:

(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.

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:

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:

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:

However, Clojure reserves new for the creation of Java objects, so we’ll use make instead:

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:

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:

It’s easier than you probably think!

Exercise 4: Change equal-triangles so that it can compare more than two triangles:

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:

However, that approach is prone to typos ². You can use one of the sequence functions you explored in the previous chapter to do a more concise job.

1. 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).↩
2. I once found a bug in a fairly complicated Unix kernel function. It had three “inode” parameters: i, ii, and iii. 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:

• 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:

And applying one is not exactly graceful:

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:

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:

That given, the definition of send-to is this:

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:

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:

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:

1. 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: {}

2. 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)

3. 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 or merge. To (slightly) emphasize that, I won’t call the method initialize. Instead, the user-supplied function will be called add-instance-values.

Before implementing make, let’s add add-instance-values to the class:

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:

We could do this:

But that’s not exactly graceful or readable. So Clojure provides an alternate way to name sub-computations. It’s called let:

Notice that let expressions return a value. So you can nest them inside other expressions:

You can create more than one name with a let:

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:

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:

The allocated step was easy. Earlier, I said we could use code like this for seeded:

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:

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 ¹.

So the “seeded” instance will be created with this:

In order to create the finished instance, we have to find and apply a particular method, namely

. Finding the method looks like this:

Let’s use let to name that constructor:

Once we have the constructor, we need only apply it to the half-finished (“seeded”) constructor and whatever arguments the user gave:

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:

5.3 Message dispatch

We now need to make calls like this work:

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:

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:

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:

So that finishes send-to:

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:

It would be better to write this:

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:

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:

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:

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:

However, your program has already created Point instances. What happens? To find out, do this at the repl:

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:

Hint: What is the value of (:not-there {:a 1, :b 2})?

Hint: What are the values of the following expressions?

Exercise 5: Having implemented the previous exercise, what do you predict is the result of the following?

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.

1. 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:

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:

1. 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, the nil 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.

2. 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:

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:

I’m calling the superclass Anything because Clojure predefines Object to refer to the Java class of the same name.

Here is Anything:

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:

… 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:

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:

Now let’s merge those maps together:

We can apply methods from the merged map, which contains elements from both classes:

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?

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.

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:

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:

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:

1. Breaks a big problem into an easy problem and a slightly-less-big problem.
2. Solves the easy problem.
3. Solves the slightly-less-big problem by applying itself (the recursive function) to it (the slightly-less-big problem).
4. Notices when the big problem has become so tiny it’s now an easy problem.
5. 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 ¹ 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:

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:

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:

So if we keep “consing”, we’d get this:

That’s the reverse of what we’re looking for. (We want the most specific class on the right.) The fix is easy:

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:

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.

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 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:

Applying class-symbol-above, we get:

The same process happens with Point as with RedPoint, yielding this:

… and then, from the call to class-symbol-above:

… which expands to:

…and then:

…and then, expanding recursive-function one last time:

In this case, nil really is nil?, so the expansion becomes:

… 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 a RedPoint.”
  • “When the one below me returns, I’m going to cons on a Point.”
    • “When the one below me returns, I’m going to cons on an Anything.”
      • “I’m going to return nil. Watch what happens!”

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:

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:

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:

(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:

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:

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:

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 ².

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:

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:

Implement factorial using it.

Exercise 3:

Use the second pattern to make a recursive-function that can add a sequence of numbers. Like this:

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:

(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:

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:

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:

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:

We can replace the use of method-from-message by looking up the message in the method-cache.

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.

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 ³ (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.

1. 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).↩
2. I’m defining the 0 and 1 cases of factorial independently. You could define the 1 case in terms of the 0 case, but keeping them separate works better for my purposes in a chapter 14 example.↩
3. “It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures.”—Alan J. Perlis↩