### Section 2.1. Interacting with Scheme

While Scheme provides various input and output procedures, the REPL takes care of reading expressions and printing their values. This frees you to concentrate on writing your program without worrying about how its results will be displayed.

The examples in this chapter and in the rest of the book follow a regular format. An expression you might type from your keyboard is given first, possibly spanning several lines. The value of the expression is given after the **=>**, to be read as "evaluates to." The **=>** is omitted for definitions and when the value of an expression is unspecified.

The example programs are formatted in a style that "looks nice" and conveys the structure of the program. The code is easy to read because the relationship between each expression and its subexpressions is clearly shown. Scheme ignores indentation and line breaks, however, so there is no need to follow a particular style. The important thing is to establish one style and keep to it. Scheme sees each program as if it were on a single line, with its subexpressions ordered from left to right.

One of the simplest Scheme expressions is a string constant. Try typing "Hi Mom!" (including the double quotes) in response to the prompt. The system should respond with "Hi Mom!"; the value of any constant is the constant itself.

```
"Hi Mom!" => "Hi Mom!"
```

Here is a set of expressions, each with Scheme's response.

```
"hello" => "hello"
42 => 42
22/7 => 22/7
3.141592653 => 3.141592653
+ => #<procedure>
(+ 76 31) => 107
(* -12 10) => -120
'(a b c d) => (a b c d)
```

Here are a few more expressions to try.

```
(car '(a b c)) => a
(cdr '(a b c)) => (b c)
(cons 'a '(b c)) => (a b c)
(cons (car '(a b c)) (cdr '(d e f))) => (a e f)
```

Next, let's try defining a procedure.

```
(define square
(lambda (n)
(* n n)
)
)
```

Try using *square*.

```
(square 5) => 25
(square -200) => 40000
(square 0.5) => .25
(square -1/2) => 1/4
```

Even though the next definition is short, you might enter it into a file. Let's assume you call the file "reciprocal.scm."

```
(define reciprocal
(lambda (n)
(if (= n 0)
"oops!"
(/ 1 n)
)
)
)
```

This procedure, *reciprocal*, computes the quantity 1/n for any number n ≠ 0. For n = 0, reciprocal

returns the string "oops!". Return to Scheme and try loading your file with the procedure `load`

.

```
(load "reciprocal.scm")
```

Finally, try using the procedure we have just defined.

```
(reciprocal 10) => 1/10
(reciprocal 1/10) => 10
(reciprocal 0) => "oops!"
(reciprocal (reciprocal 1/10)) => 1/10
```

### Section 2.2. Simple Expressions

The simplest Scheme expressions are constant data objects, such as strings, numbers, symbols, and lists. Scheme supports other object types, but these four are enough for many programs.

Let's discuss numbers in a little more detail. Numbers are constants. If you enter a number, Scheme echoes it back to you. The following examples show that Scheme supports several types of numbers.

```
123456789987654321 => 123456789987654321
3/4 => 3/4
2.718281828 => 2.718281828
2.2+1.1i => 2.2+1.1i
```

Scheme numbers include exact and inexact integer, rational, real, and complex numbers. Exact integers and rational numbers have arbitrary precision, i.e., they can be of arbitrary size. Inexact numbers are usually represented internally using IEEE standard floating-point representations.

Scheme provides the names `+`

, `-`

, `*`

, and `/`

for the corresponding arithmetic procedures. Each procedure accepts two numeric arguments. The expressions below are called *procedure applications*, because they specify the application of a procedure to a set of arguments.

```
(+ 1/2 1/2) =>1
(- 1.5 1/2) => 1.0
(* 3 1/2) => 3/2
(/ 1.5 3/4) => 2.0
```

Scheme employs prefix notation even for common arithmetic operations. Any procedure application, whether the procedure takes zero, one, two, or more arguments, is written as `(procedure arg ...)`

. This regularity simplifies the syntax of expressions; one notation is employed regardless of the operation, and there are no complicated rules regarding the precedence or associativity of operators.

Procedure applications may be nested, in which case the innermost values are computed first. We can thus nest applications of the arithmetic procedures given above to evaluate more complicated formulas.

```
(+ (+ 2 2) (+ 2 2)) => 8
(- 2 (* 4 1/3)) => 2/3
(* 2 (* 2 (* 2 (* 2 2)))) => 32
(/ (* 6/7 7/2) (- 4.5 1.5)) => 1.0
```

Simple numeric objects are sufficient for many tasks, but sometimes aggregate data structures containing two or more values are needed. In many languages, the basic aggregate data structure is the array. In Scheme, it is the *list*. Lists are written as sequences of objects surrounded by parentheses. For instance, (1 2 3 4 5) is a list of numbers, and ("this" "is" "a" "list") is a list of strings. **Lists need not contain only one type of object**, so (4.2 "hi") is a valid list containing a number and a string. **Lists may be nested** (may contain other lists), so ((1 2) (3 4)) is a valid list with two elements, each of which is a list of two elements.

You might notice that lists look just like procedure applications and wonder how Scheme tells them apart. The answer might be that Scheme looks at the first element of the list or procedure application and makes its decision based on whether that first element is a procedure or not. This answer is not good enough, since we might even want to treat a valid procedure application such as `(+ 3 4)`

as a list. The answer is that we must tell Scheme explicitly to treat a list as data rather than as a procedure application. We do this with `quote`

.

```
(quote (1 2 3 4 5))
(quote ("this" "is" "a" "list"))
(quote (+ 3 4))
```

The `quote`

forces the list to be treated as data. Because `quote`

