Haskellの評価戦略を作ったよ

Haskellの評価を書いたのに基づいて、純粋関数型言語の評価戦略を書いてみました。若干、胡散臭い部分がありますが、少なくとも Wiki に書いたのは動いています。無限リスト(repeat)もちゃんと扱えています。

object Haskell extends Application {
  // 構文に出てくるノード
  abstract class Expr
  case class Symbol(name:String) extends Expr
  case class Lambda(left:List[Symbol], right:List[AnyRef]) extends Expr
  abstract class Statement
  case class Equation(left:List[Symbol], right:List[AnyRef]) extends Statement
  // 短縮表記用の関数
  def S (name:String) = new Symbol(name)
  def L (l:List[Symbol], r:List[AnyRef]) = new Lambda(l, r)
  def EQ(l:List[Symbol], r:List[AnyRef]) = new Equation(l, r)
  // 定義済みの式
  val eqs = List(
      // cons x y = \f -> f x y
      EQ(List(S("cons"), S("x"), S("y")), 
          List(L(List(S("f")), List(S("f"), S("x"), S("y"))))),
      // car  l   = l (\x y -> x)
      EQ(List(S("car"), S("l")),
          List(S("l"), L(List(S("x"), S("y")), List(S("x"))))),
      // repeat x = cons x (repeat x)
      EQ(List(S("repeat"), S("x")),
          List[AnyRef](S("cons"), S("x"), List(S("repeat"), S("x")))))
  
  // car (repeat X) を評価し、X が返ってくる
  println("final = " + eval(List(S("car"), List(S("repeat"), S("X"))))(0))
  // car (cons X Y) を評価し、X が返ってくる
  println("final = " + eval(List(S("car"), List(S("cons"), S("X"), S("Y"))))(0))
  
  // 評価（式変形）を行う
  def eval(e:List[AnyRef]):List[AnyRef] = {
    println("e = " + e)
    // 関数を適用する
    val eq = eqs.find(isMatch(_, e))
    if(eq.isDefined)
      return eval(replace(e, eq.get.left.tail, eq.get.right))
    // ラムダ式を評価する
    e(0) match {
      case lb:Lambda if(e.size >= 2) =>
        return eval(replace(e, lb.left, lb.right))
      case _ =>
    }
    // 引数の評価
    for(i <- 0 until e.length) {
      if(e(i).isInstanceOf[List[AnyRef]]) {
        val ei = eval(e(i).asInstanceOf[List[AnyRef]])
        return eval(List.concat(e.take(i),
            if(ei.size == 1) List(ei(0)) else ei,
            e.drop(i+1)))
      }
    }
    return e
  }
  
  // 式変形
  def replace(expr:List[AnyRef], left:List[Symbol], right:List[AnyRef]):List[AnyRef] = {
    // 変数名 -> 値
    val map = Map(left.zip(expr.tail):_*)
    // 右辺を置換
    def rep(right:List[AnyRef]):List[AnyRef] = 
      right.map(_ match {
        case s:Symbol => 
          if(map.contains(s)) map(s) else s
        case l:List[AnyRef] => 
          rep(l)
        case lb:Lambda =>
          L(rep(lb.left).asInstanceOf[List[Symbol]], rep(lb.right))
      })
    return List.concat(rep(right), expr.drop(left.length + 1))
  }
  
  def isMatch(eq:Equation, expr:List[AnyRef]):boolean =
    eq.left(0) == expr(0) && eq.left.size <= expr.size
}