Skip to content

michiakig/lisp-in-c

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

95 Commits
 
 
 
 
 
 
 
 

Repository files navigation

"What I cannot create, I do not understand." -- Richard Feynman

A rudimentary Lisp interpreter and compiler, inspired by the last two
exercises of Structure and Interpretation of Computer Programs.

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-35.html#%_thm_5.51

Exercise 5.51.

"Develop a rudimentary implementation of Scheme in C (or some other
low-level language of your choice) by translating the explicit-control
evaluator of section 5.4 into C. In order to run this code you will
need to also provide appropriate storage-allocation routines and other
run-time support."

Exercise 5.52.

"As a counterpoint to exercise 5.51, modify the compiler so that it
compiles Scheme procedures into sequences of C instructions. Compile
the metacircular evaluator of section 4.1 to produce a Scheme
interpreter written in C."

Build

Run make in the interpreter's directory. Start the interpreter's REPL with

$ lispinc ./scm/repl.scm

or, with no derived forms (let, cond, and, or, etc)

$ lispinc ./scm/simplerepl.scm

Features/bugs

The interpreter's reader can't handle two s-expression in one line; it
will ignore the second one. Primitives don't check for arity. The
interpreter has no tail-call optimizationm and no garbage
collection. There are no user-defined macros, although a macro system
is in place for some syntactic sugar used in the compiler (let, cond,
etc) and user-defined macros would be relatively straightforward to
add. There is very, very little error checking. There are many, many
memory leaks.

The compiler is really just a translator from the register machine
language to C. It includes tail-call optimization (well the one from
SICP does) and a naive mark-and-sweep garbage collector, which appears
to work.

License

Since this builds and relies upon SICP, which is graciously available
under a Creative Commons license, this code is under the same license.

http://creativecommons.org/licenses/by-nc/3.0/

See also:

Scheme from Scratch (closest to this project)
http://michaux.ca/articles/scheme-from-scratch-introduction

A tiny self-hosting Lisp-to-C compiler
https://github.com/darius/ichbins

90 Minute Scheme to C Compiler
http://www.iro.umontreal.ca/~boucherd/mslug/meetings/20041020/minutes-en.html

An Incremental Approach to Compiler Construction
http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf