Программирование

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

  При вызове функции реализация языка программирования создает структуру данных, содержащую копии всех ее параметров и локальных переменных. Например, при первом вызове функции 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 v; // v — глобальная переменная

void f()

{

  string s; // s — локальная переменная в функции f

  while (cin>>s && s!="quit") {

    string stripped; // stripped — локальная переменная в цикле

    string not_letters;

    for (int i=0; i

                                   // видимости инструкции

      if (isalpha(s[i]))

        stripped += s[i];

      else

        not_letters += s[i];

      v.push_back(stripped);

      // ...

  }

  // ...

}