рекурсивная => нерекурсивная реализация

Ты с этого всегда и начинай

придурок, начинай чтение темы на ЛОРе с первого поста. А то твоё кукареканье тут не в тему.

Один из вариантов - используй fifo/lifo для аргументов и возвращаемых значений (собственно то же, что и делают языки программироавния), только в данном случае стэк у тебя под контролем.

например для языков Java...

Тебе того же желаю, даун.

ARMARM я десятки раз прочел от корки до корки. RTL почти всех ядер ARM читал. Расскажи мне, чего это я тут не знаю, и где там, например, явный ret, вшитый в архитектуру, а не в ABI.

например для языков Java...

Тебе того же желаю, даун.

т.е. незнакомые тебе буквы ты просто отбрасываешь, да?

т.е. незнакомые тебе буквы ты просто отбрасываешь, да?

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

https://ru.wikipedia.org/wiki/Функция_Аккермана

И что? Кто мешает ее сделать нерекурсивной, с самодельным стеком?

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

детка, ты про какой «мой язык» говоришь?

Хвосторекурсивный вызов должен быть в хвосте.

детка, «хвост» и «конец» это там, где return, а не где функция заканчивается.

«хвост» и «конец» это там, где return

В том же C++ не обязательно. В «return f();» он между вызовом f() и return еще много чего вставить может.

То есть, опять же, без return TCO не возможен. О чем тебе и говорили. Если нет явного выхода и tail-call не в хвосте, возможность исчерпать стек и засрать память у тебя остается.

А изначально тут некоторые клоуны утверждали, что хвосторекурсивный вызов не обязан быть в хвосте.

Кто мешает ее сделать нерекурсивной, с самодельным стеком?

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

В том же C++ не обязательно. В «return f();» он между вызовом f() и return еще много чего вставить может.

можно конечно. Тогда это будет не TC. Речь о том, что return вовсе не обязан быть в конце. Он может быть где угодно, и всё равно TCO может быть применена (если ты ничего не вставил после f()).

Речь о том, что return вовсе не обязан быть в конце

Я говорил о том, что вот это рекурсивная => нерекурсивная реализация (комментарий) не не хвостовой вызов. Ты впрегся. А теперь задом начал вилять, ретурн сюда приплел.

То есть, опять же, без return TCO не возможен.

я этого и не оспаривал. Без return TCO может быть только в самом хвосте, да и то не всегда(т.к. вообще говоря, между хвостом и выходом в C++ выполняются деструкторы(возможно), как и при return).

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

в C/C++ и без этого есть Over9000 таких возможностей.

Числа Фибоначчи уже вспоминали?

вот это:

fun qwe(arg) {
if (...) qwe(arg+1) else arg
}

Чем это отличается от ast?

Ты там ретурн где то увидел?

f=function(x){
 if(x) {f(x - 1)}else{"fuck"}
 console.log(x)
}

f(10)
// ::: 0
// ::: 1
// ::: 2
// ::: 3
// ::: 4
// ::: 5
// ::: 6
// ::: 7
// ::: 8
// ::: 9
// ::: 10

И ты про нелокальные выходы не забудь. Допустим я выстроил стек, а потом его сбросил. А если ты все будешь оптимизировать, у тебя вместо этого все побочные эффекты отработают, которые должны были отработать при схлопывании стека.

Как компилятор может знать, какой там дальше код идет, пока не исполнит его

вот как можно быть таким мудаком?

Компилятор вообще не исполняет код. Он его только компилирует.

если тебе так интересно, то вот код C/C++

void f(int x)
{
·   printf("%d\n", x);
·   if(x)
·   ·   f(x-1);
·   else
·   ·   printf("fuck\n");
}

08048630 <_Z1fi>:
 8048630:   53                      push   ebx
 8048631:   83 ec 18                sub    esp,0x18
 8048634:   8b 5c 24 20             mov    ebx,DWORD PTR [esp+0x20]
 8048638:   eb 07                   jmp    8048641 <_Z1fi+0x11>
 804863a:   8d b6 00 00 00 00       lea    esi,[esi+0x0]
 8048640:   4b                      dec    ebx
 8048641:   89 5c 24 04             mov    DWORD PTR [esp+0x4],ebx
 8048645:   c7 04 24 9f 87 04 08    mov    DWORD PTR [esp],0x804879f
 804864c:   e8 9f fd ff ff          call   80483f0 <printf@plt>
 8048651:   85 db                   test   ebx,ebx
 8048653:   75 eb                   jne    8048640 <_Z1fi+0x10>
 8048655:   c7 44 24 20 80 87 04    mov    DWORD PTR [esp+0x20],0x8048780
 804865c:   08
 804865d:   83 c4 18                add    esp,0x18
 8048660:   5b                      pop    ebx
 8048661:   e9 9a fd ff ff          jmp    8048400 <puts@plt>

как видишь, компилятор(gcc) в данном случае сделал TCO, заменив хвостовой вызов на jne 8048640.

И ты про нелокальные выходы не забудь. Допустим я выстроил стек, а потом его сбросил. А если ты все будешь оптимизировать, у тебя вместо этого все побочные эффекты отработают, которые должны были отработать при схлопывании стека.

а сейчас ты про brainfuck?

Компилятор вообще не исполняет код

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

компилятор

исполнит

брысь под лавку со своей скриптотой

Нет, это я приблизительно про longjump, на твоем птичьем языке, вероятно.

