-----------------------------------------
Recitation notes #21 for 5/2/2007

Guest instructor: Stephen McCamant
Email:            smcc@mit.edu
http://people.csail.mit.edu/smcc/6.001-sp07/
-----------------------------------------
Adding new primitive procedures

I'm going to give away part of question
1 on project 5: pointing out where you
can add new primitive procedures.

Of course, you aren't limited to
procedures that are built in to DrScheme.
Let's add a not-equals operator.

        (list '!= (lambda (a b) (not (= a b))))

However, something goes wrong when we try
to add a higher-order procedure like
"map". How can we work around this?

        (list 'map (lambda (proc lst)
                     (map (lambda (x) (m-apply proc (list x))) lst)))

Complete code: eval-map.scm
-----------------------------------------
Supporting infix operators

Sometimes when people start using Scheme,
they wish it had infix syntax for
operators, so you could say (3 + 5) rather
than (+ 3 5).

I've made this change in a slightly silly
way to a copy of the metacircular
evaluator. Can you figure out by
experiment what I did?

I just changed the read-eval-print-loop so
that just after reading an input
expression, it swaps the first and second
elements of every list in the tree.

Complete code: eval-infix.scm
-----------------------------------------
Memoization

"Memoization" (note: not a typo for
"memorization") is a the technique of
storing the values of a procedure, so that
if it's ever called with the same
arguments, you can just return the same
result.

We saw how it can be implemented as a
higher-order procedure that makes a
procedure with state:

(define (memoize proc)
  (let ((hist '()))
    (lambda (arg)
      (let ((seen (in-history? arg hist)))
        (if seen
            (value already-there)
            (let ((return (proc arg)))
              (set! hist
                    (insert-history
                     arg return hist))
              return))))))

Memoization can make your code faster by
avoiding the need to repeat computations.
This can happen even without lazy
evaluation: for instance, consider our
slow Fibonacci function:

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

(define fib3
  (memoize
   (lambda (n)
     (if (< n 2)
      1
      (+ (fib3 (- n 1)) (fib3 (- n 2)))))))

Note that it's important that the
recursive calls also be memoized: that's
what improves the asymptotic behavior of
the implementation.

Complete code: memoize.scm
-----------------------------------------
"Hash consing"

Suppose we memoized "cons". Discuss
advantages and disadvantages.

Note I'm assuming you'd do this
consistently: nothing in the system
would ever use a non-memoized cons.
Thus it would be impossible to create
two different cons pairs with the same
contents.

Advantages:

* Saves space; don't have to worry about
making duplicates.

* equal? can now be implemented as eq?

Disadvantages:

* May not save time

* Incompatible with mutation

-----------------------------------------
Laziness: what's it good for?

We saw that lazy evaluation (also called
"normal-order", though it's not normal for
Scheme) evaluates things in a different
order. If your code has side effects, they
may happen differently.

If your program doesn't use side-effects,
and it gives some answer under eager
evaluation, lazy evaluation will give the
same result.

Lazy evaluation is sometimes faster, but
its major advantage is an extreme case of
that: some programs will give a reasonable
result under lazy evaluation but would
just be an infinite loop in regular
Scheme.

We'll see lots of cool examples tomorrow,
but you actually saw one a long time ago.
Remember question 12 from project 2?

A strategy takes a list of #t and #f
values, and returns either #t or #f. For
instance:

(define (guess-last hist)
  (if (null? hist) #t (car hist)))

"skip-most-recent" turns one strategy into
another that looks at all but the first
element of its input.

The procedure "random-choice" takes two
strategies and a probability, and makes a
strategy that chooses randomly between the
two given strategies.

We'd like to write a strategy that returns
the first value 50% of the time, the
second 25% of the time, the third 12.5%,
and so on.

The following implementation works fine
in a lazy evaluator, but gives an
infinite loop in an eager one:

(define (make-backoff)
  (random-choice guess-last
                 (skip-most-recent (make-backoff))
                 0.5))
(define q12-strategy (make-backoff))

Complete code: leval-rand.scm
-----------------------------------------
Extending m-eval: generalized assignment

We've seen it would be nice to have a
single mutation operation that operated
on any kind of expression: it would be
like set! on a variable, like set-car!
if applied to (car x), and so on.

(:= x 5)
same as (set! x 5)

(:= (car x) 5)
same as (set-car! x 5)

(:= (caar x) 5)
same as (set-car! (car x) 5)

(:= (car (last-pair lst) 5)
same as (set-car! (last-pair lst) 5)

(:= (second lst) 8)
changes the second element, of course

How could we implement this? The key idea
is actually a lot like the lazy evaluator:
we need to wrap certain values with
deferred operations.

(define (assignment? exp) (tagged-list? exp ':=))
(define (assignment-lhs exp) (cadr exp))
(define (assignment-rhs exp) (caddr exp))
(define (make-assignment lhs rhs)
  (list ':= var expr))

(define (make-assignable setter get)
  (list 'assignable setter get))
(define (assignable? exp)
  (tagged-list? exp 'assignable))
(define (assignable-get a)
  (third a))
(define (assignable-set! a value)
  ((second a) value))

(define (actual-value val)
  (if (assignable? val)
      (actual-value (assignable-get val))
      val))

(define (eval-assignment exp env)
  (let ((lhs-a (m-eval (assignment-lhs exp) env)))
    (if (not (assignable? lhs-a))
        (error "Not assignable in := :" lhs-a)
        (assignable-set! lhs-a (m-eval (assignment-rhs exp) env)))))

(define (lookup-variable-value var env)
  (let ((binding (find-in-environment var env)))
    (if binding
        (make-assignable
         (lambda (val) (set-binding-value! binding val))
         (binding-value binding))
        (error "Unbound variable -- LOOKUP" var))))

(define (primitive-procedures)
  (list (list 'car (lambda (pair)
                     (make-assignable (lambda (val) (set-car! pair val))
                                      (car pair))))
        (list 'cdr (lambda (pair)
                     (make-assignable (lambda (val) (set-cdr! pair val))
                                      (cdr pair))))
        ...))

Also, you need to add actual-value in
many of the same places as in the lazy
evaluator: the operator in a
combination, the condition in an if, the
final result to be printed, and the
arguments to a primitive procedure.

Complete code: eval-assign.scm