Метациркулярный оценщик, внедряющий среду

Question

Я пытаюсь внедрить Metacircular Evaluator в Scheme в соответствии с известной книгой Гарольда Абельсона и Джеральда Джея Суссмана "Структура и интерпретация компьютерных программ".

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

Авторы предлагают настроить среду следующим образом:

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

Тем не менее, я не могу понять, почему

(define myenv (setup-environment))

должен работать так, как мы ожидаем в Scheme, потому что, как я знаю, Scheme по умолчанию передает переменные в функции по значению, поэтому после двухкратного применения "define-variable!" к initial-env, initial-env не будет меняться каждый раз, а функция setup-environment будет возвращать значение по мере того, как его возвращает extension-environment.

Где моя ошибка в понимании, не могли бы вы посоветовать, пожалуйста?

Заранее спасибо!

Answer 1

Ваш вопрос может быть немного более конкретным, но я верю, что понимаю его.

В частности, ваш вопрос выглядит так:

"Я удивлен поведением

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

В частности, я ожидал бы, что это потерпит неудачу, потому что Схема является вызовом по значению."Это ваш вопрос?

Если так, то я думаю, что смогу ответить. Вызов по значению не означает, что значения не могут измениться. Это просто означает, что вызовы функций предполагают передачу значений от вызывающего к вызываемому. Фактически, почти все языки являются по значению; этот термин широко понимают неправильно. Java, например, также является языком вызова по значению.

Таким образом, в Схеме нет ничего, что мешало бы вам изменять или "мутировать" значение. В этом примере set-car! Вызов изменяет список, на который ссылается. Это изменение затем видно любому фрагменту кода, который может "увидеть" это значение.

Я думаю, что ваш фундаментальный вопрос действительно имеет отношение к тому, что означает "вызов по стоимости", и я надеюсь, что я пролил некоторый свет на это.

Answer 2

Чтобы понять, как это работает, прежде всего вы должны понять, что переменная initial-env будет указывать на первый кадр среды, и эта ссылка никогда не изменяется. Сама среда представляет собой список кадров, и каждый кадр представляет собой пару списков, car первого кадра является заголовком списка переменных, а cdr первого кадра - заголовок списка значений.

Как только это станет ясно, вы должны знать, как процедуры scan а также add-binding-to-frame! Работа. Scan будет искать в текущем кадре в списке переменных переменную с тем же именем, что и var; если он найден, он заменит соответствующее значение в списке значений. Если переменная не была найдена, add-binding-to-frame! добавит новую переменную и новое значение в заголовки соответствующих списков, обновив кадр так, чтобы он указывал на эти новые заголовки. Заметить, что initial-environment все еще указывает на первый кадр, а первый кадр все еще указывает на заголовки своих списков переменных и значений (но с новой привязкой).

Итак, вы видите сейчас, хотя initial-env не был изменен, списки, которые он содержит, были изменены на месте, поэтому добавлены новые переменные с соответствующими значениями. Я полагаю, что лучший способ понять весь процесс - это взять ручку и бумагу и шаг за шагом нарисовать результат изменения соответствующих клеток.