SML#勉強会で末尾再帰最適化が分かった！

東北大で大堀先生の話が聞けるので行ってみてます。
入門な感じなので簡単なんじゃないかと思ってたのですけど、
関数型言語の授業を受けた事がないので絶好の機会なので楽しみにしてます。

今回の授業では、末尾再帰最適化の話がありました。
実は複雑な末尾再帰最適化は良くわかってなかったのですが、
状態遷移マシンとして考えると良いと言う話を聞いて理解してしまいました。
なるほど！secdマシンみたいに書けば良いんだ！と。

ということで、末尾再帰最適化した、パーサを作ってみました。
適当だけど、それっぽく動きます。

object p {
  def main(argv:Array[String]) {
    println(parse("a = b = - [ i ++ + 2 * 3 + add [ 1 ] ] a = 2 if { a } b c if { } a ; [ ] a [ ]"))
  }
  var ins = Map[Any,Int] ("*"->2,"/"->2,"-"->1,"+"->1)
  var inrs = Map[Any,Int] ("="->0)
  var pres = Map[Any, Int] ("-"->3)
  var prns = Map[Any,String] ("("->")","{"->"}","["->"]")
  var psts = Map[Any, Int] ("++"->4,"--"->4,";"->4)
  var sts  = Map[Any,Int] (
    ("if","{")->2
  )
  def find(m:Map[Any,Int], i:Any):Int = {
    if(m.contains(i)) m(i)
    else -1
  }
  def parse(src:String):Any = {
   f(List(),null, src.split(" ").toList, 0)
  }
  def eat(expected:Any, token:Any):Any = {
    if(expected != token)
      throw new Exception("error. expected is "+expected + " but found "+token);
    token
  }

  def f(s:List[Any],e:Any,c:List[Any],p:Int):Any = (s,e,c,p) match {
  case (s, null, a::b::c, p) if prns.contains(a) && prns(a) == b => f(s, (a,"void",b), c, p)
  case (s, null, op::c, p) if prns.contains(op) => f(("prn",op,p,prns(op))::s, null, c, 0)
  case (s, null, op::c, p) if p < find(pres,op) => f(("pre",op,p)::s, null, c, pres(op))
  case (s, null, a::o::r::c, p) if p < find(sts,(a,o)) && prns(o)==r =>
    f(("sts2",a,o,"void",r)::s, null, c, 0)
  case (s, null, a::b::c, p) if sts.contains(a,b) => f(("sts",a,b,p,prns(b))::s, null, c, 0)
  case (s, null, t::c, p) => f(s, t, c, p)
  case (s, e, op::c, p) if p < find(ins, op) => f(("in",e,op,p)::s, null, c, ins(op))
  case (s, e, op::c, p) if p <= find(inrs, op) => f(("in",e,op,p)::s, null, c, inrs(op))
  case (s, e, op::c, p) if p <= find(psts,op) => f(s, (e,op), c, p)
  case (s, e, a::b::c, p) if prns.contains(a) && prns(a) == b  => f(s, (e,a,"void",b), c, p)
  case (s, e, op::c, p) if prns.contains(op) => f(("msg",e,op,p,prns(op))::s, null, c, 0)

  case (("in",a,op,(p:Int))::s, e, c, _) => f(s, (a,op,e), c, p)
  case (("pre",op,(p:Int))::s, e, c, _) => f(s, (op,e), c, p)
  case (("prn",op,(p:Int),rp)::s, e, r::c, _) => f(s, (op, e, eat(rp, r)), c, p)
  case (("msg",a,op,(p:Int),rp)::s, e, r::c, _) => f(s, (a,op,e,eat(rp,r)), c, p)
  case (("sts",a,op,(p:Int),rp)::s, e, r::c, _) => f(("sts2", a, op, e, eat(rp,r))::s, null, c, p)
  case (("sts2",a,op, b, rp)::s, e, c, _) => f(s, (a,op,b,rp,e), c, 0)
  case (("@", a)::s, e, c, p) => f(s,(a,"@",e), c, p)

  case (s, e, List(), p) => e
  case (s, null, c, p) => throw new Exception("state error "+(s,null,c,p))
  case (s, e, c, p) => f(("@", e)::s, null, c, 0)
  }
}

ところで、自作のスタックとVMのコールスタックとどっちが速いのかな？
って言う話で、VMのスタックの方が速いかもしれないのだけど、テスト作るの面倒いから良いやっていう。。。

1+1+1+1+...........で1000個、10000個と増やしてテストすればいいんですよね。テストすれば。

ということで、テストしたら、やっぱり、JVMのスタックを使ってる方が10%くらい速いようでした。
ぬー。いや、でも良い勉強になりました。