Регистровые и стековые машины

В каком смысле, ортогональны ? В каком-то ортогональны, в каком-то -- противоположны.

Объясните тогда, что есть одно и что — другое.

Непонятен критерий ортогональности. Например, если взять за основу такой критерий как тьюринг-полнота системы команд, то и стековые и регистровые машины эквивалентны (т.е. в твоих терминах ортогональны, если я тебя правильно понял).

С позиции же разработчика компилятора, например, эти машины неортогональны. Потому что методы трансляции в стековую машину и в регистровую несколько отличаются.

Короче, либо я что-то не догоняю, либо надо определить понятие "ортогональности"

Может ли стековая машина быть одновременно и регистровой?

Я не очень силён в понятиях, поэтому и прошу объяснить, что такое стековая машина и что такое регистровая.

>Непонятен критерий ортогональности.

По сути человек спрашивает, возможна ли стековая регистровая машина.

В принципе - да. Можно изобразить машину с регистрами стеков :)

...

Кстати, классика PDP и 68K не относятся ли к таким?

Угу. Но я чувствую, что не очень хорошо понимаю понятия. У VAX, например, есть инструкции по работе со стеком, но есть и регистры. Разве это не регистровая машина и не стековая?

Почитай http://en.wikipedia.org/wiki/Register_machine и http://en.wikipedia.org/wiki/Stack_machine, потом задавай вопросы.

Теоретически можно тупо объединисть системы команд регистровой и стековой машины. В лоб. Будет и регистровая и стековая машины в одном флаконе. Только какой практический смысл ?

Не спец, но если посмотреть на итаниум -- там куча регистров, но они в stack-like fashion вроде могут использоваться. Там всякое аппаратное переименование регистров вроде.

> Может ли стековая машина быть одновременно и регистровой?

может. Например, регистровые окна в SPARC: http://en.wikipedia.org/wiki/SPARC >> http://en.wikipedia.org/wiki/Register_file

> то такое стековая машина и что такое регистровая.

Вот смотри. В конечном итоге любая программа исполняется на процессоре, на тех физических ресурсах, которые у него есть. У процессора нет "переменных", нет "типов переменных" (исключение: тегированная архитектура, i432), нет высокоуровневых циклов, есть простой IF с флагами и JMP. Язык Си -- это самый простой "ассемблер высокого уровня" -- уже есть структурные операторы, абстрактные типы данных, указатели, зачаточные модули и т.п.
Правда, выясняется что есть проблемы: указатели ведут к небезопасному коду, потому что неявно нужно управлять временем жизни выделенных в хипе переменных, а средств (узнать, как указатель используется) нет -- нужны ссылки или символы вместо указателей; модульность хотелось бы получше (чтобы подгружалась таблица символов); контролировать исполнение программы в какой-то среде, и т.п.
Выясняется, что можно вместо реального, физического ЦПУ с ассемблером сделать виртуальную машину, виртуальный ЦПУ со своим ассемблером -- байткодом. В котором все опасные операции убраны, и который лучше переносится. Можно пойти по пути виртуального процессора (Elate/Taos VP, Amiga DE, HLASM, AS/400, и т.п.) , а можно сделать свою "платформу" для исполнения этого байткода, как в Ява.
Значит, нужна модель исполнения байткода. Первое, что приходит в голову -- это форт, второе, лисп, третье -- Java/.NET/Oberon, четвёртое -- всё остальное (lua, llvm, etc):)
Стековый байткод работает с данными на верхушке стека. Значит, байткод выходит проще, компиляторы в этот байткод писать проще. Но неявно получается лишний уровень косвенности, вместо работы с imm значениями работаем со значениями по ссылке (в верхушке стека). Оно, возможно, всё равно попадает в кеш, и кешируется хорошо, за исключением случаев, когда происходит очистка кеша (JMP/CALL).
Регистровый байткод в этом смысле "ближе к железу". Виртуальные регистры, опкоды похожи на реальные регистры и ассемблер этого ЦПУ. Но, компилятор должен быть хитрее -- раскладывать переменные по регистрам (задача раскраски графа). Это довольно хитрая задача, поэтому регистровый байткод встречается реже. Про устройство виртуальных машин с регистровым байткодом можно прочитать про Оберон (slim binaries), LUA (5.0+ -- регистровый байткод), LLVM.

