# Introduction to Clojure¶

Clojure is a dynamically typed and compiled dialect of Lisp that runs on the Java Virtual Machine (JVM). In addition to its traditional support for lists and functional programming, Clojure has good built-in data structures other than lists (vectors, maps, sets), and agent-based concurrency. And because it is based on Java, you can easily access all the Java standard library functions within Clojure.

It has a big (for a Lisp!) community of users and it has been used for all kinds of applications, including interactive websites (e.g. Clojurescript).

We are going to use only a few of the traditional Lisp features of Clojure. But that’s enough to see why it such an interesting and influential language.

## Running Clojure¶

For this course we will mainly be using Clojure at the interactive command- line, and with a single file.

There are two common ways to launch the Clojure interpreter. One way is to call Clojure by name:

$clojure Clojure 1.4.0 =>  The other common way is to use the lein command, e.g.: $ lein repl


lein is Leiningen, a popular tool for managing Clojure projects. It’s probably the best way to use Clojure, so it’s worth the time to set it up and understand how it works.

To load a file named, say, primes.clj, into the interpreter use load- file:

=> (load-file "primes.clj")
#'user/prime?


Here, prime? is the name of the last function defined in primes.clj.

## The Clojure REPL: the Interactive Interpreter¶

We’ll mostly be using Clojure via its interpreter, or REPL. REPL stands for read-eval-print loop, and it lets us evaluate Clojure expressions one at a time. For instance:

=> (+ 3 2)
5
=> (* 10 4)
40
=> (- 5 8)
-3
=> (/ 1 2)    ;; dividing two ints returns a rational
1/2


Right away you can see that Clojure is a bit different than most languages. All functions in Clojure are called using prefix notation. This can seem strange, at first, especially for arithmetic. Most languages use infix notation for arithmetic expressions, e.g. 3 + 2, since that’s we learn in elementary school. However, when we evaluate functions, we normally use prefix notation, e.g. f(2, 3). Clojure — and Lisp in general — uses prefix notation for everything, which, once you get used to it, is simple and consistent.

The other interesting feature of Lisp notation is that expressions are always delineated by open and closed brackets. As you will see, Lisp programs can end up having a lot of brackets, and making sure they all match can be tricky.

Notice the final expression, (/ 1 2). In Clojure, this is a rational object, which stores both a numerator and denominator. If you want a floating- point number, you need to convert it, e.g.:

=> (double (/ 1 2))   ;; convert a rational to an int
0.5


You can pass multiple arguments to arithmetic operations:

=> (+ 1 2 3)     ;; you can pass any number of args to +
6
=> (* 1 6 2 2)
24
=> (/ 100 10 5)
2
=> (- 1 2 3)
-4


Or mix and match numbers and expressions in the usual way:

=> (+ (- 1 2 3) (* 4 5))
16


Even though we are using an interpreter here, Clojure is still a compiled language. Every Clojure expression gets compiled to Java bytecode.

## Numbers, Variables, Symbols, and Lists¶

While Clojure supports many different data types, we will restrict ourselves to three main kinds: numbers, symbols, and lists.

You can use the built-in number? function to test if an object is a number:

