Y комбинатор и оптимизация хвостовых вызовов

Определение Y комбинатора в F #

let rec y f x = f (y f) x

В качестве первого аргумента f ожидает продолжения рекурсивных подзадач. Используя yf в качестве продолжения, мы видим, что f будет применяться к последовательным вызовам, поскольку мы можем развить

let y f x = f (y f) x = f (f (y f)) x = f (f (f (y f))) x etc...

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

Так :

• с одной стороны, использование Y комбинатора требует явно другого продолжения, чем сама функция.
• Что касается применения TCO, мы хотели бы, чтобы в f не было ожидающих операций, а вызывался только сам f.

Знаете ли вы, каким образом эти двое могли бы примириться? Как Y с трюком аккумулятора или Y с трюком CPS? Или аргумент, доказывающий, что это невозможно сделать?

Знаете ли вы, каким образом эти двое могли бы примириться?

Нет, и не без причины, ИМХО.

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

Таким образом, комбинатор Y поистине увлекателен.

Но : Никто на самом деле не использует Y-комбинатор для реальной рекурсии! (За исключением, может быть, для развлечения, чтобы показать, что это действительно работает.)

Оптимизация хвостового вызова, OTOH, как следует из названия, является оптимизацией. Это ничего не добавляет к выразительности языка, мы заботимся только о практических соображениях, таких как пространство стека и производительность рекурсивного кода.

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

Я не совсем уверен в этом ответе, но это лучшее, что я мог придумать.

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

let rec y f x = f (y f) x

Ваше определение выглядит так, как будто оно требует лени для завершения, иначе (y f)аргумент никогда не завершит оценку и должен будет оценить, fиспользовал ли он его или нет . TOC в ленивом контексте является более сложным, и, кроме того, результатом (y f)является повторное составление функции без применения с x. Я не уверен, что это нужно для O (n) памяти, где n - глубина рекурсии, но я сомневаюсь, что вы могли бы достичь того же типа TOC, что возможно с чем-то вроде (переключение на Haskell, потому что я на самом деле не знаю F #)

length acc []    = acc
length acc (a:b) = length (acc+1) b 

Если вы еще не знаете об этом, разница между Хаскелом foldlи foldl'в Хаскеле может пролить свет на ситуацию. foldlнаписано как было бы сделано на нетерпеливом языке. Но вместо того, чтобы быть TOC'd, это на самом деле хуже, чем foldrпотому, что аккумулятор хранит потенциально огромный гром, который не может быть частично оценен. (Это связано с тем, что как foldl, так и foldl 'не работают с бесконечными списками.) Таким образом, в более поздних версиях Haskell foldl'был добавлен, который заставляет вычислять аккумулятор каждый раз, когда функция повторяется, чтобы гарантировать, что не создается огромный поток. Я уверен, что http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 может объяснить это лучше, чем я.