Бесконечная рекурсия без переполнения стека

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

 

Такой процедуры быть не может. Поставим в соответствие каждому состоянию работы программы следующий набор чисел: (адрес возврата на уровень вложенности 0, адрес возврата на уровень вложенности 1, ..., адрес возврата из текущего уровня вложенности, текущий eip + 1). Адрес возврата считается как в x86 - адрес следующей после call инструкции (можно считать адресом самой инструкции call, тогда в определение не нужно вводить +1). Введём на таких наборах чисел лексикографический порядок. Нетрудно видеть, что при выполнении любой допустимой команды соответствующий набор строго увеличивается (call не уменьшает последнее число в наборе и добавляет ещё одно, ret увеличивает предпоследнее и убирает последнее, прочие команды увеличивают последнее - переходы назад запрещены). Если глубина стека ограничена, то таких наборов конечное число (случай бесконечно длинных процедур исключаем), так что рано или поздно процесс выполнения этой процедуры вынужден будет прерваться. А прерваться он может только возвратом из начального вызова.
Возможность нескольких взаимодействующих процедур, равно как и возможность произвольных действий с возвращаемыми значениями, на рассуждение не влияют.

 

Нужен цикл или рекурсия в чистом виде(чтобы можно было возвращаться)?

 

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

Код (Text):

1. void func( int i )
2. {
3.   if ( i <= 0 ) return;
4.   print( i );
5.   func( i - 1 );
6. };
7.  
8. func( 100000000000000000000 ); // распечатывает числа от 1 до  без циклов.

То понятно как оптимизрующий компилятор разрулил бы эту ситуацию без пререполнения стека при любых входных параметрах в псевдоасме:

Код (Text):

1. void func( int i )
2. {
3.   if ( i <= 0 ) ret;
4.   call print( i );
5.   dec i;
6.   jump func // зная что результат ф-ии не используется и вызывает она сама себя
7.                // непосредственно перед своим выходом мы можем скорректировать
8.                // параметры в стеке и просто перейти на своё же начало.
9.                // если когда-нибудь ret сработает - всё корректно вернется к месту
10.                // call func и не будет никаких side-эффектов.
11. };
12.  
13. call func( 100000000000000000000 ); // распечатывает числа от 1 до  без циклов.

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

 

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

 

aa_dav

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

Код (Text):

1. FUN func: nat -> nat
2. DEF func == \\ a .
3.     IF a > 0 THEN
4.         func(a-1)
5.     ELSE
6.         func(5)
7.     FI

на OPAL тем не менее вызывает переполнение стека. Ну и вопрос собственно не в том, реализуют ли функциональные языки рекурсию, как цикл, а в том, реально ли реализовать цикл (бесконечный, разумеется) через рекурсию.
MSoft

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

Код (Text):

1. xor eax,eax
2. call func
3. ret
4.  
5. func:
6.    not eax
7.    test eax,eax
8.    jz @F
9.       push func
10.       call func
11.    @@:
12. retn

Voodoo
Об оптимизации рекурсивных алгоритмов вопрос не стоит.
Y_Mur

Очень хочу увидеть пример.
SashaTalakin
Это не есть ответ на вопрос. Если удержать esp в определённом интервале невозможно, то бесконечная рекурсия всегда переполнит стек, каких бы размеров он ни был.

 

l_inc

> ...а в том, реально ли реализовать цикл (бесконечный, разумеется) через рекурсию.

Ээээ... Ну технически же уже понятно что можно симитировать рекурсивный цикл через модификацию текущего кадра стека и передачу управления джампов в начало. Но мне непонятно чем вызваны ограничения что так делать нельзя? =) Разве от этого она перестанет быть рекурсией (идеологически)? Поведение то аналогичное. Даже финальный ret поведет себя как следует... Т.е. я лично не понял в чём подвох ограничений. Чисто в том чтобы сделать задачу невыполнимой? Если так, то непонятно само обсуждение...

 

diamond
Мне непонятны Ваши рассуждения. Например:

Но последнее число в наборе - это текущий eip. При рекурсивном вызове (если не трогать взаимовызывающие процедуры) eip именно уменьшается. Равно как и в большинстве случаев ret.
Booster

Эм... реализовать нужно бесконечный цикл. Что значит "рекурсия в чистом виде"?
CyberManiac
Логически разнести стек и код можно где угодно. Достаточно не использовать под стек кодовую память. Но, как я уже писал, перезапись старых адресов возврата в стеке считается переполнением стека. Или имеется в виду не это?

 

Поигрался с примерами - похоже всё-таки без переходов назад и "мухлежа" со стеком нельзя...

Код (Text):

1. ============= masm: ===============
2. .code
3. recursion proc, count:dword
4.   mov eax, [count]
5.   .if eax < 5
6.      add eax, 1
7.      invoke recursion, eax
8.      .if eax < 1
9.         invoke recursion, 1     ; <- 0 здесь приводит к замедленному переполнению стека
10.      .endif
11.   .endif
12.   sub eax, 1
13.   ret
14. recursion endp
15.  
16. start:
17.    invoke recursion, 0
18.    invoke ExitProcess, 0
19. end start
20.  
21. =============== C ===============
22. int recursion(int count)
23. {
24.     if (count < 5)
25.         if (recursion(count + 1) < 1)
26.             recursion(1);   // <- 0 здесь приводит к замедленному переполнению стека
27.     return count - 1;
28. }
29.  
30. void main(void)
31. {
32.     ExitProcess(recursion(0));
33. }

