О хвостовой рекурсии

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

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

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

а можно в двух словах? Лично мне непонятно, ЗАЧЕМ? Вот код который выше - тупой, и он сворачивается. Лично я не понимаю, как его сделать хоть на что-то годным? Вот так например:

void f(const char *s)
{
	if(!*s)
		return;
	char c = *s++;
	f(s);
	printf("%c", c);
}

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

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

а можно в двух словах?

нет, прочитай хотя бы abstract

Лично мне непонятно, ЗАЧЕМ?

ЗАЧЕМ ЧТО?

Лично я не понимаю, как его сделать хоть на что-то годным?

и?

Но это не хвостовая рекурсия, и она НЕ сворачивается в цикл.

и что дальше то? что ты этим доказал?

Ну ясно, студентота. Давай, до свидания!

если честно, но в open source дебагер попросту не нужен... Не, это действительно так...

Почему?

Спасибо, уже стало попроще.

ЗАЧЕМ ЧТО?

зачем ХР нужна. Можно пример кода?

Почему?

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

Только в коде ничего не ясно. Есть проекты побольше чем Cheese

Да, и у меня опечатка, надо «в начале функции ставишь if»

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

В догонку:

Henry G. Baker. Garbage in/garbage out: When bad programs happen to good people. ACM SIGPLAN Notices, 32(3):27{31} March 1997.

M. Anton Ertl. Stack caching for interpreters. In SIGPLAN ’95 Conference on Programming Language Design and Implementa- tion, pages 315{327}, 1995

так же github://hopc пример, где это явно использовалось.

советую не тратить время зря.

1. Дык гугл же.
2. F# например.

является хвостовым (sic!)

Я что-то не понял, кого именно ты тут цитируешь, чтобы sic-ать?

Переводи с латыни: «именно так!»

Странно ты sic erat scriptum перевел.

sic - отдельное слово.

жжошь

Твоя программа упала по SIGSEGV.

Твои действия?

В математике всё, что не тривиально, - ошибочно.

Ты вообще программист, или так, студентота? Не похож ты на программиста, если честно.

в гриме не видно, да

Ты вообще программист, или так, студентота? Не похож ты на программиста, если честно.

«The most effective debugging tool is still careful thought, coupled with judiciously placed print statements.»

Честно, дебагер стараюсь по возможности не трогать.

Это победа.

А имеем хвостовой вызов bindA, который рекурсивно вызывает whileA.

Вызов whileA в bindA не рекурсивный.

Потом, сам рекурсивный вызов whileA является хвостовым (sic!) для whileA

Хвостовым вызовом для whileA является вызов bindA. Вызов whileA вообще для whileA никаким вызовом не является - ни хвостовым, ни нехвостовым, т.к. этого вызова там банально нет.

И этот вызов не подпадает под определение «хвостовой рекурсии» выше.

Вызов bindA в whileA - хвостовой. Вызов санки в bindA - хвостовой. Вызов whileA в санке - хвостовой. Что там у вас не подпадает и почему должно подпадать?

но поскольку он неявный, то он тоже не подпадает под то определение «хвостовой рекурсии»

Конечно, не подпадает. Он и не должен. С какой стати, собственно?

Вызов «+» - хвостовой.

Например, если где-то в коде швыряется exception, то его stack trace тоже будет полным враньем, если где-то по дороге были хвостовые говновызовы.

Рекурсивные (в том числе неявно) хвостовые вызовы только засоряют стек, так что это правильно, что их убирают (эти вызовы всегда эквивалентны циклу). Нерекурсивные можно preserve (т.к. их всегда конечное число, это не противоречит семантике хвостовых вызовов), что и делается в нормальных языках. В результате стектрейс получается полный.

Ты что, тупой? «Оптимизация» хвостовых вызовов СТИРАЕТ из стека НЕОБХОДИМУЮ для дебага информацию. А в случае с циклом все на месте, ничто никуда не исчезает.

В случае с циклом имеется _точно та же_ информация, что и в случае хвосто-рекурсивной реализации этого цикла. Так что либо информация стирается и циклом в том числе, либо никакой нужной информации не стирается при оптимизации TCO. Выбирай.

Если у меня цикл, то я могу breakpoint хотя бы разумно поставить и повторить.

Точно так же можно поставить брекпоинт и с TCO.

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

В цикле тоже вся история потеряна, и ты не знаешь где поставить брекпоинт.

зачем ХР нужна.

Иногда она удобнее, чем цикл. Ну и кроме того речь не о ХР, а о TCO в общем. Спрашивать зачем нужна TCO, ну это то же самое, что спрашивать, зачем нужно RA или инлайнинг.

Мне надоело с тобой спорить. Вижу, что это бессмысленно.

