[Регистровые и стековые машины][Book request] Теория.

Всё таки предложу теорию автоматов вместе с машиной Тьюринга http://www.williamspublishing.com/Books/5-8459-0261-4.html. Во-первых реальное железо ни разу не полно по Тьюрингу :) Потом там особо ничего не формализуют - грубая инженерия. Ну и в-третьих - в SICP вполне хорошо рассказано в последней главе про регистровые машины с практической точки зрения.

Ну и потом, если формализировать регистровые машины, то чем как ни машиной Тьюринга (а там как раз теория вполне развита).

Подробно - 8.6.2 и 8.6.3 в той книжке.

Хреново.

Во-первых реальное железо ни разу не полно по Тьюрингу :)

Wut?

Можно попробовать посмотреть в сторону замечательной книжки Н. Катленда «Вычислимость. Введение в теорию рекурсивных функций». Если мне не изменяет память, в ней изложение ведется в контексте МНР.

Wut?

Памяти-то конечное количество, а у полной по Тьюрингу машины на ёмкость не накладывается ограничений, например у лямбда-исчисления это неограниченная вложенность термов, у самой МТ - бесконечная лента. У обычной машины даже стек конечного размера (если сравнивать ещё с МП-автоматами).

Хреново.

А что в итоге нужно? Если теорию, то можно посмотреть formal definition и references в википедии, http://en.wikipedia.org/wiki/Register_machine, там эквивалентность МТ - правда это больше похоже на область мат. логики, чем на алгоритмику :). Да и всё равно потребует знание теории автоматов.

А для практики (типа разработки трансляторов) достаточно книжек которые уже читаете и здравого смысла :). Правда, я вот раздумывал о представлении катаморфических алгоритмов от LC в терминах регистровых машин, но так ни к чему не пришёл, может тут уже нужна какая-то хорошая теория. Например, преобразования многопроходных списочных алгоритмов (любая функция прохода выражается через функцию выражающую катаморфизм) в однопроходный алгоритм регистрово-стековой машины - это сейчас открытая тема.

Мне интересно, если ли жизнь вне процедур.

Процедура описывается просто: метка, вычисление, callback. Интересно посмотреть на вычисления которые организованы не с помощью процедур, а чем-нибудь иным.

Как я понял, нужно смотреть реализацию Пролога и, возможно, Haskell.

Я надеялся, что уже есть теория, которая описывает всевозможные способы организовать вычисления на регистровой машине.

Например, те же continuations. Откуда они взялись? На них случайно наткнулись? Можно ли было их вывести постепенно развивая теорию?

Я надеялся, что уже есть теория, которая описывает всевозможные способы организовать вычисления на регистровой машине.

Есть теория вычислимости, регистровые машины ничем не лучше машины Тьюринга, и также ничем не лучше лямбда исчисления или комбинаторной логики. Это эквивалентные в плане вычислимости вещи ни одна из которых не является первичной. Что-то удобнее формально выражать в одних терминах, что-то в других, также можно моделировать одно на другом (т.е. фактически строить гомоморфизм представления из одной модели в другую). Вот например в компиляторах которые используют регистрово-стековую модель (например, gcc) есть представление target языка в SSA виде и оптимизации на этом представлении, а в компиляторах которые используют представление в виде лямбда-исчисления (ghc) ту же роль играет CPS форма. При этом SSA и CPS эквивалентны, но они используются там где их удобно использовать. Особое положение регистровых моделей только в том что это ближе к железу - с точки зрения теории о процедурах можно сразу забыть :) Всё это разные формальные системы (как разные интерпретации квантовой механики, например).

Как я понял, нужно смотреть реализацию Пролога и, возможно, Haskell.

Более менее активная жизнь вне процедур это лямбда исчисление и комбинаторная логика :) Так что нужно читать «Введение в ФП» (первод гуглится по funprog). А МТ гораздо ближе к процедурам.

Например, те же continuations. Откуда они взялись? На них случайно наткнулись? Можно ли было их вывести постепенно развивая теорию?

Ну а в си есть setjump/longjump с подобной же ролью. Т.е. continuations это не очень значительная вещь в рамках CPS, как переход в произвольное место с возвращением в МТ.

Процедура описывается просто: метка, вычисление, callback. Интересно посмотреть на вычисления которые организованы не с помощью процедур, а чем-нибудь иным.

Ну да, http://code.google.com/p/funprog-ru/ :)

Но там нет вообще ничего про регистры и стек.

.