LINUX.ORG.RU

Зачем нужна хвостовая рекурсия?

 , ,


1

2

Как известно, она нужна для того, чтобы ркурсивные вызовы превращать в цикл. Это звучит глуповато. Н*я писать циклы через жопу, если их можно написать напрямую. Некоторые утверждают, что, якобы, рекурсия — более выразительное средство, чем циклы. Это утверждение спорное, к тому же, те кто это утверждает, обычно думают, что компилятор с поддержкой опимизации хp разворачивает любой рекурсивный код, тогда как он разворачиват только хвосторкурсивный, который представляет из себя гребаный адЪ. Я, BTW, что-то не слишком часто наблюдаю, чтобы кто-то писал в хвосторекурсивном стиле.

Так зачем же она нужна? Дело опять в оптимизации? Или это просто дешвые понты фп-дрочеров?

UPD. Я в курсе, тащемта, что в языках с запретом присваивания циклы просто нвозможно написать, я просто думал, что есть другие причины (кроме ограничений языка). Например в SICP уделено ей немало, нсмотря на то, что scheme разрешает присваивания. Видел даже питонистов, ратующих за то, чтобы в питоне запилили оптимизацию. На*й она им нужна?



Последнее исправление: anonimous (всего исправлений: 2)

Ответ на: комментарий от emulek

кто тебе сказал, что я буду юзать машинный стек? Или что его юзает компилятор ФП язычка?

Так у тебя никакого стека не хватит, при чем тут машинный? Посчитай на каком количестве итераций отвалится нехвосторекурсивная версия факториала при 10 гигах оперативки, например.

anonymous
()
Ответ на: комментарий от emulek

Там внутри неонкаmalloc(3).

Нет конечно там никаких маллоков, иначе выделение памяти бы работало как в сишичке, а не на несколько порядков быстрее.

anonymous
()
Ответ на: комментарий от anonymous

Так у тебя никакого стека не хватит, при чем тут машинный? Посчитай на каком количестве итераций отвалится нехвосторекурсивная версия факториала при 10 гигах оперативки, например.

дык можно же освобождать неиспользуемую память. Т.е. когда ты считаешь 5!, то

4*5→20

3*20→60

тут 20 уже не нужно, возвращаем системе память.

2*60→120

а теперь можно вернуть память под 60.

т.к. памяти у нас 18`446`744`073`709`551`616 байт, то переполнение будет не скоро. Лень считать, но думаю, что мы просто не доживём до этого момента(т.к. сложность умножения растёт экспоненциально).

emulek
()
Ответ на: комментарий от anonymous

Нет конечно там никаких маллоков, иначе выделение памяти бы работало как в сишичке, а не на несколько порядков быстрее.

если в твоём коде на сишечке память выделяется на несколько порядков медленнее, то у тебя просто руки из жопы.

emulek
()
Ответ на: комментарий от korvin_

И то, и другое ведь раскрывается в одинаковый letrec.

ilammy ★★★
()
Ответ на: комментарий от jtootf

Ссылочная прозрачность «есть» не у программиста, а у производителя компилятора. Проще: если, скажем, Ларри Уолл или Остерхаут трахались с языком ради того, чтобы программистам было ништяк, то тут все с точностью до наоборот, авторы языка заставляют трахаться программистов ради удобного парсинга. Фича то всегда есть, да, токо вопрос в том, чья фича.

anonymous
()
Ответ на: комментарий от anonymous

При чём тут парсинг вообще?

anonymous
()
Ответ на: комментарий от emulek

Ну так ты в функцию будешь передавать не само длинное число, а указатель или ссылку. Тогда ничего копировать не надо.

Тем более, я уверен, что скопировать длинное число в разы быстрее, чем умножить его на пусть даже и int

Waterlaz ★★★★★
()
Ответ на: комментарий от anonymous

нехвосторекурсивная версия факториала

На каждой итерации тратится 4 байта на адрес возврата и 4 байта на данные. Итого для 10^10 байт стека можно сделать ~10^9!. Но длина получившегося числа будет во много раз больше, чем 10Гбайт.

На самом деле единственный выигрыш — скорость. Не приходится записывать адрес возврата. Ну и когда стек был 64Кб, тогда действительно спасало от переполнения.

monk ★★★★★
()
Ответ на: комментарий от Waterlaz

Ну так ты в функцию будешь передавать не само длинное число, а указатель или ссылку. Тогда ничего копировать не надо.

да мне поровну, что ты там передаёшь, я говорю о том, ГДЕ ты будешь это всё хранить. Если ты будешь это всё хранить в стеке, то это будет быстрее. На старых компьютерах с этим была проблема, из-за того, что стек растёт в одну сторону, а память не слишком большая. Но сейчас у нас виртуальная память и 64 бита, потому переполнение стека если и бывает, то очень редко(и то, вряд-ли мы до него доживём, т.к. оперативная память у нас довольно медленная. Мы просто тупо не успеем забить весь стек).

