-----------------------------------------
Tutorial notes #10 for 4/30 or 5/1/2007

TA:       Stephen McCamant
Email:    smcc@mit.edu
Location: 36-113A or 36-115
http://people.csail.mit.edu/smcc/6.001-sp07/
-----------------------------------------
Dynamic versus lexical scope

Scheme has "lexical scope", meaning that
the free variables in a procedure are
searched for in the code surrounding the
definition of the procedure. An
alternative rule is "dynamic scope", in
which free variables are looked for in
the environment where the procedure was
called.

Write a procedure that returns the
symbol 'lexical if you evaluate it in
regular Scheme, but would return the
symbol 'dynamic if you evaluated it in a
dynamically-scope variant of Scheme.

(define (test-scope)
  (define x 'lexical)
  (define (func) x)
  (let ((x 'dynamic))
    (func)))

;; OR

(define (test-scope)
  (let ((x 'dynamic))
    ((let ((x 'lexical))
       (lambda () x)))))

;; or many other answers possible


You can use the environment model for
dynamic scope, but your procedures lose
their second bubbles.

-----------------------------------------
Extending m-eval: "while"

For all you recovering C and Java
programmers, let's give Scheme a looping
syntax that looks like what those
languages provide.

(while <cond> <exp1> <exp2> ...)

The rules for evaluating while are as
follows:

1. Evaluate the condition
2. If it's #f, you're done
3. Otherwise, evaluate the <exp>s in
   sequence
4. Go back to step 1

As an example, let's try writing
factorial using while.

(define (fact n)
  (let ((product 1))
    (while (> n 0)
           (set! product (* product n))
           (set! n (- n 1)))
    product))

Next, let's implement it in our
metacircular evaluator. First, we need
some syntax procedures:

(define (while? exp) ...)
(define (while-condition exp) ...)
(define (while-body exp) ...)

(define (while? exp) (tagged-list? exp 'while))
(define (while-condition exp) (cadr exp))
(define (while-body exp) (cddr exp))

We'll add a clause like this to m-eval:

((while? exp) (eval-while exp env))

Now, let's write eval-while:

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

Alternatively, we could implement
"while" as syntactic sugar. What should
it be short for?

(begin
  (define loop
    (lambda ()
      (if <cond>
          (begin
            <exp1> <exp2> ...
            (loop)))))
  (loop))

What would eval-while look like in this
case?

(define (eval-while exp env)
  (m-eval        
   (make-begin (list
     (make-define 'loop
      (make-lambda '() (list
        (make-if
         (while-condition exp)
         (make-begin
          (append
           (while-body exp)
           (list
            (make-application
             'loop '()))))
         #f))))
     (make-application
      'loop '()))) env))

What's one problem with this desugaring?

Bad things will happen if the programmer
is using a variable named "loop"
themselves, since the one the desugaring
defines will shadow it. This is a general
problem with expansions that define
variables.

-----------------------------------------
Extending m-eval: "quasiquote"

Sometimes it's nice to have some data
that's mainly literal, but has small
variable sections, like a form letter.
We'd like to have a construct like
"quote", but with a way of getting out
of the quote and back to Scheme code.

(quote (1 2 3))
-> (1 2 3)

(quasiquote (1 (unquote (+ 1 1)) 3))
-> (1 2 3)

Suppose we have the following syntax
procedures:

(define (quasiquoted? exp)
  (tagged-list? exp 'quasiquote))
(define (text-of-qq exp)
  (cadr exp))

(define (unquoted? exp)
  (tagged-list? exp 'unquote))
(define (body-of-unquote exp)
  (cadr exp))

and the following clause in m-eval:

((quasiquoted? exp)
 (eval-qq (text-of-qq exp) env))

What should eval-qq look like?

(define (eval-qq exp env)
  (cond 
    ((unquoted? exp)
     (m-eval (body-of-unquote exp) env))
    ((list? exp)
     (map (lambda (e)
            (eval-qq e env))
          exp))
    (else exp)))

What do you think the following should
print?

(The answers below are what Scheme really
does; I make no other claim for their
being logical.)

(quasiquote (quote (unquote (+ 1 1))))
;-> (quote 2)

(quasiquote (quasiquote (unquote (+ 1 1))))
;-> (quasiquote (unquote (+ 1 1)))

By the way, real Scheme does have
quasiquote and unquote, though they're
better known by short-hand syntaxes
analogous to ' for quote: ` (backquote,
usually on the same key as ~) for
quasiquote and , (comma) for unquote.

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

(:= (last-pair lst) '())
Could this work?

As mentioned in Gerald's recitation last
week, this would require a significant
change to the evaluator. What kind of
change would be needed?

We'd have to add a new kind of value to
represent a result that can be assigned
to: such values would remember how to
change when they're assigned to, such as
with a procedure. More details in the
forthcoming recitation notes.