9 ms·

Let's make a Teeny Tiny compiler

256 points by whack 6y ago

lixtra 6y ago
I wonder if he left out the LET nums = nums - 1 on purpose.
boudewijnrempt 6y ago
What I always admired about the ZX-Spectrum's Basic was that it skipped the entire idea of a lexer, because, well, the keyboard let you input tokens directly.
- jacobush 6y ago
  Which tied into how they could make the keyboard cheaper, remember the rubber keys? :-)
- Lerc 6y ago
  I think it was closer to the other way around. The keyboard let you input tokens because it didn't have a lexer. I suspect this is more due to the memory cost of storing a literal line of code more than the ROM or CPU cost of a lexer. Going back to the ZX-80 storing even the current line being typed as characters was probably a burden.
  - tachyonbeam 6y ago
    AFAIK the keyboard was also just very cheap and a pain to type on.
    - webreac 6y ago
      I don't remember complaining about keyboard. The only issue was loosing memory because the memory expansion (16ko) had bad contacts.
      - thom 6y ago
        Ha, my dad tells me we had a strict rule of no running in the house while he was working on the Spectrum for this exact reason.
    - JasonFruit 6y ago
      The keyboard was a disaster. My dad had an old teletype keyboard and adapted that to it when the original membrane died. I was pretty impressed.
  - Someone 6y ago
    That can’t be it. The Basic interpreter could run the lexer on each line the user typed and store the tokens. You would lose the ability to print lines exactly the way the user typed them, but that isn’t a big blocker for the technology of the time. Alternatively, the Basic interpreter could store each line as a combination of tokens and characters. Commodore Basic did that (https://www.masswerk.at/nowgobang/2020/commodore-basic-renumber https://www.masswerk.at/nowgobang/2020/commodore-basic-renum...). I also think none of the microcomputer Basics stored keywords as ascii strings. It would both slow down the interpreter and use more memory.
    - edw 6y ago
      I can confirm that AppleSoft ][ BASIC stored its programs in memory in tokenized form. On another note, I went ahead and wrote a code emitter, because I couldn't wait for part three (though I noticed it's in the GitHub repo). Once you get this compiler up and running the sane thing to do is write a Makefile so you can treat Teeny as a first-class programming language. Just add a Makefile with the following: %.c : %.tiny <TAB>python3 ./teenytiny.py $< > $@ And you'll be able to type `make hello` and have hello.tiny compiled to hello.c compiled to hello automagically. I can never pass up an opportunity to remind people that Make is wonderful.
- stevekemp 6y ago
  I wrote a simple BASIC interpreter inspired by the Sinclair, over here https://github.com/skx/gobasic https://github.com/skx/gobasic
cloogshicer 6y ago
If you want to dive deeper into this topic, I also recommend the wonderful book Crafting Interpreters by Bob Nystrom. It can even be read for free online: http://craftinginterpreters.com/ http://craftinginterpreters.com/ I'm not affiliated with it, but I devoured it recently and thought it was amazing.
- mhh__ 6y ago
  'tis a good book. Appel's compiler implementation in x (if you choose anything other than ML you don't deserve to live) is a good follow on
- azhenley 6y ago
  Author of Teeny Tiny here! I really like Crafting Interpreters too (I link to it at the bottom). Also highly recommend the book Writing an Interpreter in Go.
  - kqr2 6y ago
    Link to Writing an Interpreter in Go website: https://interpreterbook.com/ https://interpreterbook.com/
- ghosty141 6y ago
  I really do appreciate this book. It's absolutely amazing, especially since it's free but I kind of dislike how in some parts the code is just shown without explaining the theory behind it. I doubt you could follow the book very well without having almost all of the source code layed out infront of you. I'd much rather have a language agnostic explanation that does not rely on certain classes or patterns that only work well in the word of OOP-Languages.
melling 6y ago
I’ve got a bunch of links about compilers in a GitHub repo: https://github.com/melling/ComputerLanguages/blob/master/compilers.md https://github.com/melling/ComputerLanguages/blob/master/com...
- cellularmitosis 6y ago
  Nice! I have been collecting a list as well :) https://gist.github.com/cellularmitosis/1f55f9679f064bcff02905acb44ca510#simple-compiler-codebases-to-study https://gist.github.com/cellularmitosis/1f55f9679f064bcff029...