Тем более, я уверен, что скопировать длинное число в разы быстрее, чем умножить его на пусть даже и int

надежды юношей питают… Если данные не лезут в кеш(а у нас они не лезут), то у нас остаётся RAM, а она ОЧЕНЬ медленная, по сравнению с CPU. Особенно на запись(процесс записи очень сложный, т.к. ядер больше одного, а RAM одна. Надо встать в очередь, и ждать, пока память освободится. А потом ждать, пока память станет консистентной, т.е. согласованной для всех ядер. И не забудь про все кеши, т.к. данные надо ещё и через них протаскивать, это тоже время и штрафные такты. И ничего с этим не поделать, увы(факториал медленнее расти не станет, хоть ты тресни).

emulek
()
Ответ на: комментарий от monk

На каждой итерации тратится 4 байта на адрес возврата и 4 байта на данные. Итого для 10^10 байт стека можно сделать ~10^9!. Но длина получившегося числа будет во много раз больше, чем 10Гбайт.

для рекурсивного алгоритма логично данные тоже хранить в стеке, а не только ссылки. При TC сборщик мусора может освобождать ненужные хвосты, потому память расходуется также, как на итеративном алгоритме. Но скорость выше, за счёт более простого алгоритма аллокации, не нужно искать дыры, просто отрезай нужные куски памяти, она всё равно виртуальная.

emulek
()
Ответ на: комментарий от emulek

дык можно же освобождать неиспользуемую память.

Конечно, можно - это и называется ТСО. А без ТСО у тебя там не будет неиспользуемой памяти.

тут 20 уже не нужно

Чтобы 20 было не нужно - нужно ТСО. Без ТСО у тебя будет держаться ссылка на фрейм с двадцаткой и нет никакого способа определить, что этот фрей «не нужен».

т.к. сложность умножения растёт экспоненциально

Она растет экспоненциально по той причине, что экспоненциально растет выделение памяти :)

anonymous
()
Ответ на: комментарий от emulek

если в твоём коде на сишечке память выделяется на несколько порядков медленнее, то у тебя просто руки из жопы.

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

anonymous
()
Ответ на: комментарий от monk

На каждой итерации тратится 4 байта на адрес возврата и 4 байта на данные.

Ну, условно говоря, у нас без ТСО еще будут храниться все хвосты, а сумма их длинн как раз примерно равна результату, то есть еще потребление памяти в куче удвоено (с ТСО эти хвосты ГЦ сможет собрать). При более медленном росте потребления памяти с итерациями профит будет значительно больше, например, при линейном потреблении «лишняя память» будет расти как квадрат от «нужной».

anonymous
()
Ответ на: комментарий от emulek

Если ты будешь это всё хранить в стеке, то это будет быстрее.

Нет, не будет. Стек на куче работает так же быстро, как и системный.

Если данные не лезут в кеш(а у нас они не лезут), то у нас остаётся RAM, а она ОЧЕНЬ медленная, по сравнению с CPU.

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

anonymous
()
Ответ на: комментарий от emulek

Но скорость выше, за счёт более простого алгоритма аллокации, не нужно искать дыры

Дыры и так не надо искать, аллокация в куче с перемещающим сборщиком ничем не отличается от аллокации на стеке.

На стеке аллоцируются только ссылки - как раз по упомянутой тобой причине. Это значительно быстрее, т.к. эти данные потом не придется копировать.

anonymous
()
Ответ на: комментарий от anonymous

На стеке аллоцируются только ссылки - как раз по упомянутой тобой причине. Это значительно быстрее, т.к. эти данные потом не придется копировать.

Ах, да, еще если аллоцировать на стеке - то резко возрастет потребление памяти, т.к. сборщик не умеет освобождать память на стеке.

anonymous
()

CPS, F# Async workflow, монада Cont, (ограниченный в силу JVM) плагин продолжений в Scala, и т.п, и т.д.

dave ★★★★★
()
Ответ на: комментарий от anonymous

Без ТСО у тебя будет держаться ссылка на фрейм с двадцаткой и нет никакого способа определить, что этот фрей «не нужен».

Я говорю про несколько другое TCO, когда call НЕ меняется на jmp. Т.е. в коде будет рекурсия самого кода, но вот для данных TCO будет применено.

emulek
()
Ответ на: комментарий от anonymous

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

почему «не будет»? В C++ это всё делается достаточно просто, данные для GC хранятся в классе, и освобождаются когда нужно. И всё это реализуется поверх ::new/::delete.

emulek
()
Ответ на: комментарий от anonymous

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

а само число где по твоему лежит, как не в контексте функции?

emulek
()
Ответ на: комментарий от anonymous

Ах, да, еще если аллоцировать на стеке - то резко возрастет потребление памяти, т.к. сборщик не умеет освобождать память на стеке.

это проблемы GC. Если мы в C++, то они решаемые, мы просто будем использовать машинный стек для ссылок и адресов возврата, а сами данные будем хранить в другом стеке в куче.

emulek
()
Ответ на: комментарий от emulek

