スタックをListで表すと分かりやすいよって話

とりあえず、スタックマシンの説明を書いてみます。

スタックマシンの説明

スタックマシンとは以下のような規則でスタックを操作する事で計算する事が出来ます。

①プログラムのコードがpush nならスタックに1を積みます。
②コードがaddならスタックから値を２つ取り出して足した値をスタックに積みます。

では、以下の状態のスタックマシンを動かしてみましょう。

スタック	プログラムコード
	push 1 push 2 add

まず、プログラムにpush 1と書いてあるので規則①を適用してスタックに１を積みます。

スタック	プログラムコード
1	push 2 add

次は、プログラムにpush 2と書いてあるので、規則①を適用してスタックに2を積みます。

スタック	プログラムコード
2 1	add

次は、プログラムにaddって書いてあるので、規則②を適用してスタックから2つ取り出し足してスタックに入れます。2と1をとりだして、2+1=3なので3を入れるわけです。

スタック	プログラムコード
3

プログラムはなくなったので、計算は終了です。1+2の計算ができました。

横に倒す

このように書くのも良いのですが、このスタックを横に倒して、評価方法も図で書いてみます。

スタックマシンの処理

評価前のスタック	評価前のプログラムコード		評価後のスタック	評価後のプログラムコード
s	push n c	→	n s	c
a b s	add c	→	a+b n s	c

スタックマシンは以下のように遷移します。

スタック	プログラムコード
	push 1 push 2 add
1	push 2 add
2 1	add
3

このように書くと分かりやすいと思うのですがいかがでしょうか？

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