Lisp in Small Pieces

Author: Christian Queinnec
All Stack Overflow 10
This Year Stack Overflow 1


by Michael Stum   2018-03-19

Big List of Resources:


  • ¶ Link to a PDF file
  • $ Link to a printed book
by anonymous   2017-08-20

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.

by anonymous   2017-08-20

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
    • 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 ...

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.

by anonymous   2017-08-20

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!