関数型プログラミング言語の定義＆実装の仕方の例

前置き：何となく成り行きで何か書かないと心苦しいので、殴り書きレベル ＆ 文才がなくてつまらない ＆ 関数型言語の授業等を受けたことがある方にはものすごく当たり前の教科書的内容ですみませんが、取り急ぎ自分が容易に書けることを書きます。（この記事に直接の関係がある）質問があれば、（すぐに反応できない場合もあると思いますが）なるべく答えます。誤植などの指摘も助かります。

さて、プログラマならば誰しも一度は「オレオレ・オリジナル・プログラミング言語を作りたい」という欲求を抱きますよね。（抱きますよね？）

そのとき、文字列レベルの文法（具象構文(concrete syntax)と言います）はわりと誰でも(?)考えられますが、それが木構造レベルでどういう風に表されて（抽象構文(abstract syntax)と言います）、どう動作するのか（操作的意味論(operational semantics)と言います）、個々の具体例だけではなく一般的に定義し、それを正しく実装することは慣れないとなかなか難しいと思います（ですよね？）。

関数型プログラミング言語（関数型言語と略します）は、対象言語としてもそれを実装する言語（メタ言語(meta language)と言います）としても比較的簡単で、「オレオレ・オリジナル・プログラミング言語を作りたい」という欲求の実現に最適です。

例として、以下のような抽象構文の言語を考えてみます。この記事では具象構文やそれを抽象構文に変換する方法（字句解析・構文解析）はどうでも良いので省略します。

E （式） ::= i                           （定数）
  　　　  |  x                           （変数）
 　　　   |  E1 - E2                     （引き算）
  　　　  |  if E1 <= E2 then E3 else E4 （条件分岐）
 　　　   |  function(x){E}              （引数xを受け取り、式Eの値を返す関数） 
  　　　  |  E1(E2)                      （関数E1を引数E2に適用する）

これはBNF（バッカス・ナウア形式）という構文定義記法の一種です。BNFは具象構文にも使えますが、ここでは抽象構文なので、ifとかthenとかelseとかfunctionとか-とか<=とか(とか)とか{とか}とか、個々の記号や単語に本当は意味はないのですが、人間がわかりやすい書き方をしています。この抽象構文を普通の人間の言葉で書き下すと、以下のとおりです。

• 式Eの構文は、以下の6種類のいずれかである
• 定数の構文は、1つの整数iからなる（整数の定義はすでにあるものと仮定します）
• 変数の構文は、1つの変数名xからなる（変数名は単なる文字列で表すことにします）
• 引き算の構文は、2つの式E1とE2からなる
• 条件分岐の構文は、4つの式E1, E2, E3, E4からなる
• 関数の構文は、1つの変数名xと、1つの式Eからなる
• 関数適用（関数呼び出し）の構文は、2つの式E1とE2からなる

しつこいですが、これは構文の定義に過ぎないので、「引き算」とか「条件分岐」とかはあくまで人間にわかりやすいように名前をつけて呼んでいるいるだけで、それらの実際の意味はまだ特に定めていないことに注意してください。

ここまでを例えばOCamlで書くと、以下のようになります（Haskell等でも見た目は違いますが本質的には同様です）。繰り返しになりますが、抽象構文なので、木構造だけが重要で、さっきのBNF定義にあったthenとか{とかの単語や記号は出てこないことに注意してください。

type exp = Int of int
  | Var of string
  | Sub of exp * exp
  | If of exp * exp * exp * exp
  | Fun of string * exp
  | App of exp * exp

構文（と言っても具象構文を省略したので抽象構文だけですが）を定めたら、次にその意味（動作）を考えます。関数型言語の場合、基本的には「プログラム＝式」「プログラムの実行＝評価(evaluation)すなわち式の値を求めること」ですので、式を受け取って評価する（＝値を求める）関数Evalを考えます。基本的には、「引き算」「条件分岐」等の「人間の意図」を抽象構文に従った場合分けと再帰により書き下すだけです。

Eval(i) = i

Eval(E1-E2) =
  Eval(E1) = i かつ Eval(E2) = j として、
  i から j を引いた整数を返す

Eval(if E1 <= E2 then E3 else E4) =
  Eval(E1) = i かつ Eval(E2) = j として、
  i <= j ならば Eval(E3) を、そうでなければ Eval(E4) を返す

Eval(function(x){E}) = function(x){E}（そのまま）

Eval(E1(E2)) =
  Eval(E1) = function(x){E} かつ Eval(E2) = v として、
  式Eの中の変数xに値vを代入した式E'に対し、Eval(E') を返す

Eval(x)のケースは？と思うかもしれませんが、最後の行で適用される関数の仮引数xには実引数vが代入されているはずなので、何も代入されていないxがいきなり出現したら、未定義の変数があったということで、エラー（評価結果すなわちEvalの返り値がまさに「未定義」）とします。

さらに鋭い方は、引き算やifのケースでEval(E1)やEval(E2)が整数にならなかったらどうするの？と思うかもしれませんが、その場合も同様にエラー（式全体の値は未定義）とします。関数適用のケースでEval(E1)が関数にならなかった場合も同様です。