А чего со мной спорить? Есть общепринятые определения. Хвостовой вызов вообще формально строго определяется в семантике конкретного языка. Формулами, а не словами.

Твоя программа упала по SIGSEGV. Твои действия?

исправлять быдлокод?

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

Иногда она удобнее, чем цикл.

примеры кода будут? или так, попиз^Wпотрепаться?

Ну и кроме того речь не о ХР, а о TCO в общем. Спрашивать зачем нужна TCO, ну это то же самое, что спрашивать, зачем нужно RA или инлайнинг.

ага. ещё тоже самое, что спрашивать, зачем нужно 2*2. Ну и зачем?

В Си? +? Функцией? Юноша, вы дёбил?

Чушь и какашка. Еще один баран, путающий хвостовую рекурсию в частности с хвостовыми вызовами вообще. Не понимаешь, что вся цепочка вызовов может оказаться рекурсивной, и ты получишь stack trace из одного элемента, а как и почему ты туда попал - неизвестно?

Точно так же можно поставить брекпоинт и с TCO.

Нельзя. Идиот. В случае с циклом я знаю, каким путем исполнение туда пришло. В случае с «оптимизацие» хвостовых вызовов информация о control flow потеряна.

А в каком месте исправлять искать с помощью 100500 printf'ов ?

ага. ещё тоже самое, что спрашивать, зачем нужно 2*2. Ну и зачем?

Зачем нужны оптимизации? Ну чтобы программа работала быстрее и занимала меньше памяти. А ты не знал?

Еще один баран, путающий хвостовую рекурсию в частности с хвостовыми вызовами вообще.

я как раз говорил только о хвостовых вызовах.

Не понимаешь, что вся цепочка вызовов может оказаться рекурсивной

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

и ты получишь stack trace из одного элемента, а как и почему ты туда попал - неизвестно?

С циклом то же самое.

Нельзя. Идиот. В случае с циклом я знаю, каким путем исполнение туда пришло.

В случае с TCO и preserved stack тоже.

Какой цикл, придурок? Все функции в цкпочке могут быть разными.

А в каком месте исправлять искать с помощью 100500 printf'ов ?

ну если у тебя 100500 мест с былокодом - то да... Придётся так делать. Конечно давить 100500 раз F8 или что там у тебя next step - оно проще, надёжнее и безопаснее.

Я открою дамп в _отладчике_, посмотрю просмотрю стек и исправлю проблемное место. Ну а такой хелло-ворлдщик как ты может конечно развлекаться с расстановкой 100500 принтфов и 100500 перекомпиляций/перезапусков на каждый принтф.

Я открою дамп в _отладчике_, посмотрю просмотрю стек и исправлю проблемное место.

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

Зачем нужны оптимизации? Ну чтобы программа работала быстрее и занимала меньше памяти. А ты не знал?

нет. я не знал, не знаю, и похоже не узнаю, за кой хрен городить антиоптимизацию в надежде, что мой цикл завёрнутый в ХР компилятор развернёт обратно в цикл. Ты можешь сказать ЗАЧЕМ заворачивать цикл в ХР? Зачем его обратно разворачивать - мне понятно.

В 90% случаев так получается. В остальных случаях логи/valgrind/gdb.

В 90% случаев так получается.

90%? Везет тебе.

Я открою дамп в _отладчике_, посмотрю просмотрю стек и исправлю проблемное место.

ты откроешь дамп, и увидишь 100500 ОДИНАКОВЫХ точек входа. И на 100501й креш из-за переполнения стека. Моя программа тупо зависнет прокручивая цикл. Это хуже/лучше?

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

передёргиваешь: у нас есть ОДИН цикл свёрнутый в ХР. Вопрос - нужно-ли что-бы компилятор его разворачивал? да/нет?

Мой ответ - ХР не нужна. Вообще. Ибо я не видел ни одного примера, где она помогает. Потому оптимизация не имеет смысла, как оптимизация деления на ноль.

ЗЫЖ и да, лучше 100500 принтфов в дебаге, чем засранный стек и в дебаге, и в продакшене. Хотя теоретикам типа тебя этого не понять похоже.

ты откроешь дамп, и увидишь 100500 ОДИНАКОВЫХ точек входа. И на 100501й креш из-за переполнения стека. Моя программа тупо зависнет прокручивая цикл. Это хуже/лучше?

ЩИТО? Это ты к чему?

передёргиваешь: у нас есть ОДИН цикл свёрнутый в ХР. Вопрос - нужно-ли что-бы компилятор его разворачивал? да/нет?

Я про отладчик, который по твоим словам «не нужен».

ЗЫЖ и да, лучше 100500 принтфов в дебаге, чем засранный стек и в дебаге, и в продакшене. Хотя теоретикам типа тебя этого не понять похоже.

Ты как всегда в свое репертуаре — позорно слил и в кусты/на другую тему.