\documentstyle[6.001-ps]{article}
\begin{document}
\header{8}{April 20, 1989}
\problem{8.1}
When the procedure returned by \verb+(make-adder 3)+ is actually called,
the evaluator will search for bindings in the caller's environment.
Because \verb+increment+ was not defined in this environment, the
evaluator will not be able to find a value for it and will return
an error.
\problem{8.2}
\bv
(define (macro-definition? exp)
  (if (atom? exp)
      '()
      (eq? (car exp) 'define-macro)))

(define (macro? p)
  (if (atom? p)
      '()
      (eq? (car p) 'macro)))

(define (macro-expand p)
  (cdr p))

(define (eval-macro-definition exp env)
  (define-variable! (macro-def-variable exp)
                    (macro-def-value exp env)
                    env)
  (macro-def-variable exp))

(define (macro-def-variable exp) (caadr exp))

(define (macro-def-value exp env)
  (let ((l (list 'lambda (macro-def-args exp) (macro-def-body exp))))
    (cons 'macro (make-procedure l env))))

(define (macro-def-args exp) (cdadr exp))

(define (macro-def-body exp) (caddr exp))
\end{verbatim}
\problem{8.3}
\bv
(initialize-lisp)
**==>(define-macro (if pred conseq altern)
       (list 'cond
             (list pred conseq)
             (list 'else altern)))
IF 
**==>(define (factorial n)
       (if (= n 0)
           1
           (* n (factorial (- n 1)))))
FACTORIAL 
**==>(factorial 4)
24 
**==>(define-macro (unless pred action alt)
       (list 'if (list 'not pred) action alt))
UNLESS 
**==>(define (factorial n)
       (unless (= n 1)
               (* n (factorial (- n 1)))
               1))
FACTORIAL 
**==>(factorial 4)
24 
**==>
\end{verbatim}
\vbreak
Either \verb+cond+ or \verb+if+ may be used in defining \verb+unless+.
When the \verb+unless+ macro is substituted, the resulting expression
is passed to \verb+mini-eval+.  When another macro (\verb+if+) is seen,
this macro is substituted as well, and everything works correctly.
\problem{8.4 and 8.5}
To test \verb+delay+ and \verb+force+ with the \verb+fibs+ stream,
all of the stream, primitives are needed, so this is the answer
to problems 8.4 and 8.5.
\vbreak
\bv
(define (initialize-lisp)
  (set! the-global-environment (setup-environment))
  (eval-stream-primitives)
  (driver-loop))

(define (eval-stream-primitives)
  (mini-eval '(define-macro (delay exp)
                (list 'lambda '() exp))
             the-global-environment)
  (mini-eval '(define (force delayed-obj)
                (delayed-obj))
             the-global-environment)
  (mini-eval '(define-macro (cons-stream s1 s2)
                (list 'cons s1 (list 'delay s2)))
             the-global-environment)
  (mini-eval '(define (head s)
                (car s))
             the-global-environment)
  (mini-eval '(define (tail s)
                (force (cdr s)))
             the-global-environment)
  (mini-eval '(define the-empty-stream '())
             the-global-environment)
  (mini-eval '(define (empty-stream? s)
                (null? s))
             the-global-environment))

(initialize-lisp)
**==>(define (add-streams s1 s2)
       (cond ((empty-stream? s1) s2)
             ((empty-stream? s2) s1)
             (else
              (cons-stream (+ (head s1) (head s2))
                           (add-streams (tail s1) (tail s2))))))
ADD-STREAMS 
**==>(define fibs
       (cons-stream 0
                    (cons-stream 1
                                 (add-streams (tail fibs) fibs))))
FIBS 
**==>(define (stream-first n s)
       (cond ((> n 1)
              (user-print (head s))
              (stream-first (- n 1) (tail s)))
             ((= n 1)
              (user-print (head s)))))
STREAM-FIRST 
**==>(stream-first 5 fibs)
0 
1 
1 
2 
3 
\end{verbatim}
\problem{8.6}
\bv
**==>(define (verb-tail s)
       (user-print 'force...)
       (tail s))
VERB-TAIL 
**==>(define (verb-add-streams s1 s2)
       (cond ((empty-stream? s1) s2)
             ((empty-stream? s2) s1)
             (else
              (cons-stream (+ (head s1) (head s2))
                           (verb-add-streams (verb-tail s1) (verb-tail s2))))))
VERB-ADD-STREAMS 
**==>(define verb-fibs
       (cons-stream 0
                    (cons-stream 1
                                 (verb-add-streams (verb-tail verb-fibs) verb-fibs))))
VERB-FIBS 
**==>(stream-first 5 verb-fibs)
0 
1 
FORCE... 
1 
FORCE... 
FORCE... 
FORCE... 
2 
FORCE... 
FORCE... 
FORCE... 
FORCE... 
FORCE... 
FORCE... 
3 
**==>
\end{verbatim}
\vbreak
In evaluating the fifth Fibonacci number, \verb+(tail fibs)+ is forced
10 times.
\problem{8.7}
\bv
(define (eval-stream-primitives)
  (mini-eval '(define (memo-proc proc)
                ((lambda (already-run? result)
                   (lambda ()
                     (cond ((not already-run?)
                            (set! result (proc))
                            (set! already-run? (not nil))
                            result)
                           (else result))))
                 nil nil))
             the-global-environment)
  (mini-eval '(define-macro (delay exp)
                (list 'memo-proc (list 'lambda '() exp)))
             the-global-environment)
  (mini-eval '(define (force delayed-obj)
                (delayed-obj))
             the-global-environment)
  (mini-eval '(define-macro (cons-stream s1 s2)
                (list 'cons s1 (list 'delay s2)))
             the-global-environment)
  (mini-eval '(define (head s)
                (car s))
             the-global-environment)
  (mini-eval '(define (tail s)
                (force (cdr s)))
             the-global-environment)
  (mini-eval '(define the-empty-stream '())
             the-global-environment)
  (mini-eval '(define (empty-stream? s)
                (null? s))
             the-global-environment))

(initialize-lisp)
**==>(define (stream-first n s)
       (cond ((> n 1)
              (user-print (head s))
              (stream-first (- n 1) (tail s)))
             ((= n 1)
              (user-print (head s)))))
STREAM-FIRST 
**==>(define (verb-tail s)
       (user-print 'force...)
       (tail s))
VERB-TAIL 
**==>(define (verb-add-streams s1 s2)
       (cond ((empty-stream? s1) s2)
             ((empty-stream? s2) s1)
             (else
              (cons-stream (+ (head s1) (head s2))
                           (verb-add-streams (verb-tail s1) (verb-tail s2))))))
VERB-ADD-STREAMS 
**==>(define verb-fibs
       (cons-stream 0
                    (cons-stream 1
                                 (verb-add-streams (verb-tail verb-fibs) verb-fibs))))
VERB-FIBS 
**==>(stream-first 5 verb-fibs)
0 
1 
FORCE... 
1 
FORCE... 
FORCE... 
2 
FORCE... 
FORCE... 
3 
**==>
\end{verbatim}
\vbreak
In evaluating with \verb+(memo-proc), \verb+(tail fibs) is only forced
5 times.
\end{document}
