Lisp in Small Pieces

Big List of Resources:

• A Nanopass Framework for Compiler Education ¶
• Advanced Compiler Design and Implementation $
• An Incremental Approach to Compiler Construction ¶
• ANTLR 3.x Video Tutorial
• Basics of Compiler Design
• Building a Parrot Compiler
• Compiler Basics
• Compiler Construction $
• Compiler Design and Construction $
• Crafting a Compiler with C $
• Compiler Design in C ¶
• Compilers: Principles, Techniques, and Tools $ — aka "The Dragon Book"; widely considered "the book" for compiler writing.
• Engineering a Compiler $
• Essentials of Programming Languages
• Flipcode Article Archive (look for "Implementing A Scripting Engine by Jan Niestadt")
• Game Scripting Mastery $
• How to build a virtual machine from scratch in C# ¶
• Implementing Functional Languages
• Implementing Programming Languages (with BNFC)
• Implementing Programming Languages using C# 4.0
• Interpreter pattern (described in Design Patterns $) specifies a way to evaluate sentences in a language
• Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages
• Let's Build a Compiler by Jack Crenshaw — The PDF ¶ version (examples are in Pascal, but the information is generally applicable)
• Linkers and Loaders $ (Google Books)
• Lisp in Small Pieces (LiSP) $
• LLVM Tutorial
• Modern Compiler Implementation in ML $ — There is a Java $ and C $ version as well - widely considered a very good book
• Object-Oriented Compiler Construction $
• Parsing Techniques - A Practical Guide
• Project Oberon ¶ - Look at chapter 13
• Programming a Personal Computer $
• Programing Languages: Application and Interpretation
• Rabbit: A Compiler for Scheme¶
• Reflections on Trusting Trust — A quick guide
• Roll Your Own Compiler for the .NET framework — A quick tutorial from MSDN
• Structure and Interpretation of Computer Programs
• Types and Programming Languages
• Want to Write a Compiler? - a quick guide
• Writing a Compiler in Ruby Bottom Up

Legend:

• ¶ Link to a PDF file
• $ Link to a printed book

A simple arithmetic interpreter in Scheme that takes a list of symbols as input:

(define (symbolic-arith lst)
  (case (car lst)
    ((add) (+ (cadr lst) (caddr lst)))
    ((sub) (- (cadr lst) (caddr lst)))
    ((mult) (* (cadr lst) (caddr lst)))
    ((div) (/ (cadr lst) (caddr lst)))
    (else (error "unknown operator"))))

Test run:

> (symbolic-arith '(add 2 43))
=> 45
> (symbolic-arith '(sub 10 43))
=> -33
> (symbolic-arith '(mu 50 43))
unknown operator
> (symbolic-arith '(mult 50 43))
=> 2150

That shows the basic idea behind meta-circular interpreters. Lisp in Small Pieces is the best place to learn about such interpreters.

Another simple example where lists of symbols are used to implement a key-value data store:

> (define person (list (cons 'name 'mat) (cons 'age 20)))
> person
=> ((name . mat) (age . 20))    
> (assoc 'name person)
=> (name . mat)
> (assoc 'age person)
=> (age . 20)

If you are new to Lisp, Common Lisp: A Gentle Introduction to Symbolic Computation is a good place to start.

Last weekend, I was asking myself the same question to port my toy language to the JVM.

I spend only few hours searching information,so take this references with a grain of salt.

• Language Implementation Patterns. I hate antlr but this book looks very good. If you dont like antlr neither, there is a very good about parsing "Parsing Techniques. A Practical Guide."

  Learn to build configuration file readers, data readers, model-driven code generators, source-to-source translators, source analyzers, and interpreters. You don’t need a background in computer science—ANTLR creator Terence Parr demystifies language implementation by breaking it down into the most common design patterns. Pattern by pattern, you’ll learn the key skills you need to implement your own computer languages.

  Chapter 10 cover in 30 pages (to fast IMO) this topics. But there are other chapter that probably you will be interested.

  • 10 Building Bytecode Interpreters
    • 10.1 Programming Bytecode Interpreters . .
    • 10.2 Defining an Assembly Language Syntax
    • 10.3 Bytecode Machine Architecture . . . . .
    • 10.4 Where to Go from Here . . . . . . . . . .
    • P.26. Bytecode Assembler . . . . . . . . . . .
    • P.27. Stack-Based Bytecode Interpreter . . .
    • P.28. Register-Based Bytecode Interpreter
    http://pragprog.com/titles/tpdsl/language-implementation-patterns

  • The Implementation of Lua 5.0 This is a great paper about register- based bytecode machines. Go an read it even for the sake of it.

  • Lisp in Small Pieces. This book teach how to write a 2 schme compailers that compile to C. So many lessons can be learned from this book. I own a copy of this book and it is really good for anyone interesting is lisp, but maybe not your cup of tea.

    This is a comprehensive account of the semantics and the implementation of the whole Lisp family of languages, namely Lisp, Scheme and related dialects. It describes 11 interpreters and 2 compilers ...

  http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/dp/0521562473

Check the Dalvik7 VM, a register-based VM. The DVM operates on bytecodes that are transformed from the Java Class files compiled by a Java compiler.

There is a mailing list about the topic, jvm-languages.

Are you planning to upload the code to anyplace? I would like to take a look.

This SICP chapter shows how to write a Lisp interpreter in Lisp (a metacircular evaluator). In my opinion this is the best place to start. Then you can move on to Lisp in Small Pieces to learn how to write advanced interpreters and compilers for Lisp. The advantage of implementing a language like Lisp (in Lisp itself!) is that you get the lexical analyzer, parser, AST, data/program representation and REPL for free. You can concentrate on the task of getting your great language working!