Re[9]: Хвостовая рекурсия и CPS
От: WolfHound  
Дата: 31.01.09 17:06
Оценка:
Здравствуйте, Tissot, Вы писали:

T>Программы написанные на Nemerle работают по .Net-ом вообще-то.

И как это относится к избавлению от стека там где алгоритм без стека не работает?
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[11]: Хвостовая рекурсия и CPS
От: WolfHound  
Дата: 31.01.09 17:09
Оценка:
Здравствуйте, Tissot, Вы писали:

T>Думаю изначально он рассматривался как средство облегчить жизнь разаботчикам. Нужен ли он сейчас — не знаю.

Даже при наличии простейшего макроассемблера весьма сомнительная помощь.
А если учесть что x86'ые call/ret принуждают к далеко не самым эффективным соглащениям о вызовах...
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[10]: Хвостовая рекурсия и CPS
От: Tissot Россия  
Дата: 31.01.09 17:18
Оценка:
Здравствуйте, WolfHound, Вы писали:

T>>Программы написанные на Nemerle работают по .Net-ом вообще-то.

WH>И как это относится к избавлению от стека там где алгоритм без стека не работает?

Так, возвращаемся к началу.

Nikov написал:

При CPS данные, которые бы хранились в стеке, переносятся в кучу. Стек расти не будет.


Ты на это ответил:

Стек это структура данных.
Так вот то что накапливается в куче и есть стек.
И ни куда ты от этого не денешься.
Никак.


Поинт моего сообщения был в том, хоть "стек в куче" и растет, "аппаратный стек" не растет. И это есть гуд.
Re[12]: Хвостовая рекурсия и CPS
От: Tissot Россия  
Дата: 31.01.09 17:21
Оценка:
Здравствуйте, WolfHound, Вы писали:

T>>Думаю изначально он рассматривался как средство облегчить жизнь разаботчикам. Нужен ли он сейчас — не знаю.

WH>Даже при наличии простейшего макроассемблера весьма сомнительная помощь.

И в чем же по-твоему была мотивация тех, кто добавлял эти инструкции в процессор?
Re[13]: Хвостовая рекурсия и CPS
От: Mr.Cat  
Дата: 31.01.09 17:45
Оценка:
Здравствуйте, Tissot, Вы писали:
T>И в чем же по-твоему была мотивация тех, кто добавлял эти инструкции в процессор?

Есть такое ощущение, что ассемблер x86 изначально предназначался для того, чтоб на нем писали люди.
Re: Хвостовая рекурсия и CPS
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.02.09 22:09
Оценка: +1
Здравствуйте, nikov, Вы писали:

N>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style).


Намного интереснее то, что CPS и хвостовая рекурсия — это немного разные вещи. CPS это всего лишь возможность вынести состояние в кучу. А хвостовая рекурсия просто переписывается в цикл. Согласись, что это разные вещи.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Хвостовая рекурсия и CPS
От: thesz Россия http://thesz.livejournal.com
Дата: 01.02.09 22:23
Оценка:
N>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style).

Что позволяет правомочно заявить, что сборка мусора может быть быстрее, чем работа со стеком.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[2]: Хвостовая рекурсия и CPS
От: Beam Россия  
Дата: 01.02.09 23:38
Оценка:
Здравствуйте, thesz, Вы писали:

T>Что позволяет правомочно заявить, что сборка мусора может быть быстрее, чем работа со стеком.


Вы забыли упомянуть о том, что:

1. Это верно только при освобождении памяти. Т.е. сравнивается вытаскивание из стека и освобождение памяти GC. И наоборот, неверно для размещения новых данных в heap (для ускорения в статье предлагается перехватывать "page fault" и вызывать сборщик мусора).
2. Скорость GC "достигается" за счет увеличения количества памяти в несколько раз от необходимого для размещения данных. Т.е. сборщик мусора срабатывает очень редко.
3. Тестирование проводилось на конкретной машине "128-megabyte VAX-11/785" в 1986-1987 гг. На современных процессорах время исполнения инструкций по работе с памятью и стеком может значительно отличаться.