Evalの定義はこれで良いのですが、最後の行の「式Eの中の変数xに値vを代入した式E'」をちゃんと定義していなかったので、(E,x,v)を引数として受け取りE'を返す関数Substを定義します。これも基本的には式Eの抽象構文に従った場合分けと再帰により定義します。

Subst(i,x,v) = i

Subst(x,x,v) = v

Subst(y,x,v) = y　（xとyが異なる変数名の場合）

Subst(E1 - E2,x,v) = Subst(E1,x,v) - Subst(E2,x,v)

Subst(if E1 <= E2 then E3 else E4,x,v) =
  if Subst(E1,x,v) <= Subst(E2,x,v) then Subst(E3,x,v) else Subst(E4,x,v)

Subst(function(y){E},x,v) =　（xとyが異なる変数名の場合）
  function(y){Subst(E,x,v)}（知っている方向けの注：vは閉じた式しか考えないことにします）

Subst(function(x){E},x,v) =
  function(x){E}（変数名がかぶっている場合、Eの中のxは外のxとは異なるので代入しない）

Subst(E1(E2),x,v) = (Subst(E1,x,v))(Subst(E2,x,v))

これらをOCamlで実装すると以下のようになります。

let rec subst e0 x v =
  match e0 with Int i -> Int i
  | Var y -> if x = y (* 同じ変数名か？ *) then v (* 置き換える *) else Var y
  | Sub(e1, e2) -> Sub(subst e1 x v, subst e2 x v) (* 単に再帰的に代入 *)
  | If(e1, e2, e3, e4) -> If(subst e1 x v, subst e2 x v,
                             subst e3 x v, subst e4 x v) (* 単に再帰的に代入 *)
  | App(e1, e2) -> App(subst e1 x v, subst e2 x v) (* 単に再帰的に代入 *)
  | Fun(y, e) -> if x = y then Fun(y, e) else Fun(y, subst e x v)

let rec eval e0 =
  (* パターンマッチが網羅的でないので警告が出るが放置（実行時型エラーに相当）*)
  match e0 with Int i -> Int i
  | Sub(e1, e2) ->
      let Int i = eval e1 in
      let Int j = eval e2 in
      Int(i - j)
  | If(e1, e2, e3, e4) ->
      let Int i = eval e1 in
      let Int j = eval e2 in
      if i <= j then eval e3 else eval e4
  | Fun(x, e) -> Fun(x, e)
  | App(e1, e2) ->
      let Fun(x, e) = eval e1 in
      let v = eval e2 in
      let e' = subst e x v in
      eval e'

プログラム例1：たしざん

let one_plus_two = Sub(Int 1, Sub(Int 0, Int 2)) (* 1 - (0 - 2) *)

ocamlコマンド（対話環境）上で実行

# eval one_plus_two ;;
- : exp = Int 3

プログラム例2：関数定義・適用と条件分岐の例

let _Let(x, e1, e2) =
  (* let x = e1 in e2 を (function(x){e2})(e1) と定義
     （このように構文レベルの読み替えで実装された言語機能を
     構文糖衣(syntax sugar)と言います） *)
  App(Fun(x, e2), e1)

let abs =
  (* let abs = function(x){if x<=0 then 0-x else x} in abs(-42) *)
  _Let("abs",
       Fun("x", If(Var "x", Int 0,
                   Sub(Int 0, Var "x"),
                   Var "x")),
       App(Var "abs", Int(-42)))

# eval abs ;;
- : exp = Int 42

プログラム例3：無限ループ

let fix =
  (* 再帰を実現するための魔訶不思議な式
     （不動点演算子(fixed-point operator)と言います） *)
  Fun("f",
      App(Fun("x",
              App(Var "f",
                  Fun("y", App(App(Var "x", Var "x"), Var "y")))),
          Fun("x",
              App(Var "f",
                  Fun("y", App(App(Var "x", Var "x"), Var "y"))))))

let _Rec(f, x, e1, e2) =
  (* let rec f(x) = e1 in f(e2) に相当 *)
  App(App(fix, Fun(f, Fun(x, e1))), e2)

let loop =
  (* let rec f(x) = f(x) in f(0) *)
  _Rec("f", "x",
       App(Var "f", Var "x"),
       Int 0)

# eval loop ;;
  C-c C-cInterrupted.

プログラム例4：1から10000までの整数の総和

let sum10000 =
  (* let rec sum(n) = if n<=0 then 0 else sum(n-1)-(0-n) in sum(10000) *)
  _Rec("sum", "n",
       If(Var "n", Int 0, Int 0,
          Sub(App(Var "sum", Sub(Var "n", Int 1)),
              Sub(Int 0, Var "n"))),
       Int 10000)

# eval sum10000 ;;
- : exp = Int 50005000

需要があれば後で書く：代入ではなく環境（とクロージャ）を用いた、より効率的な実装 → 書きました！ 環境とクロージャを用いた、より効率的な関数型プログラミング言語の定義＆実装の仕方の例