コールスタック
コールスタックを使う目的はいくつかあるが、主たる目的はサブルーチンの処理を完了して制御を戻す(呼び出し側に戻る)ときに、どこに戻ればよいかを記憶しておくことである。
コールスタックはスタックとして構成されているので、呼び出し側はリターンアドレスをスタックに push し、呼び出されたサブルーチンが完了したときにリターンアドレスをコールスタックから pop する(そしてそのアドレスに制御を戻す)。呼び出されたサブルーチンがさらに別のサブルーチンを呼び出す場合も、リターンアドレスをコールスタックに push し、プログラムに書かれている通りに情報をスタックに積んだり下ろしたりする。あるサブルーチンに関する情報をコールスタックに載せることをワインド (巻き上げ, winding)、逆にそれを削除することをアンワインド (巻き戻し, unwinding) と呼ぶ。また、サブルーチンの呼び出しごとにコールスタックに格納するひとまとまりの情報の集合をスタックフレーム (stack frame) または単にフレームと呼ぶ。
なお、コールスタックに割り当てられている領域を使い切ると「スタックオーバーフロー」と呼ばれる実行時エラーが発生する。
呼び出された関数から復帰するとスタックのトップにあったフレームがpopされ、戻り値が残される。
Pascalなどの言語は関数の入れ子を越えた広域のgoto文をサポートしており、呼び出し側関数に制御を移すことができる。このとき、スタックのアンワインドを行って、goto文の戻り先の関数に対応したスタックフレームまで戻す必要がある。このような制御の転送は一般にエラー処理にのみ使われる。
スタックは例外処理の際にもアンワインドされなければならない。例外をサポートするためには、スタックフレームにさらに例外ハンドラを示すエントリが必要となる。例外がスローされると、スタックはその例外を処理できる例外ハンドラが見つかるところまでアンワインドされる。Common Lispではスタックがアンワインドされたときに起きることを制御するunwind-protectという特殊なマクロがある。
継続を適用する場合、スタックは一度アンワインドされ、再度ワインドされて実行を継続する。継続を実装する方法はこれだけではなく、明示的に複数のスタックを用意して継続するアプリケーションが単にそのスタックを起動して渡すべき値をワインドする。
2006年、コールスタックを使ったこれまでとは全く異なる技法が発表された。それはコールスタックを使った test suite reduction と呼ばれる技法である。大まかに言えば、実行時のコールスタックが同じになるテストケースは等価だとみなしてテスト件数を減らしつつ、テストスイート全体の問題検出能力を維持するという考え方である。
多くのサブルーチンは局所変数(自動変数(英語版))の値を格納するメモリ領域を必要とする。局所変数とは実行中のサブルーチンでのみ使われる変数で、そのサブルーチンの処理が終われば値を必要としない。このためにスタックのトップを動かして空き領域を作り、局所変数に利用することができる。これは動的メモリ確保に比べると非常に高速に行える。サブルーチンが呼び出される度にスタック上の局所データの領域が確保される点に注意されたい。