Так ли нужна оптимизация хвостовых вызовов?

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

твоё утверждение что ТСО это только саморекурсия заменяемая на итерацию.

и не нужен тут стек ибо концевые вызовы.

а так конечно условный гоуту и индексные переменые достаточны всем :)

стек не потому выкинуть можно , что он переодичен , а потому , что концевой вызов по сути показывает что в «списке» есть узел который не нужно хранить ибо при popе не будет ни как использован ибо концевой.

есть. Смотри внимательнее.

Где?

find(node *x)
{
 find(x->left);
 find(x->right);// (***1)
 // (***2)
}

твоё утверждение что ТСО это только саморекурсия заменяемая на итерацию.

Где? Как раз наоборот - устал повторять, что «хвостовая рекурсия» - подмножество всех ТС.

та ды ок.

Ну вот ты сам себя и опровергаешь. Ты-то утверждал, что относительная стоимость jmp и call может зависеть от контекста, а теперь признаешь, что call - это тот же jmp с подвыпердыхтом.

стек не потому выкинуть можно , что он переодичен , а потому , что концевой вызов по сути показывает что в «списке» есть узел который не нужно хранить ибо при popе не будет ни как использован ибо концевой.

главное - это есть или нет информация в стеке? Если стек служит только для хранения фиксированного числа переменных, и детерминированных и независимых от данных адресов возврата, то он не нужен, и _может_ быть оптимизирован итеративно. Для x86 (и наверное для ARM) это почти всегда ведёт к экономии(если на каждой итерации требуется много данных, то их всё равно придётся хранить на стеке, в этом случае tco возможно, но к экономии обычно НЕ приводит). Да и вообще, _обязательность_ применения tco ИМХО - бред. А вот в _возможности_ я не вижу ничего плохого - почему я должен думать, как в ЭТОМ процессор быстрее? Пусть компилятор думает, это его работа, а не моя.

Где?

вторая find транслируется в call, а } за ней транслируется в ret. Можешь попробовать с -O0 -S.

Ну вот ты сам себя и опровергаешь. Ты-то утверждал, что относительная стоимость jmp и call может зависеть от контекста, а теперь признаешь, что call - это тот же jmp с подвыпердыхтом.

где тут противоречие? Да, call это push+jmp. В разном коде время выполнения их(vs развёрнутый код после TCO) ОЧЕНЬ разное.

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

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

Да и вообще, _обязательность_ применения tco ИМХО - бред. А вот в _возможности_ я не вижу ничего плохого - почему я должен думать, как в ЭТОМ процессор быстрее? Пусть компилятор думает, это его работа, а не моя.

Не вижу предмета спора: естественно компилятору решать, когда можно применять ТСО, а когда - нет

а вот обход правого узла возвращает нас в (***2). Никакое это НЕ TCO

Второй вызов find - хвостовой, соответственно, при ТСО он будет оптимизирован и стек расти не будет.

Или приводи пример, когда call будет быстрее чем jump

call может быть быстрее jmp например если код с jmp не лезет в кеш L1 (или даже в линейку этого кеша). Не забудь, что развёрнутый код TCO обычно заметно больше.

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

посмотри. Посмотри, КАК твой любимый компилятор сделает тут TCO. Можешь и ручками попробовать.

Второй вызов find - хвостовой, соответственно, при ТСО он будет оптимизирован и стек расти не будет.

подумай ещё раз.

Посмотри, КАК твой любимый компилятор сделает тут TCO. Можешь и ручками попробовать.

