Re[9]: Реализация рекурсии в компиляторах ФЯ - Декларативное программирование

Всем доброго времени суток!

Моя диссертация напрямую связана с одним "домашним" ФЯ. Сейчас пробую создать экспериментальную версию компилятора для него. Сам компилятор генерит код на Java. Всё бы хорошо с создаваемым кодом, но есть одна проблема — РЕКУРСИИ. Функциональные языки, как известно, построены, главным образом, на рекурсивных функциях. Но как быть с рекурсией, если при даже небольших глубинах рекурсии (~1000 уровней) получается переполнение стека?
В интерпретаторах это лечится просто — вызвали первую функцию, интерпретируем ее код, встретили в нем вызов другой функции, выполнение первой функции приостановили, стали выполнять вторую функцию и т.д. Рекурсии как таковой нет.
Если же мы генерим код на императивном языке, то получаем классическую рекурсию.
Пока единственный видимый мне вариант состоит в генерации кода, который бы напоминал интерпретатор. То есть каждый вызов невстроенной функции оборачивать в код, который бы либо получал результат уже вычисленной функции, либо выходил из данной функции в вызывающий ее код "интерпретатора".

Может быть уважаемый All подскажет более красивые методы решения проблемы рекурсии в компиляторах ФЯ?

Здравствуйте, mik1, Вы писали:

M>Может быть уважаемый All подскажет более красивые методы решения проблемы рекурсии в компиляторах ФЯ?

Про хвостовую рекурсию ты слыхал?

Здравствуйте, Курилка, Вы писали:

К>Здравствуйте, mik1, Вы писали:

M>>Может быть уважаемый All подскажет более красивые методы решения проблемы рекурсии в компиляторах ФЯ?

К>Про хвостовую рекурсию ты слыхал?

Либо я про нее не все слышал, либо она всё-таки не всюду может помочь.
Например, с числами Фиббоначчи.

int fib(i)
{
if (i==0 || i==1)
return 1;
return fib(i-1) + fib(i-2);
}

Как здесь может помочь хвостовая рекурсия — не очень понимаю...

Здравствуйте, mik1, Вы писали:

M>Здравствуйте, Курилка, Вы писали:

К>>Здравствуйте, mik1, Вы писали:

К>>Про хвостовую рекурсию ты слыхал?

M>Либо я про нее не все слышал, либо она всё-таки не всюду может помочь.
Никто и не говорит про серебрянную пулю, но вот помогает она очень много где
M>Например, с числами Фиббоначчи.

...

M>Как здесь может помочь хвостовая рекурсия — не очень понимаю...
Поиском пользоваться не пытался ? Вот первая же ссылка с гугла:
http://triton.towson.edu/~akayabas/COSC455_Spring2000/Recursion_Iteration.htm
Фибоначчи преобразуется в хвостовую рекурсию довольно просто

К>>>Про хвостовую рекурсию ты слыхал?

M>>Либо я про нее не все слышал, либо она всё-таки не всюду может помочь.
К>Никто и не говорит про серебрянную пулю, но вот помогает она очень много где
M>>Например, с числами Фиббоначчи.

К>...

M>>Как здесь может помочь хвостовая рекурсия — не очень понимаю...
К>Поиском пользоваться не пытался ? Вот первая же ссылка с гугла:
К>http://triton.towson.edu/~akayabas/COSC455_Spring2000/Recursion_Iteration.htm
К>Фибоначчи преобразуется в хвостовую рекурсию довольно просто

Мда, похоже я был слегка не прав.
Спасибо.

Здравствуйте, mik1, Вы писали:

M>В интерпретаторах это лечится просто — вызвали первую функцию, интерпретируем ее код, встретили в нем вызов другой функции, выполнение первой функции приостановили, стали выполнять вторую функцию и т.д. Рекурсии как таковой нет.

А куда же она делась?

Здравствуйте, Трурль, Вы писали:

Т>Здравствуйте, mik1, Вы писали:

M>>В интерпретаторах это лечится просто — вызвали первую функцию, интерпретируем ее код, встретили в нем вызов другой функции, выполнение первой функции приостановили, стали выполнять вторую функцию и т.д. Рекурсии как таковой нет.

Т>А куда же она делась?

