1. Хотелось бы получше разобраться в устройстве хвосто-рекурсивных функций и их вызовов, дабы объяснить человеку, далекому от этой темы - в чем там магия?

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-2.html#%_toc_%_sec_3.5

2. Какие еще популярные ЯП и компиляторы поддерживают оптимизацию данного вида рекурсии?

Большинство функциональных языков. Схема требует этой оптимизации стандартом.

Guy Lewis Steele, Jr.. «Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO». MIT AI Lab. AI Lab Memo AIM-443. October 1977

Кстати, Scala такую оптимизацию в полной мере не поддерживает, но это уже ограничения JVM.

Какие еще популярные ЯП и компиляторы поддерживают оптимизацию данного вида рекурсии?

Scheme, некоторые реализации CL (SBCL), Haskell. А еще посоны говорили, что gcc умеет TCO, поэтому Си тоже можно добавить в список :)

+ Erlang

Боже мой, ну какая магия? Просто в текущем стэк фрэйме заменяются actual parameters на новые и вычисления продолжаются без создания нового фрэйма. По сути вместо рекурсивной функции получился цикл.

С такой позицией и в математике нет никакой магии, даже самой хитровывернутой.

А еще посоны говорили, что gcc умеет TCO, поэтому Си тоже можно добавить в список :)

Опяит таки с ограничениями, variadic functions не совместимы с TCO. А так в список ещё надо добавить OCaml, SML, F# и прочие диалекты ML, Tcl 8.6.

tail call — если функция последним действием вызывает функцию, возвращая её результат, то можно заменить это последнее действие на некий аналог goto в начало другой функции. Собственно, вместо call-вычисления-return-return получается goto-вычисления-return и можно забыть обо всём, что было в оригинальной функции.

tail recursion — частный случай, когда функция последним действием вызывает себя.

erlang.

Tail call может быть рекурсивным (while в F# Async). Что-то неладно в этой терминологии.

То есть, tail call, использующий опосредованную рекурсию внутри call, не является случаем tail recursion по определению, приведенному тобой. Явный диссонанс.

tail recursion — частный случай tail call, когда call идёт на себя. В этом вашем F# фактически описывается функция, не?

ХР - это костыль для недоязычкой не умеющих циклы.

А эстетический оргазм от наблюдения ажурных костылей - извращение.

Твое определение является проблемным безотносительно F#, исходя из общих рассуждений. А, вообще, вот та функция:

        /// Implement the while loop
        let rec whileA gd prog =
            if gd() then 
                bindA prog (fun () -> whileA gd prog) 
            else 
                doneA

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

Еще раз.

1. Функция whileA определена рекурсивно, о чем намекает ключевое слово «rec».

2. Везде используются хвостовые вызовы (не съедается стек).

3. Хвостовой вызов в whileA, использующий рекурсию, не подподает под «твое» определение «хвостовой рекурсии».

4. Явно что-то здесь не так.

whileA не содержит хвостового вызова whileA, с-но хвостовой рекурсии тут нету. С определением всё в порядке.

С какой такой позицией? Что не надо искать магию там где ее нет? Пожалуй, да.

Именно поэтому его реализовали в С.

Видел вот эту статью? Там собраны описания и примеры всяких разных элементов функциональных языков. По сабжу см. п. 7 — Хвостовой вызов.

Awwww, Java-кодерок делает первые шажки, как это мило.

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

Эта фигня идёт от английских определений, где ни кто практически не говорит «tail recursion», но все говорят «tail call». В русском наоборот - «хвостовой вызов» как-то не употребляется. И да, «хвостовая рекурсия» - частный случай «хвостового вызова», но полноценная поддержка последнего - довольно серьёзная «фича», встречающаяся довольно редко. А вот «хвостовую рекурсию» именно через «банальный цикл» (в виде «банального GOTO») поддерживают уже почти все кому не лень.

Не?

whileA не содержит хвостового вызова whileA, с-но хвостовой рекурсии тут нету. С определением всё в порядке.

Именно, что содержит хвостовые вызовы. Там все вызовы - хвостовые. Это одна из фишек продолжений, на которых основана монада Async в F#.

Я тоже думаю, что трудности перевода. Например, буквально позавчера встретил такое выражение в RWH: «tail-recursive function». Как я понимаю, «tail-recursive» больше относится к функциям, тогда как «tail call» относится к самому вызову.

А еще посоны говорили, что gcc умеет TCO, поэтому Си тоже можно добавить в список :)

вериться с трудом - gcc вообще не любит функции раскрывать, а уж рекурсивные...

Хвостовая рекурсия - дрянь, и приличный компилятор не имеет права применять эту копеечную, бесполезную оптимизацию по умолчанию. Соответственно, никакой кодеришко не имеет права рассчитывать на то, что компилятор эту «оптимизацию» говняную сделает.

А почему ХР дрянь, спросите вы? Ну и тупые. Элементарно же - после такой «оптимизации» хрена огрызок вы увидите в stack trace, вместо того, что должно быть на самом деле. Соответственно, дебажить такой говнокод становится просто невозможно.

В день, когда в JVM появится вдруг поддержка хвостовой рекурсии (чур меня, чур, надеюсь, такого не будет никогда), мне придется переходить на какую-либо другую технологию. Может, на C++ вернусь.

Именно, что содержит хвостовые вызовы.

