Arantium Maestum

プログラミング、囲碁、読書の話題

めざそう言語処理系の沼　〜shift/resetへの旅 〜　その６ 関数（ダイナミック・スコープ）

OCaml めざそう言語処理系の沼 言語処理系

分岐や変数束縛が出来るようになったので、次は関数定義を追加したい。

機能としては：

  • fnで無名関数を作成
  • letfnで関数を名前付きで作成（複数同時も可）
  • 多引数に対応、引数の数が定義時と呼び出し時に合っていなかったらエラー
  • 今回はダイナミック・スコープ

といったところ。

使用例としては：

((fn [x y]
   (+ (* x x)
      (* y y)))
 3
 4)

（結果は25）とか：

(letfn [f [x y] (+ (* x x) (* y y))]
  (f 3 4))

(letfn [(f [x] (* x x))
        (g [x] (+ x x))]
  (- (f 5) (g 10)))

（結果は２５と5）といったプログラムが書けるようになる。（letと同じく、定義されている関数が一つだけだったら[]の内側の()は省略できる）

今回のコード差分：

Comparing v0.5...v0.6 · zehnpaard/kontlang · GitHub

まず、Exp.tにfnとletfnの式を追加：

type t =
...
| Fn of string list * t
| LetFn of (string * string list * t) list * t

無名関数は

  • 引数の文字列のリスト
  • 呼び出し時、引数を変数束縛した後に評価される式

だけで成り立っている。

名前付き関数だとここに関数名を表す文字列が追加される。なのでLetFnは

  • 名前付き関数を表す「『関数名の文字列』『引数の文字列のリスト』『呼び出し時に（中略）評価される式』」のリスト
  • let本体の式

を持つ。

次にValモジュール：

type t =
...
| Fn of string * string list * Exp.t

無名関数、名前付き関数どちらも定義が評価されるとVal.Fnという値になる。

  • 関数名の文字列
  • 引数の文字列のリスト
  • 呼び出し時に（中略）評価される式

と、関数の値は式とほとんど同じ構成になっている。この簡単な構成はダイナミック・スコープならではで、本体の式に出てくる自由変数を捕捉してクロージャにしたりする必要がないので非常に楽（その分言語がピーキーになるが・・・）。

最後はExecuteモジュール。eval：

let eval env cont = function
...
| Exp.Fn(params, body) -> ApplyCont(env, cont, Val.Fn("anon", params, body))
| Exp.LetFn(fns, e) ->
    let f (fname, params, body) = (fname, Val.Fn(fname, params, body)) in
    Eval(Env.extend_list (List.map f fns) env, Cont.Env::cont, e)

Exp.Fnの場合はそのままVal.Fnに変換（変数名は"anon"に統一）して、apply_contに渡している。

Exp.LetFnの場合はExp.Fnと同じようにVal.Fnに変換してから、Exp.Letと同じように変数束縛し、継続にCont.Envを追加して本体の式を評価している。

新しい継続がまったく出てこない。関数定義を評価する時に「式の一部分の式を評価してあれこれする」と流れが出てこないので特殊な継続が必要ないのである。

ただし、apply_contのCont.Callケースに手を入れる必要はある：

let apply_cont env cont v = match cont with
...
| Cont.Call([], vs) :: cont' -> (match List.rev (v::vs) with
  | Val.Op(_, fn) :: vs' -> ApplyCont(env, cont', (fn vs'))
  | Val.Fn(s, ss, e) :: vs' ->
    let paramcount = List.length ss in
    let argcount = List.length vs' in
    if paramcount = argcount then Eval(Env.extend_list (List.combine ss vs') env, Cont.Env::cont', e)
    else failwith @@ Printf.sprintf "Function %s called with incorrect number of args: expected %d received %d" s paramcount argcount
  | _ -> failwith "Calling non-callable in operator position")

今までは関数呼び出し時にオペレータポジションがVal.Opならよし、そうでない場合はエラーだったのだが、今回Val.Fnケースを追加（ついでにエラー時にCalling non-opだったメッセージをCalling non-callableにした）。

関数呼び出しのロジックはけっこう簡単で、定義時の引数の数と呼び出し時の引数の数（仮引数と実引数）が一致しない場合はエラー。一致した場合、仮引数と実引数を合わせて変数環境に追加し、Cont.Envを継続に追加した上で、関数の本体の式を評価する。

このように意外と簡単に関数が実装できた。ダイナミック・スコープなのも楽だった要因の一つである。

しかし、ダイナミック・スコープだと言語としては使いづらい。関数呼び出し時の変数環境によって関数の挙動が変わってしまう可能性があるからである。

例えば変な例だが：

(letfn [f [x] (* x x)]
  (let [* +] (f 5)))

だと、f定義時には*は普通なのに、呼び出し時にはシャドーされてしまって挙動が完全に変わっている（結果は１０になる）。例を簡単にするために*を使ったが、普通のユーザ定義された変数だったらこのようなシャドーイングが簡単に起き得るのは想像がつくと思う。うまくやれば面白い使い方もできそうだが、プログラムの挙動が予想できなくなる可能性の方がずっと高い。

ということで次回は関数をレキシカル・スコープに変更する。