Комбинатор FIX с фиксированной запятой (он же Y-комбинатор) в (нетипизированном) лямбда-исчислении ( ) определяется как:
FIX
Я понимаю его назначение и прекрасно отслеживаю выполнение его приложения; Я хотел бы понять, как вывести FIX из первых принципов .
Вот, насколько я понимаю, когда я пытаюсь получить это сам:
- FIX - это функция: FIX
- FIX использует другую функцию, , чтобы сделать ее рекурсивной: FIX
- Первый аргумент функции - это «имя» функции, используемое там, где предназначено рекурсивное приложение. Поэтому все появления первого аргумента для должны быть заменены функцией, и эта функция должна ожидать остальных аргументов (давайте просто предположим, что принимает один аргумент): FIX
Это где я не знаю, как «сделать шаг» в моих рассуждениях. Маленькие эллипсы указывают, где в моем FIX чего-то не хватает (хотя я могу узнать это только по сравнению с «настоящим» FIX).
Я уже прочитал « Типы и языки программирования» , который не пытается вывести его напрямую, а вместо этого отсылает читателя к «Маленькому интригану» за выводом. Я тоже это читал, и его «вывод» не был таким уж полезным. Более того, речь идет не о прямом выводе, а об использовании очень специфического примера и о специальной попытке написать подходящую рекурсивную функцию в .
Ответы:
Я нигде не читал это, но вот как я полагаю, мог быть получен:Y
Давайте иметь рекурсивную функцию , возможно, факториал или что-то еще в этом роде. Неформально мы определяем f как псевдо-лямбда-термин, где f встречается в его собственном определении:f f f
Во-первых, мы понимаем, что рекурсивный вызов может быть выделен как параметр:
Теперь мы могли бы определить если бы у нас был только способ передать его в качестве аргумента самому себе. Это невозможно, конечно, потому что у нас нет f под рукой. То , что мы имеем под рукой M . Поскольку M содержит все, что нам нужно для определения f , мы можем попытаться передать M в качестве аргумента вместо f и попытаться восстановить f из него позже внутри. Наша первая попытка выглядит так:f f M M f M f f
Однако это не совсем правильно. Перед тем , получили заменить г внутри М . Но теперь мы проходим М вместо. Мы должны как - то исправить все места , где мы используем г , чтобы они реконструкции п от М . На самом деле, это совсем не сложно: теперь, когда мы знаем, что f = M M , везде, где мы используем r, мы просто заменяем его на ( r r ) .f r M M r f M f=MM r (rr)
Это решение хорошо, но нам пришлось изменить внутри. Это не очень удобно. Мы можем сделать это более элегантно, не изменяя M , введя другой λ, который посылает M свой аргумент, примененный к самому себе: выражая M ′ как λ x . М ( х х ) мы получаемM M λ M M′ λx.M(xx)
Таким образом, когда заменяется на x , M M заменяется на r , который по определению равен f . Это дает нам нерекурсивное определение f , выраженное как действительный лямбда-членM x MM r f f
Переход на теперь легкий. Мы можем взять произвольный лямбда-член вместо M и выполнить эту процедуру для него. Таким образом, мы можем выделить М и определитьY M M
Действительно, сводится к f, как мы его определили.YM f
Примечание: я получил как это определено в литературе. Комбинатор вы описали это вариант Y для вызова по значению языков, иногда также называют Z . Смотрите эту статью в Википедии .Y Y Z
источник
Как отметил Ювал, не существует только одного оператора с фиксированной запятой. Их много. Другими словами, уравнение для теоремы о неподвижной точке не имеет единственного ответа. Таким образом, вы не можете извлечь оператора из них.
Это все равно что спрашивать, как люди выводят как решение для x = y . Они не! Уравнение не имеет единственного решения.(x,y)=(0,0) x=y
На тот случай, если вы хотите узнать, как была открыта первая теорема о неподвижной точке. Позвольте мне сказать, что я также задавался вопросом о том, как они придумали теоремы о фиксированной точке / рекурсии, когда я впервые увидел их. Это кажется таким гениальным. Особенно в форме теории вычислимости. В отличие от того, что говорит Ювал, это не тот случай, когда люди играют, пока не найдут что-то. Вот что я нашел:
Насколько я помню, теорема изначально принадлежит С. К. Клини. Клини предложила оригинальную теорему о фиксированной точке, спасая доказательство несостоятельности первоначального лямбда-исчисления Чёрча. Первоначальное лямбда-исчисление церкви пострадало от парадокса типа Рассела. Модифицированное лямбда-исчисление позволило избежать этой проблемы. Клини изучил доказательство несоответствия, вероятно, чтобы увидеть, как модифицированное лямбда-исчисление будет страдать от аналогичной проблемы, и превратил доказательство несоответствия в полезную теорему модифицированного лямбда-исчисления. Благодаря своей работе по эквивалентности исчисления лямбад с другими моделями вычислений (машинами Тьюринга, рекурсивными функциями и т. Д.) Он перенес его в другие модели вычислений.
Как вывести оператора вы можете спросить? Вот как я это запомнил. Теорема о неподвижной точке об удалении самоссылки.
Все знают парадокс лжеца:
Или в более лингвистической форме:
Теперь большинство людей думают, что проблема с этим предложением связана с самообращением. Нет! Самостоятельная ссылка может быть устранена (проблема с правдой, язык не может говорить об истинности своих собственных предложений вообще, см. Теорему Тарского о неопределимости истины ). Форма, в которой удалена собственная ссылка, выглядит следующим образом:
Нет ссылки на себя, у нас есть инструкции о том, как создать предложение, а затем что-то с ним сделать. И построенное предложение равно инструкции. Обратите внимание, что в калькуляции нам не нужны кавычки, потому что нет различия между данными и инструкциями.λ
Теперь, если мы проанализируем это, у нас есть где M x - это инструкции, чтобы построить x x и что-то с ним сделать.MM Mx xx
Итак, есть λ х . е ( х х ) и мы имеемM λx.f(xx)
Это для фиксированного . Если вы хотите сделать это оператором, мы просто добавим λ f и получим Y :f λf Y
Так что я просто иметь в виду , парадокс без самоссылки , и это помогает мне понять , что о.Y
источник
Таким образом, вам нужно определить комбинатор с фиксированной точкой
но без явной рекурсии. Начнем с самого простого неприводимого комбинатора
В
x
первой лямбде многократно подставляется вторая лямбда. Простое альфа-преобразование делает этот процесс более понятным:Т.е. переменная в первой лямбде всегда исчезает. Так что, если мы добавим
f
к первой лямбдаf
будет всплыватьМы получили нашу
omega
спину. Теперь должно быть ясно, что, если мы добавим af
ко второй лямбде, тоf
появится в первой лямбде, а затем она подпрыгнет:поскольку
мы можем переписать выражение как
который просто
и мы получили наше уравнение
Y f = f (Y f)
. Таким образом,Y
комбинатор по существуf
f
подпрыгнулисточник
Возможно, вы видели классический пример уравнения без нормальной формы:
Аналогичное уравнение предлагается для общей рекурсии:
источник