# **Epilogue**

Serious engineering is only a few thousand years old. Our attempts at deliberately producing very complex robust systems are immature at best. We have yet to glean the lessons that biological evolution has learned over the last few billion years.

We have been more concerned with efficiency and correctness than with the kind of robustness of biological systems that comes from optimizing evolvability, flexibility, and resistance to attack. This is sensible for developing mission-critical systems that have barely enough resources to perform their function. However, the rapid advance of microelectronics has alleviated the resource problem for most applications. Our increasing dependence on computational and communications infrastructure, and the development of ever more sophisticated attacks on that infrastructure, make it imperative that we turn our attention to robustness.

We are not advocating biomimetics; but observations of biological systems give us hints about how to incorporate powerful principles of robustness into our engineering practice. Many of these principles are in direct conflict with the established practices of optimization of efficiency and of the ability to prove correctness. In this book we deliberately violate these established practices to explore the possibilities of optimizing for flexibility. A motivation of our approach is the observation that most systems that have survived the test of time are built as an assembly of domain-specific languages, each of which is appropriate to make some parts of the system easy to construct.

As part of the effort to build artificially intelligent symbolic systems, the AI community has incidentally developed technological tools that can be used to support principles of flexible and robust design. For example, rather than thinking of backtracking as a method of organizing search, we can employ it to increase the general applicability of components in a complex system that organizes itself to meet externally imposed constraints. We believe that by pursuing this new synthesis we will obtain better hardware and software systems.

We started out in chapter 2 with some rather unobjectionable techniques that are universally applicable. We introduced the strategy of building systems of combinators—libraries of parametric parts that have standardized interfaces. Such parts can be combined in many ways to meet a great variety of needs. We demonstrated how this idea can be used to simplify the construction of a language of regular-expression matchers. We introduced systems of wrappers that allow us to adapt parts to applications with different standards than the parts were built to, and we used this to make a language of unit-conversion wrappers. We progressed to build a rule interpreter for a language to express the rules of board games like checkers.

In chapter 3 we embarked on an exciting and dangerous adventure: we investigated what can be done if we are allowed to modulate the meanings of the primitive procedures of a language. We extended arithmetic to handle symbolic expressions and functions, as well as numbers. We created extensible generic procedures and used the extension mechanism to integrate forwardmode automatic differentiation into our arithmetic. This kind of extension is dangerous, but if we are careful, we can make old programs have new abilities without losing their old abilities. To make this strategy efficient and even more powerful, we proceeded to explore user-defined types, with declarable subtype relationships, and we used that to make a simple but easily extensible adventure game.

Pattern matching and pattern-directed invocation, introduced in chapter 4, are crucial techniques for erecting domain-specific languages. We started with term-rewriting rules for algebraic

simplification. We then showed an elegant strategy for compiling patterns into a composition of elementary pattern matchers in a system of pattern-matching combinators. We then expanded our pattern-matching tools to allow pattern variables on both sides of a match, implementing unification, which we then used to make an elementary type-inference system. Finally, we built matchers that match arbitrary graphs, not just expression trees, and used graphs and graph matching to express the rules for moves in chess in an elegant manner.

Because all sane computer languages are universal, programmers do not have an excuse that a solution cannot be expressed in some language. If seriously pressed, good programmers can make an interpreter or compiler for any language they please in any language they are stuck with. This is not very hard, but it is probably the most powerful move a programmer can make. In chapter 5 we showed how to make increasingly powerful languages by interpretation and compilation. We started with a simple applicative-order interpreter for a Scheme-like language. For extensibility, the interpreter was built on generic procedures. We then extended it to allow procedure definitions to declare lazy formal parameters. Next we compiled the language to a combination of execution procedures—a system of combinators. We then added a model of nondeterministic evaluation, with the amb operator. Finally, we showed how by exposing the underlying continuations we could arrange to get the power of amb in the underlying Scheme system. In chapter 6 we began to explore multilayer computations, based on a novel mechanism closely related to generic procedures. For example, we modified our arithmetic so that a program that computes numerical results from numerical arguments could be extended, without modification, to compute the same results, augmented with units. The units of the result are automatically derived from the units of the inputs, and combinations are checked for consistent units: adding 5 kilograms to 2 meters will signal an error. We used the same layering mechanism to augment programs to carry dependencies, so that a result automatically has reference to the sources of the ingredients that went into making that result.

