言語の実装は関数型言語で、は本当か

表題の様なことがちょっと気になったので、型無λ計算の big step semantics (戦略は正格評価)を実装しました。まあ要するにしょぼいインタプリタですね。

FP でλ計算を実装する

まず、普通に関数型言語(OCaml)で実装してみました。

• λ式の型は t (term)
• λ式には整数定数と加減をプリミティブとして追加
• λ式を評価すると value になる(計算止まらない場合はさようなら)
• value には引数を待っているプリミティブがある

open List

(** primitives *)

type prim = Add | Sub

(** terms *)

type t =
  | Int of int
  | Var of string
  | App of t * t
  | Lambda of string * t
  | Prim of prim

(** semantic values *)

type value =
  | VInt of int
  | Closure of env * string * t
  | VPrim of prim * int * value list (** Not fully applied primitive *)

and env = (string * value) list

(** primitive semantics *)

let eval_prim prim args = match prim, args with
  | Add, [VInt i1; VInt i2] -> VInt (i1 + i2)
  | Sub, [VInt i1; VInt i2] -> VInt (i1 - i2)
  | _ -> assert false

(** big step semantics of terms *)

let rec eval env = function
  | Int n -> VInt n
  | Var v -> assoc v env
  | App (t1, t2) ->
      let v2 = eval env t2 in
      let v1 = eval env t1 in
      begin match v1 with
      | Closure (env, var, t) -> eval ((var,v2)::env) t
      | VPrim (prim, arity, applied) ->
          let len = length applied in
          if arity <= length applied then assert false
          else if arity = len + 1 then eval_prim prim (rev (v2::applied))
          else VPrim (prim, arity, v2 :: applied)
      | _ -> assert false
      end
  | Lambda (v, t) -> Closure (env, v, t)
  | Prim Add -> VPrim (Add, 2, [])
  | Prim Sub -> VPrim (Sub, 2, [])

(** test *)

let () =
  (*
    ley y = 2 in
    let f x = x + y in
    let y = 100 in
    f 2

    (\y.(\f.(\y.f 2) 100) (\x.x+y)) 2
  *)
  assert (eval [] (App (Lambda ("y", App (Lambda ("f", App (Lambda ("y", App (Var "f", Int 2)), Int 100)), Lambda ("x", App (App (Prim Add, Var "x"), Var "y")))), Int 2)) = VInt 4)

知っている人にはごくごく普通ですね。 まずデータ型を考えて全コンストラクタを列挙。それから関数を書いていく。

知らない？んーとね、関数型言語の凄く簡単なやつのインタプリタを関数型言語で書いたらこれくらいの短いコードで書けますねーということだと思ってください。

ロクにテストしていないがともかくクロージャーはクロージャーとして動いているみたいだ。(let なしでこういう長いλ式書くのは正直体がついていかん歳になりました) eval が末尾再帰でないから気になるという人はご自分で直してください。

OO でλ計算を実装する

でさぁ、これでいやー短くかけますねぇ！関数型言語凄いですねぇ！ねぇねぇ！では自分に対しても説得力無いので、わざわざ今度は同じ物を OO で書いてみます。本論の目的は FP と OO アプローチを比べるものですので、あえて代数的データ型(Variant)は使ったら負け。なので使いません。できるだけクラスで実現します。

open List

(** interfaces *)

class virtual value = object
end

class virtual prim = object
  method virtual arity : int
  method virtual eval : value list -> value
end

type env = (string * value) list

class virtual t = object
  method virtual eval : env -> value
end

(** implementations *)

(** values *)

class vint (n:int) = object
  inherit value
  method int = n
end

class virtual applicable = object
  inherit value
  method virtual apply : value -> value
end

class closure (env:env) (var:string) (t:t) = object
  inherit applicable
  method apply v = t#eval ((var,v)::env)
end

class vprim (prim : prim) (applied : value list) = object
  inherit applicable
  method apply v =
    let len = length applied in
    let arity = prim#arity in
    if arity <= len then assert false
    else if arity = len + 1 then prim#eval (rev (v::applied))
    else (new vprim prim (v::applied) :> value)
