Почему стек?

В прошлый раз мы говорили о том, почему компиляторы всех языков платформы .NET компилируют исходный код в «промежуточный язык» или в IL, который затем преобразуется jitter-ом в машинные инструкции: поскольку это существенно сокращает расходы на разработку многоязыковой платформы, работающей на разном оборудовании. Сегодня я хочу рассказать о том, почему язык IL является именно таким, каким он есть; в частности, почему он является стековым?

Для начала нужно понять, что же такое «машина со стековой организацией» (stack machine)? Давайте подумаем о том, как бы вы разрабатывали свой собственный язык машинного уровня, способный представлять операцию сложения двух целых чисел для получения третьего числа, содержащего результат. Это можно было бы сделать таким образом:

прибавить [адрес первого аргумента], [адрес второго аргумента], [адрес суммы]

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

Можно пойти другим путем. Можно сказать, что у нас есть специальная область памяти, которая называется «аккумулятором», которая знает, как сложить некоторое значение с текущим значением:

Очистить_аккумулятор
увеличить_аккумулятор [адрес первого слагаемого]
увеличить_аккумулятор [адрес второго слагаемого]
сохранить_значение_аккумулятора [адрес суммы]

Или у нас может быть специальная область памяти, которая называется «стеком», способная расти и уменьшаться; и к вершине которой вы можете обращаться:

поместить_значение_в_стек [адрес первого аргумента]
поместить_значение_в_стек [адрес второго аргумента]
сложить
получить_значение_из_стека_и_поместить_в [адрес суммы]

Инструкция «сложить» берет два верхних значения стека, складывает их каким-то образом, и помещает полученный результат обратно в стек; в результате размер стека уменьшается на единицу.

Большинство инструкций в виртуальных машинах построены последним способом, именно поэтому они называются «машинами со стековой организацией».

Как и большинство виртуальных машин, язык IL является стековым. Хотя большая часть аппаратных наборов инструкций ближе ко второму варианту: регистры являются своего рода аккумуляторами. Тогда почему такое большое количество виртуальных сред являются стековыми?

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

В качестве примера, давайте представим, что мы выбрали первый подход и нам нужно скомпилировать выражение вида: x = A() + B() + C(); Что мы должны получить в этом случае? Что-то в этом роде:

создаем_временное_хранилище // для результатов метода A()
вызываем A(), [адрес временного хранилища]
создаем_временное_хранилище // для результатов метода B()
вызываем B(), [адрес временного хранилища]
создаем_временное_хранилище // для результатов первого сложения [адрес первого временного хранилища], [адрес второго временного хранилища], [адрес третьего временного хранилища]
...

Вы видите, что получается? Такой язык очень «многословен» и, к тому же, нам приходится следить за памятью, значения в которой нам никогда больше не понадобятся. Реализация стека позволяет решить проблему временных хранилищ; код для стековой машины будет выглядеть следующим образом:

поместить в стек [адрес переменной x]
вызвать A() // неявно создается временное хранилище путем помещения результата вызова в стек
вызвать B()
сложить
вызвать C()
сложить
сохранить // сохраняет результат из верхушки стека по адресу из следующего элемента стека (адресу переменной х).

Кода значительно меньше и его гораздо проще понять. Стековая машина является очень простым способом представления сложных вычислений; возможность генерации кода для такой простой машины существенно уменьшает стоимость разработки компилятора. И это не только упрощает разработку компиляторов и jitter-ов, это также упрощает разработку и других средств анализа кода. Верификатор IL-кода, например, может легко найти фрагменты кода, нарушающие выравнивание стека или места передачи неверных аргументов в методы.

Оригинал статьи

Comments

• Anonymous
  December 20, 2011
  Инструкция «сложить» берет два верхних значения стека, складывает их каким-то образом, и помещает полученный результат обратно в стек; в результате размер стека увеличивается на единицу. Наверное, всё-таки уменьшается. Иначе вычисление A() + B() + C() не будет работать, как указано в примере ниже.

• Anonymous
  December 20, 2011
  <quote>Инструкция «сложить» берет два верхних значения стека, складывает их каким-то образом, и помещает полученный результат обратно в стек; в результате размер стека увеличивается на единицу.</quote> Наверное, всё-таки уменьшается. Иначе вычисление A() + B() + C() не будет работать, как указано в примере ниже.

• Anonymous
  December 26, 2011
  Совершенно верно. Спасибо, Евгений!