Он не мой любимый :) Я его вообще не могу запустить из-за некоторых косяков :( И что он там накосячил - его проблемы, и ни как не [не]возможность применения ТСО.

Посмотри, КАК твой любимый компилятор сделает тут TCO. Можешь и ручками попробовать.

Он не мой любимый :) Я его вообще не могу запустить из-за некоторых косяков :( И что он там накосячил - его проблемы, и ни как не [не]возможность применения ТСО.

если тебе не нравится твой компилятор - смени его или попробуй вручную. Вопрос не в этом.

Просто представь дерево, и подумай, что ты будешь делать после обработки ветки? возвращаться наверх (а это куда?) или поворачивать направо? Если ты используешь мой код, проблемы нет - переменная «x» у тебя автоматически вспоминается, а возвращаешься ты именно туда, куда нужно.

А всё потому, что задача сама по себе рекурсивная, и развернуть её в конечную итерацию невозможно в принципе (придётся велосипедить свой список, для хранения точек возврата и направления. Фактически делать стек вместо того, что есть в C/C++).

Если ты используешь мой код, проблемы нет - переменная «x» у тебя автоматически вспоминается, а возвращаешься ты именно туда, куда нужно.

За каким хреном что будет вспоминаться, если я вижу «зацикливание вызовов» и ничего более? По мне приведенный кусок кода бессмысленный чуть более, чем полностью. Или я чего-то не догоняю :)

За каким хреном что будет вспоминаться, если я вижу «зацикливание вызовов» и ничего более? По мне приведенный кусок кода бессмысленный чуть более, чем полностью. Или я чего-то не догоняю

недогоняешь. Смысл кода прост:

• обходим левое поддерево
• обходим правое поддерево
• возвращаемся

ну да, в начало надо ещё if(!x) return; поставить, дабы не сегфолтнулось в листе. Именно так команда rm -rf уничтожает каталоги.

менять на jmp тут нельзя, по той простой причине, что нам нужно запомнить, ОТКУДА мы вошли, что-бы выйти туда-же. Ну и кроме того, переменная x тоже разная. Сначала это корень, потому узел первого уровня, потом второго… Итого, если мы сейчас на уровне N у нас в стеке N указателей на узлы в которых мы были, и ещё N адресов возврата, причём они там разные - левый или правый. Типа

X0 L X1 L X2 R X3 L X4 R

Код не так прост, как кажется, потому-что понятие «вернуться» не эквивалентно понятию «перейти в точку Б». Да и понятие «вспомнить значение переменной в этой точке» не эквивалентно «изменить значение переменной». Хотя в простых примерах типа факториала это одно и то же.

О чем тут думать? Есть конкретное определение хвостового вызова и конкретное поведение компилятора в этом случае. Второй вызов find - хвостовой, по определению (любой последний вызов в функции является хвостовым, вообще написать ф-ю без хвостовых вызовов невозможно), с proper TCO он будет оптимизирован и стек при этом вызове расти не будет.

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

Именно так.

(а это куда?)

На предыдущий стекфрейм, очевидно. А куда еще можно вернуться из функции? Только на предыдущий стекфрейм.

А всё потому, что задача сама по себе рекурсивная, и развернуть её в конечную итерацию невозможно в принципе

А ТСО ничего не имеет общего с разворачиванием в итерацию.

ну да, в начало надо ещё if(!x) return; поставить

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

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