Пусть мы (интерпретатор) — есть как бы процессор. Мы идем по коду функции, выполняем условные операторы, арифметику и прочие ВСТРОЕННЫЕ функции (будем считать их командами процессора). Теперь встретили вызов функции. Мы сохраняем текущий контекст в массив (а его то размеры у нас ничем не ограничены, в отличии от стека!) и начинаем исполнять эту вызываемую функцию. Ну и так далее. Получив результат вызываемой функции мы ищем то место, где мы прервали вычисления и идем выполнять нашу первую функцию дальше. Картина огрубленная, но работает все примерно так.
Никаким стеком здесь и не пахнет, как видите.

Здравствуйте, mik1, Вы писали:

M>Здравствуйте, Трурль, Вы писали:

Т>>Здравствуйте, mik1, Вы писали:

M>>>В интерпретаторах это лечится просто — вызвали первую функцию, интерпретируем ее код, встретили в нем вызов другой функции, выполнение первой функции приостановили, стали выполнять вторую функцию и т.д. Рекурсии как таковой нет.

Т>>А куда же она делась?

M>Пусть мы (интерпретатор) — есть как бы процессор. Мы идем по коду функции, выполняем условные операторы, арифметику и прочие ВСТРОЕННЫЕ функции (будем считать их командами процессора). Теперь встретили вызов функции. Мы сохраняем текущий контекст в массив (а его то размеры у нас ничем не ограничены, в отличии от стека!)
Ограничена свободной памятью

M>>>>В интерпретаторах это лечится просто — вызвали первую функцию, интерпретируем ее код, встретили в нем вызов другой функции, выполнение первой функции приостановили, стали выполнять вторую функцию и т.д. Рекурсии как таковой нет.

Т>>>А куда же она делась?

M>>Пусть мы (интерпретатор) — есть как бы процессор. Мы идем по коду функции, выполняем условные операторы, арифметику и прочие ВСТРОЕННЫЕ функции (будем считать их командами процессора). Теперь встретили вызов функции. Мы сохраняем текущий контекст в массив (а его то размеры у нас ничем не ограничены, в отличии от стека!)
S>Ограничена свободной памятью

Хранить состояние в стеке или массиве небольшая разница, но принципиальна в доступе, т.к. при обращении к массиву нужно вводить дополнительную коственность, для изменения размера и соответственно скоростью доступа.
S>В принципе любая рекурсия обходится ручным хранением состояний, что не есть удобно, но это суть одного итого же просто под стеком понимается динамическая память

Попробуйте в Java сделать размер стека потока хотя бы в 100 мег (если у Вас памяти просто жутко много — у меня 1.5 гиг, то поставьте чуть больше).
Тогда выясняется неприятный факт, что в Java размер стека выставляется один и тот же для всех потоков. А их бывает немало. Так что лучше иметь вектор с контекстами в ОДНОМ месте, чем кучу потоков с огромным, но НЕНУЖНЫМ им стеком. Да и ручное сохранение контекста банально меньше памяти кушать может, чем сохранение контекста в рекурсивных функциях.
Конкретно в нашей реализации используется докрученный для наших целей дек. Работает достаточно быстро.

Здравствуйте, mik1, Вы писали:

Сразу оговорюсь что с самим подходом полностью согласен. Кстати в NET 2 для yield (рекурсивный обход) используют список классов, вместо фиберов использующие стек.

M>Попробуйте в Java сделать размер стека потока хотя бы в 100 мег (если у Вас памяти просто жутко много — у меня 1.5 гиг, то поставьте чуть больше).

M>Тогда выясняется неприятный факт, что в Java размер стека выставляется один и тот же для всех потоков. А их бывает немало. Так что лучше иметь вектор с контекстами в ОДНОМ месте, чем кучу потоков с огромным, но НЕНУЖНЫМ им стеком. Да и ручное сохранение контекста банально меньше памяти кушать может, чем сохранение контекста в рекурсивных функциях.
M>Конкретно в нашей реализации используется докрученный для наших целей дек. Работает достаточно быстро.

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

Здравствуйте, Курилка, Вы писали:

Лучше уж эта http://am.rusimport.ru/MsAccess/topic.aspx?ID=266

Здравствуйте, Serginio1, Вы писали:

S>Здравствуйте, Курилка, Вы писали:

S>Лучше уж эта http://am.rusimport.ru/MsAccess/topic.aspx?ID=266

На самом деле одно не лучше другого. Пока мы имеем чистую хвостовую рекурсию, то ее переписать в цикл несложно. Но как только алгоритм у нас усложняется, то становится тошно. Ради примера — попробуйте понять закономерность для трансформации функции fib(n) в ту функцию, то была на приведенной Курилкой ссылке...

