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.

————————————————————————————————————————————————————————————————————————

We can implement and and or as derived expressions implemented in terms 
of if.

In eval we can handle these analogously to cond expressions:

(define (eval exp env)
  (cond ...
        ...
        ((and? exp) (eval (and->if exp) env))
        ((or? exp) (eval (or->if exp) env))
        ...))

(define (and? exp) (tagged-list? exp 'and))
(define (if? exp) (tagged-list? exp 'and))

;; selectors for the abstract syntax

(define (and-exprs exp) (cdr exp))
(define (or-exprs exp) (cdr exp))

;; despite the procedure name, we only return an if expression for 
;; and and or expressions with more than one sub-expression.

(define (and->if exp)
  (expand-and (and-exprs exp)))

(define (expand-and exprs)
  (if (null? exprs) ;; if empty, return 'true
      'true
      (let ((first (car exprs))
            (rest (cdr exprs)))
        (if (null? rest) ;; with only one subexpression, (and expr) -> expr
            first
            (make-if first
                     (expand-and rest)
                     'false)))))

(define (or->if exp)
  (expand-or (or-exprs exp)))

(define (expand-or exprs)
  (if (null? exprs)
      'false
      (let ((first (car exprs))
            (rest (cdr exprs)))
        (if (null? rest)
            first
            (make-if first
                     first ;; XXX see below
                     (or->if rest))))))

This implementation of and->if is fine, but the implementation of or->if 
is fundamentally flawed, because it can evaluate an expression twice if 
that expression is true.

There are several ways around this.  One is to implement or directly and 
not as a derived expression.  Another is to generate for (or a b) an 
expression which uses the let special form to store the value of a, and 
then tests this value using if, and either returns it, or continues on 
into b.  Unfortunately, there is no way to implement that cleanly here 
with what we have so far, as to introduce a binding into the expression 
would require us to choose a name for that binding, and any name so 
chosen could potentially conflict with a name already existing in the 
expression.

Here instead we implement or as a special form:

(define (eval exp env)
  (cond ...
        ...
        ((and? exp) (eval (and->if exp) env))
        ((or? exp) (eval-or exp env))
        ...))

(define (eval-or exp env)
  (if (null? (or-exprs exp))
      false
      (let ((first-value (eval (car (or-exprs exp)) env)))
        (if (true? first-value)
            first-value
            (eval-or (cdr (or-exprs exp)) env)))))