現実のハードウェアが備えている物理レジスタの個数は有限である．そのため，関数（とくに再帰関数）を用いるプログラムではプログラム中のすべての計算を物理レジスタだけで実行することは困難であり，一般に，プログラム中の各変数が束縛されている値の格納場所を，何らかの系統的な手順に従いメモリ中のどこかへ確保する必要がある．たとえば，次のようなOCamlプログラム：

let f a = a + 1 in
let g b = f b in
g 0

を（物理レジスタは使用せずに）実行するだけであれば，プログラム全体で「関数fの引数aを格納する場所」「関数fを呼び出した結果（返り値）を格納する場所」「関数gの引数bを格納する場所」「関数gの返り値を格納する場所」の計4ワード分のメモリ領域を確保すれば十分である．

しかし，そのような素朴な方法を用いて：

let rec fact n = if n < 1 then 1
                 else n * fact (n - 1) in
fact 10

のような再帰関数を実行しようとすると，複数の異なる（再帰）呼出しの引数や返り値の格納場所として同じメモリ領域を使うことになり，明らかにおかしな計算を行ってしまう．具体的には，再帰呼出しfact 9の直後には，その返り値に対しを掛ける必要があるが，呼出しfact 10の引数である値は関数factの引数を格納するために一つだけ確保されていた場所に置かれていたため，再帰呼出しfact 9の時点で値により上書きされてしまっている（正確には，さらにで上書きされているが，ともかくという値は乗算を実行する時点ではもう存在しない）．

結局のところ，（再帰関数を含めた）関数呼出しを行うプログラムを正しく動かすためには，プログラム中の関数定義毎に必要な領域のサイズを求め，その総和分のメモリ領域を確保するだけでは不十分であり，実行中に行われる関数呼出し毎に異なるメモリ領域を確保する必要があることが分かる．そのため，関数の概念を備えているプログラミング言語（関数型プログラミング言語に限らず，C言語やJava言語なども含む）の処理系では，通常，関数呼出し/リターンの制御構造に対応できるよう，各関数呼出しにおける関数本体の実行に必要となるメモリ領域を管理するためのデータ構造として，LIFO (Last-In First-Out)で管理するスタックを使用する．また，このスタックは，呼出し側が関数呼出しの次に実行するべき命令のアドレス（リターンアドレス (return address)と呼ばれる）を保存しておくためにも用いられる（詳細は後述）．

原理的には，各関数の実行で必要となるすべての引数，返り値，局所変数，リターンアドレスのための場所を上述のとおりにスタック上に必ず確保することにすれば，再帰関数であっても正しく実行できる．しかしながら，そのような素朴な方法を用いると，プログラム実行中に計算されるすべての値を逐一メモリ領域に格納することになり，レジスタを有効に活用しないため実行性能があまり良くない．たとえば返り値の場合，返り値を格納する場所をスタック上の特定の場所に決めてしまうと，（レジスタだけで演算を行うRISC系のハードウェアにおいては特に）呼び出された関数の本体の最後で必ずスタック上のその場所に返り値をストアし，その直後に，関数を呼び出した側がそこからレジスタへロードするという，無駄なメモリアクセスが頻繁に起こる．

このような無駄による実行オーバヘッドは，たとえば「関数呼出しの返り値は必ずa1レジスタを使って受け渡しする」のように決めておけば避けることができる．また，引数の受け渡しについても同様に，レジスタの使い方に関して何らかの約束事を決めておけば，実行効率を良くすることができる．

以上のようなスタックとレジスタの使い方に関する約束事は，レジスタの種類や個数，関数の呼出し/リターンに用いることのできるジャンプ命令の詳細な振舞いなどに依存するため，通常，計算機アーキテクチャ毎に定められている．関数呼出しに関するそのような約束事は呼出し規約 (calling convention)と呼ばれる．

この実験で作成するMiniMLコンパイラは，ARMアセンブリをターゲットとするため，本来であればARMの呼出し規約に厳密に従うべきだが，実装を分かりやすくするため，少し簡略化した独自の呼出し規約を用いることにする．より本格的なプログラミング言語・処理系との互換性（一方の言語からもう一方の言語で定義された関数を呼び出すことが可能等）を厳密に確保したい場合には，この資料に書かれている説明を理解した後，各自でさらに調べてみて欲しい（「ARM calling convention」などと検索すれば，たくさんの情報を得ることが出来る）．

MiniMLコンパイラにおける呼出し規約

まず，関数の返り値については，先程触れたとおり，a1レジスタを介して受け渡すことにする．また，MiniMLのすべての関数はちょうど1つしか引数を受け取らないため，そこから生成した仮想機械コードのすべての関数は，_toplevelを除き，必ず2つの引数を受け取る．そこで，第1，2引数を，それぞれa1，a2レジスタを介して受け渡すことにする．_toplevelについては，プログラム開始時にa1，a2レジスタに入っている値はゴミだと思えば良い．

