Compiling a Lisp: Reader(bernsteinbear.com)
bernsteinbear.com
Compiling a Lisp: Reader
https://bernsteinbear.com/blog/compiling-a-lisp-6/
29 comments
Racket is fun. You can indeed use it to write about any language you want, not limited to Lisp-alikes.
https://blind.guru/MarioLANG.html
https://blind.guru/MarioLANG.html
I've been meaning to do beautiful racket but totally forgot about it. Thanks for mentioning it.
Thank you for sharing the link to that book. I'm very much not a pro coder, just a sysadmin-turned-devops person who writes Terraform, Ansible, and CloudFormation YAML. (And Emacs-Lisp) This book seems really fascinating to me and the idea that I could put together my own devops-oriented DSL is a very intriguing idea!
If you are new into lisp I highly recommmend you htdp2. It also uses subsets of racket to teach. I love how it teaches the fundamentals of programming. Simple and clean.
https://htdp.org/2018-01-06/Book/
https://htdp.org/2018-01-06/Book/
Thank you! Greatly Appreciated :)
The Common Lisp specification has the entire reader algorithm laid out[1]. It fits on a single page, and it's really easy to understand.
Note, however, that there is heavy lifting done by the default read-table (the CL reader is table-based and is dynamically modifiable[2]), so you will only be able to read tokens if you implement what is on that page.
However, the most common characters are nearly trivial to implement: #\( #\" #\' as well as the most common dispatch characters for #\#
1: http://www.lispworks.com/documentation/HyperSpec/Body/02_b.h...
2: Someone modified the lisp reader to be able to read in valid C89 code, and implemented a backend to compile that to common-lisp: https://github.com/vsedach/Vacietis
Note, however, that there is heavy lifting done by the default read-table (the CL reader is table-based and is dynamically modifiable[2]), so you will only be able to read tokens if you implement what is on that page.
However, the most common characters are nearly trivial to implement: #\( #\" #\' as well as the most common dispatch characters for #\#
1: http://www.lispworks.com/documentation/HyperSpec/Body/02_b.h...
2: Someone modified the lisp reader to be able to read in valid C89 code, and implemented a backend to compile that to common-lisp: https://github.com/vsedach/Vacietis
For a very simple, very readable Lisp reader, see Lumen's reader.l file: https://github.com/sctb/lumen/blob/master/reader.l
It compiles to Javacript and Lua, so if you prefer reading those, you can:
https://github.com/sctb/lumen/blob/master/bin/reader.js
https://github.com/sctb/lumen/blob/master/bin/reader.lua
It turns out that you can greatly simplify the code by e.g. "does an atom start with 0x, 0-9, or dash? if so, try converting it to a number."
That turns out to handle cases like 1e9 too. Whereas "1e" becomes a valid lisp symbol. So you can set it to your own value.
The emacs source code is also worth reading. It's not simple, but it's simple enough to be understandable: https://github.com/emacs-mirror/emacs/blob/7b3e94b6648ed00c6...
I like emacs source code because it handles "every possible real-world case that you can think of."
It compiles to Javacript and Lua, so if you prefer reading those, you can:
https://github.com/sctb/lumen/blob/master/bin/reader.js
https://github.com/sctb/lumen/blob/master/bin/reader.lua
It turns out that you can greatly simplify the code by e.g. "does an atom start with 0x, 0-9, or dash? if so, try converting it to a number."
That turns out to handle cases like 1e9 too. Whereas "1e" becomes a valid lisp symbol. So you can set it to your own value.
The emacs source code is also worth reading. It's not simple, but it's simple enough to be understandable: https://github.com/emacs-mirror/emacs/blob/7b3e94b6648ed00c6...
I like emacs source code because it handles "every possible real-world case that you can think of."
Why are atoms that start with numbers accepted as symbols? Is there any usecase for that?
I don't know about lumen, but i think in Scheme a symbol is "just" an immutable string, except that is used in a different ways for different purposes than strings which are for text.
Here is Guile Scheme (not sure if this is standard or Guile specific):
Here is Guile Scheme (not sure if this is standard or Guile specific):
scheme@(guile-user)> 1e9
$2 = 1.0e9
scheme@(guile-user)> (string->symbol "1e9")
$3 = #{1e9}# ;; This the double quote equivalent for symbols.
scheme@(guile-user)> (define #{1e9}# "foo")
scheme@(guile-user)> #{1e9}#
$4 = "foo"
The use case is someone wanted to name a symbol that way. What’s wrong with that?
Nothing wrong, was just wondering in case I missed something, in most languages by convention variables and functions cannot start with a number. I'm learning lisp and ran into this at some point just had the chance to ask someone experienced why.
[deleted]
I had floating point implemented like that in Nokolisp. If the item contains anything except number characters, it is a symbol. Stupid, but very transparent eventually, because modified arithmetic operators test if a symbol can be interpreted as a floating point number.
Common Lisp has a concept of a "potential number" number which is a token that looks numberish, and it permits implementations to have custom numeric literals that are potential numbers. Even then though, if you have e.g. an asterisk or a percent or something it will not be a potential number.
http://www.lispworks.com/documentation/HyperSpec/Body/02_caa...
http://www.lispworks.com/documentation/HyperSpec/Body/02_caa...
Lots of things you might want to name have natural names starting with numbers. If you're writing, say, a TSP solver, some of your procedures may be called 2-opt or 3-opt, for example.
I like that about lisp and surprisingly I came to like the kebab case, i find it quite easy to read at a glance. Before toying with scheme that and the parentheses seemed a bit dated but I came to like them quite a bit
I attribute a big chunk of my real-world education (back in the 90s) about how to ship a complicated software product on multiple architectures to reading the Mosaic and XEmacs source code. It helped me immensely when trying to ship my own software.
Femtolisp has a nice, comprehensible Lisp reader written in C, with syntax very similar to Common Lisp:
https://github.com/JeffBezanson/femtolisp/blob/master/read.c
CMUCL has a fairly complex, but still comprehensible implementation of a Common Lisp reader:
https://gitlab.common-lisp.net/cmucl/cmucl/-/blob/master/src...
It uses a FSM to recognize numbers and symbols when tokenizing, and it demonstrates an implementation of Common Lisp readtables.
Here's how the Common Lisp Hyperspec specifies the Common Lisp reader (as an algorithm):
http://www.lispworks.com/documentation/HyperSpec/Body/02_b.h...
https://github.com/JeffBezanson/femtolisp/blob/master/read.c
CMUCL has a fairly complex, but still comprehensible implementation of a Common Lisp reader:
https://gitlab.common-lisp.net/cmucl/cmucl/-/blob/master/src...
It uses a FSM to recognize numbers and symbols when tokenizing, and it demonstrates an implementation of Common Lisp readtables.
Here's how the Common Lisp Hyperspec specifies the Common Lisp reader (as an algorithm):
http://www.lispworks.com/documentation/HyperSpec/Body/02_b.h...
Oh cool, someone else besides me posted my blog :D
I'm the author and here to answer questions and take constructive criticism.
If you want to comment but don't have an HN account, please check out the mailing list: https://lists.sr.ht/~max/compiling-lisp
I'm the author and here to answer questions and take constructive criticism.
If you want to comment but don't have an HN account, please check out the mailing list: https://lists.sr.ht/~max/compiling-lisp
Is there a reason you treat the arithmetic operators specially in your reader? Non-lisps do so as they are infix operators, but most lisps treat them the same as any other identifier.
I don't think I treat them any differently in my reader. They are part of the set of "symbol characters". I do special case + and - prefixed integers, though.
Right, just read some logic backwards flipping through that code.
I love seeing long form blog posts like this! Whilst its not something I’d personally do for a long time, its great to have resources on the web that go into detail in advanced topics like building a lisp interpreter.
From another lisper, congrats and well done!
From another lisper, congrats and well done!
I agree that I really enjoy reading in-depth blog post series, but after releasing a 3-part series myself, I'm not sure if I would do it again. Each subsequent post got about 1/3 the views of the previous one, and wow does it take sooo much more effort to write than a one-off post!
This one is great though. I just every few days for the next post!
This one is great though. I just every few days for the next post!
Indeed, these things take a lot of effort and views / feedback isn’t great.
Unfortunately the internet has moved towards short form, rehashing simple concepts and clickbait titles - there’s so much junk online, and the signal to noise ratio is high.
But people are gaming for most interaction, views, etc and attention spans are shorter. So this is the world we live in
Unfortunately the internet has moved towards short form, rehashing simple concepts and clickbait titles - there’s so much junk online, and the signal to noise ratio is high.
But people are gaming for most interaction, views, etc and attention spans are shorter. So this is the world we live in
You're right, it is a lot of effort! I made myself a promise that I wouldn't sprint through the first couple and then fall off a cliff on the rest. That's been a failing of mine in the past.
Progress is currently regular-ish because I've already implemented this stuff before I started writing. Once we get to labels and label calls, though, there very well could be a significant slowdown. I haven't figured out how to do that properly!
I'm glad you like the series and I'm very flattered that you posted it.
Progress is currently regular-ish because I've already implemented this stuff before I started writing. Once we get to labels and label calls, though, there very well could be a significant slowdown. I haven't figured out how to do that properly!
I'm glad you like the series and I'm very flattered that you posted it.
I am following the "Compiling a Lisp" series, its great, please keep posting, and thanks for your effort.
[deleted]
Racket (if you're not aware of what it is) is just a lisp, but the standard library includes an incredible amount of support for creating readers and expanders for programming languages with very little effort.
You aren't even limited to Racket as the target language for your compilation. It's incredibly easy to formulate whatever output you want (like assembly in this article).
Of course there's still an incredible amount of value and fun in doing everything from scratch like this article's series describes. One of the most intellectually rewarding things I've ever done is working through nand2tetris.
You have a great blog /u/tekknolagi.
[1]: https://beautifulracket.com/