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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Шаблон проектирования F#

FP группирует вещи «по операциям», тогда как OO группирует вещи «по типам», а «по операциям» более естественно для компилятора/интерпретатора.

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

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

Это, конечно, не единственный способ создания парных фреймворков.