# 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
=> (add1 21)
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]
(* 3.14 radius radius)
)
=> (circle-area 5)
78.5
=> (circle-area (add1 4))
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.

## 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 '+) 'addition
(= op '-) 'subtraction
(= op '*) 'multiplication
(= op '/) 'division
:else 'unknown
)
)
)
=> (operator '(+ 1 2))
addition
=> (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
(let [head (first seq)
body (rest seq)
new_body (deepmap fn body)
]
(cond
(seq? head)
(cons (deepmap fn head) new_body)
:else
(cons (fn head) new_body)
)
)
)
)
```

## 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))
```