Поэтому, "сборка мусора может быть быстрее, чем работа со стеком", но очень-очень редко
... << RSDN@Home 1.2.0 alpha 4 rev. 1136>>
Best regards, Буравчик
Re[2]: Хвостовая рекурсия и CPS
От: Mr.Cat  
Дата: 02.02.09 01:20
Оценка:
Здравствуйте, thesz, Вы писали:
T>Что позволяет правомочно заявить, что сборка мусора может быть быстрее, чем работа со стеком.

А бобра с ослом можно и совместить, кстати: http://home.pipeline.com/~hbaker1/CheneyMTA.html
Re[9]: Хвостовая рекурсия и CPS
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 02.02.09 05:26
Оценка:
Здравствуйте, Tissot, Вы писали:

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


WH>>>>Почему?

T>>>Потому что в данном случае имеется в виду тот стек, с которым работает процессор.
G>>Какая-то принципиальная разница есть?
T>Конечно есть. В своем стеке ты волен реализовать его так, как тебе нужно, а в аппаратном тебе приходится мириться с существующей реализацией.
Можно не использовать аппаратный стек при наличии хвостовой рекурсии и CPS.

T>>>Каким образом? Работа со стеком .Net-е в конечном счете сводится все к тем же ассемблерным push/pop. Чтобы убрать подобные ограничения придется переделывать процессор.

G>>И кто мешает держать стек на куче? Значение регистра esp можно изменять.

T>Можно, но я не слышал, чтобы .Net делал что-то подобное.

Чтобы убрать ограничения стандартной реализации аппатного стека не нужно переделывать процессор.
Другое дело что в .NET и других платформах этого не делается.
Re[3]: Хвостовая рекурсия и CPS
От: minorlogic Украина  
Дата: 02.02.09 06:16
Оценка:
Здравствуйте, Beam, Вы писали:

B>Поэтому, "сборка мусора может быть быстрее, чем работа со стеком", но очень-очень редко


Стоит читать ? ведь теоретически мы не выполняем никаких действий при размещении на стеке ? как стек может быть медленее ?
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[10]: Хвостовая рекурсия и CPS
От: Tissot Россия  
Дата: 02.02.09 09:22
Оценка:
Здравствуйте, gandjustas, Вы писали:

G>>>Какая-то принципиальная разница есть?

T>>Конечно есть. В своем стеке ты волен реализовать его так, как тебе нужно, а в аппаратном тебе приходится мириться с существующей реализацией.
G>Можно не использовать аппаратный стек при наличии хвостовой рекурсии и CPS.

Но тем не менее он используется.

T>>Можно, но я не слышал, чтобы .Net делал что-то подобное.

G>Чтобы убрать ограничения стандартной реализации аппатного стека не нужно переделывать процессор.
G>Другое дело что в .NET и других платформах этого не делается.

Да, не делается.
Re[4]: Хвостовая рекурсия и CPS
От: Beam Россия  
Дата: 02.02.09 10:21
Оценка:
Здравствуйте, minorlogic, Вы писали:

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


B>>Поэтому, "сборка мусора может быть быстрее, чем работа со стеком", но очень-очень редко


M>Стоит читать ?

Статью? Думаю, что нет.

M>ведь теоретически мы не выполняем никаких действий при размещении на стеке ?

Ну почему же. Выполняем действия и там, и там.
Другое дело, что стек, скорее всего, будет быстрее.

M>как стек может быть медленее ?

Да он и не может быть медленнее. Но вот только это не доказать в общем случае, т.к. зависит от многих факторов.
А пока не доказано, то, наверное, всё же может
... << RSDN@Home 1.2.0 alpha 4 rev. 1136>>
Best regards, Буравчик
Re[2]: Хвостовая рекурсия и CPS
От: nikov США http://www.linkedin.com/in/nikov
Дата: 02.02.09 12:58
Оценка:
Здравствуйте, VladD2, Вы писали:

