Scalaを思い出すために書いたミニミニLisp

Main.scala

// libraryDependencies += "org.scala-lang.modules" %% "scala-parser-combinators" % "1.1.2"
import scala.util.parsing.combinator._
import scala.collection.mutable._

sealed trait SExpr
case class Symbol(x: String) extends SExpr
case class IntLiteral(x: Int) extends SExpr
case class SList(xs: List[SExpr]) extends SExpr

sealed trait SValue
case class SymbolVal(x: String) extends SValue
case class IntVal(x: Int) extends SValue
case class FuncVal(f: List[SValue] => SValue) extends SValue
case class Cons(car: SValue, cdr: SValue) extends SValue
case object NilVal extends SValue

object Evaluator {
  val globalEnv: Map[String, SValue] = Map(
    "atom" -> FuncVal(_ match {
      case Cons(_, _) :: _ => NilVal
      case x :: Nil        => SymbolVal("t")
      case _               => sys.error("invalid argument")
    }),
    "eq" -> FuncVal(_ match {
      case x :: y :: Nil => if (x == y) SymbolVal("t") else NilVal
      case _             => sys.error("invalid argument")
    }),
    "car" -> FuncVal(_ match {
      case Cons(car, _) :: Nil => car
      case _                   => sys.error("invalid argument")
    }),
    "cdr" -> FuncVal(_ match {
      case Cons(_, cdr) :: Nil => cdr
      case _                   => sys.error("invalid argument")
    }),
    "cons" -> FuncVal(_ match {
      case x :: y :: Nil => Cons(x, y)
      case _             => sys.error("invalid argument")
    }),
    "nil" -> NilVal
  )
  def eval(e: SExpr, env: Map[String, SValue]): SValue = {
    e match {
      case Symbol(x)                                               => env.getOrElse(x, sys.error(s"$x is not defined"))
      case IntLiteral(x)                                           => IntVal(x)
      case SList(Symbol("define") :: Symbol(name) :: value :: Nil) => env.addOne((name, eval(value, env))); NilVal
      case SList(Symbol("lambda") :: SList(ps) :: body :: Nil) => {
        val params: List[String] = ps.map(_ match {
          case Symbol(x) => x
          case x         => sys.error(s"$x must be a symbol")
        })
        val newEnv = env.clone()
        FuncVal(as => {
          params.zip(as).foreach(newEnv.addOne _)
          eval(body, newEnv)
        })
      }
      case SList(x :: xs) =>
        eval(x, env) match {
          case FuncVal(f) => f(xs.map(eval(_, env)))
          case x          => sys.error(s"$x is not function or special form")
        }
      case SList(Nil) => sys.error("empty list")
    }
  }
}

class LispParser extends RegexParsers {
  def symbol: Parser[SExpr] = """[A-Za-z_][A-Za-z0-9!]*""".r ^^ Symbol
  def intLiteral: Parser[SExpr] = """[1-9][0-9]*|0""".r ^^ (x => IntLiteral(x.toInt))
  def slist: Parser[SExpr] = "(" ~ rep(expr) ~ ")" ^^ (_ match { case (_ ~ xs ~ _) => SList(xs) })
  def expr: Parser[SExpr] = slist | symbol | intLiteral
}

object Tester extends LispParser {
  def run() = {
    assert(eval("42"))
    assert(eval("(atom 1)"))
    assert(eval("(eq 1 1)"))
    assert(eval("(eq 1 2)"))
    assert(eval("(eq (atom 1) (atom 2))"))
    assert(eval("(cons 1 (cons 2 nil))"))
    assert(eval("(define x 1)"))
    assert(eval("(eq x 1)"))
    assert(eval("(define id (lambda (x) x))"))
    assert(eval("(id 42)"))
    assert(eval("x"))
  }

  def eval(src: String): Boolean = parse(expr, src) match {
    case Success(result, next) => println(Evaluator.eval(result, Evaluator.globalEnv)); true
    case e                     => println(e); false
  }
}
object Main extends App {
  Tester.run()
}