Три вопроса w.r.t. модель среды оценки

Стрелочная нотация SICP немного перегружена. Я процитирую соответствующую часть текста, чтобы понять эту диаграмму.

Объект процедуры — это пара, код которой указывает, что процедура имеет один формальный параметр, а именно x, и тело процедуры (* x x). Средовая часть процедуры является указателем на глобальную среду, поскольку это среда, в которой лямбда-выражение было вычислено для создания процедуры. В глобальный фрейм добавлена ​​новая привязка, которая связывает объект процедуры с квадратом символа. Как правило, define создает определения, добавляя привязки к фреймам.

Итак, давайте разберем каждую стрелку.

1. "глобальная оболочка" → квадрат. Кажется, что эта стрелка просто отмечает квадрат как символ глобальной среды. Примечательно, что эта среда является единственным активным кадром стека с момента вызова define в глобальной среде.

2. "квадрат" → две точки. Эта стрелка указывает на то, что все, что представляют эти две точки, хранится под именем "square", которое находится в глобальной среде.

3. левая точка → "параметры"/"тело". Эта стрелка указывает, что левая точка — это «объект», который, как считается, хранит две части данных: «список формальных параметров» и «тело процедуры».

4. правая точка → квадрат. Эта стрелка указывает, что правая точка содержит «указатель» на глобальную среду.

Эта диаграмма показывает, как символы получают значение в Лиспе. В частности, символ «оценивается» в конкретном «контексте». Контекст — это связанный список «фреймов среды», каждый из которых содержит некоторый набор сопоставлений имя→значение. Чтобы оценить символ, нужно следовать этому связанному списку и вернуть первое значение, которое отображается из имени символа. Схематически примером может быть

"foo" → { "bar" : 3    →  { "foo" : 8 }   →   { "foo" : 10 }
        , "baz" : 4 }

где вычисление foo возвращает 8, «пропуская» первый кадр и находя значение 8 во втором кадре, игнорируя третий кадр. Эта функция игнорирования важна — она предполагает, что некоторые контексты могут иметь имена, которые затеняют значения из более крупных контекстов.

Итак, вся картина здесь указывает на следующее:

1. Вызов define в глобальном контексте добавляет новое сопоставление имя→значение в глобальный фрейм.

2. Сохранение лямбда-объекта хранит две части информации (две точки)

   • Левая точка содержит текст тела лямбды вместе со списком символов, которые следует считать «формальными параметрами».

   • Правая точка содержит ссылку на некоторый кадр стека, который может быть или не быть глобальным кадром, хотя он случайно является глобальным кадром на этом изображении.

Наконец, мы должны поговорить о том, что значит оценивать лямбда. Чтобы вычислить лямбду, вы должны передать ей список значений. Он использует этот список входных значений и сопоставляет их с сохраненным списком формальных параметров, чтобы генерировать новый фрейм среды, который сопоставляет формальные параметры с входными значениями. Затем он оценивает тело лямбда-выражения, используя этот новый фрейм в качестве основного фрейма и связанный фрейм в качестве последующего контекста. Схематически, скажем, square выглядело так

        +--- Formal parameter list
       /   +--- Body of function
       |   |
(left: (x) (* x x))    (right: {global frame})

Затем, когда мы оцениваем его как (square 3), мы создаем новый фрейм, используя 3 и список формальных параметров.

{ "x" : 3 }

и оценить тело. Сначала мы ищем имя *. Поскольку его нет в нашем новом локальном фрейме, мы должны найти его в глобальном фрейме.

"*"   →   { "x" : 3 }   →   { global frame }

Оказывается, оно там существует и является определением умножения. Таким образом, нам нужно передать ему некоторые значения, поэтому мы ищем «x»

"x"   →   { "x" : 3 }   →   { global frame }

поскольку x хранится в локальном фрейме, мы находим его там и передаем 3 и 3 в качестве аргументов найденной нами функции умножения.

Важно то, что локальный фрейм закрывает глобальный фрейм. Это означает, что если бы x также имело значение в глобальном фрейме, мы бы переопределили его в контексте оценки тела square.

Наконец, поскольку меня попросили ответить на этот вопрос в контексте вопросов о том, что такое «переменная», важно отметить, что приведенное выше является очень конкретной реализацией очень конкретной семантики. переменных. На первый взгляд всегда можно сказать, что "переменные в lisp означают, что происходит именно этот процесс". Однако с этим может быть немного сложно работать.

