Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Scalaを思い出すために書いたミニミニLisp
// 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()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.