Structure and Interpretation of Computer Programs (72 page)

(define (begin? exp) (tagged-list? exp 'begin))
(define (begin-actions exp) (cdr exp))
(define (last-exp? seq) (null? (cdr seq)))
(define (first-exp seq) (car seq))
(define (rest-exps seq) (cdr seq))

We also include a constructor
sequence->exp
(for use by
cond->if
) that transforms a sequence into a single expression,
using
begin
if necessary:

(define (sequence->exp seq)
  (cond ((null? seq) seq)
        ((last-exp? seq) (first-exp seq))
        (else (make-begin seq))))
(define (make-begin seq) (cons 'begin seq))

¤ A procedure application is any compound expression
that is not one of the above expression types. The
car
of the
expression is the operator, and the
cdr
is the list of operands:

(define (application? exp) (pair? exp))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))

Some special forms in our language can be defined in terms of
expressions involving other special forms, rather than being
implemented directly. One example is
cond
, which can be
implemented as a nest of
if
expressions. For example,
we can reduce the problem of evaluating the expression

(cond ((> x 0) x)
      ((= x 0) (display 'zero) 0)
      (else (- x)))

to the problem of evaluating the following
expression involving
if
and
begin
expressions:

(if (> x 0)
    x
    (if (= x 0)
        (begin (display 'zero)
               0)
        (- x)))

Implementing the evaluation of
cond
in this way
simplifies the evaluator because it reduces the number of special
forms for which the evaluation process must be explicitly specified.

We include syntax procedures that extract the parts of a
cond
expression, and a procedure
cond->if
that transforms
cond
expressions into
if
expressions. A case analysis begins with
cond
and has a list of predicate-action clauses. A clause is an
else
clause if its predicate is the symbol
else
.
¹²

(define (cond? exp) (tagged-list? exp 'cond))
(define (cond-clauses exp) (cdr exp))
(define (cond-else-clause? clause)
  (eq? (cond-predicate clause) 'else))
(define (cond-predicate clause) (car clause))
(define (cond-actions clause) (cdr clause))
(define (cond->if exp)
  (expand-clauses (cond-clauses exp)))
(define (expand-clauses clauses)
  (if (null? clauses)
      'false                          
; no 
else
 clause
      (let ((first (car clauses))
            (rest (cdr clauses)))
        (if (cond-else-clause? first)
            (if (null? rest)
                (sequence->exp (cond-actions first))
                (error "ELSE clause isn't last -- COND->IF"
                       clauses))
            (make-if (cond-predicate first)
                     (sequence->exp (cond-actions first))
                     (expand-clauses rest))))))

Expressions (such as
cond
) that we choose to implement as syntactic
transformations are called
derived expressions
.
Let
expressions are also derived expressions
(see exercise 
4.6
).
¹³

Exercise 4.2.
  
Louis Reasoner plans to reorder the
cond
clauses
in
eval
so that the clause for procedure applications appears
before the clause for assignments. He argues that this will make the
interpreter more efficient: Since programs usually contain more
applications than assignments, definitions, and so on,
his modified
eval
will usually check fewer
clauses than the original
eval
before identifying the type of an
expression.

a. What is wrong with Louis's plan? (Hint: What will
Louis's evaluator do with the expression
(define x 3)
?)

b. Louis is upset that his plan didn't work.
He is willing to go to any lengths to make his evaluator
recognize procedure applications before it checks for most other
kinds of expressions.
Help him by changing the syntax of the evaluated language so that
procedure applications start with
call
. For example, instead of
(factorial 3)
we will now have to write
(call factorial 3)
and instead of
(+ 1 2)
we will have to write
(call + 1 2)
.

Exercise 4.3.
  
Rewrite
eval
so that the dispatch is done in data-directed
style. Compare this with the data-directed
differentiation procedure of
exercise 
2.73
.
(You may use the
car
of a compound expression as the
type of the expression, as is appropriate for the syntax implemented
in this section.)
.

Exercise 4.4.
  
Recall the definitions of the special forms
and
and
or
from chapter 1:

• and
  : The expressions are evaluated from
  left to right. If any expression evaluates to
  false, false is returned; any remaining expressions are not
  evaluated. If all the expressions evaluate to true values, the value
  of the last expression is returned. If there are no expressions then
  true is returned.
  
• or
  : The expressions are evaluated from left to right. If any
  expression evaluates to a true value, that value is
  returned; any remaining expressions are not evaluated. If all
  expressions evaluate to false, or if there are no expressions,
  then false is returned.
  

Install
and
and
or
as new special forms for the evaluator
by defining appropriate syntax procedures and evaluation
procedures
eval-and
and
eval-or
. Alternatively, show how
to implement
and
and
or
as derived expressions.

Exercise 4.5.
  
Scheme allows an additional syntax for
cond
clauses,
(<
test
> => <
recipient
>)
. If <
test
>
evaluates to a true value, then <
recipient
> is evaluated. Its
value must be a procedure of one argument; this procedure is then
invoked on the value of the <
test
>, and the result is returned as
the value of the
cond
expression. For example

(cond ((assoc 'b '((a 1) (b 2))) => cadr)
      (else false))

returns 2.
Modify the handling of
cond
so that it supports this extended
syntax.

Exercise 4.6.
  
Let
expressions are derived expressions, because

(let ((<
var
₁
> <
exp
₁
>) 
...
(<
var
_n
> <
exp
_n
>))
  <
body
>)

is equivalent to

((lambda (<
var
₁
> 
...
<
var
_n
>)
   <
body
>)
 <
exp
₁
>
 ⋮
 <
exp
_n
>)

Implement a syntactic transformation
let->combination
that
reduces evaluating
let
expressions to evaluating combinations of
the type shown above, and add the appropriate clause to
eval
to
handle
let
expressions.

Exercise 4.7.
  
Let*
is similar to
let
, except that the bindings of the
let
variables are performed sequentially from left to right, and each
binding is made in an environment in which all of the preceding
bindings are visible. For example

(let* ((x 3)
       (y (+ x 2))
       (z (+ x y 5)))
  (* x z))

returns 39. Explain how a
let*
expression can be rewritten as a
set of nested
let
expressions, and write a procedure
let*->nested-lets
that performs this transformation. If we
have already implemented
let
(exercise 
4.6
)
and we want to
extend the evaluator to handle
let*
, is it sufficient to add
a clause to
eval
whose action is

(eval (let*->nested-lets exp) env)

or must we
explicitly expand
let*
in terms of non-derived expressions?

Exercise 4.8.
  
“Named
let
” is a variant of
let
that has the form

(let <
var
> <
bindings
> <
body
>)

The <
bindings
> and <
body
> are just as in ordinary
let
, except that <
var
> is bound within <
body
> to a
procedure whose body is <
body
> and whose parameters are the
variables in the <
bindings
>. Thus, one can repeatedly execute the
<
body
> by invoking the procedure named <
var
>. For example,
the iterative Fibonacci procedure (section 
1.2.2
)
can be rewritten using named
let
as follows:

(define (fib n)
  (let fib-iter ((a 1)
                 (b 0)
                 (count n))
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1)))))

Modify
let->combination
of exercise 
4.6
to
also support named
let
.

Exercise 4.9.
  
Many languages support a variety of iteration constructs, such as
do
,
for
,
while
, and
until
. In Scheme,
iterative processes can be expressed in terms of ordinary procedure
calls, so special iteration constructs provide no essential gain in
computational power. On the other hand, such constructs are often
convenient. Design some iteration constructs, give examples of their
use, and show how to implement them as derived expressions.

Exercise 4.10.
  
By using data abstraction, we were able to write an
eval
procedure that is independent of the particular syntax of the language
to be evaluated. To illustrate this, design and implement a new
syntax for Scheme by modifying the procedures in this section, without
changing
eval
or
apply
.

In addition to defining the external syntax of expressions, the
evaluator implementation must also define the data structures that the
evaluator manipulates internally, as part of the execution of a
program, such as the representation of procedures and environments and
the representation of true and false.

For conditionals, we accept anything to be true that is not
the explicit
false
object.

(define (true? x)
  (not (eq? x false)))
(define (false? x)
  (eq? x false))

To handle primitives, we assume that we have available the
following procedures:

• (apply-primitive-procedure <
  proc
  > <
  args
  >)
  applies the given primitive procedure to the argument values in the
  list <
  args
  > and returns the result of the application.
  
• (primitive-procedure? <
  proc
  >)
  tests whether <
  proc
  > is a primitive procedure.
  

These mechanisms for handling primitives are further described in
section 
4.1.4
.

Compound procedures are constructed from parameters, procedure
bodies, and environments using the constructor
make-procedure
:

(define (make-procedure parameters body env)
  (list 'procedure parameters body env))
(define (compound-procedure? p)
  (tagged-list? p 'procedure))
(define (procedure-parameters p) (cadr p))
(define (procedure-body p) (caddr p))
(define (procedure-environment p) (cadddr p))

The evaluator needs operations for manipulating environments. As
explained in section 
3.2
, an environment is a
sequence of frames, where each frame is a table of bindings that
associate variables with their corresponding values. We use
the following operations for manipulating environments:

• (lookup-variable-value <
  var
  > <
  env
  >)
  returns the value that is bound to the symbol <
  var
  > in the
  environment <
  env
  >, or signals an error if the variable is unbound.
  
• (extend-environment <
  variables
  > <
  values
  > <
  base-env
  >)
  returns a new environment, consisting of a new frame in which the
  symbols in the list <
  variables
  > are bound to the corresponding
  elements in the list <
  values
  >, where the enclosing environment is
  the environment <
  base-env
  >.
  
• (define-variable! <
  var
  > <
  value
  > <
  env
  >)
  adds to the first frame in the environment <
  env
  > a new binding that
  associates the variable <
  var
  > with the value <
  value
  >.
  
• (set-variable-value! <
  var
  > <
  value
  > <
  env
  >)
  changes the binding of the variable <
  var
  > in the environment <
  env
  >
  so that the variable is now bound to the value <
  value
  >, or signals
  an error if the variable is unbound.