Почему проще писать компилятор на функциональном языке? [закрытый]


Я думал об этом вопросе очень долго, но действительно не мог найти ответ на Google, а также аналогичный вопрос о Stackoverflow. Если есть дубликат, я сожалею об этом.

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

Это правда? И если да - почему это так эффективно и легко напишите их на функциональных языках, а не на императивном языке, например C? Кроме того-разве языковой инструмент на функциональном языке не медленнее, чем на каком-то низкоуровневом языке, таком как C?

7 77

7 ответов:

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

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

многие задачи компилятора-это сопоставление шаблонов в древовидных структурах.

и OCaml и Haskell имеют мощные и сжатые возможности сопоставления с образцом.

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

одним важным фактором является то, что большая часть любого проекта компилятор, когда вы можете самостоятельно разместить компилятор и "съесть свой собственный корм для собак."По этой причине, когда вы смотрите на такие языки, как OCaml, где они предназначены для исследования языка, они, как правило, имеют большие возможности для проблем типа компилятора.

в моей последней работе компилятора мы использовали OCaml именно по этой причине, манипулируя кодом C, это был просто лучший инструмент для этой задачи. Если люди в ИНРИИ если бы он построил OCaml с другими приоритетами, возможно, это было бы не так хорошо.

/ me: ползет обратно к моим задачам Java немного менее радостно...

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

см. также

F# design pattern

ФП групп вещей 'по эксплуатации', в то время как ОО группах то, что 'типа', и 'операция' является более естественным для компилятора/интерпретатора.

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

похоже, все пропустили еще одну важную причину. Довольно легко написать встроенный доменный язык (EDSL)для парсеров, которые очень похожи на (E) BNF в обычном коде. парсер комбинаторов like Parsec довольно легко писать на функциональных языках, используя функции более высокого порядка и композицию функций. Не только проще, но и очень элегантно.

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

Это не единственный способ сделать parer рамки-конечно.