recitation 21: more evaluator practice

suppose we change the call in m-apply from:
  (extend-environment (procedure-parameters procedure)
		      (procedure-environment procedure))
  (extend-environment (procedure-parameters procedure)

* does this change how we draw environment diagrams?  how?

  yes, now all frames will hang directly from the global environment.
  the environment pointer of the procedure is ignored.

* write the simplest expression (or set of expressions) you can, which
  evaluate to a different value with the original m-apply versus the
  modified m-apply.

    (define x 5)
    ((lambda (x) x) 2)

  original m-apply --> 2
  modified m-apply --> 5

  NOTE:  the value of the sugared version of this expression:
    (let ((x 2)) x)
  will depend on the implementation of let in the evaluator.  (why?)

(incr! <var> <exp>)

(define x 10)
(incr! x 3)
x --> 13

* change the evaluator to add incr!

* now add decr! does it have to be a special form?

  yes decr! must be a special form.  we can't let the application 
  clause handle this expression, because we don't want to evaluate <var>.

* make a (general) list of the things that need to be changed/added
  when you extend the evaluator to add a new special form.

  - write expression detector, accessor & constructor functions
  - write necessary helper functions 
  - add clause to m-eval
  - modify m-apply or other parts of the evaluator, as necessary

practice using the "named-let" special form:

(let <var> <bindings> <body>)

The <bindings> and <body> are just as in ordinary let, except that
<var> is bound within <body> to a procedure whose body is <body> and
whose parameters are the variables in the <bindings>. Thus, one can
repeatedly execute the <body> by invoking the procedure named <var>.

(let foo ((x 5)) 
  (display x) 
  (if (< x 1) 
      (foo (- x 1))))

* draw an environment diagram for this example.  what variables does
  the procedure foo need access to?
  NOTE: this is one possible solution.  there are other variations 
  that also correctly implement the specified semantics.

* how would you use named-let to iteratively reverse a list?
  (hint: use 2 variables in the <bindings>)

  (let reverse ((rest '(1 2 3 4))
	        (answer '()))
    (if (null? rest)
        (reverse (cdr rest) (cons (car rest) answer))))

* you're asked to add named-let to the evaluator for project 5...

practice using the "letrec" special form:

(letrec ((<var1> <exp1>) (<var2> <exp2>) ... ) <body>)

the <var>s are bound in a new frame to (initially) undefined values.
the <exp>s are evaluated in the resulting environment (in unspecified
order), and bound to the corresponding <var>.  the <body> is evaluated
in the resulting environment, and the value of the last expression in
<body> is returned.  each binding of a <var> has the entire `letrec'
expression as its region, making it possible to define mutually
recursive procedures.

* what does it mean to say that m-eval and m-apply are
  "mutually-recursive procedures"?

  even? calls odd?, and odd? calls even?  the environment 
  for each procedure must contain the definition for the other. 

One restriction on "letrec" is very important: it must be possible to
evaluate each <exp> without assigning or referring to the value of any
<var>. If this restriction is violated, then it is an error. The
restriction is necessary because Scheme passes arguments by value
rather than by name. In the most common uses of `letrec', all the
<exp>s are lambda expressions and the restriction is satisfied

(letrec ((even?
	  (lambda (n)
            (if (zero? n)
                (odd? (- n 1)))))
          (lambda (n)
            (if (zero? n)
                (even? (- n 1))))))
  (even? 5))   

* draw an environment diagram for this example.  what variables do
  the procedures even? and odd? need access to?
* use letrec to create a toy expression with 3 mutually-recursive
  procedures.  show that your expression does not result in an 
  infinite loop.

* you're asked to add letrec to the evaluator for project 5...


* can you rewrite (desugar) a "named-let" using "let"?  

* can you rewrite (desugar) a "named-let" using "letrec"?

(dolist (<var> <lst>) <body>)

<var> is bound to each element in <lst> sequentially and <body> is
executed once for each binding.  the expression returns the value of
the last expression in body for the binding of <var> to the last
element of <lst>.

(dolist (x '(1 2 3 4)) (display (* x x)))

* is dolist a special form?  why or why not?

* change the evaluator to add dolist