Почему запись является компилятором на функциональном легче языке? [закрытый]
7 ответов
Часто компилятор много работает с деревьями. Исходный код анализируется в синтаксическом дереве. Затем это дерево может быть преобразовано в другое дерево с аннотациями типов для проверки типов. Теперь вы можете преобразовать это дерево в дерево, содержащее только элементы ядра языка (преобразование синтаксических нотаций, подобных сахару, в несахарную форму). Теперь вы можете выполнять различные оптимизации, которые в основном представляют собой преобразования дерева. После этого вы, вероятно, создадите дерево в некоторой нормальной форме, а затем выполните итерацию по этому дереву, чтобы создать целевой (сборочный) код.
Функциональный язык имеет такие функции, как сопоставление с образцом и хорошую поддержку эффективной рекурсии, что упрощает работу с деревьями, поэтому они обычно считаются хорошими языками для написания компиляторов.
Одна из возможностей заключается в том, что компилятору, как правило, приходится очень аккуратно работать с целым рядом угловых случаев. Получение правильного кода часто облегчается использованием паттернов проектирования, которые структурируют реализацию таким образом, что она параллельна правилам, которые она реализует. Часто это оказывается декларативным (сопоставление шаблонов, "где"), а не императивным (последовательность, "когда") дизайном, и поэтому его легче реализовать на декларативном языке (а большинство из них являются функциональными).
Похоже, все упустили еще одну важную причину. Достаточно легко написать встроенный предметно-ориентированный язык (EDSL) для парсеров, которые очень похожи на (E) BNF в обычном коде. Комбинаторы синтаксического анализатора , такие как Parsec, довольно легко написать на функциональных языках, используя функции высшего порядка и композицию функций. Не только проще, но и очень элегантно.
По сути, вы представляете самые простые общие синтаксические анализаторы как просто функции, и у вас есть специальные операции (обычно функции высшего порядка), которые позволяют вам объединить эти примитивные синтаксические анализаторы в более сложные, более конкретные синтаксические анализаторы для вашей грамматики.
Конечно, это не единственный способ создать более ранние фреймворки.
Многие задачи компилятора связаны с сопоставлением шаблонов древовидных структур.
И OCaml, и Haskell обладают мощными и краткими возможностями сопоставления с образцом.
Сложнее добавить сопоставление с образцом в императивные языки, поскольку любое значение, которое оценивается или извлекается для сопоставления с образцом, не должно иметь побочных эффектов.
См. Также
FP группирует элементы «по операции», тогда как OO группирует элементы «по типу» , а для компилятора / интерпретатора более естественно «по работе».
Одним из важных факторов, который следует учитывать, является то, что важной частью любого проекта по созданию компилятора является возможность самостоятельного хостинга компилятора и "поедания собственного собачьего корма". По этой причине, когда вы смотрите на такие языки, как OCaml, где они предназначены для исследования языков, они, как правило, имеют большие возможности для решения проблем компиляторного типа.
На моей последней работе, связанной с компиляторами, мы использовали OCaml именно по этой причине при работе с кодом на языке Си, это был просто лучший инструмент для этой задачи. Если бы ребята из INRIA создавали OCaml с другими приоритетами, он, возможно, не был бы таким подходящим.
Тем не менее, функциональные языки являются лучшим инструментом для решения любой проблемы, поэтому логически следует, что они являются лучшим инструментом для решения этой конкретной проблемы. QED.
/me: ползет обратно к своим Java-задачам чуть менее радостно...
По сути, компилятор - это преобразование одного набора кода в другой - от источника к IR, от IR к оптимизированному IR, от IR к сборке и т.д. функциональные языки предназначены для - чистая функция - это просто преобразование одного объекта в другой. Императивные функции не обладают этим качеством. Хотя вы можете написать такой код на императивном языке, функциональные языки специализируются на этом.