Introduction to Scheme Continued¶
Let¶
Sometimes a Scheme function needs to re-do the same calculation, e.g.:
(define operator1
(lambda (e)
(cond
((equal? (car e) '+) 'addition)
((equal? (car e) '-) 'subtraction)
((equal? (car e) '*) 'multiplication)
((equal? (car e) '/) 'division)
(else 'unknown)
)
)
)
The expression (car e) is repeated 4 times, making the code a little
longer and slower than it needs to be. Better would be to evaluate (car e)
once, save its value, and then use this saved value in place of repeated calls
to (car e).
Here’s a neat trick that does that for us:
(define operator2
(lambda (e)
(
(lambda (op)
(cond
((equal? op '+) 'addition)
((equal? op '-) 'subtraction)
((equal? op '*) 'multiplication)
((equal? op '/) 'division)
(else 'unknown)
) ;; cond
) ;; op
(car e) ;; bound to op
)
) ;; e
)
The idea here is to evaluate (car e) one time and assign its value to
op. Then we use op wherever we wrote (car e). Notice how we are
taking advantage of the fact that a lambda function call binds the value of
the argument you pass it to op.
Clearly, this is longer and harder to read than the code in operator1, and
the distance between op and the value it gets assigned is pretty big —
in practice one could easily not realize that op is being assigned (car
e).
So what Scheme does is provide some “syntactic sugar” to simplify this trick.
Here is a version that uses a let expression:
(define operator3
(lambda (e)
(let ((op (car e))
)
(cond
((equal? op '+) 'addition)
((equal? op '-) 'subtraction)
((equal? op '*) 'multiplication)
((equal? op '/) 'division)
(else 'unknown)
)
)
)
)
This is much clearer! Now op and its assigned value are right beside each
other. Plus the use of the let keyword signals our intention much more
clearly than using the basic lambda trick.
In general, a Scheme let expression allows you to define any number of
variables:
(let ((x1 val1)
(x2 val2)
...
(xn valn)
)
body ;; x1 ... xn can be used here
)
The entire expression returns the value of body, so you can wrap any
expression in a let if useful.
For example:
> (let ((a 1) (b 1) (c 2)) (+ a b c))
4
There is a subtlety here that is worth exploring a bit. The let expression
in the example could be re-written like this:
> ((lambda (a b c) (+ a b c)) 1 1 2)
4
Indentation makes the scope clearer:
(
(lambda (a b c)
(+ a b c)
)
1 1 2 ;; a, b, c are not in scope here
)
The scope of the variables a, b, and c is limited to the lambda
function they’re defined in and, in particular, they cannot be used in the
calculation of the parameters passed to it.
So, for example, this expression causes an error:
(
(lambda (a b c)
(+ a b c)
)
1 a 2 ;; error: a is not in scope
)
If you re-write this as an equivalent let expression, you get this:
(let ((a 1)
(b a) ;; error: can't use a in let value expression!
(c 2)
)
(+ a b c)
)
This is an also an error, because let does not let you use any of the
variables you are defining within the value expression for any other
variables.
While this limitation makes sense given what let compiles to, it is
inconvenient in practice. And so Scheme provides let* to remove this
restriction. This works as expected:
(let* ((a 1)
(b a) ;; okay: this is a let* environment
(c 2)
)
(+ a b c)
)
This let* could be re-written as embedded let environments:
(let ((a 1))
(let ((b a)) ;; ok: a is in scope
(let ((c 2))
(+ a b c)
)
)
)
Or even as plain lambdas:
(
(lambda (a)
(
(lambda (b)
(
(lambda (c)
(+ a b c)
)
2 ;; bound to c
)
)
a ;; bound to b
)
)
1 ;; bound to a
)
Here’s an example of a basic let expression 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)
)
)
)
)
> (eval-basic '(1 + 2))
3
> (eval-basic '(1 - 2))
-1
Another example where a let-environment is useful is in the following
implementation of the deep-map function. deep-map is a variation of
map that works like map, except the passed-in mapping function is
applied to every non-list value in the list, even those nested inside lists.
For example:
> (deep-map1 1+ '(1 (2 (3) 4 5 (6))))
(2 (3 (4) 5 6 (7)))
Here’s the definition for deep-map1:
(define deep-map1
(lambda (f lst)
(cond
((null? lst)
())
(else
(let* ((head (car lst))
(body (cdr lst))
(new_body (deep-map1 f body))
)
(cond
((list? head)
(cons (deep-map1 f head) new_body))
(else
(cons (f head) new_body))
)
)
)
)
)
)
Notice that this uses let* instead of let to make the definition of
new_body easier.
An alternative implementation is to embed the conditional into cons,
e.g.:
(define deep-map2
(lambda (f lst)
(cond
((null? lst)
())
(else
(let* ((head (car lst))
(body (cdr lst))
(new_body (deep-map2 f body))
)
(cons (if (list? head)
(deep-map2 f head)
(f head)
)
new_body
)
)
)
)
)
)
Yet another way to write it would be to use my-fold from the previous notes. In this
version, there are no repeated computations in the body, so let/let*
isn’t needed:
(define deep-map3
(lambda (f lst)
(my-fold (lambda (a rest)
(cons (if (list? a)
(deep-map3 f a)
(f a)
)
rest
)
)
'()
lst
)
)
)
In fact, it can be done even more simply just using my-map from above,
e.g.:
(define deep-map4
(lambda (f lst)
(my-map (lambda (a)
(if (list? a)
(deep-map4 f a)
(f a)
)
)
lst
)
)
)
Again, no let/let* is needed here since there are no repeated
expressions.
A Propositional Expression Evaluator¶
One of the applications that Scheme is good at is writing interpreters, compilers, and other programs that process programming languages. As long as we’re willing to stick languages with a Scheme-like syntax, then Scheme is often a great choice for at least prototyping such programs.
Lets write some functions that deal with literal boolean propositional
expressions like (t and (not f)). The symbols t and f stand for
true and false respectively, and there are no variables allowed in the
expressions. We are not using the built-in Scheme boolean values (#t and
#f) since this is out own little language that we’re defining.
First, we define a series of functions to test if a value has a particular top-level form:
(define is-true? (lambda (e) (equal? e 't)))
(define is-false? (lambda (e) (equal? e 'f)))
(define is-literal?
(lambda (e)
(or (is-false? e)
(is-true? e))
)
)
;; 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))
)
)
)
;; (p op q)
(define is-bin-op?
(lambda (e op)
(and (nlist? 3 e)
(equal? op (second e))
)
)
)
(define is-and? (lambda (e) (is-bin-op? e 'and))) ;; (p and q)
(define is-or? (lambda (e) (is-bin-op? e 'or))) ;; (p or q)
These are all non-recursive functions that check that the top-level form of an expression. They don’t check if sub-expressions are valid. Also notice how we use lots of little functions to build more complex functions.
Next, lets write a recursive 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? (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))))
(else
#f)
)
)
)
The idea of this function is to first determine the top-level form of e,
and then to recursively check that its sub-expressions are also valid.
Next, lets write an evaluator that calculates the value of a valid proposition:
(define eval-prop-bool
(lambda (e)
(cond
((is-literal? e)
(is-true? e))
((is-not? e)
(not (eval-prop-bool (second e))))
((is-and? e)
(and (eval-prop-bool (first e))
(eval-prop-bool (third e))))
((is-or? e)
(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:
> (eval-prop '((not t) and (t or (not f))))
f
We write the -eval-prop function to be consistent, i.e. in our boolean
literal language t means true and f means false, and so we want those
values returned instead of #t and #f.
EBNF: Extended Backus-Naur Notation¶
The is-expr? function is a precise definition of what is, and isn’t, a
valid boolean literal expression. Another way to precisely specify a language
is to use Extended Backus-Naur Formalism, or EBNF
for short. EBNF is a a little language designed for precisely defining the
syntax (not semantics!) of programming languages.
An EBNF “program” consists of a series of named productions, i.e. rules of this general form:
production-name = body .
The idea is that whenever you see production-name in an EBNF rule, you
can replace that name with the body of the corresponding rule. A set of
productions is called a grammar, and grammars are very useful for creating
things like lexers and parsers.
We’ll use the Go EBNF notation,
which, among other details given below, ends production rules with a ..
For example, here is the production that Go uses to define an assignment
operator:
assign_op = [ add_op | mul_op ] "=" .
Anything in “”-marks is indicates a token/symbol that could appear as-is in a
Go program. So in this production, the "=" at the end means a =
character that appears in a Go program, while the = that appears near the
start is part of the EBNF language that separates a production’s name from its
body.
Two other EBNF operators appear in this production. The | is the
alternation operator, and indicates a choices between two, or more,
alternatives. So add_op | mul_op means you can chose add_op or
mul_up (but not both). Here’s another example:
add_op = "+" | "-" | "|" | "^" .
This production, named add_op, says that an add_op is a "+",
"-", "|", or "^". This defines add_op by simply listing all
the possible alternatives.
The [] operator indicates an optional expression that can occur 0, or
1, times. So the expression [ add_op | mul_op ] means that the entire
expression can appear, or not appear. If it does occur, then, because of the
|, either add_op or mul_op is chosen.
Another EBNF operator is {}, which indicates repetition of 0, or
more, times. For example:
identifier = letter { letter | unicode_digit } .
This describes legal identifiers in Go, i.e. the legal names for things like
variables, functions, structs, types, and packages. It says that an identifier
must start with a letter, and then be followed by 0 or more letters or
digits:
letter = unicode_letter | "_" .
decimal_digit = "0" ... "9" .
In the Go EBNF notation, ... is
an informal short-hand that is used to indicate an obvious pattern. So the
decimal_digit production is understood to be equivalent to this:
decimal_digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
The identifier rule lets us check if a sequence of characters is a legal
identifier name. For example, up2 is a legal Go identifier. We can check
this by tracing the identifier production. The first character, u, is
a valid letter, and the next character is a valid letter. The 2 is a
valid digit, and so the entire identifier is valid.
Now consider 4xyz, which is not a valid Go identifier. It starts with
4, but according to the letter production 4 is not a valid
letter. So we know 4xyz cannot be an identifier, because a valid
identifier must start with a letter.
The unicode_letter production allows all characters marked as “Letter” by
Unicode. There are thousands of such characters, so they are not listed
explicitly.
Example: EBNF Rules for Literal Propositional Expressions¶
Now lets write an EBNF grammar, using the Go EBNF notation, to describe the valid boolean
literal expressions that (is-expr? e) returns true for.
Here are the productions:
expr = bool-literal | not-expr | and-expr | or-expr .
bool-literal = "t" | "f" .
not-expr = "(" "not" expr ")" .
and-expr = "(" expr "and" expr ")" .
or-expr = "(" expr "or" expr ")" .
Note that EBNF does not require the productions to appear in any particular order. But, for humans, we usually group related productions, and often put them in the order either from most general to specific, or more specific to general.
We should point out that the syntax of this little language is specifically designed to be Scheme-like, and so every expression is fully-bracketed. This means we don’t need to define the precedence of operators, since the brackets always make that explicit. This makes the parsing much simpler, in fact almost trivial.
Consider the not-expr production. It is recursive because it expands into
an expression involving expr, which could expand into not-expr. This
allows us to show that an expression like “(not (not t))” is valid as
follows:
expr = not-expr
= "(" "not" expr ")"
= "(" "not" not-expr ")"
= "(" "not" "(" "not" expr ")" ")"
= "(" "not" "(" "not" bool-literal ")" ")"
= "(" "not" "(" "not" "t" ")" ")"
Each step expands one part of the expression, and, by making the right choice of rules, eventually we get the exact expression we want. If you want to automate this process, you could write a parser to do this.
Comparing this EBNF grammar to the implementation of is-expr?, you can
see that it shares some direct similarities. Each of the productions
corresponds to a Scheme function, and those functions essentially mimic
the recursive structure of the productions.
Simplifying a Propositional Expression¶
Some propositional expressions can be simplified into logically equivalent
expressions. For example, an expression of the form (not (not p))
simplifies to the logically equivalent expression p.
Lets write an expression simplifier that applies this one particular rule to expressions:
;; double negation elimination
;; (not (not expr)) <==> expr
(define simplify
(lambda (e)
(cond
((is-literal? e)
e)
((and (is-not? e) (is-not? (second e))) ;; (not (not 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 "invalid expression"))
)
)
)
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:
> (simplify '((not (not t)) and (not (not t))))
(t and t)
Rewriting an Expression with Only nand¶
An interesting and useful fact about propositional logic is that any
expression can be re-written as a logically equivalent expression that uses
onle 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 the other propositional operators in terms of
nand:
(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))
With these rules we can transform any propositional expression into a
logically equivalent one using only nand.
Note here that we are allow variables, like p or q, in the expressions
we want to simplify. However, we don’t make any assumptions about value these
variables represent.
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)
)
)
;; Returns an expression logically equivalent to e that uses
;; "nand" as the only operator.
(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)))
)
)
)
> (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.
Example: Rewriting Scheme Code¶
After you’ve written some Scheme code, you may have noticed that these two expressions evaluate to the same thing:
(cond (test val1)
(else val2))
;; same as
(if test val1 val2)
The if-expression is a little simpler and easier to read, so it’s often the
preferred form. But when writing code you don’t always know for sure if you
have only one test, and so it’s wise to use cond everywhere. After your
program is done you could go back and re-write any single-condition cond
expressions as an equivalent if-expression, but that is tedious and
error-prone.
What we could do instead is write a Scheme function to automatically replace
occurrences of a simple cond with an equivalent if.
To do this, we first, we define a few helper functions:
;; returns true iff lst is a list of length n
(define nlist?
(lambda (n lst)
(and (list? lst)
(= n (length lst))
)
)
)
;; returns true iff the first element of lst equals x
(define starts-with
(lambda (x lst)
(equal? x (car lst))
)
)
Next, we’ll write a function that recognizes simple cond expressions:
;; Returns true for cond expressions of this form:
;;
;; (cond (test val1)
;; (else val2) ;; else could be #f instead
;; )
;;
(define is-simple-cond?
(lambda (lst)
(and (nlist? 3 lst)
(starts-with 'cond lst)
(nlist? 2 (second lst))
(nlist? 2 (third lst))
(member (car (third lst)) '(else #t))
)
)
)
Notice that the last expression of the and conveniently lets use use
either else or #t.
Now, we write a function that re-writes a simple cond as an equivalent
if:
;; (cond (test val1)
;; (else val2))
;;
;; same as
;;
;; (if test val1 val2)
;;
;; Pre-condition:
;; (is-simple-cond? lst)
(define rewrite-simple-cond-top-level
(lambda (lst)
(list 'if (car (second lst))
(second (second lst))
(second (third lst)))
)
)
It’s called top-level because it does not recursively rewrite any sub-
expressions.
Next, we define a general-purpose rewriting function that replaces one expression with another:
(define rewrite
(lambda (is-expr? rewrite-top-level lst)
(cond ((is-expr? lst)
(rewrite is-expr? rewrite-top-level (rewrite-top-level lst)))
((list? lst)
(map (lambda (x) (rewrite is-expr? rewrite-top-level x))
lst))
(else
lst)
)
)
)
Here, is-expr? is function (such as is-simple-cond?) that tests if a
value matches an expression, and rewrite-top-level is a function that,
given an expression that satisfies is-expr?, returns a new expression.
rewrite is a deep function, i.e. it recursively rewrites all
sub-expression of the passed-in list.
Finally, we use rewrite to create a simple-cond-to-if function like this:
(define rewrite-simple-cond
(lambda (x)
(rewrite is-simple-cond? rewrite-simple-cond-top-level x)
)
)
You can use it as follows:
(define test
'(define my-length
(lambda (lst)
(cond
((null? lst)
0)
(else
(+ 1 (my-length (cdr lst))))
)
)
)
)
;;;
> (pp (rewrite-simple-cond test))
(define my-length
(lambda (lst)
(if (null? lst)
0
(+ 1 (my-length (cdr lst))))))
Many kinds of useful code transformations can be implemented in the same way, i.e. by providing a recognizer function, and a top-level rewriting function.
If you write a number of these transformations, you will most likely find that
writing the specific recognizer and re-write functions are usually simple but
tedious. While we won’t go into the details here, it is possible to use
unify (see below) to implement a function called make-rewriter that
lets us implement rewrite-simple-cond like this:
(define rewrite-simple-cond
(make-rewriter '(cond (?test ?val1) ;; input pattern
(else ?val2))
'(if ?test ?val1 ?val2) ;; output patten
)
)
The implementation of make-rewriter takes a bit of work, but once you have
it then many transformations can be described simply by writing the input
pattern and the output pattern.
Here’s the source code for these two different implementations of these re-writers:
Pattern Matching with Unification¶
If you do a lot of Scheme programming, you soon discover that you need a lot
of code that splits lists up into pieces using functions like car,
cdr, cadr, cddr, and so on. While this code isn’t hard to write,
it does get pretty tedious and cluttered.
An alternative to writing this sort of code by hand is to use pattern
matching. Here, we will use the simple pattern matching code in the file
unify.scm. It implements unification
through the use of the function (unify expr1 expr2). It is easiest to
understand through some examples.
unify.scm provides one main function called
unify that can be called like this:
=> (unify 'a 'b)
#f
This returns #f (false) because 'a and 'b are not the same, i.e.
they don’t unify. However:
=> (unify 'a 'a)
()
'a and 'a do unify, because they are the same. (unify 'a 'a)
returns the empty list, '(), which might seem a bit odd. It will make more
sense after seeing some more examples.
Symbols that begin with a ? are variables from the point of view of
unify, and they are can be bound to other expressions. For example:
=> (unify '?x 'a)
((?x . a))
The return value is ((?x . a)), which is list of pairs (i.e. an
association list), where each pair is a variable and its value. unify
promises that these if you replace the variables in the input expressions with
their corresponding values, then the two expressions will be the same.
In other words, (unify expr1 expr2) returns a list of variable/value pairs
that, when the variables in expr1 and expr2 are replaced by their
values, the resulting expressions will be the same.
More examples should make this clear:
=> (unify '(?x b c) '(a b c))
((?x . a))
=> (unify '(?x b c) '(a b ?y))
((?y . c) (?x . a))
=> (unify '(?x ?x ?x) '(?y 2 ?y))
((?y . 2) (?x . ?y))
=> (unify '(?left ?op ?right) '(5 + x))
((?right . x) (?op . +) (?left . 5))
=> (unify '(?left ?op ?right) '((2 * a) - (16 / 4)))
((?right 16 / 4) (?op . -) (?left 2 * a))
If there are no assignments of values to the variables in an expression that
will make them equal, then #f is returned:
=> (unify '(?s 1) '(2 ?s))
#f
=> (unify '(?s ?t) '(?s ?t ?t))
#f
If you try to unify two expressions that are the same and have no variables,
or the variables can be any value, then unify returns an empty list:
=> (unify '(2 (a b)) '(2 (a b)))
()
=> (unify '(?x ?x) '(?x ?x))
()
The practical value of unification is that it’s often a short and easy way to chop up lists into smaller parts.
For example, suppose we want to check that the top-level of a list is a propositional expression:
(define make-recognizer
(lambda (e1)
(lambda (e2)
(if (unify e1 e2)
#t
#f
)
)
)
)
(define is-and? (make-recognizer '(?x and ?y)))
(define is-or? (make-recognizer '(?x or ?y)))
(define is-not? (make-recognizer '(not ?x)))
The is-and?, is-or?, and is-not? functions are quite are short and
readable.
Example: Binary Search Trees¶
The following is a sample Scheme implementation of a basic binary search tree. It’s provided as an example of straightforward Scheme implementation of a standard program.
;;; 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 tree-sort
(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)))
)
)
)