Representing Expressions

The evaluator is reminiscent of the symbolic differentiation program discussed in section . Both programs operate on symbolic expressions. In both programs, the result of operating on a compound expression is determined by operating recursively on the pieces of the expression and combining the results in a way that depends on the type of the expression. In both programs we used data abstraction to decouple the general rules of operation from the details of how expressions are represented. In the differentiation program this meant that the same differentiation procedure could deal with algebraic expressions in prefix form, in infix form, or in some other form. For the evaluator, this means that the syntax of the language being evaluated is determined solely by the procedures that classify and extract pieces of expressions.

Here is the specification of the syntax of our language:

$\bullet$ The only self-evaluating items are numbers and strings:

(define (self-evaluating? exp)
  (cond ((number? exp) true)
        ((string? exp) true)
        (else false)))

$\bullet$ Variables are represented by symbols:

(define (variable? exp) (symbol? exp))

$\bullet$ Quotations have the form (quote text-of-quotation):

(define (quoted? exp)
  (tagged-list? exp 'quote))


(define (text-of-quotation exp) (cadr exp))

Quoted? is defined in terms of the procedure tagged-list?, which identifies lists beginning with a designated symbol:

(define (tagged-list? exp tag)
  (if (pair? exp)
      (eq? (car exp) tag)
      false))

$\bullet$ Assignments have the form (set! var value):

(define (assignment? exp)
  (tagged-list? exp 'set!))

(define (assignment-variable exp) (cadr exp))

(define (assignment-value exp) (caddr exp))

$\bullet$ Definitions have the form

(define var value)

or the form

(define (var parameter1$\ \ldots\$parametern)
  body)

The latter form (standard procedure definition) is syntactic sugar for

(define var
  (lambda (parameter1$\ \ldots\$parametern)
    body))

The corresponding syntax procedures are the following:

(define (definition? exp)
  (tagged-list? exp 'define))

(define (definition-variable exp)
  (if (symbol? (cadr exp))
      (cadr exp)
      (caadr exp)))

(define (definition-value exp)
  (if (symbol? (cadr exp))
      (caddr exp)
      (make-lambda (cdadr exp)   ; formal parameters
                   (cddr exp)))) ; body

$\bullet$ Lambda expressions are lists that begin with the symbol lambda:

(define (lambda? exp) (tagged-list? exp 'lambda))

(define (lambda-parameters exp) (cadr exp))

(define (lambda-body exp) (cddr exp))

We also provide a constructor for lambda expressions, which is used by definition-value, above:

(define (make-lambda parameters body)
  (cons 'lambda (cons parameters body)))

$\bullet$ Conditionals begin with if and have a predicate, a consequent, and an (optional) alternative. If the expression has no alternative part, we provide false as the alternative.

(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)
      'false))

We also provide a constructor for if expressions, to be used by cond->if to transform cond expressions into if expressions:

(define (make-if predicate consequent alternative)
  (list 'if predicate consequent alternative))

$\bullet$ Begin packages a sequence of expressions into a single expression. We include syntax operations on begin expressions to extract the actual sequence from the begin expression, as well as selectors that return the first expression and the rest of the expressions in the sequence.

(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))

$\bullet$ 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))

Derived expressions

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 ).

Exercise. 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. Rewrite eval so that the dispatch is done in data-directed style. Compare this with the data-directed differentiation procedure of exercise . (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. 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. 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. Let expressions are derived expressions, because

(let ((var1 exp1) ... (varn expn))
  body)

is equivalent to

((lambda (var1 ... varn)
   body)
 exp1
 $\vdots$
 expn)

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. 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 ) 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. ``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 ) 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  to also support named let.

Exercise. 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. 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.