Любопытно, как "loop = loop" оценивается в Haskell

Question

Я думал, что подобные выражения заставят Haskell оценивать вечно.Но поведение как в GHCi, так и в скомпилированной программе меня удивило.

Например, в GHCi эти выражения блокировались до I Control+C, но не потребляли ЦП.Похоже, что он спал.

let loop = loop
let loop = 1 + loop

Я попытался скомпилировать эти программы с GHC:

main = print loop
  where loop = 1 + loop

main = print loop
  where loop = if True then loop else 1

Что было напечатано было:

Main: <<loop>>

Так что мой вопросОчевидно, что эти выражения компилируются в нечто отличное от циклов или рекурсивных вызовов в императивных языках.Для чего они составлены?Это специальное правило для обработки функций 0-arg, которые находятся справа, или это особый случай чего-то более общего, чего я не знаю?

[EDIT]:

Еще один вопрос: если это происходит из-за особой обработки компилятором, что является причиной этого, когда невозможно проверить все бесконечные циклы?«Знакомые» языки не заботятся о таких случаях, как while (true); или int f() { return f();}, верно?

Большое спасибо.

Answer 1

GHC реализует Haskell как машину для сокращения графов. Представьте, что ваша программа представлена ​​в виде графика, в котором каждое значение является узлом, а от него идут линии для каждого значения, от которого зависит это значение. За исключением того, что мы ленивы, поэтому вы действительно начинаете с одного узла - и для оценки этого узла GHC должен «войти» в него и открыть его для функции с аргументами. Затем он заменяет вызов функции телом функции и пытается уменьшить его настолько, чтобы привести его в нормальную форму и т. Д.

Выше очень волнистые, и я уверен, что для краткости вычеркну некоторые необходимые детали.

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

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

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

Техническую информацию о текущей реализации черных дыр можно найти в выступлении Саймона Марлоу на недавнем семинаре для разработчиков Haskell "Планирование отложенной оценки на многоядерном компьютере" в нижней части http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010.

Answer 2

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

Что касается того, почему Haskell находит это чаще, чем другиеlanguages:

• Эти случаи не встречаются в таких строгих языках, как C. Эти циклы происходят, когда вычисление отложенной переменной зависит от ее собственного значения.
• Такие языки, как Cиметь очень специфическую семантику в циклах;то есть, в каком порядке делать, что в. Как таковые, они вынуждены фактически выполнить цикл.Однако Haskell определяет специальное значение _|_ («низ»), которое используется для представления ошибочных значений.Значения, которые являются строгими для самих себя - то есть, они зависят от их собственной ценности для вычисления - _|_.Результатом сопоставления с образцом в _|_ может быть либо бесконечный цикл, либо исключение;ваш компилятор выбирает последнее здесь.
• Компилятор Haskell очень заинтересован в выполнении анализа строгости, т. е. доказательства того, что определенное выражение зависит от определенных других выражений, для выполнения определенных оптимизаций.Этот цикл анализа естественно выпадает как крайний случай в анализаторе строгости, который должен обрабатываться так или иначе.