Другая семантика слова «переменная» (которую одобряю я и большая часть математиков) — это идея о том, что переменная в контексте обозначает конкретное, фиксированное, но неизвестное значение в области. Если мы рассмотрим определение лямбда в теле square

(lambda (x) (* x x))

мы видим, что это более или менее предполагаемая семантика этой фразы --- при интерпретации (* x x) мы видим x как некоторое значение (например, число), но о котором мы ничего не знаем. При интерпретации (lambda (x) (* x x)) мы видим, что для того, чтобы понять значение фразы внутри лямбды, мы должны придать ей значение x. Это примерно стандартная семантика переменных и функций, используемая повсеместно.

Проблема заключается в том, что описанная здесь реализация стекового фрейма также легко нарушает эту семантику — на самом деле, в этом примере она делает это очень тонко. В частности: define нарушает семантику. Причина видна в следующем фрагменте кода

(define foo 3)
foo
(define foo 4)
foo

В этом фрагменте мы последовательно оцениваем каждую фразу и видим, что (предположительно "фиксированное, но неизвестное") значение переменной foo меняется со строки 2 на строку 4. Это связано с тем, что define позволяет нам редактировать стек кадр, который живет в контексте, а не просто создает новый контекст, который затеняет старый, как это делает lambda. Это означает, что мы должны рассматривать переменные не как «фиксированные, но неизвестные», а как серию изменяемых слотов, которые не могут гарантировать сохранение своего значения с течением времени — гораздо более сложная семантика, которая, возможно, должна заставить нас называть foo «слотом». " или "назначаемый".

Мы также можем рассматривать это как дырявую абстракцию. Мы хотели бы, чтобы переменные имели стандартную семантику «фиксированная, но неизвестная», но из-за механизма фреймов стека и поведения define мы не полностью придерживаемся этого значения.

И последнее замечание: Лиспы часто дают вам форму под названием let, которую можно использовать для повторения предыдущего примера, не отбрасывая семантику переменных:

(let ((foo 3))
  foo
  (let ((foo 4))
    foo)
  foo)

В этом случае foo в строке 2 принимает значение 3, foo в строке 4 существует в другом контексте переменной и, таким образом, только закрывает foo в строке 2. .. и, таким образом, принимает другое фиксированное значение 4, наконец, foo в строке 5 снова идентично foo в строке 2 и принимает то же значение.

Другими словами, let позволяет нам создавать произвольные локальные контексты (по совпадению, создавая новые кадры стека за кулисами, как и следовало ожидать). Золотое правило, которое позволяет нам знать, что эти семантики безопасны, называется, к сожалению, α-конверсией. Это правило гласит, что если вы переименуете переменную везде и единообразно в пределах одного контекста, то смысл программы не изменится.

Таким образом, предыдущий пример, благодаря α-преобразованию, идентичен по смыслу этому.

(let ((foo 3))
  foo
  (let ((bar 4))
    bar)
  foo)

и, возможно, немного менее запутанно, поскольку нам больше не нужно беспокоиться об эффектах затенения foo.

Так можем ли мы сделать семантику define в Лиспе более безопасной? Что-то вроде. Вы можете представить себе следующее преобразование:

1. Запретить циклические зависимости в наборах определения, например. (define x y) (define y x) запрещено, а (define x 3) (define y x) — нет.
2. Переместите все define в самое начало любого заданного контекста (кадра стека) и расположите их в порядке зависимости.
3. Сделать ошибкой "redefine" любую переменную

Оказывается, это преобразование немного сложное (перемещение кода затруднено, поэтому могут быть циклические зависимости), но если вы устраните некоторые небольшие проблемы, вы увидите, что в любом контексте переменная может принимать только одно фиксированное, но неизвестное значение. ценность.

Вы также обнаружите следующее для хранения --- любая программа следующего, преобразованного вида

(define x ... definition of x ...)
(define y ... definition of y ...)
(define z ... definition of z ...)
... body ...

эквивалентно следующему

(let ((x ... definition of x ...))
  (let ((y ... definition of y ...))
    (let ((z ... definition of z ...))
      ... body ...)))

это еще один способ показать, что наша хорошая, простая семантика «переменная как фиксированная, но неизвестная величина» верна.