44e26d6972
- CLAUDE.md 생성 (볼트 운영 규칙, Karpathy LLM Wiki 10가지 규칙) - 나의 핵심 맥락.md 생성 (아키텍트 프로필, 세컨드 브레인 목적, 핵심 소스) - raw/ 구조 정립 (book/기존 설계원칙 보존, articles/repos/notes/ 추가) - wiki/ 초기화 (index.md, log.md, concepts/sources/patterns/ 폴더) - output/ 초기화 - LLMWiki/ 기존 프롬프트 패턴 파일 보존 Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
2219 lines
120 KiB
Markdown
2219 lines
120 KiB
Markdown
# **Evaluation**
|
||
|
||
One of the best ways to attack a problem is to make up a domainspecific language in which the solution is easily expressed. If the language you make up is powerful enough, many problems that are similar to the one you are attacking will have easy-to-express solutions in your language. This strategy is especially effective if you start with a flexible mechanism. We explored this idea in limited contexts in chapters 2, 3, and 4. Here we will pursue this idea in full generality.
|
||
|
||
When we make up a language we must give it meaning. If we want the expressions of the language to describe computational processes, we must build a mechanism that, when given expressions in the language, evolves the desired process. An *interpreter* is just such a mechanism. We will explore this creative realm starting with an extensible version of the applicative order Scheme eval/apply interpreter similar to the ones described in SICP [1], Chapter 4.
|
||
|
||
Scheme procedures are strict, requiring each argument to be evaluated before the body of the procedure is entered. We next generalize our interpreter, adding declarations to the formal parameter list of a procedure. These declarations will allow a procedure to defer evaluation of the corresponding argument to when its value is actually needed, providing for lazy evaluation, with or without memoization of the value. This declaration mechanism can also be used for other information, such as types and units.
|
||
|
||
An interpreter is rather inefficient, because it must analyze the expression to be interpreted in order to know what to do at each step. This effort is repeated each time the interpreter encounters the
|
||
|
||
same expression. So we next separate the interpretation into two phases, analysis and execution. The analysis phase examines the expression and compiles an execution procedure, which when called will perform the intent of the expression. The execution procedure runs without access to the expression it was compiled from. The execution procedures all have the same form, and constitute a system of combinators.
|
||
|
||
We next add McCarthy's amb operator to allow us to do nondeterministic evaluation and search. Remarkably, this requires no change to the analysis part of the evaluator. The only change required is in the format of the execution procedures, which are reexpressed in continuation-passing style. The use of continuationpassing style suggests exposing the underlying continuation to the programmer.
|
||
|
||
The procedure call/cc that exposes the underlying continuation is a standard procedure in Scheme, and it turns out that all we need is call/cc to implement amb directly in Scheme, so we conclude by showing how to do this.
|
||
|
||
## **5.1 Generic eval/apply interpreter**
|
||
|
||
Our first interpreter is constructed to be extensible. All significant parts are generic procedures, and we are careful to avoid unnecessary commitments. Let's start.
|
||
|
||
<span id="page-1-0"></span>The essence of the interpreter is in two procedures: eval and apply. The procedure eval takes an expression and an environment as inputs. The expression is a combination of subexpressions that are syntactically glued together. The environment gives meanings to some of the symbols that appear in the expression. There are other symbols that have meanings that are fixed in the definition of eval. [1](#page-70-0) But most expressions are interpreted as combinations of an *operator* and *operands*. Evaluation of the operator should yield a procedure and evaluation of the operands should yield arguments. The procedure and arguments are then passed to apply. The
|
||
|
||
procedure usually names the arguments with *formal parameters*. The procedure apply evaluates the *body* of the procedure (using eval) in an environment in which the formal parameters of the procedure are *bound* to the arguments. This is the central computational loop of the interpreter.
|
||
|
||
What we just described is the traditional applicative-order interpreter plan. In our interpreter we will pass the unevaluated operands and the environment for their evaluation to apply to make it possible to implement a variety of evaluation strategies, such as normal order as well as applicative order.
|
||
|
||
<span id="page-2-0"></span>The language we will be implementing is a Lisp variant. [2](#page-70-1) This implies that the code is expressed as list structures. In Lisp all compound expressions are lists, some of which start with distinguished keywords. Compound expressions that have distinguished keywords are called *special forms*. The compound expressions that are not special forms are interpreted as applications of procedures to arguments. The implementation will be organized as a set of rules for each expression type, with the exception of applications, which are distinguished by not being special forms. With each rule we give the syntactic definition of the expression type. This strategy can be used to implement almost any language, though a new parser would be needed. With Lisp the reader converts the character-string input into list structures, which are natural representations of the abstract syntax tree (AST) of the language. With other languages the AST is more elaborate and the parser is much more complicated.
|
||
|
||
### **5.1.1 eval**
|
||
|
||
We define g:eval as a generic procedure with two arguments.
|
||
|
||
```
|
||
(define g:eval
|
||
(simple-generic-procedure 'eval 2 default-eval))
|
||
```
|
||
|
||
The default case for eval is an *application* (sometimes described as a *combination*).
|
||
|
||
```
|
||
(define (default-eval expression environment)
|
||
(cond ((application? expression)
|
||
(g:apply (g:advance
|
||
(g:eval (operator expression)
|
||
environment))
|
||
(operands expression)
|
||
environment))
|
||
(else
|
||
(error "Unknown expression type" expression))))
|
||
```
|
||
|
||
In Lisp-based languages the operator of a list representing an application is the first element of the list and the operands are the rest of the elements of the list.
|
||
|
||
```
|
||
(define (application? exp) (pair? exp))
|
||
(define (operator app) (car app))
|
||
(define (operands app) (cdr app))
|
||
```
|
||
|
||
Note how the code above follows the pattern we described on page 235. We are presenting both the interpretation of a particular syntactic construct (application), and the definition of its syntax. Also as we explained there, it is necessary to handle applications as the default case of the generic procedure, because there is no special keyword identifying an application in Lisp—instead it is identified by being a list *not* starting with one of the distinguished keywords.
|
||
|
||
An application first evaluates the operator part of the expression and then passes that value to g:apply along with the operands of the expression and the current environment. However, after evaluating the operator, we pass the value to the generic procedure g:advance. The purpose of g:advance is to continue evaluations that have been postponed. We will not need to postpone evaluations until section 5.2, so until then g:advance is just an identity function: [3](#page-71-0)
|
||
|
||
```
|
||
(define g:advance
|
||
(simple-generic-procedure 'g:advance 1 (lambda (x) x)))
|
||
```
|
||
|
||
This is not the traditional way that apply is defined. By passing along the unevaluated operands and the environment of the application we leave open the option to introduce normal-order evaluation as well as applicative-order evaluation; we also enable
|
||
|
||
the implementation of declarations on the formal parameters, and perhaps some other options.
|
||
|
||
For each non-application expression type we provide a handler. Self-evaluating expressions return themselves:
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args self-evaluating? environment?)
|
||
(lambda (expression environment) expression))
|
||
```
|
||
|
||
In Lisp languages the self-evaluating expressions include the numbers, the boolean values, and strings. In Scheme, number? is a rather complicated predicate. The objects that satisfy number? include integers of arbitrary size, rational fractions, reals, and complex numbers. [4](#page-71-1)
|
||
|
||
```
|
||
(define (self-evaluating? exp)
|
||
(or (number? exp)
|
||
(boolean? exp)
|
||
(string? exp)))
|
||
```
|
||
|
||
There may be other self-evaluating expressions, so to make that option really flexible we could have defined self-evaluating? as a generic procedure. But here this is not necessary, because we could just make another handler for g:eval to define any other selfevaluating expression type that we might want to add.
|
||
|
||
<span id="page-4-1"></span>Quotations are required in languages that allow manipulation of the symbolic expressions of the language. [5](#page-71-2) A quotation is an expression that protects a subexpression from evaluation.
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args quoted? environment?)
|
||
(lambda (expression environment)
|
||
(text-of-quotation expression)))
|
||
```
|
||
|
||
In Lisp-based languages the list-structure representation of a quoted expression is a list beginning with the keyword quote. The reader (parser) for Lisp expands any expression beginning with an apostrophe character (e.g., '(a b c)) into a quoted expression (here (quote (a b c))).
|
||
|
||
```
|
||
(define (quoted? exp) (tagged-list? exp 'quote))
|
||
(define (text-of-quotation quot) (cadr quot))
|
||
```
|
||
|
||
A *tagged list* is just a list beginning with a given unique symbol:
|
||
|
||
```
|
||
(define (tagged-list? e t) (and (pair? e) (eq? (car e) t)))
|
||
```
|
||
|
||
Scheme variables are just looked up in the environment. In other languages there are more complex rules about variables. For example, in C there are *lvalues* and *rvalues*, and they are handled differently.
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args variable? environment?)
|
||
lookup-variable-value)
|
||
```
|
||
|
||
In Lisp-based languages the variables are represented by symbols. [6](#page-71-3)
|
||
|
||
```
|
||
(define (variable? exp) (symbol? exp))
|
||
```
|
||
|
||
<span id="page-5-1"></span>The procedure lookup-variable-value looks up its argument in the given environment. If no value is found for that variable, it looks for a value in the underlying Scheme. [7](#page-71-4) If no value is found, an Unbound variable error is signaled.
|
||
|
||
Binary conditional expressions (*if-then-else*) have a simple handler. If the predicate part of the expression evaluates to a true value, evaluate the consequent part of the expression, otherwise evaluate the alternative part of the expression.
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args if? environment?)
|
||
(lambda (expression environment)
|
||
(if (g:advance
|
||
(g:eval (if-predicate expression) environment))
|
||
(g:eval (if-consequent expression) environment)
|
||
(g:eval (if-alternative expression) environment))))
|
||
```
|
||
|
||
We must call g:advance on the evaluated predicate because we need to know the value to make the decision. Notice that the evaluator for if uses the if construct of the embedding language to do the work!
|
||
|
||
The Lisp syntax for the if expression is simple. If no alternative is specified, the value of the if expression with a false predicate is the value of the global variable the-unspecified-value.
|
||
|
||
```
|
||
(define (if? exp) (tagged-list? exp 'if))
|
||
(define (if-predicate exp) (cadr exp))
|
||
(define (if-consequent exp) (caddr exp))
|
||
(define (if-alternative exp)
|
||
(if (not (null? (cdddr exp)))
|
||
(cadddr exp)
|
||
'the-unspecified-value))
|
||
(define (make-if pred conseq alternative)
|
||
(list 'if pred conseq alternative))
|
||
```
|
||
|
||
The first really interesting special form is the specification of an anonymous procedure, represented by a lambda expression. A lambda expression is a special form, the constructor for procedures. Evaluation of a lambda expression constructs a procedure from the formal parameters, the body, and the current environment. The environment must be carried by the procedure if the variables in the language are lexically scoped. In a lexically scoped language the free variables in the body of the lambda expression (those that are not formal parameters) are given meanings from the lexical context (where the lambda expression appears textually).
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args lambda? environment?)
|
||
(lambda (expression environment)
|
||
(make-compound-procedure
|
||
(lambda-parameters expression)
|
||
(lambda-body expression)
|
||
environment)))
|
||
```
|
||
|
||
### The syntax for lambda expressions is:
|
||
|
||
```
|
||
(define (lambda? exp) (tagged-list? exp 'lambda))
|
||
(define (lambda-parameters lambda-exp) (cadr lambda-exp))
|
||
(define (lambda-body lambda-exp)
|
||
(let ((full-body (cddr lambda-exp)))
|
||
```
|
||
|
||
```
|
||
(sequence->begin full-body)))
|
||
(define (make-lambda parameters body)
|
||
(cons 'lambda
|
||
(cons parameters
|
||
(if (begin? body)
|
||
(begin-actions body)
|
||
(list body)))))
|
||
```
|
||
|
||
Note that the body of a lambda expression may contain several expressions. These are intended to be evaluated in sequence, to allow for side-effecting actions, such as assignment, or I/O control actions, such as printing. This is handled by sequence->begin, which creates a begin special form.
|
||
|
||
```
|
||
(define (sequence->begin seq)
|
||
(cond ((null? seq) seq)
|
||
((null? (cdr seq)) (car seq))
|
||
(else
|
||
(make-begin
|
||
(append-map (lambda (exp)
|
||
(if (begin? exp)
|
||
(begin-actions exp)
|
||
(list exp)))
|
||
seq)))))
|
||
```
|
||
|
||
Notice that the procedure sequence->begin flattens nested begin forms, preserving the order of execution. The syntax and evaluation of begin forms is defined and described on page 242.
|
||
|
||
#### **Derived expression types**
|
||
|
||
<span id="page-7-0"></span>The expression types already introduced are sufficient to conveniently write most programs, but it is often nice to have some syntactic sugar. These can be implemented by transformations of expressions into combinations of simpler ones. Macros are a way to generalize such transformations; but we choose not to build a macro expander as part of our interpreter. [8](#page-71-5) Here we explicitly show how the Lisp multi-armed conditional can be turned into a nest of if expressions:
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args cond? environment?)
|
||
(lambda (expression environment)
|
||
(g:eval (cond->if expression)
|
||
environment)))
|
||
```
|
||
|
||
### The procedure cond->if is a rather simple data manipulation:
|
||
|
||
```
|
||
(define (cond->if cond-exp)
|
||
(define (expand clauses)
|
||
(cond ((null? clauses)
|
||
(error "COND: no values matched"))
|
||
((else-clause? (car clauses))
|
||
(if (null? (cdr clauses))
|
||
(cond-clause-consequent (car clauses))
|
||
(error "COND: ELSE not last"
|
||
cond-exp)))
|
||
(else
|
||
(make-if (cond-clause-predicate (car clauses))
|
||
(cond-clause-consequent (car clauses))
|
||
(expand (cdr clauses))))))
|
||
(expand (cond-clauses cond-exp)))
|
||
```
|
||
|
||
### And here is the syntax for the cond special form:
|
||
|
||
```
|
||
(define (cond? exp) (tagged-list? exp 'cond))
|
||
(define (cond-clauses exp) (cdr exp))
|
||
(define (cond-clause-predicate clause) (car clause))
|
||
(define (cond-clause-consequent clause)
|
||
(sequence->begin (cdr clause)))
|
||
(define (else-clause? clause)
|
||
(eq? (cond-clause-predicate clause) 'else))
|
||
```
|
||
|
||
Because cond allows a sequence of actions for the consequent of a clause, this definition also depends on sequence->begin.
|
||
|
||
Local variables can be introduced with let expressions. These are implemented by translation into a combination with an explicit lambda expression:
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args let? environment?)
|
||
(lambda (expression environment)
|
||
```
|
||
|
||
```
|
||
(g:eval (let->combination expression)
|
||
environment)))
|
||
```
|
||
|
||
### The syntax for let is:
|
||
|
||
```
|
||
(define (let? exp) (tagged-list? exp 'let))
|
||
(define (let-bound-variables let-exp)
|
||
(map car (cadr let-exp)))
|
||
(define (let-bound-values let-exp)
|
||
(map cadr (cadr let-exp)))
|
||
(define (let-body let-exp)
|
||
(sequence->begin (cddr let-exp)))
|
||
(define (let->combination let-exp)
|
||
(let ((names (let-bound-variables let-exp))
|
||
(values (let-bound-values let-exp))
|
||
(body (let-body let-exp)))
|
||
(cons (make-lambda names body)
|
||
values)))
|
||
```
|
||
|
||
### **Effects**
|
||
|
||
If there are operations in the language that have effects, like assignment or printing, they must be sequenced, because the order is essential. In Scheme we syntactically represent such sequences of operations with begin:
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args begin? environment?)
|
||
(lambda (expression environment)
|
||
(evaluate-sequence (begin-actions expression)
|
||
environment)))
|
||
(define (begin? exp) (tagged-list? exp 'begin))
|
||
(define (begin-actions begin-exp) (cdr begin-exp))
|
||
(define (make-begin actions) (cons 'begin actions))
|
||
```
|
||
|
||
#### The real work is actually in the sequence evaluation:
|
||
|
||
```
|
||
(define (evaluate-sequence actions environment)
|
||
(cond ((null? actions)
|
||
(error "Empty sequence"))
|
||
```
|
||
|
||
```
|
||
((null? (cdr actions))
|
||
(g:eval (car actions) environment))
|
||
(else
|
||
(g:eval (car actions) environment)
|
||
(evaluate-sequence (cdr actions)
|
||
environment))))
|
||
```
|
||
|
||
The value returned by evaluating a nonempty sequence of expressions is the value of the last expression in the sequence. But effects caused by executing expressions in the sequence happen in the order of the sequence.
|
||
|
||
Most effects are implemented by assignment of variables. (Indeed, input/output operations are usually implemented in hardware by assignment to particular sensitive locations in the address space.) In Scheme we allow a program to assign to a variable in the lexical environment of the assignment statement:
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args assignment? environment?)
|
||
(lambda (expression environment)
|
||
(set-variable-value! (assignment-variable expression)
|
||
(g:eval (assignment-value
|
||
expression)
|
||
environment)
|
||
environment)))
|
||
```
|
||
|
||
### The syntax for assignment is:
|
||
|
||
```
|
||
(define (assignment? exp) (tagged-list? exp 'set!))
|
||
(define (assignment-variable assn) (cadr assn))
|
||
(define (assignment-value assn) (caddr assn))
|
||
```
|
||
|
||
We also allow definition, the creation of a new variable with a given value. A definition creates a new variable in the most local lexical environment frame of the definition statement.
|
||
|
||
```
|
||
(define-generic-procedure-handler g:eval
|
||
(match-args definition? environment?)
|
||
(lambda (expression environment)
|
||
(define-variable! (definition-variable expression)
|
||
(g:eval (definition-value expression)
|
||
environment)
|
||
environment)
|
||
(definition-variable expression)))
|
||
```
|
||
|
||
<span id="page-11-0"></span>The syntax for definitions is more complicated than the syntax for assignment, because we allow multiple ways to define a procedure: [9](#page-72-0)
|
||
|
||
```
|
||
(define (definition? exp) (tagged-list? exp 'define))
|
||
(define (definition-variable defn)
|
||
(if (variable? (cadr defn)) ; (DEFINE foo ...)
|
||
(cadr defn)
|
||
(caadr defn))) ; (DEFINE (foo ...) ...)
|
||
(define (definition-value defn)
|
||
(if (variable? (cadr defn)) ; (DEFINE foo ...)
|
||
(caddr defn)
|
||
(cons 'lambda ; (DEFINE (foo p...) b...)
|
||
(cons (cdadr defn) ; =(DEFINE foo
|
||
(cddr defn))))) ; (LAMBDA (p...) b...))
|
||
```
|
||
|
||
This completes the usual list of special forms that define the syntax of the language. Of course, the generic procedure implementation enables creation of new special forms easily, allowing the language to grow to make it more convenient to express computational ideas that were not well supported in the base language. But a language with many different syntactic constructs may be difficult to learn, document, and use; this is a classic engineering tradeoff (remember Alan Perlis's maxim on page 159).
|
||
|
||
## **5.1.2 apply**
|
||
|
||
The traditional Scheme apply takes two arguments, the procedure to be applied and the evaluated arguments to be passed to the procedure. This is sufficient for Scheme, because Scheme is a strict applicative-order language with only lexically scoped variables.
|
||
|
||
By generalizing the interface to apply to take three arguments the procedure to be applied, the *un*evaluated operands, and the calling environment—we make it possible to include procedures that require normal-order evaluation for some parameters (e.g., call by need) or procedures that make declarations on parameters, such as types and units. We will make some extensions like these in section 5.2. The environment argument also makes it possible to
|
||
|
||
accommodate non-lexically scoped variables, but we will not do so; it is generally a bad idea. We will start out with Scheme applicative order, with generic hooks for extension.
|
||
|
||
Our apply is a generic procedure with three arguments:
|
||
|
||
```
|
||
(define g:apply
|
||
(simple-generic-procedure 'apply 3 default-apply))
|
||
(define (default-apply procedure operands calling-
|
||
environment)
|
||
(error "Unknown procedure type" procedure))
|
||
```
|
||
|
||
We will need handlers for the various kinds of procedures. Some procedures, like arithmetic addition (usually named by the + operator), are *strict*: they need all of their arguments evaluated before they can compute a value. In Scheme all procedures are strict, including primitive procedures (implemented in the system or hardware below the level of the language). So we need a generic handler for strict primitives:
|
||
|
||
```
|
||
(define-generic-procedure-handler g:apply
|
||
(match-args strict-primitive-procedure?
|
||
operands?
|
||
environment?)
|
||
(lambda (procedure operands calling-environment)
|
||
(apply-primitive-procedure procedure
|
||
(eval-operands operands calling-environment))))
|
||
```
|
||
|
||
The application of a primitive procedure is "magic" at this level of detail. The operands evaluator, like if on page 238, must call g:advance on the result of evaluation to ensure a value.
|
||
|
||
```
|
||
(define (eval-operands operands calling-environment)
|
||
(map (lambda (operand)
|
||
(g:advance (g:eval operand calling-environment)))
|
||
operands))
|
||
```
|
||
|
||
Note that the order of evaluation of the operands is determined by the behavior of map.
|
||
|
||
Procedures constructed by evaluating lambda expressions are not primitive. Here we can take apart the procedure. We can grab the formal parameter specifications, which are the names of the formal
|
||
|
||
parameters. We also can extract the body of the procedure, which we will pass to eval with an environment that includes the formal parameter bindings. For lexical scoping, that extended environment is built on the environment packaged with the procedure by the evaluation of the lambda expression that constructed the procedure.
|
||
|
||
```
|
||
(define-generic-procedure-handler g:apply
|
||
(match-args strict-compound-procedure?
|
||
operands?
|
||
environment?)
|
||
(lambda (procedure operands calling-environment)
|
||
(if (not (n:= (length (procedure-parameters procedure))
|
||
(length operands)))
|
||
(error "Wrong number of operands supplied"))
|
||
(g:eval (procedure-body procedure)
|
||
(extend-environment
|
||
(procedure-parameters procedure)
|
||
(eval-operands operands calling-environment)
|
||
(procedure-environment procedure)))))
|
||
```
|
||
|
||
<span id="page-13-0"></span>Here strict-compound-procedure? is true of all compound procedures that have no declarations on any of their parameters. [10](#page-72-1)
|
||
|
||
#### **Driver loop**
|
||
|
||
To interact with this evaluator we need a read-eval-print loop:
|
||
|
||
```
|
||
(define (repl)
|
||
(check-repl-initialized)
|
||
(let ((input (g:read)))
|
||
(write-line (g:eval input the-global-environment))
|
||
(repl)))
|
||
```
|
||
|
||
Here g:read issues a prompt, eval>, on the terminal. It accepts characters and parses them, converting what it gets into an sexpression. That s-expression is then evaluated with g:eval with respect to the-global-environment and the result is written back to the terminal. The procedure repl calls itself tail recursively. For this to work, the global environment must be initialized:
|
||
|
||
```
|
||
(define the-global-environment
|
||
'not-initialized)
|
||
```
|
||
|
||
```
|
||
(define (initialize-repl!)
|
||
(set! the-global-environment (make-global-environment))
|
||
'done)
|
||
(define (check-repl-initialized)
|
||
(if (eq? the-global-environment 'not-initialized)
|
||
(error
|
||
"Interpreter not initialized. Run (init) first.")))
|
||
```
|
||
|
||
This completes the elementary evaluator.
|
||
|
||
## **Exercise 5.1: Unbound-variable handling**
|
||
|
||
In Lisps, including Scheme, attempting to evaluate an unbound symbol is an unbound-variable error. However, in some algebraic processes it is often sensible to allow an unbound symbol to be a self-evaluating object. For example, if we generically extend arithmetic to build algebraic expressions with symbolic values, as we did in chapter 3, it is sometimes useful to allow the following:
|
||
|
||
```
|
||
(+ (* 2 3) (* 4 5))
|
||
26
|
||
(+ (* a 3) (* 4 5))
|
||
(+ (* a 3) 20)
|
||
```
|
||
|
||
Our generic arithmetic supported symbolic extensions: the operators \* and + were extended to build expressions when their arguments were not reducible to numbers. But it did not allow the use of unbound variables as literal numbers. Here the symbol a is unbound. We may want it to be self-evaluating.
|
||
|
||
**a.** Make a generic extension to eval to allow this kind of behavior. To make this work with the numerical primitives (+, \*, -, /) it is necessary to extend their behavior as well. Note that these operators should be changed in the underlying Scheme environment. As in chapter 3, the generic operator mechanism
|
||
|
||
may be given handlers that work in the underlying Scheme system.
|
||
|
||
**b.** Also augment apply to allow unbound symbols in the operator position to be interpreted as literal functions, known only by their names: (+ (f 3) (\* 4 5)) ==> (+ (f 3) 20)
|
||
|
||
These extensions to eval and apply are generally dangerous, because they hide real unbound-variable errors. Make them contingent on the value of a user-settable variable: allow-selfevaluating-symbols.
|
||
|
||
## **Exercise 5.2:** *n***-ary procedures**
|
||
|
||
Footnote 10 on page 246 points out a nasty assumption that we put into the g:apply handler that implies a restriction on the future expansion of this evaluator. In Scheme, if the procedureparameters of a procedure is not a list but rather a symbol, then that symbol is taken as a single parameter that will be bound to the list of arguments. [11](#page-72-2)
|
||
|
||
<span id="page-15-0"></span>In this exercise we change the interpreter to accept a single symbol as the formal parameter list, so that a procedure can be defined to take an indefinite number of arguments. In our interpreter the procedure lambda-parameters (page 239) is happy to return a single symbol, and everywhere it is called the result is passed to make-compound-procedure. That value is retrieved by procedure-parameters, which is used in g:apply. So it appears that the only part of the interpreter that needs to be changed is g:apply.
|
||
|
||
Change g:apply to work with the new compound procedures. This can be done by rewriting the existing strict-compoundprocedure? handler of g:apply (page 246), but it is both easier and clearer to specialize that handler for the case where the procedureparameters is a list, and to add a new handler for the case where the procedure-parameters is a symbol.
|
||
|
||
## **Exercise 5.3: Vectors of procedures**
|
||
|
||
In mathematical text a common abuse of notation is to identify a tuple of functions with a function that returns a tuple of values. For example, if (cos 0.6) produces 0.8253356149096783 and if (sin 0.6) produces 0.5646424733950354 then we expect ((vector cos sin) 0.6) to produce #(0.8253356149096783 0.5646424733950354).
|
||
|
||
Although we had an exercise 3.2 to extend the arithmetic to vectors, those extensions did not modify the underlying language evaluator. This behavior needs an extension to g:apply so it can handle vectors of functions as a kind of function. Make this extension, demonstrate it, and show that it interoperates with more conventional code.
|
||
|
||
### **Exercise 5.4: Your turn**
|
||
|
||
Invent a fun, interesting construct that can easily be implemented using generic eval/apply but would be rather painful without that kind of generic support.
|
||
|
||
## **Exercise 5.5: Interoperation with the underlying system**
|
||
|
||
As pointed out on page 238, evaluating the expression
|
||
|
||
```
|
||
eval> (map (lambda (x) (* x x)) '(1 2 3))
|
||
```
|
||
|
||
in our interpreter does not work if the map in this expression refers to the map procedure from the underlying Scheme system.
|
||
|
||
However, if we redefine map for our interpreter it does work:
|
||
|
||
```
|
||
eval> (define (map f l)
|
||
(if (null? l)
|
||
'()
|
||
(cons (f (car l)) (map f (cdr l)))))
|
||
map
|
||
```
|
||
|
||
```
|
||
eval> (map (lambda (x) (* x x)) '(1 2 3))
|
||
(1 4 9)
|
||
```
|
||
|
||
Why does it not work to use the underlying procedures that take procedural arguments, such as map? Explain. Outline a strategy to fix the problem and implement your solution. Note: This is subtle to get right, so don't spend infinite time trying to make it work perfectly.
|
||
|
||
## **Exercise 5.6: Different quotation**
|
||
|
||
There have been interesting languages with very different evaluation and quotation rules. For example, in MDL (see Wikipedia [91]) a symbol is assumed to be self evaluating, and variables to be looked up are distinguished with a prefix character. Also, in MDL a combination is a special form, but with an implied keyword. Our evaluator can easily be modified to interpret a MDLlike syntax, just by changing the syntax definitions. Try it!
|
||
|
||
## **Exercise 5.7: Infix notation**
|
||
|
||
Unlike Lisp, most computer languages use infix notations. If we wanted to include infix expressions in Scheme we might write:
|
||
|
||
```
|
||
(infix
|
||
"fact := lambda n:
|
||
if n == 0
|
||
then 1
|
||
else n*fact(n-1)")
|
||
(fact 6) ; The Lisp procedure is now defined
|
||
720
|
||
(infix "fact(5)") ; And it can be used in infix notation.
|
||
120
|
||
```
|
||
|
||
This is entirely a small matter of syntax (ha!). However, it is an interesting project to make it work. You do not need to change the interpreter. The work is parsing the character string to compile it into the corresponding Lisp expressions, in the same way that cond- >if works. Lisp programmers have done this many times, but people who program in Lisp seem to like the native Lisp Polish prefix notation! [12](#page-72-3) Oh, well...
|
||
|
||
## <span id="page-18-0"></span>**5.2 Procedures with non-strict arguments**
|
||
|
||
In this section we will investigate adding declarations to the formal parameters of a procedure to allow deferred evaluation of the corresponding operands.
|
||
|
||
In Scheme, procedures are *strict*. Strict procedures require evaluating all the operands of the calling expression and binding the resulting arguments to the formal parameters before the body of the procedure is evaluated. But for an if expression, the predicate part must be evaluated to determine whether to evaluate the consequent part or the alternative part; they won't both be evaluated. This is why if must be a special form, not a procedure. A *non-strict* procedure is one that defers the evaluation of some operands. How can we make it possible for a programmer to define non-strict procedures as needed, rather than just using a few special forms, such as if, that are specified in the language definition?
|
||
|
||
For example, suppose we want to make a procedure unless that works like the special form if in that it does not evaluate the alternatives that are not needed. [13](#page-72-4) Using unless we could write:
|
||
|
||
```
|
||
(define (fib n)
|
||
(unless (< n 2)
|
||
(+ (fib (- n 1)) (fib (- n 2)))
|
||
n))
|
||
```
|
||
|
||
For this definition of the Fibonacci function to work correctly, the second operand of the unless expression should not be evaluated if *n <* 2, and the third operand should not be evaluated if *n* ≥ 2. But
|
||
|
||
the first operand of the unless expression must always be evaluated to determine the choice.
|
||
|
||
We need a way to determine which operands of unless to evaluate, and which to defer. To do this we introduce a kind of declaration and write:
|
||
|
||
```
|
||
(define (unless condition (usual lazy) (exception lazy))
|
||
(if condition exception usual))
|
||
```
|
||
|
||
<span id="page-19-0"></span>Here we define the procedure unless in terms of the special form if, but we declare that the second and third arguments are lazy. [14](#page-72-5) The first argument is, by default, strict.
|
||
|
||
We could have many kinds of declarations on formal parameters, describing how to handle operands and arguments. A parameter could be declared lazy and memoized, to implement call by need, as are arguments to all procedures in languages like Haskell; a parameter could be declared to require that its argument satisfy given predicates, which could be types and units; etc.
|
||
|
||
### **Implementing generalized formal parameters**
|
||
|
||
To implement generalized formal parameters, we need a special applicator that handles the new cases. This is accomplished by adding a single handler to g:apply, similar to the earlier one for strict compound procedures (see page 246):
|
||
|
||
```
|
||
(define-generic-procedure-handler g:apply
|
||
(match-args general-compound-procedure?
|
||
operands?
|
||
environment?)
|
||
(lambda (procedure operands calling-environment)
|
||
(if (not (n:= (length (procedure-parameters procedure))
|
||
(length operands)))
|
||
(error "Wrong number of operands supplied"))
|
||
(let ((params (procedure-parameters procedure))
|
||
(body (procedure-body procedure)))
|
||
(let ((names (map procedure-parameter-name params))
|
||
(arguments
|
||
(map (lambda (param operand)
|
||
(g:handle-operand param
|
||
operand
|
||
```
|
||
|
||
```
|
||
calling-environment))
|
||
params
|
||
operands)))
|
||
(g:eval body
|
||
(extend-environment names arguments
|
||
(procedure-environment procedure)))))))
|
||
```
|
||
|
||
This differs from the strict applicator in two ways: first, we must extract the names of the parameters, since they could be wrapped in declarations; second, we must handle the operands specially, depending on the declarations. This is done by the generic procedures procedure-parameter-name and g:handle-operand.
|
||
|
||
The procedure procedure-parameter-name allows us to add declarations to a formal parameter and still be able to retrieve its name. The default handler is the identity function, so the name of an undecorated formal parameter is just itself.
|
||
|
||
```
|
||
(define procedure-parameter-name
|
||
(simple-generic-procedure 'parameter-name 1 (lambda (x)
|
||
x)))
|
||
```
|
||
|
||
The procedure g:handle-operand allows us to choose how to process an operand based on the declarations of the corresponding formal parameter:
|
||
|
||
```
|
||
(define g:handle-operand
|
||
(simple-generic-procedure 'g:handle-operand 3
|
||
(lambda (parameter operand environment)
|
||
(g:advance (g:eval operand environment)))))
|
||
```
|
||
|
||
The default way to handle an operand without declarations is to evaluate the operand, as was previously done by eval-operands on page 245.
|
||
|
||
We need a syntax to allow us to decorate a formal parameter with declarations. Here we choose to use a list beginning with the name of the formal parameter:
|
||
|
||
```
|
||
(define-generic-procedure-handler procedure-parameter-name
|
||
(match-args pair?)
|
||
car)
|
||
```
|
||
|
||
We will start by implementing two kinds of declarations. The first is lazy, which means the operand is evaluated only when its value is needed, for example as the predicate of an if expression. The second is lazy memo, which is like lazy except that the first time the operand is evaluated, the value is remembered so that subsequent uses do not require reevaluation.
|
||
|
||
If a parameter is specified to be lazy (or lazy memoized) the evaluation of the operand must be postponed. The postponed expression must be packaged with the environment that will be used to give values to the free variables in that expression when its value is required. [15](#page-73-0)
|
||
|
||
```
|
||
(define-generic-procedure-handler g:handle-operand
|
||
(match-args lazy? operand? environment?)
|
||
(lambda (parameter operand environment)
|
||
(postpone operand environment)))
|
||
(define-generic-procedure-handler g:handle-operand
|
||
(match-args lazy-memo? operand? environment?)
|
||
(lambda (parameter operand environment)
|
||
(postpone-memo operand environment)))
|
||
```
|
||
|
||
Of course, we must extend g:advance, which so far has only a default handler (see page 236), to do the postponed evaluation. Notice that the result of g:advance may itself be a postponement, so we may have to advance that.
|
||
|
||
```
|
||
(define-generic-procedure-handler g:advance
|
||
(match-args postponed?)
|
||
(lambda (object)
|
||
(g:advance (g:eval (postponed-expression object)
|
||
(postponed-environment object)))))
|
||
```
|
||
|
||
If the expression is postponed with the intent of memoizing the result, the result is saved by advance-memo!:
|
||
|
||
```
|
||
(define-generic-procedure-handler g:advance
|
||
(match-args postponed-memo?)
|
||
(lambda (object)
|
||
(let ((value
|
||
(g:advance
|
||
(g:eval (postponed-expression object)
|
||
```
|
||
|
||
```
|
||
(postponed-environment object)))))
|
||
(advance-memo! object value)
|
||
value)))
|
||
```
|
||
|
||
The memoized value never needs to be evaluated again. The advance-memo! procedure changes the type of the postponed object to satisfy the predicate advanced-memo? and saves the value, making it accessible by advanced-value: [16](#page-73-1)
|
||
|
||
```
|
||
(define-generic-procedure-handler g:advance
|
||
(match-args advanced-memo?)
|
||
advanced-value)
|
||
```
|
||
|
||
### **Example: Lazy pairs and lists**
|
||
|
||
<span id="page-22-1"></span>Procedures with lazy parameters give us new power. For example, we can define a constructor kons, and selectors kar and kdr, so that we can make pairs without evaluating their contents. [17](#page-73-2) Here we have implemented kons as a procedure that takes its arguments call by need (memoized lazy). It produces a message acceptor, thepair, for kar and kdr. It also puts a "sticky note" on the-pair for identifying it as the result of kons.
|
||
|
||
```
|
||
(define (kons (x lazy memo) (y lazy memo))
|
||
(define (the-pair m)
|
||
(cond ((eq? m 'kar) x)
|
||
((eq? m 'kdr) y)
|
||
(else (error "Unknown message – kons" m x y))))
|
||
(hash-table-set! kons-registrations the-pair #t)
|
||
the-pair)
|
||
(define (kar x)
|
||
(x 'kar))
|
||
(define (kdr x)
|
||
(x 'kdr))
|
||
```
|
||
|
||
The reason why we need the sticky note is to be able to recognize a kons pair:
|
||
|
||
```
|
||
(define (kons? object)
|
||
(hash-table-exists? kons-registrations object))
|
||
```
|
||
|
||
<span id="page-23-0"></span>Using this lazy pair mechanism we can easily implement streamtype processing. Streams are like lists, but they are built as needed by the processes that consume them. [18](#page-73-3) Thus a stream that is infinitely long may be processed incrementally, with only a finite portion actual at any time.
|
||
|
||
Some streams are finite, so it is useful to choose a representation for the empty stream. Let's make it the same as the empty list:
|
||
|
||
```
|
||
(define the-empty-stream '())
|
||
(define (empty-stream? thing)
|
||
(null? thing))
|
||
```
|
||
|
||
#### We can add streams:
|
||
|
||
```
|
||
(define (add-streams s1 s2)
|
||
(cond ((empty-stream? s1) s2)
|
||
((empty-stream? s2) s1)
|
||
(else
|
||
(kons (+ (kar s1) (kar s2))
|
||
(add-streams (kdr s1) (kdr s2))))))
|
||
```
|
||
|
||
#### We can find the *n*th element of a stream:
|
||
|
||
```
|
||
(define (ref-stream stream n)
|
||
(if (= n 0)
|
||
(kar stream)
|
||
(ref-stream (kdr stream) (- n 1))))
|
||
```
|
||
|
||
Given these, we can create a (potentially infinite) stream of Fibonacci numbers with two initial entries and the rest of the stream formed by adding the stream to its kdr:
|
||
|
||
```
|
||
(define fibs
|
||
(kons 0 (kons 1 (add-streams (kdr fibs) fibs))))
|
||
```
|
||
|
||
### Then we can look at a few Fibonacci numbers
|
||
|
||
```
|
||
(ref-stream fibs 10)
|
||
55
|
||
(ref-stream fibs 100)
|
||
354224848179261915075
|
||
```
|
||
|
||
The usual doubly recursive Fibonacci program is exponential, so one could not expect to get the 100th entry in this sequence by that method; but the fact that the kons pairs are memoized reduces this to a linear problem. Notice that by this point in the sequence the ratio of two successive Fibonacci numbers has converged to the golden ratio in full precision:
|
||
|
||
```
|
||
(inexact
|
||
(/ (ref-stream fibs 100)
|
||
(ref-stream fibs 99)))
|
||
1.618033988749895
|
||
```
|
||
|
||
## **Exercise 5.8: Integrating differential equations**
|
||
|
||
Unfortunately, the use of kons does not, in itself, solve all stream problems. For example, the difficulty alluded to in SICP [1] section 4.2.3 (p. 411) does not automatically dissipate. Suppose we want to integrate a differential equation given some initial conditions. We make the following definitions:
|
||
|
||
```
|
||
(define (map-stream proc (items lazy memo))
|
||
(if (empty-stream? items)
|
||
items
|
||
(kons (proc (kar items))
|
||
(map-stream proc (kdr items)))))
|
||
(define (scale-stream items factor)
|
||
(map-stream (lambda (x) (* x factor))
|
||
items))
|
||
(define (integral integrand initial-value dt)
|
||
(define int
|
||
(kons initial-value
|
||
(add-streams (scale-stream integrand dt)
|
||
int)))
|
||
int)
|
||
(define (solve f y0 dt)
|
||
(define y (integral dy y0 dt))
|
||
(define dy (map-stream f y))
|
||
y)
|
||
```
|
||
|
||
We try to find an approximation to *e* by integrating *x !*(*t*) = *x*(*t*) with initial condition *x*(0) = 1. We know that *e* = *x*(1) so we write:
|
||
|
||
```
|
||
(ref-stream (solve (lambda (x) x) 1 0.001) 1000)
|
||
;Unbound variable: dy
|
||
```
|
||
|
||
### We get an error—ugh!
|
||
|
||
However, now we have the tools to fix this problem. What has to be changed to make this work as expected? Fix this program to get the following behavior:
|
||
|
||
```
|
||
(ref-stream (solve (lambda (x) x) 1 0.001) 1000)
|
||
2.716923932235896
|
||
```
|
||
|
||
(Yes, we know this is a terrible approximation to *e*, but it illustrates a programming point, not a numerical analysis point!)
|
||
|
||
## **Exercise 5.9: Why not kons?**
|
||
|
||
The kons special form is equivalent to a cons with both arguments lazy and memoized. If the arguments were not memoized, the computation (ref-stream fibs 100) above would take a very long time.
|
||
|
||
- **a.** Is there ever an advantage to not memoizing? When might it matter?
|
||
- **b.** Why could we not have defined kons simply as
|
||
|
||
```
|
||
(define (kons (a lazy memo) (d lazy memo))
|
||
(cons a d))
|
||
```
|
||
|
||
using the primitive procedure cons imported from Scheme?
|
||
|
||
**c.** More generally, the Lisp community has avoided changing cons to be kons, as recommended by Friedman and Wise (see footnote 17 on page 254). What potentially serious problems are avoided by using cons rather than kons? Assume that we do not care about small constant factors in performance.
|
||
|
||
### **Exercise 5.10: Restricted parameters**
|
||
|
||
One nice idea is to build restrictions into the declaration of a formal parameter. We might want to require that an arbitrary predicate be true of a parameter, similar to our use of restrictions in pattern variables in section 4.3.2. For example, we might want a procedure to take three arguments: the first is any integer, but the second is prime, and the third is unrestricted. This might be notated:
|
||
|
||
```
|
||
(define (my-proc (n integer?) (p prime?) g)
|
||
...)
|
||
```
|
||
|
||
Unfortunately, this kind of ad hoc design does not play well with other declarations, like lazy and memo, unless we legislate the order of the declarations or make them reserved identifiers. Suppose, for convenience, we declare lazy and memo to be special keywords, and require other declarations to be announced with a keyword, such as restrict-to for a predicate:
|
||
|
||
```
|
||
(define (my-proc (n restrict-to integer?)
|
||
(p restrict-to prime? lazy)
|
||
g)
|
||
...)
|
||
```
|
||
|
||
- **a.** Design an appropriate syntax. Make sure it is extensible in that new declaration types can be added as needed. Express your syntax in BNF and change the syntax procedures of your interpreter to implement it.
|
||
- **b.** Implement predicate restrictions. If a restriction is violated at run time, the program should report an error. You may find guarantee useful here.
|
||
|
||
## **Exercise 5.11:** *n***-ary procedures, again!**
|
||
|
||
**a.** In exercise 5.2 on page 248 we modified the g:apply handler to allow the formal parameters of a procedure to be a single symbol that is bound to a list of the arguments. Unfortunately, this way of specifying a rest argument is not natural for a system where the formal parameters may be decorated with declarations. However, we can invent a decoration syntax that allows us to define procedures with optional and rest arguments.
|
||
|
||
For example, if we allow the last formal parameter in the formal parameter list be decorated with the word rest, it should be bound to the unmatched arguments. This rest declaration should be usable with other declarations on that argument. So we should be able to create procedures like:
|
||
|
||
```
|
||
(lambda (x
|
||
(y restrict-to integer? lazy)
|
||
(z rest restrict-to list-of-integers?))
|
||
...)
|
||
```
|
||
|
||
where list-of-integers? is a predicate that is true of lists of integers. The rest declaration should be able to be used with other declarations, such as lazy and restrict-to.
|
||
|
||
Make rest declarations work!
|
||
|
||
**b.** It may also be useful to allow a procedure to have optional arguments, possibly with specified default values. For example, a numerical procedure could allow the user to specify a tolerance for approximation, but specify a default value if the user does not supply the tolerance:
|
||
|
||
```
|
||
(lambda (x (epsilon optional flo:ulp-of-one))
|
||
...)
|
||
```
|
||
|
||
Here flo:ulp-of-one is a globally defined symbol that specifies the smallest power of two that when added to 1.0 produces a value that is not equal to 1.0. In the C library it is called DBL EPSILON. (For those few of you who care, in IEEE double-precision floating point the value of flo:ulp-of-one is 2.220446049250313e-16.)
|
||
|
||
Make optional declarations work too! Be sure that your extension can mix and match with all other declarations that make sense.
|
||
|
||
## **5.3 Compiling to execution procedures**
|
||
|
||
The evaluator that we have been working with is extremely flexible and extensible, but it is dumb: our programs run rather slowly. One culprit is that the evaluator is repeatedly looking at the syntax (however simple) of the program. We avoided this problem in chapter 4 by transforming each matcher pattern into a composition of matcher procedures that all have the same form—a combinator language—in section 4.3. In interpreting a language we can avoid reexamining the syntactic structure by similarly compiling into a composition of execution procedures. So before getting deeper into evaluation, let's make this transition.
|
||
|
||
The critical idea is to separate the problem of evaluation of an expression relative to an environment into two phases. In the first phase the expression is analyzed and converted into an execution procedure. In the second phase that execution procedure is applied to an environment, producing the expected evaluation result. We implement this idea directly, as the composition of the two phases.
|
||
|
||
```
|
||
(define (x:eval expression environment)
|
||
((analyze expression) environment))
|
||
```
|
||
|
||
The analysis and conversion of the expression is called *compilation*, and the work that it does is said to be done at *compile time*. The compiler extracts that part of the behavior that does not depend on the values of the free variables in the expression. This is mostly syntactic analysis, but it is also a venue for some optimizations that are implementable by syntactic rules. The resulting execution procedure depends on the mapping of symbols to values specified in the environment; the work it does is said to be done at *run time*.
|
||
|
||
#### **Analysis of expressions**
|
||
|
||
Since we want to be able to extend the language syntax as needed, we implement the analysis as a generic procedure, with the default being an application of an operator to operands. This has to be a default for Lisp/Scheme because there is no syntactic keyword that distinguishes an application. [19](#page-73-4)
|
||
|
||
```
|
||
(define x:analyze
|
||
(simple-generic-procedure 'x:analyze 1 default-analyze))
|
||
```
|
||
|
||
The convention for x:analyze is that it takes an expression as an argument and returns an execution procedure, which takes one argument, an environment.
|
||
|
||
The procedure analyze captures a common usage pattern:
|
||
|
||
```
|
||
(define (analyze expression)
|
||
(make-executor (x:analyze expression)))
|
||
```
|
||
|
||
The purpose of wrapping the execution procedure with the procedure make-executor is to aid in debugging. The resulting *executor* is also a procedure, with the same arguments and returned value as the execution procedure that it wraps. One useful aspect of this wrapper is that it maintains an "execution trace" that can be helpful while determining how a program got to a point of failure.
|
||
|
||
As we said, the default analysis is of an application.
|
||
|
||
```
|
||
(define (default-analyze expression)
|
||
(cond ((application? expression)
|
||
(analyze-application expression))
|
||
(else (error "Unknown expression type" expression))))
|
||
(define (analyze-application expression)
|
||
(let ((operator-exec (analyze (operator expression)))
|
||
(operand-execs (map analyze (operands expression))))
|
||
(lambda (environment)
|
||
(x:apply (x:advance (operator-exec environment))
|
||
operand-execs
|
||
environment))))
|
||
```
|
||
|
||
Notice the division of labor here: the operator and the operands are extracted from the expression and analyzed to make up the execution procedures operator-exec and operand-execs. This may require significant analysis. The execution procedure for the application is then a procedure (created by the lambda expression) that takes an environment and does the application. The procedure x:apply (on page 265) is analogous to g:apply in the interpreter; but x:apply takes execution procedures for the operands, rather than the operand expressions that were used by g:apply. The procedure x:advance, analogous to g:advance, is introduced for the same reason. Every part of the evaluator can be transformed in this way.
|
||
|
||
The transformation of self-evaluating expressions (such as numbers, boolean values, or strings) is trivial. The only hard part of this is the actual syntax of the expressions, which is handled by the Scheme parser. The text of the programs is parsed into tokens and sexpressions before it ever gets to the evaluator, so we need not concern ourselves with those complexities here.
|
||
|
||
```
|
||
(define (analyze-self-evaluating expression)
|
||
(lambda (environment) expression))
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args self-evaluating?)
|
||
analyze-self-evaluating)
|
||
```
|
||
|
||
<span id="page-30-0"></span>Quotation is easy, again because the hard part is in the parser. [20](#page-73-5)
|
||
|
||
```
|
||
(define (analyze-quoted expression)
|
||
(let ((qval (text-of-quotation expression)))
|
||
(lambda (environment) qval)))
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args quoted?)
|
||
analyze-quoted)
|
||
```
|
||
|
||
Variables are also easy. Once we identify the variable, all of the work is in the execution procedure.
|
||
|
||
```
|
||
(define (analyze-variable expression)
|
||
(lambda (environment)
|
||
```
|
||
|
||
```
|
||
(lookup-variable-value expression environment)))
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args variable?)
|
||
analyze-variable)
|
||
```
|
||
|
||
Procedure definitions, expressed in Lisp/Scheme by lambda expressions, are an example of a powerful division of labor. Before building the execution procedure, the analyzer (compiler) parses the lambda expression, extracting the formal parameter specifications, and compiles the body of the expression. Thus the execution procedure for the lambda expression, and the code that eventually executes the body, need not do that work.
|
||
|
||
```
|
||
(define (analyze-lambda expression)
|
||
(let ((vars (lambda-parameters expression))
|
||
(body-exec (analyze (lambda-body expression))))
|
||
(lambda (environment)
|
||
(make-compound-procedure vars body-exec environment))))
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args lambda?)
|
||
analyze-lambda)
|
||
```
|
||
|
||
The special form if is another very clear example of the advantage of separating analysis from execution. The three parts of the if expression are analyzed at compile time, allowing the execution procedure to do no more work than extract the boolean value from the predicate to decide whether to do the consequent or the alternative. The analysis of the subexpressions is not necessary to do at run time (when the execution procedure is used).
|
||
|
||
```
|
||
(define (analyze-if expression)
|
||
(let ((predicate-exec
|
||
(analyze (if-predicate expression)))
|
||
(consequent-exec
|
||
(analyze (if-consequent expression)))
|
||
(alternative-exec
|
||
(analyze (if-alternative expression))))
|
||
(lambda (environment)
|
||
(if (x:advance (predicate-exec environment))
|
||
(consequent-exec environment)
|
||
(alternative-exec environment)))))
|
||
```
|
||
|
||
```
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args if?)
|
||
analyze-if)
|
||
```
|
||
|
||
Sequences of expressions to be evaluated are an especially good example of separation of analysis and execution. There is no good reason to recompile a sequence of expressions every time we enter the body of a procedure; this work can be done once and for all at compile time.
|
||
|
||
The analyze-begin procedure first analyzes each subexpression of the begin expression, producing a list of execution procedures (preserving the order of the expressions in the begin expression). These execution procedures are then glued together using reduceright and a pairwise combinator that takes two execution procedures and produces an execution procedure that executes the two given execution procedures in sequence. [21](#page-73-6)
|
||
|
||
```
|
||
(define (analyze-begin expression)
|
||
(reduce-right (lambda (exec1 exec2)
|
||
(lambda (environment)
|
||
(exec1 environment)
|
||
(exec2 environment)))
|
||
#f
|
||
(map analyze
|
||
(let ((exps
|
||
(begin-actions expression)))
|
||
(if (null? exps)
|
||
(error "Empty sequence"))
|
||
exps))))
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args begin?)
|
||
analyze-begin)
|
||
```
|
||
|
||
The treatment of assignments is not problematical in the absence of compiler optimizations.
|
||
|
||
```
|
||
(define (analyze-assignment expression)
|
||
(let ((var
|
||
(assignment-variable expression))
|
||
(value-exec
|
||
(analyze (assignment-value expression))))
|
||
```
|
||
|
||
```
|
||
(lambda (environment)
|
||
(set-variable-value! var
|
||
(value-exec environment)
|
||
environment)
|
||
'ok)))
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args assignment?)
|
||
analyze-assignment)
|
||
```
|
||
|
||
However, if there are compiler optimizations to be done, assignments pose serious problems. Indeed, assignments introduce time into a program: some things happen before the assignment and some happen after the assignment, and the assignment can change the events that reference the variable that was changed. Thus, for example, common subexpressions may not really have the same value if they reference a variable that can be assigned!
|
||
|
||
Definitions are not a problem, unless we think of them (and incorrectly use them) as assignments, potentially interfering with compiler optimizations.
|
||
|
||
```
|
||
(define (analyze-definition expression)
|
||
(let ((var
|
||
(definition-variable expression))
|
||
(value-exec
|
||
(analyze (definition-value expression))))
|
||
(lambda (environment)
|
||
(define-variable! var
|
||
(value-exec environment)
|
||
environment)
|
||
var)))
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args definition?)
|
||
analyze-definition)
|
||
```
|
||
|
||
Special forms that are implemented by transformations of expressions, such as cond and let, are really easy in this system; we simply compile the transformed expression. Indeed, this is the place where a very general macro facility could be hooked in.
|
||
|
||
```
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args cond?)
|
||
```
|
||
|
||
```
|
||
(compose analyze cond->if))
|
||
(define-generic-procedure-handler x:analyze
|
||
(match-args let?)
|
||
(compose analyze let->combination))
|
||
```
|
||
|
||
### **Application of procedures**
|
||
|
||
The execution procedure for an application calls the execution procedure for the operator to obtain the compound procedure to be applied. (See analyze-application on page 260.) The operands have also been converted to execution procedures.
|
||
|
||
The procedure x:apply is analogous to g:apply in the elementary evaluator (on page 245):
|
||
|
||
```
|
||
(define x:apply
|
||
(simple-generic-procedure 'x:apply 3 default-apply))
|
||
(define (default-apply procedure operand-execs environment)
|
||
(error "Unknown procedure type" procedure))
|
||
```
|
||
|
||
Note that the default-apply here is the same as the one used by g:apply except for the names of the two unused parameters.
|
||
|
||
As before, we need handlers for application of the various kinds of procedures, with particular kinds of parameters. The application handler for strict primitive procedures has to force the arguments and then execute the primitive procedure.
|
||
|
||
```
|
||
(define-generic-procedure-handler x:apply
|
||
(match-args strict-primitive-procedure?
|
||
executors?
|
||
environment?)
|
||
(lambda (procedure operand-execs environment)
|
||
(apply-primitive-procedure procedure
|
||
(map (lambda (operand-exec)
|
||
(x:advance (operand-exec environment)))
|
||
operand-execs))))
|
||
```
|
||
|
||
The application handler for general procedures is only slightly different than in the elementary evaluator shown earlier. The difference is that we have execution procedures rather than operand expressions to work with.
|
||
|
||
```
|
||
(define-generic-procedure-handler x:apply
|
||
(match-args compound-procedure? executors? environment?)
|
||
(lambda (procedure operand-execs calling-environment)
|
||
(if (not (n:= (length (procedure-parameters procedure))
|
||
(length operand-execs)))
|
||
(error "Wrong number of operands supplied"))
|
||
(let ((params (procedure-parameters procedure))
|
||
(body-exec (procedure-body procedure)))
|
||
(let ((names (map procedure-parameter-name params))
|
||
(arguments
|
||
(map (lambda (param operand-exec)
|
||
(x:handle-operand param
|
||
operand-exec
|
||
calling-environment))
|
||
params
|
||
operand-execs)))
|
||
(body-exec (extend-environment names arguments
|
||
(procedure-environment procedure)))))))
|
||
```
|
||
|
||
This application handler for compound procedures needs to be able to deal with the various kinds of formal parameters that may be present in the compound procedure. This is accomplished, in our usual way, by making x:handle-operand a generic procedure. The default, for an operand to be evaluated before entering the body of the compound procedure, is to immediately execute the operand execution procedure to obtain a value. However, lazy parameters and memoized lazy parameters need to be able to postpone the execution appropriately.
|
||
|
||
```
|
||
(define x:handle-operand
|
||
(simple-generic-procedure 'x:handle-operand 3
|
||
(lambda (parameter operand-exec environment)
|
||
(operand-exec environment))))
|
||
(define-generic-procedure-handler x:handle-operand
|
||
(match-args lazy? executor? environment?)
|
||
(lambda (parameter operand-exec environment)
|
||
(postpone operand-exec environment)))
|
||
(define-generic-procedure-handler x:handle-operand
|
||
(match-args lazy-memo? executor? environment?)
|
||
(lambda (parameter operand-exec environment)
|
||
(postpone-memo operand-exec environment)))
|
||
```
|
||
|
||
The postponement of an execution procedure for an operand is the same as the postponement of an operand expression. But the handlers for the generic procedure x:advance to deal with a postponed operand execution procedure are different from those for g:advance: the postponed execution procedure must be called on the postponed environment rather than evaluated relative to that environment (compare with g:advance on page 253).
|
||
|
||
```
|
||
(define-generic-procedure-handler x:advance
|
||
(match-args postponed?)
|
||
(lambda (object)
|
||
(x:advance ((postponed-expression object)
|
||
(postponed-environment object)))))
|
||
(define-generic-procedure-handler x:advance
|
||
(match-args postponed-memo?)
|
||
(lambda (object)
|
||
(let ((value
|
||
(x:advance ((postponed-expression object)
|
||
(postponed-environment object)))))
|
||
(advance-memo! object value)
|
||
value)))
|
||
```
|
||
|
||
The handling of operands in this x:apply is not very clever. In fact, it does lots of "parsing" of the formal parameter list in the execution procedure, so we really did not fully compile the compound procedure. One step to improve this compilation would be to separate out the handler for strict compound procedures, as we did earlier. Fixing this nastiness is your job in exercise 5.16.
|
||
|
||
## **Exercise 5.12: Implementing** *n***-ary procedures**
|
||
|
||
In exercises 5.2 and 5.11 we noted that it is often valuable to have procedures that can take an indefinite number of arguments. The addition and multiplication procedures in Scheme are examples of such procedures.
|
||
|
||
To define such a procedure in Scheme, we specify the formal parameters of a lambda expression as a single symbol rather than a list. That symbol is bound to a list of the arguments supplied. For
|
||
|
||
example, to make a procedure that takes several arguments and returns a list of the squares of the arguments, we can write:
|
||
|
||
```
|
||
(lambda x (map square x))
|
||
or
|
||
(define (ss . x) (map square x))
|
||
and then we can say
|
||
(ss 1 2 3 4) ==> (1 4 9 16)
|
||
```
|
||
|
||
Modify the analyzing interpreter to allow this construct.
|
||
|
||
Hint: You do not need to change the code involving define or lambda in the syntax definitions! This is entirely a change in the analyzer.
|
||
|
||
Demonstrate that your modification allows this kind of procedure and that it does not cause other troubles.
|
||
|
||
## **Exercise 5.13: Simplifying debugging**
|
||
|
||
One problem with this compiler is that the execution procedures are all anonymous lambda expressions. So there is little information for a backtrace to report. However, it is easy to improve matters. If we rewrite the procedure that makes execution procedures for applications
|
||
|
||
```
|
||
(define (analyze-application exp)
|
||
(let ((operator-exec (analyze (operator exp)))
|
||
(operand-execs (map analyze (operands exp))))
|
||
(lambda (env)
|
||
(x:apply (x:advance (operator-exec env))
|
||
operand-execs
|
||
env))))
|
||
```
|
||
|
||
### like this:
|
||
|
||
```
|
||
(define (analyze-application exp)
|
||
(let ((operator-exec (analyze (operator exp)))
|
||
(operand-execs (map analyze (operands exp))))
|
||
```
|
||
|
||
```
|
||
(define (execute-application env)
|
||
(x:apply (x:advance (operator-exec env))
|
||
operand-execs
|
||
env))
|
||
execute-application))
|
||
```
|
||
|
||
then (in MIT/GNU Scheme) the execution procedure will have a name that tells us what kind of execution procedure it is. Implement this idea in all the execution procedures.
|
||
|
||
Think of, and perhaps implement, other ways we could improve the debuggability of the runtime code without impairing the execution speed. One thing you might do is add the expression exp as a "sticky note" on the execution procedure.
|
||
|
||
## **Exercise 5.14: Constant folding**
|
||
|
||
Assume we have a declaration to tell the analyzer that certain symbols have a given meaning (for example a declaration that the conventional arithmetic operators {+, -, \*, /, sqrt} refer to known constant procedures). Then any combination of constants with these operators, such as (/ (+ 1 (sqrt 5)) 2), may be evaluated by the analyzer at compile time and the result used instead of executing the computation at run time. This compile-time optimization is called *constant folding*.
|
||
|
||
Implement constant folding in the analyzer. To do constant folding, the analyzer needs to know which symbols in the program text it can count on to be bound to known values. For example, it needs to know if car is actually bound to the primitive selector of pairs. Assume that the analyzer can call a procedure that finds the bindings of known symbols. This procedure should take a symbol and return the value that the analyzer may depend on, or #f if the symbol is not under control of the analyzer.
|
||
|
||
### **Exercise 5.15: Other optimizations**
|
||
|
||
There are many simple transformations that can improve the execution of a program. For example, we can use our patternmatching technology to make a term-rewriting system that implements peephole optimization and loop-invariant code motion. Perhaps it would be nice to add common subexpression elimination; but be careful about side effects due to assignments. Add a phase of optimization to the analysis, implement some classic compiler optimizations, and show their effects.
|
||
|
||
# **Exercise 5.16: Compiling formal-parameter declarations**
|
||
|
||
Although the transformation to compositions of execution procedures is quite effective, and produces much faster code than straight interpretation, the version we presented is not very clever: the compound-procedure execution procedure for x:apply parses the formal parameter list to determine how to handle the operands. This should really be done at compile time rather than run time: the analysis of the lambda expression that made the compound procedure should produce an execution procedure that knows what to do with the operands and calling environment.
|
||
|
||
Figure this out and do it. Make sure that you do not carry the calling environment any further than is absolutely needed.
|
||
|
||
Note: This is a big project.
|
||
|
||
## **5.4 Exploratory behavior**
|
||
|
||
We have already encountered explicit backtracking search for matching segment variables in pattern matching. But even in the absence of segment variables, the implementation of the termrewriting system required some backtracking search. When a rule's consequent expression determined that the match was not selective enough for the consequent to replace the matched part of the data,
|
||
|
||
even though the antecedent pattern of the rule matched a piece of data, the consequent expression returned #f, failing back into the match and perhaps trying a different rule.
|
||
|
||
Also, the trie mechanism for optimizing the access to a generic procedure handler requires backtracking. The trie chases a sequence of predicates that the sequence of arguments must satisfy. But there may be multiple ways that an initial segment of predicates matches the initial segment of arguments, so there is an implicit search built into the trie mechanism.
|
||
|
||
We normally think of backtracking, and its extreme use in search, as an AI technique. However, backtracking can be viewed as a way of making systems that are modular and independently evolvable, as in the exploratory behavior of biological systems. Consider a simple but practical example: solving a quadratic equation. There are two roots to a quadratic. We could return both, and assume that the user of the solution knows how to deal with that, or we could return one and hope for the best. (The canonical square-root procedure sqrt returns the positive square root, even though there are two square roots!) The disadvantage of returning both solutions is that the receiver of that result must know to try the computation with both and either reject one, or return both results of the computation, which may itself have made some choices. The disadvantage of returning only one solution is that it may not be the right one for the receiver's purpose. This can be a real problem in simulations of physical systems.
|
||
|
||
### **Linguistically implicit search**
|
||
|
||
The searches we have explicitly built are okay, but perhaps we can do better by building a backtracking mechanism into the linguistic infrastructure. The square-root procedure should return one of the roots, with the option to change its mind and return the other one if the first choice is determined to be inappropriate by the receiver. It is, and should be, the receiver's responsibility to determine if the ingredients to its computation are appropriate and acceptable. This may itself require a complex computation, involving choices whose
|
||
|
||
consequences may not be apparent without further computation; so the process is recursive. Of course, this gets us into potentially deadly exponential searches through all possible assignments to all the choices that have been made in the program.
|
||
|
||
It is important to consider the extent to which a search strategy can be separated from the other parts of a program, so that one can interchange search strategies without greatly modifying the program. Here we take the further step of pushing search and search control into the infrastructure that is supported by the language, and not explicitly building search into our program at all. Making search implicit may encourage excessive use of search. As usual, modular flexibility can be dangerous.
|
||
|
||
This idea has considerable history. In 1961 John McCarthy [90] had the idea of a nondeterministic operator, amb, which could be useful for representing nondeterministic automata. In 1967 Bob Floyd [35] had the idea of building backtracking search into a computer language as part of the linguistic infrastructure. In 1969 Carl Hewitt [56] proposed a language, PLANNER, that embodied these ideas. In the early 1970s Colmerauer, Kowalski, Roussel, and Warren developed Prolog [78], a language based on a limited form of first-order predicate calculus, which made backtracking search implicit. [22](#page-74-0)
|
||
|
||
### <span id="page-41-0"></span>**5.4.1 amb**
|
||
|
||
McCarthy's amb takes any number of arguments. The value of the amb expression is the value of one of the arguments, but we don't know in advance which one is appropriate. For example,
|
||
|
||
```
|
||
(amb 1 2 3)
|
||
```
|
||
|
||
produces the value 1 or 2 or 3, depending on the future of the computation. The expression (amb), with no arguments, has no possible values: it is a computational failure, rejecting the choices previously made.
|
||
|
||
An expression using amb may have many possible values. To see all the possible values we print one and then cause a failure, forcing
|
||
|
||
the production of the next value, until there are no more to be had.
|
||
|
||
```
|
||
(begin
|
||
(newline)
|
||
(write-line (list (amb 1 2 3) (amb 'a 'b)))
|
||
(amb))
|
||
;;; Starting a new problem (1 a)
|
||
(2 a)
|
||
(3 a)
|
||
(1 b)
|
||
(2 b)
|
||
(3 b)
|
||
;;; There are no more values
|
||
```
|
||
|
||
Using amb we can generate Pythagorean triples rather easily. We use amb to generate triples of integers and reject the ones that are not Pythagorean.
|
||
|
||
To facilitate programming with amb, we introduce a helper. We use require as a filter that will force a failure and backtrack if its argument predicate expression is not true.
|
||
|
||
```
|
||
(define (require p)
|
||
(if (not p) (amb) 'ok))
|
||
```
|
||
|
||
To obtain some integer in an interval, we write:
|
||
|
||
```
|
||
(define (an-integer-between low high)
|
||
(require (<= low high))
|
||
(amb low (an-integer-between (+ low 1) high)))
|
||
```
|
||
|
||
With these helpers we can write the search for Pythagorean triples in a very intuitive form:
|
||
|
||
```
|
||
(define (a-pythagorean-triple-between low high)
|
||
(let ((i (an-integer-between low high)))
|
||
(let ((j (an-integer-between i high)))
|
||
(let ((k (an-integer-between j high)))
|
||
(require (= (+ (* i i) (* j j))
|
||
(* k k)))
|
||
(list i j k)))))
|
||
(begin
|
||
(newline)
|
||
(write-line (a-pythagorean-triple-between 1 20))
|
||
(amb))
|
||
```
|
||
|
||
```
|
||
;;; Starting a new problem
|
||
(3 4 5)
|
||
(5 12 13)
|
||
(6 8 10)
|
||
(8 15 17)
|
||
(9 12 15)
|
||
(12 16 20)
|
||
;;; There are no more values
|
||
```
|
||
|
||
This seems like a generally useful facility. Let's see how we can make it part of our language.
|
||
|
||
### **5.4.2 Implementing amb**
|
||
|
||
It is nice that we separated the analysis of the expressions of the language from the execution, because that allows us to change the execution without changing any of the syntactic analysis. So building nondeterministic search into the language is a matter of changing only the execution procedures. The critical step is to transform the execution procedures into continuation-passing style, where in addition to the environment argument, each execution procedure takes two continuation arguments: one, typically named succeed, that is called when the computation is successful, and the other, typically named fail, that is called when the computation is unsuccessful.
|
||
|
||
The execution procedure returns a proposed value by calling the success continuation with the value and a failure continuation. The failure continuation is the "complaint department": if some future of the computation does not like the tendered value, it may call the failure continuation with no arguments to demand a different result. (In section 4.3 we used a returned value of #f as a failure indication. In section 4.2.2 we used success and failure continuations. The use of success and failure continuations is more flexible and can be expanded to include information about why the value was rejected.)
|
||
|
||
So the general pattern of an execution procedure will be:
|
||
|
||
```
|
||
(lambda (environment succeed fail)
|
||
;; succeed = (lambda (value fail)
|
||
```
|
||
|
||
```
|
||
;; Try this value.
|
||
;; if don't like it (fail).
|
||
;; ...)
|
||
;; fail = (lambda () ...)
|
||
...
|
||
;; Try to make a result. If cannot, (fail).
|
||
...)
|
||
```
|
||
|
||
The transformation to continuation-passing style is a bit unpleasant, as it expands the code considerably, but it is basically mechanical. For example, the analyze-application procedure on page 260 is:
|
||
|
||
```
|
||
(define (analyze-application expression)
|
||
(let ((operator-exec (analyze (operator expression)))
|
||
(operand-execs (map analyze (operands expression))))
|
||
(lambda (environment)
|
||
(x:apply (x:advance (operator-exec environment))
|
||
operand-execs
|
||
environment))))
|
||
```
|
||
|
||
<span id="page-44-0"></span>If we transform this code to continuation-passing style we get: [23](#page-74-1)
|
||
|
||
```
|
||
(define (analyze-application exp)
|
||
(let ((operator-exec (analyze (operator exp)))
|
||
(operand-execs (map analyze (operands exp))))
|
||
(lambda (env succeed fail)
|
||
(operator-exec env
|
||
(lambda (operator-value fail-1)
|
||
(a:advance operator-value
|
||
(lambda (procedure fail-2)
|
||
(a:apply procedure
|
||
operand-execs
|
||
env
|
||
succeed
|
||
fail-2))
|
||
fail-1))
|
||
fail))))
|
||
```
|
||
|
||
This execution procedure is more complicated than the one it was derived from. In the body of the original execution procedure, the expression (operator-exec environment) returns a value to the expression (x:advance ...), which in turn returns a value to the expression (x:apply). In the new execution procedure, these
|
||
|
||
nested expressions are gone. Each procedure "returns" by calling a procedure that accepts the results of its computation.
|
||
|
||
Since we will often have to force a value, it is appropriate to make an abstraction that captures the forcing. The procedure executestrict hides the uninteresting details associated with the process of forcing the evaluation of a postponed expression in order to ensure an unpostponed value. In analyze-application above, it is used to force the value of the operator in order to get an applicable procedure.
|
||
|
||
```
|
||
(define (execute-strict executor env succeed fail)
|
||
(executor env
|
||
(lambda (value fail-1)
|
||
(a:advance value succeed fail-1))
|
||
fail))
|
||
```
|
||
|
||
The procedure execute-strict calls the given execution procedure (executor). The result of that is then passed to a:advance to be forced. The forced value is then passed to the success continuation (succeed) of execute-strict, effectively returning the result of the forcing to the caller of execute-strict.
|
||
|
||
Using execute-strict we can rewrite analyze-application:
|
||
|
||
```
|
||
(define (analyze-application exp)
|
||
(let ((operator-exec (analyze (operator exp)))
|
||
(operand-execs (map analyze (operands exp))))
|
||
(lambda (env succeed fail)
|
||
(execute-strict operator-exec
|
||
env
|
||
(lambda (procedure fail-2)
|
||
(a:apply procedure
|
||
operand-execs
|
||
env
|
||
succeed
|
||
fail-2))
|
||
fail))))
|
||
```
|
||
|
||
Each of the execution procedures has to be transformed in this way. We use execute-strict in analyze-if to force the value of the predicate of the conditional, without which we cannot proceed:
|
||
|
||
```
|
||
(define (analyze-if exp)
|
||
(let ((predicate-exec (analyze (if-predicate exp)))
|
||
(consequent-exec (analyze (if-consequent exp)))
|
||
(alternative-exec (analyze (if-alternative exp))))
|
||
(lambda (env succeed fail)
|
||
(execute-strict predicate-exec
|
||
env
|
||
(lambda (pred-value pred-fail)
|
||
((if pred-value
|
||
consequent-exec
|
||
alternative-exec)
|
||
env succeed pred-fail))
|
||
fail))))
|
||
```
|
||
|
||
Most of the transformations are straightforward, and we will not burden you with the details in this text. But there is an interesting case: assignments. Often in backtracking systems we need two different kinds of assignment. The usual permanent assignment, set!, is useful for accumulating information during a search process, such as how many times a particular branch is investigated. There is also an undoable assignment maybe-set! that must be undone if the branch it is on is retracted. The usual permanent assignment is implemented as:
|
||
|
||
```
|
||
(define (analyze-assignment exp)
|
||
(let ((var (assignment-variable exp))
|
||
(value-exec (analyze (assignment-value exp))))
|
||
(lambda (env succeed fail)
|
||
(value-exec env
|
||
(lambda (new-val val-fail)
|
||
(set-variable-value! var new-val env)
|
||
(succeed 'ok val-fail))
|
||
fail))))
|
||
```
|
||
|
||
The undoable assignment is more complex. The failure continuation passed with the successful assignment reverts the value of the assigned variable to its previous value.
|
||
|
||
```
|
||
(define (analyze-undoable-assignment exp)
|
||
(let ((var (assignment-variable exp))
|
||
(value-exec (analyze (assignment-value exp))))
|
||
(lambda (env succeed fail)
|
||
(value-exec env
|
||
(lambda (new-val val-fail)
|
||
```
|
||
|
||
```
|
||
(let ((old-val
|
||
(lookup-variable-value var env)))
|
||
(set-variable-value! var new-val env)
|
||
(succeed 'ok
|
||
(lambda ()
|
||
(set-variable-value! var
|
||
old-val
|
||
env)
|
||
(val-fail)))))
|
||
fail))))
|
||
```
|
||
|
||
The only other interesting case is the implementation of amb itself. Here is where we have to select the next alternative if the last one tendered is rejected. This is done by the failure continuation for the current alternative:
|
||
|
||
```
|
||
(define (analyze-amb exp)
|
||
(let ((alternative-execs
|
||
(map analyze (amb-alternatives exp))))
|
||
(lambda (env succeed fail)
|
||
(let loop ((alts alternative-execs))
|
||
(if (pair? alts)
|
||
((car alts) env
|
||
succeed
|
||
(lambda ()
|
||
(loop (cdr alts))))
|
||
(fail))))))
|
||
```
|
||
|
||
If there are no alternatives left, the execution procedure for amb calls the failure continuation it was called with. This makes the program execute a depth-first search of the tree of alternatives. The alternatives are examined by cdring down the list of alternatives; thus the search proceeds in left-to-right order. [24](#page-74-2)
|
||
|
||
<span id="page-47-0"></span>Except for adjustments to the read-eval-print loop (page 246) to make it work with the continuation-passing structure, that is all there is to it!
|
||
|
||
## **Exercise 5.17: A puzzle**
|
||
|
||
Formalize and solve the following puzzle using amb:
|
||
|
||
Two women (Alyssa and Eva) and four men (Ben, Louis, Cy, and Lem) are seated at a round table, playing cards. Each has a hand; no two of the hands are equally strong.
|
||
|
||
- Ben is seated opposite Eva.
|
||
- The man at Alyssa's right has a stronger hand than Lem has.
|
||
- The man at Eva's right has a stronger hand than Ben has.
|
||
- The man at Ben's right has a stronger hand than Cy has.
|
||
- The man at Ben's right has a stronger hand than Eva has.
|
||
- The woman at Lem's right has a stronger hand than Cy has.
|
||
- The woman at Cy's right has a stronger hand than Louis has.
|
||
|
||
What is the arrangement at the table? Is it unique up to rotation of the table?
|
||
|
||
Use amb to specify the alternatives that are possible for each choice. Also determine how many solutions there are if we are not told that "The man at Ben's right has a stronger hand than Cy has," but rather that "The man on Ben's right is not Cy." Explain this result.
|
||
|
||
<span id="page-48-0"></span>Note: The most straightforward solution is slow; it takes a few hours on a laptop (2017). However, there is a clever solution that converges in only about 2 minutes. [25](#page-74-3)
|
||
|
||
## **Exercise 5.18: Failure detection**
|
||
|
||
Implement a new construct called if-fail that permits a program to catch the failure of an expression. if-fail takes two expressions. It evaluates the first expression as usual, and returns its value as usual if the evaluation succeeds. If the evaluation fails, however, the value of the second expression is returned, as in the following example:
|
||
|
||
```
|
||
(if-fail (let ((x (amb 1 3 5)))
|
||
(require (even? x))
|
||
x)
|
||
```
|
||
|
||
```
|
||
'all-odd)
|
||
all-odd
|
||
(if-fail (let ((x (amb 1 3 4 5)))
|
||
(require (even? x))
|
||
x)
|
||
'all-odd)
|
||
4
|
||
```
|
||
|
||
Hint: This is trivial!
|
||
|
||
## **Exercise 5.19: Assignment**
|
||
|
||
What are the results of the following evaluations, where if-fail is as specified in exercise 5.18?
|
||
|
||
```
|
||
(let ((pairs '()))
|
||
(if-fail (let ((p (prime-sum-pair '(1 3 5 8) '(20 35
|
||
110))))
|
||
(set! pairs (cons p pairs))
|
||
(amb))
|
||
pairs))
|
||
(let ((pairs '()))
|
||
(if-fail (let ((p (prime-sum-pair '(1 3 5 8) '(20 35
|
||
110))))
|
||
(maybe-set! pairs (cons p pairs))
|
||
(amb))
|
||
pairs))
|
||
```
|
||
|
||
### You may use the following definitions:
|
||
|
||
```
|
||
(define (prime-sum-pair list1 list2)
|
||
(let ((a (an-element-of list1))
|
||
(b (an-element-of list2)))
|
||
(require (prime? (+ a b)))
|
||
(list a b)))
|
||
(define (an-element-of lst)
|
||
(if (null? lst)
|
||
(amb)
|
||
(amb (car lst)
|
||
(an-element-of (cdr lst)))))
|
||
(define (prime? n)
|
||
```
|
||
|
||
```
|
||
(= n (smallest-divisor n)))
|
||
(define (smallest-divisor n)
|
||
(define (find-divisor test-divisor)
|
||
(cond ((> (square test-divisor) n) n)
|
||
((divides? test-divisor n) test-divisor)
|
||
(else (find-divisor (+ test-divisor 1)))))
|
||
(define (divides? a b)
|
||
(= (remainder b a) 0))
|
||
(find-divisor 2))
|
||
```
|
||
|
||
## **Exercise 5.20: Choice ordering**
|
||
|
||
The amb mechanism, as written, always tries the choices in the order given in the amb expression. But sometimes we can use contextual information to make a better ordering. For example, in a board game the choice of a move from the possible legal moves should depend on the state of the game board. Let's invent a version of amb that can give us this kind of flexibility. Let's assume that each choice expression is paired with a numerical weight expression:
|
||
|
||
```
|
||
(choose (<weight-1> <choice-1>) ... (<weight-n> <choice-n>))
|
||
```
|
||
|
||
We can evaluate all the weight expressions and use them to choose the next choice expression to be evaluated and returned. Of course, after a choice is made, it is exhausted, and if a failure gets back to this choose form, the remaining weight expressions must be reevaluated before making the next choice.
|
||
|
||
- **a.** Implement choose so that a choice with the largest weight is chosen.
|
||
- **b.** In real situations the weights are usually not strong enough to make a unique choice. Sometimes a good strategy is to make a random choice with probability that is proportional to the computed weights. Implement an alternative chooser pchoose, with the same syntax as choose, that works in this way.
|
||
|
||
## **5.5 Exposing the underlying continuations**
|
||
|
||
Now we are in a position to deal with real magic!
|
||
|
||
Most languages, including Scheme, are organized around the notion of an expression. An expression has a value that it "returns." An expression is made up of subexpressions, each of which has a value that it returns to the bigger expression it is a part of. What is the essential idea of an expression?
|
||
|
||
Consider the compound expression
|
||
|
||
```
|
||
(+ 1 (* 2 3) (/ 8 2))
|
||
```
|
||
|
||
Of course, this has the value 11. It is computed by evaluating the operator and the operands, then applying the value of the operator (the procedure) to the values of the operands (the arguments).
|
||
|
||
This process can be clarified by reformulating the computation in *continuation-passing style*. Here we invent new operators \*\*, //, and ++ to name the continuation-passing style multiplication, division, and addition procedures:
|
||
|
||
```
|
||
(define (** m1 m2 continue)
|
||
(continue (* m1 m2)))
|
||
(define (// n d continue)
|
||
(continue (/ n d)))
|
||
(define (++ a1 a2 continue)
|
||
(continue (+ a1 a2)))
|
||
```
|
||
|
||
These procedures differ from the usual \*, /, and + in that they do not return to their caller; rather they are defined to call their last argument with the value computed. The argument that receives the value is called the *continuation* procedure. We used continuationpassing style in sections 4.2.2 and 5.4.2 and also in the unifier on page 188.
|
||
|
||
The computation of (+ 1 (\* 2 3) (/ 8 2)) in continuationpassing style looks like:
|
||
|
||
```
|
||
(** 2 3
|
||
(lambda (the-product) ; A
|
||
(// 8 2
|
||
(lambda (the-quotient) ; B
|
||
(++ 1 the-product the-quotient
|
||
k)))))
|
||
```
|
||
|
||
<span id="page-52-0"></span>where k is the final continuation procedure, which takes one argument, which is the value 11 of the computation. [26](#page-74-4)
|
||
|
||
In this example the procedure \*\* computes the product of 2 and 3 and calls its continuation procedure (the lambda expression labeled by comment A) with 6. Thus, in the body of A, the-product is bound to 6. In the body of A the procedure // computes the quotient of 8 and 2 and passes the resulting 4 to the procedure labeled B, where the-quotient is bound to 4. In the body of B the procedure ++ computes the sum of 1, 6, and 4, and passes the resulting 11 to the continuation procedure k.
|
||
|
||
In continuation-passing style there are no nested expressions that return values. All results are passed to continuation procedures. Thus, there is no need for a stack, because there is nobody waiting for the value returned! Instead, we have linearized our expression tree in the same way that a compiler must in order to compute the value of the expression in a sequential machine.
|
||
|
||
#### **Underlying continuations**
|
||
|
||
The idea is that the slot in the expression that contains the subexpression is just syntactic sugar for a procedure that accepts the value of the subexpression for later use in continuing the evaluation of the expression. This idea is very powerful, because the continuation represents the entire future of the computation. This deeper understanding of the meaning of an expression allows us to escape from the single-valued expression style of programming, at the considerable cost of complexity and syntactic nesting.
|
||
|
||
Whenever an expression is evaluated, a continuation exists that expects the result of the expression. If the expression is evaluated at top level, for example, the continuation will take the result, print it
|
||
|
||
on the screen, prompt for the next input, evaluate it, and so on, forever. Most of the time the continuation includes actions specified by user code, as in a continuation that will take the result, multiply it by the value stored in a local variable, add seven, and give the answer to the top-level continuation to be printed. Normally these ubiquitous continuations are hidden behind the scenes, and programmers don't think much about them. Scheme provides the ability for a programmer to get the underlying continuation of an expression. An underlying continuation is a first-class object that can be passed as an argument, returned as a value, and incorporated into a data structure. Most other languages do not support the use of first-class continuations. (Languages that do have them include SML, Ruby, and Smalltalk.)
|
||
|
||
Explicit underlying continuations are one of the most powerful (and most dangerous) tools of a programmer. Continuations give the programmer explicit control over time. A computation can be captured and suspended at one moment and restored and continued at any future time. This makes it possible to write coroutines (cooperative multitasking), and with the addition of a timer interrupt mechanism we get timesharing (preemptive multitasking). On the occasions that you may need to deal explicitly with continuations, Scheme lets you do so by creating an explicit procedure that is the current continuation. But before we can take charge of this power we need a deeper understanding of continuations.
|
||
|
||
<span id="page-53-0"></span>A continuation is a captured control state of a computation. [27](#page-74-5) If a continuation is invoked, the computation continues at the place represented by the continuation. A continuation may represent the act of returning a value of a subexpression to the evaluation of the enclosing expression. The continuation is then a procedure that when invoked returns its argument to the evaluation of the enclosing expression as the value of the subexpression. A continuation can be invoked multiple times, allowing a computation to be resumed at a particular point with different values returned by the continuation. We will see an example shortly.
|
||
|
||
Scheme provides call-with-current-continuation (abbreviated call/cc), which gives access to the continuations that underly expression structure. The argument to call/cc is a procedure that gets the continuation of the call/cc expression as its argument. Again: a continuation is a first-class procedure that takes one argument—the value to be returned when the continuation is called. [28](#page-74-6) Here is a simple example:
|
||
|
||
```
|
||
(define foo)
|
||
(set! foo
|
||
(+ 1
|
||
(call/cc
|
||
(lambda (k)
|
||
;; k is the continuation
|
||
;; of the call/cc expression.
|
||
;; so if we call k with 6
|
||
;; then foo will get the value 11
|
||
(k (* 2 3))))
|
||
(/ 8 2)))
|
||
foo
|
||
11
|
||
```
|
||
|
||
So call/cc calls its argument with the continuation of the call/cc. Not very exciting yet! So far this is no different from the straightforward evaluation of (+ 1 (\* 2 3) (/ 8 2)).
|
||
|
||
But procedures in Scheme have indefinite extent. This is a game changer. Let's save the continuation for reuse.
|
||
|
||
```
|
||
(define bar)
|
||
(define foo)
|
||
(set! foo
|
||
(+ 1
|
||
(call/cc
|
||
(lambda (k)
|
||
(set! bar k)
|
||
(k (* 2 3))))
|
||
(/ 8 2)))
|
||
foo
|
||
11
|
||
```
|
||
|
||
```
|
||
(bar -2)
|
||
foo
|
||
3
|
||
```
|
||
|
||
Wow, look what happened! We saved in bar the future of the computation that ultimately gives a value to foo. When we called that continuation with another value, the assignment of foo was redone, resulting in a different value of foo.
|
||
|
||
#### **5.5.1 Continuations as nonlocal exits**
|
||
|
||
Consider the following simple example of a nonlocal exit continuation (adapted from the Scheme report [109]):
|
||
|
||
```
|
||
(call/cc
|
||
(lambda (exit)
|
||
(for-each (lambda (x)
|
||
(if (negative? x) (exit x)))
|
||
'(54 0 37 -3 245 -19)) ; **
|
||
(exit #t)))
|
||
-3
|
||
```
|
||
|
||
Because Scheme's for-each procedure walks the list in left-to-right order, the first negative element encountered is -3, which is immediately returned. Had the list contained no negative numbers, the result would have been #t (since the body of the outer lambda expression is a sequence of two expressions, the for-each expression followed by returning #t).
|
||
|
||
The use of call/cc might appear within some other expression, as in the following definition. (Traditionally, a symbol bound to an underlying continuation starts with the letter k.)
|
||
|
||
```
|
||
(define (first-negative list-of-numbers)
|
||
(call/cc
|
||
(lambda (k exit)
|
||
(or (call/cc (lambda (k shortcut)
|
||
(for-each (lambda (n)
|
||
(cond ((not (number? n))
|
||
(pp '(not-a-number:
|
||
,n))
|
||
(k exit #f))
|
||
((negative? n)
|
||
```
|
||
|
||
```
|
||
(k shortcut n))
|
||
(else
|
||
'keep-looking)))
|
||
list-of-numbers)
|
||
#f))
|
||
'no-negatives-found))))
|
||
```
|
||
|
||
### This behaves as follows:
|
||
|
||
```
|
||
(first-negative '(54 0 37 -3 245 -19))
|
||
-3
|
||
(first-negative '(54 0 37 3 245 19))
|
||
no-negatives-found
|
||
(first-negative '(54 0 37 no 245 -19))
|
||
(not-a-number: no)
|
||
#f
|
||
```
|
||
|
||
This demonstrates nested continuations, where the outermost k exit continuation exits the entire call to first-negative while the inner k shortcut continuation exits only to the enclosing disjunction, then continues from there.
|
||
|
||
In short, if a continuation captured by call/cc is ever invoked with some value, then the computation will continue by returning that value as the value of the call to call/cc that captured it and resuming execution normally from there.
|
||
|
||
### **Exercise 5.21: Nonlocal exits**
|
||
|
||
This exercise is to be done in the native Scheme, where it will be easier to debug and instrument than in our embedded interpreter. There is a good implementation of call/cc in the native Scheme.
|
||
|
||
<span id="page-56-0"></span>**a.** Define a simple procedure, snark-hunt, [29](#page-74-7) that takes a tree as its argument and recursively descends the tree looking for the symbol snark at any leaf. It should immediately stop searching and return #t if one is found; #f otherwise. Use call/cc. For example:
|
||
|
||
```
|
||
(snark-hunt '(((a b c) d (e f)) g (((snark . "oops") h) (i
|
||
. j))))
|
||
#t
|
||
```
|
||
|
||
Note that the input to snark-hunt may not be composed solely of proper lists.
|
||
|
||
**b.** How might you verify that snark-hunt exits immediately rather than silently returning through multiple return levels? Define a new procedure, snark-hunt/instrumented, to demonstrate this.
|
||
|
||
Hint: Setting an exit status flag, then signaling an error on wayward return paths might work if placed carefully, but simply tracing via pp may be easier. Any quick and dirty hack that works will do. The goal here is to build your intuition about continuations, not to ship product-quality code. Briefly explain your strategy.
|
||
|
||
#### **5.5.2 Nonlocal transfer of control**
|
||
|
||
The preceding was somewhat simplistic, because the continuations captured were used only for nonlocal exits. But continuations are more powerful than that: they can be reentered once invoked. The following example illustrates the idea: [30](#page-74-8)
|
||
|
||
```
|
||
(define the-continuation #f)
|
||
(define (test)
|
||
(let ((i 0))
|
||
;; The argument to call/cc assigns the
|
||
;; continuation produced by call/cc to the
|
||
;; global variable the-continuation.
|
||
(call/cc (lambda (k) (set! the-continuation k)))
|
||
;; When the-continuation is called, execution
|
||
;; resumes here.
|
||
(set! i (+ i 1))
|
||
i))
|
||
```
|
||
|
||
The behavior is perhaps surprising. The procedure test creates a local variable i initialized to 0. It also creates a continuation representing the control state of returning from the call/cc expression in the body of the let expression and stores that state in
|
||
|
||
the global variable the-continuation. It then increments i and returns i's new value: 1.
|
||
|
||
```
|
||
(test)
|
||
1
|
||
```
|
||
|
||
When the-continuation is called, the call/cc returns to the body of the let expression. Execution proceeds to increment i and return its new value. The continuation can be reused to increment i again and return its new value.
|
||
|
||
```
|
||
(the-continuation 'OK)
|
||
2
|
||
(the-continuation 'OK)
|
||
3
|
||
```
|
||
|
||
(The argument OK is the value of the call/cc; it is ignored by the let body.)
|
||
|
||
We save the continuation in another-continuation, so we can make a new one to be stored in the-continuation by executing test again. The call to test creates another instance of i, which is initialized to 0.
|
||
|
||
```
|
||
(define another-continuation the-continuation)
|
||
(test)
|
||
1
|
||
```
|
||
|
||
This new continuation is independent of the one we saved in another-continuation.
|
||
|
||
```
|
||
(the-continuation 'OK)
|
||
2
|
||
(another-continuation 'OK) ; uses the saved continuation
|
||
4
|
||
```
|
||
|
||
Now consider the following slightly more interesting scenario:
|
||
|
||
```
|
||
(define the-continuation #f)
|
||
(define sum #f)
|
||
```
|
||
|
||
```
|
||
(begin
|
||
(set! sum
|
||
(+ 2 (call/cc
|
||
(lambda (k)
|
||
(set! the-continuation k)
|
||
(k 3)))))
|
||
'ok)
|
||
ok
|
||
sum
|
||
5
|
||
(the-continuation 4)
|
||
ok
|
||
sum
|
||
6
|
||
(the-continuation 5)
|
||
ok
|
||
sum
|
||
7
|
||
```
|
||
|
||
Note carefully how reentering this captured continuation, by calling the-continuation, returns control to the point before the addition and, therefore, before assigning variable sum and returning the symbol ok. This is why invoking it always returns the symbol ok. However, sum is assigned the sum of 2 and the argument we supplied to the-continuation. So when we ask for the value of sum we get that new sum. This demonstrates how to use a captured continuation to proceed from intermediate return points. We will see how this mechanism can be used for backtracking in section 5.5.3.
|
||
|
||
### **5.5.3 From continuations to amb**
|
||
|
||
It turns out that almost anything we want to do, including implementing amb, can be done with just the Scheme native call/cc; let's see how to do that.
|
||
|
||
Indeed, continuations are a natural mechanism for supporting backtracking. A choice can be made, and if that choice turns out to
|
||
|
||
be inappropriate, an alternative choice can be made and its consequences worked out. (Wouldn't we like real life to have this feature!) In our square-root example, the square-root program should return the amb of both square roots, where amb is the operator that chooses and returns one of them, with the option to provide the other if the first is rejected. The receiver can then just proceed to use the given solution; but if at some point the receiver finds that its computation does not meet some constraint, it can fail, causing the amb operator to revise its choice and return with the new choice through its continuation. In essence, the continuation allows the generator of choices to be written as a coroutine that interacts with the receiver/tester of the choices.
|
||
|
||
The heart of the backtracker is amb-list, which takes a sequence of sibling thunks, each representing an alternative value for the amb expression. The thunks are produced by an amb macro, which syntactically transforms amb expressions into amb-list expressions, as follows:
|
||
|
||
```
|
||
(amb e1 ... en) ==>
|
||
(amb-list (list (lambda () e1) ... (lambda () en)))
|
||
```
|
||
|
||
The amb macro (written in portable syntax-rules form) is:
|
||
|
||
```
|
||
(define-syntax amb
|
||
(syntax-rules ()
|
||
((amb exp ...)
|
||
(amb-list (list (lambda () exp) ...)))))
|
||
```
|
||
|
||
### For example:
|
||
|
||
```
|
||
(pp (syntax '(amb a b c) user-initial-environment))
|
||
(amb-list (list (lambda () a) (lambda () b) (lambda () c)))
|
||
```
|
||
|
||
The search maintains a search schedule, an agenda of thunks that can be called when it is necessary for an amb expression to return with a new alternative value. The procedure amb-list first adds the thunks for its alternative values to the search schedule and then yields control to the first pending thunk on the schedule. If there are no alternatives (the expression was just (amb)) then the amblist yields control without adding anything to the search schedule and increments a global counter for auditing the search.
|
||
|
||
```
|
||
(define (amb-list alternatives)
|
||
(if (null? alternatives)
|
||
(set! *number-of-calls-to-fail*
|
||
(+ *number-of-calls-to-fail* 1)))
|
||
(call/cc
|
||
(lambda (k)
|
||
((add-to-search-schedule)
|
||
(map (lambda (alternative)
|
||
(lambda ()
|
||
(within-continuation k alternative)))
|
||
alternatives))
|
||
(yield))))
|
||
```
|
||
|
||
For a particular amb expression the thunks for the alternatives are constructed so as to return from that amb expression, using the continuation, k, captured at the entrance to their enclosing amblist. [31](#page-75-0)
|
||
|
||
<span id="page-61-0"></span>The way to yield control is to retrieve a thunk specifying an alternative, if any, from the search schedule and execute it. The search schedule is both a stack and a queue; we will see why shortly.
|
||
|
||
```
|
||
(define (yield)
|
||
(if (deque-empty? (*search-schedule*))
|
||
((*top-level*) 'no-more-alternatives)
|
||
((pop! (*search-schedule*)))))
|
||
```
|
||
|
||
You may be puzzled by the fact that we call \*top-level\* and add-to-search-schedule to get the procedures that do the work. We also call \*search-schedule\* to get the search schedule object. The reason for this indirection is that these are Scheme *parameter* objects (see page 394). We have defined them this way because we will be dynamically binding them to different values, as will be shown shortly. We initialize the \*search-schedule\* to be empty:
|
||
|
||
```
|
||
(define *search-schedule*
|
||
(make-parameter (empty-search-schedule)))
|
||
```
|
||
|
||
The magic is the call/cc in amb-list. The amb-list (and thus the amb) executes the yield. The continuation of this call/cc, and
|
||
|
||
thus of this amb, is put onto the search schedule for each alternative of this amb. When an alternative popped from the search schedule is executed, its value is returned by whatever amb expression put that alternative into the search schedule.
|
||
|
||
By making the search schedule both a stack and a queue, we can implement both depth-first and breadth-first search, because they differ only in the order of the schedule. This is done by dynamically binding the add-to-search-schedule parameter to the ordering desired, as shown below.
|
||
|
||
The default is depth first:
|
||
|
||
```
|
||
(define add-to-search-schedule
|
||
(make-parameter add-to-depth-first-search-schedule))
|
||
```
|
||
|
||
The following two procedures can be used to control the search order in the execution of a thunk that encapsulates a problem to be solved, by dynamically binding add-to-search-schedule. For an example of their use, see exercise 5.22 on page 293.
|
||
|
||
```
|
||
(define (with-depth-first-schedule problem-thunk)
|
||
(call/cc
|
||
(lambda (k)
|
||
(parameterize ((add-to-search-schedule
|
||
add-to-depth-first-search-schedule)
|
||
(*search-schedule*
|
||
(empty-search-schedule))
|
||
(*top-level* k))
|
||
(problem-thunk)))))
|
||
(define (with-breadth-first-schedule problem-thunk)
|
||
(call/cc
|
||
(lambda (k)
|
||
(parameterize ((add-to-search-schedule
|
||
add-to-breadth-first-search-schedule)
|
||
(*search-schedule*
|
||
(empty-search-schedule))
|
||
(*top-level* k))
|
||
(problem-thunk)))))
|
||
```
|
||
|
||
These procedures also locally reinitialize the \*search-schedule\* and the \*top-level\* by dynamically binding them, providing control in extent rather than scope. If yield finds no more
|
||
|
||
alternatives it can cause this search to terminate and return the value no-more-alternatives to the caller of with-...-firstschedule. For example:
|
||
|
||
```
|
||
(define search-order-demo
|
||
(lambda ()
|
||
(let ((x (amb 1 2)))
|
||
(pp (list x))
|
||
(let ((y (amb 'a 'b)))
|
||
(pp (list x y))))
|
||
(amb)))
|
||
(with-depth-first-schedule search-order-demo)
|
||
(1)
|
||
(1 a)
|
||
(1 b)
|
||
(2)
|
||
(2 a)
|
||
(2 b)
|
||
no-more-alternatives
|
||
(with-breadth-first-schedule search-order-demo)
|
||
(1)
|
||
(2)
|
||
(1 a)
|
||
(1 b)
|
||
(2 a)
|
||
(2 b)
|
||
no-more-alternatives
|
||
```
|
||
|
||
The orderings are implemented in terms of the low-level stack and queue mutators. For depth first the alternatives are put onto the front of the schedule, and for breadth first they are put onto the end of the schedule. In both cases they appear on the schedule in the order in which they were supplied to amb.
|
||
|
||
```
|
||
(define (add-to-depth-first-search-schedule alternatives)
|
||
(for-each (lambda (alternative)
|
||
(push! (*search-schedule*) alternative))
|
||
(reverse alternatives)))
|
||
(define (add-to-breadth-first-search-schedule alternatives)
|
||
(for-each (lambda (alternative)
|
||
```
|
||
|
||
```
|
||
(add-to-end! (*search-schedule*) alternative))
|
||
alternatives))
|
||
```
|
||
|
||
The parameter \*top-level\* is initialized so that when no alternatives are found, the system continues in the read-eval-print loop with the given result. (In the code above, yield passes the symbol no-more-alternatives to the top level.) Note that with-...-first-schedule rebinds \*top-level\*.
|
||
|
||
```
|
||
(define *top-level*
|
||
(make-parameter
|
||
(lambda (result)
|
||
(abort->nearest
|
||
(cmdl-message/active
|
||
(lambda (port)
|
||
(fresh-line port)
|
||
(display "; " port)
|
||
(write result port)))))))
|
||
```
|
||
|
||
#### To start everything up we also need:
|
||
|
||
```
|
||
(define (init-amb)
|
||
(reset-deque! (*search-schedule*))
|
||
(set! *number-of-calls-to-fail* 0)
|
||
'done)
|
||
```
|
||
|
||
And finally, almost every program using amb will need require:
|
||
|
||
```
|
||
(define (require p)
|
||
(if (not p) (amb) 'ok))
|
||
```
|
||
|
||
That is all there is to it! It is amazing what one can do with call/cc. So we do not need to make an embedded system to implement amb (as we did in section 5.4.2), if we have call/cc in our native environment.
|
||
|
||
### **Other ways to try alternatives**
|
||
|
||
If there are multiple possible ways to solve a subproblem, and only some of them are appropriate for solving the larger problem, sequentially trying them as in generate-and-test is only one way to proceed. For example, if some of the choices lead to very long
|
||
|
||
(perhaps infinite) computations in the tester while others may succeed or fail quickly, it is appropriate to allocate each choice to a thread that may run concurrently. This requires a way for threads to communicate and perhaps for a successful thread to kill its siblings. All of this can be arranged with continuations, with the thread-tothread communications organized around transactions.
|
||
|
||
## **Exercise 5.22: Breadth versus depth**
|
||
|
||
Recall the dumb way to find Pythagorean triples (on page 272). We instrument the searcher with a counter of the number of triples tried:
|
||
|
||
```
|
||
(define (a-pythagorean-triple-between low high)
|
||
(let ((i (an-integer-between low high)))
|
||
(let ((j (an-integer-between i high)))
|
||
(let ((k (an-integer-between j high)))
|
||
(set! triples-tested (+ triples-tested 1))
|
||
(require (= (+ (* i i) (* j j))
|
||
(* k k)))
|
||
(list i j k)))))
|
||
(define triples-tested 0)
|
||
```
|
||
|
||
Consider the following experiment. First we try breadth-first search:
|
||
|
||
```
|
||
(begin (init-amb) ; to reset failure counter
|
||
(set! triples-tested 0)
|
||
(with-breadth-first-schedule
|
||
(lambda ()
|
||
(pp (a-pythagorean-triple-between 10 20)))))
|
||
(12 16 20)
|
||
triples-tested
|
||
246
|
||
*number-of-calls-to-fail*
|
||
282
|
||
```
|
||
|
||
And then we try depth-first search:
|
||
|
||
```
|
||
(begin (init-amb)
|
||
(set! triples-tested 0)
|
||
(with-depth-first-schedule
|
||
(lambda ()
|
||
(pp (a-pythagorean-triple-between 10 20)))))
|
||
(12 16 20)
|
||
triples-tested
|
||
156
|
||
*number-of-calls-to-fail*
|
||
182
|
||
```
|
||
|
||
- **a.** Explain the difference in triples-tested between depthfirst and breadth-first search (in rough terms, not the exact counts).
|
||
- **b.** Explain the difference between the number of triples tested and the \*number-of-calls-to-fail\*. Where are the extra failures coming from?
|
||
- **c.** Considering that the breadth-first search does more work, why is the following a-pythagorean-triple-from search not usable under the depth-first search strategy, although it works fine under the breadth-first strategy?
|
||
|
||
```
|
||
(define (a-pythagorean-triple-from low)
|
||
(let ((i (an-integer-from low)))
|
||
(let ((j (an-integer-from i)))
|
||
(let ((k (an-integer-from j)))
|
||
(require (= (+ (* i i) (* j j)) (* k k)))
|
||
(list i j k)))))
|
||
(define (an-integer-from low)
|
||
(amb low (an-integer-from (+ low 1))))
|
||
(with-depth-first-schedule
|
||
(lambda ()
|
||
(pp (a-pythagorean-triple-from 10))))
|
||
```
|
||
|
||
## **Exercise 5.23: Less deterministic nondeterminism**
|
||
|
||
Eva Lu Ator points out that our amb implementation is not as nondeterministic as one might sometimes like. Specifically, given a list of alternatives in an amb form, we always choose the leftmost alternative first, then the second leftmost, and so on, in left-to-right order.
|
||
|
||
She suggests that one might wish to override this choice, say, by going from right to left, or even in random order. Specifically, she would like something like:
|
||
|
||
```
|
||
(with-left-to-right-ordering problem-thunk)
|
||
(with-right-to-left-ordering problem-thunk)
|
||
(with-random-ordering problem-thunk)
|
||
```
|
||
|
||
She's quick to point out that this choice of ordering is independent of the search order (depth-first, breadth-first, or other).
|
||
|
||
- **a.** Under what circumstances might you want an unordered (random) amb? Craft a specific short example to use as a test case in part **b**.
|
||
- **b.** Implement these three choice orders and give an example use of each. For simplicity and uniformity, model your code after that for with-depth-first-schedule, add-to-depth-firstsearch-schedule, etc. Hint: Feel free to use Scheme's built-in random procedure.
|
||
|
||
## **Exercise 5.24: Nesting strategies**
|
||
|
||
We intended that the breadth-first and depth-first search strategies could be arbitrarily nested within searches. Does the nesting of depth-first and breadth-first scheduling work correctly as currently implemented? Specifically, design an experiment that exposes the bug (if there is one) or that demonstrates anecdotally that it does work correctly (if it does). Explain your rationale.
|
||
|
||
This involves crafting experiments that distinguish between depth-first and breadth-first search strategies, then composing them
|
||
|
||
in interesting ways to demonstrate local control over nested searches.
|
||
|
||
Identify a natural class of problems for which this flexibility is useful— not just hacked together to prove a point.
|
||
|
||
## **Exercise 5.25: Undoable assignment**
|
||
|
||
In the embedded interpreter version of amb in section 5.4.2 we showed how to use two kinds of assignment: the usual permanent assignment, indicated by set!, and the undoable assignment, indicated by maybe-set!, which gets undone by backtracking. We can implement a general wrapper for undoable effects in the nativecode implementation of this section:
|
||
|
||
```
|
||
(define (effect-wrapper doer undoer)
|
||
(force-next
|
||
(lambda () (undoer) (yield)))
|
||
(doer))
|
||
(define (force-next thunk)
|
||
(push! (*search-schedule*) thunk))
|
||
```
|
||
|
||
And we can then implement maybe-set! as a macro:
|
||
|
||
```
|
||
(define-syntax maybe-set!
|
||
(syntax-rules ()
|
||
((maybe-set! var val)
|
||
(let ((old-val var))
|
||
(effect-wrapper
|
||
(lambda ()
|
||
(set! var val))
|
||
(lambda ()
|
||
(set! var old-val)))))))
|
||
```
|
||
|
||
Unfortunately, this makes sense only for depth-first search; it makes no sense for breadth-first search. Explain why. Is this fixable?
|
||
|
||
## **Exercise 5.26: Search control in the embedded system**
|
||
|
||
How could we change the embedded system of section 5.4.2, with analysis to combinators that have success and failure continuations, to enable both depth-first search (as it is now) and breadth-first search? Explain your strategy. Make a new implementation that incorporates this ability to control the search order. Note: This is a rather large transformation.
|
||
|
||
## **5.6 Power and responsibility**
|
||
|
||
In this chapter we have seen that we have great power from the Church-Turing universality of computation. We can never complain: "I cannot express this in the language I must use." If we know the tricks of interpretation and compilation we can always escape from the confines of any language because it is always possible to build an appropriate domain-specific language for the problem at hand. The exposition here uses Scheme as the underlying language and builds powerful Lisp-based languages on top of Scheme. The reason we use Lisp syntax here is because it greatly simplifies the exposition of these ideas. (See exercise 5.7 on infix notations. If we had to do this in a language with a complicated syntax the exposition would be many times longer and more tedious.) But the power of interpretation is available in any Turinguniversal language.
|
||
|
||
It is important for future flexibility that the languages we build be simple and general. They must have very few mechanisms: primitives, means of combination, and means of abstraction. We want to be able to extend them as needed and to be able to mix and match the parts of programs. And, most important, when we have multiple languages, each of which is appropriate for some part of a problem, there must be good ways for those languages to interoperate.
|
||
|
||
With great power comes even greater responsibility. Every time we create a language we must also document it so that it can be taught to others. The programs we write today will be read and modified by others in the future. (Indeed, even when we read next year what we wrote last year, we will be very different and we will not remember the details of what we did.) So it is important that we use this power very sparingly, and that when we do so we document the result very carefully. Otherwise we will be leaving an incomprehensible mess for the next programmer (or for ourselves!) to clean up and rewrite. Don't participate in the creation of a "Tower of Babel."
|
||
|
||
The systems that derive from UNIX show both the good and the bad sides of this issue. The commands all have their own languages. If you know about awk and sed and grep you know that each has its own language, including the really ugly and badly defined regularexpression language we discussed in section 2.2. Certainly each of those languages helped make the immediate problems easier to solve. But they do not have a consistent underlying idea that makes them easy to learn and understand. Just think about how the quotation conventions of the shell interact with the quotation conventions of grep and you will appreciate this point. To become a UNIX guru you have to learn lots of nasty special-case stuff. On the other hand, UNIX itself has a wonderfully simple and elegant way to glue stuff together: *streams*. Each of the basic UNIX utilities takes input from streams and puts out streams. They can be connected by piping output streams to input streams. This lesson is very worth contemplating.
|
||
|
||
<span id="page-70-0"></span>[<sup>1</sup>](#page-1-0) But because our eval is a generic procedure, the set of symbols that are defined by eval may be changed easily and even dynamically.
|
||
|
||
<span id="page-70-1"></span>[<sup>2</sup>](#page-2-0) Our interpreter's implementation is made simpler by the use of Scheme as the implementation language. We inherit the Scheme
|
||
|
||
reader, so our syntax is very simple; we inherit tail recursion, so we don't need to pay special care when implementing procedure calls; and we use Scheme procedures as primitives. If we were to choose a different implementation language, for example C, we would have many more issues to contend with. Nevertheless, it is possible to build this kind of interpreter in any language.
|
||
|
||
- <span id="page-71-0"></span>[3](#page-3-0) The use of the g: prefix in g:apply and other names serves to identify those names as specific to this "generic" interpreter. In later sections we introduce different versions of the interpreter, each of which has its own prefix.
|
||
- <span id="page-71-1"></span>[4](#page-4-0) Reals are usually represented in the computer as floating-point numbers. The parts of a Scheme complex number may be integers or rational fractions, as well as reals.
|
||
- <span id="page-71-2"></span>[5](#page-4-1) The understanding of quotation and its relationship to evaluation has deep consequences in analytic philosophy. One good exposition of this is in the 1982 PhD thesis of Brian Cantwell Smith [112].
|
||
- <span id="page-71-3"></span>[6](#page-5-0) A symbol is an atomic object that is named by a string of characters. What makes a symbol interesting is that it is unique: any two instances of a symbol with the same character-string name may be presumed to be identical (they are eq?).
|
||
- <span id="page-71-4"></span>[7](#page-5-1) Many of the Scheme primitives found this way will work, such as car or +. However, primitives that take procedures as arguments, such as map or filter, will not accept nonprimitive procedures (i.e., those created by this interpreter from lambda expressions). This is addressed in exercise 5.5 on page 249.
|
||
- <span id="page-71-5"></span>[8](#page-7-0) The real problem with macros is that they can introduce bindings that can inadvertently conflict with existing bindings, making them referentially opaque. There are several attacks on the referential-opacity problem, leading to the development of Scheme *hygienic* macro systems. See [73, 74, 8, 31]. Also, drastically modifying a language by introducing special forms
|
||
|
||
- makes it harder for a reader to understand a program—the reader must learn the new special forms before reading the program that uses them.
|
||
- <span id="page-72-0"></span>[9](#page-11-0) MIT/GNU Scheme allows a more general syntax for definitions, with recursive expansion of the cadr of the define form (see page 383). We do not do this here.
|
||
- <span id="page-72-1"></span>[10](#page-13-0) We have made a decision here that limits future extension. The fact that we require the procedure parameters to be a list of the same length as the list of operands means that we cannot extend this g:apply handler to allow procedures with optional or rest parameters. So we could not define the traditional Lisp + that takes an unspecified number of arguments and adds them up! But see exercise 5.2.
|
||
- <span id="page-72-2"></span>[11](#page-15-0) In Scheme, a parameter that takes all the arguments after the explicitly declared ones is called a *rest parameter*. If there are explicitly declared parameters we can use an improper list (a chain of pairs in which the last cdr is not the empty list) as our parameter list. For example (lambda (a b . c) ...) is a procedure that takes at least two arguments, which will be bound to a and b; any additional arguments supplied (after the first two) are made into a list that is the value of c. If there are no explicitly declared parameters and just a rest parameter we use a single symbol to be the name of the rest parameter. For example, in Scheme we can write (lambda xs ...) to define a procedure that takes any number of arguments and binds the parameter xs to be the list of arguments.
|
||
- <span id="page-72-3"></span>[12](#page-18-0) Such an infix parser can be found on the website for this book.
|
||
- <span id="page-72-4"></span>[13](#page-18-1) You may notice that this definition of unless differs from that used in many Lisp languages, including standard Scheme [109] and Emacs Lisp.
|
||
- <span id="page-72-5"></span>[14](#page-19-0) Common practice uses the term "lazy evaluation" to mean that the argument's evaluation is postponed and that the result is
|
||
|
||
- memoized. Here we separate those ideas and use lazy to mean just postponed.
|
||
- <span id="page-73-0"></span>[15](#page-21-0) In the original implementations of by-name parameters in Algol-60 these combinations of expression and environment were called *thunks*. Because Scheme programs commonly use procedures with no formal parameters to package an expression to be evaluated later in some other environment, we also call such nullary procedures used in this way *thunks*.
|
||
- <span id="page-73-1"></span>[16](#page-22-0) The procedure advance-memo! also drops the pointer from the postponed object to the environment for its evaluation, allowing that environment to be garbage-collected if there are no other pointers to it.
|
||
- <span id="page-73-2"></span>[17](#page-22-1) An ancient but important paper by Dan Friedman and David Wise, entitled "Cons should not evaluate its arguments"[40], showed how lazy functional programming can be powerful, but is easily obtained using kons rather than cons.
|
||
- <span id="page-73-3"></span>[18](#page-23-0) Scheme [109] provides delay and force for implementing streams. For more information about streams see SICP [1] and SRFI-41 [13].
|
||
- <span id="page-73-4"></span>[19](#page-29-0) This evaluator differs significantly from the previous ones, so as mentioned in footnote 3 on page 236, we use a new prefix (x:, for "eXecution procedure") to identify analogous procedures.
|
||
- <span id="page-73-5"></span>[20](#page-30-0) In Lisp (and so in Scheme) the extraction of the text of the quotation is simple—it is just a cadr—but our intent is to be general enough to accommodate any language syntax. In most languages the extraction of the text of the quotation is much harder.
|
||
- <span id="page-73-6"></span>[21](#page-32-0) In analyze-begin the reduce-right procedure will never use the #f argument because the #f is accessed only if the list of expressions is empty. But that would signal the error Empty sequence before the reduction started.
|
||
|
||
- <span id="page-74-0"></span>[22](#page-41-0) Erik Sandewall's survey [107] of systems that support tools for "nonmonotonic" reasoning gives more context than we can provide here.
|
||
- <span id="page-74-1"></span>[23](#page-44-0) In this evaluator we use the a: prefix (for amb) to distinguish analogous procedures, as explained in footnote 19 on page 260.
|
||
- <span id="page-74-2"></span>[24](#page-47-0) Our implementation of amb is not quite the idea envisioned by McCarthy. His amb is "prescient" in that it will converge to a value even if one of the alternatives diverges. Since our evaluator does a left-to-right, depth-first search of the alternatives, if *e* is an expression that diverges (computes infinitely or signals an error), our (amb *e* 5) diverges; but McCarthy's amb would return 5. This is explained beautifully by William Clinger [21].
|
||
- <span id="page-74-3"></span>[25](#page-48-0) These timings are with the embedded exploratory-behavior interpreter itself interpreted by the underlying Scheme system. If we use the Scheme compiler to compile the embedded interpreter we get a factor of about 30 speed improvement.
|
||
- <span id="page-74-4"></span>[26](#page-52-0) The idea of continuation-passing style was introduced by computer language theorists to clarify the semantics of computer languages. For a complete history of this idea see [103]. In Scheme the continuations underlying subexpressions are exposed as first-class procedures [120, 61, 109].
|
||
- <span id="page-74-5"></span>[27](#page-53-0) This control state is not to be confused with the full state of a system. The full state is all the information required, along with the program, to determine the future of a computation. It includes all of the current values of mutable variables and data. The continuation does not capture the current values of mutable variables and data.
|
||
- <span id="page-74-6"></span>[28](#page-54-0) But note that the Scheme report [109] allows continuations to take any number of arguments.
|
||
- <span id="page-74-7"></span>[29](#page-56-0) See "The Hunting of the Snark," by Lewis Carroll, 1876.
|
||
- <span id="page-74-8"></span>[30](#page-57-0) This example is adapted from Wikipedia [25].
|
||
|
||
<span id="page-75-0"></span>[31](#page-61-0) The use of the MIT/GNU Scheme extension withincontinuation procedure, which here is approximately equivalent to the call (k (alternative)), prevents the capture of pieces of the control stack that are unnecessary for continuing the computation correctly. |