>Теоретически можно <..>. Только какой практический смысл ?

Практический смысл: подумай, как будет выглядеть компилятор Явы в маш.код на Спарках с регистровым окном. Гораздо красивее, чем на x86, наверно и производительнее. На ARM'ах, наверное, тоже ничего.
А то, что на x86 по логике регистровый байткод быстрее должен работать, ибо к железу ближе -- это так, мелочи.

> В принципе - да. Можно изобразить машину с регистрами стеков :)

есть что-то фортоподобное, с двумя или больше стеками. n-stack bytecode. Где бы про это подробнее почитать?

> Кстати, классика PDP и 68K не относятся ли к таким?

ортогональный набор понятий -- значит, каждое отдельное понятие не зависит от других в наборе. Например, у PDP и 68K машинный код с "ортогональным набором команд". В том смысле, что нет "регистров по умолчанию" вроде команды DJNZ B/LOOP (ECX), а в каждом опкоде может быть любой регистр.
Что имел в виду топикстартер про "ортогональность" -- это надо у него спросить. В виртуально-вакуумно-сферичной машине, наверное, регистры -- это верхушки стеков, а стеки -- это цепочка по указателю в регистре. Правда, в реальности регистры быстрее чем стек. И вся "ортогональность" рушится. Это как матрицы перемножать, А на Б или А на Б транспонированную. Первая не помещается в кеш, и умножение работает медленнее.

//c:: eyerded намекает, что пора завязывать

> http://en.wikipedia.org/wiki/Register_machine

пошел по ссылке в конце, прочитал про ручного бобра вильфреда:
http://en.wikipedia.org/wiki/Busy_beaver

А белка -- стековая? Куда она орешки кладёт, это FIFO?

Большое спасибо.

//И пусть ещё кто-нибудь усомнится в том, что анонимус нужен.

где-то была работа про Slim binaries Михаэля Франца (байткод в Обероне, то ли регистровый, то ли своя деревоподобная структура (ещё была другая отдельная среда Flora/C+ "деревоподобная")). Там было подробное сравнение стековый vs. регистровый байткод, плюсы и минусы (стековый короче, проще писать компилятор; регистровый как бы эффективнее, там были цифры, на сколько, какая-то количественная оценка). Сейчас она возможно устарела, надо бы сравнить .NET+LUA5+LLVM, но как ориентир "за и против".
Ещё был регистровый байткод в Dis (виртуальная машина в Inferno / Plan9).

> Сейчас она возможно устарела, надо бы сравнить .NET+LUA5+LLVM, но как ориентир "за и против".

Как сравнить JVM, LLVM и .NET по скорости исполнения ? Ведь это лишь языки промежуточного представления. Все они в конечном итоге транслируются в нативный код. Если для жабакода и LLVM еще можно представить некую абстрактную вычислительную машину, то для нетовского IL такую машину придумать очень сложно. Там какбы система команд более высокоуровневая.

> Ещё был регистровый байткод в Dis (виртуальная машина в Inferno / Plan9).

Про Parrot забыли :)

> Как сравнить JVM, LLVM и .NET по скорости исполнения?

вот оттранслированный в нативный код и сравнить, на одинаковых задачах (mono --aot ... = всё скомпилировать в нативный бинарник). И сравнить для справки "интерпретируемый" байткод, но тут может вмешаться JIT и вообще неоднозначно. Ещё можно попытаться сравнить JVM под .NET через IKVM и родное и через LLVM (llvm-gcc + gcj), но тут уже две переменных, а ведь первая заповедь радиотехники "не крутить две ручки одновременно" :)

> Про Parrot забыли :)

тысячи их, да :)