The propagator model of chapter 7 is really a way of thinking about the plumbing of large systems. Although, in the examples we show in this chapter, the propagators are all simple arithmetic functions or relations, the idea is far more general. A propagator could be hardware or software. It could be a simple function or a huge computer doing an enormous crunch. If it is software, it could be written in any language. Indeed, a system of propagators does not have to be homogeneous. Different propagators may be constructed differently. Cells may be specialized to hold different kinds of information and they may merge information in their own favorite way. The communication between propagators and cells may be signals on a chip or on a global network. All that matters is the protocol for a propagator to query a cell and to add information to a cell.

In this book we introduced many programming ideas. It is now up to you to evaluate them and perhaps apply them.

# **A**

# **Appendix: Supporting Software**

All of the code shown in this book and the infrastructure code that supports it can be downloaded as an archive file from <http://groups.csail.mit.edu/mac/users/gjs/sdf.tgz>

The archive is organized as a directory tree, where each subdirectory approximately corresponds with a section of this book. The software runs in MIT/GNU Scheme version 10.1.10 or later, which can be obtained from <http://www.gnu.org/software/mit-scheme>

The software uses a number of features specific to the MIT/GNU implementation, so it won't work with other distributions. It should be possible to port it to another distribution, but we have not tried this and it is likely to require some work. Because this is free software (licensed under the GPL) you may modify it and distribute it to others.

The software archive is a tar file called sdf.tgz, which can be unpacked using the command

```
tar xf .../sdf.tgz
```

This tar command produces a directory sdf in whatever directory the tar command is executed in.

The primary interface to the software archive is a management program, which is distributed with the archive. To use this program, start MIT/GNU Scheme and load it like this:

```
(load ".../sdf/manager/load")
```

where .../ refers to the directory in which the archive was unpacked. The manager creates a single definition in the global

environment, called manage. Once loaded, it's not necessary to reload the manager unless a new instance of Scheme is started.

Suppose you are working on section 4.2 "Term rewriting," and you'd like to play with the software or work on an exercise. The loader for code in that section is stored in the subdirectory .../sdf/term-rewriting, along with files that are specific to that section. But you do not need to know how the loader works. (Of course, you may read the manager code. It is pretty interesting.)

The manage command

```
(manage 'new-environment 'term-rewriting)
```

will create a new top-level environment, load all of the necessary files for that section, and move the read-eval-print loop into that environment. After you are done with that section, you can use the manage command to load the software for another section by replacing term-rewriting with the name corresponding to the new section.