Конечно, содержит. Любая функция содержит хвостовые вызовы (т.к. последний вызов - всегда хвостовой). Но хвостовых вызовов whileA она не содержит. Она _вообще_ не содержит _никаких_ вызовов whileA. Там неявная рекурсия. Сперва идет хвостовой вызов bindA, потом хвостовой вызов санки (я так полагаю, т.к. реализации bindA не знаю) и, наконец, в этой санке хвостовой вызов whileA.

Тогда и циклы - дрянь, ведь они тоже не содержат стектрейса.

Ну, и что имеем? А имеем хвостовой вызов bindA, который рекурсивно вызывает whileA. И этот вызов не подпадает под определение «хвостовой рекурсии» выше. Это раз. Потом, сам рекурсивный вызов whileA является хвостовым (sic!) для whileA (да-да, продолжения), но поскольку он неявный, то он тоже не подпадает под то определение «хвостовой рекурсии». Это два. Нет, тут явно с терминологией что-то не так.

Ладно. Мне надо работать. Разбирайтесь тут сами со своей терминологией. Не удивлюсь, если на википедии есть похожие ляпы.

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

Любая функция содержит хвостовые вызовы (т.к. последний вызов - всегда хвостовой).

Тупой? Где хвостовые вызовы в функции:

int f(int x, int y) { return g(x) + g(y); }

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

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

P.S. и в отличие от register allocation (ну, все помнят в дебаггере облом про «value optimized out») это имеет последствия далеко за пределами интерактивной отладки. Например, если где-то в коде швыряется exception, то его stack trace тоже будет полным враньем, если где-то по дороге были хвостовые говновызовы.

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

мне кажется, или все нормальные люди если и берут в руки дебагер, то делают это с -O0 ?

Тебе кажется. Потому как оптимизации могут сильно поменять поведение кода. Нормальные люди берут в руки дебагер с "-g -O2" как минимум.

Кроме того, смотри выше про exception-ы. Они-то как раз представляют особый интерес, когда в продакшене вылетают.

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

вообще-то никакая информация никуда не девается. То, что в стеке - это ИЗБЫТОЧНАЯ информация, по логике алгоритма там её и быть не должно.

вообще-то никакая информация никуда не девается. То, что в стеке - это ИЗБЫТОЧНАЯ информация, по логике алгоритма там её и быть не должно.

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

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

если у тебя цикл, то промежуточных результатов тоже нет. А стало быть экономится место и время (как не крути, но долбить аккумулятор быстрее, чем пихать результат в стек). Для дебага можешь и дополнительный массив за #ifdef заделать...

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

2. Какие еще популярные ЯП и компиляторы поддерживают оптимизацию данного вида рекурсии?

gcc, например

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

дык не юзай хвостовые вызовы - делов-то? ну или volatile пригодится, если так хочется отключить такое поведение.

дык не юзай хвостовые вызовы - делов-то? ну или volatile пригодится, если так хочется отключить такое поведение.

Что значит «не юзай»? Тупой, что ли? Переписывать код только из-за того, что компилятор писали недоумки? Нет уж, я лучше просто перейду на компилятор, который этого говна ГАРАНТИРОВАННО не делает. Потому что «такое поведение» отключать надо всегда. Пользы от него ноль, один вред.

gcc, например

кстати да

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

08048440 <f>:
 8048440:	53                   	push   ebx
 8048441:	83 ec 18             	sub    esp,0x18
 8048444:	8b 5c 24 20          	mov    ebx,DWORD PTR [esp+0x20]
 8048448:	0f be 03             	movsx  eax,BYTE PTR [ebx]
 804844b:	84 c0                	test   al,al
 804844d:	74 11                	je     8048460 <f+0x20>
 804844f:	90                   	nop
 8048450:	89 04 24             	mov    DWORD PTR [esp],eax
 8048453:	e8 88 fe ff ff       	call   80482e0 <putchar@plt>
 8048458:	43                   	inc    ebx
 8048459:	0f be 03             	movsx  eax,BYTE PTR [ebx]
 804845c:	84 c0                	test   al,al
 804845e:	75 f0                	jne    8048450 <f+0x10>
 8048460:	83 c4 18             	add    esp,0x18
 8048463:	5b                   	pop    ebx
 8048464:	c3                   	ret    

Что значит «не юзай»? Тупой, что ли? Переписывать код только из-за того, что компилятор писали недоумки?

может дело не в бобине, а просто йух сидит в кабине? См. код в моём прошлом сообщении - сколько надо было выпить ъаду, что-бы такое написать IRL?

тогда уж сразу так (многобукаф):

http://www.complang.tuwien.ac.at/schani/diplarb.ps

тогда уж сразу так (многобукаф):

а что там?

Тебе кажется. Потому как оптимизации могут сильно поменять поведение кода. Нормальные люди берут в руки дебагер с "-g -O2" как минимум.

ты просто не видел нормальных людей

Кроме того, смотри выше про exception-ы. Они-то как раз представляют особый интерес, когда в продакшене вылетают.

Проблемы говноязыков какие-то.

много теории о том как правильно реализовывать tail-recursion, и как правильно писать код, чтобы его в tail-recursion можно было завернуть, рассмотрены разные случаи и приведена реализация (как со стороны пишущего код, так и во что это скомпилируется) в gcc, ну и рассмотрены особенности разных архитектур в применении к ХР.

ты просто не видел нормальных людей

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

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

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