Scalisp - a Lisp interpreter in Scala

Inspired by 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:

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, the source is on GitHub, so give it a whirl if you want.

Tags: programming, university