6.001/Recitation 20

Rob Speer

Dynamic scope

It sounds exciting! And dynamic! Actually, it kind of sucks. It's the alternative to lexical scope.

Briefly: lambda expressions are evaluated in the current evaluation environment, not the lambda's enclosing environment. Lambdas are "single bubbles" in the environment model.

Consider this code:

(define circ
  (let ((pi 3))    ; If it's good enough for the Bible, it's good enough for us
    (lambda (r) (* 2 pi r))))

(define (test)
  (let ((pi 4))    ; Then again, if it's good enough for the state of Indiana...
    (circ 5)))

(test)

• What is the value of (test) under lexical scope?
• What is the value of (test) under dynamic scope?
• Write a short procedure that determines what kind of scope is in use: it should return either 'lexical or 'dynamic.

Problem to ponder: How could you make objects (procedures with state) in a dynamically scoped environment?

Interpretation

We can have Scheme be an interpreter for another programming language. We can even take advantage of Scheme's data structures, garbage collection, and other features in that programming language, to make life easier.

What language would be simple enough to implement in Scheme in one recitation? Hmm. It should be functional, like Scheme... and it should have a ridiculously small number of possible operations. This sounds like a job for:

Unlambda

"It's like abstract lambda calculus, without the lambdas"

You can compute anything that you can compute in lambda calculus (and therefore, anything you can compute with a Turing machine) by composing just two functions. This is the premise that Unlambda is built on. In order to make your life just a bit less hellish, though, it provides a few extra functions as well.

The syntax of Unlambda is this: every expression is either a basic function (a lowercase letter like "s" or "k") or an application of one expression to another (a backquote, "`", followed by two expressions). So Unlambda code looks like this:

```s``s``sii`ki

 `k.*``s``s`ks
``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
 `k``s`ksk

The K function ("Konstant") takes two arguments (curried, of course), and returns the first.

(define k
  (lambda (x) (lambda (y) x)))

And the S function ("Substitution") takes three arguments X, Y, and Z, applies both X and Y to Z, and applies X's result to Y's result.

(define s
  (lambda (x)
    (lambda (y)
      (lambda (z)
        ((x z) (y z))))))

The I function is the identity. Useful. But you can build it out of S and K: ``skk.

(define i (lambda (x) x))

.* is a function that acts just like the identity, but prints an asterisk as a side effect. In general, you can do that with a dot followed by any character. r is similar, but prints a newline.

(define (dot-function c)
  (lambda (x)
    (display c)
    x))

(define r
  (lambda (x)
    (newline)
    x))

Unlambda defines a couple more functions, like C for call/cc, but these are all we'll need.

For practical reasons, we'll need some variables holding the symbols for the backquote and the dot, which don't work as literals.

(define backq (string->symbol "`"))
(define dot (string->symbol "."))

The task: given those functions, define (unlambda-eval code), where code is a list of one-character symbols.

The full code is at: http://torg.mit.edu/files/unlambda.scm