Принудительная хвостовая рекурсия: жрать память вместо стека?

[metaclass]

Читаю про катаморфизмы и FSharp. Вообще, изначально это я искал ответ на этот вопрос, но зачитался и забыл.

Там приводится пример, как выразить foldBack (оно же foldr) через fold(оно же foldl) с помощью continuations. И выглядит это как будто мы заменяем использование стека в случае не-tail-recursive функции таким же использованием памяти из head. Причем в случае стека выделение и удаление памяти достаточно дешевое, а вот что будет в случае обычной памяти - вопрос загадочный. Непонятно, есть ли тогда какие-нибудь преимущества у такого преобразования не-tail-recursive функции в tail-recursive?

Comments

[antilamer.livejournal.com]

Нет никаких преимуществ, обыкновенное извращение.

[blacklion.livejournal.com]

Стек, особенно в 32-бит мультитреде, может быть куда меньше хипа.

[gds.livejournal.com]

стек бывает ограничен жостко (обычно в опциях линкера устанавливается), тогда как хип растёт согласно имеющейся памяти (а то и своп используется, если есть).
Например, кое-где я использую формально типо-небезопасную библиотеку (хотя там с типами всё хорошо, но не доказано), но чуть более медленную, зато tail-recursive на всех функциях, работающих со списками.

[raydac.livejournal.com]

в случае рекурсии прикинь какой у тебя отладочный стек вызовов JVM попытается построить для объекта Exception и это при нехватке памяти то, так что разница есть

[usovalx.livejournal.com]

Не знаю как там с производительностью аллокатора в .Net, но в том-же ocaml выделение памяти в куче чудовищно быстрое.

[migmit.livejournal.com]

Ну, появляется возможность делать call/cc.

[mchrome-cat.livejournal.com]

Кстати, существует книжка от Andrew Appel - "Compiling with continuations", где он по идее (я сам не читал) подробно рассказывает, зачем нужен cps.