第10章 型とクラスの定義 #4
10.5 仮想マシン
二つ目の長い例題として、整数と加算演算子からなる単純な数式の型と、この数式を評価して整数にする関数を考えよう。
data Expr = Val Int | Add Expr Expr value :: Expr -> Int value (Val n) = n value (Add x y) = value x + value y
で、式 (2+3)+4 をこのデータ型を使って表すと、Add (Add (Val 2) (Val 3)) (Val 4)となる。図にすると下のような感じ。
[f:id:matarillo:20120223232540p:image:w200]
図を書いたときにあらためて気づいたけど、データ型って値型じゃなくて参照型なんだよな。
さて、ここまでなら何て事ないんだけど……
関数
valueの定義は、加算演算子の左の引数を右の引数よりも先に評価すると指定している訳ではない。さらに一般的に、どの時点でも次に何をすべきかを指定している訳ではない。評価の順番はHaskellの処理系が決める。
ふむふむ。
しかし望むのであれば、数式を処理する仮想マシンを定義することで、処理の順番を指示できる。 それを実現するために、仮想マシンを制御するスタックの型を宣言しよう。
はい？
で、ここから教科書は仮想マシンの話に突入するのだが、図がなくてちょっとわかりにくかったので、自分の理解のために図を書いてみた（これ、Haskellの勉強から外れるよなあ）。
まず、この仮想マシンは基本的には加算しかしないので、加算用のレジスタと、加算命令を保持するスタックを想定する。加算命令はADD nの形で、加算レジスタにnを足すという動きをする。
[f:id:matarillo:20120223232541p:image:w200]
こんな仮想マシンで(((1+2)+3)+4)+5を計算する様子が下の図だ。スタックに積んである加算命令を次々に実行した結果、15が得られる。
[f:id:matarillo:20120223232542p:image:w400]
ただし計算したい数式はこんな風に左から足していけばいいわけじゃない。木構造になる。そうすると、ADD n命令は足す数が分かっている場合にしか使えないので困ってしまう。
そこで命令とレジスタを増やす。評価用のレジスタと、評価命令だ。
[f:id:matarillo:20120223232543p:image:w200]
命令スタックの中にEVAL命令が含まれていた場合の命令実行イメージはこのような流れだ。
[f:id:matarillo:20120223232544p:image:w400]
まずはADD 2を実行して、加算レジスタが3になる。次の命令がEVAL xだったとする（xの中身はExpr型のデータ）。xを評価して、その結果を足したい。そこで、xは評価レジスタに置き、加算レジスタにあった3という値をADD 3命令に変えてスタックに積み、加算モードから評価モードに切り替える。
評価モードの動作は後で説明するとして、まあ結果的にxを評価した値が3だったとする。評価結果が出た場合はその値を加算レジスタに置き、再度スタック上の加算命令を順に実行していく。
ここまでの流れが理解できれば、評価命令の動作は簡単だ。
評価する式がVal nだったら、評価結果はnだ。評価モードを終了して加算モードに移行する。
[f:id:matarillo:20120223232545p:image:w300]
評価する式がAdd x yだったら、yは後で評価して足すのでスタックにEVAL yを積んで、評価レジスタにはxを置き、再度評価する。
[f:id:matarillo:20120223232546p:image:w300]
というわけで、最初の数式 (2+3)+4 がどう評価されて加算されていくかを見てみよう。
[f:id:matarillo:20120223232540p:image:w200]
[f:id:matarillo:20120223232547p:image:w600]
計算の順番が、当初の想定通りに2→3→2+3=5→4→4+5=9となっているのが分かる。
で、コードはこれ。EVALを実行する関数evalの引数は評価レジスタとスタックで、スタックに積まれた命令を実行しながら加算処理をする関数execの引数はスタックと加算レジスタだ。
data Expr = Val Int | Add Expr Expr type Cont = [Op] data Op = EVAL Expr | ADD Int eval :: Expr -> Cont -> Int eval (Val n) c = exec c n eval (Add x y) c = eval x (EVAL y:c) exec :: Cont -> Int -> Int exec [] n = n exec (EVAL y:c) n = eval y (ADD n:c) exec (ADD n:c) m = exec c (n + m) value :: Expr -> Int value e = eval e []
