Inspired by [cached]Peter Norvig's lispy, I wrote a little Lisp interpreter in Scala. So far, it only provides a small subset of Lisp, but I plan to extend it eventually.
It makes heavy use of Scala's parser-combinators to build the AST (abstract syntax tree), execution is little more than calling "eval" on this tree.
Here's what the main parser looks like:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class LispParser extends JavaTokenParsers {
def expression: Parser[Expression] = (
"("~>expressionBody<~")" | number | string | variable )
def expressionBody: Parser[Expression] = ( "quote"~>expression
| "if"~expression~expression~expression ^^ {
case "if"~cond~thn~els => If(cond, thn, els) }
| "set!"~variable~expression ^^ { case "set!"~v~e => Set(v.name, e) }
| "define"~variable~expression ^^ { case "define"~v~e => Define(v.name, e) }
| "lambda"~"("~rep(variable)~")"~expression ^^ {
case "lambda"~"("~args~")"~exp => Lambda(args, exp) }
| "begin"~rep(expression) ^^ { case "begin"~exps => ExpressionList(exps) }
| variable~rep(expression) ^^ { case name~params => Procedure(name, params)})
def number: Parser[Number] = floatingPointNumber ^^ (n => Number(n.toDouble))
def string: Parser[Text] = "\""~>"[^\"]*".r<~"\"" ^^ (s => Text(s))
def variable: Parser[Variable] = """[A-Za-z\+\-\<\>\=\*][A-Za-z0-9_]*""".r ^^ (n => Variable(n))
}
|
To store the tree, Scala's case classes are very convenient, here's the if-expression as an example (the others are quite similar):
| abstract class Expression { def eval(env: Env): (Seq[Any]) => Any }
case class If(cond: Expression, thn: Expression, els: Expression) extends Expression {
override def eval(env: Env) = cond.eval(env)(List()) match {
case r: Boolean => if(r) thn.eval(env) else els.eval(env)
case _ => els.eval(env)
}
}
|
If you look back to the first listing, you can see that the If class is created in 6. The funny (Seq[Any]) => Any business is a result of how I've implemented lamda-expressions - right now everything is a function, even primitive values. For example, a number is a function that takes zero arguments and returns the value of the number.
If you run the program itself you'll get a primitive REPL where you can evaluate expressions, like factorials or fibonacci numbers:
| >>> (define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1))))))
()
>>> (fact 10)
3628800.0
>>> (define fib (lambda (n) (if (< n 3) 1 (+ (fib (- n 1)) (fib (- n 2))))))
()
>>> (fib 15)
610.0
|
As alway, [cached]the source is on GitHub, so give it a whirl if you want.