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

Question

Это обычное определение комбинатора с фиксированной точкой в ​​Haskell:

fix :: (a -> a) -> a
fix f = let x = f x in x

On https://wiki.haskell.org/Prime_numbers, они определяют другой комбинатор с фиксированной точкой:

_Y   :: (t -> t) -> t
_Y g = g (_Y g)                -- multistage, non-sharing,  g (g (g (g ...)))
    -- g (let x = g x in x)    -- two g stages, sharing

_Y - комбинатор с фиксированной точкой без совместного использования, здесь он организует рекурсивное "телескопическое" производство многоступенчатых простых чисел ( башня производителей).

Что именно это значит?Что такое «делиться» и «не делиться» в этом контексте?Чем _Y отличается от fix?

Answer 1

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

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

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

В

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

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

Конечно, благодаря прозрачности ссылок, в Haskell языке нет никаких гарантий для всего этого.Но 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), по крайней мере.Таким образом, производственные точки даются примерно путем повторного возведения в квадрат, и в цепочке (или "башня" ) из этих * 1076 имеется в общей сложности ~ log (log N) таких функций.* Производители простых чисел , каждый из которых подлежит немедленному сбору мусора, самый низкий из них производит свои простые числа с учетом только первого нечетного простого числа, 3, известного априори.

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

Answer 2

Я думаю, что вы уже получили отличные ответы с точки зрения 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 теории предметной области, которое формирует основу нашего мышленияо Хаскелле в целом. Хасэгава показал, что можно определить эти «общие» операторы фиксированной точки в такой ситуации, и установил, что они соответствуют обычному развертывающемуся представлению фиксированных точек из лямбда-исчисления Черча.способ отличить их друг от друга, заставляя их давать разные ответы.

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

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

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

Answer 3

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

_Y f = let x = _Y f in f x

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

fix f = let x = f x in x

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

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