люди, как рекурсию сделать?

>Современные процессоры ближе к машине Тьюринга

Чем? Памятью и лентой?

>и по своей прирове итеративны.

Лямбда-редукция также итеративна. Есть функция f, есть даные g, нужно посчитать терм f g. Итеративно применяем бета-редукцию до тех пор, пока не получим финальный терм (кажется так называется терм, который нельзя редуцировать дальше). Этот терм и есть результат.

>Видимо, ты просто не понял. Именно про это и говорили.

Ты хот тред то прочитай %)

>Почему "Нет", если из дальнейших твоих слов следует "Да"?

Почему следует "Да" если "Нет"

>Ладно, я свою точку зрения сформулировал.

В разговоре недостаточно сформулировать свою точку зрения. Надо еще и воспринять и понять чужую. Без этого получается монолог :)

>>Неее, в этом случае зло в "тупом" программисте

>Спорим я могу написать такой компилятор, что любой достаточно длинный цикл будет вываливаться по нехватке стека :-)

Опять проблема в тупом программисте, на этот раз авторе компилятора :)

>Есть очевидные и однозначные критерии, позволяющие определить, что вызов можно заменить безусловным переходом. Так почему же стоит считать _правильным_ компилятор, не делающий этого? Вот если процессор такую операцию не поддерживает - другое дело:-)

Ты это вообще к чему, если не секрет?

>Жаль Антихриста не было. ;-|)

Ты думаешь модератору и так работы было мало???

>>почему же стоит считать _правильным_ компилятор, не делающий этого

>Ты это вообще к чему, если не секрет?

Ты недавно писал, "нужно оптимизировать руками на случай если компилятор тупой". Я намекаю на то, что в этом случае нужно менять компилятор.

Правильно сказать - пока не получим выражение в НОРМАЛЬНОЙ ФОРМЕ.

От МТ сей процесс отличается тем, что порядок применение редукций недетерминирован, и не обязательно каждое преобразование будет приближать нас к НФ - к примеру, мы можем сначала всё в комбинАторную форму привести (e.g., если хотим компилять ленивый лямбда-язык).

WFrag(21.01.2005 6:32:09):

>>Современные процессоры ближе к машине Тьюринга

>Чем? Памятью и лентой?

Да

>Правильно сказать - пока не получим выражение в НОРМАЛЬНОЙ ФОРМЕ.

Ага, именно так.

>От МТ сей процесс отличается тем, что порядок применение редукций недетерминирован,

Да, это так. Но если нормальная форма существует, то она единственна, а значит порядок роли не играет.

>и не обязательно каждое преобразование будет приближать нас к НФ - к примеру, мы можем сначала всё в комбинАторную форму привести (e.g., если хотим компилять ленивый лямбда-язык).

Да? Именно альфа-конверсией и бета-редукцией? Т.е без усложнения терма, единственные допустимые операции - альфа-конверсия и бета-редукция.

Нет, конечно же - с усложнением.

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

P.S. Нормальная форма существует ВСЕГДА. ;)

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

Ну, вопрос бы абстрактный.

>P.S. Нормальная форма существует ВСЕГДА. ;)

Не согласен.

(lamda (x) x x) (lambda (x) x x)

У этого терма нормальной формы нет (по крайней мере по тому определенюи нормальной формы, которое я знаю). Если я правильно понимаю, такие термы - это аналог зациклившейся машины Тьюринга.

Я обычно молчу во время таких научно-популярных дискусий, но тут решил высказаться. В книжках к тем курсам из которых ты почернул сведения про функцию Аккермана, чуть дальше доказывается вообще то равномощность оператора будем звать его просто -- while (в случае с языком C и for) и рекурсивных функций, такое вот дело, соответсвенно про неприведение к нерекуррентному виду это ты не по делу, так что не знаю что и думать про неимоверную глубину твоих знаний.

pustota1

Это вклад русских... математиков в С++, теперь тимплэйты тюрингово полный язык, да. Конкретно, товарища А. Степанова, писателя STL