Как реализуется Lexical Scoping?

Question

Пару лет назад я начал писать интерпретатор для небольшого предметно-ориентированного языка, который включал определенные программистом функции.

Сначала я реализовал переменную область видимости, используя простой стек таблиц символов. Но теперь я хочу перейти к правильной лексической области видимости (с опцией замыканий). Кто-нибудь может объяснить структуру данных и алгоритм за лексической областью?

Answer 1

Чтобы получить правильную лексическую область видимости и закрытия в переводчике, все, что вам нужно сделать, это следовать этим правилам:

• В вашем интерпретаторе переменные всегда ищутся в таблице окружения, передаваемой вызывающей стороной или хранящейся как переменная, а не какой-то глобальный env-стек. Подпись вашей операции eval похожа на eval(expression, env) => value,
• Когда интерпретированный код вызывает функцию, среда НЕ передается этой функции. Сигнатура работы вашего приложения функции apply(function, arguments) => value,
• Когда вызывается интерпретируемая функция, среда, в которой оценивается ее тело, является средой, в которой было сделано определение функции, и не имеет никакого отношения к вызывающей стороне. Так что если у вас есть локальная функция, то это замыкание, то есть структура данных, содержащая поля {function definition, env-at-definition-time},

Чтобы расширить этот последний бит в синтаксисе Python-ish:

x = 1
return lambda y: x + y

должно быть выполнено, как если бы это было

x = 1
return make_closure(<AST for "lambda y: x + y">, {"x": x})

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

Answer 2

Существует много разных способов реализации лексического определения объема. Вот некоторые из моих любимых:

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

• Если вам нужны скорости нативного кода, моя любимая техника описана в книге "Создание быстрого карри " Саймона Марлоу и Саймона Пейтона Джонса.

• Если вам нужны скорости встроенного кода, но функции карри не так важны, рассмотрите стиль передачи замыкания.

Answer 3

Прочитайте реализацию Lua 5.0, например.

Answer 4

Нет единственно правильного способа сделать это. Важно четко указать семантику, которую вы хотите предоставить, и тогда будут следовать структуры данных и алгоритмы.

Answer 5

Страуструп реализовал это в первом компиляторе C++ просто с одной таблицей символов на область действия и правилом связывания, которое следовало за пределами области действия, пока не найдено определение. Как именно это работает, зависит от вашей точной семантики. Убедитесь, что вы прибили их в первую очередь.

Кнут в книге "Искусство компьютерного программирования", том 1, дает алгоритм для таблицы символов Кобола, в соответствии с которой определение объема выполняется с помощью ссылок.