Здравствуйте, mik1, Вы писали:
Есть алгоритмы чисто рекурсивные требующие своего стека. В большинстве случаев избавление от использования програмного стека это содание экземпляра класса и инициализация в каждой процедуре.

Для примера

public class Factorial
{ 
   private int _n
  public Factorial(n)
{ _n=n}

    public int fac()
{
    if _n<=0 return 1;
    Factorial factorial =new Factorial(n-1);

   return _n*factorial.fac()

}
}

Здравствуйте, mik1, Вы писали:

M>На самом деле одно не лучше другого. Пока мы имеем чистую хвостовую рекурсию, то ее переписать в цикл несложно. Но как только алгоритм у нас усложняется, то становится тошно. Ради примера — попробуйте понять закономерность для трансформации функции fib(n) в ту функцию, то была на приведенной Курилкой ссылке...

На самом деле, закономерность несложная и по сути напоминает CPS: сделать и результат и все промежуточные результататы аргументами функции:

-- рекурсивно:
fact(n)
  if (n == 1)
    return 1;
  return n * fact(n - 1);

-- хвосто-рекурсивно
fact(n, result)
  if (n == 0)
    return result;
  return fact((n - 1), (n * result));

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

Здравствуйте, z00n, Вы писали:

Z> С другой стороны, мне кажется, что вряд ли есть компиляторы, которые сами преобразуют древовидную рекурсию в хвостовую, как в случае с Fib. Обычно от компиляторов требуют лишь умения правильно работать с хвостовой.
Z> Еще можно попробовать мемоизацию.

Мемоизацию мы пробовали использовать в интерпретаторе.
Он с рекурсией она плохой помощник.

Пусть у нас есть функция

int foo(int n)
{
if (n < 0) return n;
return foo(n-1);
}

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

Другое дело, если аргумент у нас растет между вызовами. Тогда вот мемоизация уже полезна (да и то не всегда — см. дальше).

У нас есть один из тестов.
Там числа представляются в таком виде:

0 = NUL
1 = NUL.SUCC
2 = NUL.SUCC.SUCC
ну и т.д.

Вот в этой арифметике мы считаем числа Фибоначчи. Допустимая глубина рекурсии в процедуре там порядка 1500 уровней.
Сама процедура переводит число в его вышеупомянутое представление.
Вызывается она на каждое из чисел Фибоначчи. Так вот, как только разница между fib(i) и fib(i+1) превысит эти вышеупомянутые 1500, то мы опять нарвемся на стек. Даже не смотря на то, что мы помним все прошлые результаты. Такая вот петрушка.

Здравствуйте, Serginio1, Вы писали:

S>Здравствуйте, mik1, Вы писали:
S> Есть алгоритмы чисто рекурсивные требующие своего стека. В большинстве случаев избавление от использования програмного стека это содание экземпляра класса и инициализация в каждой процедуре.

S>Для примера

S>

S>public class Factorial
S>{ 
S>   private int _n
S>  public Factorial(n)
S>{ _n=n}

S>    public int fac()
S>{
S>    if _n<=0 return 1;
S>    Factorial factorial =new Factorial(n-1);

S>   return _n*factorial.fac()

S>}
S>}
S>

Ээээ... Тут стек очень даже используется. Да еще и покрепче, чем в лоб писать (Object + int-поле вместо int-локальной переменной)...
Вот если бы каждый объект факториала в новом потоке считался, тогда да...

Здравствуйте, mik1, Вы писали:

M>Здравствуйте, Serginio1, Вы писали:

S>>Здравствуйте, mik1, Вы писали:
S>> Есть алгоритмы чисто рекурсивные требующие своего стека. В большинстве случаев избавление от использования програмного стека это содание экземпляра класса и инициализация в каждой процедуре.

S>>Для примера

S>>

S>>public class Factorial
S>>{ 
S>>   private int _n
S>>  public Factorial(n)
S>>{ _n=n}

S>>    public int fac()
S>>{
S>>    if _n<=0 return 1;
S>>    Factorial factorial =new Factorial(_n-1);

S>>   return _n*factorial.fac()

S>>}
S>>}
S>>

M>Ээээ... Тут стек очень даже используется. Да еще и покрепче, чем в лоб писать (Object + int-поле вместо int-локальной переменной)...
M>Вот если бы каждый объект факториала в новом потоке считался, тогда да...

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