userbinator 6y ago
There seems to have been an explosion of such articles within the past few years, despite things like Crenshaw's tutorial existing for several decades; I wonder why a large number of people have suddenly started thinking "I understand this, I should write an article about it". My favourite demonstration of a "teeny tiny compiler" is still C4: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 Perhaps it inspired all these compiler articles?
- molticrystal 6y ago
  Always enjoyed Fabrice Bellard's work, like https://bellard.org/otcc/ https://bellard.org/otcc/ which is 2048 bytes and self compiles & https://bellard.org/tcc/ https://bellard.org/tcc/ , his TinyEmu and Javascript PC Emulator that boots several OSes including linux are cool as well.
- staycoolboy 6y ago
  <I deleted this because it wasn't nice>
  - azhenley 6y ago
    Actually, my students were having trouble following other tutorials so I wrote this for them. (I also just love talking about compilers!) I’d summarize my tutorial as a shorter version of Crenshaw’s. I love seeing more and more compiler tutorials. They all have different goals and perspectives.
    - staycoolboy 6y ago
      Sorry, my comment wasn't in the HN spirit.
  - hliyan 6y ago
    Been on many internet forums for the past 20 years. The first time I've ever seen such candid yet terse retraction. This is what I like about HN as a community (either that, or moderation is out of this world).
ngcc_hk 6y ago
Python!? Anyway wait for part 2 and 3.
- azhenley 6y ago
  I released Part 2 yesterday! (I had forgot to update the link, which is now fixed.) http://web.eecs.utk.edu/~azh/blog/teenytinycompiler2.html http://web.eecs.utk.edu/~azh/blog/teenytinycompiler2.html
mrlonglong 6y ago
REPEAT seems superfluous as only ENDWHILE is needed to end the loop. And, oh yes who forgot to decrement nums? Edit: s/N/nums
dntbnmpls 6y ago
Not a fan of people sneaking referral links here. You could have easily recommended the book without the referral link and if you were going to link it, be open about it being a referral link.
- azhenley 6y ago
  Didn’t mean to, sorry. I just copied and pasted it from the blog post (which is labeled). I’ve removed it.
  - bogomipz 6y ago
    You don't need to apologize. Their comment is uncalled for and just seems mean-spirited. I thoroughly enjoyed your article and am looking forward to future posts. I hope you post them here when they're up! Cheers.
    - dntbnmpls 6y ago
      It wasn't mean spirited and it was justified. If people are using link shorteners to hide the fact that their link is a referral, then it invites everyone to sneak referral links in their comments here. Do you really want that? He removed that link from his comment and he apologized because it was the right thing to do. Also, virtue signaling to encourage bad behavior isn't right, no matter how good or superior you think it makes you feel. Especially considering you weren't smart enough to realize that I wasn't criticizing the referrals in his article ( valid ), I was criticizing the shortened link in his comment which was a referral.
      - bogomipz 6y ago
        Yeah, no. In civil discourse you give people the benefit of the doubt that they weren't doing something for nefarious purposes but that they maybe made an honest mistake. In this case it was simply a copy paste error which they pointed out. They apologized because they were being civil and polite not out of some admission of guilt. Somehow you were the one that missed all of this. I think you can see what others thought of your tone as well. Both of your comments here come across as very angry.
bluedays 6y ago
I really like this. Python is the first language I learned. So it's like this is being written in my native tongue. I've read crafting interpreters, numerous times both before and after learning some Java basics, but seeing it in Python made it click. Also love the way you used classes. That helped clarify some confusion I had with classes in Python.
- yardshop 6y ago
  I'm working through Crafting Interpreters right now, converting the Java to Python as I go. Most things are fairly straight forward to convert, but there are definitely some topics that I've had to learn about in Java (not a language I know very well) so I could figure out how to do it in Python. Really great book and great learning project.
