Token t = ts.get();
switch (t.kind) {
case '(':
{ double d = expression(ts);
// ...
}
// ...
}
}
Теперь у этих функций нет скрытых глобальных переменных, и они превосходно подходят для иллюстрации: у них есть аргумент и локальные переменные, и они вызывают друг друга. Возможно, вы захотите освежить память и еще раз посмотреть, как выглядят эти функции в законченном виде, но все их основные свойства, относящиеся к механизму вызова функций, уже перечислены.
При вызове функции реализация языка программирования создает структуру данных, содержащую копии всех ее параметров и локальных переменных. Например, при первом вызове функции
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()
, стек возвращается в предыдущее состояние.
Когда функция
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);
// ...
}
