![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Принудительная хвостовая рекурсия: жрать память вместо стека?
Читаю про катаморфизмы и FSharp. Вообще, изначально это я искал ответ на этот вопрос, но зачитался и забыл.
Там приводится пример, как выразить foldBack (оно же foldr) через fold(оно же foldl) с помощью continuations. И выглядит это как будто мы заменяем использование стека в случае не-tail-recursive функции таким же использованием памяти из head. Причем в случае стека выделение и удаление памяти достаточно дешевое, а вот что будет в случае обычной памяти - вопрос загадочный. Непонятно, есть ли тогда какие-нибудь преимущества у такого преобразования не-tail-recursive функции в tail-recursive?
Там приводится пример, как выразить foldBack (оно же foldr) через fold(оно же foldl) с помощью continuations. И выглядит это как будто мы заменяем использование стека в случае не-tail-recursive функции таким же использованием памяти из head. Причем в случае стека выделение и удаление памяти достаточно дешевое, а вот что будет в случае обычной памяти - вопрос загадочный. Непонятно, есть ли тогда какие-нибудь преимущества у такого преобразования не-tail-recursive функции в tail-recursive?
no subject
no subject
no subject
Кстати, в исходниках Async есть забавный комментарий (там продолжения используются):
"F# don't always take tailcalls to functions returning 'unit' because this is represented as type 'void' in the underlying IL. Hence we don't use the 'unit' return type here, and instead invent our own type."
no subject
Там вместо того, чтобы сделать нормальный foldr, с помощью foldl строилось замыкание, которое потом сделает foldr.
Так вот, это замыкание для своего *выполнения* требует такого же линейного объема *стека*, а не кучи (а само по себе еще и занимает место в куче).
no subject
Посмотрел еще раз пример FoldBack. Вроде бы, выглядит логично (но куда проще было бы взять и переписать все через надежный Async :). Только unit как возвращаемый тип несколько беспокоит меня. Если я правильно понял тот комментарий разработчиков F#, то такое продолжение как в статье может запросто съесть и стек на некоторых версиях .NET, а может и сработать как надо.
no subject