2.1 言語仕様

MiniML言語のBNF文法を以下に示す．文法中，$\langle \ldots\rangle$は非終端記号を表し，$\color{red}{\mathtt{...}}$（空白を含まない文字列）は終端記号を表すものとする．$\langle \mathit{ID}\rangle$は英小文字，数字，下線記号（_），単一引用符（'）の列である．ただし，最初の文字は英小文字とする．$\langle \mathit{IntV}\rangle$は1個以上の数字の列である．終端記号の区切りは任意個のスペース，タブ，または改行とする．

MiniMLの文法規則

$$\begin{align*} \langle \mathit{toplevel}\rangle &::= \langle \mathit{Expr}\rangle \color{red}{\texttt{ ;;}} \\ \\ \langle \mathit{Expr}\rangle &::= \color{red}{\texttt{if }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ then }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ else }} \langle \mathit{Expr}\rangle \\ &\ \ \ | \ \ \ \color{red}{\texttt{fun }} \langle \mathit{ID}\rangle \color{red}{\texttt{ -> }} \langle \mathit{Expr}\rangle \\ &\ \ \ | \ \ \ \color{red}{\texttt{let }} \langle \mathit{ID}\rangle \color{red}{\texttt{ = }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ in }} \langle \mathit{Expr}\rangle \\ &\ \ \ | \ \ \ \color{red}{\texttt{let rec }} \langle \mathit{ID}\rangle \color{red}{\texttt{ = fun }} \langle \mathit{ID}\rangle \color{red}{\texttt{ -> }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ in }} \langle \mathit{Expr}\rangle \\ &\ \ \ | \ \ \ \color{red}{\texttt{loop }} \langle \mathit{ID}\rangle \color{red}{\texttt{ = }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ in }} \langle \mathit{Expr}\rangle \\ &\ \ \ | \ \ \ \langle \mathit{LTExpr}\rangle \\ \\ \langle \mathit{LTExpr}\rangle &::= \langle \mathit{PExpr}\rangle \color{red}{\texttt{ < }} \langle \mathit{PExpr}\rangle \\ &\ \ \ | \ \ \ \langle \mathit{PExpr}\rangle \\ \\ \langle \mathit{PExpr}\rangle &::= \langle \mathit{PExpr}\rangle \color{red}{\texttt{ + }} \langle \mathit{MExpr}\rangle \\ &\ \ \ | \ \ \ \langle \mathit{MExpr}\rangle \\ \\ \langle \mathit{MExpr}\rangle &::= \langle \mathit{MExpr}\rangle \color{red}{\texttt{ * }} \langle \mathit{AppExpr}\rangle \\ &\ \ \ | \ \ \ \langle \mathit{AppExpr}\rangle \\ \\ \langle \mathit{AppExpr}\rangle &::= \langle \mathit{AppExpr}\rangle \color{red}{\texttt{ }} \langle \mathit{AExpr}\rangle \\ &\ \ \ | \ \ \ \color{red}{\texttt{recur }} \langle \mathit{AExpr}\rangle \\ &\ \ \ | \ \ \ \langle \mathit{AExpr}\rangle \\ \\ \langle \mathit{AExpr}\rangle &::= \langle \mathit{IntV}\rangle \\ &\ \ \ | \ \ \ \color{red}{\texttt{true}} \\ &\ \ \ | \ \ \ \color{red}{\texttt{false}} \\ &\ \ \ | \ \ \ \langle \mathit{ID}\rangle \\ &\ \ \ | \ \ \ \color{red}{\texttt{( }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ )}} \\ &\ \ \ | \ \ \ \color{red}{\texttt{( }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ , }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ )}} \\ &\ \ \ | \ \ \ \langle \mathit{AExpr}\rangle \color{red}{\texttt{ . }} \langle \mathit{IntV}\rangle \end{align*}$$

MiniML言語は，講義テキストのML$^4$言語と比較し，以下の3つの点で大きく異なる．

(1) トップレベル宣言

MiniML言語では，トップレベルの宣言 (declaration)を書くことはできず，プログラム全体は単一の式 (expression)からなる．トップレベルで宣言できないだけであり，let式やlet rec式による変数や関数の束縛は可能である．したがって：

のようなトップレベル宣言を含むML$^4$のプログラムと同等のMiniMLプログラムは，単に：

と書けば良く，言語の表現力はまったく損われていない．

(2) 組

