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

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

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

スタックマシンの説明

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

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

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

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

まず、プログラムにpush 1と書いてあるので規則①を適用してスタックに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 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

FSharp

module Test.Main

open System

type E = Add | Push of int

let rec step = function
    | a::s,[] -> a
    | a::b::s,Add::c -> step((a+b)::s, c)
    | s,Push(i)::c -> step(i::s, c)
    | _ -> -1

[<EntryPoint>]
let main args = 
    (step ([], [ Push(1); Push(2); Add ])) |> Console.WriteLine
    0

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

状態遷移マシンと末尾再帰最適化

関数型言語でスタックマシンを書いてみました。スタックマシンのような末尾再帰で書かれている状態が変わって行くプログラムを状態遷移マシンといいます。

複数の状態を持ったマシンが、状態を変化させながら動いて行くというものが状態遷移マシンです。

例えば、factの計算を書いてみます。

def fact(n:Int):Int = if(n == 1) 1 else n * fact(n - 1)

と書けますが、これは末尾再帰にはなっていません。

これを状態遷移マシンに書き換える事で、末尾再帰にしてみます。

def fact(n:Int):Int = {
    def f(n:Int, ans:Int):Int = {
        if(n==0) ans else f(n-1, n * ans)
    }
    f(n, 1)
}

と書き換える事が出来ます。

末尾再帰最適化するということは、状態を全て関数の引数にするということなのです。処理系のスタックに保存していた状態を、関数の引数にすることでただのループに出来る訳です。

状態がもの凄くたくさんある場合

もの凄く状態が多いと、困ってしまいます。 たとえば、コマンドラインオプションをパースする関数を末尾再帰最適化して書いてみます。

object test {

    def opt(args:List[String], a:Boolean, b:String, c:Boolean):
        (Boolean, String, Boolean) = {
        (args,a,b,c) match {
        case (List(),a,b,c) => (a,b,c)
        case ("-a"::args,a,b,c) => opt(args,true,b,c)
        case ("-b"::name::args,a,b,c) => opt(args,a,name,c)
        case ("-c"::args,a,b,c) => opt(args,a,b,false)
        case (n::args,a,b,c) => throw new Exception("usage: [-a|-b name|-c]")
        }
    }

    def main(args:Array[String]) {
        println(opt(args.toList,false,"",true))
    }
}

これは、オプションとして、-a,-b,-cが使えるという物で、aとbのデフォルトはfalseで、cのデフォルトがtrueです。というプログラムですが、引数がだんだん大きくなって困りそうです。 こういう場合は、scalaだとcopyとかいうのを使うといい感じに書けます。 SML#の#はscalaのcopyです。

object test {
    case class Opt(a:Boolean=false,b:String="",c:Boolean=true)

    def opt(args:List[String], o:Opt):Opt = {
        args match {
        case List() => o
        case "-a"::args => opt(args, o.copy(a=true))
        case "-b"::name::args => opt(args, o.copy(b=name))
        case "-c"::args => opt(args, o.copy(c=false))
        case n::args => throw new Exception("usage: [-a|-b|-c]")
        }
    }

    def main(args:Array[String]) {
        println(opt(args.toList,Opt()))
    }
}

こんな感じに書いておけば、いくら、オプションが増えても安心ですし、 デフォルト引数を指定する事で、デフォルト値も記述出来てよいです。