На этом шаге мы рассмотрим, что представляют собой стековые кадры.
Каждый вызов подпрограммы в первую очередь создает в стеке стековый кадр (stack frame), или фрейм, - блок данных, размещаемый на вершине программного стека. Помимо адреса возврата, он содержит, в частности, параметры и локальные переменные метода или ссылки на них, а также другую низкоуровневую информацию. Адрес возврата указывает на машинную команду, которой метод должен передать управление по завершении своих действий. По завершении метода его запись активации удаляется из программного стека, а освобождаемая память может использоваться для вызовов других методов. Таким образом, в любой момент программный стек содержит информацию только об "активных" подпрограммах, то есть вызванных, но еще не завершённых (стековые кадры называют также активными кадрами, или записями активации).
На рисунке 1 приведены состояния программного стека при выполнении кода из примера 10.1, а по существу - последовательность вызовов-возвратов методов на рисунке 1, 153 шага.
Рис.1. Выделение стековых кадров при выполнении кода из примера 10.1, где cos, | · | и <·, ·> обозначают методы cosine(), norm_Eudidean() и dot_product() соответственно
После инициализации списков a и b в строках 16 и 17 вызов cosine(u, v) создаёт в программном стеке первый стековый кадр (тёмный прямоугольник на рисунке), в котором сохраняются ссылки на два входных списка (шаг 1). После этого управление передаётся вызываемому методу, первая операция которого (строка 13) - вычисление скалярного произведения его входных параметров dot_product(u, v). Следовательно, вызов этого нового метода добавляет в стек новый стековый кадр (шаг 2) с выделением памяти для хранения двух ссылок на входные списки и двух локальных переменных s и i. По завершении этого метода весь его стековый кадр удаляется из программного стека (шаг 3). На следующем шаге в той же строке 13 вычисляется norm_Eudidean(u).
Вызов этой функции помещает в программный стек свой стековый кадр (шаг 4). Метод вычисляет евклидову норму вектора - своего входного списка (в данном случае a), вызывая dot_product(v, v), который, в свою очередь, создаёт новый стековый кадр (шаг 5). На рисунке 2 показаны сохранённые в программном стеке параметры и локальные переменные для вычисления этого скалярного произведения, а также данные двух предшествующих вызовов из приведённого примера кода.
Рис.2. Программный стек и данные на шаге 5 из рисунка 1
На двух следующих шагах 6 и 7 из стека последовательно удаляются стековые кадры полностью завершённых функций dot_product() и norm_Eudidean(). Затем алгоритм вычисляет евклидову норму второго вектора - входного списка b, поэтому шаги 8-11 аналогичны шагам 4-7. В итоге функция cosine() завершается, возвращая свой результат и освобождая стек программы.
Программный стек - это структура данных, наилучшим образом приспособленная для реализации последовательности вложенных вызовов подпрограмм, включая рекурсию. Рассмотрим рекурсивные вызовы функции sum_first_naturals() на рисунке 2, 153 шага. Глядя на него, может показаться, что при каждом вызове функции в памяти создаётся ещё одна копия кода, но это не так: в памяти находится только один экземпляр кода, а весь механизм каждого конкретного вызова и отслеживания цепочек вызовов сосредоточен исключительно в программном стеке. В данном случае каждый новый стековый кадр очередного вызова хранит значение входного параметра n для этого вызова. Таким образом, при выполнении кода конкретное значение n будет именно тем, что хранится в кадре, расположенном на вершине программного стека. На рисунке 3 приведено состояние программного стека при выполнении вызова sum_first_naturals(4), где каждый кадр, очевидно, связан с одним и тем же методом.
Рис.3. Выделение стековых кадров для sum_first_naturals(4)
Выделение стековых кадров отражает цепочку вызовов-возвратов, как в дереве рекурсии (см. рисунок 1, 155 шага). Затемнённый прямоугольник представляет собой цепочку стековых кадров тех методов, которые могли быть вызваны до вызова sum_first_naturals(4).
На следующем шаге мы рассмотрим трассировку стека.
