Metacircular evaluator implementing environment
I am trying to implement the Metacircular Evaluator in Scheme according to the famous book The 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
The authors suggest setting up the 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 cannot figure out why
(define myenv (setup-environment))
should work as we expect in the Schema, because as I know the schema by default passes variables to the function by value, so after applying "define-variable!" for initial-env, initial-env will not change every time, and the setup-environment function will return a value when the returning environment returned it.
Where is my error in understanding, can you advise please?
Thank you in advance!
source to share
Your question may be a little more specific, but I believe I understand.
Specifically, your question looks like this:
"I am surprised by the behavior
(define myenv (setup-environment))
(define-variable! 'a 13 myenv)
(lookup myenv 'a)
In particular, I expect it to fail because Scheme is the callsign. "Is that your question?
If so, then I think I can answer it. Calling by value does not mean that values cannot change. It simply means that function calls are associated with passing values from the caller. In fact, almost all languages are default; this term is widely misunderstood. Java, for example, is also the default language.
There is nothing that Scheme does not allow you to change or "mutate" a value. In this example, the call set-car!
mutates the list it refers to. This change is then visible on 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 shed some light on it.
source to share
To understand how this works, first of all you need to understand that the variable initial-env
will point to the first frame of the environment, and this reference will never be changed. The environment itself is a list of frames, and each frame is a pair of lists, the car
first frame is the header of the variable list and the cdr
first frame is the header of the list of values.
Once this becomes clear, you should know how the procedures scan
and work add-binding-to-frame!
. scan
will appear inside the current frame in the variable list for a variable with the same name as var
; if found, it will replace the corresponding value in the list of values. If no variable is found, add-binding-to-frame!
will add a new variable and a new value to the beginning of the corresponding lists, updating the frame to indicate this new chapters. Note that initial-environment
it still points to the first frame, and the first frame still points to the chapters of its variable and value lists (but with a new binding).
So you see now, although it initial-env
has never changed, the lists it contains has been changed in place, so adding new variables with their respective values. I believe that the best way to understand the whole process is to grab a pen and paper and step by step make the result of changing the cells involved.
source to share