is required fairly frequently in Scheme code, Scheme recognizes a single quotation mark ( ' ) preceding an expression as an abbreviation for `quote`

.

```
'(1 2 3 4 5)
'("this" "is" "a" "list")
'(+ 3 4)
```

Both forms are referred to as `quote`

expressions. We often say an object is quoted when it is enclosed in a `quote`

expression.

A `quote`

expression is *not* a procedure application, since it inhibits the evaluation of its subexpression. It is an entirely different syntactic form. Scheme supports several other syntactic forms in addition to procedure applications and `quote`

expressions. Each syntactic form is evaluated differently.

Not all quote expressions involve lists.

```
(quote hello) => hello
```

The symbol "hello" must be quoted in order to prevent Scheme from treating "hello" as a *variable*.

You might wonder why applications and variables share notations with lists and symbols. The shared notation allows Scheme programs to be represented as Scheme data, simplifying the writing of interpreters, compilers, editors, and other tools in Scheme. This is demonstrated by the Scheme interpreter given in Section 12.7, which is itself written in Scheme. Many people believe this to be one of the most important features of Scheme.

Numbers and strings may be quoted, too.

```
'2 => 2
'2/3 => 2/3
(quote "Hi Mom!") => "Hi Mom!"
```

Numbers and strings are treated as constants in any case, however, so quoting them is unnecessary.

Now let's discuss some Scheme procedures for manipulating lists. There are two basic procedures for taking lists apart: `car`

and `cdr`

(pronounced could-er). `car`

returns the first element of a list, and `cdr`

returns the remainder of the list. (The names "car" and "cdr" are derived from operations supported by the first computer on which a Lisp language was implemented, the IBM 704. Click this wiki link for more details) Each requires a nonempty list as its argument.

```
(car '(a b c)) => a
(cdr '(a b c)) => (b c)
(cdr '(a)) => ()
(car '((a b) (c d))) => (a b)
(cdr '((a b) (c d))) => ((c d))
```

The first element of a list is often called the "car" of the list, and the rest of the list is often called the "cdr" of the list. The `cdr`

of a list with one element is (), the *empty* list.

The procedure `cons`

constructs lists. It takes two arguments. The second argument is usually a list, and in that case `cons`

returns a list.

```
(cons 'a '()) => (a)
(cons 'a '(b c)) => (a b c)
(cons 'a (cons 'b (cons 'c '()))) => (a b c)
(cons '(a b) '(c d)) => ((a b) c d)
```

Just as "car" and "cdr" are often used as nouns, "cons" is often used as a verb. Creating a new list by adding an element to the beginning of a list is referred to as *consing* the element onto the list.

Notice the word "usually" in the description of cons's second argument. The procedure `cons`

actually builds *pairs*, and there is no reason that the `cdr`

of a pair must be a list. A list is a sequence of pairs; each pair's `cdr`

is the next pair in the sequence.

Note: here the *pair* means a datum and the next pointer(in other languages). Click this wiki link for more details:

https://en.wikipedia.org/wiki/Lisp_%28programming_language%29#Conses_and_lists

The `cdr`

of the last pair in a *proper* list is the empty list. Otherwise, the sequence of pairs forms an *improper* list. More formally, the empty list is a proper list, and any pair whose `cdr`

is a proper list is a proper list.

An improper list is printed in dotted-pair notation, with a period, or dot, preceding the final element of the list.

```
(cons 'a 'b) => (a . b)
(cdr '(a . b)) => b
(cons 'a '(b . c)) => (a b . c)
```

Because of its printed notation, a pair whose `cdr`

is not a list is often called a dotted pair. Even pairs whose `cdrs`

are lists can be written in dotted-pair notation, however, although the printer always chooses to write proper lists without dots.

```
'(a . (b . (c . ()))) => (a b c)
```

The procedure `list`

is similar to `cons`

, except that it takes an arbitrary number of arguments and always builds a proper list.

```
(list 'a 'b 'c) => (a b c)
(list 'a) => (a)
(list) => ()
```

### Section 2.3. Evaluating Scheme Expressions

Let's turn to a discussion of how Scheme evaluates the expressions you type. We have already established the rules for constant objects such as strings and numbers: the object itself is the value. You have probably also worked out in your mind a rule for evaluating procedure applications of the form (procedure arg_{1} ... arg_{n}). Here, procedure is an expression representing a Scheme procedure, and arg_{1} ... arg_{n} are expressions representing its arguments. One possibility is the following.

- Find the value of procedure.
- Find the value of arg
_{1}. - Find the value of arg
_{n}. - Apply the value of procedure to the values of arg
_{1}... arg_{n}.

For example, consider the simple procedure application (+ 3 4). The value of + is the addition procedure, the value of 3 is the number 3, and the value of 4 is the number 4. Applying the addition procedure to 3 and 4 yields 7, so our value is the object 7.

By applying this process at each level, we can find the value of the nested expression (* (+ 3 4) 2). The value of * is the multiplication procedure, the value of (+ 3 4) we can determine to be the number 7, and the value of 2 is the number 2. Multiplying 7 by 2 we get 14, so our answer is 14.

This rule works for procedure applications but not for `quote`

expressions because the subexpressions of a procedure application are evaluated, whereas the subexpression of a `quote`

expression is not. The evaluation of a `quote`

expression is more similar to the evaluation of constant objects. The value of a `quote`

expression of the form `(quote object)`

is simply `object`

.

Constant objects, procedure applications, and `quote`

expressions are only three of the many syntactic forms provided by Scheme. Fortunately, only a few of the other syntactic forms need to be understood directly by a Scheme programmer; these are referred to as *core* syntactic forms. The remaining syntactic forms are *syntactic extensions* defined, ultimately, in terms of the core syntactic forms. We will discuss the remaining core syntactic forms and a few syntactic extensions in the remaining sections of this chapter. Section 3.1 summarizes the core syntactic forms and introduces the syntactic extension mechanism.

Before we go on to more syntactic forms and procedures, two points related to the evaluation of procedure applications are worthy of note. First, the process given above is over-specified, in that it requires the subexpressions to be evaluated from left to right. That is, procedure is evaluated before arg_{1}, arg_{1} is evaluated before arg_{2}, and so on. This need not be the case. A Scheme evaluator is free to evaluate the expressions in any order---left to right, right to left, or any other sequential order. In fact, the subexpressions may be evaluated in different orders for different applications, even in the same implementation.

The second point is that procedure is evaluated in the same way as arg_{1} ... arg_{n}. While procedure is often a variable that names a particular procedure, this need not be the case. Exercise 2.2.3 had you determine the value of the expression `((car (list + - * /)) 2 3)`

. Here, procedure is `(car (list + - * /))`

. The value of `(car (list + - * /))`

is the addition procedure, just as if procedure were simply the variable +.

### Section 2.4. Variables and Let Expressions

Suppose *expr* is a Scheme expression that contains a variable *var*. Suppose, additionally, that we would like *var* to have the value *val* when we evaluate *expr*. For example, we might like *x* to have the value 2 when we evaluate `(+ x 3)`

. Or, we might want *y* to have the value 3 when we evaluate `(+ 2 y)`

. The following examples demonstrate how to do this using Scheme's `let`

syntactic form.

```
(let ((x 2))
(+ x 3)) => 5
(let ((y 3))
(+ 2 y)) => 5
(let ((x 2) (y 3))
(+ x y)) => 5
```

The `let`

syntactic form includes a list of variable-expression pairs, along with a sequence of expressions referred to as the body of the `let`

. The general form of a `let`

expression is: `(let ((var expr) ...) body1 body2 ...)`

.

We say the variables are bound to the values by the `let`

. We refer to variables bound by `let`

as *let-bound* variables.

A `let`

expression is often used to simplify an expression that would contain two identical subexpressions. Doing so also ensures that the value of the common subexpression is computed only once.

```
(+ (* 4 4) (* 4 4)) => 32
(let ((a (* 4 4))) (+ a a)) => 32
```

Brackets are often used in place of parentheses to delimit the bindings of a let expression(**seems not supported in mit-scheme**).

```
(let ([list1 '(a b c)] [list2 '(d e f)])
(cons (cons (car list1) (car list2))
(cons (car (cdr list1))
(car (cdr list2))))) => ((a . d) b . e)
```

Scheme treats forms enclosed in brackets just like forms enclosed in parentheses. An open bracket must be matched by a close bracket, and an open parenthesis must be matched by a close parenthesis. We use brackets for `let`

(and, as we'll see, several other standard syntactic forms) to improve readability, especially when we might otherwise have two or more consecutive open parentheses.

Since expressions in the first position of a procedure application are evaluated no differently from other expressions, a *let-bound* variable may be used there as well.

```
(let ([f +]) (f 2 3)) => 5
(let ([f +] [x 2]) (f x 3)) => 5
(let ([f +] [x 2] [y 3])
(f x y)) => 5
```

The variables bound by `let`

are visible only within the body of the `let`

.

```
(let ([+ *]) (+ 2 3)) => 6
(+ 2 3) => 5
```

This is fortunate, because we would not want the value of + to be the multiplication procedure everywhere.

It is possible to nest let expressions.

```
(let ((a 4) (b -3))
(let ((a-squared (* a a)) (b-squared (* b b)))
(+ a-squared b-squared))) => 25
```

When nested `let`

expressions bind the same variable, only the binding created by the inner `let`

is visible within its body.

```
(let ((x 1))
(let ((x (+ x 1)))
(+ x x))) => 4
```

The outer `let`

expression binds x to 1 within its body, which is the second `let`

expression. The inner `let`

expression binds x to (+ x 1) within its body, which is the expression (+ x x). What is the value of (+ x 1)? Since (+ x 1) appears within the body of the outer `let`

but not within the body of the inner `let`

, the value of x must be 1 and hence the value of(+ x 1) is 2. What about (+ x x)? It appears within the body of both `let`

expressions. Only the inner binding for x is visible, so x is 2 and (+ x x) is 4.

The inner binding for x is said to *shadow* the outer binding. A *let-bound* variable is visible everywhere within the body of its `let`

expression except where it is shadowed. The region where a variable binding is visible is called its *scope*. The scope of the first x in the example above is the body of the outer `let`

expression minus the body of the inner `let`

expression, where it is shadowed by the second x. This form of scoping is referred to as *lexical scoping*, since the scope of each binding can be determined by a straightforward textual analysis of the program.

Shadowing may be avoided by choosing different names for variables. Although choosing different names can sometimes prevent confusion, shadowing can help prevent the accidental use of an "old" value. For example, with the original version of the preceding example, it would be impossible for us to mistakenly refer to the outer x within the body of the inner `let`

.

### Section 2.5. Lambda Expressions

In the expression `(let ((x (* 3 4))) (+ x x))`

, the variable x is bound to the value of (* 3 4). What if we would like the value of (+ x x) where x is bound to the value of (/ 99 11)? Where x is bound to the value of (- 2 7)? In each case we need a different `let`

expression. When the body of the `let`

is complicated, however, having to repeat it can be inconvenient.

Instead, we can use the syntactic form *lambda* to create a new procedure that has x as a parameter and has the same body as the `let`

expression.

```
(lambda (x) (+ x x)) => #<procedure>
```

The general form of a lambda expression is

```
(lambda (var ...) body1 body2 ...)
```

The variables *var ...* are the formal parameters of the procedure, and the sequence of expressions *body1 body2 ...* is its body. (Actually, the true general form is somewhat more general than this, as you will see later.)

The most common operation to perform on a procedure is to apply it to one or more values.

```
((lambda (x) (+ x x)) (* 3 4)) => 24
```

Because procedures are objects, we can establish a procedure as the value of a variable and use the procedure more than once.

```
(let ((double (lambda (x) (+ x x))))
(list (double (* 3 4))
(double (/ 99 11))
(double (- 2 7)))) => (24 18 -10)
```

The procedure expects its actual parameter to be a number, since it passes the actual parameter on to +. In general, the actual parameter may be any sort of object. Consider, for example, a similar procedure that uses `cons`

instead of +.

```
(let ((double-cons (lambda (x) (cons x x)))) (double-cons 'a)) => (a . a)
```

Noting the similarity between *double* and *double-cons*, you should not be surprised to learn that they may be collapsed into a single procedure by adding an additional argument.

```
(let ((double-any (lambda (f x) (f x x))))
(list (double-any + 13)
(double-any cons 'a))) => (26 (a . a))
```

This demonstrates that procedures may accept more than one argument and that arguments passed to a procedure may themselves be procedures.

As with `let`

expressions, `lambda`

expressions become somewhat more interesting when they are nested within other `lambda`

or `let`

expressions.

The occurrence of x within the `lambda`

expression refers to the x outside the `lambda`

that is bound by the outer `let`

expression. The variable x is said to *occur free* in the `lambda`

expression or to be a free variable of the `lambda`

expression. The variable y does not occur free in the lambda expression since it is bound by the `lambda`

expression. A variable that occurs free in a `lambda`

expression should be bound, e.g., by an enclosing `lambda`

or `let`

expression, unless the variable is (like the names of primitive procedures) bound outside of the expression, as we discuss in the following section.

What happens when the procedure is applied somewhere outside the scope of the bindings for variables that occur free within the procedure, as in the following expression?

```
(let ((f (let ((x 'sam))
(lambda (y z) (list x y z)))))
(f 'i 'am)) => (sam i am)
```

The answer is that the same bindings that were in effect when the procedure was created are in effect again when the procedure is applied. This is true even if another binding for x is visible where the procedure is applied.

```
(let ((f (let ((x 'sam))
(lambda (y z) (list x y z)))))
(let ((x 'not-sam))
(f 'i 'am))) => (sam i am)
```

Incidentally, a `let`

expression is nothing more than the direct application of a `lambda`

expression to a set of argument expressions. For example, the two expressions below are equivalent.

```
(let ((x 'a)) (cons x x)) ((lambda (x) (cons x x)) 'a)
```

In fact, a `let`

expression is a syntactic extension defined in terms of `lambda`

and procedure application, which are both core syntactic forms. In general, any expression of the form

```
(let ((var expr) ...) body1 body2 ...)
```

is equivalent to the following.

```
((lambda (var ...) body1 body2 ...) expr ...)
```

As mentioned above, the general form of `lambda`

is a bit more complicated than the form we saw earlier, in that the formal parameter specification, `(var ...)`

, need not be a proper list, or indeed even a list at all. The formal parameter specification can be in any of the following three forms:

- a proper list of variables, (var
_{1}... var_{n}), such as we have already seen, - a single variable, var
_{r}, or - an improper list of variables, (var
_{1}... var_{n}. var_{r}).

In the first case, exactly n actual parameters must be supplied, and **each variable is bound to the corresponding actual parameter**. In the second, any number of actual parameters is valid; **all of the actual parameters are put into a single list and the single variable is bound to this list.** The third case is a hybrid of the first two cases. At least n actual parameters must be supplied. The variables var_{1} ... var_{n} are bound to the corresponding actual parameters, and the variable var_{r} is bound to a list containing the remaining actual parameters. In the second and third cases, var_{r} is sometimes referred to as a "rest" parameter because it holds the rest of the actual parameters beyond those that are individually named.

Let's consider a few examples to help clarify the more general syntax of `lambda`

expressions.

```
(let ((f (lambda x x)))
(f 1 2 3 4)) => (1 2 3 4)
(let ((f (lambda x x)))
(f)) => ()
(let ((g (lambda (x . y) (list x y))))
(g 1 2 3 4)) => (1 (2 3 4))
(let ((h (lambda (x y . z) (list x y z))))
(h 'a 'b 'c 'd)) => (a b (c d))
```

### Section 2.6. Top-Level Definitions

The variables bound by `let`

and `lambda`

expressions are not visible outside the bodies of these expressions. Suppose you have created an object, perhaps a procedure, that must be accessible anywhere, like `+`

or `cons`

. What you need is a top-level definition, which may be established with `define`

. Top-level definitions, which are supported by most interactive Scheme systems, are visible in every expression you enter, except where shadowed by another binding.

Let's establish a top-level definition of the *double-any* procedure of the last section.

```
(define double-any
(lambda (f x)
(f x x)))
```

The variable *double-any* now has the same status as `cons`

or the name of any other primitive procedure.

We can use *double-any* as if it were a primitive procedure.

```
(double-any + 10) => 20
(double-any cons 'a) => (a . a)
```

A top-level definition may be established for any object, not just for procedures.

```
(define sandwich "peanut-butter-and-jelly")
sandwich => "peanut-butter-and-jelly"
```

Most often, though, top-level definitions are used for procedures.

As suggested above, top-level definitions may be shadowed by `let`

or `lambda`

bindings.

```
(define xyz '(x y z))
(let ((xyz '(z y x)))
xyz) => (z y x)
```

Variables with top-level definitions act almost as if they were bound by a `let`

expression enclosing all of the expressions you type.

Here is the `list`

definition.

```
(define list (lambda x x))
```

Also, Scheme provides the abbreviations `cadr`

and `cddr`

for the compositions of `car`

with `cdr`

and `cdr`

with `cdr`

. That is, `(cadr list)`

is equivalent to `(car (cdr list))`

, and, similarly, `(cddr list)`

is equivalent to `(cdr (cdr list))`

. They are easily defined as follows.

```
(define cadr
(lambda (x)
(car (cdr x))))
(define cddr
(lambda (x)
(cdr (cdr x))))
```

Any definition *(define var expr)* where *expr* is a `lambda`

expression can be written in a shorter form that suppresses the `lambda`

. The exact syntax depends upon the format of the `lambda`

expression's formal parameter specifier, i.e., whether it is a proper list of variables, a single variable, or an improper list of variables. A definition of the form

*(define var _{0} (lambda (var_{1} ... var_{n}) e_{1} e_{2} ...))*

may be abbreviated

*(define (var*

_{0}var_{1}... var_{n}) e_{1}e_{2}...)while

*(define var*

_{0}(lambda var_{r}e_{1}e_{2}...))may be abbreviated

*(define (var*

_{0}. var_{r}) e_{1}e<sub2 ...)and

*(define var*

_{0}(lambda (var_{1}... var_{n}. var_{r}) e_{1}e_{2}...))may be abbreviated

*(define (var*

_{0}var_{1}... var_{n}. var_{r}) e_{1}e_{2}...)For example, the definitions of

`cadr`

and `list`

might be written as follows.```
(define (cadr x) (car (cdr x)))
(define (list . x) x)
```

This book does not often employ this alternative syntax. Although it is shorter, it tends to mask the reality that procedures are not intimately tied to variables, or names, as they are in many other languages.

Top-level definitions make it easier for us to experiment with a procedure interactively because we need not retype the procedure each time it is used. Let's try defining a somewhat more complicated variation of *double-any*, one that turns an "ordinary" two-argument procedure into a "doubling" one-argument procedure.

```
(define doubler
(lambda (f)
(lambda (x) (f x x))))
```

*doubler* accepts one argument, f, which must be a procedure that accepts two arguments. The procedure returned by *doubler* accepts one argument, which it uses for both arguments in an application of f. We can define, with *doubler*, the simple *double* and &double-cons* procedures of the last section.

```
(define double (doubler +))
(double 13/2) => 13
(define double-cons (doubler cons))
(double-cons 'a) => (a . a)
```

We can also define *double-any* with *doubler*.

```
(define double-any
(lambda (f x)
((doubler f) x)))
```

What happens if you attempt to use a variable that is not bound by a `let`

or `lambda`

expression and that does not have a top-level definition? Try using the variable *i-am-not-defined* to see what happens.

```
(i-am-not-defined 3)
```

Most Scheme systems print a message indicating that an unbound or undefined-variable exception has occurred.

The system should not, however, complain about the appearance of an undefined variable within a `lambda`

expression, until and unless the resulting procedure is applied. The following should not cause an exception, even though we have not yet established a top-level definition of *proc2*.

```
(define proc1
(lambda (x y)
(proc2 y x)))
```

If you try to apply *proc1* before defining *proc2*, you should get a undefined exception message. Let's give *proc2* a top-level definition and try *proc1*.

```
(define proc2 cons)
(proc1 'a 'b) (b . a)
```

When you define *proc1*, the system accepts your promise to define *proc2*, and does not complain unless you use *proc1* before defining *proc2*. This allows you to define procedures in any order you please.

### Section 2.7. Conditional Expressions

So far we have considered expressions that perform a given task unconditionally. Suppose that we wish to write the procedure `abs`

. If its argument x is negative, abs returns -x; otherwise, it returns x. The most straightforward way to write `abs`

is to determine whether the argument is negative and if so negate it, using the if syntactic form.

```
(define abs
(lambda (n)
(if (< n 0)
(- 0 n)
n)))
(abs -3) => 3
(abs 3) => 3
```

An `if`

expression has the form `(if test consequent alternative)`

, where *consequent* is the expression to evaluate if *test* is true and *alternative* is the expression to evaluate if *test* is false. In the expression above, *test* is `(< n 0)`

, *consequent* is `(- 0 n)`

, and *alternative* is *n*.

The procedure *abs* could be written in a variety of other ways. Any of the following are valid definitions of *abs*.

```
(define abs
(lambda (n)
(if (>= n 0) n
(- 0 n))))
(define abs
(lambda (n)
(if (not (< n 0))
n
(- 0 n))))
(define abs
(lambda (n)
(if (or (> n 0) (= n 0))
n
(- 0 n))))
(define abs
(lambda (n)
(if (= n 0) 0
(if (< n 0)
(- 0 n)
n))))
(define abs
(lambda (n)
((if (>= n 0) + -)
0
n)))
```

The syntactic form `or`

operates in a manner similar to `if`

. The general form of an or expression is `(or expr ...)`

. If there are no subexpressions, i.e., the expression is simply `(or)`

, the value is false. Otherwise, each *expr* is evaluated in turn until either (a) one of the expressions evaluates to true or (b) no more expressions are left. In case (a), the value is true; in case (b), the value is false.

Every Scheme object, is considered to be either true or false by conditional expressions and by the procedure `not`

. Only `#f`

is considered false; all other objects are considered true.

The `and`

syntactic form is similar in form to `or`

, but an `and`

expression is true if all its subexpressions are true, and false otherwise. In the case where there are no subexpressions, i.e., the expression is simply `(and)`

, the value is true. Otherwise, the subexpressions are evaluated in turn until either no more subexpressions are left or the value of a subexpression is false. The value of the `and`

expression is the value of the last subexpression evaluated.

Using `and`

, we can define a slightly different version of *reciprocal*.

```
(define reciprocal
(lambda (n)
(and (not (= n 0))
(/ 1 n))))
(reciprocal 3) => 1/3
(reciprocal 0.5) => 2.0
(reciprocal 0) => #f
```

In this version, the value is `#f`

if n is zero and 1/n otherwise.

The procedures `=, <, >, <=, and >=`

are called *predicates*. A predicate is a procedure that answers a specific question about its arguments and returns one of the two values `#t`

or `#f`

. The names of most predicates end with a question mark ( ? ); the common numeric procedures listed above are exceptions to this rule. Not all predicates require numeric arguments, of course. The predicate `null?`

returns true if its argument is the empty list `()`

and false otherwise.

The procedure `cdr`

must not be passed anything other than a pair, and an exception is raised when this happens. Common Lisp, however, defines `(cdr '())`

to be `()`

.

Another useful predicate is `eqv?`

, which requires two arguments. If the two arguments are equivalent, `eqv?`

returns true. Otherwise, `eqv?`

returns false.

```
(eqv? 'a 'a) => #t
(eqv? #f #t) => #f
(eqv? 3 2) => #f
(eqv? (cons 'a 'b) (cons 'a 'b)) => #f
```

As you can see, `eqv?`

returns true if the arguments are the same symbol, boolean, number, pair, or string. Two pairs are not the same by `eqv?`

if they are created by different calls to `cons`

, even if they have the same contents. Detailed equivalence rules for `eqv?`

are given in Section 6.2. (See this SO question: https://stackoverflow.com/questions/16299246/what-is-the-difference-between-eq-eqv-equal-and-in-scheme for more details).

Scheme also provides a set of *type predicates* that return true or false depending on the type of the object, e.g., `pair?`

, `symbol?`

, `number?`

, and `string?`

. The predicate `pair?`

, for example, returns true only if its argument is a pair.

```
(pair? '(a . c)) => #t
(pair? '(a b c)) => #t
(pair? '()) => #f
(pair? 'abc) => #f
(pair? "Hi Mom") =>#f
(pair? 12345) =>#f
```

Type predicates are useful for deciding if the argument passed to a procedure is of the appropriate type. For example, the following version of *reciprocal* checks first to see that its argument is a number before testing against zero or performing the division.

```
(define reciprocal2
(lambda (n)
(if (and (number? n) (not (= n 0)))
(/ 1 n)
"oops!")))
(reciprocal2 2/3) => 3/2
(reciprocal2 'a) => "oops!"
```

~~By the way, the code that uses ~~*reciprocal2* must check to see that the returned value is a number and not a string. To relieve the caller of this obligation, it is usually preferable to report the error, using `assertion-violation`

, as follows.

```
;assertion-violation not found on my machine: scheme 9.2
(define reciprocal3
(lambda (n)
(if (and (number? n) (not (= n 0)))
(/ 1 n)
(assertion-violation 'reciprocal3
"improper argument"
n))))
(reciprocal3 .25) => 4
(reciprocal3 0) => Unbound variable: assertion-violation
(reciprocal3 'a)
```

The first argument to `assertion-violation`

is a symbol identifying where the message originates, the second is a string describing the error, and the third and subsequent arguments are "irritants" to be included with the error message.

Let's look at one more conditional expression, `cond`

, that is often useful in place of `if`

. `cond`

is similar to `if`

except that it allows multiple test and alternative expressions. Consider the following definition of *sign*, which returns -1 for negative inputs, +1 for positive inputs, and 0 for zero.

```
(define sign
(lambda (n)
(if (< n 0)
-1
(if (> n 0)
+1
0))))
(sign -3.5)
(sign 0)
(sign 123)
(* (sign -1.2) (abs -12.3))
```

The two `if`

expressions may be replaced by a single `cond`

expression as follows.

```
(define sign2
(lambda (n)
(cond
((< n 0) -1)
((> n 0) +1)
(else 0))))
```

A `cond`

expression usually takes the form

```
(cond (test expr) ... (else expr))
```

though the `else`

clause may be omitted. This should be done only when there is no possibility that all the tests will fail, as in the new version of *sign* below.

```
(define sign3
(lambda (n)
(cond
((< n 0) -1)
((> n 0) +1)
((= n 0) 0))))
```

These definitions of `sign`

do not depend on the order in which the tests are performed, since only one of the tests can be true for any value of n.

### Section 2.8. Simple Recursion

A *recursive procedure* is a procedure that applies itself. For example, the `length`

procedure could be defined as this.

```
(define length
(lambda (ls)
(if (null? ls)
0
(+ (length (cdr ls)) 1))))
(length '()) => 0
(length '(a b)) => 2
```

Many Scheme implementations allow you to trace the execution of a procedure to see how it operates. In Chez Scheme, for example, one way to trace a procedure is to type `(trace name)`

, where *name* is the name of a procedure you have defined at top level. If you trace *length* as defined above and pass it the argument '(a b c d), you should see something like this:

```
| (length (a b c d))
| (length (b c d))
| | (length (c d))
| | | (length (d))
| | |0
| | 1
| |2
| 3
|4
```

Let's write a procedure, *list-copy*, that returns a copy of its argument, which must be a list. That is, *list-copy* returns a new list consisting of the elements (but not the pairs) of the old list. Making a copy might be useful if either the original list or the copy might be altered via `set-car!`

or `set-cdr!`

, which we discuss later.

```
(define list-copy
(lambda (ls)
(if (null? ls)
'()
(cons (car ls) (list-copy (cdr ls))))))
```

There is no reason why there cannot be more than one base case. The procedure *memv* takes two arguments, an object and a list. It returns the first sublist, or *tail*, of the list whose `car`

is equal to the object, or `#f`

if the object is not found in the list. The value of `memv`

may be used as a list or as a truth value in a conditional expression.

```
(define memv
(lambda (x ls)
(cond
((null? ls) #f)
((eqv? (car ls) x) ls)
(else (memv x (cdr ls))))))
(memv 'a '(a b b d)) => (a b b d)
(memv 'b '(a b b d)) => (b b d)
(memv 'c '(a b b d)) => #f
(if (memv 'b '(a b b d))
"yes"
"no") => "yes"
```

There may also be more than one recursion case. Like *memv*, the procedure *remv* defined below takes two arguments, an object and a list. It returns a new list with all occurrences of the object removed from the list.

```
(define remv
(lambda (x ls)
(cond
((null? ls) '())
((eqv? (car ls) x) (remv x (cdr ls)))
(else (cons (car ls) (remv x (cdr ls))))
)
)
)
(remv 'a '(a b b d))
(remv 'b '(a b b d))
(remv 'c '(a b b d))
(remv 'd '(a b b d))
```

Up to now, the recursion has been only on the `cdr`

of a list. It is sometimes useful, however, for a procedure to recur on the `car`

as well as the `cdr`

of the list. The procedure tree-copy defined below treats the structure of pairs as a tree rather than as a list, with the left subtree being the `car`

of the pair and the right subtree being the `cdr`

of the pair. It performs a similar operation to list-copy, building new pairs while leaving the elements (leaves) alone.

```
(define tree-copy
(lambda (tr)
(if (not (pair? tr))
tr
(cons (tree-copy (car tr))
(tree-copy (cdr tr))
)
)
)
)
(tree-copy '((a . b) . c)) => ((a . b) . c)
```

Before we leave the topic of recursion, let's consider a special form of repetition called *mapping*. Consider the following procedure, *abs-all*, that takes a list of numbers as input and returns a list of their absolute values.

```
(define abs-all
(lambda (ls)
(if (null? ls)
'()
(cons
(abs (car ls))
(abs-all (cdr ls))
)
)
)
)
(abs-all '(1 -2 3 -4 5 -6)) => (1 2 3 4 5 6)
```

This procedure forms a new list from the input list by applying the procedure `abs`

to each element. We say that *abs-all* maps abs over the input list to produce the output list. Mapping a procedure over a list is a fairly common thing to do, so Scheme provides the procedure `map`

, which maps its first argument, a procedure, over its second, a list. We can use `map`

to define *abs-all*.

```
(define abs-all
(lambda (ls)
(map abs ls)
)
)
```

We really do not need *abs-all*, however, since the corresponding direct application of `map`

is just as short and perhaps clearer.

```
(map abs '(1 -2 3 -4)) => (1 2 3 4)
```

Of course, we can use `lambda`

to create the procedure argument to `map`

, e.g., to square the elements of a list of numbers.

```
(map (lambda (x) (* x x)) '(1 -3 5 -7)) => (1 9 25 49)
```

We can map a multiple-argument procedure over multiple lists, as in the following example.

```
(map cons '(a b c) '(1 2 3)) => ((a . 1) (b . 2) (c . 3))
```

The lists must be of the same length, and the procedure should accept as many arguments as there are lists. Each element of the output list is the result of applying the procedure to corresponding members of the input list.

Looking at the first definition of *abs-all* above, you should be able to derive, before studying it, the following definition of *map1*, a restricted version of `map`

that maps a one-argument procedure over a single list.

```
(define map1
(lambda (p ls)
(if (null? ls)
'()
(cons (p (car ls))
(map1 p (cdr ls))
)
)
)
)
(map1 abs '(1 -2 3 -4 5 -6))
```

### Section 2.9. Assignment

Although many programs can be written without them, assignments to top-level variables or `let`

-bound and `lambda`

-bound variables are sometimes useful. Assignments do not create new bindings, as with `let`

or `lambda`

, but rather change the values of existing bindings. Assignments are performed with `set!`

.

```
(define abcde '(a b c d e))
abcde => (a b c d e)
(set! abcde (cdr abcde))
abcde => (b c d e)
(let ((abcde '(a b c d e)))
(set! abcde (reverse abcde))
abcde
) => (e d c b a)
```

Many languages require the use of assignments to initialize local variables, separate from the declaration or binding of the variables. In Scheme, all local variables are given a value immediately upon binding. Besides making the separate assignment to initialize local variables unnecessary, it ensures that the programmer cannot forget to initialize them, a common source of errors in most languages.

In fact, most of the assignments that are either necessary or convenient in other languages are both unnecessary and inconvenient in Scheme, since there is typically a clearer way to express the same algorithm without assignments. One common practice in some languages is to sequence expression evaluation with a series of assignments, as in the following procedure that finds the roots of a quadratic equation.

```
(define quadratic-formula
(lambda (a b c)
(let ((root1 0) (root2 0) (minusb 0) (radical 0) (divisor 0))
(set! minusb (- 0 b))
(set! radical (sqrt (- (* b b) (* 4 (* a c)))))
(set! divisor (* 2 a))
(set! root1 (/ (+ minusb radical) divisor))
(set! root2 (/ (- minusb radical) divisor))
(cons root1 root2))))
```

The definition above works, but it can be written more clearly without the assignments, as shown below.

```
(define quadratic-formula2
(lambda (a b c)
(let ( (minusb (- 0 b))
(radical (sqrt (- (* b b) (* 4 (* a c)))))
(divisor (* 2 a)))
(let ((root1 (/ (+ minusb radical) divisor))
(root2 (/ (- minusb radical) divisor)))
(cons root1 root2)))))
```

Assignments do have some uses in Scheme, otherwise the language would not support them. Consider the following version of `cons`

that counts the number of times it is called, storing the count in a variable named *cons-count*. It uses `set!`

to increment the count; there is no way to achieve the same behavior without assignments.

```
(define kons-count 0)
(define kons
(lambda (x y)
(set! kons-count (+ kons-count 1))
(cons x y)))
(kons 'a '(b c)) => (a b c)
kons-count => 1
(kons 'a (kons 'b (kons 'c '()))) => (a b c)
kons-count => 4
```

Another solution also generalizes easily to provide multiple counters, each with its own local counter. The procedure *make-counter*, defined below, returns a new counting procedure each time it is called.

```
(define make-counter
(lambda ()
(let ((next 0))
(lambda ()
(let ((v next))
(set! next (+ next 1))
v)))))
(define counter1 (make-counter))
(define counter2 (make-counter))
```

If a state variable must be shared by more than one procedure defined at top level, but we do not want the state variable to be visible at top level, we can use let to bind the variable and set! to make the procedures visible at top level.

```
(define shhh #f)
(define tell #f)
(let ((secret 0))
(set! shhh
(lambda (message)
(set! secret message)))
(set! tell
(lambda ()
secret)))
(shhh "hello world")
(tell) => "hello world"
```

Variables must be defined before they can be assigned, so we define shhh and tell to be #f initially. (Any initial value would do.)

Local state is sometimes useful for caching computed values or allowing a computation to be evaluated lazily, i.e., only once and only on demand.

```
(define lazy
(lambda (t)
(let ((val #f) (flag #f))
(lambda ()
(if (not flag)
(begin (set! val (t))
(set! flag #t)
)
)
val
)
)
)
)
```

The syntactic form `begin`

, used here for the first time, evaluates its subexpressions in sequence from left to right and returns the value of the last subexpression, like the body of a `let`

or `lambda`

expression. We also see that the alternative subexpression of an `if`

expression can be omitted. This should be done only when the value of the `if`

is discarded, as it is in this case.

The operation of *lazy* can best be illustrated by printing a message from within a procedure passed to *lazy*.

```
(define p
(lazy (lambda ()
(display "Ouch!")
(newline)
"got me"
)
)
)
```

The first time *p* is invoked, the message *Ouch!* is printed and the string "got me" is returned. Thereafter, "got me" is returned but the message is not printed. The procedures `display`

and `newline`

are the first examples of explicit input/output we have seen; `display`

prints the string without quotation marks, and `newline`

prints a newline character.

To further illustrate the use of `set!`

, let's consider the implementation of stack objects whose internal workings are not visible on the outside. A stack object accepts one of four messages: `empty?`

, which returns `#t`

if the stack is empty; `push!`

, which adds an object to the top of the stack; `top`

, which returns the object on the top of the stack; and `pop!`

, which removes the object on top of the stack.

```
(define make-stack
(lambda ()
(let ((ls '()))
(lambda (msg . args)
(cond
((eqv? msg 'empty?) (null? ls))
((eqv? msg 'push!) (set! ls (cons (car args) ls)))
((eqv? msg 'top) (car ls))
((eqv? msg 'pop!) (set! ls (cdr ls)))
(else "oops")
)
)
)
)
)
(define stack1 (make-stack))
(define stack2 (make-stack))
(list (stack1 'empty?) (stack2 'empty?))
(stack1 'push! 'a)
(list (stack1 'empty?) (stack2 'empty?))
(stack1 'push! 'b)
(stack2 'push! 'c)
(stack1 'top)
(stack2 'top)
(stack1 'pop!)
(stack1 'top)
(list (stack1 'empty?) (stack2 'empty?))
```

As with the counters created by *make-counter*, the state maintained by each stack object is directly accessible only within the object. Each reference or change to this state is made explicitly by the object itself. One important benefit is that we can change the internal structure of the stack, perhaps to use a vector (see Section 6.9) instead of a list to hold the elements, without changing its external behavior. Because the behavior of the object is known abstractly (not operationally), it is known as an *abstract object*. See

Section 12.8 for more about creating abstract objects.

In addition to changing the values of variables, we can also change the values of the `car`

and `cdr`

fields of a pair, using the procedures `set-car!`

and `set-cdr!`

.

```
(define p (list 1 2 3))
(set-car! (cdr p) 'two)
p
(set-cdr! p '())
p
```

We can use these operators to define a queue data type, which is like a stack except that new elements are added at one end and extracted from the other. The following queue implementation uses a *tconc* structure. A *tconc* consists of a nonempty list and a header. The header is a pair whose `car`

points to the first pair (head) of the list and whose `cdr`

points to the last pair (end) of the list.

The last element of the list is a placeholder and not considered part of the queue.

Four operations on queues are defined below: *make-queue*, which constructs a queue; *putq!*, which adds an element to the end of a queue; *getq*, which retrieves the element at the front of a queue; and *delq!*, which removes the element at the front of a queue.

```
(define make-queue
(lambda ()
(let ((end (cons 'ignored '())))
(cons end end)
)
)
)
(define putq!
(lambda (q v)
(let ((end (cons 'ignored '())))
(set-car! (cdr q) v)
(set-cdr! (cdr q) end)
(set-cdr! q end)
)
)
)
(define getq
(lambda (q)
(car (car q))
)
)
(define delq!
(lambda (q)
(set-car! q (cdr (car q)))
)
)
```

All are simple operations except for *putq!*, which modifies the end pair to contain the new value and adds a new end pair.

```
(define myq (make-queue))
(putq! myq 'a)
(putq! myq 'b)
(getq myq) => a
(delq! myq)
(getq myq) => b
(delq! myq)
(putq! myq 'c)
(putq! myq 'd)
(getq myq) => c
(delq! myq)
(getq myq) => d
```