Как Лексический Обзор реализован? [закрытый]

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

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

• Если вам нужна скорость машинного кода, моя любимая техника описана в Making a Fast Curry Саймона Марлоу и Саймона Пейтона Джонса.

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

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

Прочитать Например, реализация Lua 5.0 .

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

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

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

x = 1
return lambda y: x + y

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

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

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

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

Кнут в The Art of Computer Programming, Vol 1, приводит алгоритм для таблицы символов Cobol, в которой выборка осуществляется с помощью ссылок.