kragen 6y ago
Unfortunately this is not yet a compiler; it's a lexer and a parser. Traditionally these are the first things you present in a compilers course, but from my point of view, that's kind of dumb, for two reasons. First, a parser isn't a compiler, so this means you get through the whole first part of the course without having a compiler. By contrast, a code generator is a compiler, at least if there's some way to invoke it. Second, although the theory of formal languages and parsers is complex, well-developed, and fascinating, it's not clear that it's important to building a compiler. People have written large systems in FORTH. MUMPS famously ran a number of hospital systems without being able to break a statement across lines. And a complete scannerless BNF grammar for S-expressions (without readmacros) is something like this: <sexp> ::= <idchar>+ " "* | "(" " "* <sexp>* ")" " "* And many, many huge systems have been written in Lisps whose grammars amount to little more than that. My favorite grammars are PEGs, which accommodate scannerless parsing rather better than LL(1) and LALR(1) parsers, because PEGs have infinite lookahead with worst-case linear-time parsing (at the expense, it must be admitted, of being a huge memory hog). PEGs are also composable in a way that LALR and LL grammars aren't. I wrote a one-page PEG parser generator targeting JS at https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md a few years back. But I think an excessive focus on the syntax of a programming language really detracts from what's really revolutionary about programming languages (and compilers), which is their semantics. We have much better theories of semantics now than we had in the 1970s when the traditional compilers course was being laid out. Books like Essentials of Programming Languages can be wonderful introductions to the fuzzier ones, and there's a lot of work in things like Coq and Idris to come up with tractable formalizations. But you don't need much of a theory of semantics to get a simple compiler up and running! But I haven't ever actually taught a compilers course, so maybe my ideas are miscalibrated about what students would enjoy and find motivating (having a working compiler for a simple language after doing the first problem set) and what students will find difficult out of proportion to any rewards it might bring (getting recursive-descent parsers for complex grammars working, debugging precedence rules, refactoring grammars to eliminate left recursion, encountering unexpected exponential-time parse failures, etc.).
- kerkeslager 6y ago
  I'm really glad you said this, because it articulates something I've thought for a long time. The focus on syntax in compilers literature is basically bike-shedding. People focus on syntax because they understand it, but code generation is much harder. Matt Might's blog is a rare exception. Do you have any resources on code generators?
signaru 6y ago
Thankful that is a dialect of BASIC! The other great references mentioned here parse C-like languages. Although I can try figuring out, I'm interested to see a good tutorial that does parse BASIC syntax. Also interested to see how it is done in Python (whereas many use C/C++ or Java which have many features that make things a little easier). Looking forward to seeing this series finished.

256 points by whack 6y ago

I wonder if he left out the LET nums = nums - 1 on purpose.

What I always admired about the ZX-Spectrum's Basic was that it skipped the entire idea of a lexer, because, well, the keyboard let you input tokens directly.

jacobush 6y ago
Which tied into how they could make the keyboard cheaper, remember the rubber keys? :-)
Lerc 6y ago
I think it was closer to the other way around. The keyboard let you input tokens because it didn't have a lexer. I suspect this is more due to the memory cost of storing a literal line of code more than the ROM or CPU cost of a lexer. Going back to the ZX-80 storing even the current line being typed as characters was probably a burden.
- tachyonbeam 6y ago
  AFAIK the keyboard was also just very cheap and a pain to type on.
  - webreac 6y ago
    I don't remember complaining about keyboard. The only issue was loosing memory because the memory expansion (16ko) had bad contacts.
    - thom 6y ago
      Ha, my dad tells me we had a strict rule of no running in the house while he was working on the Spectrum for this exact reason.
  - JasonFruit 6y ago
    The keyboard was a disaster. My dad had an old teletype keyboard and adapted that to it when the original membrane died. I was pretty impressed.
- Someone 6y ago
  That can’t be it. The Basic interpreter could run the lexer on each line the user typed and store the tokens. You would lose the ability to print lines exactly the way the user typed them, but that isn’t a big blocker for the technology of the time. Alternatively, the Basic interpreter could store each line as a combination of tokens and characters. Commodore Basic did that (https://www.masswerk.at/nowgobang/2020/commodore-basic-renumber https://www.masswerk.at/nowgobang/2020/commodore-basic-renum...). I also think none of the microcomputer Basics stored keywords as ascii strings. It would both slow down the interpreter and use more memory.
  - edw 6y ago
    I can confirm that AppleSoft ][ BASIC stored its programs in memory in tokenized form. On another note, I went ahead and wrote a code emitter, because I couldn't wait for part three (though I noticed it's in the GitHub repo). Once you get this compiler up and running the sane thing to do is write a Makefile so you can treat Teeny as a first-class programming language. Just add a Makefile with the following: %.c : %.tiny <TAB>python3 ./teenytiny.py $< > $@ And you'll be able to type `make hello` and have hello.tiny compiled to hello.c compiled to hello automagically. I can never pass up an opportunity to remind people that Make is wonderful.