Можно обойти и хранения ссылки на объет, если сохранять ее в пользовательской очереди (стеке) статическом поле

... << RSDN@Home 1.1.4 stable rev. 510>>

Здравствуйте, z00n, Вы писали:

Z> На самом деле, закономерность несложная и по сути напоминает CPS: сделать и результат и все промежуточные результататы аргументами функции:

Z>

Z>-- рекурсивно:
Z>fact(n)
Z>  if (n == 1)
Z>    return 1;
Z>  return n * fact(n - 1);

Z>-- хвосто-рекурсивно
Z>fact(n, result)
Z>  if (n == 0)
Z>    return result;
Z>  return fact((n - 1), (n * result));
Z>

З.Ы. Переписать код факториала в вид без рекурсии — это не та проблема. До сих пор не пойму алгоритма для переписывания tree-recursive функций.

Здравствуйте, Serginio1, Вы писали:

M>>Ээээ... Тут стек очень даже используется. Да еще и покрепче, чем в лоб писать (Object + int-поле вместо int-локальной переменной)...
M>>Вот если бы каждый объект факториала в новом потоке считался, тогда да...

S> Стек используется только под ссылку на объект при каждом вызове, а вот переменные хранятся в динамической памяти объекта.
S> Выигрыш получаем если количество сохраняемых параметров в полях объекта, более чем ссылка под объект

S> Можно обойти и хранения ссылки на объет, если сохранять ее в пользовательской очереди (стеке) статическом поле

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

Здравствуйте, mik1, Вы писали:

M>З.Ы. Переписать код факториала в вид без рекурсии — это не та проблема. До сих пор не пойму алгоритма для переписывания tree-recursive функций.

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

... << RSDN@Home 1.1.4 stable rev. 510>>

Здравствуйте, Serginio1, Вы писали:

S>Здравствуйте, mik1, Вы писали:

M>>З.Ы. Переписать код факториала в вид без рекурсии — это не та проблема. До сих пор не пойму алгоритма для переписывания tree-recursive функций.

S>Если под tree-recursive функций понимается рекурсивный обход, то опять же на примере списка экземпляров класса, создается новый объект со своими состояниями и вызывается метод этого объекта который сравнивает состояния и либо возвращает результат, либо продолжает идти по дереву.
У глобального объекта есть ссылка на текущий объект
у объекта кроме всего прочего есть ссылка на родителя. При этом достигается движение в разных напрвлениях передавая изменяя при этом ссылку на текущий объект.

... << RSDN@Home 1.1.4 stable rev. 510>>

Здравствуйте, mik1, Вы писали:

M>Здравствуйте, Serginio1, Вы писали:

S>>Здравствуйте, Курилка, Вы писали:

S>>Лучше уж эта http://am.rusimport.ru/MsAccess/topic.aspx?ID=266

M>На самом деле одно не лучше другого. Пока мы имеем чистую хвостовую рекурсию, то ее переписать в цикл несложно. Но как только алгоритм у нас усложняется, то становится тошно. Ради примера — попробуйте понять закономерность для трансформации функции fib(n) в ту функцию, то была на приведенной Курилкой ссылке...

А зачем убирать рекурсию в общем случае? Широкое применение рекурсии в ФЯ связано, прежде всего, с неиспользованием циклов, но поскольку любой цикл мы можем представить в виде хвостовой рекурсии проблем со стеком в этом случае не будет. Если же мы имеем более сложную рекурсию, то для того, чтобы избежать переполнения стека программист должен сам преобразовать ее либо в цикл (на императивном ЯП) либо в хвостовую рекурсию (на функциональном ЯП).

Статья по теме с отличным списком литературы в конце (я не читал

):
http://citeseer.ist.psu.edu/liu00from.html

M>З.Ы. Переписать код факториала в вид без рекурсии — это не та проблема. До сих пор не пойму алгоритма для переписывания tree-recursive функций.

А какая разница? Вот для фибоначчивидных:

int foo(int n)
{
    if(n < 3)
        return n;
    return 3*foo(n-3) + 2*foo(n-2) + foo(n-1);
}

int foo_tail(int ft_n_3, int ft_n_2, int ft_n_1, int n )
{
    if(n < 3)
        return ft_n_1;
    return foo_tail(ft_n_2, ft_n_1, (3*ft_n_3 + 2*ft_n_2 + ft_n_1), --n);
}

