# 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) '-) '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 '-) '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 '-) '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
(body (cdr lst))
(new_body (deep-map1 f body))
)
(cond
(else
)
)
)
)
)
)


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
(body (cdr lst))
(new_body (deep-map2 f body))
)
)
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)))
)
)
)