Introduction to Scheme¶
Scheme is a popular dialect of Lisp, a language developed in the 1950s and 1960s by John McCarthy and his students. Lisp is based on the lambda calculus, a mathematical formalism for defining and executing functions.
Despite being so simple and not quite having achieved mainstream success on its own, Lisp has proven to be an extremely flexible and powerful language, and has been the source of ideas found in many other languages.
Getting Scheme¶
These notes will be using MIT Scheme, a popular version of Scheme that is easy to use.
To install MIT Scheme on Ubuntu Linux, run this command in a shell:
$ sudo apt-get install mit-scheme
For other systems, see the MIT Scheme home page.
Running Scheme¶
Once it’s installed, you can run it at the command-line like this:
$ mit-scheme
MIT/GNU Scheme running under GNU/Linux
Type `^C' (control-C) followed by `H' to obtain information about interrupts.
Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Image saved on Tuesday October 22, 2013 at 12:31:09 PM
Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/i386 4.118
Edwin 3.116
1 ]=>
]=> is the interpreter prompt, and means that it is waiting for you to
type something. So try this:
1 ]=> (* 2 3 5)
;Value: 30
1 ]=>
The Scheme expression (* 2 3 5) calculates the product of 2, 3, and 5,
i.e. \(2 \cdot 3 \cdot 5 = 30\).
While it is possible to compile Scheme, we will stick to just the interpreter for this course.
Quitting Scheme¶
To exit the interpreter, type ctrl-d:
1 ]=>
Kill Scheme (y or n)? Yes
Moriturus te saluto.
Or by typing (exit) and return:
1 ]=> (exit)
Kill Scheme (y or n)? Yes
Moriturus te saluto.
Note
The ending message “Moriturus te saluto.” is Latin for “I who am about to die salute you.”
Loading Files¶
We’ll usually be putting Scheme functions in text files and then loading that
text file into the interpreter. For example, suppose the file circle.scm
contains this:
;;; (circle-perim r) calculates perimeter of a circle of radius r
(define circle-perim
(lambda (radius)
(* 2 3.14 radius)
)
)
Then in Scheme we can load and run it like this:
1 ]=> (load "circle.scm")
1 ]=> (circle-perim 2)
;Value: 12.56
1 ]=>
Using Scheme in an Editor¶
While you can use MIT-Scheme directly at the command-line, it lacks many basic editing features and so is a very unpleasant experience. Most programmers prefer to run it directly in their text editor.
For example, if you are using Sublime Text as your editor, then you can install the SublimeREPL package, which lets you run an interpreter in a Sublime window.
Another popular editor for Lisp-like languages is Emacs, which comes already to run Scheme in an editor window.
Using Scheme’s Interactive Interpreter¶
We’ll mostly be using Scheme via its interpreter, or REPL. REPL stands for read-eval-print loop, and it lets us evaluate Scheme expressions one at a time. For instance:
1 ]=> (+ 3 2)
;Value: 5
1 ]=> (* 10 4)
;Value: 40
1 ]=> (- 5 8)
;Value: -3
1 ]=> (/ 5 2)
;Value: 5/2
1 ]=> (/ 6 2)
;Value: 3
1 ]=> (/ 5 2)
;Value: 5/2 ;; 5/2 is a rational value
Right away you can see that Scheme is a bit different than most languages.
All functions in Scheme 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). Scheme uses prefix notation for everything,
which, once you get used to it, is simple and consistent.
The other interesting feature of Scheme notation is that expressions are
always delineated by open ( and closed ) brackets. As you will see,
Scheme programs can end up having a lot of brackets, and making sure they
all match can be tricky.
You can pass multiple arguments to arithmetic operations:
=> (+ 1 2 3)
6
=> (* 1 6 2 2)
24
=> (/ 100 10 5)
2
=> (- 1 2 3)
-4
Or combine numbers and expressions:
=> (+ (- 1 2 3) (* 4 5))
16
Notice that Scheme supports a rational numeric type, which is not common in mainstream languages:
1 ]=> (+ 1/2 1/2)
;Value: 1
1 ]=> (+ 1/2 1/2 1/2)
;Value: 3/2
Number Basics¶
Lets look at the basic types of values in Scheme.
The standard Scheme functions integer?, rational?, real?,
complex?, and number? can be used to test for various kinds of
numbers. For example:
;;
;; integers
;;
1 ]=> (integer? 5)
;Value: #t
1 ]=> (integer? 6.0)
;Value: #t
1 ]=> (integer? 6.1)
;Value: #f
;;
;; rationals
;;
1 ]=> (rational? 6/3)
;Value: #t
1 ]=> (rational? 6)
;Value: #t
1 ]=> (rational? 6.1)
;Value: #t
;;
;; reals
;;
1 ]=> (real? 2)
;Value: #t
1 ]=> (real? 2.1)
;Value: #t
1 ]=> (real? 6/17)
;Value: #t
;;
;; complex
;;
1 ]=> (complex? 3.1+4i)
;Value: #t
1 ]=> (complex? 3.1+0i)
;Value: #t
1 ]=> (complex? 6)
;Value: #t
The value #t means true, and #f means false. The number? function
can be used to test if a value is any kind of number at all.
Here are a few handy built-in numerical functions: zero?, positive?,
negative?, odd?, even?. For example:
1 ]=> (zero? (- 5 5))
;Value: #t
1 ]=> (positive? (- 5 5))
;Value: #f
1 ]=> (positive? 22)
;Value: #t
1 ]=> (negative? 0)
;Value: #f
1 ]=> (negative? -3)
;Value: #t
1 ]=> (odd? 101)
;Value: #t
1 ]=> (even? 2038)
;Value: #t
There’s also min and max:
1 ]=> (min 8 3 -2 9 1 0)
;Value: -2
1 ]=> (max 8 3 -2 9 1 0)
;Value: 9
See the MIT Scheme documentation for a list of the other mathematical functions.
Symbol Basics¶
Symbol are a kind of value that is not found in many other mainstream
languages. Use symbol? to test if a value is a symbol:
1 ]=> (symbol? 'a)
;Value: #t
1 ]=> (symbol? 'apple)
;Value: #t
1 ]=> (symbol? 'first-ever-airplane)
;Value: #t
1 ]=> (symbol? 4)
;Value: #f
1 ]=> (symbol? odd?)
;Value: #f
1 ]=> (symbol? x)
;Unbound variable: x
While they may look like strings, they are not. Symbols are just values with names, and we don’t usually care about their individual characters. Like other Scheme names, symbol names cannot contain certain characters (such as spaces).
Note the ' in front of all the valid symbols. Quoting is an important part
of Scheme, and it is necessary to distinguish a symbol from a variable. For
example, x is a variable, while 'x' is a symbol:
1 ]=> (symbol? 'x)
;Value: #t
1 ]=> (symbol? x)
;Unbound variable: x
The expression (symbol? x) does not evaluate because Scheme does not know
about the variable x.
Like numbers, symbols evaluate to themselves:
1 ]=> 'a
;Value: a
1 ]=> 'cat
;Value: cat
This contrasts with variables, which evaluate to the value they’re bound to.
define is one way to create new variables:
1 ]=> (define pi 3.14)
;Value: pi
1 ]=> pi
;Value: 3.14
1 ]=> (* 2 pi)
;Value: 6.28
Here, pi is a variable bound to the value 3.14. Thus, pi evaluates to
3.14, and can be used anywhere a number is needed.
Notice also that the variable pi does not have a type. This is a key
feature of Scheme: it is a weakly typed language, meaning that the type of
most expressions is not known until the expression is evaluated (in contrast
to more strongly typed languages where types are often known at compile-time).
pi is not a symbol, it’s a variable:
1 ]=> (symbol? pi) ;; pi is a variable
;Value: #f
1 ]=> (symbol? 'pi) ;; 'pi is a symbol
;Value: #t
Basics of Lists¶
A list is a sequence of 0, or more, values. The values an in a list can be any Scheme value: numbers, symbols, other lists, etc.
As with symbols, literal lists usually begin with a ':
1 ]=> '(1 2 3)
;Value 13: (1 2 3)
1 ]=> '(my dog has fleas)
;Value 14: (my dog has fleas)
1 ]=> '(my dog (and hamster) have 10 fleas each))
;Value 15: (my dog (and hamster) have 10 fleas each)
The empty list is a list with 0 values in it, and is written as either ()
or '(). Use null? to test if a list is empty:
1 ]=> (null? '(1 2))
;Value: #f
1 ]=> (null? '())
;Value: #t
If you try to evaluate a list with the ' at the start, you will sometimes
get an error:
1 ]=> (my dog has fleas)
;Unbound variable: fleas
By default, Scheme treats the first element of a list as a function, and the
remaining elements as inputs to that function. Since my is not bound to a
function (or anything at all!), Scheme reports an error.
Compare it to this example:
1 ]=> (min 3 1)
;Value: 1
(min 3 1) is an unquoted list, so Scheme assumes it is a function call.
It replaces the variable min with the function it is bound to, and then
passes 3 and 1 to it as parameters.
If you put a ' in front of this list, then it evaluates to itself:
1 ]=> '(min 3 1)
;Value 16: (min 3 1)
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 an 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).
Scheme lists are essentially singly-linked lists, and so that has a big impact on their performance characteristics.
List Processing¶
Scheme has a number of useful built-in list processing functions. When thinking about the performance characteristics of these functions, keep in mind that Scheme lists are essentially singly-linked lists.
The car function returns the first element of a list:
1 ]=> (car '(1 2 3))
;Value: 1
1 ]=> (car '((1 2) 3 4))
;Value 18: (1 2)
1 ]=> (car '(my dog has fleas))
;Value: my
1 ]=> (car '())
;The object (), passed as the first argument to car, is not the correct type.
The empty list has no first element, so (car '()) is an error.
The cdr function returns everything on a list except for the first
element:
1 ]=> (cdr '(1 2 3))
;Value 19: (2 3)
1 ]=> (cdr '((1 2) 3 4))
;Value 20: (3 4)
1 ]=> (cdr '(my dog has fleas))
;Value 21: (dog has fleas)
1 ]=> (cdr '())
;The object (), passed as the first argument to cdr, is not the correct type.
Note
The names car and cdr are traditional, and refer to the
underlying hardware of the original computer on which Lisp was first
implemented.
Some languages use the name first instead of car, and rest
instead of cdr.
The cons function returns a new list by adding a new element to the start
of the list:
1 ]=> (cons 1 '(2 3))
;Value 22: (1 2 3)
1 ]=> (cons '(2 3) '(3 4))
;Value 23: ((2 3) 3 4)
1 ]=> (cons 'my '(dog has fleas))
;Value 24: (my dog has fleas)
1 ]=> (cons 'x '())
;Value 25: (x)
car, cdr, and cons work well together, e.g.:
1 ]=> (cons (car '(1 2 3)) (cdr '(1 2 3)))
;Value 26: (1 2 3)
It’s sometimes useful to think of a list as a nested series of calls to
cons. For example, the list '(a b c d) could be written like this:
1 ]=> (cons 'a (cons 'b (cons 'c (cons 'd '()))))
;Value 27: (a b c d)
Recall that because Scheme implements lists as singly-linked lists, then
car, cdr, and cons all run very quickly, no matter the size of the
list: they all run in worst-case \(O(1)\) time.
Another convenient way to create a list is to use the list function:
1 ]=> (list 1 2 3)
;Value 28: (1 2 3)
1 ]=> (list '(1 2) 3 4)
;Value 29: ((1 2) 3 4)
1 ]=> (list 'my 'dog 'has 'fleas)
;Value 30: (my dog has fleas)
1 ]=> (list)
;Value: ()
These functions can be combined to many different useful things. For example,
the car of a lists cdr is its second element:
1 ]=> (car (cdr '(a b c d)))
;Value: b
Be aware that Scheme expressions are quite general, so you can even do things like this:
1 ]=> ((car (list min max)) 41 2 3)
;Value: 2
To evaluate this entire expression, (car (list min max)) is evaluated.
First, the sub-expression (list min max) evaluates to (list <min-fn>
<max-fn>), i.e. the variables min and max are replaced by the
functions they’re bound to. Then (list <min-fn> <max-fn>) evaluates to the
list (<min-fn> <max-fn>). So (car (list min max)) then becomes (car
(<min-fn> <max-fn)), which is just <min-fn>.
Functions¶
Functions are the heart of Lisp, and there are a number of ways to create
them. One way is to use defn:
(define add1
(lambda (n)
(+ n 1)
)
)
This defines a function named add1 that takes a single value, n, as
input. It returns the value of (+ 1 n):
1 ]=> (add1 5)
;Value: 6
1 ]=> (add1 (add1 (add1 3)))
;Value: 6
Notice the type of n is not specified. Scheme is dynamically typed:
it doesn’t check the type of n until run-time.
Here’s another function:
(define circle-area
(lambda (radius)
(* 3.14 radius radius)
)
)
1 ]=> (circle-area 3)
;Value: 28.259999999999998
1 ]=> (circle-area (add1 4))
;Value: 78.5
In the following function, p1 and p2 are assumed to both be of the
form (x y):
(define add-points
(lambda (p1 p2)
(list (+ (first p1) (first p2))
(+ (second p1) (second p2))
)
)
)
1 ]=> (add-points '(2 1) '(5 9))
;Value 11: (7 10)
Logical Expressions¶
You can use and, or, and not to evaluate logical expressions in
Scheme. For example:
(define all-diff?
(lambda (x y z)
(and (not (equal? x y))
(not (equal? x z))
(not (equal? y z))
)
)
)
1 ]=> (all-diff? 1 2 1)
;Value: #f
1 ]=> (all-diff? 1 2 -5)
;Value: #t
and is what is known in Scheme as a special form. It is different
than an ordinary function because it does not immediately evaluate the
expressions passed to it. Instead, and evaluates the expression one at a
time from left to right, and stops immediately after the first expression that
evaluates to false; none of the expressions after this are evaluated.
or is also a special form, e.g.:
(define any-same?
(lambda (x y z)
(or (equal? x y)
(equal? x z)
(equal? y z)
)
)
)
1 ]=> (any-same? 3 5 3)
;Value: #t
1 ]=> (any-same? 3 5 13)
;Value: #f
Similar to and, the or special form evaluates its inputs one at a
time, from left to right, stopping after finding the first true expression
(and not evaluating anything after that).
not works as expected, i.e. it flips true to false and false to true:
(define any-same2?
(lambda (x y z)
(not (all-diff? x y z))
)
)
Decisions with cond¶
cond is a special form in Scheme that it is similar to if-else structures
in other languages. Consider this function:
(define sign
(lambda (n)
(cond ((< n 0) 'negative)
((= n 0) 'zero)
(#t 'positive)
)
)
)
1 ]=> (sign -4)
;Value: negative
1 ]=> (sign 0)
;Value: zero
1 ]=> (sign 5)
;Value: positive
A cond expression consists of a number of 2-element (test value)
lists. For example, (< n 0) is a test, and 'negative is it’s
corresponding value.
cond evaluates its pairs one at a time in left to right order. If a test
evaluates to true, its corresponding value is returned, and the which always
evaluates to true, and so its corresponding value is always returned if
it’s reach. It serves the same purpose as an else clause in an if-else
statement.
Instead of #t in the final test, you can also use else:
(define sign
(lambda (n)
(cond ((< n 0) 'negative)
((= n 0) 'zero)
(else 'positive)
)
)
)
Recursive Functions¶
If you want to determine the length of a list, Scheme provides a built-in
length function:
1 ]=> (length '(1 (2 3) 4))
;Value: 3
We could also write our own function using recursion like this:
(define len
(lambda (lst)
(cond
((null? lst) 0) ;; base case
(#t (+ 1 (len (cdr lst)))) ;; recursive case
)
)
)
len has two cases:
- base case: when the list
lstis empty - recursive case: calculate the length of the
cdroflst, then add 1
As you can see, you must take care to get all the parentheses to match!
Here’s another good example of recursion:
;; Returns true if x is in lst, and false otherwise.
(define member
(lambda (x lst)
(cond
((null? lst) #f)
((equal? x (car lst)) #t)
(#t (member x (cdr lst)))
)
)
)
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:
(define count-sym
(lambda (lst)
(cond
((null? lst) 0)
((symbol? (car lst)) (+ 1 (count-sym (cdr lst))))
(#t (count-sym (cdr lst)))
)
)
)
If instead we want to count how many numbers are in a list, a small
modification to count-sym is all that’s needed:
(define count-num
(lambda (lst)
(cond
((null? lst) 0)
((number? (car lst)) (+ 1 (count-num (cdr lst))))
(#t (count-num (cdr lst)))
)
)
)
Compared to count-sym, count-num is the same except for two
differences: number? is used instead of symbol?, and each occurrence
of count-sym has been changed to count-num.
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 input:
(define count-fn
(lambda (fn? lst)
(cond
((null? lst) 0)
((fn? (car lst)) (+ 1 (count-fn fn? (cdr lst))))
(#t (count-fn fn? (cdr lst)))
)
)
)
To use it we pass in any function that takes a single input value and returns
either true or false:
1 ]=> (count-fn even? '(1 2 3 4 5 6 7))
;Value: 3
1 ]=> (count-fn odd? '(1 2 3 4 5 6 7))
;Value: 4
1 ]=> (count-fn number? '(1 2 3 4 5 6 7))
;Value: 7
1 ]=> (count-fn symbol? '(1 2 3 4 5 6 7))
;Value: 0
Using count-fn, it is easy to re-write the previous functions like this:
(define count-symbol (lambda (lst) (count-fn symbol? lst)))
(define count-number (lambda (lst) (count-fn number? lst)))
More Examples¶
;;
;; Remove all top-level occurrences of x from lst.
;;
(define remove-all
(lambda (x lst)
(cond
((null? lst)
'())
((equal? x (car lst))
(remove-all x (cdr lst)))
(else
(cons (car lst) (remove-all x (cdr lst))))
)
)
)
;;
;; Replace all top-level occurrences of 'clinton with 'trump.
;;
(define trumpify
(lambda (lst)
(cond
((null? lst)
'())
((equal? 'clinton (car lst))
(cons 'trump (trumpify (cdr lst))))
(else
(cons (car lst) (trumpify (cdr lst))))
)
)
)
;;
;; Replace all top-level occurrences of old with new.
;;
(define replace
(lambda (old new lst)
(cond
((null? lst)
'())
((equal? old (car lst))
(cons new (replace old new (cdr lst))))
(else
(cons (car lst) (replace old new (cdr lst))))
)
)
)
;;
;; Returns a function that, when called, replaces all occurrences of old
;; with new on a given list.
;;
(define make-replacer
(lambda (old new)
(lambda (lst) (replace old new lst))
)
)
;;
;; Returns the number of numbers on lst, even numbers inside of lists.
;;
(define deep-count-num
(lambda (lst)
(cond
((null? lst)
0)
((list? (car lst))
(+ (deep-count-num (car lst)) (deep-count-num (cdr lst))))
((number? (car lst))
(+ 1 (deep-count-num (cdr lst))))
(else
(deep-count-num (cdr lst)))
)
)
)
Lambda Functions¶
In Scheme, a lambda function is essentially a function without a name. We’ve been using lambda functions to define named functions, so you should be somewhat familiar with them.
Here’s a lambda function that adds 1 to its input:
(lambda (n) (+ n 1))
This function takes one input which it names n, and returns the value of
n + 1. Notice that the function has no name! So to call it, you must do
something like this:
((lambda (n) (+ n 1)) 5)
This passes 5 to the lambda function, and so the entire expression evaluates to 6.
Lambda functions are often a convenient way to write small functions. For example, suppose we want to count how many times 2 or 5 occurs in a list. Then we could do it like this:
(count-fn (lambda (n) (or (= n 2) (= n 5)))
'(2 2 6 5 7 5 2 1)
)
Once you get the hang of them, using lambda functions in this way is often very convenient.
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:
(define keep-if
(lambda (pred? lst)
(cond
((null? lst)
'())
((pred? (car lst))
(cons (car lst) (keep-if pred? (cdr lst))))
(else
(keep-if pred? (cdr lst)))
)
)
)
1 ]=> (keep-if even? '(1 2 3 4 5))
;Value 13: (2 4)
1 ]=> (keep-if (lambda (n) (or (= n 1) (even? n))) '(1 2 3 4 5))
;Value 14: (1 2 4)
Here’s an expression that partitions a list of numbers so that all the evens come before all the odds:
1 ]=> (append (keep-if even? '(1 2 3 4 5)) (keep-if odd? '(1 2 3 4 5)))
;Value 18: (2 4 1 3 5)
The append function appends two (or more) lists together to form a single
list.
We can write this as a function:
(define parity-partition
(lambda (nums)
(append (keep-if even? nums) (keep-if odd? nums))
)
)
1 ]=> (parity-partition '(1 2 3 4 5))
;Value 21: (2 4 1 3 5)
Note that Scheme 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. Scheme already has a map function built in, but lets
write our own version called mymap:
(define mymap
(lambda (f lst)
(cond
((null? lst)
'())
(else
(cons (f (car lst)) (mymap f (cdr lst))))
)
)
)
1 ]=> (mymap (lambda (n) (* n n)) '(1 2 3))
;Value 23: (1 4 9)
1 ]=> (mymap list '(1 2 3))
;Value 24: ((1) (2) (3))
Notice that the function, f, that is passed into mymap takes one item
as input. The idea is that f is applied to every element of the list, e.g.
(mymap f (a b c d)) returns ((f a) (f b) (f c) (f d)). Thus, it is
similar to a loop in other languages.
Folding a List¶
Consider the following function for summing a list of numbers:
(define sum-list
(lambda (nums)
(cond
((null? nums)
0)
(else
(+ (car nums) (sum-list (cdr nums))))
)
)
)
1 ]=> (sum-list '(1 4 2))
;Value: 7
Compare it to this function that calculates the product of a list of numbers:
(define prod-list
(lambda (nums)
(cond
((null? nums)
1)
(else
(* (car nums) (prod-list (cdr nums))))
)
)
)
1 ]=> (prod-list '(1 4 2))
;Value: 8
sum-list and prod-list are very similar. There are three main
differences. First, notice that sum-list returns 0 for an empty list,
while prod-list returns 1. Second, in the recursive case, sum-list use
+ and prod-list uses *. Finally, the names of the recursive calls
are different.
Now lets write a general-purpose function that implements this pattern, taking the base case value and function to be passed in as parameters:
(define my-fold
(lambda (f empty-val lst)
(cond
((null? lst)
empty-val)
(else
(f (car lst) (my-fold f empty-val (cdr lst))))
)
)
)
1 ]=> (my-fold + 0 '(1 2 4))
;Value: 7
1 ]=> (my-fold * 1 '(1 2 4))
;Value: 8
In Scheme, there are a number of built-in functions similar to my-fold,
such as reduce-left, reduce-right, fold-left, and fold-right.
Each of these functions implements a variation of the same essential pattern
as my-fold.
An interesting way to think about my-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 my-fold on it, it as if each cons is replaced by f, and the
empty list is replaced by empty-val. For example:
(my-fold + 0 '(1 4 2))
= (my-fold + 0 (cons 1 (cons 4 (cons 2 ()))))
= (+ 1 (+ 4 (+ 2 0))
= 7
And:
(my-fold * 1 '(1 4 2))
= (my-fold * 1 (cons 1 (cons 4 (cons 2 ()))))
= (* 1 (* 4 (* 2 1))
= 8
With this trick in mind, it is easy to see, for instance, that (my-fold cons
() lst) returns lst itself.
It is also worth noting that the order in which my-fold evaluates its list
is from right to left, i.e. the first things that get evaluated are the last
element of lst and empty-val. Thus, this version of my-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):
(define my-fold-left
(lambda (f z lst)
(cond
((null? lst)
z)
(else
(my-fold-left f (f z (car lst)) (cdr lst)))
)
)
)
Here’s a trace:
(my-fold-left + 0 '(1 4 2))
= (my-fold-left + (+ 0 1) '(4 2))
= (my-fold-left + (+ (+ 0 1) 4)) '(2))
= (my-fold-left + (+ (+ (+ 0 1) 4) 2) '())
= (+ (+ (+ 0 1) 4) 2)
= 7
An advantage of my-fold-left over my-fold (i.e. a right fold) is that
the final function call of my-fold-left is a recursive call to my-fold-
left itself. This is an instance of tail recursion, and it is important
because Scheme automatically converts such recursion to a loop, thus avoiding
the use of the call stack. In contrast, the last function called in my-
fold function is to f, and so it must use the stack because there is no
general-purpose way to replace its recursive calls with a loop that avoids
using a linear amount of memory. Thus my-fold can run out of memory on
large lists that my-fold-left can handle without a problem.
Let¶
An important and useful feature of Scheme is the let environment. Using
let, you can bind values to variables. For example:
(define operator
(lambda (e)
(let ((op (car e))
)
(cond
((equal? op '+) 'addition)
((equal? op '-) 'subtraction)
((equal? op '*) 'multiplication)
((equal? op '/) 'division)
(else 'unknown)
)
)
)
)
1 ]=> (operator '(+ 1 2 3))
;Value: addition
1 ]=> (operator '(/ 1 2 3))
;Value: division
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 numeric expressions of the form (left
op right):
(define eval-basic
(lambda (e)
(let ((left (car e))
(op (car (cdr e)))
(right (car (cdr (cdr e))))
)
(cond
((equal? op '+) (+ left right))
((equal? op '-) (- left right))
((equal? op '*) (* left right))
((equal? op '/) (/ left right))
(else 'err)
)
)
)
)
1 ]=> (eval-basic '(1 + 2))
;Value: 3
1 ]=> (eval-basic '(1 - 2))
;Value: -1
Another example where a let-environment is in the deepmap function.
deepmap is a variation on map that works like map, except the
passed-in mapping function is applied to every non-list value on the list,
even those nested inside lists. For example:
1 ]=> (deepmap 1+ '(1 (2 (1 1)) 3))
;Value 31: (2 (3 (2 2)) 4)
Here’s a definition for deepmap:
(define deepmap
(lambda (f lst)
(cond
((null? lst)
())
(else
(let* ((head (car lst))
(body (cdr lst))
(new_body (deepmap f body))
)
(cond
((list? head)
(cons (deepmap f head) new_body))
(else
(cons (f head) new_body))
)
)
)
)
)
)
Notice that this uses let* instead of let. That’s because binding for
new_body uses body, which is defined in the same let-environment. If
we had used a regular let, then we’d get an error saying body is
unbound. let* is designed specifically to allow already-bound variables to
be used.
An Expression Evaluator¶
The eval-basic function given in the previous section only evaluates
expressions of the form (num op num), where num is a number. But it is
not much more work to evaluate any arithmetic expression of the form (expr
op expr):
(define my-eval
(lambda (e)
(cond
((number? e)
e)
(else
(let ((left (my-eval (car e)))
(op (car (cdr e)))
(right (my-eval (car (cdr (cdr e)))))
)
(cond
((equal? op '+) (+ left right))
((equal? op '-) (- left right))
((equal? op '*) (* left right))
((equal? op '/) (/ left right))
)))))) ;; closing brackets all on one live to save space
1 ]=> (my-eval '(2 * (2 + 3)))
;Value: 10
1 ]=> (my-eval '((10 - 5) / (2 * (2 + 3))))
;Value: 1/2
This is a recursive function: the expressions assigned to left and
right both call my-eval recursively.
The expression (car (cdr e)) returns the second element of e. A short-
hand way to write this is (cadr e); notice how the a and the d of
cadr mirror the order of those letters in car and cdr. Similarly,
the expression (car (cdr (cdr e))) can be re-written as (caddr e).
A Propositional Expression Evaluator¶
Lets write another evaluator, this time for infix propositional expressions
like (t and (not f)). We will assume that the symbols t and f
stand for true and false respectively, and that there no variables allowed in
the expressions.
First, we define a series of functions that test if an object has a particular form:
(define is-literal?
(lambda (e)
(or (equal? e 't) (equal? e 'f))
)
)
;; returns true iff lst is a list of length n
(define nlist
(lambda (n lst)
(and (list? lst)
(= n (length lst))
)
)
)
;; (not expr)
(define is-not?
(lambda (e)
(and (nlist 2 e)
(equal? 'not (car e))
)
)
)
;; (and expr)
(define is-and?
(lambda (e)
(and (nlist 3 e)
(equal? 'and (cadr e))
)
)
)
;; (or expr)
(define is-or?
(lambda (e)
(and (nlist 3 e)
(equal? 'or (cadr 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 a valid proposition:
;; Returns true iff e is a valid propositional expression.
(define is-expr?
(lambda (e)
(cond
((is-literal? e)
#t)
((is-not? e)
(is-expr? (cadr e)))
((is-and? e)
(and (is-expr? (car e)) (is-expr? (third e))))
((is-or? e)
(and (is-expr? (car e)) (is-expr? (third e))))
((is-nand? e)
(and (is-expr? (car e)) (is-expr? (third e))))
(else
#f)
)
)
)
The idea of this function is to first check that e has a valid top-level
form, and to then recursively check that its sub-expressions are also valid.
Next, lets write an evaluator that calculates whether the value of a valid proposition:
(define eval-prop-bool
(lambda (e)
(cond
((is-literal? e)
(equal? e 't))
((is-not? e) ;; (not expr)
(not (eval-prop-bool (second e))))
((is-and? e) ;; (expr and expr)
(and (eval-prop-bool (first e)) (eval-prop-bool (third e))))
((is-or? e) ;; (expr or expr)
(or (eval-prop-bool (first e)) (eval-prop-bool (third e))))
(else
#f)
)
)
)
(define eval-prop
(lambda (e)
(if (eval-prop-bool e) 't 'f)
)
)
For example:
1 ]=> (eval-prop '((not t) and (t or (not f))))
;Value: f
Simplifying a Propositional Expression¶
Something else we can 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
(define simplify
(lambda (e)
(cond
((is-literal? e)
e)
;; (not (not e))
((and (is-not? e) (is-not? (second e)))
(simplify (second (second e))))
((is-not? e)
(list 'not (simplify (second e))))
((is-and? e)
(list (simplify (first e)) 'and (simplify (third e))))
((is-or? e)
(list (simplify (first e)) 'or (simplify (third e))))
(else
'error)
)
)
)
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:
1 ]=> (simplify '((not (not t)) and (not (not t))))
;Value 34: (t and t)
Rewriting an Expression with Only nand¶
An basic 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 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 rules are enough to transform any propositional expression into a
logically equivalent one using only nand.
Here’s some code that does the transformation:
(define is-prop-literal?
(lambda (x)
(symbol? x)
)
)
(define make-nand
(lambda (p q)
(list p 'nand q)
)
)
;; Rewrites propositional logic expression e to a logically equivalent
;; expression that uses "nand" as the only connective.
(define nand-rewrite
(lambda (e)
(cond
((is-prop-literal? e)
e)
((is-not? e)
(let ((np (nand-rewrite (second e)))
)
(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)))
)
)
)
1 ]=> (pp (nand-rewrite '((p and q) or ((not p) or q))))
((((p nand q) nand (p nand q)) nand ((p nand q) nand (p nand q)))
nand
((((p nand p) nand (p nand p)) nand (q nand q))
nand
(((p nand p) nand (p nand p)) nand (q nand q))))
Note the use of the pp function: it “pretty prints” a Scheme expression,
making it is easier for humans to read.
Lisp is often a good choice for writing language-processing code as in the last couple of examples. 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 ideas, especially if they can be implemented in an interpreter.
Example: Binary Search Trees¶
The following is a sample Scheme implementation of a basic binary search tree’s.
;;; bst.scm
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; An implementation of a binary search tree (BST). Nodes are lists of the
;; form (value left-tree right-tree).
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; '() is the empty tree
(define is-empty? (lambda (t) (null? t)))
;; getters
(define value (lambda (node) (first node)))
(define left (lambda (node) (second node)))
(define right (lambda (node) (third node)))
;; insert value x into tree t
(define insert
(lambda (x t)
(if (is-empty? t)
(list x '() '())
(let ((V (value t))
(L (left t))
(R (right t))
)
(cond
((is-empty? t)
(list x '() '()))
((= x V) ;; x already in the tree, so do nothing
t)
((< x V)
(list V (insert x L) R))
(else
(list V L (insert x R)))
)
)
)
)
)
;; convert a list of things into a tree
(define make-tree
(lambda (lst)
(if (null? lst)
'()
(insert (car lst) (make-tree (cdr lst))))))
;; 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
(define list-inorder
(lambda (t)
(cond
((is-empty? t) '())
(else (append (list-inorder (left t))
(list (value t))
(list-inorder (right t))))
)
)
)
(define treesort
(lambda (lst)
(list-inorder (make-tree lst))
)
)
;; Returns the depth of a tree
(define depth
(lambda (t)
(cond
((is-empty? t)
0)
(else
(+ 1 (max (depth (left t)) (depth (right t))))
)
)
)
)
;; return the max value in a tree
(define tree-max
(lambda (t)
(cond
((is-empty? t)
'error)
((is-empty? (right t))
(value t))
(else
(tree-max (right t)))
)
)
)
;; test if x is a value in tree t
(define contains
(lambda (x t)
(cond
((is-empty? t)
#f)
((= x (value t))
#t)
((< x (value t))
(contains x (left t)))
(else
(contains x (right t)))
)
)
)