Usually, the name of a subdirectory can be used as an argument to (manage 'new-environment ...). When used in this context, the subdirectory name is called a *flavor*. However, some of the subdirectories have multiple flavors, and in those cases the available flavor names differ from the subdirectory names.

The correspondence between sections of the book and subdirectories/flavors in the archive can be found in the file

```
.../sdf/manager/sections.scm
```

In addition, there are two special subdirectories: common holds shared files that are used extensively; and manager holds the implementation of manage.

The software management program manage has many other useful abilities. Among them are managing working environments by name, finding the files that define a name and those that refer to it, and running unit tests. For more information refer to the documentation that is included in the manager subdirectory.

Using the software may require additional steps that are not spelled out in the book text, such as initialization. Every subdirectory contains tests: any file named test-*FOO*.scm is a "standard" test, using a testing framework similar to those of other programming languages. Additionally, the load-spec files in each subdirectory may contain references to tests, marked with the inline-test? symbol, that use a different testing framework that is similar to read-eval-print loop transcripts. Look there for examples of how to run the programs.

# **Appendix: Scheme**

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary. Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.

*IEEE Standard for the Scheme Programming Language* [61], p. 3

Here we give an elementary introduction to the Scheme dialect of Lisp. For a longer introduction see the textbook *Structure and Interpretation of Computer Programs (SICP)* [1].

For a more precise explanation of the language see the IEEE standard [61] and the Seventh *Revised Report on the Algorithmic Language Scheme (R7RS)* [109]

Some of the programs in this book depend on nonstandard features in MIT/GNU Scheme; for documentation of this system see the *MIT/GNU Scheme Reference Manual* [51]. Also, for Scheme features that are documented elsewhere the index to the Reference Manual provides pointers to the appropriate documents.

# **B.1 Essential Scheme**

Scheme is a simple programming language based on expressions. An expression names a value. For example, the numeral 3.14 names an approximation to a familiar number, and the numeral 22/7 names another approximation to it. There are primitive expressions, such as numerals, that we directly recognize, and there are compound expressions of several kinds.

Compound expressions are delimited by parentheses. Those that start with distinguished keywords, such as if, are called *special forms*. Those that are not special forms, called *combinations*, denote applications of procedures to arguments.

### **Combinations**

A *combination*—also called a *procedure application*—is a sequence of expressions delimited by parentheses:

```
(operator operand-1 ... operand-n)
```

The first subexpression in a combination, called the *operator*, is taken to name a procedure, and the rest of the subexpressions, called the *operands*, are taken to name the arguments to that procedure. The value returned by the procedure when applied to the given arguments is the value named by the combination. For example,

```
(+ 1 2.14)
3.14
(+ 1 (* 2 1.07))
3.14
```

<span id="page-8-0"></span>are both combinations that name the same number as the numeral 3.14. [1](#page-26-0) In these cases the symbols + and \* name procedures that add and multiply, respectively. If we replace any subexpression of any expression with an expression that names the same thing as the

original subexpression, the thing named by the overall expression remains unchanged.

Note that in Scheme every parenthesis is essential: you cannot add extra parentheses or remove any.

### **Lambda expressions**

<span id="page-9-0"></span>Just as we use numerals to name numbers, we use lambda expressions to name procedures. [2](#page-26-1) For example, the procedure that squares its input can be written:

```
(lambda (x) (* x x))
```

This expression can be read: "The procedure of one argument, *x*, that multiplies *x* by *x*." Of course, we can use this expression in any context where a procedure is needed. For example,

```
((lambda (x) (* x x)) 4)
16
```

The general form of a lambda expression is

```
(lambda formal-parameters body)
```

where *formal-parameters* is (usually) a parenthesized list of symbols that will be the names of the formal parameters of the procedure. When the procedure is applied to arguments, the formal parameters will have the arguments as their values. The *body* is an expression that may refer to the formal parameters. The value of a procedure application is the value of the body of the procedure with the arguments substituted for the formal parameters. [3](#page-27-0)

<span id="page-9-1"></span>In the example shown above, the symbol x is the only formal parameter of the procedure named by (lambda (x) (\* x x)). That procedure is applied to the value of the numeral 4, so in the body, (\* x x), the symbol x has the value 4, and the value of the combination ((lambda (x) (\* x x)) 4) is 16.

We said "usually" above because there are exceptions. Some procedures, such as the procedure that multiplies numbers, named

by the symbol \*, can take an indefinite number of arguments. We will explain how to do that later (on page 389).

### **Definitions**

We can use the define special form to give a name to any object. We say that the name identifies a *variable* whose value is the object. For example, if we make the definitions

```
(define pi 3.141592653589793)
(define square (lambda (x) (* x x)))
```

we can then use the symbols pi and square wherever the numeral or the lambda expression could appear. For example, the area of the surface of a sphere of radius 5 is

```
(* 4 pi (square 5))
314.1592653589793
```

Procedure definitions may be expressed more conveniently using "syntactic sugar." The squaring procedure may be defined

```
(define (square x) (* x x))
```

which we may read: "To square *x* multiply *x* by *x*."

In Scheme, procedures are *first-class* objects: they may be passed as arguments, returned as values, and incorporated into data structures. For example, it is possible to make a procedure that implements the mathematical notion of the composition of two functions: [4](#page-27-1)

```
(define compose
  (lambda (f g)
    (lambda (x)
      (f (g x)))))
((compose square sin) 2)
.826821810431806
(square (sin 2))
.826821810431806
```

One thing to notice is that the values of f and g in the returned procedure, (lambda (x) (f (g x))), are the values of the formal parameters of the outer procedure, (lambda (f g) ...). This is the essence of the lexical scoping discipline of Scheme. The value of any variable is obtained by finding its binding in the lexically apparent context. There is an implicit context for all the variables defined globally by the system. (For example, + is globally bound by the system to the procedure that adds numbers.)

Using the syntactic sugar shown above for square, we can write the definition of compose more conveniently:

```
(define (compose f g)
  (lambda (x)
    (f (g x))))
```

In MIT/GNU Scheme we can use the sugar recursively, to write:

```
(define ((compose f g) x)
  (f (g x)))
```

Sometimes it is advantageous to make a definition local to another definition. For example, we may define compose as follows:

```
(define (compose f g)
  (define (fog x)
    (f (g x)))
  fog)
```

The name fog is not defined outside the definition of compose, so it is not particularly useful in this case, but larger chunks of code are often easier to read if internal pieces are given names. Internal definitions must always precede any expressions that are not definitions in the body of the procedure.

### **Conditionals**

Conditional expressions may be used to choose among several expressions to produce a value. For example, a procedure that implements the absolute value function may be written:

```
(define (abs x)
  (cond ((< x 0) (- x))
        ((= x 0) x)
        ((> x 0) x)))
```

The conditional cond takes a number of *clauses*. Each clause has a *predicate expression*, which may be either true or false, and a *consequent expression*. The value of the cond expression is the value of the consequent expression of the first clause for which the corresponding predicate expression is true. The general form of a conditional expression is

```
(cond (predicate-1 consequent-1)
      ...
      (prredicate-n consequent-n))
```

For convenience there is a special keyword else that can be used as the predicate in the last clause of a cond.

The if special form provides another way to make a conditional when there is only a binary choice to be made. For example, because we have to do something special only when the argument is negative, we could have defined abs as:

```
(define (abs x)
  (if (< x 0)
      (- x)
      x))
```

The general form of an if expression is

```
(if predicate consequent alternative)
```

If the *predicate* is true the value of the if expression is the value of the *consequent*, otherwise it is the value of the *alternative*.

# **Recursive procedures**

Given conditionals and definitions, we can write recursive procedures. For example, to compute the *n*th factorial number we may write:

```
(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))
(factorial 6)
720
(factorial 40)
815915283247897734345611269596115894272000000000
```

### **Local names**

A let expression is used to give names to objects in a local context. For example,

```
(define (f radius)
  (let ((area (* 4 pi (square radius)))
        (volume (* 4/3 pi (cube radius))))
    (/ volume area)))
(f 3)
1
```

The general form of a let expression is

```
(let ((variable-1 expression-1)
      ...
      (variable-n expression-n))
  body)
```

The value of the let expression is the value of the *body* expression in the context where the variables *variable-i* have the values of the expressions *expression-i*. The expressions *expression-i* may not refer to any of the variables *variable-j* given values in the let expression.

A let\* expression is the same as a let expression except that an expression *expression-i* may refer to variables *variable-j* given values earlier in the let\* expression.

A slight variant of the let expression provides a convenient way to write a loop. We can write a procedure that implements an alternative algorithm for computing factorials as follows:

```
(define (factorial n)
  (let factlp ((count 1) (answer 1))
    (if (> count n)
        answer
        (factlp (+ count 1) (* count answer)))))
(factorial 6)
720
```

Here, the symbol factlp following the let is locally defined to be a procedure that has the variables count and answer as its formal parameters. It is called the first time with 1 and 1 as arguments, initializing the loop. Whenever the procedure named factlp is called later, these variables get new values that are the values of the operand expressions (+ count 1) and (\* count answer).

An equivalent way to express this procedure has an explicitly defined internal procedure:

```
(define (factorial n)
  (define (factlp count answer)
    (if (> count n)
        answer
        (factlp (+ count 1) (* count answer))))
  (factlp 1 1))
```

The procedure factlp is defined locally; it exists only in the body of factorial. Because factlp is lexically enclosed in the definition of factorial, the value of n in its body is the value of the formal parameter of factorial.

## **Compound data—lists, vectors, and records**

Data can be glued together to form compound data structures. A *list* is a data structure in which the elements are linked sequentially. A *vector* is a data structure in which the elements are packed in a linear array. New elements can be added to lists, but to access the *n*th element of a list takes computing time proportional to *n*. By contrast, a vector is of fixed length, and its elements can be accessed in constant time. A *record* is similar to a vector, except that its fields are addressed by names rather than index numbers. Records also

provide new data types, which are distinguishable by type predicates and are guaranteed to be different from other types.

Compound data objects are constructed from components by procedures called *constructors* and the components are accessed by *selectors*.

<span id="page-15-0"></span>The procedure list is the constructor for lists. The predicate list? is true of any list, and false of all other types of data. [5](#page-27-2) For example,

```
(define a-list (list 6 946 8 356 12 620))
a-list
(6 946 8 356 12 620)
(list? a-list)
#t
(list? 3)
#f
```

Here #t and #f are the printed representations of the boolean values true and false. [6](#page-27-3)

<span id="page-15-1"></span>Lists are built from pairs. A *pair* is made using the constructor cons. The selectors for the two components of the pair are car and cdr (pronounced "could-er"). [7](#page-27-4)

```
(define a-pair (cons 1 2))
a-pair
(1 . 2)
(car a-pair)
1
(cdr a-pair)
2
```

A list is a chain of pairs, such that the car of each pair is the list element and the cdr of each pair is the next pair, except for the last cdr, which is a distinguishable value called the empty list and written (). Thus,

```
(car a-list)
6
(cdr a-list)
(946 8 356 12 620)
(car (cdr a-list))
946
(define another-list
  (cons 32 (cdr a-list)))
another-list
(32 946 8 356 12 620)
(car (cdr another-list))
946
```

The lists a-list and another-list share their tail (their cdr).

The predicate pair? is true of pairs and false of all other types of data. The predicate null? is true only of the empty list.

Vectors are simpler than lists. There is a constructor vector that can be used to make vectors and a selector vector-ref for accessing the elements of a vector. In Scheme all selectors that use a numerical index are zero-based:

```
(define a-vector
  (vector 37 63 49 21 88 56))
a-vector
#(37 63 49 21 88 56)
(vector-ref a-vector 3)
21
(vector-ref a-vector 0)
37
```

The printed representation of a vector is distinguished from the printed representation of a list by the character # before the initial parenthesis.

There is a predicate vector? that is true of vectors and false for all other types of data.

Scheme provides a numerical selector for the elements of a list, list-ref, analogous to the selector for vectors:

```
(list-ref a-list 3)
356
(list-ref a-list 0)
6
```

Records are more involved, as they must be declared before they can be constructed. A simple record declaration might be

```
(define-record-type point
    (make-point x y)
    point?
  (x point-x)
  (y point-y))
```

After this declaration, we can make and use points:

```
(define p (make-point 1 2))
(point? p)
#t
(point-x p)
1
(point-y p)
2
```

The elements of lists, vectors, and records may be any kind of data, including numbers, procedures, lists, vectors, and records. Numerous other procedures for manipulating lists, vectors, and records can be found in the Scheme online documentation.

## **Procedures with an indefinite number of arguments**

The procedures that we have seen are specified with a list of formal parameters that are bound to the arguments that the procedure is called with. However, there are many procedures that take an indefinite number of arguments. For example, the arithmetic procedure that multiplies numbers can take any number of

arguments. To define such a procedure we specify the formal parameters as a single symbol rather than a list of symbols. The single symbol is then bound to a list of the arguments that the procedure is called with. For example, given a binary multiplier \*:binary we can write

```
(define * (lambda args (accumulate *:binary 1 args)))
where accumulate is just
(define (accumulate proc initial lst)
  (if (null? lst)
      initial
      (proc (car lst)
            (accumulate proc initial (cdr lst)))))
```

Sometimes we want a procedure that takes some named arguments and an indefinite number of others. In a procedure definition a parameter list that has a dot before the last parameter name (called *dotted-tail notation*) indicates that the parameters before the dot will be bound to the initial arguments, and the final parameter will be bound to a list of any remaining arguments. In the example of \* above there are no initial arguments, so the value of args is a list of all the arguments. Thus, alternatively, we could define \* as:

```
(define (* . args) (accumulate *:binary 1 args))
```

The procedure named by - is more interesting, as it requires at least one argument: when given one argument - negates it; when given more than one argument it subtracts the rest from the first:

```
(define (- x . ys)
 (if (null? ys) ; Only one argument?
     (-:unary x)
     (-:binary x (accumulate +:binary 0 ys))))
```

### This can also be written

```
(define -
  (lambda (x . ys)
    (if (null? ys)
```

```
(-:unary x)
(-:binary x (accumulate +:binary 0 ys)))))
```

Parameters like args and ys in the examples above are called *rest parameters* because they are bound to the rest of the arguments.

## **Symbols**

Symbols are a very important kind of primitive data type that we use to make programs and algebraic expressions. You probably have noticed that Scheme programs look just like lists. In fact, they *are* lists. Some of the elements of the lists that make up programs are symbols, such as + and vector. [8](#page-27-5)

<span id="page-19-0"></span>If we are to make programs that can manipulate programs, we need to be able to write an expression that names such a symbol. This is accomplished by the mechanism of *quotation*. The name of the symbol + is the expression '+, and in general the name of an expression is the expression preceded by a single quote character. Thus the name of the expression (+ 3 a) is '(+ 3 a).

We can test if two symbols are identical by using the predicate eq?. For example, we can write a program to determine if an expression is a sum:

```
(define (sum? expression)
  (and (pair? expression)
       (eq? (car expression) '+)))
(sum? '(+ 3 a))
#t
(sum? '(* 3 a))
#f
```

Consider what would happen if we left out the quote in the expression (sum? '(+ 3 a)). If the variable a had the value 4, we would be asking if 7 is a sum. But what we wanted to know was whether the expression (+ 3 a) is a sum. That is why we need the quote.

## **Backquote**

To manipulate patterns and other forms of list-based syntax, it is often useful to intersperse quoted and evaluated parts in the same expression. Lisp systems provide a mechanism called *quasiquotation* that makes this easy.

<span id="page-20-0"></span>Just as we use the apostrophe character to indicate regular quotation, we use the backquote character to indicate quasiquotation. [9](#page-27-6) We specify such a partially quoted expression as a list in which the parts to be evaluated are prefixed with the comma character. For example,

```
'(a b ,(+ 20 3) d)
(a b 23 d)
```

The backquote mechanism also provides for "splicing" into a list expression: an evaluated subexpression produces a list, which is then spliced into the enclosing list. For example,

```
'(a b ,@(list (+ 20 3) (- 20 3)) d)
(a b 23 17 d)
```

Consult the Scheme Report [109] for a more detailed explanation of quasiquotation.

## **Effects**

<span id="page-20-1"></span>Sometimes we need to perform an action, such as plotting a point or printing a value, in the process of a computation. Such an action is called an *effect*. [10](#page-27-7) For example, to see in more detail how the factorial program computes its answer, we can interpolate a writeline statement in the body of the factlp internal procedure to print a list of the count and the answer for each iteration:

```
(define (factorial n)
  (let factlp ((count 1) (answer 1))
    (write-line (list count answer))
    (if (> count n)
```

```
answer
(factlp (+ count 1) (* count answer)))))
```

When we call the modified factorial procedure we can watch the counter being incremented and the answer being built:

```
(factorial 6)
(1 1)
(2 1)
(3 2)
(4 6)
(5 24)
(6 120)
(7 720)
720
```

The body of every procedure or let, as well as the consequent of every cond clause, allows statements that have effects to be used. The effect statement generally has no useful value. The final expression in the body or clause produces the value that is returned. In this example the if expression produces the value of the factorial.

# **Assignments**

Effects like printing a value or plotting a point are pretty benign, but there are more powerful (and thus dangerous) effects, called *assignments*. An assignment *changes* the value of a variable or an entry in a data structure. Almost everything we are computing is a mathematical function: for a particular input it always produces the same result. However, with assignment we can make objects that change their behavior as they are used. For example, we can use set! to make a device that increments a count every time we call it: [11](#page-28-0)

```
(define (make-counter)
  (let ((count 0))
    (lambda ()
      (set! count (+ count 1))
      count)))
```

## Let's make two counters:

```
(define c1 (make-counter))
(define c2 (make-counter))
```

These two counters have independent local state. Calling a counter causes it to increment its local state variable, count, and return its value.

```
(c1)
1
(c1)
2
(c2)
1
(c1)
3
(c2)
2
```

For assigning to the elements of a data structure, such as a pair, a list, or a vector, Scheme provides:

```
(set-car! pair new-value)
(set-cdr! pair new-value)
(list-set! list index new-value)
(vector-set! vector index new-value)
```

A record may be defined to allow assignments to its fields (compare page 388:

```
(define-record-type point
    (make-point x y)
    point?
  (x point-x set-x!)
  (y point-y set-y!))
(define p (make-point 1 2))
(point-x p)
```

```
1
(point-y p)
2
(set-x! p 3)
(point-x p)
3
(point-y p)
2
```

<span id="page-23-0"></span>In general, it is good practice to avoid assignments when possible, but if you need them they are available. [12](#page-28-1)

# **B.2 More advanced stuff**

Scheme provides many more powerful features, but we won't try to describe them here. For example, you will probably want to know about hash tables. In general, the best sources are the

*Revised Report on the Algorithmic Language Scheme (R7RS)* [109] and the *MIT/GNU Scheme Reference Manual* [51]. But here are two fairly complex features that you may need to reference while reading this book:

### **Dynamic binding**

We sometimes want to specify the way in which some evaluation or action will be accomplished—for example, to specify the radix to use when printing a number. To do this we use an object called a *parameter*.

For example, the Scheme procedure number->string produces a character string that represents a number in a given radix:

```
(number->string 100 2)
"1100100"
(number->string 100 16)
"64"
```

Suppose we want to use number->string in many places in a complex program that we run by calling myprog, but we want to be able to control the radix used when the program is run. We can accomplish this by making a parameter radix with the default value 10:

```
(define radix (make-parameter 10))
```

The value of a parameter is obtained by calling the parameter with no arguments:

```
(radix)
10
```

We define a specialized version of number->string to use instead of number->string:

```
(define (number->string-radix number)
  (number->string number (radix)))
```

In an execution of (myprog), every call to number->string-radix will produce a decimal string, because the default value of (radix) is 10. However, we can wrap our program with parameterize to change the execution to use another radix:

```
(parameterize ((radix 2))
  (myprog))
```

The syntax of parameterize is the same as the syntax of let, but it can be used only for parameters created by make-parameter.

### **Bundles**

MIT/GNU Scheme provides a simple mechanism for building a collection of related procedures with shared state: a *bundle*. A bundle is a procedure that delegates to a collection of named procedures: the first argument to the bundle is the name of the delegate to use, and the rest of the arguments are passed to the specified delegate. This is similar to the way that some objectoriented languages work, but much simpler, and without classes or inheritance.

A bundle is sometimes called a *message-accepting procedure*, where the message type is the delegate name and the message body is the arguments. [13](#page-28-2) This emphasizes that the bundle supports a message-passing protocol and can be thought of as a node in a communications network.

<span id="page-25-0"></span>Here is a simple example:

```
(define (make-point x y)
  (define (get-x) x)
  (define (get-y) y)
  (define (set-x! new-x) (set! x new-x))
  (define (set-y! new-y) (set! y new-y))
  (bundle point? get-x get-y set-x! set-y!))
```

The procedure make-point defines four internal procedures, which share the state variables x and y. The bundle macro creates a bundle procedure, for which those procedures are the delegates.

The first argument to the bundle macro is a predicate, which is created with make-bundle-predicate. The bundle that is created will satisfy this predicate:

```
(define point? (make-bundle-predicate 'point))
(define p1 (make-point 3 4))
(define p2 (make-point -1 1))
(point? p1)
#t
(point? p2)
#t
(point? (lambda (x) x))
#f
```

The argument to make-bundle-predicate is a symbol that is used to identify the predicate when debugging.

If a predicate is not needed, bundle alternatively accepts #f as a first argument. In that case there will be no way to distinguish the created bundle procedure from other procedures.

The remaining arguments to the bundle macro are the names of the delegate procedures: get-x, get-y, set-x!, and set-y!. These names are looked up in the lexical environment of the macro to get the corresponding delegate procedures. A bundle procedure is then created, containing an association from each name to its delegate procedure.

When the resulting bundle procedure is called, its first argument is a symbol that must be the name of one of the delegate procedures. The association is used to select the named delegate procedure, which is then called with the bundle procedure's remaining arguments as its arguments.

It is easier to use a bundle than to describe it:

```
(p1 'get-x)
3
(p1 'get-y)
4
(p2 'get-x)
-1
(p2 'get-y)
1
(p1 'set-x! 5)
(p1 'get-x)
5
(p2 'get-x)
-1
```

- <span id="page-26-0"></span>[1](#page-8-0) In examples we show the value that would be printed by the Scheme system using *slanted* characters following the input expression.
- <span id="page-26-1"></span>[2](#page-9-0) The logician Alonzo Church [16] invented *λ* notation to allow the specification of an anonymous function of a named parameter: *λx*[expression in *x*]. This is read, "That function of one argument whose value is obtained by substituting the argument for *x* in the indicated expression."

- <span id="page-27-0"></span>[3](#page-9-1) We say that the formal parameters are *bound* to the arguments, and the *scope* of the binding is the body of the procedure.
- <span id="page-27-1"></span>[4](#page-10-0) The examples are indented to help with readability. Scheme does not care about extra white space, so we may add as much as we please to make things easier to read.
- <span id="page-27-2"></span>[5](#page-15-0) A *predicate* is a procedure that returns true or false. By Scheme cultural convention, we usually give a predicate a name ending with a question mark (?), except for the elementary arithmetic comparison predicates: =, <, >, <=, and >=. This is just a stylistic convention. To Scheme the question mark is just an ordinary character.
- <span id="page-27-3"></span>[6](#page-15-1) It is convenient, but irritating to some, that the conditional expressions (if and cond) treat any predicate value that is not explicitly #f as true.
- <span id="page-27-4"></span>[7](#page-15-2) These names are accidents of history. They stand for "Contents of the Address part of Register" and "Contents of the Decrement part of Register" of the IBM 704 computer, which was used for the first implementation of Lisp in the late 1950s. Scheme is a dialect of Lisp.
- <span id="page-27-5"></span>[8](#page-19-0) A symbol may have any number of characters. A symbol may not normally contain whitespace or delimiter characters, such as parentheses, brackets, quotation marks, comma, or #; but there are special notations that allow any characters to be included in a symbol's name.
- <span id="page-27-6"></span>[9](#page-20-0) On an American keyboard the backquote character "'" is the lowercase character on the key that has the tilde character "∼" as the uppercase character.
- <span id="page-27-7"></span>[10](#page-20-1) This is computer-science jargon. An effect is a change to something. For example, write-line changes the display by printing something to the display.

- <span id="page-28-0"></span>[11](#page-21-0) It is another cultural convention that we terminate the name of a procedure that has "side effects" with an exclamation point (!). This warns the reader that changing the order of effects may change the results of running the program.
- <span id="page-28-1"></span>[12](#page-23-0) The discipline of programming without assignments is called *functional programming*. Functional programs are generally easier to understand and have fewer bugs than *imperative programs*.
- <span id="page-28-2"></span>[13](#page-25-0) This terminology dates back to the ACTOR framework [58] and the Smalltalk programming language [46].