スタックマシン
OCamlではリストでスタックを表しパターンマッチで奇麗にスタックマシンを書く事が出来ます。
let rec eval (s,c) = match (s,c) with | `I a::`I b::s,`O "+"::c -> eval (`I(a+b)::s, c) | `I a::`I b::s,`O "-"::c -> eval (`I(a-b)::s, c) | `I a::`I b::s,`O "*"::c -> eval (`I(a*b)::s, c) | `I a::`I b::s,`O "/"::c -> eval (`I(a/b)::s, c) | s, `I a::c -> eval ( `I a::s, c) | `I a::s, c -> a | _ -> assert false let _ = Printf.printf "%d\n" (eval([], [`I 1; `I 2; `O "+"])); Printf.printf "%d\n" (eval([], [`I 1; `I 2; `O "+"; `I 3; `O "*"]))
実行結果:
3 9
です。
このプログラムの構造は関数の末尾で必ず値を返すか、関数呼び出しを行っています。
このようなプログラムは多くの関数型言語では末尾再帰最適化が行われます。
末尾再帰最適化とは、関数の最後の関数呼び出しをジャンプ命令に変換する最適化です。
要するにこのプログラムは再帰的な関数ですが、実は只のループとみなす事が出来ます。
只のループとしてみた場合に、引数SやCは状態を表す変数としてみなせます。
このプログラムはどのように動くか見てみましょう。
| S | |||||
| C | 1 | 2 | + | 3 | * |
Cに1があったら、Sに入れます。
| S | 1 | |||
| C | 2 | + | 3 | * |
Cに2があったら、Sに入れます。
| S | 1 | 2 | |
| C | + | 3 | * |
Cに+があったら、Sから値を2つ取り出して1と2を足し合わせた3をSに入れます。
| S | 3 | |
| C | 3 | * |
Cの3をSに入れます。
| S | 3 | 3 |
| C | * |
Cに*があったので、Sから値を2つ取り出して、3と3をかけた9をSに入れます。
| S | 9 |
| C |
答え9です。
このような構造は1964年にP.J.Landinによって作られたLISPの為の仮想マシンであるSECDマシンで採用されています。
SECDマシンは多くの仮想マシンに影響を与えている有名な仮想マシンです。
64年っていう事はSECDマシンはちょうど半世紀前に産まれたんですね。
60年にLISPが誕生しているので殆どLISPが産まれてすぐに出来たと言ってよいでしょう。
P.J. Landin, ”The Mechanical Evaluation of Expressions”, The Computer Journal, 6:308–320, 1964
