Почему проще написать компилятор на функциональном языке?
Автор вопроса: wvdОтветов: 7
Я очень долго думал над этим вопросом, но действительно не смог найти ответ в Google, а также аналогичный вопрос в Stackoverflow. Если есть дубликат, извините за это.
Кажется, многие люди говорят, что писать компиляторы и другие языковые инструменты на функциональных языках, таких как OCaml и Haskell, гораздо эффективнее и проще, чем писать их на императивных языках.
Это правда? И если да, то почему так эффективно и легко писать их на функциональных языках, а не на императивном языке, таком как C? Кроме того, разве языковой инструмент на функциональном языке не медленнее, чем на каком-нибудь низкоуровневом языке, таком как C?
Я бы не сказал, что легче. Но функциональная природа задач компиляции, таких как синтаксический анализ, вероятно, вполне естественно подходит для функционального программирования. Функциональные языки, такие как OCaml, могут быть очень быстрыми, соперничая со скоростью C. Robert Harvey 25.05.2010
Люди, это действительно аргумент? Наверняка у кого-то есть понимание. Я хотел бы знать себя. Robert Harvey 25.05.2010
Я думаю, что должно быть по крайней мере несколько веских причин, по которым следует использовать функциональный язык вместо императивного. Я нашел какую-то статью, которая в основном сводилась к тому, что функциональные языки не имеют побочных эффектов и тому подобное. Но это было не совсем ясно. Однако, если это спорно, то, возможно, было бы лучше закрыть его или переформулировать вопрос. wvd 25.05.2010
Можем ли мы изменить его на "...эффективно и легко"? Это делает его менее спорным. Donal Fellows 25.05.2010
Действительно ли аргументировано признать, что некоторые ниши лучше подходят для определенного стиля языка? Я думаю, что вопрос о том, почему C лучше, чем Javascript для написания драйверов устройств, не вызывает споров... C. A. McCann 25.05.2010
Я думал, что будет наоборот. Я читаю супер крошечный компилятор, и он повсюду использует переменную мутацию. Rolf 25.09.2017
Часто компилятор много работает с деревьями. Исходный код анализируется в синтаксическом дереве. Затем это дерево может быть преобразовано в другое дерево с аннотациями типов для выполнения проверки типов. Теперь вы можете преобразовать это дерево в дерево, содержащее только основные элементы языка (преобразовав синтаксические сахароподобные нотации в несахарную форму). Теперь вы можете выполнять различные оптимизации, которые в основном представляют собой преобразования дерева. После этого вы, вероятно, создадите дерево в какой-то нормальной форме, а затем выполните итерацию по этому дереву, чтобы создать целевой (ассемблерный) код.
Функциональные языки имеют такие функции, как сопоставление с образцом и хорошую поддержку эффективной рекурсии, которые упрощают работу с деревьями, поэтому они обычно считаются хорошими языками для написания компиляторов.
Ответ 2 · рейтинг 38 · Pete Kirkham
Многие задачи компилятора связаны с сопоставлением шаблонов в древовидных структурах.
И OCaml, и Haskell обладают мощными и лаконичными возможностями сопоставления с образцом.
В императивные языки сложнее добавить сопоставление с образцом, поскольку любое значение, которое оценивается или извлекается для сопоставления с образцом, должно быть свободным от побочных эффектов.
Ответ 3 · рейтинг 15 · Ukko
Один важный фактор, который следует учитывать, заключается в том, что большая часть любого проекта компилятора - это когда вы можете самостоятельно разместить компилятор и "есть свою собачью еду". По этой причине, когда вы смотрите на такие языки, как OCaml, где они предназначены для языковых исследований, они, как правило, имеют отличные возможности для решения проблем типа компилятора.
В моей последней работе, похожей на компилятор, мы использовали OCaml именно по этой причине при манипулировании кодом C, это был просто лучший инструмент для этой задачи. Если бы люди из INRIA построили OCaml с другими приоритетами, возможно, он не был бы таким подходящим.
Тем не менее, функциональные языки - лучший инструмент для решения любой проблемы, поэтому логически следует, что они являются лучшим инструментом для решения этой конкретной проблемы. КЭД.
/me: чуть менее радостно ползет обратно к моим Java-задачам...
Ответ 4 · рейтинг 9 · Chuck
По сути, компилятор - это преобразование одного набора кода в другой - от исходного кода к IR, от IR к оптимизированному IR, от IR к ассемблеру и т. д. Это как раз то, для чего предназначены функциональные языки - чистая функция просто превращение одного в другое. Императивные функции не обладают этим качеством. Хотя вы можете написать такой код на императивном языке, функциональные языки предназначены для этого.
Ответ 5 · рейтинг 7 · BCS
Одна из возможностей состоит в том, что компилятору приходится очень тщательно обрабатывать множество крайних случаев. Получение правильного кода часто упрощается за счет использования шаблонов проектирования, которые структурируют реализацию таким образом, чтобы она соответствовала правилам, которые она реализует. Часто это оказывается декларативным (сопоставление с образцом, "где"), а не императивным (последовательность, "когда") дизайном, и поэтому его легче реализовать на декларативном языке (и большинство из них функциональны).
FP группирует вещи "по операциям", тогда как OO группирует вещи "по типам", а "по операциям" более естественно для компилятора/интерпретатора.
Ответ 7 · рейтинг 4 · snk_kid
Похоже, все упустили еще одну важную причину. Довольно легко написать встроенный предметно-ориентированный язык (EDSL) для синтаксических анализаторов, который очень похож на (E)BNF в обычном коде. Комбинаторы синтаксического анализатора, такие как Parsec, довольно легко написать на функциональных языках, используя функции высшего порядка и композицию функций. Не только проще, но и очень элегантно.
По сути, вы представляете самые простые общие парсеры как просто функции, и у вас есть специальные операции (обычно функции более высокого порядка), которые позволяют вам компоновать эти примитивные парсеры в более сложные, более специфичные парсеры для вашей грамматики.
Это, конечно, не единственный способ создания парных фреймворков.
