コールスタック
コールスタック (Call Stack)は、プログラムで実行中のサブルーチンに関する情報を格納するスタックである。実行中のサブルーチンとは、呼び出されたが処理を完了していないサブルーチンを意味する。実行スタック (Execution Stack)、制御スタック (Control Stack)、関数スタック (Function Stack)などとも呼ばれる。また、単に「スタック」と言ったときにコールスタックを指していることが多い。コールスタックを正しく保つことは多くのソフトウェアが正常動作するのに重要であるが、その詳細は高水準言語からは透過的である。
概要
コールスタックを使う目的はいくつかあるが、主たる目的は実行中サブルーチンの処理を完了して制御を戻す（呼び出し側に戻る）ときに、どこに戻ればよいかを覚えておくことである。例えば、次の擬似コードを考える。
subroutine DrawSquare(Point p1, Point p2, Point p3, Point p4)
{
    ... 略 ...
    
    DrawLine(p1, p2);
    DrawLine(p2, p3);
    DrawLine(p3, p4);
    DrawLine(p4, p1);
    
    ... 略 ...
}
サブルーチンDrawSquare内の4ヶ所からサブルーチンDrawLineを呼び出すとしたとき、DrawLineは4ヶ所のうちのどこに戻ればよいかを知る必要がある。一般にDrawSquareのコード内でDrawLineを呼び出しているそれぞれの箇所で、呼び出し処理の次の命令のアドレス（これをリターンアドレスと呼ぶ）をコールスタックに格納することでこれを実現する。
コールスタックはスタックとして構成されているので、呼び出し側はリターンアドレスをスタックに push し、呼び出されたサブルーチンが完了したときにリターンアドレスをコールスタックから pop する（そしてそのアドレスに制御を戻す）。呼び出されたサブルーチンがさらに別のサブルーチンを呼び出す場合も、リターンアドレスをコールスタックに push し、プログラムに書かれている通りに情報をスタックに積んだり下ろしたりする。コールスタックに割り当てられている領域を使い切ると「スタックオーバフロー」と呼ばれるエラーが発生する。あるサブルーチンに関する情報をコールスタックに載せることをワインド (winding)、逆にそれを削除することをアンワインド (unwinding) と呼ぶ。また、サブルーチン毎にコールスタックに格納する情報をスタックフレーム (Stack Frame) と呼ぶ。
1つの実行中のプログラム（より正確に言えばスレッド）には、1つのコールスタックが対応して存在する。シグナル処理や協調的マルチタスク処理で追加のスタックを使う場合もあるが、通常使用中のコールスタックは常に1つなので、これを単に「（そのタスクの）スタック」と呼ぶことがある。
高級言語では、コールスタックの詳細はプログラマからは見えない。関数のリストだけにアクセス可能で、スタックを構成しているメモリ自体にアクセスすることはできない。一方アセンブリ言語の多くでは、プログラマはスタックを操作する必要がある。プログラミング言語におけるスタックの詳細はコンパイラ、オペレーティングシステム、命令セットなどに依存する。
呼び出し側処理
通常、サブルーチンを呼び出す側でのコールスタック処理は最小限になっている。呼び出すコードがあちこちに存在することを考慮すれば、こうすることでコードの増大を抑えることができる。実際の引数の値は呼び出し毎に固有なので呼び出し側で評価され、呼出規約に従ってスタックにpushされるかレジスタに置かれる。「Branch and Link」のような実際の呼び出し命令が制御をターゲットのサブルーチンに転送するために実行される。
呼ばれた側の処理
呼ばれたサブルーチンでは、最初にサブルーチンプロローグと呼ばれるコードを実行する。そこで実際のコードを実行する前に行わなければならない細々とした処理を行う。
プロローグでは、一般に呼び出し命令が所定のレジスタに置いたリターンアドレスをコールスタックにpushする。同様に現在のスタックポインタかフレームポインタ（あるいは両方）をpushする。命令セットアーキテクチャによってはこれらが呼び出し命令の一部として実行され、そのような環境ではプロローグですべきことは無い。
フレームポインタを使っている場合、プロローグではフレームポインタに新たな値をセットする（スタックポインタの値を活用する）。局所変数の領域は必要に応じて徐々にスタックポインタを変化させて確保していく。
FORTH言語ではコールスタック（リターンスタック）を明示的にワインドすることができる。Scheme言語では「動的ワインド dynamic wind」という機能があり、スタック上に特殊なフレームをワインドすることができる。
復帰処理
サブルーチンから復帰することができる状態になると、プロローグの逆のエピローグ処理が行われる。これは一般的には保存されていたレジスタの値（フレームポインタなど）をスタックフレームからリストアし、スタックポインタの値を変更してスタックフレーム全体をpopし、最後にリターンアドレスに分岐する命令を実行する。多くの呼出規約ではエピローグ処理でpopする範囲に元々の引数も含まれる。その場合、呼び出した側に戻ったときにすべきことは何もない。呼出規約によっては、引数部分のpopを呼び出し側の責任で行うものがある。
アンワインド
呼び出された関数から復帰するとスタックのトップにあったフレームがpopされ、戻り値が残される。
Pascalなどの言語は関数の入れ子を越えた広域のgoto文をサポートしており、呼び出し側関数に制御を移すことができる。このとき、スタックのアンワインドを行って、goto文の戻り先の関数に対応したスタックフレームまで戻す必要がある。このような制御の転送は一般にエラー処理にのみ使われる。
スタックは例外処理の際にもアンワインドされなければならない。例外をサポートするためには、スタックフレームにさらに例外ハンドラを示すエントリが必要となる。例外がスローされると、スタックはその例外を処理できる例外ハンドラが見つかるところまでアンワインドされる。Common Lispではスタックがアンワインドされたときに起きることを制御するunwind-protectという特殊なマクロがある。
継続を適用する場合、スタックは一度アンワインドされ、再度ワインドされて実行を継続する。継続を実装する方法はこれだけではなく、明示的に複数のスタックを用意して継続するアプリケーションが単にそのスタックを起動して渡すべき値をワインドする。
コールスタックとソフトウェアテスト
近年（2006年）、コールスタックを使ったこれまでとは全く異なる技法が発表された。それはコールスタックを使った test suite reduction と呼ばれる技法である。大まかに言えば、実行時のコールスタックが同じになるテストケースは等価だとみなしてテスト件数を減らしつつ、テストスイート全体の問題検出能力を維持するという考え方である。
性能解析
無作為にコールスタックの標本を採取することで、プログラムの性能最適化に利用することができる。コールスタック上によく現れるサブルーチンは頻繁に呼び出されるか1回の実行に時間がかかっていると想定でき、その呼び出し回数を減らしたり、1回の実行にかかる時間を短縮することで大きな効果が期待できる。詳しくは性能解析を参照。
セキュリティ
コード（リターンアドレス）とデータ（引数、戻り値、局所変数）がコールスタックに混在していることはセキュリティ上危険である。詳しくはバッファオーバーランおよびスタックを参照されたい。