Здравствуйте, nikov, Вы писали:
N>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style).
Намного интереснее то, что CPS и хвостовая рекурсия — это немного разные вещи. CPS это всего лишь возможность вынести состояние в кучу. А хвостовая рекурсия просто переписывается в цикл. Согласись, что это разные вещи.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, nikov, Вы писали:
N>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style).
Попробуй перепиши функцию Аккермана так чтобы ей не был нужен стек в том или ином виде...
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
N>>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style). WH>Попробуй перепиши функцию Аккермана так чтобы ей не был нужен стек в том или ином виде...
Что значит "том или ином"? При CPS данные, которые бы хранились в стеке, переносятся в кучу. Стек расти не будет.
Здравствуйте, WolfHound, Вы писали: WH>Попробуй перепиши функцию Аккермана так чтобы ей не был нужен стек в том или ином виде...
Есть вполне формальный алгоритм перевода. Другое дело, что нехвостовые вызовы после cps приводят к накоплению на том же стеке или в куче данных, необходимых для континуаций.
Здравствуйте, WolfHound, Вы писали:
N>>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style). WH>Попробуй перепиши функцию Аккермана так чтобы ей не был нужен стек в том или ином виде...
// F#
#light
let ackermann m n =
let rec ackermann' continuation m n =
match m with
| 0I -> continuation (n + 1I)
| m ->
match n with
| 0I -> ackermann' continuation (m - 1I) 1I
| n -> ackermann' (ackermann' continuation (m - 1I)) m (n - 1I)
ackermann' id m n
Здравствуйте, nikov, Вы писали:
N>Что значит "том или ином"?
То и значит.
Как ни крути, а стек в явном или не явном виде останется.
N>При CPS данные, которые бы хранились в стеке, переносятся в кучу. Стек расти не будет.
Стек это структура данных.
Так вот то что накапливается в куче и есть стек.
И ни куда ты от этого не денешься.
Никак.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Mr.Cat, Вы писали:
MC>Есть вполне формальный алгоритм перевода.
Я в курсе.
MC>Другое дело, что нехвостовые вызовы после cps приводят к накоплению на том же стеке или в куче данных, необходимых для континуаций.
И я о томже.
Как ни крути, а если алгоритму действительно нужен стек то ни какой CPS не спасет.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
N>>При CPS данные, которые бы хранились в стеке, переносятся в кучу. Стек расти не будет. WH>Стек это структура данных. WH>Так вот то что накапливается в куче и есть стек. WH>И ни куда ты от этого не денешься. WH>Никак.
Нет, стек в данном случае некорректно рассматривать как всего-лишь "структуру данных".
Стек "выполнения" — это относительно небольшой участок памяти фиксированного размера, а стек как "структура данных" может не иметь подобных ограничений.
Здравствуйте, Tissot, Вы писали:
T>Нет, стек в данном случае некорректно рассматривать как всего-лишь "структуру данных".
Почему?
T>Стек "выполнения" — это относительно небольшой участок памяти фиксированного размера, а стек как "структура данных" может не иметь подобных ограничений.
Это зависит от реализации стека.
Вполне возможно реализовать "стек исполнения" так чтобы у него небыло подобных ограничений.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
T>>Нет, стек в данном случае некорректно рассматривать как всего-лишь "структуру данных". WH>Почему?
Потому что в данном случае имеется в виду тот стек, с которым работает процессор.
T>>Стек "выполнения" — это относительно небольшой участок памяти фиксированного размера, а стек как "структура данных" может не иметь подобных ограничений. WH>Это зависит от реализации стека. WH>Вполне возможно реализовать "стек исполнения" так чтобы у него небыло подобных ограничений.
Каким образом? Работа со стеком .Net-е в конечном счете сводится все к тем же ассемблерным push/pop. Чтобы убрать подобные ограничения придется переделывать процессор.
Здравствуйте, Tissot, Вы писали:
T>Здравствуйте, WolfHound, Вы писали:
T>>>Нет, стек в данном случае некорректно рассматривать как всего-лишь "структуру данных". WH>>Почему? T>Потому что в данном случае имеется в виду тот стек, с которым работает процессор.
Какая-то принципиальная разница есть?
T>>>Стек "выполнения" — это относительно небольшой участок памяти фиксированного размера, а стек как "структура данных" может не иметь подобных ограничений. WH>>Это зависит от реализации стека. WH>>Вполне возможно реализовать "стек исполнения" так чтобы у него небыло подобных ограничений.
T>Каким образом? Работа со стеком .Net-е в конечном счете сводится все к тем же ассемблерным push/pop. Чтобы убрать подобные ограничения придется переделывать процессор.
И кто мешает держать стек на куче? Значение регистра esp можно изменять.
Здравствуйте, Mr.Cat, Вы писали:
T>>Чтобы убрать подобные ограничения придется переделывать процессор.
MC>Ограничения на стек налагаются операционной системой. На том же x86 нет аппаратных ограничений на размер стека (ну кроме очевидных).
В операционной системе тоже. Только речь не о наличии ограничений, а о том, что размер, будучи однажды задан, нельзя поменять.
Здравствуйте, gandjustas, Вы писали:
WH>>>Почему? T>>Потому что в данном случае имеется в виду тот стек, с которым работает процессор. G>Какая-то принципиальная разница есть?
Конечно есть. В своем стеке ты волен реализовать его так, как тебе нужно, а в аппаратном тебе приходится мириться с существующей реализацией.
T>>Каким образом? Работа со стеком .Net-е в конечном счете сводится все к тем же ассемблерным push/pop. Чтобы убрать подобные ограничения придется переделывать процессор. G>И кто мешает держать стек на куче? Значение регистра esp можно изменять.
Можно, но я не слышал, чтобы .Net делал что-то подобное.
Здравствуйте, Tissot, Вы писали: T>В операционной системе тоже.
Не тоже, а только.
T>Только речь не о наличии ограничений, а о том, что размер, будучи однажды задан, нельзя поменять. http://msdn.microsoft.com/en-us/library/ms686774(VS.85).aspx.
man pthread_create
Здравствуйте, Mr.Cat, Вы писали:
T>>В операционной системе тоже. MC>Не тоже, а только.
Кажется, я не совсем ясно выразил, что хотел сказать. Под "тоже" я имел в виду, что в операционной системе тоже нет ограничений на размер стека, выделяемого потоку.
T>>Только речь не о наличии ограничений, а о том, что размер, будучи однажды задан, нельзя поменять. MC>http://msdn.microsoft.com/en-us/library/ms686774(VS.85).aspx. MC>man pthread_create
MC>Задавайте, если так надо.
Задать можно. Нельзя поменять после того, как задал.
Здравствуйте, Tissot, Вы писали:
T>>>Нет, стек в данном случае некорректно рассматривать как всего-лишь "структуру данных". WH>>Почему? T>Потому что в данном случае имеется в виду тот стек, с которым работает процессор.
И что?
T>Каким образом? Работа со стеком .Net-е в конечном счете сводится все к тем же ассемблерным push/pop.
А при чем тут вобще .NET?
T>Чтобы убрать подобные ограничения придется переделывать процессор.
Нет.
Достаточно переделать соглашения о вызовах.
И вобще не дело процессора стеком заведовать.
Его работа чисилки молотить.
И не более того.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Tissot, Вы писали:
T>Конечно есть. В своем стеке ты волен реализовать его так, как тебе нужно, а в аппаратном тебе приходится мириться с существующей реализацией.
А зачем нужен аппаратный стек?
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
T>>Каким образом? Работа со стеком .Net-е в конечном счете сводится все к тем же ассемблерным push/pop. WH>А при чем тут вобще .NET?
Программы написанные на Nemerle работают по .Net-ом вообще-то.
T>>Чтобы убрать подобные ограничения придется переделывать процессор. WH>Нет. WH>Достаточно переделать соглашения о вызовах.
Не суть важно. В данной реализации компилятора/рантайма это ложится один в один на асемблерные push/pop
Здравствуйте, WolfHound, Вы писали:
T>>Конечно есть. В своем стеке ты волен реализовать его так, как тебе нужно, а в аппаратном тебе приходится мириться с существующей реализацией. WH>А зачем нужен аппаратный стек?
Думаю изначально он рассматривался как средство облегчить жизнь разаботчикам. Нужен ли он сейчас — не знаю.
Здравствуйте, Tissot, Вы писали:
T>Программы написанные на Nemerle работают по .Net-ом вообще-то.
И как это относится к избавлению от стека там где алгоритм без стека не работает?
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Tissot, Вы писали:
T>Думаю изначально он рассматривался как средство облегчить жизнь разаботчикам. Нужен ли он сейчас — не знаю.
Даже при наличии простейшего макроассемблера весьма сомнительная помощь.
А если учесть что x86'ые call/ret принуждают к далеко не самым эффективным соглащениям о вызовах...
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
T>>Программы написанные на Nemerle работают по .Net-ом вообще-то. WH>И как это относится к избавлению от стека там где алгоритм без стека не работает?
Так, возвращаемся к началу.
Nikov написал:
При CPS данные, которые бы хранились в стеке, переносятся в кучу. Стек расти не будет.
Ты на это ответил:
Стек это структура данных.
Так вот то что накапливается в куче и есть стек.
И ни куда ты от этого не денешься.
Никак.
Поинт моего сообщения был в том, хоть "стек в куче" и растет, "аппаратный стек" не растет. И это есть гуд.
Здравствуйте, WolfHound, Вы писали:
T>>Думаю изначально он рассматривался как средство облегчить жизнь разаботчикам. Нужен ли он сейчас — не знаю. WH>Даже при наличии простейшего макроассемблера весьма сомнительная помощь.
И в чем же по-твоему была мотивация тех, кто добавлял эти инструкции в процессор?
1. Это верно только при освобождении памяти. Т.е. сравнивается вытаскивание из стека и освобождение памяти GC. И наоборот, неверно для размещения новых данных в heap (для ускорения в статье предлагается перехватывать "page fault" и вызывать сборщик мусора).
2. Скорость GC "достигается" за счет увеличения количества памяти в несколько раз от необходимого для размещения данных. Т.е. сборщик мусора срабатывает очень редко.
3. Тестирование проводилось на конкретной машине "128-megabyte VAX-11/785" в 1986-1987 гг. На современных процессорах время исполнения инструкций по работе с памятью и стеком может значительно отличаться.
Поэтому, "сборка мусора может быть быстрее, чем работа со стеком", но очень-очень редко
Здравствуйте, Tissot, Вы писали:
T>Здравствуйте, gandjustas, Вы писали:
WH>>>>Почему? T>>>Потому что в данном случае имеется в виду тот стек, с которым работает процессор. G>>Какая-то принципиальная разница есть? T>Конечно есть. В своем стеке ты волен реализовать его так, как тебе нужно, а в аппаратном тебе приходится мириться с существующей реализацией.
Можно не использовать аппаратный стек при наличии хвостовой рекурсии и CPS.
T>>>Каким образом? Работа со стеком .Net-е в конечном счете сводится все к тем же ассемблерным push/pop. Чтобы убрать подобные ограничения придется переделывать процессор. G>>И кто мешает держать стек на куче? Значение регистра esp можно изменять.
T>Можно, но я не слышал, чтобы .Net делал что-то подобное.
Чтобы убрать ограничения стандартной реализации аппатного стека не нужно переделывать процессор.
Другое дело что в .NET и других платформах этого не делается.
Здравствуйте, gandjustas, Вы писали:
G>>>Какая-то принципиальная разница есть? T>>Конечно есть. В своем стеке ты волен реализовать его так, как тебе нужно, а в аппаратном тебе приходится мириться с существующей реализацией. G>Можно не использовать аппаратный стек при наличии хвостовой рекурсии и CPS.
Но тем не менее он используется.
T>>Можно, но я не слышал, чтобы .Net делал что-то подобное. G>Чтобы убрать ограничения стандартной реализации аппатного стека не нужно переделывать процессор. G>Другое дело что в .NET и других платформах этого не делается.
Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, Beam, Вы писали:
B>>Поэтому, "сборка мусора может быть быстрее, чем работа со стеком", но очень-очень редко
M>Стоит читать ?
Статью? Думаю, что нет.
M>ведь теоретически мы не выполняем никаких действий при размещении на стеке ?
Ну почему же. Выполняем действия и там, и там.
Другое дело, что стек, скорее всего, будет быстрее.
M>как стек может быть медленее ?
Да он и не может быть медленнее. Но вот только это не доказать в общем случае, т.к. зависит от многих факторов.
А пока не доказано, то, наверное, всё же может
Здравствуйте, VladD2, Вы писали:
N>>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style).
VD>Намного интереснее то, что CPS и хвостовая рекурсия — это немного разные вещи. CPS это всего лишь возможность вынести состояние в кучу. А хвостовая рекурсия просто переписывается в цикл. Согласись, что это разные вещи.
После CPS-преобразования любая рекурсивная функция содержит только хвостовую рекурсию, которая может быть преобразована в цикл. То, что в некоторых случаях можно добиться хвостовой рекурсии без CPS-преобразования — я согласен. И согласен, что это разные вещи.
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, Kalushin, Вы писали:
WH>>>Хвостовыми считаются вызовы результат кторых возвращается из функции.
K>>Все, понял K>>Спасибо
N>Интересный факт, что любую рекурсию можно переписать так, чтобы она была хвостовой (Continuation-passing style).
И этот факт используется во многих компиляторах. А в некоторых не используется. Например, попробуй посчитать на Scala рекурсивно факториал от 10000 — рекурсия не будет сведена к хвостовой и соответсвтенно не будет пребразована в цикл. А компилятор haskell вполне это делает.
... << RSDN@Home 1.2.0 alpha 4 rev. 1089>>
Социализм — это власть трудящихся и централизованная плановая экономика.
Здравствуйте, 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)))
LP>И этот факт используется во многих компиляторах. А в некоторых не используется. Например, попробуй посчитать на Scala рекурсивно факториал от 10000 — рекурсия не будет сведена к хвостовой и соответсвтенно не будет пребразована в цикл. А компилятор haskell вполне это делает.
Разработчики Скала никогда и не утверждали, что они на лету рекурсию сводят к хвостовой рекурсии. Они вроде как утверждали, что преобразуют хвостовую рекурсию в цикл.
LP>>И этот факт используется во многих компиляторах. А в некоторых не используется. Например, попробуй посчитать на Scala рекурсивно факториал от 10000 — рекурсия не будет сведена к хвостовой и соответсвтенно не будет пребразована в цикл. А компилятор haskell вполне это делает.
A>Разработчики Скала никогда и не утверждали, что они на лету рекурсию сводят к хвостовой рекурсии. Они вроде как утверждали, что преобразуют хвостовую рекурсию в цикл.
Ага, и то не всегда Где-то в рассылке даже была идея добавить аннотацию tailrec, чтобы компилятор ругался, если не может преобразовать эту рекурсию в цикл.
<< RSDN@Home 1.2.0 alpha 4 rev. 1128>>
Сейчас играет Мельница — Полнолуние
A>>Разработчики Скала никогда и не утверждали, что они на лету рекурсию сводят к хвостовой рекурсии. Они вроде как утверждали, что преобразуют хвостовую рекурсию в цикл. G>Ага, и то не всегда Где-то в рассылке даже была идея добавить аннотацию tailrec, чтобы компилятор ругался, если не может преобразовать эту рекурсию в цикл.
A>>>Разработчики Скала никогда и не утверждали, что они на лету рекурсию сводят к хвостовой рекурсии. Они вроде как утверждали, что преобразуют хвостовую рекурсию в цикл. G>>Ага, и то не всегда Где-то в рассылке даже была идея добавить аннотацию tailrec, чтобы компилятор ругался, если не может преобразовать эту рекурсию в цикл.
A>а что за рассылка? гугл групс?
scala@listes.epfl.ch
<< RSDN@Home 1.2.0 alpha 4 rev. 1128>>
Сейчас играет Мельница — Полнолуние
A>>>а что за рассылка? гугл групс? G>>scala@listes.epfl.ch
A>Чего-то не могу подписаться используя mail.ru, хотя если с корпоративного подписаться (.com), то прокатывает.
A>Они зону ру целиком ненавидят или только мэйл.ру?
Хз, у мну гмейл
<< RSDN@Home 1.2.0 alpha 4 rev. 1128>>
Сейчас играет Anna — Movchy
Где-то в рассылке даже была идея добавить аннотацию tailrec, чтобы компилятор ругался, если не может преобразовать эту рекурсию в цикл.
