Каковы основные проблемы при разработке интерпретатора для функционального языка?

Question

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

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

На веб-сайте MIT есть онлайн-копия Structure and Interpretation of Computer Programs, а также videos лекций MIT 6.001 с использованием Схемы, записанных в HP в 1986 году. Они представляют собой отличное введение в языковой дизайн.

Answer 1

Я очень рекомендую Structure and Interpretation of Computer Programs (SICP) в качестве отправной точки. В этой книге будет представлено представление о том, что значит писать интерпретатор (и компилятор) и, как правило, обязательно читать для любого, кто разрабатывает языки.

Внедрение интерпретатора для функционального языка вряд ли будет сильно отличаться от реализации интерпретатора для любого другого языка общего назначения. Есть лексический анализ, разбор, построение АСТ, семантический анализ, плюс выполнение (для чистого интерпретатора) или генерация кода и оптимизация (для компилятора, даже для компиляции в байт-код, например Java/Perl/Python). SICP представит разницу между оценкой «аппликативный порядок» и «нормальным порядком», которая может быть важна для вас в чисто функциональном контексте.

Answer 2

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

Answer 3

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

Вам необходимо решить некоторые основные характеристики языка (семантика, а не синтаксис), и основная часть дизайна вещи вытекает из этого.

• Например, имеет ли ваш язык есть система типа? Если да, то какие типы есть ? Это будет статически типизированный, динамически типизированный, утка?

• Какие выражения вы используете ? Планирование поддержки? Нужно ли вам определить порядок операций? Будет у вас даже есть операторы?

• Что вы будете использовать в качестве времени выполнения Представление программы? Будет ли преобразовать текст в байт-код , или AST, или токенированную форму исходного текста?

Есть наборы инструментов, которые помогут принять некоторую скуку из фактического разбора текста (ANTLR и Bison, чтобы назвать два), но я не знаю ничего, что помогает с фактической интерпретацией частью задачи. Я уверен, что кто-то что-то предложит.

Answer 4

См http://www.cs.cornell.edu/courses/cs312/2005sp/lectures/lec17.asp

Answer 5

Я рекомендую Основы языков программирования как хорошее дополнение к SICP, особенно если вы заинтересованы в интерпретаторов: Официальный сайт еор. Вы можете проверить third edition - сайт еще не обновлен.

Редактировать: предотвращение спама делает выбор между ссылками, поэтому официальная страница теперь не нагревается. Тем не менее, это легко Google.