Бэкэндер компилятора для функционального языка

Question

Я написал интерпретатор для функционального языка, который я пытаюсь загрузить с помощью компилятора. Язык имеет систему динамического типа и использует списки, числа и строки. Он также является функциональным, и функция принимает свой аргумент как список (например, perls @_ или аргументы js). Функции являются первоклассными и могут быть вложенными. На каком языке я должен настраиваться с помощью компилятора, кстати. Я думаю, что цель статического типизированного императивного языка, такого как C, будет сложной. Язык должен поддерживать динамическое типирование и функциональное программирование (js не будет приятным - язык должен иметь сам компилятор, например обычный lisp)

Answer 1

Вам не нужна специальная поддержка с вашего целевого языка. Динамическую отправку можно решить, используя общие версии ваших функций (но подумайте об оптимизации, когда типы могут быть безопасно выведены), например, для a + b вы можете сгенерировать код, например generic_add(a, b), где generic_add - это функция, которая выбирает подходящую реализацию в зависимости от информацию о времени выполнения.

Для функциональной части тривиально устранить ее, используя подъем лямбда. Для последнего вам просто нужно создать списки свободных и связанных переменных для каждого узла AST: список свободных переменных строится из листьев в корень, а связанный список построен в противоположном направлении. Для каждого лямбда-узла вы вычитаете свободную от привязки и создаете новую функцию верхнего уровня, которая принимает как явные аргументы лямбда, так и эту разницу (т. Е. Захваченные переменные).

Кроме того, если вы хотите сделать оптимизацию или если ваш язык должен поддерживать продолжения, рассмотрите возможность использования CPS-преобразования.

Answer 2

Ориентация на языки низкого уровня, такие как LLVM и C, прекрасна, если вы готовы реализовать динамическую отправку, закрытие и т. Д. Самостоятельно. Однако, поскольку вы упоминаете JavaScript как возможную цель (за исключением отсутствия компиляторов, хотя даже JS скомпилирован JIT в основных браузерах в настоящее время), как насчет Scheme? Это динамически типизированный функциональный язык более высокого порядка и уже содержит компиляторы с собственным кодом: http://community.schemewiki.org/?scheme-faq-standards#implementations Единственная проблема может заключаться в том, что она слишком близка к исходному языку, и ваш компилятор (или «переводчик», я бы сказал, был бы слишком легко возможно :-)

Если вы готовы предназначаться C, является хорошей отправной точкой может быть учебник Марк Фили «The 90 минут Схема для компилятора Си»:. http://churchturing.org/y/90-min-scc.pdf