stevekemp 6y ago
I wrote a simple BASIC interpreter inspired by the Sinclair, over here https://github.com/skx/gobasic https://github.com/skx/gobasic

cloogshicer 6y ago

If you want to dive deeper into this topic, I also recommend the wonderful book Crafting Interpreters by Bob Nystrom. It can even be read for free online: http://craftinginterpreters.com/ http://craftinginterpreters.com/ I'm not affiliated with it, but I devoured it recently and thought it was amazing.

mhh__ 6y ago
'tis a good book. Appel's compiler implementation in x (if you choose anything other than ML you don't deserve to live) is a good follow on
azhenley 6y ago
Author of Teeny Tiny here! I really like Crafting Interpreters too (I link to it at the bottom). Also highly recommend the book Writing an Interpreter in Go.
- kqr2 6y ago
  Link to Writing an Interpreter in Go website: https://interpreterbook.com/ https://interpreterbook.com/
ghosty141 6y ago
I really do appreciate this book. It's absolutely amazing, especially since it's free but I kind of dislike how in some parts the code is just shown without explaining the theory behind it. I doubt you could follow the book very well without having almost all of the source code layed out infront of you. I'd much rather have a language agnostic explanation that does not rely on certain classes or patterns that only work well in the word of OOP-Languages.

melling 6y ago

I’ve got a bunch of links about compilers in a GitHub repo: https://github.com/melling/ComputerLanguages/blob/master/compilers.md https://github.com/melling/ComputerLanguages/blob/master/com...

cellularmitosis 6y ago
Nice! I have been collecting a list as well :) https://gist.github.com/cellularmitosis/1f55f9679f064bcff02905acb44ca510#simple-compiler-codebases-to-study https://gist.github.com/cellularmitosis/1f55f9679f064bcff029...

userbinator 6y ago

There seems to have been an explosion of such articles within the past few years, despite things like Crenshaw's tutorial existing for several decades; I wonder why a large number of people have suddenly started thinking "I understand this, I should write an article about it". My favourite demonstration of a "teeny tiny compiler" is still C4: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 Perhaps it inspired all these compiler articles?

molticrystal 6y ago
Always enjoyed Fabrice Bellard's work, like https://bellard.org/otcc/ https://bellard.org/otcc/ which is 2048 bytes and self compiles & https://bellard.org/tcc/ https://bellard.org/tcc/ , his TinyEmu and Javascript PC Emulator that boots several OSes including linux are cool as well.
staycoolboy 6y ago
<I deleted this because it wasn't nice>
- azhenley 6y ago
  Actually, my students were having trouble following other tutorials so I wrote this for them. (I also just love talking about compilers!) I’d summarize my tutorial as a shorter version of Crenshaw’s. I love seeing more and more compiler tutorials. They all have different goals and perspectives.
  - staycoolboy 6y ago
    Sorry, my comment wasn't in the HN spirit.
- hliyan 6y ago
  Been on many internet forums for the past 20 years. The first time I've ever seen such candid yet terse retraction. This is what I like about HN as a community (either that, or moderation is out of this world).

ngcc_hk 6y ago

Python!? Anyway wait for part 2 and 3.

azhenley 6y ago
I released Part 2 yesterday! (I had forgot to update the link, which is now fixed.) http://web.eecs.utk.edu/~azh/blog/teenytinycompiler2.html http://web.eecs.utk.edu/~azh/blog/teenytinycompiler2.html

mrlonglong 6y ago

REPEAT seems superfluous as only ENDWHILE is needed to end the loop. And, oh yes who forgot to decrement nums? Edit: s/N/nums

dntbnmpls 6y ago

Not a fan of people sneaking referral links here. You could have easily recommended the book without the referral link and if you were going to link it, be open about it being a referral link.

