ts является глобальной переменной. Это несколько снижает прозрачность работы программы. Мы можем улучшить эти функции, позволив им принять аргумент типа Token_stream&. Благодаря этому нам не придется переделывать ни один вызов функции.
Во-первых, функция expression() совершенно очевидна; она имеет один аргумент (ts) и две локальные переменные (left и t).
double expression(Token_stream& ts)
{
double left = term(ts);
Token t = ts.get();
// ...
}
Во-вторых, функция term() очень похожа на функцию expression(), за исключением того, что имеет дополнительную локальную переменную (d), которая используется для хранения результата деления (раздел case '/').
double term(Token_stream& ts)
{
double left = primary(ts);
Token t = ts.get();
// ...
case '/':
{
double d = primary(ts);
// ...
}
// ...
}
В-третьих, функция primary() очень похожа на функцию term(), за исключением того, что у нее нет локальной переменной left.
double primary(Token_stream& ts)
{
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);
// ...
}
// ...
}
Глобальные переменные, такие как program_name и v, инициализируются до выполнения первой инструкции функции main(). Они существуют, пока программа не закончит работу, а потом уничтожаются. Они создаются в порядке следования своих определений (т.е. переменная program_name создается до переменной v), а уничтожаются — в обратном порядке (т.е. переменная v уничтожается