6.001:  WEEKLY OUTLINE FOR STAFF
			     Spring 1998
			    Week of Feb. 9

Administration:

1) getting tutorials set up -- 
     problem next week with virtual Monday
      tutorials; psets

2) section lists - finalize with Jill
     find out who has dropped
     get new lists for Wednesday
     take weekly surveys of answers to questions on lab:
       # of people using
          Lab only
          NT only
          Win95 only
          Lunux (standalone)
          Linux/Athena only
          NT+Lab      
          Win95+Lab
          Lunux+Lab (standalone)
          Linux/Athena+Lab
          Other

3) other section problems?

4) answers for psets 3, 4, 6, 7
   pset 3 answers due to LAs next week (organize)



LECTURE, Tuesday, February 10, 1998

THEME:  Processes and the Procedures which direct them.
        Example: Public-Key cryptography

   The goal of this lecture is to provide us with at least one
model of the evolution of a computational process under the direction
of procedures.  As with all models in engineering, the models we will
supply in 6.001 are intrinsically imperfect.  They are approximations
to the behavior that are useful answering particular questions.
Various models will be employed to answer a variety of questions.

The primary model of evaluation to be introduced today is an INFORMAL
substitution model.  It is phrased as a successive reduction model,
reducing expressions to "simpler" expressions naming the same value.
The particular questions that our model is designed to address are
ones about resources:

	How many steps that are performed in the execution of a process?

	How much space is required to execute a process

	It is not concerned with locality of computation, for example.

   There are important caveats here:

	The scale factors for space and steps
	  are not specified in the model 

	The answers to these questions depend critically 
	  on what data and procedures WE CHOOSE to count as
	  primitive.


Here's a definition of the substitution model in more details than you
should show:

The model is based on expression rewrite rules.

   "Elementary expressions" are left alone:
        Elementary expressions are
          numerals, 
          initial names of primitive procedures,
          lambda expressions, naming procedures.

   A name bound by DEFINE:
        Rewrite the name as the value it is associated with by the definition.

   IF: If the evaluation of the predicate expression terminates in 
           a non-false value
        then rewrite the IF expression as 
           the value of the consequent expression,
        otherwise, rewrite the IF expression as 
           the value of the alternative expression.

   Combination -- (<operator> <operand1> ... <operandn>):
       Evaluate the operator expression to get the procedure, 
         and evaluate the operand expressions to get the arguments.
       If the operator names a primitive procedure, 
         do whatever magic the primitive procedure does.
       If the operator names a compound procedure, 
         evaluate the body of the compound procedure 
         with the arguments substituted for the formal
         parameters in the body.  Count internal definitions 
         as part of the body.
              -- watch out for substitution bugs here.