azhenley 6y ago
Didn’t mean to, sorry. I just copied and pasted it from the blog post (which is labeled). I’ve removed it.
- bogomipz 6y ago
  You don't need to apologize. Their comment is uncalled for and just seems mean-spirited. I thoroughly enjoyed your article and am looking forward to future posts. I hope you post them here when they're up! Cheers.
  - dntbnmpls 6y ago
    It wasn't mean spirited and it was justified. If people are using link shorteners to hide the fact that their link is a referral, then it invites everyone to sneak referral links in their comments here. Do you really want that? He removed that link from his comment and he apologized because it was the right thing to do. Also, virtue signaling to encourage bad behavior isn't right, no matter how good or superior you think it makes you feel. Especially considering you weren't smart enough to realize that I wasn't criticizing the referrals in his article ( valid ), I was criticizing the shortened link in his comment which was a referral.
    - bogomipz 6y ago
      Yeah, no. In civil discourse you give people the benefit of the doubt that they weren't doing something for nefarious purposes but that they maybe made an honest mistake. In this case it was simply a copy paste error which they pointed out. They apologized because they were being civil and polite not out of some admission of guilt. Somehow you were the one that missed all of this. I think you can see what others thought of your tone as well. Both of your comments here come across as very angry.

bluedays 6y ago

I really like this. Python is the first language I learned. So it's like this is being written in my native tongue. I've read crafting interpreters, numerous times both before and after learning some Java basics, but seeing it in Python made it click. Also love the way you used classes. That helped clarify some confusion I had with classes in Python.

yardshop 6y ago
I'm working through Crafting Interpreters right now, converting the Java to Python as I go. Most things are fairly straight forward to convert, but there are definitely some topics that I've had to learn about in Java (not a language I know very well) so I could figure out how to do it in Python. Really great book and great learning project.

kragen 6y ago

Unfortunately this is not yet a compiler; it's a lexer and a parser. Traditionally these are the first things you present in a compilers course, but from my point of view, that's kind of dumb, for two reasons. First, a parser isn't a compiler, so this means you get through the whole first part of the course without having a compiler. By contrast, a code generator is a compiler, at least if there's some way to invoke it. Second, although the theory of formal languages and parsers is complex, well-developed, and fascinating, it's not clear that it's important to building a compiler. People have written large systems in FORTH. MUMPS famously ran a number of hospital systems without being able to break a statement across lines. And a complete scannerless BNF grammar for S-expressions (without readmacros) is something like this: <sexp> ::= <idchar>+ " "* | "(" " "* <sexp>* ")" " "* And many, many huge systems have been written in Lisps whose grammars amount to little more than that. My favorite grammars are PEGs, which accommodate scannerless parsing rather better than LL(1) and LALR(1) parsers, because PEGs have infinite lookahead with worst-case linear-time parsing (at the expense, it must be admitted, of being a huge memory hog). PEGs are also composable in a way that LALR and LL grammars aren't. I wrote a one-page PEG parser generator targeting JS at https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md a few years back. But I think an excessive focus on the syntax of a programming language really detracts from what's really revolutionary about programming languages (and compilers), which is their semantics. We have much better theories of semantics now than we had in the 1970s when the traditional compilers course was being laid out. Books like Essentials of Programming Languages can be wonderful introductions to the fuzzier ones, and there's a lot of work in things like Coq and Idris to come up with tractable formalizations. But you don't need much of a theory of semantics to get a simple compiler up and running! But I haven't ever actually taught a compilers course, so maybe my ideas are miscalibrated about what students would enjoy and find motivating (having a working compiler for a simple language after doing the first problem set) and what students will find difficult out of proportion to any rewards it might bring (getting recursive-descent parsers for complex grammars working, debugging precedence rules, refactoring grammars to eliminate left recursion, encountering unexpected exponential-time parse failures, etc.).

kerkeslager 6y ago
I'm really glad you said this, because it articulates something I've thought for a long time. The focus on syntax in compilers literature is basically bike-shedding. People focus on syntax because they understand it, but code generation is much harder. Matt Might's blog is a rare exception. Do you have any resources on code generators?

signaru 6y ago

Thankful that is a dialect of BASIC! The other great references mentioned here parse C-like languages. Although I can try figuring out, I'm interested to see a good tutorial that does parse BASIC syntax. Also interested to see how it is done in Python (whereas many use C/C++ or Java which have many features that make things a little easier). Looking forward to seeing this series finished.