Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, mik1, Вы писали:
M>>З.Ы. Переписать код факториала в вид без рекурсии — это не та проблема. До сих пор не пойму алгоритма для переписывания tree-recursive функций.
S>Если под tree-recursive функций понимается рекурсивный обход, то опять же на примере списка экземпляров класса, создается новый объект со своими состояниями и вызывается метод этого объекта который сравнивает состояния и либо возвращает результат, либо продолжает идти по дереву.
У глобального объекта есть ссылка на текущий объект
у объекта кроме всего прочего есть ссылка на родителя. При этом достигается движение в разных напрвлениях передавая изменяя при этом ссылку на текущий объект.
... << RSDN@Home 1.1.4 stable rev. 510>>
и солнце б утром не вставало, когда бы не было меня
Re[6]: Реализация рекурсии в компиляторах ФЯ
От:
Аноним
Дата:
21.03.06 13:59
Оценка:
Здравствуйте, 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 от общего числа. Тогда уже можно и программиста попросить привести к одной из нескольких форм ручками функцию.
Re[10]: Реализация рекурсии в компиляторах ФЯ
От:
Аноним
Дата:
22.03.06 11:45
Оценка:
Здравствуйте, mik1, Вы писали:
M>А мы в курсе. Нам бы и набора эвристик для частных случаев хватило бы. Процентов так на 50-60 от общего числа. Тогда уже можно и программиста попросить привести к одной из нескольких форм ручками функцию.
Еще конечно в красном драконе и современном ИИ Норвига, например, это все обсасывается со всех сторон.
Re: Реализация рекурсии в компиляторах ФЯ
От:
Аноним
Дата:
22.03.06 12:07
Оценка:
Здравствуйте, mik1, Вы писали:
M>Может быть уважаемый All подскажет более красивые методы решения проблемы рекурсии в компиляторах ФЯ?
Читать побольше про graph reduction и смотреть как это работает в GHC/helium/clean
Причем, конкретно в GHC еще очень просто посмотреть на код т.н "evil mangler"'a (ну и прочих перловых скриптов в дистрибутиве. но вот брать пример с этого хака точно не стоит — ну то есть как подхода к имплементации
ну и если компилить все в С--, то многими вещами себе можно голову особо не забивать — многие оптимизации там встроены. Уж как минимум хвостовые вызовы оно элиминирует. Ну и вообще вещь хорошая, рекомендую.
Re[8]: Реализация рекурсии в компиляторах ФЯ
От:
Аноним
Дата:
22.03.06 13:21
Оценка:
Здравствуйте, 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>И еще раз напомню, что интерпретатору на рекурсию наплевать — он работает прекрасно (и весьма быстро). Проблемы с компилятором.
Интерпретатору не плевать. Компилятор от интерпретатора тут ничем не отличается. Никто не запрещает компилировать в код который не будет использовать системный стек.
):
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