N>>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style).


VD>Намного интереснее то, что CPS и хвостовая рекурсия — это немного разные вещи. CPS это всего лишь возможность вынести состояние в кучу. А хвостовая рекурсия просто переписывается в цикл. Согласись, что это разные вещи.


После CPS-преобразования любая рекурсивная функция содержит только хвостовую рекурсию, которая может быть преобразована в цикл. То, что в некоторых случаях можно добиться хвостовой рекурсии без CPS-преобразования — я согласен. И согласен, что это разные вещи.
Re: Хвостовая рекурсия и CPS
От: LaPerouse  
Дата: 02.02.09 13:24
Оценка:
Здравствуйте, nikov, Вы писали:

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


WH>>>Хвостовыми считаются вызовы результат кторых возвращается из функции.


K>>Все, понял

K>>Спасибо

N>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style).


И этот факт используется во многих компиляторах. А в некоторых не используется. Например, попробуй посчитать на Scala рекурсивно факториал от 10000 — рекурсия не будет сведена к хвостовой и соответсвтенно не будет пребразована в цикл. А компилятор haskell вполне это делает.
... << RSDN@Home 1.2.0 alpha 4 rev. 1089>>
Социализм — это власть трудящихся и централизованная плановая экономика.
Re[3]: Хвостовая рекурсия и CPS
От: Mr.Cat  
Дата: 02.02.09 14:11
Оценка:
Здравствуйте, nikov, Вы писали:
N>После CPS-преобразования любая рекурсивная функция содержит только хвостовую рекурсию, которая может быть преобразована в цикл.

А вот это уже не факт. Рекурсия тут вполне возможно будет косвенная, если преобразователь не очень умный. Так что надеяться на то, что рекурсивный процесс станет итеративным нельзя. Например, код из небезызвестного EoPL сделал бы примерно следующее.
Было:
(define (fact x)
  (if (= x 0)
      1
      (* x (fact (- x 1)))))

Стало:
(define fact
  (lambda (_rt.cont0 x)
    (= (lambda (_rt.1)
         (if _rt.1
           (_rt.cont0 1)
           (- (lambda (_rt.3)
                (fact (lambda (_rt.2) (* _rt.cont0 x _rt.2)) _rt.3))
              x
              1)))
       x
       0)))
Re[4]: Хвостовая рекурсия и CPS
От: Mr.Cat  
Дата: 02.02.09 14:16
Оценка:
Здравствуйте, Mr.Cat, Вы писали:
MC>Так что надеяться на то, что рекурсивный процесс станет итеративным нельзя.

Т.е. вру, конечно. процесс будет итеративным, но тривиального цикла может не получиться.
Re[11]: Хвостовая рекурсия и CPS
От: swined Россия  
Дата: 11.02.09 11:15
Оценка:
Tissot wrote:

> Поинт моего сообщения был в том, хоть "стек в куче" и растет, "аппаратный

> стек" не растет. И это есть гуд.

но проблема алгоритма то не в аппартном стеке, а в стеке вообще.
Posted via RSDN NNTP Server 2.1 beta
Re[4]: Хвостовая рекурсия и CPS
От: Mr.Cat  
Дата: 11.02.09 11:38
Оценка:
Таки после просмотра scheme to C in 90 minutes признаю свою неправоту. При желании будет цикл, независимо от вложенности лямбд и косвенности рекурсии.
Re[2]: Хвостовая рекурсия и CPS
От: avpavlov  
Дата: 13.02.09 14:31
Оценка:
LP>И этот факт используется во многих компиляторах. А в некоторых не используется. Например, попробуй посчитать на Scala рекурсивно факториал от 10000 — рекурсия не будет сведена к хвостовой и соответсвтенно не будет пребразована в цикл. А компилятор haskell вполне это делает.

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