path: root/ps03_evalapply/ps.txt

                MASSACHVSETTS INSTITVTE OF TECHNOLOGY
      Department of Electrical Engineering and Computer Science

                          6.945 Spring 2009
                            Problem Set 3

  Issued: Wed. 18 Feb. 2009                    Due: Wed. 25 Feb. 2009

Reading:
    SICP, From Chapter 4: 4.1 and 4.2; (pp. 359--411)
    en.wikipedia.org/wiki/Evaluation_strategy
    www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR44

Code: load.scm, utils.scm, ghelper.scm, 
      syntax.scm, rtdata.scm, interp.scm, repl.scm
      general-procedures.scm
   code is on the class web page... no reason to kill more trees.


Evaluators for Extended Scheme

You will be working with an evaluator system for an extended version
of Scheme similar to the ones described in SICP, Chapter 4.  Without a
good understanding of how the evaluator is structured it is very easy
to become confused between the programs that the evaluator is
interpreting, the procedures that implement the evaluator itself, and
Scheme procedures called by the evaluator.  You will need to study
Chapter 4 through subsection 4.2.2 carefully in order to do this
assignment.

The interpreters in the code that we will work with in this problem
set are built on the generic operations infrastructure we developed in
the last problem set.  (Actually, there is a small change: we specify
a handler with "defhandler" as an alias for "assign-operation".  Also,
we allow handlers to be specified without declaring all of the
arguments, avoiding the need for "any?".)  Indeed, in these
interpreters, unlike the ones in SICP, EVAL and APPLY are generic
operations!  That means that we may easily extend the types of
expressons (by adding new handlers to EVAL) and the types of
procedures (by adding new handlers to APPLY).

Before beginning work on this problem set you should carefully read
the code in interp.scm.  Also, look at the difference between the
ghelper.scm in this problem set and the ghelper.scm in the previous
set.

		    Using the generic interpreter

Download the supplied code to a fresh directory in your computer.
Get a fresh Scheme system, and load the file load.scm:

   (load "<your-code-directory>/load")

Initialize the evaluator:

   (init)

You will get a prompt:

   eval> 

You can enter an expression at the prompt:

   eval> (define cube (lambda (x) (* x x x)))
   cube
   
   eval> (cube 3)
   27