Я говорю про несколько другое TCO, когда call НЕ меняется на jmp.

Ну про свое собственное ТСО емулека ты можешь говорить что угодно. Только и называй его тогда как-то по-другому.

anonymous
()
Ответ на: комментарий от emulek

почему «не будет»?

Это будут свои собственные написанные с нуля аллокаторы, не имеющие ничего общего со стандартными.

anonymous
()
Ответ на: комментарий от emulek

это проблемы GC.

Нет, это не проблемы GC.

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

Именно так и делается, лол. Для ссылок и адресов возврата используется стек, а данные хранятся на куче.

anonymous
()
Ответ на: комментарий от emulek

а само число где по твоему лежит, как не в контексте функции?

Само число лежит в куче (если это бигнум).

anonymous
()
Ответ на: комментарий от emulek

да мне поровну, что ты там передаёшь, я говорю о том, ГДЕ ты будешь это всё хранить.

Выделю кусок памяти и буду там его хранить.

Но сейчас у нас виртуальная память и 64 бита, потому переполнение стека если и бывает, то очень редко(и то, вряд-ли мы до него доживём, т.к. оперативная память у нас довольно медленная.

Это где так? В сишечке и глазом моргнуть не успеешь, как стек закончится.

надежды юношей питают… Если данные не лезут в кеш(а у нас они не лезут), то у нас остаётся RAM, а она ОЧЕНЬ медленная, по сравнению с CPU. Особенно на запись(процесс записи очень сложный, т.к. ядер больше одного, а RAM одна. Надо встать в очередь, и ждать, пока память освободится. А потом ждать, пока память станет консистентной, т.е. согласованной для всех ядер. И не забудь про все кеши, т.к. данные надо ещё и через них протаскивать, это тоже время и штрафные такты. И ничего с этим не поделать, увы(факториал медленнее расти не станет, хоть ты тресни).

Тебе что так, что эдак не будет хватать кеша. При чем тут TCO?

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

ещё раз: отличай реализацию от алгоритма. Тот стек, что в сишке, это одна из реализаций. Встроенная и дефолтная. Ничто не мешает тебе сделать свой стек в куче, как в этом вашем лиспе. В этом-то стеке в куче и можно хранить все контексты функций. А в машинном стеке останутся адреса возврата и ссылки на наш стек в куче.

emulek
()
Ответ на: комментарий от emulek

А в машинном стеке останутся адреса возврата и ссылки на наш стек в куче.

Нету никакого «машинного стека».

anonymous
()
Ответ на: комментарий от anonymous

Не забывай, с кем разговариваешь. Этот утырок считает, что прочитать слово по смещению от ESP быстрее, чем по смещению от любого другого регистра.

anonymous
()
Ответ на: комментарий от anonymous

Нету никакого «машинного стека».

точнее ты про него не в курсе.

Этот утырок считает, что прочитать слово по смещению от ESP быстрее, чем по смещению от любого другого регистра.

не нужно приписывать мне свой бред.

emulek
()
Ответ на: комментарий от emulek

Не отрицай, баран, что ты смел блеять, что доступ к стеку быстрее, чем к произвольному массиву в куче.

anonymous
()
Ответ на: комментарий от anonymous

баран это ты. Стек(его вершина) практически 100% лежит в L1. А вот куча — не факт. Потому доступ к стеку практически всегда быстрее.

emulek
()
Ответ на: комментарий от emulek

Ты таки баран. Речь шла про большой массив, более одного cache line. Еще не было темы, в которой ты, шлюшка, не обосралась.

anonymous
()
Ответ на: комментарий от anonymous

Ты таки баран. Речь шла про большой массив, более одного cache line.

разве что только в твоих фантазиях. IRL большой массив в стек не засовывают.

emulek
()
Ответ на: комментарий от emulek

точнее ты про него не в курсе.

Вот тебе планка с оперативной памятью, покажи, где там стек.

anonymous
()
Ответ на: комментарий от emulek

Стек(его вершина) практически 100% лежит в L1. А вот куча — не факт. Потому доступ к стеку практически всегда быстрее.

А стек не в куче по-твоему находится, ебанько?

anonymous
()
Ответ на: комментарий от anonymous

На моей планке оперативной памяти нету никакого %ESP, извини.

твоя планка и работать не будет без процессора. Ты просто не туда смотришь.

emulek
()

Все эти иллюзорные сложности запиливают хотя-бы ради облегчения жизни GC, который, в свою очередь, запилен ради облегчения жизни разработчику.
Для примера, сравни GC в Java и Erlang.

blexey ★★★★★
()
Ответ на: комментарий от anonymous

Большой - больше cache line, то есть 64 байт, и не выровненный по границе cache line.

1. в L1 больше одной линии.

2. я предлагал там хранить лишь ссылки размером 4 или 8 байт.

3. есть ещё L2, он тоже быстрее кучи.

Короче: машинный стек конечно плох тем, что маленький(и не расширяемый), за то из-за этого он более быстрый(из-за компактности).

emulek
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.