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

88

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

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

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

wvd
источник
5
Я бы не сказал, что это проще. Но функциональный характер задач компиляции, таких как синтаксический анализ, вероятно, вполне естественно поддается функциональному программированию. Функциональные языки, такие как OCaml, могут быть чрезвычайно быстрыми, соперничая по скорости с C.
Роберт Харви
17
Ребята, это действительно аргумент? Наверняка у кого-то есть понимание. Я хотел бы знать себя.
Роберт Харви,
Я думаю, что должно быть по крайней мере несколько веских причин, почему следует использовать функциональный язык вместо императивного. Я нашел статью, которая в основном сводилась к тому, что функциональные языки не имеют побочных эффектов и тому подобное. Но это было не совсем понятно. Однако, если это аргумент, то, возможно, лучше закрыть его или переформулировать вопрос.
wvd
12
Является ли это на самом деле АРГУМЕНТАТИВНО признать , что некоторые ниши лучше подходят для определенного стиля языка? «Почему C лучше, чем Javascript для написания драйверов устройств» не будет спорным, я думаю ...
CA McCann
1
Думал, будет наоборот. Я читаю "супер крошечный компилятор", и он повсюду использует мутацию переменных.
Рольф

Ответы:

101

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

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

sepp2k
источник
Самый полный ответ на данный момент, я отмечу это как принятый ответ, однако я думаю, что ответ Пита Киркхэма также хорош.
wvd
1
Что касается «доказательства правильности», поскольку правильность компилятора является важным атрибутом, я часто слышал, что любители функциональных языков как-то включают «доказательство» правильности в свой рабочий процесс. Я понятия не имею, что это на самом деле означает с практической точки зрения, но, поскольку надежность компилятора важна, это кажется стоящим.
Уоррен П.
3
@WarrenP: Концепция «кода с проверкой» пришла из функциональных языков со статической типизацией. Идея состоит в том, что вы используете систему типов таким образом, чтобы функция могла проверять тип только на правильность, поэтому факт компиляции кода является доказательством правильности. Конечно, это невозможно в полной мере при сохранении целостности языка по Тьюрингу и решимости проверки типов. Но чем сильнее система типов, тем ближе вы можете подойти к этой цели.
sepp2k
3
Причина, по которой эта концепция в основном популярна в функциональном сообществе, заключается в том, что в языках с изменяемым состоянием вам также придется кодировать информацию о том, когда и где происходит изменение состояния в типах. На языках, где вы знаете, что результат функции зависит только от ее аргументов, гораздо проще закодировать доказательство в типах (также гораздо проще вручную проверить правильность кода, потому что вам не нужно учитывать, какое глобальное состояние является возможно и как это повлияет на поведение функции). Однако ничего из этого не имеет отношения к компиляторам.
sepp2k
3
На мой взгляд, самая важная особенность - это сопоставление с образцом. Оптимизировать абстрактное синтаксическое дерево с помощью сопоставления с образцом до глупости просто. Делать это без сопоставления с образцом часто бывает очень сложно.
Боб Аман,
38

Многие задачи компилятора - это сопоставление с образцом в древовидной структуре.

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

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

Пит Киркхэм
источник
Звучит как разумный ответ, но разве это единственное? например, будут ли играть роль такие вещи, как хвостовая рекурсия?
wvd
Казалось бы, это указывает на то, что это больше проблема системы типов, чем реальной модели выполнения. Что-то, основанное на императивном программировании с неизменяемыми значениями над структурными типами, может подойти.
Donal Fellows
@wvd: Оптимизация хвостовой рекурсии - это деталь реализации, а не языковая функция как таковая, которая делает линейные рекурсивные функции эквивалентными итеративному циклу. Рекурсивная функция для обхода связанного списка в C выиграет от этого так же, как и рекурсивный просмотр списка в Scheme.
CA McCann
@wvd gcc C имеет исключение хвостового вызова, как и другие изменяемые государственные языки,
Пит Киркхэм,
3
@camccann: Если стандарт языка гарантирует tco (или, по крайней мере, гарантирует, что рекурсивные функции определенной формы никогда не вызовут переполнение стека или линейный рост потребления памяти), я бы счел это особенностью языка. Если стандарт не гарантирует этого, но компилятор все равно это делает, это функция компилятора.
sepp2k
15

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

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

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

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

Укко
источник
4
-1 за «функциональные языки - лучший инструмент для решения любой проблемы». Если бы это было правдой, мы бы все использовали их везде. ;)
Андрей Кротков
15
@Andrei Krotkov: Сегодняшнее слово дня устрашающе Произношение: \ fə-ˈsē-shəs \ Функция: прилагательное Этимология: среднефранцузский facetieux, от facetie jest, от латинского facetia Дата: 1599 г. 1: шутить или шутить часто неуместно : waggish <просто шутить> 2: шутить или смешно: несерьезно <шуточное замечание> синонимы видеть остроумие Помимо того, что вы упустили шутку, ваша логика по-прежнему ошибочна. Вы предполагаете, что все люди являются рациональными действующими лицами, и, боюсь, это неверное предположение.
Укко
5
Думаю, я пропустил шутку, так как в реальной жизни я знаю людей, которые сказали бы в значительной степени то же самое, кроме как полностью серьезно. Думаю, закон По. tvtropes.org/pmwiki/pmwiki.php/Main/PoesLaw
Андрей Кротков
13
@Andrei: Использование аргументации ad populum : «Если разум лучше эмоционального невежества, мы все будем использовать его везде».
Тим Шеффер,
9

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

Чак
источник
6

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

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

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

Брайан
источник
3
Это относится к тому, что в некоторых кругах теории языков программирования называется «проблемой выражения». Например, см. Этот вопрос , в котором я демонстрирую действительно ужасный код Haskell, который делает что-то в стиле «расширяемых типов». Напротив, принуждение языка ООП к стилю «расширяемых операций» имеет тенденцию мотивировать шаблон посетителей.
CA McCann
6

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

БКС
источник
4

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

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

Конечно, это не единственный способ создать более ранние фреймворки.

snk_kid
источник