Ты не понял о чем я говорю.

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

а теперь — под лавку.

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

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

с тобой, мудаком, сложно общаться.

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

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

08048580 <_Z1fi>:
 8048580:   53                      push   ebx
 8048581:   83 ec 18                sub    esp,0x18
 8048584:   8b 5c 24 20             mov    ebx,DWORD PTR [esp+0x20]
 8048588:   85 db                   test   ebx,ebx
 804858a:   75 24                   jne    80485b0 <_Z1fi+0x30>
 804858c:   c7 04 24 d0 86 04 08    mov    DWORD PTR [esp],0x80486d0
 8048593:   e8 88 fd ff ff          call   8048320 <puts@plt>
 8048598:   89 5c 24 04             mov    DWORD PTR [esp+0x4],ebx
 804859c:   c7 04 24 ef 86 04 08    mov    DWORD PTR [esp],0x80486ef
 80485a3:   e8 68 fd ff ff          call   8048310 <printf@plt>
 80485a8:   83 c4 18                add    esp,0x18
 80485ab:   5b                      pop    ebx
 80485ac:   c3                      ret
 80485ad:   8d 76 00                lea    esi,[esi+0x0]
 80485b0:   8d 43 ff                lea    eax,[ebx-0x1]
 80485b3:   89 04 24                mov    DWORD PTR [esp],eax
 80485b6:   e8 c5 ff ff ff          call   8048580 <_Z1fi>
 80485bb:   eb db                   jmp    8048598 <_Z1fi+0x18>

а что ты этим хотел доказать? Что для не хвостовой рекурсии TCO не работает? Иногда разворачивание таки работает, пруф

08048560 <_Z9factoriali>:
 8048560:   8b 54 24 04             mov    edx,DWORD PTR [esp+0x4]
 8048564:   b8 01 00 00 00          mov    eax,0x1
 8048569:   83 fa 01                cmp    edx,0x1
 804856c:   7f 04                   jg     8048572 <_Z9factoriali+0x12>
 804856e:   eb 0d                   jmp    804857d <_Z9factoriali+0x1d>
 8048570:   89 ca                   mov    edx,ecx
 8048572:   8d 4a ff                lea    ecx,[edx-0x1]
 8048575:   0f af c2                imul   eax,edx
 8048578:   83 f9 01                cmp    ecx,0x1
 804857b:   75 f3                   jne    8048570 <_Z9factoriali+0x10>
 804857d:   c3                      ret

int factorial(int x)
{
·   return x<=1? 1: x*factorial(x-1);
}

это не tail-call школота ты тупая.

Нет, это я приблизительно про longjump, на твоем птичьем языке, вероятно.

а по-русски ты сказать можешь?

tail-call-recursive

//FIXED

то рекурсию убрать gcc не сможет(точнее не захочет)

Именно не сможет.

это не хвостовой вызов

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

Компилятор не может развернуть данный код

может и разворачивает. При некоторых условиях конечно, если у хвоста есть внешняя функция, которую компилятор не может заинлайнить и к которой нет доступа (e.g. printf(3)), то конечно рекурсию будет не развернуть. Также рекурсию не развернуть, если мешают контексты, которые необходимо хранить в стеке. В конце концов, компилятор может рассчитать, что рекурсия тупо _выгоднее_ цикла, и тоже не будет делать TCO.

то рекурсию убрать gcc не сможет(точнее не захочет)

Именно не сможет.

потому-что printf(3)

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

ну куда C/C++ до божественного JavaScript!

Функция Акермана смотрит на тебя!1!1!11

Еще один? И чем тебе так впилась функция Акермана? Что, к ней CPS в SSA неприменимо?

покажи как а?

вот они тут совсем не к месту ибо достаточно умножения матриц

1 1
0 1

Ну вот тебе для начала, CPS-форма Аккермана (на схемке):

(define (ack x y cnt)
  (if (> x 0)
      (if (> y 0)
          (ack x (- y 1) (lambda (n)
                           (ack (- x 1) n cnt)))
          (ack (- x 1) 1 cnt))
      (cnt (+ y 1))
      ))

Сообразишь дальше, как сделать lambda lifting и развернуть все в цикл?

Начал , так довони до конца!111!!

покажи без рекурсии. (и без своего стека, ибо фортран"60" уже изобрели)

То есть, компилятор схемы вместо того чтобы оптимизировать код, предлагает сделать это пользователю, а потом это все называется оптимизацией?

ну и замечания по стилю ветки бы стоило поменять местами заменив > на =

Начал , так довони до конца!111!!

Лень руками делать. А компилятор выдает огромных размеров лапшу.

покажи без рекурсии. (и без своего стека, ибо фортран"60" уже изобрели)

Это как это «без своего стека»? Я тебе такого не обещал. Я обещал избавиться от любых вызовов функций, а стек из lambda lifting тут вылезает, никуда его не денешь.

На фига? CPS-преобразование полностью автоматическое. CPS в SSA тоже автоматически делается (естественно, ценой адского количества локальных переменных, которые потом надо отоптимизировать нахуй).

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

Можно подробнее?

http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

На фига? CPS-преобразование полностью автоматическое. CPS в SSA тоже автоматически делается (естественно, ценой адского количества локальных переменных, которые потом надо отоптимизировать нахуй).

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

и без своего стека, ибо фортран"60" уже изобрели

Смысл слов «без своего стека» мне не очень понятен.

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