Совместное использование и отсутствие совместного использования комбинатора с фиксированной запятой

«Совместное использование» означает f x повторное использование созданного x; но с _Y g = g . g . g . g . ... каждый g вычисляет свой вывод заново (см. this и this).

В этом контексте версия с совместным доступом имеет гораздо худшее использование памяти, приводит к утечке места. ¹

Определение _Y отражает обычный эффект определения лямбда-исчисления для комбинатора Y, который имитирует рекурсию путем дублирования, в то время как истинная рекурсия относится к тому же (следовательно, общий) объект.

In

    x      = f x
    (_Y g) = g (_Y g)

оба x относятся к одному и тому же объекту, но каждый из (_Y g) относится к эквивалентному, но отдельному объекту. Во всяком случае, это его намерение.

Конечно, благодаря ссылочной прозрачности в Haskell the language нет никаких гарантий в этом отношении. Но компилятор GHC действительно так себя ведет.

_Y g - это распространенное подвыражение, и оно могло быть "исключено" компилятором, дав ему имя и повторно использовав этот именованный объект, разрушая всю его цель. Вот почему в GHC есть флаг «исключение общих подвыражений» -fno-cse, который явно предотвращает это. Раньше вам приходилось использовать этот флаг для достижения желаемого поведения здесь, но теперь это не так. GHC больше не будет так агрессивно устранять распространенные подвыражения с более свежими (читай: несколько лет назад) версиями.

отказ от ответственности: я являюсь автором той части страницы, на которую вы ссылаетесь. Я надеялся на то, что обычно на вики-страницах будет взад-вперед, но этого так и не произошло, поэтому мои работы так не рецензировались. Либо никто не побеспокоил, либо он пройден (без серьезных ошибок). Кажется, что вики уже много лет заброшены.

¹ Используемая функция g,

(3:) . minus [5,7..] . foldr (\ (x:xs) ⟶ (x:) . union xs) [] 
                      . map (\ p ⟶ [p², p² + 2p..])

производит увеличивающийся поток всех нечетных простых чисел, заданный увеличивающимся потоком всех нечетных простых чисел. Чтобы получить простое число N по значению, он потребляет свой входной поток, по крайней мере, до первого простого числа выше sqrt(N) по значению. Таким образом, производственные очки даются примерно путем повторного возведения в квадрат, и всего в цепочке (или "башне") этих простых чисел имеется ~ log (log N) таких g функций. производителей, каждый из которых подлежит немедленной сборке мусора, причем самый младший из них производит свои простые числа с учетом только первого нечетного простого числа, 3, известного априори.

А с двухэтапным _Y2 g = g x where { x = g x } их было бы только два в цепочке, но только верхний сразу стал бы сборщиком мусора, как обсуждалось по указанной выше ссылке.

_Y переведен на следующий STG:

_Y f = let x = _Y f in f x

fix переводится идентично исходному тексту Haskell:

fix f = let x = f x in x

Итак, fix f устанавливает рекурсивный преобразователь x и возвращает его, в то время как _Y является рекурсивной функцией и, что важно, не является хвостовой рекурсивной. Принуждение _Y f входит в f, передавая new вызов _Y f в качестве аргумента, поэтому каждый рекурсивный вызов устанавливает новый преобразователь; принуждение x, возвращаемого fix f, входит в f, передавая x в качестве аргумента, поэтому каждый рекурсивный вызов выполняется в один и тот же преобразователь - это и есть то, что подразумевается под «совместным использованием».

Версия с совместным использованием обычно лучше использует память, а также позволяет GHC RTS обнаруживать некоторые виды бесконечных циклов. Когда преобразователь выполняется принудительно, перед началом оценки он заменяется «черной дырой»; если в любой момент во время оценки преобразователя черная дыра достигается из того же потока, тогда мы знаем, что имеем бесконечный цикл и можем вызвать исключение (которое вы могли видеть как Exception: <<loop>>).

Я думаю, вы уже получили отличные ответы с точки зрения GHC / Haskell. Я просто хотел вмешаться и добавить несколько исторических / теоретических заметок.

Соответствие между развернутым и циклическим представлениями о рекурсии тщательно изучено в докторской диссертации Хасегавы: https://www.springer.com/us/book/9781447112211

(Вот более короткий документ, который вы можете прочитать, не платя Springer: https://link.springer.com/content/pdf/10.1007%2F3-540-62688-3_37.pdf)

Хасегава предполагает наличие отслеживаемой моноидальной категории, требование, которое гораздо менее жесткое, чем обычное предположение PCPO теории предметной области, которое формирует основу того, как мы думаем о Haskell в целом. Хасегава показал, что можно определить эти «разделяющие» операторы с фиксированной точкой в ​​такой обстановке, и установил, что они соответствуют обычному развернутому представлению о неподвижных точках из лямбда-исчисления Черча. То есть невозможно отличить их друг от друга, заставляя давать разные ответы.

Соответствие Хасэгавы справедливо для так называемых центральных стрелок; т.е. когда нет никаких "эффектов". Позже Бентон и Хайланд расширили эту работу и показали, что соответствие сохраняется для некоторых случаев, когда нижележащая стрелка также может выполнять «умеренные» монадические эффекты: https://pdfs.semanticscholar.org/7b5c/8ed42a65dbd37355088df9dde122efc9653d.pdf

К сожалению, Benton и Hyland допускают только довольно «мягкие» эффекты: такие эффекты, как монады состояния и среды, подходят под все требования, но не общие эффекты, такие как исключения, списки или ввод-вывод. (Операторы с фиксированной точкой для этих эффективных вычислений известны как mfix в Haskell с сигнатурой типа (a -> m a) -> m a, и они составляют основу рекурсивной нотации-do.)

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