← Writing へ戻る
Data Structure

コールスタック（Call Stack）

概要

コールスタックとは関数の実行順序と実行状態を管理するためのスタック構造（LIFO）です。 一回の操作でスタックに積み上げるひとまとまりのデータをスタックフレームと言います。

  • 関数が呼ばれると「スタックフレーム」が積まれる（push）
  • 関数が終了するとフレームが取り除かれる（pop）
  • 最後に呼ばれた関数が最初に終了する（LIFO: Last In, First Out）

=> スタックが割り当てられている量よりも多くのスペースを使用した場合、"stack overflow" エラーが発生します。

目的

コールスタックを使う目的は、サブルーチン（関数）の処理を完了して制御を戻す（呼び出し側に戻る）ときに、どこに戻ればよいか（戻るべき命令のアドレス）を記憶しておくことです。

関数自身が再帰的に呼び出された場合でも、戻るべき場所（リターンアドレス）は呼び出されるたびに記憶しておく必要があります。コールスタックはこの情報を管理するための構造です。

動き

下のインタラクティブ図で、関数の呼び出しと終了にともなってスタックフレームがどのように積まれ・取り除かれるかを確認できます。

Call stack animation with Python codeLeft: Python source code. Right: call stack frames animating as functions are called and returned. Code blocks and stack frames are synchronized.Python codedef main(): num = 42 result = calculate() print(result)main() # entry pointdef calculate(): x = 10 val = add(3, 4) return val + x# returns to maindef add(a, b): result = a + b return result# returns to calculateExecution order① call main()② main → calls calculate()③ calculate → calls add(3, 4)④ add returns 7⑤ calculate returns 17⑥ main prints 17 and exitsCall stack (memory)(unused stack space)PUSH ↓add(3, 4)args: a=3, b=4local: result=7return addr → calculatecalculate()local: x=10waiting for add(3, 4)return addr → mainmain()local: num=42waiting for calculate()return addr → OSSPSPSPPOPhighlowLegendmain()calculate()add()corresponds to
  1. main() が呼ばれると main フレームが push される
  2. main から calculate() が呼ばれると calculate フレームが push される
  3. calculate から add(3, 4) が呼ばれると add フレームが push される
  4. add が 7 を返して終了すると add フレームが pop される
  5. calculate が 17 を返して終了すると calculate フレームが pop される
  6. main が 17 を表示して終了すると main フレームが pop され、スタックは空になる

参考