Metacircular evaluator, implementing the environment

Question

I am trying to implement the Metacircular Evaluator in Scheme according to the well-known book "Structure and Interpretation of Computer Programs" by Harold Abelson and Gerald Jay Sussman.

http://mitpress.mit.edu/sicp/full-text/sicp/book/node79.html, http://mitpress.mit.edu/sicp/full-text/sicp/book/node80.html

Authors suggest to setup environment in this way:

(define (define-variable! var val env)
  (let ((frame (first-frame env)))
    (define (scan vars vals)
      (cond ((null? vars)
             (add-binding-to-frame! var val frame))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (scan (frame-variables frame)
          (frame-values frame))))

(define (setup-environment)
  (let ((initial-env
         (extend-environment (primitive-procedure-names)
                             (primitive-procedure-objects)
                             the-empty-environment)))
    (define-variable! 'true true initial-env)
    (define-variable! 'false false initial-env)
    initial-env))

However, I can’t understand why

(define myenv (setup-environment))

should work as we expect in Scheme, because, as I know, Scheme by default passing variables to function by value, therefore after two times applying “define-variable!” to initial-env, initial-env won't be changed each time, and the setup-environment function will return the value as the extend-environment has returned it.

Where is my mistake in understanding, could you advise, please?

Thank you in advance!

Answer 1

Your question could be a teensy bit more specific, but I believe I understand it.

Specifically, your question appears to be this:

"I'm surprised by the behavior of

(define myenv (setup-environment))
(define-variable! 'a 13 myenv)
(lookup myenv 'a)

Specifically, I would expect it to fail, because Scheme is call-by-value." Is this your question?

If so, then I think I can answer it. Call-by-value doesn't mean that values can't change. It just means that function calls involve passing values from caller to callee. In fact, nearly all languages are call-by-value; this term is widely misunderstood. Java, for instance, is also a call-by-value language.

There's nothing about Scheme, then, that prevents you from changing, or "mutating", a value. In this example, the set-car! call mutates the list that it's referring to. This change is then visible to any piece of code that can "see" this value.

I think your fundamental question really has to do with what "call-by-value" means, and I hope I've shed some light on it.

Answer 2

To understand how this works, first of all you have to understand that the variable initial-env will point to the first frame of the environment, and this reference is never modified. The environment itself is a list of frames, and each frame is a pair of lists, the car of the first frame is the head of the list of variables, and the cdr of the first frame is the head of the list of values.

Once that is clear, you need to be aware of how the procedures scan and add-binding-to-frame! work. Scan will look inside the current frame, in the list of variables, for a variable with the same name as var; if found it will replace the corresponding value in the list of values. If the variable wasn't found, add-binding-to-frame! will add a new variable and a new value at the head of the corresponding lists, updating the frame to point to this new heads. Notice that initial-environment is still pointing to the first frame, and the first frame is still pointing to the heads of its lists of variables and values (but with a new binding).

So you see now, even though initial-env was never changed, the lists it contains were modified in place, therefore adding new variables with their respective values. I believe the best way to understand the whole process is to grab a pen and a paper and to draw, step-by-step, the result of modifying the cons cells involved.