The evaluator code we supplied does not have an error system of its
own, so it reverts to the underlying Scheme error system.  (Maybe an
interesting little project?  It is worth understanding how to make
exception-handling systems!)  If you get an error, clear the error
with two control Cs and then continue the evaluator with "(go)" at the
Scheme.  If you redo "(init)" you will lose the definition of cube,
because a new environment will be made.

   eval> (cube a)
   ;Unbound variable a
   ;Quit!

   (go)

   eval> (cube 4)
   64

   eval> (define (fib n)
            (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
   fib

   eval> (fib 10)
   55

You can always get out of the generic evaluator and get back to the
underlying Scheme system by quitting (with two control Cs).

-------------
Problem 3.1: Warmup

In mathematical text a common abuse of notation is to identify a
tuple of functions with a function that returns a tuple of values.
For example, (written in Lisp prefix form)

 If   (cos 0.6) ==> 0.8253356149096783 
 and  (sin 0.6) ==> 0.5646424733950354

 then we expect

 ((vector cos sin) 0.6) ==> #(0.8253356149096783 0.5646424733950354)

This requires that an extension to APPLY so it can handle Scheme
vectors as a kind of function.  Make this extension; demonstrate it;
show that it interoperates with more conventional code.
-------------


-------------
Problem 3.2: Unbound-variable handling

In Lisps, including Scheme, attempting to evaluate an unbound symbol
is an unbound-variable error.  However, in some algebraic processes it
is sensible to allow an unbound symbol to be a self-evaluating object.
For example, if we generically extend arithmetic to build algebraic
expressions with symbolic values, it is sometimes useful to allow the
following: 

(+ (* 2 3) (* 4 5)) ==> 26

(+ (* a 3) (* 4 5)) ==> (+ (* a 3) 20)

In this case, the symbol "a" is unbound and self-evaluating.  The
operators "*" and "+" are extended to just build expressions when
their arguments are not reducible to numbers.  

Make generic extensions to +, *, -, /, and to EVAL, to allow this kind
of behavior. 

Also augment APPLY to allow literal functions, known only by their
names:

(+ (f 3) (* 4 5)) ==> (+ (f 3) 20)

These extensions to EVAL and APPLY are generally dangerous, because
they hide real unbound-variable errors.  Make them contingent on the
value of a user-settable variable: ALLOW-SELF-EVALUATING-SYMBOLS.
-------------

Much more powerful extensions are available once we accept generic
operations at this level.  For example, we can allow procedures to
have both strict and non-strict arguments.  

   If you don't know what we are talking about here please read 
   the article: http://en.wikipedia.org/wiki/Evaluation_strategy.

If you load the file general-procedures.scm into the underlying
Scheme, after loading (with '(load "load")') the generic interpreter,
you will find that there are extensions that allow us to define
procedures with some formal parameters asking for the matching
arguments to be lazy (or lazy and memoized).  Other undecorated
parameters take their arguments strictly.  These extensions make it
relatively easy to play otherwise painful games.  For example, we may
define the UNLESS conditional as an ordinary procedure:

   ;Quit!

   (load "general-procedures" generic-evaluation-environment)
   ;Loading "general-procedures.scm"... 
   ;Warning: Replacing top-level handler
   ;... done
   ;Value: #[compound-procedure 17 operator]


   (go)

   eval> (define unless
           (lambda (condition (usual lazy) (exception lazy))
	     (if condition exception usual)))

We may use the usual define abbreviations (see syntax.scm):

   eval> (define (unless condition (usual lazy) (exception lazy))
	   (if condition exception usual))
   unless

   eval> (define (ffib n)
	   (unless (< n 2)
		   (+ (ffib (- n 1)) (ffib (- n 2)))
		   n))
   ffib

   eval> (ffib 10)
   55

Notice that UNLESS is declared to be strict in its first argument (the
predicate) but nonstrict in the alternatives: neither alternative will
be evaluated until it is necessary.

Additionally, if we include the file kons.scm we get a special form
that is the non-strict memoized version of CONS.  This immediately
gives us the power of infinite streams:

   ;Quit!

   (load "kons" generic-evaluation-environment)
   ;Loading "kons.scm"... done
   ;Value: #[compound-procedure 19 operator]

   (go)

   eval> (define (add-streams s1 s2)
	   (kons (+ (car s1) (car s2))
		 (add-streams (cdr s1) (cdr s2))))
   add-streams

   eval> (define (ref-stream stream n)
	   (if (= n 0)
	       (car stream)
	       (ref-stream (cdr stream) (- n 1))))
   ref-stream

   eval> (define fibs
	   (kons 0
		 (kons 1
		       (add-streams (cdr fibs) fibs))))
   fibs

   eval> (ref-stream fibs 10)
   55

   eval> (ref-stream fibs 20)
   6765

   eval> (ref-stream fibs 30)
   832040

   eval> (ref-stream fibs 40)
   102334155


-------------
Problem 3.3: Streams

a. The non-strict procedure KONS adds great power to the system.
Notice that there is no need to make CAR or CDR different to obtain
the use of streams.  In a short paragraph explain why KONS is almost
sufficient.  It may be instructive to read an ancient paper by
Friedman and Wise:
   www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR44

b. Unfortunately, the addition of KONS does not, in itself, solve all
stream problems.  For example, the difficulty alluded to in SICP
section 4.2.3 (p. 411) does not automatically dissipate.  If we make
the following definitions:

   (define (map-stream proc items)
     (kons (proc (car items))
	   (map-stream proc (cdr items))))

   (define (scale-stream items factor)
     (map-stream (lambda (x) (* x factor))
		 items))

   (define (integral integrand initial-value dt)
     (define int
       (kons initial-value
	     (add-streams (scale-stream integrand dt)
			  int)))
     int)

   (define (solve f y0 dt)
     (define y (integral dy y0 dt))
     (define dy (map-stream f y))
     y)

and then we try:

   (ref-stream (solve (lambda (x) x) 1 0.001) 1000)

we will get an error (try it!).  Why?  Explain the error.  What other
declarations should be made in these stream-procedure definitions to
fix all such errors?
-------------


-------------
Problem 3.4: Why not?

a. The KONS special form is equivalent to a CONS with both arguments
lazy and memoized.  If the arguments were not memoized the computation
(ref-stream fibs 40) in Problem 3.3a above would take a very long
time.  Is there ever any advantage to not memoizing?  When might it
matter?

b. Why, given that CONS is a strict procedure imported from Scheme,
could we not have defined KONS simply as:

   (define (kons (a lazy memo) (d lazy memo))
     (cons a d))
?

c. More generally, the Lisp community has avoided changing CONS to be
KONS, as recommended by Friedman and Wise.  What potentially serious
problems are avoided by using CONS rather than KONS?  Assume that we
do not care about small constant factors in performance.
-------------


-------------
Problem 3.5: Your turn

Invent some fun, interesting construct that can easily be implemented
using generic EVAL/APPLY that would be rather painful without that
kind of generic support.  Show us the construct, the implementation,
and some illustrative examples.  Enjoy!
-------------