ソースプログラムが「末尾位置以外にrecur式を書くことは許されない」という制約を満たしているかの検査は,ソースプログラム(の抽象構文木)をトップダウンに巡回しつつ,recur式を見つける度に巡回途中のその位置が末尾位置かどうかを逐一確認するような再帰関数として実現すれば良い.

実際の再帰関数を定義するには,「末尾位置」がどのような位置を指すのかを正確に知る必要がある.言語仕様で触れたとおり,直観的には「その評価結果が,それを取り囲む最も内側のloop式の評価結果となる式」を末尾位置に書かれている式であると考えれば良い.そのような直観に基づき,式の種類に応じて場合分けしながら末尾位置を正確に定義すると以下のようになる.

  • loop = in において,は末尾位置にある.

  • if then else において,このif式全体が末尾位置にあるならも末尾位置にある.

  • let = in において,このlet式全体が末尾位置にあるならも末尾位置にある.

  • let rec = fun -> in において,このlet rec式全体が末尾位置にあるならも末尾位置にある.

  • 上記以外のプログラム中のすべての(部分)式は,末尾位置にはない.

プログラム中に現れるすべてのrecur式が,この定義によって定められる末尾位置にあるなら,そのプログラムはrecur式を正しく用いている.

この定義に従うと,「fun -> 」がどのような位置に書かれていたとしても,本体式は末尾位置にはないことに注意して欲しい.let rec式の関数本体式や,recur式の引数についても同様である.ただし,それらの部分式が末尾位置にはないからといって,その式自体をまったく検査しなくて良いというわけではない(それらの内部にloop式があるかも知れない).

課題4(必須) recur式の検査
syntax.ml中のrecur_check関数を完成させることにより,recur式の検査を実装しなさい.parser.mly中の呼び出している箇所を見ると分かるとおり,recur_check関数はunit型の値を返す.末尾位置ではないところに書かれたrecur式を発見したら,即座に例外を投げコンパイル処理を中断すること.