int main()
{
    printf("%d\n", foo(24));
    printf("%d\n", foo_tail(0, 1, 2, 24));
}

Здравствуйте, Аноним, Вы писали:

M>>На самом деле одно не лучше другого. Пока мы имеем чистую хвостовую рекурсию, то ее переписать в цикл несложно. Но как только алгоритм у нас усложняется, то становится тошно. Ради примера — попробуйте понять закономерность для трансформации функции fib(n) в ту функцию, то была на приведенной Курилкой ссылке...

А>А зачем убирать рекурсию в общем случае? Широкое применение рекурсии в ФЯ связано, прежде всего, с неиспользованием циклов, но поскольку любой цикл мы можем представить в виде хвостовой рекурсии проблем со стеком в этом случае не будет. Если же мы имеем более сложную рекурсию, то для того, чтобы избежать переполнения стека программист должен сам преобразовать ее либо в цикл (на императивном ЯП) либо в хвостовую рекурсию (на функциональном ЯП).

Преобразовать самостоятельно? И тем самым повысить уровень вхождения в язык... Ну да, если других путей не останется.
И еще раз напомню, что интерпретатору на рекурсию наплевать — он работает прекрасно (и весьма быстро). Проблемы с компилятором.

mik1,

M>Думается мне, что и в этом случае компилятор что-то сохраняет в стеке при каждом вызове. Регистры (или их аналог), адрес возврата.
M>Это чуть ослабляет проблему, но не решает. Хотя как один из методов, да, можно использовать.

А зачем возвращаться из хвостовой рекурсии?

Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>mik1,

M>>Думается мне, что и в этом случае компилятор что-то сохраняет в стеке при каждом вызове. Регистры (или их аналог), адрес возврата.
M>>Это чуть ослабляет проблему, но не решает. Хотя как один из методов, да, можно использовать.

LCR>А зачем возвращаться из хвостовой рекурсии?

А Вы посмотрите, на какой пост я отвечал. Тогда и поймете, откуда там идет возврат. Речь шла о случаях, когда нельза получить хвостовую рекурсию и остается лишь снизить нагрузку на стек.

mik1,

LCR>>А зачем возвращаться из хвостовой рекурсии?

M>А Вы посмотрите, на какой пост я отвечал. Тогда и поймете, откуда там идет возврат. Речь шла о случаях, когда нельза получить хвостовую рекурсию и остается лишь снизить нагрузку на стек.

Ой.

Здравствуйте, mik1, Вы писали:

M>З.Ы. Переписать код факториала в вид без рекурсии — это не та проблема. До сих пор не пойму алгоритма для переписывания tree-recursive функций.

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

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, mik1, Вы писали:

M>>З.Ы. Переписать код факториала в вид без рекурсии — это не та проблема. До сих пор не пойму алгоритма для переписывания tree-recursive функций.

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

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

Здравствуйте, mik1, Вы писали:

M>А мы в курсе. Нам бы и набора эвристик для частных случаев хватило бы. Процентов так на 50-60 от общего числа. Тогда уже можно и программиста попросить привести к одной из нескольких форм ручками функцию.

А, ну тады полезно будет прочитать вот это например:
http://citeseer.ist.psu.edu/zaadnoordijk01source.html
Обратить внимание на библиографию в конце.
и еще вот это:
http://citeseer.ist.psu.edu/peytonjones96compiling.html
это в плане подхода и ваще.

Еще конечно в красном драконе и современном ИИ Норвига, например, это все обсасывается со всех сторон.

Здравствуйте, mik1, Вы писали:

M>Может быть уважаемый All подскажет более красивые методы решения проблемы рекурсии в компиляторах ФЯ?

Читать побольше про graph reduction и смотреть как это работает в GHC/helium/clean
Причем, конкретно в GHC еще очень просто посмотреть на код т.н "evil mangler"'a (ну и прочих перловых скриптов в дистрибутиве. но вот брать пример с этого хака точно не стоит — ну то есть как подхода к имплементации

важные ссылки по теме:
http://citeseer.ist.psu.edu/peytonjones92implementing.html
http://citeseer.ist.psu.edu/leroy90zinc.html

Здравствуйте, Аноним, Вы писали, но недописали:

забыл сказать
вот еще на что точно стоит обратить внимание:
http://repetae.net/john/computer/jhc/
прогрессивный компилятор хаскеля

