Моя диссертация напрямую связана с одним "домашним" ФЯ. Сейчас пробую создать экспериментальную версию компилятора для него. Сам компилятор генерит код на Java. Всё бы хорошо с создаваемым кодом, но есть одна проблема — РЕКУРСИИ. Функциональные языки, как известно, построены, главным образом, на рекурсивных функциях. Но как быть с рекурсией, если при даже небольших глубинах рекурсии (~1000 уровней) получается переполнение стека?
В интерпретаторах это лечится просто — вызвали первую функцию, интерпретируем ее код, встретили в нем вызов другой функции, выполнение первой функции приостановили, стали выполнять вторую функцию и т.д. Рекурсии как таковой нет.
Если же мы генерим код на императивном языке, то получаем классическую рекурсию.
Пока единственный видимый мне вариант состоит в генерации кода, который бы напоминал интерпретатор. То есть каждый вызов невстроенной функции оборачивать в код, который бы либо получал результат уже вычисленной функции, либо выходил из данной функции в вызывающий ее код "интерпретатора".
Может быть уважаемый 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>>Либо я про нее не все слышал, либо она всё-таки не всюду может помочь. К>Никто и не говорит про серебрянную пулю, но вот помогает она очень много где 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 размер стека выставляется один и тот же для всех потоков. А их бывает немало. Так что лучше иметь вектор с контекстами в ОДНОМ месте, чем кучу потоков с огромным, но НЕНУЖНЫМ им стеком. Да и ручное сохранение контекста банально меньше памяти кушать может, чем сохранение контекста в рекурсивных функциях.
Конкретно в нашей реализации используется докрученный для наших целей дек. Работает достаточно быстро.
Сразу оговорюсь что с самим подходом полностью согласен. Кстати в NET 2 для yield (рекурсивный обход) используют список классов, вместо фиберов использующие стек.
M>Попробуйте в Java сделать размер стека потока хотя бы в 100 мег (если у Вас памяти просто жутко много — у меня 1.5 гиг, то поставьте чуть больше).
M>Тогда выясняется неприятный факт, что в Java размер стека выставляется один и тот же для всех потоков. А их бывает немало. Так что лучше иметь вектор с контекстами в ОДНОМ месте, чем кучу потоков с огромным, но НЕНУЖНЫМ им стеком. Да и ручное сохранение контекста банально меньше памяти кушать может, чем сохранение контекста в рекурсивных функциях. M>Конкретно в нашей реализации используется докрученный для наших целей дек. Работает достаточно быстро.
Все от задач, просто суть одна и таже, но у каждого подхода свои премущества и недостатки. Хотя в целом я за динамический стек
и солнце б утром не вставало, когда бы не было меня
На самом деле одно не лучше другого. Пока мы имеем чистую хвостовую рекурсию, то ее переписать в цикл несложно. Но как только алгоритм у нас усложняется, то становится тошно. Ради примера — попробуйте понять закономерность для трансформации функции 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: сделать и результат и все промежуточные результататы аргументами функции:
С другой стороны, мне кажется, что вряд ли есть компиляторы, которые сами преобразуют древовидную рекурсию в хвостовую, как в случае с 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>
Здравствуйте, Serginio1, Вы писали:
M>>Ээээ... Тут стек очень даже используется. Да еще и покрепче, чем в лоб писать (Object + int-поле вместо int-локальной переменной)... M>>Вот если бы каждый объект факториала в новом потоке считался, тогда да...
S> Стек используется только под ссылку на объект при каждом вызове, а вот переменные хранятся в динамической памяти объекта. S> Выигрыш получаем если количество сохраняемых параметров в полях объекта, более чем ссылка под объект S> Можно обойти и хранения ссылки на объет, если сохранять ее в пользовательской очереди (стеке) статическом поле
Думается мне, что и в этом случае компилятор что-то сохраняет в стеке при каждом вызове. Регистры (или их аналог), адрес возврата.
Это чуть ослабляет проблему, но не решает. Хотя как один из методов, да, можно использовать.
Здравствуйте, mik1, Вы писали:
M>З.Ы. Переписать код факториала в вид без рекурсии — это не та проблема. До сих пор не пойму алгоритма для переписывания tree-recursive функций.
Если под tree-recursive функций понимается рекурсивный обход, то опять же на примере списка экземпляров класса, создается новый объект со своими состояниями и вызывается метод этого объекта который сравнивает состояния и либо возвращает результат, либо продолжает идти по дереву.
... << RSDN@Home 1.1.4 stable rev. 510>>
и солнце б утром не вставало, когда бы не было меня
Хранить состояние в стеке или массиве небольшая разница, но принципиальна в доступе, т.к. при обращении к массиву нужно вводить дополнительную коственность, для изменения размера и соответственно скоростью доступа.
