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.