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


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

## スタックマシンの説明

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

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

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

<table border="0px">
	<tr>
		<td>スタック</td>
		<td>プログラムコード</td>
	</tr>
	<tr>
		<td valign="bottom">
			<table width="200px">
			</table>
		</td>
		<td valign="bottom">
			<table width="200px">
				<tr><td>push 1</td></tr>
				<tr><td>push 2</td></tr>
				<tr><td>add</td></tr>
			</table>
		</td>
	</tr>
</table>


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

<table border="0px">
	<tr>
		<td>スタック</td>
		<td>プログラムコード</td>
	</tr>
	<tr>
		<td valign="bottom">
			<table width="200px">
				<tr><td>1</td></tr>
			</table>
		</td>
		<td valign="bottom">
			<table width="200px">
				<tr><td>push 2</td></tr>
				<tr><td>add</td></tr>
			</table>
		</td>
	</tr>
</table>


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

<table border="0px">
	<tr>
		<td>スタック</td>
		<td>プログラムコード</td>
	</tr>
	<tr>
		<td valign="bottom">
			<table width="200px">
				<tr><td>2</td></tr>
				<tr><td>1</td></tr>
			</table>
		</td>
		<td valign="bottom">
			<table width="200px">
				<tr><td>add</td></tr>
			</table>
		</td>
	</tr>
</table>

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

<table border="0px">
	<tr>
		<td>スタック</td>
		<td>プログラムコード</td>
	</tr>
	<tr>
		<td valign="bottom">
			<table width="200px">
				<tr><td>3</td></tr>
			</table>
		</td>
		<td valign="bottom">
			<table width="200px">
			</table>
		</td>
	</tr>
</table>

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

## 横に倒す

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

<table width="100%">
	<caption>スタックマシンの処理</caption>
		<tr>
			<td width="24%">評価前のスタック</td>
			<td width="24%">評価前のプログラムコード</td>
			<td width="4%"></td>
			<td width="24%">評価後のスタック</td>
			<td width="24%">評価後のプログラムコード</td>
		</tr>
		<tr>
			<td align="right"><table><tr>
				<td>s</td>
			</tr></table></td>
			<td align="right"><table><tr>
				<td>push n</td>
				<td>c</td>
			</table></td>
			<td>→</td>
			<td align="right"><table><tr>
				<td>n</td>
				<td>s</td>
			</tr></table></td>
			<td align="right"><table><tr>
				<td>c</td>
			</tr></table></td>
		</tr>
		<tr>
			<td align="right"><table><tr>
				<td>a</td>
				<td>b</td>
				<td>s</td>
			</tr></table></td>
			<td align="right"><table><tr>
				<td>add</td>
				<td>c</td>
			</table></td>
			<td>→</td>
			<td align="right"><table><tr>
				<td>a+b</td>
				<td>n</td>
				<td>s</td>
			</tr></table></td>
			<td align="right"><table><tr>
				<td>c</td>
			</tr></table></td>
		</tr>
	</table>

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

<table border="0px"  width="60%">
	<tr>
		<td width="50%">スタック</td>
		<td width="50%">プログラムコード</td>
	</tr>
	<tr>
		<td align="right">
			<table>
				<tr>
				</tr>
			</table>
		</td>
		<td align="right">
			<table>
				<tr>
					<td>push 1</td>
					<td>push 2</td>
					<td>add</td>
			</table>
		</td>
	</tr>
	<tr>
		<td align="right">
			<table>
				<tr>
					<td>1</td>
				</tr>
			</table>
		</td>
		<td align="right">
			<table>
				<tr>
					<td>push 2</td>
					<td>add</td>
			</table>
		</td>
	</tr>
	<tr>
		<td align="right">
			<table>
				<tr>
					<td>2</td>
					<td>1</td>
				</tr>
			</table>
		</td>
		<td align="right">
			<table>
				<tr>
					<td>add</td>
			</table>
		</td>
	</tr>
	<tr>
		<td align="right">
			<table>
				<tr>
					<td>3</td>
				</tr>
			</table>
		</td>
		<td align="right">
			<table>
				<tr></tr>
			</table>
		</td>
	</tr>
</table>

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

# SML

さらに、関数型言語で書けばスタックマシンが見たままのイメージで書く事が出来ます。

```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で書くと以下のようになります。

```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