型推論が出来たなら

型推論が出来るようになったら、もうバラ色である。
型を持った、コンパイラが作れるわけだ。
Lisp級マクロが当然のように動く。
実装は美しく簡単で、解説も書いてある。
型推論があるので、プログラムはスッキリ書ける。
型推論が分かったので、C++やScalaのテンプレートの型変数を省略の検討をする。
そして、パターンマッチング構文を入れる。GCを導入する。
そのGCを使ったLLを作る。

そんな夢を見て、元気を出す。元気を出して、次につなげる。
で、その言語で何作るのかって？
もう忘れた。
JVMのようなものも作れるよな。
iPhoneのアプリを作ったりも出来るだろう。
うーん。夢は広がる。
大変だけど、頑張ろう。あと少し。あと少しで素晴らしい世界が開ける。
あと少しだ。いつも、つめが甘いけど、これだけはつめていこう。
きっちり作り上げよう。

俺なら出来る。俺ならやれる。型推論なんて簡単さ。型推論なんてちょろいもんさ。
一度失敗して、ビビってしまったけど、大丈夫。俺ならやれる。絶対出来る。

まず、熱い思いを取り戻そう。夢中になってしまえばこっちの物なのだから。
型推論が出来るってことはもの凄い事なんだ。
よく知られている、型推論付きのC言語レベルの言語はないからね。
Lisp級のマクロがC言語レベルの言語で動くってこともまた凄い事だ。
俺は凄い。凄い人なんだ。だから、頑張れ！

多くの人が、多くの事を教えてくれたから出来る事なんだ。
自分一人で作り上げた訳ではない。
感謝の気持ちを忘れちゃいけない。

さぁ、基本から徐々に、焦らずにゆっくりと、進めよう。やれる。
ということで、住井さんの型推論の実装方法を見て、Scalaに移植してみました。

http://itpro.nikkeibp.co.jp/article/COLUMN/20070717/277580/

参照の移植に悩んだのと、List.assocを自作したくらいであとは、移植しただけです。
上から順番に作って行って、最後にunifyでちゃんとチェックするって感じだったので
かなり楽だったように思います。ただ、参照を正しく実現出来てるか微妙なので、
間違えているかも知れません。

とにかく、ちょっとだけ進んだのでよかったです。
unifyのあたりから飛ばして読んでしまってるのでちゃんと理解出来てない。情けない。

sealed trait Exp
case class Const(a:Int) extends Exp
case class Var(a:String) extends Exp
case class Add(a:Exp,b:Exp) extends Exp
case class Let(a:String,b:Exp,c:Exp) extends Exp
case class Fun(a:String,c:Exp) extends Exp
case class App(a:Exp,b:Exp) extends Exp

sealed trait Typ
case class TInt() extends Typ
case class TFun(a:Typ,b:Typ) extends Typ
case class TVar(var t:Option[Typ]) extends Typ

object tes {

  def main(argv:Array[String]) {
    println(infer(List(),Const(3)))
    println(find(List("a" -> TInt(),"b"->TFun(TInt(),TInt())), "b"))
    println(infer(List("a" -> TInt(),"b"->TFun(TInt(),TInt())), Var("b")))
  }

  def infer(tenv:List[(String,Typ)], e:Exp):Typ = {
   e match {
     case Const(_) => TInt()
     case Var(x) => find(tenv, x)
     case Add(x, y) =>
       unify(infer(tenv, x), TInt())
       unify(infer(tenv, y), TInt())
       TInt()
     case Let(x,e1,e2) =>
       val t = infer(tenv, e1)
       val newtenv = (x, t) :: tenv
       infer(newtenv, e2)
     case Fun(x, e0) =>
       val t1 = TVar(None)
       val newtenv = (x, t1)::tenv
       val t2 = infer(newtenv, e0)
       TFun(t1, t2)
     case App(e1, e2) =>
       val t1 = infer(tenv, e1)
       val t2 = infer(tenv, e2)
       val t = TVar(None)
       unify(t1, TFun(t2, t))
       t
     case _ => TVar(None)
   }
  }

  def unify(t1:Typ, t2:Typ) {
    (t1, t2) match {
      case (TInt(), TInt()) =>
      case (TFun(t11,t12), TFun(t21, t22)) =>
        unify(t11, t21)
        unify(t12, t22)
      case (TVar(r1), TVar(r2)) if (r1 == r2) =>
      case (r@TVar(r1), _) if (!occur(r1, t2)) =>
        // t1はt2の中に現われない型変数
        r1 match {
        case None => // t1は未定
          r.t = Some(t2) // t1にt2を代入
        case Some(t1d) => // すでにt1'が代入されている
          unify(t1d, t2) // t1'とt2を等しくする
        }
      case (_, TVar(r2)) => // t2が型変数
        unify(t2, t1) // t1とt2を入れ替えてunify
      case (_, _) => // 上述以外の場合
        throw new Exception("Type Error") // 型エラーを表す例外を発生
    }
  }

  def occur(r1:Option[Typ], t2:Typ):Boolean = {
    t2 match {
      case TInt() => false
      case TFun(t21, t22) => occur(r1, t21) || occur(r1, t22)
      case TVar(r2) => (r1 == r2) || (r2 match {
          case None => false
          case Some(t2d) => occur(r1, t2d)
        })
    }
  }

  def find(env:List[(String,Typ)], x:String):Typ = {
    env match {
      case List() => throw new Exception("error")
      case (`x`, t)::xs => t
      case _::xs => find(xs, x)
    }
  }

}