MiniML言語は，OCamlと同じ組を組込みのデータ型として扱うことができる（組についてはObjective Caml入門の3.2節を参照）．ただし簡単のため，一つの組に含めることのできる要素の数はちょうど2個であり，また，組から要素を取り出すためのパターンマッチ構文も備えていない．組を扱うための構文は次の2つである．

$$\begin{align*} \langle \mathit{AExpr}\rangle &::= \cdots \\ &\ \ \ | \ \ \ \color{red}{\texttt{( }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ , }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ )}} \\ &\ \ \ | \ \ \ \langle \mathit{AExpr}\rangle \color{red}{\texttt{ . }} \langle \mathit{IntV}\rangle \end{align*}$$

たとえば，let t = (0, 100) in ...によって生成した組tから第1要素0を取り出すにはt.1と書き，第2要素を取り出すにはt.2と書く（それぞれt.0とt.1ではないことに注意）．3つ以上のデータをまとめて扱いたい場合には：

のように，2つ組を必要なだけ入れ子にすれば良い．

(3) ループ構文

関数型言語で何らかの処理の繰り返しを表現する場合，一般的には再帰関数を用いる．MiniML言語でもlet rec式を使って再帰関数を定義することはもちろん可能だが，それ以外に，繰り返しを直接的に表現するための特殊構文も備えている．

$$\begin{align*} \langle \mathit{Expr}\rangle &::= \cdots \\ &\ \ \ | \ \ \ \color{red}{\texttt{loop }} \langle \mathit{ID}\rangle \color{red}{\texttt{ = }} \langle \mathit{Expr}\rangle \color{red}{\texttt{ in }} \langle \mathit{Expr}\rangle \\ \\ \langle \mathit{AppExpr}\rangle &::= \cdots \\ &\ \ \ | \ \ \ \color{red}{\texttt{recur }} \langle \mathit{AExpr}\rangle \end{align*}$$

loop式は，その見た目からも分かるとおり，let式とほとんど同じ意味を持ち，変数を値に束縛してから本体式の評価を行う．let式と異なるのは，loop式が繰り返しの先頭位置をマークしている点である．loop本体式の中で「recur $e$」を実行すると，最も内側のloop式の先頭に戻り，$\langle \mathit{ID}\rangle$を$e$の評価結果に束縛し直してから，本体式を再度評価する．ここで，「recur $e$」は，recurという名前の特別な関数を式$e$に適用しているのではなく，全体で一つの特殊な式であることに注意して欲しい．そのため：

のようなコードは構文エラーであり書くことはできない．

たとえば，$1$から$100$までの総和を計算するloop式は次のように書くことができる．

recur式には，普通の再帰関数呼出しとは異なり，その評価結果がそれを取り囲む一番内側のloop式全体の評価結果となるような位置にしか書くことができない，という強い制約がある．

ただし，「その評価結果」と書いているが，recur式の評価結果などというものは 存在しないことに注意して欲しい．たとえば，上の総和計算コードを代わりに：

のように書くことは出来ない．

さらに，loop式の本体式中に現れる（fun式やlet rec式による）関数本体式に含まれるrecur式や，同じくloop式の本体式中に現れる「recur $e$」の式$e$に含まれるrecur式は，外側のloop式と制御構造上の結びつきを持たない．そのため，先程のコードを少し（不自然に）書き換えた：

のようなコードは許されない．（当然のことながら，関数本体式の中に別のloop式を書き，その内側にrecur式を含めることは可能である．）

上記の様々な制約を踏まえた上でrecur式を書くことのできるプログラム中の位置のことを，末尾位置 (tail position)と呼ぶ．様々な制約があるため，慣れないうちはきちんと理解するのに時間がかかるかも知れないが，さしあたっては上の例を理解できていれば十分である．末尾位置の正確な定義は，recur式の検査であらためて示す．末尾位置の概念を用いると，上記の制約は「recur式は末尾位置にしか書くことができない」と簡潔に言い換えることができる．

なお，通常の関数についても，関数定義の本体式中に含まれる関数適用式の評価結果が，その本体式全体の評価結果となる場合，その関数適用式は末尾位置にあると言い，その関数適用を末尾呼出し (tail call)と呼んだりする．末尾呼出しを効率良く実装するための最適化手法が数多く存在するが，この実験では時間の都合により扱わないこととする．

BNF文法では上記のrecur構文に関する制約を表現できていないため，入力プログラムが制約を満たしていることの確認は抽象構文木に対して行う．