этот пример (одно и тоже на разных языках) позволяет неоднократно гонять закрутку/раскрутку, но возврат к "закрутке" через invoke recursion, 1 или recursion(1) сдвигает точку возврата и приводит к завершению рекурсии, можно не допустить достижения этой новой точки возврата, заменив повторный вход на invoke recursion, 0 или recursion(0), но это приводит к хоть и замедленному, но безвозратному заполнению стека. Соответственно заменив 5 на большое число, и/или увеличив цепочку повторных входов можно добиться очень медленного безвозвратного захламления стека, но совсем исключить его похоже невозможно.

ЗЫ: забавно что msvc 9 позволяет скомпилить это только при отключенной оптимизации, иначе сразу говорит что результат функции = -1 и нечего, тут рекурсию гонять, особенно бесконечную при повторном recursion(0) )

 

aa_dav

Модификация текущего кадра стека - это модификация адреса возврата? Разумеется, что идеологически такой код перестаёт быть рекурсией. Остановимся на высокоуровневых языках. Нельзя использовать циклы и goto (ну и, скажем, вызывать системные функции, т.к. они потенциально могут содержать циклы). Вы ведь не сможете стандартными языковыми средствами подменить адрес возврата? Кстати, пример косвенной модификации адреса возврата в посте 26 - это тоже модификация адреса возврата. Что, собственно, нарушает идеологию рекурсии.
Да... вистовый Windows Defender этот пример называет Rustock.C. Некоторые похожие попытки называл Rustock.B.

 

Y_Mur

Вот-вот... И что усложняет проверку невозможности реализации бесконечного цикла - это различные навороты сверх этого вроде пяти произвольным образом взаимовызывающих процедур.
Похоже, diamond предлагает инварианту, которая показывает, что это невозможно, но я не понял объяснений.

 

l_inc

> Модификация текущего кадра стека - это модификация адреса возврата?

Нет, правятся только параметры вызова. Т.е. вместо того чтобы запихивать в стек новый кадр с параметром i <- i + 1 мы просто в текущем кадре меняем i++; и снова возвращаемся в начало процедуры JUMP-ом. Адрес возврата как раз остаётся как и был - чтобы финальный (и единственный фактический) ret вернул управление туда, откуда наша процедура получила управление.
Но я опять повторюсь - уже в первом посте был запрет на JUMP назад - а с чем это связано? Зачем эти ограничения?

 

l_inc
Пример. Пусть главная процедура находится по адресу 0x10000, управление дошло до адреса 0x12345 и там стоит рекурсивный вызов себя же. Тогда непосредственно перед вызовом call набор состоит из одного числа, (0x12345+1), а в ходе call меняется на набор из двух чисел (0x1234A, 0x10000+1). Далее в ходе выполнения возрастает второе число. Когда дело дойдёт до ret, из (0x1234A, 0x1FFFF+1) получится (0x1234A+1). Лексикографически состояния возрастают: (0x12345+1) < (0x1234A, 0x10000+1) < ... < (0x1234A, 0x1FFFF+1) < (0x1234A+1).

 

Можно придумать разные трики. Например выделяем кусок памяти, копируем себя в него, переходим на новый, удаляем старый. l_inc сейчас скажет, что и этого чудо скипт язык Opal не умеет. Зачем язык который ничего не умеет?

 

aa_dav

Ну так прыжок назад - это стандартный цикл. Какой смысл тогда вообще говорить о рекурсии? Сделаем прыжок назад вообще без всяких параметров... да просто EB FE и будет бесконечный цикл.
Отсутствие циклов в функциональных языках мотивируется обычно тем, что рекурсия - это более мощный инструмент. Т.е. с её помощью можно реализовать все задачи, которые можно реализовать с помощью циклов, но с помощью только циклов нельзя реализовать все задачи, которые можно реализовать с помощью рекурсии. И вот невозможность реализовать бесконечный цикл через рекурсию - это вроде как опровержение такой мотивации.

 

l_inc
Я пожалуй переформулирую инварианту от diamond так:
1) Цикл "закрутки" может быть бесконечным, но он на каждом "обороте" захламляет стек, и неизбежно вызывает его переполнение.
2) Цикл "раскрутки" начинается с адреса следующего за командой самовызова функции и он всегда конечен поскольку его "счётчик" всегда равен количеству "оборотов цикла закрутки".
3) Чтобы вернуться из цикла "раскрутки" в цикл "закрутки" нужна команда перехода назад, которую можно заменить на рекурсию, но в этом случае "старый" цикл "раскрутки", заменяется на новый, начинающийся с команды следующей за новым рекурентным вызовом и к этому новому циклу опять применимы рассужения из п.1, п.2

 

Я бы поспорил скорее не с

а с

поскольку на самом деле нет таких задач которые принципиально не решаются без рекурсии, другое дело что такое решение не всегда очевидно, и имхо единственное оправдание применения рекурси это - "работает и ладно, лень думать о каких-то там побочных эффектах и искать альтернативные пути" )

 

Тогда чем не нравится трик с потоками?

Если бы не ограничение стековой памяти.

 

Нда только сейчас дошло как там всё сильно запущено )
l_inc - ты совершенно прав, что на одних рекурсиях бесконечный цикл не получишь и если циклов и переходов нет принципиально это конечно нечто...

 

l_inc

> Ну так прыжок назад - это стандартный цикл.

Технически - да. Теоретически это просто оптимизация рекурсии при данных условиях.

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

Ааааа... В этом смысле... Ну тут нет опровержения собственно этой мотивации, ибо с помощью рекурсии действительно любой вменяемый ФЯ-компилятор сделает задачу бесконечного цикла выполнимой - исходный код то не был циклом, хоть и в цикл превратился, но разве это важно когда мы обсуждаем СЕМАНТИКУ ЯЗЫКА?