プログラム実行中，1回の関数呼出しを実行するために必要なスタック上の連続領域をフレーム (frame)と呼ぶ．フレームは，呼び出された関数の実行開始時に，以下の図のようにスタックの一番上（下位アドレス側）に確保され，spレジスタは常にスタックトップ（フレームの一番下）を指すようにする．

stack spec
フレームの中身

各フレーム中には，関数の実行に必要となる以下のデータが含まれている．

退避されたfpレジスタ（saved fp）
このフレームを使用する関数を呼び出す以前にfpレジスタに入っていた値を退避するための場所．フレーム中の（ほとんど）すべてのフィールドには，現在実行中の関数のフレーム最上部を指しているfpレジスタを介して（つまり，レジスタ間接アドレッシングによって）アクセスする．関数が呼び出された直後，fpレジスタは呼び出した側の関数用のフレーム最上部を指しているため，上図のように呼び出された側のフレーム最上部を指すよう更新されるが，関数呼出しからのリターン後には，元の位置を指すように戻す必要がある．
リターンアドレス（lr）
このフレームを使用する関数を呼び出した側が，その関数呼出しの次に実行する命令のアドレス（通常，lrレジスタに入っている）を退避するための場所．さらに別の関数を呼ぶことがなければ必ずしも退避する必要はないが，ここでは簡単のため必ず退避することにする．
局所変数（local 0, , local n-1）
関数本体中でlet式を使って束縛する局所変数の値を格納するための場所．
退避されたa1，a2レジスタ（saved a1, saved a2）
このフレームを使っている関数が実引数をa1，a2レジスタにセットして他の関数を呼び出す際，a1，a2レジスタに含まれている自分自身のパラメータを退避するための場所．関数呼出し以降にパラメータを使わないのであれば必ずしも退避する必要はないが，ここでは簡単のため必ず退避することにする．

上記のとおりにフレーム中にデータを配置すれば，saved fpのアドレスは$fp，lrのアドレスは$fp，局所変数のアドレスは$fp，saved a1，saved a2 のアドレスはそれぞれ$sp，$spとなる．

関数呼出しを実行する際の具体的な手順は以下のとおりである．

  1. 呼出し側は，a1，a2レジスタに含まれている値を自身のフレームのsaved a1，saved a2領域に退避してから，関数呼出しの実引数をa1，a2レジスタにセットする．

  2. blあるいはblx命令を実行し，呼び出される関数の先頭へジャンプする．ジャンプ後，呼出し側の直後の命令のアドレス（手順12以降を実行するための命令が含まれている）はlrレジスタにセットされている．

  3. （以降，呼び出された関数側で実行）fpレジスタに入っている呼出し側のフレームの最上部アドレスを，スタックの所定の位置に退避する．所定の位置は，spからの相対アドレス（1ワード下）で求まる．

  4. lrレジスタに入っているリターンアドレスを，スタックの所定の位置に退避する．所定の位置は，spからの相対アドレス（2ワード下）で求まる．

  5. 新しく確保するフレームの最上部（現在spが指している位置から1ワード下）を指すように，fpレジスタを更新する．

  6. 局所変数の個数を考慮し，必要な分だけspレジスタを下げる．

  7. 関数本体を実行し，求まった返り値をa1レジスタにセットする．

  8. スタック中に退避していたリターンアドレスをlrレジスタに戻す．

  9. spレジスタの指す位置を，手順6以前の位置に戻すことで，スタックからフレームを取り除く．元の位置に戻すには，手順6で下げた分だけspレジスタを上げても良いが，fpレジスタが現在指している位置から1ワード上であることを利用する方がより簡単である．

  10. スタック中の退避していたsaved fpをfpレジスタに戻す．

  11. bx命令を実行し，手順8で取り出したリターンアドレスへジャンプする．

  12. （以降，呼出し側で実行）a1レジスタから返り値を取り出し，文脈に応じた適切な場所に保存する．

  13. 退避しておいたsaved a1，saved a2を，それぞれa1，a2レジスタに戻す．

最後に，以下の簡単なOCamlコード：

let f a b = g (a + b) (a - b) in
let g m n = let x = m + n in
            let y = x * x in
            let z = y + 1 in
            z
in f 1 2

をこの節の呼出し規約に従って実行する場合において，関数fから関数gを呼び出す前後のスタックの状態を以下に示す．

(a) 関数gを呼び出す直前

before call

(b) 関数gを呼び出した直後

during call

(c) 関数gからのリターン直後

after call