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