-----------------------------------------
Tutorial notes #12 for 5/14 or 5/15/2007

TA:       Stephen McCamant
Email:    smcc@mit.edu
Location: 36-113A or 36-115
http://people.csail.mit.edu/smcc/6.001-sp07/
-----------------------------------------
Project 5 debrief

We intended this to be the most
conceptually 'interesting' project, but
it ended up being a bit harder than we'd
planned. (This was the first year we'd
done advice).

Skills this project was intended to
exercise:

- Creating and using new data
abstractions

- Manipulating nested list structures
(representing code)

- Understanding the environment model

- Understanding the metacircular
evaluator, and what happens when you
change it

- Testing changes to a language

Which of these did you find most
difficult?

I noticed a lot of people didn't even
attempt the last problem. Was this just
running out of time, or was it hard to
think about?

I'll have your projects graded as soon
as possible, but no sooner.

-----------------------------------------
Register machine basics

Instructions:
  (assign <reg> <expr>)
  (test <op> <expr>)      Expressions:  
  (goto <expr>)    	    (const <C>) 
  (branch <expr>)	    (reg <R>)   
  (save <reg>)		    (label <L>) 
  (restore <reg>)	    (op <O>)    

How can I swap the values in registers a
and b, using a third register tmp?

(assign tmp (reg a))
(assign a (reg b))
(assign b (reg tmp))


Using the stack?

(save a)
(save b)
(restore a)
(restore b)


How do you do the equivalent of
(set! d (if a b c))?
 
 (test (reg a))
 (branch (label if-true))
 (assign d (reg b)
 (goto (label end))
if-true
 (assign d (reg a))
end


-----------------------------------------
Explicit control evaluator: mysteries

What does the following mystery
evaluation routine implement?

ev-mystery1
  (assign unev (op caddr) (reg exp))
  (assign exp (op cadr) (reg exp))
  (save continue)
  (save env)
  (save unev)
  (assign continue (label label1))
  (goto (label eval-dispatch))
label1
  (restore unev)
  (restore env)
  (test (op true?) (reg val))
  (branch (label label2))
  (assign exp (reg unev))
  (assign continue (label label2))
  (goto (label eval-dispatch))
label2
  (restore continue)
  (goto (reg continue)

;-> "or"

Is mystery1 tail recursive?

;-> No, but you could make it tail recursive if you wanted to.

How about this one:

ev-mystery2
  (assign exp (op cadr) (reg exp))
  (save continue)
  (save env)
  (assign continue (label label3))
  (goto (label eval-dispatch))
label3
  (restore env)
  (restore continue)
  (assign exp (reg val))
  (goto (label eval-dispatch))

;-> "eval" (see last week's tutorial notes)

-----------------------------------------
Explicit control evaluator: while

Recall how we added a "while loop" to
the metacircular evaluator:

(define (eval-while exp env)
  (if (m-eval (while-test exp) env)
      (begin
        (eval-sequence
         (while-body exp) env)
        (eval-while exp env))))

Translate this definition to the EC
evaluator. Remember that eval-sequence
takes the sequence in unev and the
return location on the top of the
stack.

ev-while
  (save continue)
  (assign unev (op while-body) (reg exp))
  (assign exp (op while-test) (reg exp))
while-loop
  (save exp)
  (save unev)
  (save env)
  (assign continue (label after-test))
  (goto (label eval-dispatch))
after-test
  (restore env)
  (restore unev)
  (test (op true?) (reg val))
  (branch (label do-body))
  (restore exp)
  (restore continue)
  (goto (reg continue))
do-body
  (save unev)
  (save env)
  (assign continue (label after-body))
  (save continue)
  (goto (label eval-sequence))
after-body
  (restore env)
  (restore unev)
  (restore exp)
  (goto (label while-loop))
-----------------------------------------
About the final

The final will probably be more than 50%
longer than the quizzes; so expect more
time pressure.

All the material up through and
including the explicit control evaluator
is fair game.

Expect about half of the questions to
include some aspects from after quiz 2;
but earlier material may appear
anywhere.

A collection of old finals are linked to
from the course web site.

You can bring three sheets of notes, and
we'll provided any big code you'll need.

List of key topics:

* Recursion and iteration
* Orders of growth in time and space
* Higher-order procedures
* Data abstraction
* Data structures with pairs
* Trees and graphs
* Mutation
* Procedures with state
* Object-oriented programming
* Evaluators
* The metacircular evaluator
* Lazy evaluation
* Memoization
* Streams
* Register machines
* The explicit control evaluator

Good luck!

-----------------------------------------
Course evaluations

At http://sixweb.mit.edu/
(also linked from course page)

Help us continue to improve 6.001

-----------------------------------------
Cartoon

Lisp and Perl