コールスタック
PascalやAdaといったプログラミング言語はサブルーチンの入れ子が可能であり、内側のルーチンが外側のルーチンのコンテキスト(外側のルーチンの引数や局所変数)にアクセスできるようになっている。この静的な入れ子はいくつも繰り返すことができ、関数の中に別の関数を定義し、その中でさらに別の関数を定義し......といったことが可能である。このため実装に当たっては呼び出された関数が静的な入れ子を遡って外側のフレームにアクセスできる手段を提供する必要がある。一般に外側のフレームへのポインタとしてこの参照を実装し、これを「ダウンスタック・リンク」または「スタティック・リンク」と呼んで、直前の呼び出し側ルーチンとのリンク(ダイナミック・リンク)と区別する(呼び出し側は定義上の外側のルーチンとは限らない)。例えば、内側のルーチンは自分自身を再帰呼び出しできるようになっている言語が多く、同じルーチンのスタックフレームがコールスタック上にいくつも重なることがあり、それらが全て同じ外側のルーチンのコンテキストへのスタティック・リンクを持つことになる。スタティック・リンクの代わりに、外側のスタックフレームへの参照を集めてポインタの配列とする方式もある。この配列を display と呼び、インデックスを指定することで必要なフレームを得ることができる。バロース B5000 はハードウェアでこれをサポートしており、32レベルの静的入れ子を使用可能だった。
呼ばれたサブルーチンでは、最初にサブルーチンプロローグ(英語版)と呼ばれるコードを実行する。そこで実際のコードを実行する前に行わなければならない細々とした処理を行う。
プロローグでは、一般に呼び出し命令が所定のレジスタに置いたリターンアドレスをコールスタックにpushする。同様に現在のスタックポインタかフレームポインタ(あるいは両方)をpushする。命令セットアーキテクチャによってはこれらが呼び出し命令の一部として実行され、そのような環境ではプロローグですべきことは無い。
フレームポインタを使っている場合、プロローグではフレームポインタに新たな値をセットする(スタックポインタの値を活用する)。局所変数の領域は必要に応じて徐々にスタックポインタを変化させて確保していく。
FORTH言語ではコールスタック(リターンスタック)を明示的にワインドすることができる。Scheme言語では「動的ワインド (dynamic wind)」という機能があり、スタック上に特殊なフレームをワインドすることができる。