Стек викликів

Стек викликів (call stack) — це структура даних у вигляді стека, яка зберігає інформацію про активні підпрограми комп'ютерної програми.

Такий тип стека також відомий під назвами стек виконання, стек управління або рантайм стек, часто скорочується до просто "стек". Хоча підтримка функціонування стека викликів дуже важлива для будь-якої програми, деталі роботи зі стеком зазвичай приховані під час роботи з високорівневими мовами програмування.

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

У зв'язку з тим, що стек викликів влаштований як стек, підпрограма, що викликає заштовхує адресу повернення на верхівку стека, а підпрограма яку викликають, після завершення своєї роботи, виштовхує адресу повернення зі стека і повертає керування інструкції за цією адресою. Якщо підпрограма, яку викликали викликає іншу підпрограму або рекурсивно саму себе, тоді вона заштовхує наступну адресу повернення на верхівку стека, і т.д. Якщо розмір стека поглинає увесь виділений під стек простір, тоді виникає помилка переповнення стека (stack overflow), яка зазвичай призводить до краху програми. Додавання запису про підпрограму іноді називається намотування (winding); відповідно, видалення запису — розмотування (unwinding).

Стек викликів може мати додаткові призначення, залежно від мови програмуання і архітектури комп'ютера. Серед них можуть бути:

Локальне сховище даних – Підпрограма часто потребує пам'ять для збереження значень локальних змінних, змінних значення яких відомі тільки під час виконання підпрограми і не зберігаються по виході з неї. Часто буває зручно виділяти для таких змінних місце просто рухаючи верхівку стека достатньо, щоб забезпечити необхідний простір. Це дуже швидке рішення у порівнянні з розташуванням в купі. Зауважимо, що кожна окрема підпрограма має свій окремий простір у стеку для локальних змінних.
Передача параметрів – Підпрогами часто вимагають від коду, що їх викликає параметри, і розташування значень цих параметрів у стеку не є незвичним рішенням. Якщо параметрів всього декілька і їхній розмір малий, тоді для передачі їх в підпрограму можна використати регістри процесора, але якщо розмір парамерів не дозволяє зужиткувати цей спосіб передачі, буде необхідний простір в пам'яті. Стек добре працює для передачі таких параметрів, особливо через те, що з кожним викликом наступної підпрограми значення параметрів змінюються, щоразу для них виділяється окреме місце.
Стек обчислення – Операнди арифметичних або логічних операцій зазвичай розташовують в регістрах і тоді провадять над ними певні дій. Однак, в деяких ситуаціях операнди можуть накопичуватися до довільної глибини, тоді постає питання використання чогось відмінного від регістрів. Стек подібних операндів, скоріше схожий на RPN калькулятор, називається стеком обчислення, і може розташовуватися у стеку викликів.
Вказівник на поточний об'єкт - Деякі об’єктозорієнтовані мови програмування (наприклад, C++),при виклику функції зберігають вказівник this разом з аргументами функції у стеку. Вказівник this вказує на об'єкт пов'язаний з методом, що викликається.

та інші.

Стек викликів в Python

Стек викликів в Python ще називається "стек часу виконання" (run time stack) або навіть просто "стек". Стек включає в себе два:

фрейми виклику (call frames) — по одному для кожного виклику функції
сховище для локальних змінних

Кожен фрейм виклику містить:

ім'я функції, що була викликана,
точку повернення — місце в коді, з якого треба продовжити виконання після повернення з викликаної функції

Спочатку стек має лише один фрейм виклику з ім'ям __main__. При кожному виклику функції створюється новий відповідний фрейм виклику і кладеться на вершину стека. Отже на вершині стека завжди буде знаходитись фрейм, який відповідає функції що була викликанан останньою (іншими словами: функції, яка виконується в даний момент часу), або ж основній програмі якщо ім'я фрейма є __main__.

Коли відбувається повернення з функції, відповідний фрейм видаляється з вершини стека.

Пригадаємо: коли викликається функція створюються локальнлі змінні, які відповідають параметрам функції і ініціалізуються значеннями аргументів.

При кожному виклику функції на стек "кладуться" також і усі локальні змінні функції. Різні функції можуть містити локальні змінні з однаковими іменами. Конфлікта не виникає тому що локальні змінні для кожної функції знаходяться у різних вузлах стека, поряд з відповідним фреймом виклику.

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

Розглянемо приклад:

>>> def f1(param):
...     return f2(param)
...
>>> def f2(param):
...     return f3(param)
...
>>> def f3(param):
...     return 1 / param
...
>>>

Покроково відстежимо що відбувається при наступному виклику функції f1():

>>> f1(1)
1.0
>>>

На вершині стека знаходиться фрейм виклику __main__
Викликається функція f1 з аргументом 1 типу int
На вершину стека "закидається" фрейм з ім'ям f1
На вершину стека "закидається" параметр param функції f1 зі значенням 1 типу int
Виконується тіло функції f1
Викликається функція f2
На вершину стека "закидається" фрейм з ім'ям f2
На вершину стека "закидається" параметр param функції f2 зі значенням 1 типу int
Виконується тіло функції f2
Викликається функція f3
На вершину стека "закидається" фрейм з ім'ям f3
На вершину стека "закидається" параметр param функції f3 зі значенням 1 типу int
Виконується тіло функції f3
Виконується повернення з функції f3
Зі стека "знімається" параметр функції f3
Зі стека "знімається" фрейм з ім'ям f3
Функція f3 повертає значення 1.0 типу float, це значення "закидається" на стек
Зі стека "знімається" значення 1.0 типу float, продовжується виконання функції f2
Виконується повернення з функції f2
Зі стека "знімається" параметр функції f2
Зі стека "знімається" фрейм з ім'ям f2
Функція f2 повертає значення 1.0 типу float, це значення "закидається" на стек
Зі стека "знімається" значення 1.0 типу float, продовжується виконання функції f1
Виконується повернення з функції f1
Зі стека "знімається" параметр функції f1
Зі стека "знімається" фрейм з ім'ям f1
Функція f3 повертає значення 1.0 типу float, це значення "закидається" на стек
Зі стека "знімається" значення 1.0 типу float, інтерпретатор виводить це значення
знову на вершині стека знаходиться фрейм виклику __main__.

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

>>> f1(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in f1
  File "<stdin>", line 2, in f2
  File "<stdin>", line 2, in f3
ZeroDivisionError: division by zero
>>>

Повідомлення:

Traceback (most recent call last):

можна перекласти як:

шлях (ланцюжок) викликів функцій, останній виклик знаходиться у кінці:

і далі власне перераховуються функції у порядку їх викликів.