как минимум почитать там описание и посмотреть ссылки
особенно вот это:
http://www.cs.chalmers.se/~boquist/phd/index.html

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

Здравствуйте, mik1, Вы писали:

M>Преобразовать самостоятельно? И тем самым повысить уровень вхождения в язык... Ну да, если других путей не останется.
M>И еще раз напомню, что интерпретатору на рекурсию наплевать — он работает прекрасно (и весьма быстро). Проблемы с компилятором.

Вам другой аноним дело говорит — любой итерационный паттерн выражается хвостовой рекурсией, а что касается "вхождения в язык", то никто почти никогда непосредственным образом рекурсивно итерацию не описывает. Есть более общие способы для выражения итерационных паттернов. Так любая примитивная рекурсия выражается через fold. Ну и в частных случаях — map/filter (которые выражаются уже через фолдинг) и т.п. Это не считая потоков.

так определение for, если очень нужен на хаскеле будет выглядеть так:

for list f = mapM_ f list

после чего

for [1..5] print -- печатает числа от 1 до 5

-- ну или развернуто
for [1..5] (\i -> do
    print i 
)

Очень понятно и подробно это все описывается здесь: http://mitpress.mit.edu/sicp/full-text/book/book.html
В том числе и компиляция в регистровую машину.
Ну и жесткой концептуальной разницы между интерпретатором и компилятором тут нет. Она надумана.

Здравствуйте, mik1, Вы писали:

M> Всё бы хорошо с создаваемым кодом, но есть одна проблема — РЕКУРСИИ. Функциональные языки, как известно, построены, главным образом, на рекурсивных функциях. Но как быть с рекурсией, если при даже небольших глубинах рекурсии (~1000 уровней) получается переполнение стека?

Прочитайте про CPS-преобразование. Если компилируете, например, в Си, то промежуточный код с применением этого
преобразования всегда легко привести к последовательности функций с хвостовыми вызовами. Стек в таких случаях
надо иметь свой, а не использовать Сишный (так надо — GC можно более эффективный реализовать). Получается очень быстро, эффективно, и никакого растущего стека.

M>В интерпретаторах это лечится просто — вызвали первую функцию, интерпретируем ее код, встретили в нем вызов другой функции, выполнение первой функции приостановили, стали выполнять вторую функцию и т.д. Рекурсии как таковой нет.

???

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

Здравствуйте, mik1, Вы писали:

M> Мы сохраняем текущий контекст в массив (а его то размеры у нас ничем не ограничены, в отличии от стека!)

Продайте пожалуйста мне ваш компьютер с неограниченной памятью. Я готов заплатить ЛЮБУЮ цену (серьёзно)!

M> и начинаем исполнять эту вызываемую функцию. Ну и так далее. Получив результат вызываемой функции мы ищем то место, где мы прервали вычисления и идем выполнять нашу первую функцию дальше. Картина огрубленная, но работает все примерно так.
M>Никаким стеком здесь и не пахнет, как видите.

Пахнет, ещё как.

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

Здравствуйте, mik1, Вы писали:

M>Преобразовать самостоятельно? И тем самым повысить уровень вхождения в язык...

Дайте пользователю хорошую библиотеку комбинаторов и итераторов.

M> Ну да, если других путей не останется.
M>И еще раз напомню, что интерпретатору на рекурсию наплевать — он работает прекрасно (и весьма быстро). Проблемы с компилятором.

Интерпретатору не плевать. Компилятор от интерпретатора тут ничем не отличается. Никто не запрещает компилировать в код который не будет использовать системный стек.

	От:	mik1
	Дата:	20.03.06 11:17
	Оценка:

От:	Курилка	http://kirya.narod.ru/
Дата:	20.03.06 11:24
Оценка:	2 (1) +2

	От:	mik1
	Дата:	20.03.06 11:35
	Оценка:

От:	Курилка	http://kirya.narod.ru/
Дата:	20.03.06 11:43
Оценка:	6 (1)

	От:	mik1
	Дата:	20.03.06 11:53
	Оценка:

От:	Serginio1	https://habrahabr.ru/users/serginio1/topics/
Дата:	20.03.06 12:29
Оценка:

От:	Lazy Cjow Rhrr	lj://_lcr_
Дата:	22.03.06 03:52
Оценка:

	От:	z00n
	Дата:	21.03.06 10:39
	Оценка:

	От:	Аноним
	Дата:	21.03.06 13:59
	Оценка: