John McCarthy passed away a few weeks ago. For those unfamiliar, he invented Lisp.

After I heard the news, I wondered how hard would it be to create a tiny Lisp in Scala. I imagined that Scala’s parser combinators would make it very simple.

And then I remembered a project called Jitescript. Jitescript is a DSL inspired by Ruby’s BiteScript. Both are very simple ways to output JVM bytecode.

So, I set out to write a Lisp to JVM bytecode compiler. I managed to fit it into 63 lines of code. Sure, it’s not going to compete with Clojure any time soon but I think it shows how easy it is to write a JVM language. I think we could make it even nicer by adding some Scala magic to Jitescript.

You put the S-expression as an argument to the SBT REPL:

> run (- (- (+ (- (+ 99 11) 10) 11) 10) 10)

And then run the Lisp.class:

$ java Lisp
91

(Works out to the number 91)

Here are the 63 lines of Scala:

package scalispa

import util.parsing.combinator.RegexParsers

import java.io.{ File, FileOutputStream, PrintStream }

import me.qmx.jitescript.{ JiteClass, CodeBlock }
import me.qmx.jitescript.util.CodegenUtils.{ p, ci, sig }

import org.objectweb.asm.Opcodes._

sealed trait Node
case class SExp(l: List[Node]) extends Node
case class SInt(i: Int) extends Node
case class SIdent(s: String) extends Node

object Parser extends RegexParsers {
  def int = regex("""[0-9]+""".r) ^^ { (i: String) => SInt(i.toInt) }
  def ident = regex("""[A-Za-z+-/\*]+""".r) ^^ SIdent
  def sexp = "(" ~> rep(node) <~ ")" ^^ SExp
  def node: Parser[Node] = int | ident | sexp
  def apply(s: String) = parse(sexp, s)
}

object Evaluator {
  def compile(b: CodeBlock, n: Node) {
    n match {
      case SExp(Nil) => {}
      case SExp(x :: xs) => {
        xs.foreach(compile(b, _))
        compile(b, x)
      }
      case SInt(x) => b.pushInt(x)
      case SIdent("+") => b.iadd()
      case SIdent("-") => b.isub()
      case SIdent("*") => b.imul()
      case SIdent("/") => b.idiv()
    }
  }

  def apply(program: SExp) {
    val b = new CodeBlock
    compile(b, program)
    b.iprintln().voidreturn()

    val name = "Lisp"
    val c = new JiteClass(name)
    c.defineMethod("main", ACC_PUBLIC | ACC_STATIC, sig(classOf[Unit], classOf[Array[String]]), b)

    val stream = new FileOutputStream(new File(name + ".class"))
    stream.write(c.toBytes)
    stream.close()
  }
}

object Main {
  def main(args: Array[String]) {
    Parser(args mkString " ") match {
      case Parser.Success(p, _) => Evaluator(p)
      case a => println(a)
    }
  }
}

The code is up on Bitbucket, under the unimaginative repo name of Scalispa. Let me know what you think!