end

(** primitives and their semantics *)

class prim_add = object
  inherit prim
  method arity = 2
  method eval = function
    | [v1; v2] -> (new vint ((Obj.magic v1 : vint)#int + (Obj.magic v2 : vint)#int) :> value)
    | _ -> assert false
end

let prim_add = new prim_add

class prim_sub = object
  inherit prim
  method arity = 2
  method eval = function
    | [v1; v2] -> (new vint ((Obj.magic v1 : vint)#int - (Obj.magic v2 : vint)#int) :> value)
    | _ -> assert false
end

let prim_sub = new prim_sub

(** terms and their semantics *)

class int i = object
  inherit t
  method eval _env = (new vint i :> value)
end

class var v = object
  inherit t
  method eval = List.assoc v
end

class app t1 t2 = object
  inherit t
  method eval env =
    let v2 = t2#eval env in
    let v1 = t1#eval env in
    (Obj.magic v1 : applicable)#apply v2
end

class lambda var t = object
  inherit t
  method eval env = (new closure env var t :> value)
end

class add = object
  inherit t
  method eval _env = (new vprim prim_add [] :> value)
end

class sub = object
  inherit t
  method eval _env = (new vprim prim_sub [] :> value)
end

(** tools (OCaml requires explicit upcasting, so things go too verbose) *)

let var x = (new var x :> t)
let int i = (new int i :> t)
let app t1 t2 = (new app t1 t2 :> t)
let lambda var t = (new lambda var t :> t)
let add = (new add :> t)
let sub = (new sub :> t)

(** test *)

let () =
  assert ((Obj.magic
            ((app (lambda "y" (app (lambda "f" (app (lambda "y" (app (var "f") (int 2))) (int 100)))
                                (lambda "x" (app (app add (var "x")) (var "y")))))
               (int 2))#eval []) : vint)#int = 4)

OCaml は upcast を明示しなければならず (e :> t)、そして downcast は不可なので (Obj.magic e : t) を 使って無理やり書いていますが、ここは動的なクラス検査コードと思ってもらって良いです。 (実際には検査しませんが)

まず基底クラスを定義して全インターフェースを書く。それから各サブクラスを一つづつ書いていく。 FPでの型がOOでの基底クラス、FPでのコンストラクタがサブクラスと対応します。 値を適用できる値として、closure と vprim があるので、これらのスーパークラスとして applicable という インターフェース(仮想クラス/抽象クラス)を value と closure, vprim の間に定義しました。

長いですね… FP版と比べて 35% 位長いです。

書くのは実際苦労しました。クラス階層をどうわけるのかとか、どこまで method にするか悩みましたが、幸運にもだいたいすっきりクラスに埋め込めました。もちろん慣れてないだけかもしれません。FP アプローチも代数的データ型に慣れてない人にとっては書くのは一苦労だと想像します。

私は両方知っている人にとってはどう考えても代数的データ型の方が判りやすいと思いますが、もちろん※個人の感想です。λ計算の文法やセマンティクスの定義自体、代数的データ型とほとんど外見が同じなので FP アプローチでは写経するだけなので簡単なはずなのですが、もちろんこれは関数型好きな人の※個人の感想です。

OCaml の OO はオカシイと思われる方もいると思いますので Ruby でダックタイピングをふんだんに使って書いてみました。私の初 Ruby プログラムです!:

# values

class Vint
  def initialize(i)
    @int = i
  end
  attr_reader :int
end

class Closure
  def initialize(env, v, t)
    @env = env
    @var = v
    @term = t
  end

  def apply(v)
    env2 = @env.clone
    env2[@var] = v
    @term.eval(env2)
  end
end

class Vprim
  def initialize(prim, applied)
    @prim = prim
    @applied = applied
  end

  def apply(v)
    len = @applied.size
    arity = @prim.arity
    if arity <= len then
      raise
    else
      if arity == len + 1 then
        @prim.prim_eval(@applied + [v])
      else
        Vprim.new(@prim, @applied + [v])
      end
    end
  end
end

class Prim_add
  def initialize()
    @arity = 2
  end

  attr_reader :arity

  def prim_eval(vs)
    if vs.size == 2 then
      Vint.new(vs[0].int + vs[1].int)
    else
      raise
    end
  end
end

prim_add = Prim_add.new()
puts prim_add.prim_eval([Vint.new(1), Vint.new(2)]).int

class Prim_sub
  def initialize()
    @arity = 2
  end

  attr_reader :arity

  def prim_eval(vs)
    if vs.size == 2 then
      Vint.new(vs[0].int - vs[1].int)
    else
      raise
    end
  end
end

# terms

class Int
  def initialize(i)
    @i = i
  end

  def eval(_env)
    Vint.new(@i)
  end
end

class Var
  def initialize(v)
    @var = v
  end

  def eval(env)
    env[@var]
  end
end

class App
  def initialize(t1, t2)
    @t1 = t1
    @t2 = t2
  end

  def eval(env)
    v2 = @t2.eval(env)
    v1 = @t1.eval(env)
    v1.apply(v2)
  end
end

class Lambda
  def initialize(var, t)
    @var = var
    @term = t
  end

  def eval(env)
    Closure.new(env, @var, @term)
  end
end

class Add
  def eval(_env)
    Vprim.new(Prim_add.new, [])
  end
end

class Sub
  def eval(_env)
    Vprim.new(Prim_sub.new, [])
  end
end

# tools
def var(v)
  Var.new(v)
end

def int(i)
  Int.new(i)
end

def app(t1, t2)
  App.new(t1,t2)
end

def lambda(v, t)
  Lambda.new(v,t)
end

add = Add.new()
sub = Sub.new()

test = app(lambda("y", app(lambda("f", app(lambda("y", app(var("f"), int(2))), int(100))),
                           lambda("x", (app(app(add, var("x")), var("y")))))),
           int(2))

puts test.eval(Hash.new).int

Ruby では cons list がよく判らなかったので Hash を clone していますがまあやりたいことは大体書けています。 バイト数で OO にして型か書かれまくった OCaml コードの 9割位ですか。思ったより縮みませんね。 (行数で比べるほど心の狭い男ではありませんよ私は) まあ、もっと短くなるんでしょうけど、OCaml の OO アプローチは型がたくさん出てきて読みにくかったので書いてみただけで、言語disする目的ではないんでその辺はどうでもいいです。 動的なチェックは明示された動的なクラスチェック(OCaml 版では (Obj.magic e : t) に相当)がなくなり、 暗黙のダックタイピングに置き換わっています。このコードでは OCaml OO 判の影響を受けているので静的型付けの心理学に毒されていますね。真に静的型付け心理学から自由な Rubist ならば VInt と Int は Integer に、 Var は String にして eval メソッド追加してコード量を少し減らせます。私は※個人の感想として、そんなことしちゃあ絶対いけないと思うんですが。

比較してみましょう

客観的には明らかに FP の方が短い。短けりゃ偉いのか、という問は常にあるが。短い。 OO で(代数的データ型なしで)短く書くのはなかなか難しそうです。※個人の感想です

それ以外はもう Expression problem な〜 な感じで出尽くしていますねえ。 http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt

色々主観はあると思うんですが、餅は餅屋ですね。

プログラミング言語の抽象構文木のような、そもそも代数的に定義されている対象はやはり代数的データ型で書くのがよい。わざわざクラスで書く必要は無い

という当たり前な※個人の感想ですの再確認となりました。

そうなると自然と代数的な対象は、代数的データ型を標準装備し そのツールが揃ったた言語で書くのがよろしいという※個人の感想になります。それが、ごく、たまたま…関数型言語であった、そういう状態にあったと認識している、という※個人の感想。え？あなたの好きなOO言語には代数的データ型がある？んじゃそれ使えばいいんじゃないですか。※個人の感想です

そういう※個人の感想でした。