 % -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input ./6001mac.tex

{\obeyspaces\gdef {\ }}


\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9.2in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Friday, April 17}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 1. Student Presentations}

{\bf Presentation 1:} Give a short summary of the lecture on Java
given by Dr. Steele.  

{\bf Presentation 2:} Write a function {\tt desugar-if} that desugars
an if into a cond.

\vskip .08in

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 2. Applicative Order vs. Normal Order}

Scheme is an applicative order language, which means that before
applying a procedure, scheme evaluates {\bf all} the sub-expressions,
even if some of those sub-expressions will never be used.  For
example, consider the following function:

\beginlisp
(define (try a b)
  (if (= a 0) 1 b))
\endlisp

Using applicative order evaluation, what will be the result of
evaluating the following:

\beginlisp
(try 0 (/ 1 0))   $\Rightarrow$   Divide by Zero Error
\endlisp

Using normal order evaluation, what will be the result of evaluating
the following:

\beginlisp
(try 0 (/ 1 0))   $\Rightarrow$   1
\endlisp

Note that normal-order is (approximately) equivalent to systematically
delaying each argument on a combination and forcing each parameter:

\beginlisp
(try (delay 0) (delay (/ 1 0)))
\null
(define (try a b)
  (if (= (force a) 0) 1 (force b)))
\endlisp

{\large\bf Special forms}

Recall that in Scheme, we cannot use {\tt define} to define any
special-forms (like {\tt while}, {\tt if}, {\tt delay}, {\tt
cons-stream}, etc.), because of the
applicative order.  Consider the definition of {\tt unless}, below.

\beginlisp
(define (unless pred usual exc)
  (if pred exc usual))
\null
(define (safe/ a b)
  (unless (= b 0) (/ a b) 0))
\endlisp

This gives us more flexibility, why not have Scheme be normal-order
(what are the disadvantages of normal-order languages?).

{\large\bf Testing Evalation Order}

Write the function {\tt normal-order?} that returns {\tt \#t} if the
language is normal order and {\tt \#f} if the language is applicative
order.  

\beginlisp
(define (normal-order?)
  (let ((x \#t))
    ((lambda (x) '())  (begin (set! x \#f) '()))
    x))
\endlisp

What does this imply about side-effects in languages with normal-order
evaluation?

{\Large\bf 3. Modifying the Evaluator}

Below is the data abstraction for a thunk, which is a delayed object.
Why do we need to store an environment with the expression?  What
environment is it that we store?

\beginlisp
(define (delay-it exp env) (list 'thunk exp env))
(define (thunk? obj) (tagged-list? obj 'thunk))
(define thunk-exp cadr)
(define thunk-env caddr)
\endlisp

Let's also define a procedure called {\tt actual-value} that will
evaluate an expression, and force the result (to make sure we get a
value back, and not a thunk).

\beginlisp
(define (actual-value exp env)
  (force-it (mc-eval exp env)))
\endlisp

To implement a simple version of normal-order evaluation, we only need
to make a few changes to the evaluator.  We need to change the
application clause of the {\tt cond} in {\tt mc-eval}.

\beginlisp
    ((application? exp)
      (mc-apply (actual-value (operator exp) env)
                (operands exp)
                env))
\endlisp

We also need to change {\tt mc-apply}:

\beginlisp
(define (mc-apply proc args env)
  (cond ((primitive-procedure? proc)
         (apply-primitive-procedure 
            proc
            (list-of-arg-values args env)))
        (else
         (mc-eval (procedure-body proc)
                  (extend-environment
                    (procedure-parameters proc)
                    (list-of-delayed-args args env)
                    (procedure-environment proc))))))
\endlisp

What's left?  Well, we still need to write {\tt force-it}, {\tt
list-of-arg-values}, and {\tt list-of-delayed-args}.

\beginlisp
(define (force-it obj)
  (if (thunk? obj)
      (actual-value (thunk-exp obj) (thunk-env obj))
      obj))
\null
(define (list-of-arg-values exps env)
  (map (lambda (exp) (actual-value exp env)) exps))
\null
(define (list-of-delayed-args exps env)
  (map (lambda (exp) (delay-it exp env)) exps))
\endlisp

{\Large\bf 4. Lazy Lists}

Consider the effect if we define {\tt cons}, {\tt car}, and {\tt cdr}
as follows in our Normal-Order version of Scheme.

\beginlisp
(define (cons x y) (lambda (m) (m x y)))
(define (car z) (z (lambda p q) p)) 
(define (cdr z) (z (lambda p q) q)) 
\endlisp

What will happen when we evaluate the following?
\beginlisp
(define ones (cons 1 ones)) 
\endlisp

Thinking back to streams, what will happen if I evaluate this?
\beginlisp
(define ones (cons-stream ones 1))
\endlisp

But, what do I get in our normal-order Scheme when I evaluate this?
\beginlisp
(define ones (cons ones 1))
\endlisp

What's the difference? 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
