Комбинаторы С Фиксированной Точкой

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

Я видел пример в Javascript для Y-комбинатора, но не смог его успешно запустить.

Вопрос здесь в том, может ли кто-то дать интуитивный ответ на:
  • Что такое комбинаторы с фиксированной точкой, (не только теоретически, но в контексте некоторого примера, чтобы показать, что именно является фиксированной точкой в этом контексте)?
  • каковы другие виды комбинаторов с фиксированной точкой, кроме y-комбинатора?

бонусные очки: Если пример не только на одном языке, предпочтительно в Clojure .

Обновление:

Я смог найти простой пример в Clojure , но все еще затрудняюсь понять Сам Y-комбинатор: 

(defn Y [r]
  ((fn [f] (f f))
   (fn [f]
     (r (fn [x] ((f f) x))))))

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

2 5
functional-programming anonymous-function combinators fixed-point higher-order-functions

2 ответа:

Предположим, вы хотите написать факторную функцию. Обычно вы пишете это как что-то вроде

function fact(n) = if n=0 then 1 else n * fact(n-1)

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

function factMaker(myFact) = lamba n. if n=0 then 1 else n * myFact(n-1)
Это принимает аргумент (myFact), который он называет "истинным" фактом, который назвал бы сам себя. Я называю этот стиль функции "y-ready", то есть он готов к подаче в Y-комбинатор.

Y-комбинатор использует фактолог должен построить нечто эквивалентное "истинному" факту.

newFact = Y(factMaker)

Зачем беспокоиться? По двум причинам. Первый-теоретический: нам действительно не нужна рекурсия, если мы можем "смоделировать" ее с помощью Y-комбинатора.

Второй вариант более прагматичен. Иногда мы хотим обернуть каждый вызов функции каким-то дополнительным кодом для ведения журнала, профилирования, запоминания или множества других вещей. Если мы попытаемся сделать это с "истинным" фактом, то дополнительный код будет вызван только для первоначального вызова факта, а не все рекурсивные вызовы. Но если мы хотим сделать это для каждого вызова, включая все рекурсивные вызовы, мы можем сделать что-то вроде 
loggingFact = LoggingY(factMaker)

, где LoggingY представляет собой модифицированный вариант y комбинатора, который вводит лесозаготовки. Обратите внимание, что нам вообще не нужно было менять factMaker!

Все это больше мотивирует, почему Y-комбинатор имеет значение, чем подробное объяснение того, как работает эта конкретная реализация Y (потому что существует много различных способов реализации Y).
11

Чтобы ответить на ваш второй вопрос о комбинаторах с фиксированной точкой, отличных от Y. существует счетно бесконечное число стандартных комбинаторов с фиксированной точкой, то есть комбинаторов fix, удовлетворяющих уравнению

fix f = f (fix f)

Существует также достаточно много нестандартных комбинаторов с фиксированной точкой, удовлетворяющих уравнению 

fix f = f (f (fix f))

И т. д. Стандартные комбинаторы точек фиксации рекурсивно перечисляются, но нестандартные-нет. Пожалуйста, смотрите следующую веб-страницу для примеров, ссылок и обсуждение. http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes

3