Example evaluation -- see how each rule is worked out...

     (define (fact n)
       (if (= n 1)
	   1
	   (* n (fact (- n 1)))))

     (fact 3)
     ((lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))) 3)
     (if (= 3 1) 1 (* 3 (fact (- 3 1))))
     (if #f 1 (* 3 (fact (- 3 1))))
     (* 3 (fact (- 3 1)))
     (* 3 ((lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))) 2))
     (* 3 (if (= 2 1) 1 (* 2 (fact (- 2 1)))))
     (* 3 (if #f 1 (* 2 (fact (- 2 1)))))
     (* 3 (* 2 (fact (- 2 1))))
     (* 3 (* 2 ((lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))) 1)))
     (* 3 (* 2 (if (= 1 1) 1 (* 1 (fact (- 1 1))))))
     (* 3 (* 2 (if #t 1 (* 1 (fact (- 1 1))))))
     (* 3 (* 2 1))
     (* 3 2)
     6

Alternate orders of evaluation are possible.  Previous rules yield
applicative order.  If instead of the previous rule for combinations we used


   Combination -- (<operator> <operand1> ... <operandn>):
       Evaluate the operator expression to get the procedure.
       If the operator names a primitive procedure,
         evaluate the operands 
         and do whatever magic the primitive procedure does.
       If the operator names a compound procedure, 
         evaluate the body of the compound procedure
         with the operands substituted for the formal
         parameters in the body.  Count internal definitions 
         as part of the body.
              -- watch out for substitution bugs here.


we would get normal-order evaluation.  The orders differ as follows:

Applicative order                 Normal order

((lambda (x) (+ x x)) (* 3 4))    ((lambda (x) (+ x x)) (* 3 4))
((lambda (x) (+ x x)) 12)         (+ (* 3 4) (* 3 4))
(+ 12 12)                         (+ 12 12)
24                                24


This may matter in some cases:

((lambda (x y) (+ x 2)) 3 (/ 1 0))


Scheme is an applicative order language.




Recitation, Wednesday, February 11, 1998

Point out agin the alternate form of procedure defintion syntax and
stress that this is just an abbraviation that hides the lambda.

Talk again about iterative and recursive PROCESSES as opposed
recursive PROCEDURES -- iterative processes really do run in constant
space in scheme (tail recursion) and you can write an infinite loop:

  (define z (lambda () (z)))

(Most other languages do procedure call in a dumb way, that builds up
stack frames unnecessarily.)

Review the definition of Theta(n) notation from the book.

Here is another set of examples, just like the exponentiation sequence
from lecture.  You can use this if you like to review substitution and
give students a change to ask questions:


Linear Recursive:

(define (mul1 n m)
  (if (= n 0)
      0
      (+ m (mul1 (- n 1) m))))


Linear Iterative, with an internal definition:

(define (mul2 n m)
  (define (iter count ans)
    (if (= count 0)
	ans
	(iter (- count 1) (+ m ans))))
  (iter n 0))


Assuming a primitive HALVE, DOUBLE, and EVEN? provides us with a 
  Logarithmic Recursive process.

(define (mul3 n m)
  (cond ((= n 0) 0)
	((even? n)
	 (double (mul3 (halve n) m)))
	(else				;n odd
	 (+ m (mul3 (- n 1) m)))))
       
  Why is this logarithmic in number of operations? in space taken?
  Why is this a "recursive" process?  (Who is waiting for what?)



Write MUL4, an iterative version of MUL3 (under the same assumptions).
This is tricky so be careful.  See A'h-mose, "The Rhind Papyrus,"
Old Egypt Pub. (Heliopolis, BC 1700) for help if needed.

alternatively, do the interative version of exponentiation with
successive squaring (lecture did the recusive version)


Write a program NMULT, which given a positive integer N and a base B
produces the number of multiplications required to compute (expt b n)
using Pingala's algorithm. Show that (nmult n b) <= 2*log2(n), for n
large. Can you describe the function computed by nmult more concisely
than the program itself.


LECTURE, Thursday, Feb. 12

THEME: capturing common patterns of usage with higher-order procedures

Procedural parameters
  SUM as abstraction of PI-SUM and SUM-SQUARES
Expressing general methods, e. g., fixed-points.
Procedures as returned values, e.g., derivative, averaging, newton's method
Generalizing methods: fixed points and integrations
First-class citzenship of programming objects

RECITATION, Friday, Feb 13

Be prepared for bewilderment. After the lecture, students should
realize that they are not programming in Pascal or C.

Stress that building higher order things out of simpler ones by
constructing useful abstractions is an important problem solving
technique, independent of Scheme. The key point is that since
procedures are objects, they can be returned as values, and accepted
as arguments by other procedures and thus are suitable "things" for
such building.

Step through an evaluation like:

((average-damp square) 10)

-> ((lambda (x) (average x (square x))) 10)

-> (average 10 (square 10))

-> (average 10 100)

-> 55

Stress that these are the same evaluation rules.  There's nothing
magical going on here.



			   DRAFT MICROQUIZ


1. The basic reason that Diffie-Hellman key exchange works is that
<blank> can be computed vastly more quickly than <blank>.




2. What is the value of the expression

    (((bop-funs +) square cube) 2)

if we defined BOP-FUNS, SQUARE, and CUBE as follows?

    (define bop-funs
      (lambda (bop)
        (lambda (f g)
          (lambda (x)
            (bop (f x) (g x))))))

    (define (square x) (* x x))

    (define (cube x) (* x x x))