Здравствуйте, 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>А зачем нужен аппаратный стек?
Думаю изначально он рассматривался как средство облегчить жизнь разаботчикам. Нужен ли он сейчас — не знаю.
