Требует ли модель замещения среды - PullRequest
1 голос
/ 11 декабря 2010

Я пишу крошечный оценщик для Схемы.

Мне нужно написать оценщик с моделью замещения, поэтому никакие назначения, подобные set!, использоваться не будут.

Но так как мне все еще нужно хранить примитивные процедуры и переменную user- define d в каком-то месте, нужна ли мне среда? Если да, в чем разница между моделью замещения и моделью среды?

Спасибо.

Ответы [ 2 ]

2 голосов
/ 11 декабря 2010

Нет - для простого оценщика на основе подстановки вам не нужна среда. Это связано с тем, что как только у вас есть привязка (например, когда вы выполняете вызов функции), вы немедленно заменяете имя значением, поэтому нет необходимости сохранять соответствие имени и значения. Фактически, вы можете рассматривать среду как способ избежать накладных расходов, связанных с заменами, кэшируя их и выполняя их позже. См. PLAI для учебника, который следует этому взгляду - фактически, он идет от подстановок к кэшам подстановки , и только позже он меняет терминологию на средах .

Но учтите, что проблема использования set! не связана со всем этим. Когда вы рассматриваете set!, вам сначала нужно понять, о каком уровне set! вы говорите: если это на языке, который вы реализуете , а не в самой реализации, то можно добавить, что при любом изменяемом значении любого типа - например, в Racket вы можете использовать boxes , и этого достаточно для реализации set! в языке. Это традиционно делается в средстве оценки на основе среды, где тип среды изменяется с сопоставления имен на значения и сопоставления имен с местоположениями (реализовано в виде блоков или аналогичного изменяемого значения). Но в этом нет особой необходимости: вы все равно можете сделать это с помощью оценщика на основе подстановок, где эти блоки становятся частью области значений, которую вы подставляете. Чтобы привести конкретный пример, вы можете начать с выражения вроде (используя язык, похожий на схему):

(let ((x 1))
  (begin (set! x 2)
         (set! x 3)))

и вместо 1 вместо x вы должны выделить ячейку, содержащую 1, а затем заменить эту такую ​​же рамку, что приведет к

(begin (set! #<box> 2)
       (set! #<box> 3))

, где два #<box> - это то единственное поле. (Обратите внимание, что это не код реализации, о котором я говорю, а выражения на языке, который вы оцениваете.) Причина, по которой это обычно не делается, состоит в том, что это может сбивать с толку - вам нужно представлять значения в виде блоков которые могут быть заменены, эти поля не являются частью исходной пользовательской программы, но они являются значениями, с которыми должен иметь дело интерпретатор (например, последний #<box> является возвращаемым значением - но это значение, которое вы хотите возвращайте, а не в поле), и вам нужно быть осторожным в отношении идентификатора блока (например, важно, чтобы два поля в приведенном выше поле были одинаковыми для интерпретации первого set! в быть видимым во втором).

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

1 голос
/ 11 декабря 2010

Да, вам по-прежнему нужна среда, потому что, как вы сказали, вам нужно иметь возможность хранить переменные и тому подобное.

Модель подстановки - это способ помочь вам увидеть, как будет оцениваться данная процедура.Например, вы можете определить квадратную функцию

(define (square x) (* x x))

С помощью модели замещения, если вы вызвали

(square 4)

, то вы заменяете 4 на каждое вхождениеx в определении вашей функции, так что

(* 4 4) => 16

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

...