3 ms·

Writing/understanding a lisp interpreter is a longstanding item on my TODO list. Question: how do I go from tackling this to tackling compilers?

pjmlp 9y ago
Make it generatem a simple bytecode format, that you can map into Assembler macros. Choose a good Macro Assembler like NASM or YASM, and implement the bytecodes as macros. It won't win any benchmark, but you will get native executables. Or use Lisp macros to generate the code. Here is a Scheme based tutorial. http://icem-www.folkwang-hochschule.de/~finnendahl/cm_kurse/doc/schintro/schintro_142.html http://icem-www.folkwang-hochschule.de/~finnendahl/cm_kurse/...
kazinator 9y ago
Make a very decent interpreter for a language that is good for writing compilers (without a question, a Lisp of some sorts, of course, ha). Then, write the compiler in that language. The compiler walks the code just like the interpreter, but instead of interpreting, it spits out a translation. Spitting out some kind of translation into something isn't a very high bar; the difficulties are all in optimization: things like analyzing lexical scopes for the presence of closures which escape, so as to be able to stack-allocate environments that aren't captured by closures. Plus all those other difficult things: like turning a program into a graph of basic blocks and doing flow analysis; register allocation, selection of instructions for a myriad target machines, debugging suport, and so on. Any of these requirements can be excluded from a compiler, yet it's still a compiler. The "Lisp in 500 lines of C" (plus accopmanying .lisp) file implemented a compiler. The complete source is hard to find, but here is a derivative project: https://github.com/jackpal/lisp5000 https://github.com/jackpal/lisp5000 A chunk of init500.lisp implements compilation to C. Search the file for terms like "compile" and also "deftransform". If you've ever written a macro, you've written a piece of a compiler. Macros take an input syntax tree and spit out a new one. Many actions traditionally associated with a compiler (by Lisp-unaware computer scientists) can be done by macros or in the macro expander. Basic compiling is a lot like macro expansion. It can actually be Lisp-to-Lisp even; the transformers can spit out a Lisp data structure representing a target language. (Heck GCC spits out a Lisp-like data structure for intermediate code. Of course; it was originally a project started by Stallman.)
gbacon 9y ago
Work through The Make-A-Lisp Process[0], which finishes at “Step A: Metadata, Self-hosting and Interop.”[1] From there, you’ll be more than ready to generate machine code. [0]: https://github.com/kanaka/mal/blob/master/process/guide.md https://github.com/kanaka/mal/blob/master/process/guide.md [1]: https://github.com/kanaka/mal/blob/master/process/guide.md#step-a-metadata-self-hosting-and-interop https://github.com/kanaka/mal/blob/master/process/guide.md#s...
whistlerbrk 9y ago
I was just recommended "Lisp in Small Pieces" for just this.
- DigitalJack 9y ago
  I have that book, though I haven't looked at it in years. I found it intractable then. I've been using clojure in the interim and feel like I've learned quite a bit, so maybe I should go back and look again.

pjmlp 9y ago

Make it generatem a simple bytecode format, that you can map into Assembler macros. Choose a good Macro Assembler like NASM or YASM, and implement the bytecodes as macros. It won't win any benchmark, but you will get native executables. Or use Lisp macros to generate the code. Here is a Scheme based tutorial. http://icem-www.folkwang-hochschule.de/~finnendahl/cm_kurse/doc/schintro/schintro_142.html http://icem-www.folkwang-hochschule.de/~finnendahl/cm_kurse/...

kazinator 9y ago

Make a very decent interpreter for a language that is good for writing compilers (without a question, a Lisp of some sorts, of course, ha). Then, write the compiler in that language. The compiler walks the code just like the interpreter, but instead of interpreting, it spits out a translation. Spitting out some kind of translation into something isn't a very high bar; the difficulties are all in optimization: things like analyzing lexical scopes for the presence of closures which escape, so as to be able to stack-allocate environments that aren't captured by closures. Plus all those other difficult things: like turning a program into a graph of basic blocks and doing flow analysis; register allocation, selection of instructions for a myriad target machines, debugging suport, and so on. Any of these requirements can be excluded from a compiler, yet it's still a compiler. The "Lisp in 500 lines of C" (plus accopmanying .lisp) file implemented a compiler. The complete source is hard to find, but here is a derivative project: https://github.com/jackpal/lisp5000 https://github.com/jackpal/lisp5000 A chunk of init500.lisp implements compilation to C. Search the file for terms like "compile" and also "deftransform". If you've ever written a macro, you've written a piece of a compiler. Macros take an input syntax tree and spit out a new one. Many actions traditionally associated with a compiler (by Lisp-unaware computer scientists) can be done by macros or in the macro expander. Basic compiling is a lot like macro expansion. It can actually be Lisp-to-Lisp even; the transformers can spit out a Lisp data structure representing a target language. (Heck GCC spits out a Lisp-like data structure for intermediate code. Of course; it was originally a project started by Stallman.)

gbacon 9y ago

Work through The Make-A-Lisp Process[0], which finishes at “Step A: Metadata, Self-hosting and Interop.”[1] From there, you’ll be more than ready to generate machine code. [0]: https://github.com/kanaka/mal/blob/master/process/guide.md https://github.com/kanaka/mal/blob/master/process/guide.md [1]: https://github.com/kanaka/mal/blob/master/process/guide.md#step-a-metadata-self-hosting-and-interop https://github.com/kanaka/mal/blob/master/process/guide.md#s...

whistlerbrk 9y ago

I was just recommended "Lisp in Small Pieces" for just this.

DigitalJack 9y ago
I have that book, though I haven't looked at it in years. I found it intractable then. I've been using clojure in the interim and feel like I've learned quite a bit, so maybe I should go back and look again.