При вызове функции реализация языка программирования создает структуру данных, содержащую копии всех ее параметров и локальных переменных. Например, при первом вызове функции
expression
компилятор создает структуру, напоминающую показанную на рисунке.
Детали зависят от реализации, но в принципе к ним относится информация о том, что функция должна вернуть управление и некое значение в точку вызова. Такую структуру данных называют записью
активации функции (function activation record), или просто активационной записью. Каждая функция имеет свою собственную запись активации. Обратите внимание на то, что с точки зрения реализации параметр представляет собой всего лишь локальную переменную.
Теперь функция
expression
вызывает
term
, поэтому компилятор создает активационную запись для вызова функции
term
.
Обратите внимание на то, что функция
term
имеет дополнительную переменную
d
, которую необходимо хранить в памяти, поэтому при вызове мы резервируем для нее место, даже если в коде она нигде не используется. Все в порядке. Для корректных функций (а именно такие функции мы явно или неявно используем в нашей книге) затраты на создание активизационных записей не зависят от их размера. Локальная переменная
d
будет инициализирована только в том случае, если будет выполнен раздел
case '/'
.
Теперь функция
term
вызывает функцию
primary
, и мы получаем следующую картину.
Все это становится довольно скучным, но теперь функция
primary
вызывает функцию
expression
.
Этот вызов функции
expression
также имеет свою собственную активационную запись, отличающуюся от активационной записи первого вызова функции
expression
. Хорошо это или плохо, но мы теперь попадаем в очень запутанную ситуацию, поскольку переменные
left
и
t
при двух разных вызовах будут разными. Функция, которая прямо или (как в данном случае) косвенно вызывает себя, называется рекурсивной (recursive). Как видим, рекурсивные функции являются естественным следствием метода реализации, который мы используем для вызова функции и возврата управления (и наоборот).
Итак, каждый раз, когда мы вызываем функцию стек активационных записей (stack of activation records), который часто называют просто стеком (stack), увеличивается на одну запись. И наоборот, когда функция возвращает управление, ее запись активации больше не используется. Например, когда при последнем вызове функции
expression
управление возвращается функции
primary
, стек возвращается в предыдущее состояние. < image l:href="#"/>
Когда функция
primary
возвращает управление функции
term
, стек возвращается в состояние, показанное ниже.
И так далее. Этот стек, который часто называют стеком вызовов (call stack), — структура данных, которая увеличивается и уменьшается с одного конца в соответствии с правилом: последним вошел — первым вышел.
Запомните, что детали реализации стека зависят от реализации языка С++, но в принципе соответствуют схеме, описанной выше. Надо ли вам знать, как реализованы вызовы функции? Разумеется,
нет; мы и до этого прекрасно обходились, но многие программисты любят использовать термины “активационная запись” и “стек вызовов”, поэтому лучше понимать, о чем они говорят.
8.6. Порядок вычислений
Выполнение программы происходит инструкция за инструкцией в соответствии с правилами языка. Когда поток выполнения достигает определения переменной, происходит ее создание, т.е. в памяти выделяется память для объекта, и этот объект инициализируется. Когда переменная выходит из области видимости, она уничтожается, т.е. объект, на который она ссылалась, удаляется из памяти, и компилятор может использовать ранее занимаемый им участок памяти для других целей. Рассмотрим пример.
string program_name = "silly";
vector<string> v; // v — глобальная переменная
void f
{
string s; // s — локальная переменная в функции f
while (cin>>s && s!="quit") {
string stripped; // stripped — локальная переменная в цикле
string not_letters;
for (int i=0; i<s.size; ++i) // i находится в области
// видимости инструкции
if (isalpha(s[i]))
stripped += s[i];
else
not_letters += s[i];
v.push_back(stripped);
// ...
}
// ...
}
Глобальные переменные, такие как
program_name
и
v
, инициализируются до выполнения первой инструкции функции
main
. Они существуют, пока программа не закончит работу, а потом уничтожаются. Они создаются в порядке следования своих определений (т.е. переменная program_name создается до переменной
v
), а уничтожаются — в обратном порядке (т.е. переменная
v
уничтожается до переменной
program_name
).
Когда какая-нибудь функция вызывает функцию
f
, сначала создается переменная
s;
иначе говоря, переменная
s
инициализируется пустой строкой. Она будет существовать, пока функция
f
не вернет управление. Каждый раз, когда мы входим в тело цикла
while
, создаются переменные
stripped
и
not_letters
. Поскольку переменная
stripped
определена до переменной
not_letters
, сначала создается переменная
stripped
. Они существуют до выхода из тела цикла. В этот момент они уничтожаются в обратном порядке (иначе говоря, переменная
not_letters
уничтожается до переменной
stripped
) и до того, как произойдет проверка условия выхода из цикла. Итак, если, до того, как мы обнаружим строку
quit
, мы выполним цикл десять раз, переменные
stripped
и
not_letters
будут созданы и уничтожены десять раз.
Каждый раз, когда мы входим в цикл
for
, создается переменная
i
. Каждый раз, когда мы выходим из цикла
for
, переменная
i
уничтожается до того, как мы достигнем инструкции
v.push_back(stripped);
.
Обратите внимание на то, что компиляторы (и редакторы связей) — довольно разумны и способны оптимизировать код. В частности, компиляторы не выделяют и не освобождают память чаще, чем это действительно требуется.