とりあえず、スタックマシンの説明を書いてみます。
スタックマシンの説明
スタックマシンとは以下のような規則でスタックを操作する事で計算する事が出来ます。
①プログラムのコードがpush nならスタックに1を積みます。
②コードがaddならスタックから値を２つ取り出して足した値をスタックに積みます。
では、以下の状態のスタックマシンを動かしてみましょう。
まず、プログラムにpush 1と書いてあるので規則①を適用してスタックに１を積みます。
次は、プログラムにpush 2と書いてあるので、規則①を適用してスタックに2を積みます。
次は、プログラムにaddって書いてあるので、規則②を適用してスタックから2つ取り出し足してスタックに入れます。2と1をとりだして、2+1=3なので3を入れるわけです。
プログラムはなくなったので、計算は終了です。1+2の計算ができました。
横に倒す
このように書くのも良いのですが、このスタックを横に倒して、評価方法も図で書いてみます。
スタックマシンの処理
| 評価前のスタック |
評価前のプログラムコード |
|
評価後のスタック |
評価後のプログラムコード |
|
|
→ |
|
|
|
|
→ |
|
|
スタックマシンは以下のように遷移します。
このように書くと分かりやすいと思うのですがいかがでしょうか？
SML
さらに、関数型言語で書けばスタックマシンが見たままのイメージで書く事が出来ます。
datatype Code = Add | Push of int
fun step(a::s,[]) = a
| step(s,(Push(n))::c) = step(n::s, c)
| step(a::b::s, Add::c) = step((a+b)::s,c)
| step(a,b) = 0
val n = step([], [Push(1),Push(2),Add]);
print (Int.toString(n) ^ "\n")
ステップを追って書くと以下のようになります。
step([],[Push(1),Push(2),Add])
step([1],[Push(2),Add])
step([2,1],[Add])
step([3],[])
3
Scala
Scalaで書くと以下のようになります。
object test extends App {
def step(s: List[Int], c: List[Any]): Int = {
println("step " + (s,c));
(s,c) match {
case (a::s,List()) => a
case (s,("push", n:Int)::c) => step(n::s, c)
case (a::b::s,"add"::c) => step((a+b)::s, c)
case _ => 0
}
}
println(step(List(),List(("push",1),("push",2),"add")))
}
出力結果は以下のようになります。
step (List(),List((push,1), (push,2), add))
step (List(1),List((push,2), add))
step (List(2, 1),List(add))
step (List(3),List())
3