Или я опять чего-то не догоняю, или рассказываю букварь :(

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

Так не нужно.

Сначала это корень, потому узел первого уровня, потом второго… Итого, если мы сейчас на уровне N у нас в стеке N указателей на узлы в которых мы были, и ещё N адресов возврата, причём они там разные - левый или правый. Типа

X0 L X1 L X2 R X3 L X4 R

А, вот тот момент который ты не понимаешь. стекфреймы левых переходов останутся, т.к. первый вызов нехвостовой. А вот стекфреймы правых вызовов уйдут, то есть без ТСО будет на стеке X0 L X1 L X2 R X3 L X4 R, с ТСО будет на стеке X0 L X1 L X3 L. То есть если у нас, например, будет обход дерева, в котором все листы идут только право, то без ТСО будет стековерфлоу, а с ТСО - память расти не будет, какого бы размера ни было дерево. Можешь сам написать код и проверить.

О чем тут думать? Есть конкретное определение хвостового вызова и конкретное поведение компилятора в этом случае. Второй вызов find - хвостовой

насколько я знаю, TC определяется не так. Может я и не прав, покажи, как это происходит.

На предыдущий стекфрейм, очевидно. А куда еще можно вернуться из функции? Только на предыдущий стекфрейм.

не только. Выше код факториала, который работает в одном стекфрейме.

А ТСО ничего не имеет общего с разворачиванием в итерацию.

что же это?

TC определяется не так.

А как ещё, кроме как «call, являющийся последней операцией перед ret»? И уж никак не «последний call перед ret», ибо между ними может быть куча других операций. Фактически call+ret. Соответственно наличие любой «постобработки» убивает ТСО на корню.

tail call - это последний вызов функции, если он является функциональным. Если в яп операторов нету (все - функции) то любой последний вызов. Поскольку практически в любой ф-и есть хоть один вызов, то практически в любой ф-и будет ТСО.

не только. Выше код факториала, который работает в одном стекфрейме.

Ну и все равно при возврате из факториала происходит возврат на предыдущий стекфрейм. Вопрос в том, какие стекфреймы вообще есть (и какой будет предыдущим). Между «стекфрейм на каждый вызов» и «один стекрефм на все вызовы» есть еще множество промежуточных ситуаций.

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

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

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

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

не «возможно», а почти наверняка. Если ты видишь каталог, то наверняка надо посмотреть, есть-ли там ещё другие файлы/каталоги.

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

что ты пристал к возврату? Считай, что оно просто ищет все узлы, и считает их сумму в глобальной переменной. А запоминать есть что: во первых значение x, которое испортится внутри другой find, во вторых - адрес возврата. Тот факт, что узел правый, и его второй раз смотреть не надо.

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

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

Или я опять чего-то не догоняю, или рассказываю букварь

да, букварь. Кнут, Искусство Программирования, том ЕМНИП 1, «основные структуры данных», в самом конце.

с ТСО будет на стеке X0 L X1 L X3 L.

а с ТСО - память расти не будет

сам то понял, что сказал?

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

не могу, ибо не понимаю, как это «на стеке X0 L X1 L X3 L» сделать без стека?

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

следовательно будь стэк данных отделно это просто снятие и выкидиывание со стека всего локального фрэйма

и вызов концевой функции через jmp без помещения в стек возврата так что вызваная вернёт деду напрямую.

так как сами аругументы функции могут быть функциями = это добавляет чутку сложности когда и как двигать вершину стека

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

Надо вернуться в прошлый правый(*)

Зачем? Прошлый правый уже полностью обработан, в прошлом правом только ret остался, который можно спокойно убрать с ТСО и вернуться сразу «домой».

Узел правее правого(*) остаётся не просмотренным.

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

ну блин , у тя контекст внимания что 2 слова?

речь про случай «линейного» последнесторонего дерева когда все не концевые вызовы переходят в лист , а концевые не уращивают стэк.

короче концевой вызов допускает реализацию с замедлением(в идеале нулевой рост) роста стэка вот и всё.

>не будет обращенией к текущим локальным(включая поля аргументов текущего вызова)

именно с этой точки зрения оказывается понятной почему имена аргументов в первой версии С были в заголовке - а их типы в секции между заголовком функции и её телом.

подобное было и в других языках-современиках.

А как ещё

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

Соответственно наличие любой «постобработки» убивает ТСО на корню.

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

p(char *s)
{
 if(!*s) return;
 p(s+1);
 putchar('Z');
}

Но если печатать *s, то TCO ломается - строка печатается наоборот. Символы загоняются в стек, а печатаются перед возвратом, начиная с последнего.

сам то понял, что сказал?

Да, понял. А вот ты - нет.

не могу, ибо не понимаю

Ты читать не умеешь? Написано же - расти не будет в том случае, если длина левых поддеревьев ограничена. Вот пример:

> (define lst (build-list 10000000 add1)
> (define (tree-sum tree)
    (cond
      [(integer? tree) tree]
      [(null? tree) 0]
      [else (begin (tree-sum (car tree)) (tree-sum (cdr tree)))]))
> (tree-sum lst)

здесь память выделяется под список lst и потом при выполнении tree-sum не растет. Теперь поменяй begin на + (вызов (tree-sum (cdr tree)) станет нехвостовым) и сравни.

как это «на стеке X0 L X1 L X3 L» сделать без стека?

Почему без стека?

что там она делает - это уже не важно.

Важно. Ибо если она что-то делает там, где у тебя // (***2), то это не ТСО. А если ничего не делает, то после отработки правого обхода x тебе уже нафиг не нужен, ибо тебе осталось только что вернуться на пред. уровень. А если и там это правый обход, то тебе тоже ничего не надо, кроме как вернуться на пред. уровень и т.д.

tail call - это последний вызов функции, если он является функциональным. Если в яп операторов нету (все - функции) то любой последний вызов.

а если хвостовой дважды? В расчёте факториала есть (* n (factorial (- n 1))) тут на хвосте (* а потом (factorial. Толку мне от умножения TCO, если это тривиальная функция?

не могу, ибо не понимаю, как это «на стеке X0 L X1 L X3 L» сделать без стека?

Можно не мучаться, да и просто взять F# async - там уже все придумано за нас. Будет тебе обход дерева без съедания стека просто за красивые глаза, если я правильно уловил суть вашей беседы - особо не вчитывался.

Ну и все равно при возврате из факториала происходит возврат на предыдущий стекфрейм. Вопрос в том, какие стекфреймы вообще есть (и какой будет предыдущим). Между «стекфрейм на каждый вызов» и «один стекрефм на все вызовы» есть еще множество промежуточных ситуаций.

у меня в main() один фрейм. И куча вызовов factorial() внутри.

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

Ну это твои фантазии, константной стека и чего-то там детерминированность никак не связана с хвостовыми вызовами.

не любой.

Любой.

тут есть TCO

Нет, тут как раз уже не будет ТСО. Иди и почитай определение, а?

В стеке одно и тоже.

Нет, в стеке не одно и то же. При входе в p надо сохранить старое значение s и адрес возврата, чтобы потом выполнить putchar('Z');

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

p(char *s)
{
 if(!*s) return;
 putchar('Z');
 p(s+1);
}

под предыдущем подразумевается явно фрэйм - можно конечно замутить недоТСО которое для случая концевого вызова хоть и уменьшает фрейм перед вызовом но не в «ноль»

бред какой-то. «недоTCO»???

ТCO тут теоретическая, ибо вообще говоря, компилятор не может быть уверен, что putchar ничего не портит.

ТСО тут практическая, ибо по выходу из putchar совершенно всё равно, портил он там что или нет. И куда возвращаться из putchar - в p, чтобы сразу вернуться в место её вызова, или сразу в это место - безразлично.

Но если печатать *s, то TCO ломается - строка печатается наоборот. Символы загоняются в стек, а печатаются перед возвратом, начиная с последнего.

Код давай

а если хвостовой дважды?

Он не может быть дважды. Совершенно очевидно, что _последний_ вызов - он один (ну разве что в разных ветках if, но это тоже не «дважды»).

В расчёте факториала есть (* n (factorial (- n 1))) тут на хвосте (* а потом (factorial

На хвосте тут *. factorial нехвостовой. Ни одинажды, ни дважды, ни трижды.

Толку мне от умножения TCO, если это тривиальная функция?

Нету толку. Но это хвостовой вызов, в языках с proper TCO он будет оптимизирован.

вот тут уже будет ТСО. А в оригинальном случае - нет, не будет.

не путай ТСО и tail recursion

И?

tail recursion - частный случай ТСО, в чем проблема, не понял?

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

в данном случае(с деревом) TCO не получится потому, что в C/C++ во фрейме есть ещё и адрес возврата. И потому, хоть x и не используется между call/ret, но вот ret использует адрес, и он вовсе не всегда указывает на начало. В половине случаев ret кидает в середину. Потому-то call/ret НЕ эквивалентно jmp.