パターンマッチ実装奮闘記(12)

11回で終わる予定だったのですが、ソースが汚いです。
リファクタリングしなきゃいけない。と思ってリファクタリングを始めました。



## レジスタをRという名前にする

レジスタはIdという型名にしていたのですが、リファクタリングしていて
idの意味が複数出て来て分かりづらい事がわかったのでRとしました。
RはレジスタのRです。

## パターンマッチの箇所が特に長くて汚いので修正する

とにかく動けばいいという方針で作っていたので、パターンマッチの箇所は大分汚かったので、関数を作って呼んだり、無駄なネストを消したりしました。

## レジスタに型を持たせる

LL型がLLVMのアセンブラを表すケースクラス群だったのですが、タイプとレジスタを分けていました。しかし、型付きのアセンブラのレジスタには型がついている方がいいだろうということで、R型にはTを持たせてアセンブラの呼び出しにはR内に型を入れて呼び出すようにしました。

## ESwitchとEMatchを纏める

分割していたのですが、纏められそうだったので、纏めました。

## 実装

パーサのソースです。

```scala:
package chapter09

import util.parsing.combinator._
import util.parsing.input.Positional

object parser extends RegexParsers with PackratParsers {
  def p(e:PackratParser[E]) = positioned(e)
  def t(e:PackratParser[T]) = positioned(e)

  // skip C/C++ style comments and whitespace.
  override protected val whiteSpace = """((/\*(?:.|\r|\n)*?\*/)|//.*|\s+)+""".r

  lazy val id: PackratParser[String] = memo("""[A-Za-z_][\w_]*""".r)
  lazy val lng: PackratParser[E] = p(memo("""(0|[1-9][0-9]*)""".r  ^^ {case a => ELdc(Ti(32),a.toLong)}))
  lazy val tpl: PackratParser[E] = p(("(" ~> expr) ~ rep("," ~> expr) <~ ")" ^^ { case a~b => ETuple(Tn, a::b) })
  lazy val tpl2: PackratParser[List[E]] = ("(" ~> expr) ~ rep("," ~> expr) <~ ")" ^^ { case a~b => a::b }
  lazy val _val: PackratParser[E] = p(("val" ~> id)~ ("=" ~> lng) ^^ { case a~b => EVal(Ti(32),a,b)} |
    ("val" ~> id)~ (":" ~> id) ~ ("=" ~> id) ~ tpl2 ^^ { case a~t~id~ls => EVal(mkT(t),a,ETag(mkT(t),id,ls))} |
    ("val" ~> id)~ (":" ~> id) ~ ("=" ~> tpl) ^^ { case a~t~tpl => EVal(mkT(t),a,tpl)} |
    ("val" ~> id)~ (":" ~> id) ~ ("=" ~> expr) ^^ { case a~t~tpl => EVal(mkT(t),a,tpl)} |
    ("val" ~> id)~ (":" ~> id) ^^ { case a~t => EVal(mkT(t),a,null)})
  
  lazy val _id: PackratParser[E] = p(id ^^ { case a => EId(Tn, a)})

  def calc(op: String, op2:String):PackratParser[(E,E)=>E] = op ^^ {
    a => (a:E,b:E) => Op(op2)(Tn, a, b)
  }
  lazy val eq: PackratParser[E] = p(expr ~ rep( "=" ~> expr) ^^ {
    case a~b =>
      b.foldLeft(a){case (a,b) => EAssign(Ti(32), a, b)}})
  lazy val t1: PackratParser[E] = p(chainl1(eq,eq, calc("*","mul") | calc("/","div") | calc("%","mod")))
  lazy val term: PackratParser[E] = p(chainl1(t1, t1, calc("+","add") | calc("-","sub")))
  lazy val print: PackratParser[E] = p("print_i" ~> "(" ~> expr <~ ")" ^^ {case a => EPrint(Ti(32),a) })
  lazy val block: PackratParser[E] = p("{" ~> rep(expr) <~ "}" ^^ {case a => EBlock(Tv,a)})
  lazy val typ: PackratParser[T] = t(id ^^ {case a => mkT(a)})
  lazy val ctyps: PackratParser[List[(String,TStr)]] = rep((id <~ "(") ~ (typs <~ ")") ^^ { case a~b => (a,TStr(b))}) 
  lazy val typs: PackratParser[List[(String,T)]] = rep((id <~ ":") ~ typ ^^ { case a~b => (a,b)}) 
  lazy val typdef: PackratParser[E] = ("type" ~> id) ~ ("=" ~> "struct" ~> "{" ~> typs <~ "}") ^^ { case a~b => EType(TStr(b), a)} |
    ("type" ~> id) ~ ("=" ~> "enum" ~> "{" ~> ctyps <~ "}") ^^ { case a~b => EType(TVariant(b), a)}
  
  lazy val fields: PackratParser[E] = (id <~ ".") ~ id ^^ { case a~b => EField(Ti(32),a,b)}
  lazy val cases: PackratParser[List[(E,E)]] =  rep(("case" ~> ((lng^^ {case a=>ECase(Tn,a)})|tag)  <~ ":") | expr ) ^^ {case a:List[E] =>
    a.foldLeft(List[(E,E)]()){
      case (l,ECase(_,a)) => (a,EBlock(Tv,List()))::l
      case ((tag,EBlock(_,bls))::ls,a) => (tag,EBlock(Tv,bls:::List(a)))::ls
      case _ => throw new Exception("error")
    }.reverse
  }    
  lazy val switch: PackratParser[E] = ("switch" ~> "(" ~> expr <~ ")") ~ ("{" ~> cases <~ "}") ^^ {case a~b => ESwitch(Ti(32), a, b)} 
  lazy val tpl3: PackratParser[List[String]] = ("(" ~> id) ~ rep("," ~> id) <~ ")" ^^ { case a~b => a::b }
  lazy val tag: PackratParser[ECase] = id ~ tpl3 ^^ {case a~b => ECase(Tn,ETag(Tn,a,b.map{case a => EVal(Tn,a,null)}))}
  lazy val expr: PackratParser[E] = typdef | term | block | switch | print | lng | _val | fields | _id

  def mkT(a:String):T = {
    a match {
      case "Int" => Ti(32)
      case a => TDef(a)
    }
  }
}

object typing {
  
  def apply(e:E):E = {
    val r = f(e)
    env.map=Map()
    r
  }
  def add(id:String, t:T):T = {
    env.add(RL(t,id))
    t
  }
  def f(e:E):E = {
    e match {
      case e @ ELdc(Tn, i:Long) => e.copy(t=Ti(32))
      case e @ ELdc(t:T, i:Long) => e
      case e @ EBin(t:T, s:String, l:E, r:E) => val (l2,r2) = (f(l),f(r)); e.copy(t=l2.t, l=l2, r=r2)
      case e @ EPrint(t:T, a:E) => val a2 = f(a); e.copy(a2.t, a2)
      case e @ EBlock(t: T, ls: List[E]) => e.copy(ls=ls.map(f))
      case e @ EVal(Tn, id: String, a: E) => val a2 = f(a); e.copy(t=add(id,a.t), a=a2)
      case e @ EVal(t: T, id: String, null) => add(id,t); e 
      case e @ EVal(t: T, id: String, a: ETuple) => e.copy(t=add(id,t), a=f(a.copy(t=t))) 
      case e @ EVal(t: T, id: String, a: E) =>
        val a2 = f(a)
        if(env.stripT(a2.t) != env.stripT(t)) throw new Exception("error "+a2+" "+a2.t +" != "+t)
        e.copy(t=add(id,t), a=a2) 
      case e @ EId(t: T, id: String) => val r=env.map(id); e.copy(t=r.t)
      case e @ EAssign(t: T, a: E, b: E) => val a2 = f(a); val b2 = f(b); e.copy(a2.t, a2, b2)
      case e @ EField(Tn, id: String, idx: String) => val r = env.map(id); f(e.copy(t=r.t))
      case e @ EField(t: T, id: String, idx: String) =>
        t match {
          case t@TStr(ls) => val (idx2,tt) = T.find(t, idx); e.copy(t=tt)
          case t:TDef => env.stripT(t) match { case t:TDef => throw new Exception("type error "+t) case t => println(t); f(e.copy(t=t)) }
          case t => e
        }
      case e @ ETuple(t:T,ls:List[E]) => e.copy(ls=ls.map(f))
      case e @ ETag(t:T,id:String,ls:List[E]) => val r = env.map(id); e.copy(t=r.t,ls=ls.map(f) )
      case e @ ESwitch(t: T, d: E, cases:List[(E,E)] ) =>
        val d2 = f(d)
        val dt = env.stripT(d2.t)
        e.copy(
            a=d2,
            cases=cases.map{
              case (a@ETag(t,id,ls),b)=>
                val ls2 = env.findTag(dt.asInstanceOf[TVariant],id).types.zip(ls) map {
                  case ((_,t), e @ EVal(_,id2,_)) => add(id2,t); e.copy(t,id2)
                  case _ => throw new Exception("error")
                }
                (a.copy(t=dt,ls=ls2), f(b))
              case (a,b) => (a,f(b))
            })
      case e @ EUnit => e
      case e @ EType(t@TVariant(ls), id:String) => env.add(id, RR(t,null));for((tag,_)<-ls) env.add(tag, RR(t,null));  e
      case e @ EType(t:T, id:String) => env.add(id, RR(t, null)); e
      case e @ ECase(t:T, a:E) => f(a)
    }
  }
}

object parseTest {
    
  def main(args:Array[String]) {
    run("""{
        print_i(100+2*3)
        print_i(10)
        print_i(20)
    }""")
    run("""{
        val a = 10
        print_i(a)
        print_i(a+10*a)
    }""")
    
    // 構造体
    run("""{
        type SA = struct { a:Int b:Int }
        val c = 10
        val aa:SA
        aa.a = 9
        aa.b = c
        print_i(aa.a)
        print_i(aa.b)
    }""")
    // 構造体初期化リテラル
    run("""{
        type SA = struct { a:Int b:Int }
        val ab:SA = (123,456)
        print_i(ab.a)
        print_i(ab.b)
    }""")
    // ヴァリアント
    run("""{
        type Data = enum { A(a:Int) B(a:Int b:Int) }
        val data:Data
        val data2:Data = B(555,777)
    }""")
    run("""{
        // switch
        switch(2) {
        case 1: print_i(10001)
        case 2: print_i(10002)
        case 3: print_i(10003) print_i(10004)
        }
        print_i(1)
        switch(0) {
        case 1: print_i(10001)
        case 2: print_i(10002)
        case 3: print_i(10003)
        }
    }""")
    run("""{
        
        // alpha test
        val a = 1000
        print_i(a)
        val a:Int = a + 2000
        print_i(a)
        // alpha block test
        {
          val a = 5000
          print_i(a)
        }
        print_i(a)
    }""")
    run("""{
        type Data = enum { A(a:Int) B(a:Int b:Int) }
        val data2:Data = B(555,777)
        // match構文
        switch(data2) {
        case A(x) : print_i(x)
        case B(x,y) : print_i(x) print_i(y)
        }
        val data3:Data = A(333)
        switch(data3) {
        case A(x) : print_i(x)
        case B(x,y) : print_i(x) print_i(y)
        }
        val x = 10
        print_i(x)
    }""")
  }

  def run(src:String) {
    println("src="+src)
    val result = parser.parseAll(parser.block,src)
    if(!result.successful) {
      println(result)
      throw new Exception(result+"")
    }
    val ast = result.get
  
    env.map = Map("Int"->RR(Ti(32),null))
    println("ast="+ast)
    val ast2 = alpha(ast)
    val ast3 = typing(ast2)
    println("ast3="+ast3)
    val ll = kNormal(ast3)
    println("ll=" + ll)
    val ll2 = constFold(ll)
    emit("e.ll", ll2)
    println(exec("llc e.ll -o e.s"))
    println(exec("llvm-gcc -m64 e.s -o e"))
    println(exec("./e"))
  }
}
```