=> (number? 6)
true
=> (number? 1.8)
true
=> (number? 'two)
false


A Clojure variable can be defined using def:

=> (def pi 3.14)
#'user/pi
=> (* 2 pi)
6.28
=> (* pi pi pi)
30.959144000000002


Symbols are things like 'a or 'cat:

=> 'a
a
=> 'cat
cat


The single-quote, ', at the start of a symbol is important. It tells Clojure to treat what follows as a symbol, and not a variable. Forgetting the ' is usually an error:

=> cat
CompilerException java.lang.RuntimeException: Unable to resolve symbol: cat
in this context, compiling:(NO_SOURCE_PATH:0)


If you happen to also define a variable called cat, it is not the same as the symbol 'cat‘:

=> (def cat 5)
#'user/cat
=> (= cat 'cat)
false
=> (= cat cat)
true
=> (= 'cat 'cat)
true


The symbol? function tests if something is a symbol:

=> (symbol? 'a)
true
=> (symbol? 'cat)
true
=> (symbol? 5)
false
=> (symbol? symbol?)
false
=> (symbol? true)
false


Note

Symbols are not strings in Clojure. In Clojure, strings begin and end with double quotes, such as "cat" or "78". You can use the built-in string? function to test if an object is a string:

=> (string? "cat")
true
=> (string? 'cat)
false


A list is a sequence of one or more items, and internally is implemented as a singly-linked list. The items can be any Clojure object:

=> '(1 2 3)
(1 2 3)
=> '(my dog has fleas)
(my dog has fleas)
=> '(my (dog and hamster) have 10 fleas)
(my (dog and hamster) have 10 fleas)
=> ()
()


The last example is important: () is the empty list. It can also be written as '() in Clojure, e.g.:

=> (= () '())
true


When we use a list as data, we must put the single-quote in front of it. We call these quoted lists. Without the single-quote, Clojure treats the list as a function call:

=> (my dog has fleas)
CompilerException java.lang.RuntimeException: Unable to resolve symbol: my
in this context, compiling:(NO_SOURCE_PATH:148)


Here, Clojure tries to call a function named my with the arguments dog, has, and fleas. But there is no function named my, so an error results.

Consider these two examples:

=> (+ 1 2)
3
=> '(+ 1 2)
(+ 1 2)


The first expression is unquoted, and so Clojure evaluates it. The second expression is quoted, and so it does not get evaluated. Instead, it is just treated as a lump of data.

Usually, we use ' to quote things, but you can also use the quote function like this:

=> (quote hat)
hat
=> (quote (+ 1 2))
(+ 1 2)


Note

Quoted lists are similar in spirit to strings in other languages. For example, in Go, this statement prints 3:

fmt.Println(1 + 2)


But this statement prints "1 + 2":

fmt.Println(“1 + 2”)

The difference is that, on its own, 1 + 2 is expression that evaluates to 3. But put it inside quotes, then it’s just a string of 5 characters that are not evaluated.

Quoted lists are the same idea: the unquoted expression (+ 1 2) evaluates to 3, while the quoted expression '(+ 1 2) evaluates to the list (+ 1 2).

Use seq? to test if an object is a sequence (i.e. a list):

=> (seq? '(1 2 3))
true
=> (seq? '(1 two 3))
true
=> (seq? 'cat)
false
=> (seq? ())
true
=> (seq? '())
true
=> (seq? -3889)
false
=> (seq? seq?)
false


Lists are not the only kind of sequence in Clojure, but we won’t be discussing non-list sequences very much, if at all, in this course.

## List Processing¶

Clojure provides numerous functions for processing lists. Two of the most important are first and rest:

=> (first '(once upon a time))
once
=> (rest '(once upon a time))
(upon a time)

=> (first (rest '(once upon a time)))  ;; second element of a list
upon
=> (rest (rest '(once upon a time)))
(a time)

=> (first ())
nil
=> (rest ())
()


Another fundamental list function is cons — it pushes an element onto the front of a list, and returns a new list:

=> (cons 'cat '(dog bird fish))
(cat dog bird fish)
=> (cons 1 '(dog 2 fish))
(1 dog 2 fish)
=> (cons 'a ())
(a)
=> (cons 'b (cons 'a ()))
(b a)
=> (cons 'c (cons 'b (cons 'a ())))
(c b a)


The last few examples show that you can think of a list as a series of nested calls to cons. As we will see, this is sometimes a very useful way to think about lists.

The list function takes any number of inputs and creates a list from them:

=> (list 'a 'b)
(a b)
=> (list 9 3 2 1)
(9 3 2 1)
=> (list 'a (first '(b c)))
(a b)
=> (list)
()


Finally, empty? tests if a list is empty:

=> (empty? ())
true
=> (empty? '())
true
=> (empty? nil)
true
=> (empty? '(1 3 5))
false
=> (empty? 4)
IllegalArgumentException Don't know how to create ISeq from:
java.lang.Long  clojure.lang.RT.seqFrom (RT.java:494)


There are many other list functions, but from just these basic ones we can write a surprisingly large amount of useful code.

## Functions¶

Functions are the heart of Lisp, and there are a number of ways to create them. One way is to use defn:

(defn add1 [n]
(+ 1 n)
)


This defines a function named add1 that takes a single value, n, as input. It returns the value of (+ 1 n):

=> (add1 5)
6
22


Notice that we have not explicitly specified the type of n. Clojure is dynamically typed: it doesn’t check the type of n until run-time.

In a Clojure function, the sequence of arguments is a vector, not a list. That’s why we write [n] instead of (n). We will mostly ignore Clojure vectors in this course, except when they are required for defining functions.

Here’s another function:

(defn circle-area [radius]
)

=> (circle-area 5)
78.5
78.5


Clojure already has a pre-defined function called second that returns the second element of a list. But if it didn’t we could define it like this:

(defn second [seq]      ;; Clojure already defines this function
(first (rest seq))
)


And another:

(defn third [seq]
(first (rest (rest seq)))
)

=> (third '(the cat in the hat))
in


Here’s a boolean function that returns true if all its three inputs are different, and false otherwise:

(defn all-diff? [x y z]
(and (not= x y) (not= x z) (not= y z))
)


It’s a common convention to put ? on the end of the name of a function that returns a boolean value.

In the following function, p1 and p2 are assumed to both be of the form (x y):

(defn add-points [p1 p2]
(list (+ (first p1) (first p2))
(+ (second p1) (second p2))
)
)

=> (add-points '(1 2) '(4 2))
(5 4)


A problem with add-points is that it will probably crash if either p1 or p2 are the wrong format. So it’s useful to write a function that tests if an object is a valid point:

(defn is-point? [p]
(and (seq? p)
(empty? (rest (rest p)))  ;; Does p have exactly 2 elements?
(number? (first p))
(number? (second p))
)
)


and uses short-circuit evaluation: it evaluates the expressions passed to it in left-to-right order, and if one of the expressions evaluates to false, then it does not evaluate any of the remaining expressions. The is-point? function relies on that behavior.

## Decisions with cond¶

Clojure has a number of different kinds of if-statements tailored for different situations, but for simplicity we will only use one of them: cond. Consider this function:

(defn sign [n]
(cond
(< n 0) 'negative
(= n 0) 'zero
:else   'positive
)
)

=> (sign 5)
positive
=> (sign -5)
negative
=> (sign 0)
zero


A cond expression consists of a number of test value pairs. For example, (< n 0) is a test, and 'negative is it’s corresponding pair.

cond evaluates the pairs one at a time in the order given. If a test evaluates to true, its corresponding value is returned, and none of the rest of the tests are checked. The final test in this example is :else, which always evaluates to true if it is reached.

## The Length of a List¶

You can calculate the length of a list using built-in function count:

=> (count '(a b 2 h))
4


It’s instructive to write our own version of this function. We’ll call it length:

;; Returns the length of seq.
(defn length [seq]
(cond
(empty? seq) 0                   ;; base case
:else (+ 1 (length (rest seq)))  ;; recursive case
)
)


This is a recursive function. The base case is the empty list: it has length zero. The length of a non-empty list is one plus the length of the rest of the list.

Here’s another good example of recursion:

;; Returns true if x is in seq, false otherwise.
(defn member [x seq]
(cond
(empty? seq) false           ;; base case 1
(= x (first seq)) true       ;; base case 2
:else (member x (rest seq))  ;; recursive case
)
)


Recall that the symbol? functions tests if an object is a symbol (such as 'cat). The following function returns the number of symbols in a list:

(defn count-sym [seq]
(cond
(empty? seq) 0
(symbol? (first seq)) (+ 1 (count-sym (rest seq)))
:else (count-sym (rest seq))
)
)

=> (count-sym '(a b c 1 2 d))
4


Now suppose we want a function that uses number? to count how many numbers are in a list:

;; Returns the number of occurrences of x in seq.
(defn count-num [seq]
(cond
(empty? seq) 0
(number? (first seq)) (+ 1 (count-num (rest seq)))
:else (count-num (rest seq))
)
)

=> (count-num '(a b c 1 2 d))
2


If you compare count-sym and count-num you’ll see that they are nearly identical. The only differences are the names of the functions in the recursive calls, and the use of number? instead of symbol?.

So what we can do is write a general-purpose counting function that takes a list and a predicate function (i.e. a function that takes one value as input and returns a boolean value as output) as input:

(defn count-fn [fn? seq]
(cond
(empty? seq) 0
(fn? (first seq)) (+ 1 (count-fn fn? (rest seq)))
:else (count-fn fn? (rest seq))
))


To use it we pass in any function that takes a single input value and returns either true or false:

=> (count-fn symbol? '(a b c 1 2 d))
4
=> (count-fn number? '(a b c 1 2 d))
2
=> (count-fn even? '(1 2 3 4 5 6))
3
=> (count-fn odd? '(1 2 3 4 5 6))
3


## Lambda Functions¶

We’ve seen how to define functions using defn, and now we want to study another way. Consider this expression:

=> (count-fn (fn [x] (> x 0)) '(1 2 3 4 5 6))
6


The expression (fn [x] (> x 0)) defines a function that takes a single value, x, as input, and returns true if, and only if, x is bigger than 0. What’s interesting about this function is that it has no name. Functions defined in this way are called anonymous functions, or a lambda functions. In theory, lambda functions can be used as the basis for all computation (the lambda calculus). In practice, they are often a quick and easy way to write small functions for use in functions like count-fn.

Here’s another example where lambda functions are useful. The keep-if function returns a list containing all the elements of a given list that match a given test function:

(defn keep-if [fn? seq]
(cond
(empty? seq) ()
(fn? (first seq)) (cons (first seq)
(keep-if fn? (rest seq)))
:else (keep-if fn? (rest seq))
)
)

=> (keep-if even? '(1 2 3 4 5))
(2 4)
=> (keep-if (fn [x] (or (= x 1) (even? x))) '(1 2 3 4 5))
(1 2 4)


Here’s an expression that partitions a list of numbers so that all the evens come before all the odds:

=> (concat (keep-if even? '(1 2 3 4 5)) (keep-if odd? '(1 2 3 4 5)))
(2 4 1 3 5)


The concat functions appends two (or more) lists together to form a single list. We can write this as a function:

(defn parity-partition [seq]
(concat (keep-if even? seq) (keep-if odd? seq))
)

=> (parity-partition '(1 2 3 4 5 6 7 8 9 10))
(2 4 6 8 10 1 3 5 7 9)


Note that Clojure has a built-in function called filter that does the same thing as keep-if.

Another useful function is called map: it applies a function to each element of a list. Clojure already has the map function built in, but lets write our own version called mymap:

(defn mymap [fn seq]
(cond
(empty? seq) '()
:else (cons (fn (first seq)) (mymap fn (rest seq)))
)
)

=> (mymap (fn [x] (+ 1 x)) '(1 2 3))  ;; add 1 to each element
(2 3 4)
=> (mymap list '(1 2 3))              ;; make each element a list
((1) (2) (3))


The member function given earlier can be generalized to test if a sequence has element that matches a passed-in function named pred?:

(defn member-if [pred? seq]
(cond
(empty? seq) false
(pred? (first seq)) true
:else (member-if pred? (rest seq))
)
)


Using member-if, we could define the original member function like this:

(defn member [x seq]
(member-if (fn [e] (= e x)) seq))


## Folding a List¶

Consider the following function for summing a list of numbers:

(defn sum [seq]
(cond
(empty? seq) 0                         ;; base case
:else (+ (first seq) (sum (rest seq))) ;; recursive case
)
)

=> (sum '(1 4 2))
7


Compare it to this function that calculates the product of a list of numbers:

(defn prod [seq]
(cond
(empty? seq) 1                           ;; base case
:else (* (first seq) (prod (rest seq)))  ;; recursive case
)
)


The general pattern is the same for both functions. But there are a couple of differences. First, notice that sum returns 0 for an empty list, while prod returns 1. Second, in the recursive case, sum use + and prod uses * (plus the names of the recursive calls are different).

Now lets write a general-purpose function that implements this pattern, requiring the base case value and function to be passed in as parameters:

(defn fold [fn empty-val seq]
(cond
(empty? seq) empty-val
:else (fn (first seq) (fold fn empty-val (rest seq)))
)
)


This is just a generalized version of sum and prod. Now we can rewrite those functions like this:

(defn sum [seq] (fold + 0 seq))

(defn prod [seq] (fold * 1 seq))


In Clojure, the built-in function reduce does essentially the same thing as fold.

An interesting way to think about fold is to see what it does to a list when it is expanded into nested calls to cons. For example, we can write the list (1 4 2) in the form (cons 1 (cons 4 (cons 2 ()))). When you call fold on it, it as if each cons is replaced by fn, and the empty list is replaced by empty-val. For example:

  (fold + 0 '(1 4 2))
= (fold + 0 (cons 1 (cons 4 (cons 2 ()))))
= (+ 1 (+ 4 (+ 2 0))
= 7


And:

  (fold * 1 '(1 4 2))
= (fold * 1 (cons 1 (cons 4 (cons 2 ()))))
= (* 1 (* 4 (* 2 1))
= 8


With this trick in mind, it is easy to see that (fold cons () seq) returns seq itself.

It is also worth noting that the order in which fold evaluates its list is from right to left, i.e. the first things that get evaluated are the last element of seq and empty-val. Thus, this version of fold is sometimes called a right fold (sometimes abbreviated foldr).

For functions like + and * the order of evaluation doesn’t matter much, but it might for other functions. So another way to fold a list is from left to right (a left fold):

(defn fold-left [fn z seq]
(cond
(empty? seq) z
:else (fold-left fn (fn z (first seq)) (rest seq))
)
)


Here’s a trace:

  (fold-left + 0                   '(1 4 2))
= (fold-left + (+ 0 1)             '(4 2))
= (fold-left + (+ (+ 0 1) 4))      '(2))
= (fold-left + (+ (+ (+ 0 1) 4) 2) '())
= (+ (+ (+ 0 1) 4) 2)
= 7


An advantage of fold-left over our (right) fold is that the final function call of fold-left is a recursive call to fold-left itself. This is an instance of tail recursion, and it is important because some compilers can automatically convert it to a loop, thus avoiding the use of the call stack. In contrast, the last function called in our fold function is fn, and so it must use the stack to do its recursive calls because there is no general-purpose way to replace its recursive calls with a loop that avoids using a linear amount of memory. Thus fold can run out of memory on large lists that fold-left can handle without a problem.

Note

Unfortunately, Clojure does not eliminate tail-recursion automatically. This is due to the nature of the underlying Java virtual machine. So, instead, Clojure provides a function called recur for eliminating tail recursion. We will not use recur in this course.

## Let¶

An important and useful feature of Clojure is the let environment. Using let, you can bind values to variables. For example:

(defn operator [e]
(let [op (first e)]
(cond
(= op '-) 'subtraction
(= op '*) 'multiplication
(= op '/) 'division
:else 'unknown
)
)
)

=> (operator '(+ 1 2))
=> (operator '(* 1 2))
multiplication


We assign the first element of the list e to op so that we don’t have to keep re-calculating it. Once a symbol is assigned in a let, it cannot be changed.

Here’s another example that evaluates expressions of the form (left op right):

(defn eval-basic [e]
(let [left (first e)
op (second e)    ;; second is a built-in function
right (third e)  ;; third is defined by the programmer
]
(cond
(= op '+) (+ left right)
(= op '-) (- left right)
(= op '*) (* left right)
(= op '/) (/ left right)
:else 'error
)
)
)

=> (eval-basic '(5 * 6))
30
=> (eval-basic '(5 - 6))
-1
=> (eval-basic '(3 + 2))
5


Another example where let is useful is when writing the deepmap function. deepmap is a variation on map that works essentially the same way as map, except the passed-in mapping function is applied to every non-sequence value on the list, even if those values are nested inside lists. The list structure is preserved. For example:

=> (defn sqr [x] (* x x))
#'user/sqr

=> (deepmap sqr '(1 3 (3 (4) 5) 6))
(1 9 (9 (16) 25) 36)


Here’s a definition for deepmap:

(defn deepmap [fn seq]
(cond
(empty? seq) ()
:else
body (rest seq)
new_body (deepmap fn body)
]
(cond
:else
)
)
)
)


## An Expression Evaluator¶

The eval-basic function given in the previous section only evaluates expressions of the form (num op num), where num represents a number. But it is not much more complicated to evaluate any arithmetic expression of the form (expr op expr):

(defn my-eval [e]
(cond
(number? e) e   ;; base case
:else
(let [left (my-eval (first e))
op (second e)
right (my-eval (third e))
]
(cond
(= '+ op) (+ left right)
(= '* op) (* left right)
(= '- op) (- left right)
(= '/ op) (float (/ left right))
))))  ;; closing brackets put on one line to save space

=> (my-eval '((8 * 5) + 2))
42


This is a recursive function: the expressions assigned to left and right both call my-eval recursively.

## A Propositional Expression Evaluator¶

Lets write another evaluator, this time for infix propositional expressions like (t and (not f)). We will assume that t and f stand for true and false respectively, and that there no variables allowed in the expressions.

First, lets define a few helper functions:

(defn third [seq] (first (rest (rest seq))))

(defn member [x seq]
(cond
(empty? seq) false
(= x (first seq)) true
:else (member x (rest seq))
))


Now we define a series of functions that test if an object has a particular form:

;; 't and 'f are the only literals
(defn literal? [e] (or (= e 'f) (= e 't)))

;; (not expr)
(defn is-not? [e] (and (list? e) (= 2 (count e)) (= 'not (first e))))

;; (expr and expr)
(defn is-and? [e] (and (list? e) (= 3 (count e)) (= 'and (second e))))

;; (expr or expr)
(defn is-or? [e] (and (list? e) (= 3 (count e)) (= 'or (second e))))

;; (expr nand expr)
(defn is-nand? [e] (and (list? e) (= 3 (count e)) (= 'nand (second e))))

;; (expr op expr)
(defn is-binop? [e] (or (is-not? e) (is-and? e) (is-or? e) (is-nand? e)))


These are all non-recursive functions that check that the top-level form of an expressions is correct. They don’t go into the sub-expressions.

Next, lets write a function that tests if an expression is valid:

(defn is-expr? [e]
(cond
(literal? e)
true
(is-not? e)
(is-expr? (second e))
(is-and? e)
(and (is-expr? (first e)) (is-expr? (third e)))
(is-or? e)
(and (is-expr? (first e)) (is-expr? (third e)))
(is-nand? e)
(and (is-expr? (first e)) (is-expr? (third e)))
:else
false
))


The idea of this function is to first check that e has a valid top-level form, and to then recursively check that the sub-expressions are also valid.

All that (is-expr? e) does is test whether or not e is a valid expression. To actually evaluate e, we need to write an evaluator:

;; helper functions that converts true to 't and false to 'f
(defn tf [b]
(cond
(= true b) 't
:else 'f
)
)

(defn eval-prop [e]
(cond
(literal? e)
e
(is-not? e)  ;; (not expr)
(tf (not (eval-prop (second e))))
(is-and? e)  ;; (expr and expr)
(tf (and (eval-prop (first e)) (eval-prop (third e))))
(is-or? e)  ;; (expr or expr)
(tf (or (eval-prop (first e)) (eval-prop (third e))))
:else
'f
)
)


For example:

user=> (eval-prop '((not t) and (t or (not f))))
f


eval-prop is similar in structure to is-expr?, but instead of returning true or false, it returns the value of the expression.

Another interesting thing we might want to do with a propositional expression is to simplify it. For example, any propositional expression of the form (not (not p)) can be simplified to p. Lets write a simplifier that applies this rule to expressions:

;; double negation elimination
;; (not (not expr)) ==> expr
(defn simplify [e]
(cond
(literal? e)
e
(and (is-not? e) (is-not? (second e)))
(simplify (second (second e)))
(is-not? e)  ;; (not expr)
(list 'not (simplify (second e)))
(is-and? e)  ;; (expr and expr)
(list (simplify (first e)) 'and (simplify (third e)))
(is-or? e)   ;; (expr or expr)
(list (simplify (first e)) 'or (simplify (third e)))
:else        ;; error if you get here
nil
)
)


simplify first checks if e is of the form (not (not X)). If so, then it extracts the X (using (second (second e))) and returns the simplification of it. Otherwise, it tries to simplify the parts of the sub- expressions (if any) of e.

For example:

user=> (simplify '((not (not (t and (not (not f))))) or ((not (not f)) or f)))
((t and f) or (f or f))


## Rewriting an Expression with Only nand¶

An interesting fact about propositional logic is that any expression can be re-written using just the nand operator. The expression (p nand q) is true just when either p, or q, or both, are false. In other words, (p nand q) is equivalent to (not (p and q)).

Here are the basic rules for writing propositional expressions using just and:

• (not p) is logically equivalent to (p nand p)
• (p and q) is logically equivalent to ((p nand q) nand (p nand q))
• (p or q) is logically equivalent to ((p nand p) nand (q nand q))

These three rules are enough to transform any propositional expression into a logically equivalent one that uses nand as the only connective.

Here’s some code that does the transformation:

;; any symbol is a literal
(defn literal? [e] (symbol? e))

(defn make-nand [p q]
(list p 'nand q)
)

;; Rewrites propositional logic expression e to a logically equivalent
;; expression that uses "nand" as the only connective.
(defn nand-rewrite [e]
(cond
(literal? e)
e
(is-not? e)
(let [p (second e)
np (nand-rewrite p)
]
(make-nand np np)
)
(is-and? e)
(let [p (nand-rewrite (first e))
q (nand-rewrite (third e))
pnq (make-nand p q)
]
(make-nand pnq pnq)
)
(is-or? e)
(let [p (nand-rewrite (first e))
q (nand-rewrite (third e))
pnp (make-nand p p)
qnq (make-nand q q)
]
(make-nand pnp qnq)
)
)
)

=> (nand-rewrite '(not (a or b)))
(((a nand a) nand (b nand b)) nand ((a nand a) nand (b nand b)))

=> (nand-rewrite '(not ((a or (not b)) or (not b))))
(((((a nand a) nand ((b nand b) nand (b nand b))) nand ((a nand a) nand ((b nand b) nand (b nand b)))) nand ((b nand b) nand (b nand b))) nand ((((a nand a) nand ((b nand b) nand (b nand b))) nand ((a nand a) nand ((b nand b) nand (b nand b)))) nand ((b nand b) nand (b nand b))))

=> (pp)
(((((a nand a) nand ((b nand b) nand (b nand b)))
nand
((a nand a) nand ((b nand b) nand (b nand b))))
nand
((b nand b) nand (b nand b)))
nand
((((a nand a) nand ((b nand b) nand (b nand b)))
nand
((a nand a) nand ((b nand b) nand (b nand b))))
nand
((b nand b) nand (b nand b))))
nil


Note the use of (pp): it pretty-prints the last expression evaluated by the interpreter. It can sometimes make long expressions easier to read, although it’s not hugely helpful in this particular case.

Language-processing code, like the kind in the last couple of examples, often uses recursion in an easy and natural way. Non-recursive versions of these functions would be much harder to write and understand. Thus, Lisp is often a good language for experimenting with new programming language ideas, especially if they can be implemented in an interpreter.

## Example: Binary Search Trees¶

Here’s a toy implementation of a binary search tree that shows some more Clojure functions.

;;; bst.clj

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; An implementation of a binary search tree (BST). Nodes are lists of the
;; form (value left-tree right-tree).
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; the empty tree is nil
(defn is-empty? [tree] (= tree nil))

;; getters
(defn value [node] (first node))
(defn left [node] (second node))
(defn right [node] (last node))

;; return the depth of a tree
(defn depth [tree]
(cond
(is-empty? tree) 0
:else (+ 1 (max (depth (left tree)) (depth (right tree))))
))

;; return the max value in a tree
(defn tree-max [tree]
(cond
(is-empty? tree)         nil  ;; oops: an empty tree has no max value
(is-empty? (right tree)) (value tree)
:else                    (tree-max (right tree))
))

;; return a list of the values of tree in "inorder" order, i.e. for
;; a BST the list of values will be in ascending sorted order
(defn list-inorder [tree]
(cond
(is-empty? tree) ()
:else (concat (list-inorder (left tree))
(list (value tree))
(list-inorder (right tree))
)))

;; test if x is a value in tree
(defn contains [tree x]
(cond
(is-empty? tree)   false
(= x (value tree)) true
(< x (value tree)) (contains (left tree) x)
:else              (contains (right tree) x)
))

;; insert value x into tree t
(defn insert [tree x]
(let [V (value tree)
L (left tree)
R (right tree)
]
(cond
(is-empty? tree)   (list x nil nil)
(= x V) tree  ;; x already in the tree, so nothing to do
(< x V) (list V (insert L x) R)
:else   (list V L (insert R x))
)))

; ;; a more verbose implementation of insert
; (defn insert [tree x]
;     (cond
;         (is-empty? tree)   (list x nil nil)
;         (= x (value tree)) tree  ;; x already in the tree, so nothing to do
;         (< x (value tree)) (list (value tree)
;                                  (insert (left tree) x)
;                                  (right tree))
;         :else              (list (value tree)
;                                  (left tree)
;                                  (insert (right tree) x))
; ))

;; convert a list of things into a tree
(defn make-tree [lst]
(cond
(empty? lst) nil
:else        (insert (make-tree (rest lst)) (first lst))
))

;; sort lst by reading its elements into a tree, and then converting the
;; tree back to a list using an inorder traversal
(defn treesort [lst] (list-inorder (make-tree lst)))

;; sample tree
(def t (make-tree '(4 8 19 5 1 3 6 9 7 2 11)))

;=> t
;(11 (2 (1 nil nil) (7 (6 (3 nil (5 (4 nil nil) nil)) nil) (9 (8 nil nil)
;nil))) (19 nil nil))