-----------------------------------------
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