Приклад 1. Розглянемо імітацію виконання програми з викликами підпрограм. Як і в підрозділі 7.1, будемо позначати локальну змінну, наприклад, L підпрограми F, як F.L, відрізняючи її від однойменної змінної програми. Вказівку точки повернення позначимо буквами ТП. Процес виконання програми

program nested ( input, output );

var a, b : integer;

function f ( x : integer ) : integer;

begin

x := x + 1; f := x

end;

function g (var x : integer ) : integer;

begin x := x div 2; g := x end;

begin a := 12; b := f ( g ( a ) ) end.

відобразимо такою таблицею:

Що виконується | Стан пам'яті 

a b

a := 12 | 12 ?

починається b := f(g(12)) | 12 ?

виклик f(g(12)) | 12 ? | f. x f. f ТП  

12 ? | ? ? b:=

починається f. x := g(12) | 12 ? | ? ? b:=

виклик g(12) | g. x ? | ? ? b:= | g. g ТП

g. x := 12 | 12 ? | ? ? b:= | ? f. x:=

g. x := g. X div 2 | 6 ? | ? ? b:= | ? f. x:=

g. g := g. X | 6 ? | ? ? b:= | 6 f. x:=

повернення з g | 6 ? | ? ? b:= | 6 f. x:=

закінчення f. x := g(12) | 6 ? | 6 ? b:=

f. x := f. x + 1 | 6 ? | 7 ? b:=

f. f := f. X | 6 ? | 7 7 b:=

повернення з f | 6 ? | 7 7 b:=

закінчення b := f(g(12)) | 6 7

Як видно з таблиці, перед виконанням виклику f(g(a)) у локальній пам'яті функції f запам'ятовується точка повернення – присвоювання b:=f(g(a)). Виконання виклику f(g(a)) починається обчисленням значення аргументу, відповідного її параметру x – виразу g(a). При цьому запам'ятовується точка повернення – присвоювання f.x:=g(a) – і починається виконання виклику функції g з аргументом a. Цей аргумент підставляється за посиланням, і зміна g.x є зміною a. З виклику функції g повертається значення 6 і присвоюється параметру f.x. Пам'ять функції g звільняється. Тільки тепер починається виконання операторів функції f. У результаті в програму повертається значення 7 і присвоюється змінній b. Пам'ять функції f звільняється.

Задачі

1.* Чи є правильною програма з прикладу 8.1, якщо замість оператора b:=f(g(a)) у її тілі записано

а) b:=g(f(a)); б) b:=f(a+33); a:=g(b); в) b:=f(g(a)+1); b:=f(f(a)+1).

Імітувати виконання нової програми, якщо вона правильна.

5. Автоматична пам'ять та програмний стек

Нагадаємо, що виконання програми починається після її завантаження в пам'ять комп'ютера. При цьому відбувається виділення пам'яті під її змінні. Ці змінні доступні з програми протягом усього часу її виконання, і тому називаються статичними. Область пам'яті, що виділяється під програму та її змінні, також називається статичною. Локальним іменам і параметрам-значенням підпрограм, як правило, зіставляють змінні з іншої області пам'яті – автоматичної. Ця назва пояснюється тим, що при виконанні викликів підпрограм ця пам'ять виділяється та звільняється "автоматично", без явних вказівок у програмі.

Як ми вже говорили в підрозділі 7.1, локальні імена, означені в підпрограмах, можуть збігатися з іменами в програмі та інших підпрограмах, оскільки вони позначають цілком різні об'єкти в різних областях пам'яті. Тому на локальні імена в підпрограмах немає ніяких обмежень. Зрозуміло, те саме ім'я в межах тіла підпрограми не повинно позначати різні об'єкти, наприклад, локальну змінну та іншу підпрограму. Не можна також означати ім'я самої підпрограми в її ж блоці.

Звернімо увагу на таблицю, що відбиває імітацію програми з прикладу 8.1. Спочатку виділяється локальна пам'ять функції f, потім – функції g, але звільнення відбувається в зворотнім порядку.

Виділення та звільнення ділянок пам'яті при виконанні викликів підпрограм відбувається за принципом "останнім зайнятий – першим звільнений". Подібно тому, як заштовхують патрони в магазин автомата й вистрілюють. Останній із них вистрілюється першим, а перший, що на самому дні магазина, – останнім. Можна вистрілити один патрон із магазина і додати згори новий. Цьому відповідає закінчення виклику підпрограми, записаного в тілі деякої підпрограми, і початок виконання наступного виклику з цього ж тіла.

Якщо складати аркуші паперу в стопку і брати їх тільки згори, то лист, що потрапив у стопку останнім, забирається першим. По-англійському така стопка називається stack (стек), а кладуться і забираються аркуші за принципом "Last In – First Out" (LIFO), тобто "першим у – останнім із". Тому автоматична пам'ять програми називається програмним стеком. Таблиця в прикладі 8.1 показує, як зростає й зменшується програмний стек при виконанні викликів підпрограм.

6. Зберігання локальних змінних між викликами підпрограми

У деяких задачах необхідно використовувати змінні, які означені й доступні в підпрограмі, але зберігають своє значення від її попереднього виклику до наступного.

Ці змінні не можна розміщати в автоматичній пам'яті, оскільки вона недоступна після виконання виклику підпрограми. Ці змінні не можна означати в програмі, оскільки тоді вони доступні не тільки в потрібній підпрограмі. Де і як їх означати?

Виходом є означення цих змінних у підпрограмі як статичних. Саме такі змінні розміщаються в статичній пам'яті програми разом із змінними програми, але доступні тільки під час виконання виклику тієї підпрограми, у якій означені. Вони називаються локальними статичними змінними.