4 ms·

Let's make a Teeny Tiny compiler (2020)

107 points by ingve 3y ago

orthoxerox 3y ago
Writing a transpiler that turns a simple imperative language like Teeny into a simple imperative language like C doesn't feel like a useful exercise at all. Even Lox, that doesn't claim to be a compiler at all, does something more useful: it transpiles code in Lox into Lox VM bytecode. I'd rather transpiler tutorials did something like turning a functional or OO-language into C.
- weird_user 3y ago
  It's still a useful generic exercise for beginners. Although I recommend starting with a simpler syntax like sexpr, you can get more practice with less code. For a deeper exercise, I recommend compiling to machine code instead of stopping at bytecode [1]; you can learn assembly along the way, which is more satisfying than compiling to C. [1]: https://github.com/byo-books/pretty_laughable_lang/ https://github.com/byo-books/pretty_laughable_lang/
  - orthoxerox 3y ago
    I agree that compiling to machine code is super satisfying, but there's a lot of upfront work you have to do before you can run your first "hello world": architectures, calling conventions, object file formats, linking. That's why I no longer object to compiler tutorials stopping at assembly or even C, as long as the phases not present in interpreter tutorials like Bob Nystrom's brilliant one are non-trivial: type checking, optimizations, lowering.
    - samsquire 3y ago
      One thing you can do is implement a JIT compiler. Here's Martin Jacob's code to execute arbitrary memory. If you malloc a byte array and insert opcodes directly at indexes, you can construct machine code and execute it. https://gist.github.com/martinjacobd/3ee56f3c7b7ce621034ec3ecbc8e13f1/fe7e78b89e1581ff15c4d2797662516f281a33bd https://gist.github.com/martinjacobd/3ee56f3c7b7ce621034ec3e... Since your C program is already in memory, you have access to the C standard library and don't have to worry about linking or object formats but you'll have to worry about parameter passing and FFI. My toy JIT compiler based on this idea is here https://github.com/samsquire/compiler https://github.com/samsquire/compiler but it is incomplete.
  - grumpyprole 3y ago
    Compiling to LLVM IR is much easier than machine code and would still be satisfying I think.
- kwhitefoot 3y ago
  Nim compiles to C. It seems very useful to me. It produces small and fast executables. But is a sophisticated language much too big to be used a tutorial.
  - orthoxerox 3y ago
    Yes, and like I've mentioned in another comment, it's not a trivial transformation. A tutorial for a transpiler doesn't have to be sophisticated, but it shouldn't be trivial, or your students will miss the point.
bvan 3y ago
Nicely done. I enjoyed reading this.
khaledh 3y ago
There's virtually unlimited resources (books, tutorials, code) on how to build the front-end (lexer, parser) of a compiler, less on semantic analysis, and very little on the back-end (codegen). A program that doesn't emit at least VM bytecode should not be called a compiler, but rather a transpiler. I wish tutorial writers focused more on the backe-end. There's a lot of topics to be covered there that usually don't get the deserved attention: intermediate language, single-static assignment (or a similar IR representation), converting certain patterns to assembly, instruction selection, register allocation, instruction encoding, object/executable file creation. The latter in particular deals with how to structure the program into code sections and map them to virtual memory areas. You also have to deal with symbol tables and symbol resolution (at the linking phase).
- grumpyprole 3y ago
  Agree that compiling to at least a bytecode is preferable. If we don't mind dealing with only expressions or reading Haskell, this one is even tinier: https://tinyurl.com/47stkzvv https://tinyurl.com/47stkzvv
- samsquire 3y ago
  I am a beginner to programming language implementation but here's what I learned. The first two chapters of the LLVM tutorial are good enough to learn the idea of how to implement lexing and parsing: https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index... I wasn't targeting LLVM so I didn't do much except skim the LLVM stuff. This document is good at explaining Pratt parsing which is useful to understand how to parse expressions with precedence. https://abarker.github.io/typped/pratt_parsing_intro.html https://abarker.github.io/typped/pratt_parsing_intro.html At university I wrote a poor motorola 68000 emulator so I had a motorola CPU textbook, so that's how I learned how encoding of instructions worked. I wrote a Java SWING GUI tool to create the opmasks for each instruction component. It was a strange way of doing it but it worked. For AMD64 x86_64 I wrote some GNU Assembler and then reviewed the generated machine code with the following commands. Put C you want the assembly for in example.c: gcc -o example example.c Put your GNU Assembler in example.S gcc -o example example.S Then run and review example-text to see the machine code and opcodes beside the assembly. objdump -dj .text example > example-text I used this page to work out the Mod/RM format for opcodes. https://www.cs.uaf.edu/2016/fall/cs301/lecture/09_28_machinecode.html https://www.cs.uaf.edu/2016/fall/cs301/lecture/09_28_machine... I have a barebones toy compiler here that compiles a simple mathematical expression to assembly: I do simple live range analysis and register allocation. I use A Normal Form as my representation. https://replit.com/@Chronological/Compiler3 https://replit.com/@Chronological/Compiler3 I have the beginnings of a toy JIT compiler here which generates some machine code for MOVs and ADD but I haven't implemented much else... I need to implement C FFI. http://github.com/samsquire/compiler http://github.com/samsquire/compiler For code how I generate an "add" instruction: https://github.com/samsquire/compiler/blob/main/jitcompiler.c#L1210 https://github.com/samsquire/compiler/blob/main/jitcompiler.... I use a case statement to match on the registers opcodes for source/destination and literally insert opcode bytes into a malloced array. You essentially end up with a nested switch statement.
z3t4 3y ago
When people talk about Rust and it's main advantage is no GC I think of FreeBASIC which is much easier, and also has no GC.
sarupbanskota 3y ago
You should submit this to https://github.com/codecrafters-io/build-your-own-x https://github.com/codecrafters-io/build-your-own-x
dang 3y ago
Discussed at the time: Let's make a Teeny Tiny compiler - https://news.ycombinator.com/item?id=23441767 https://news.ycombinator.com/item?id=23441767 - June 2020 (44 comments)

107 points by ingve 3y ago

Writing a transpiler that turns a simple imperative language like Teeny into a simple imperative language like C doesn't feel like a useful exercise at all. Even Lox, that doesn't claim to be a compiler at all, does something more useful: it transpiles code in Lox into Lox VM bytecode. I'd rather transpiler tutorials did something like turning a functional or OO-language into C.

weird_user 3y ago
It's still a useful generic exercise for beginners. Although I recommend starting with a simpler syntax like sexpr, you can get more practice with less code. For a deeper exercise, I recommend compiling to machine code instead of stopping at bytecode [1]; you can learn assembly along the way, which is more satisfying than compiling to C. [1]: https://github.com/byo-books/pretty_laughable_lang/ https://github.com/byo-books/pretty_laughable_lang/
- orthoxerox 3y ago
  I agree that compiling to machine code is super satisfying, but there's a lot of upfront work you have to do before you can run your first "hello world": architectures, calling conventions, object file formats, linking. That's why I no longer object to compiler tutorials stopping at assembly or even C, as long as the phases not present in interpreter tutorials like Bob Nystrom's brilliant one are non-trivial: type checking, optimizations, lowering.
  - samsquire 3y ago
    One thing you can do is implement a JIT compiler. Here's Martin Jacob's code to execute arbitrary memory. If you malloc a byte array and insert opcodes directly at indexes, you can construct machine code and execute it. https://gist.github.com/martinjacobd/3ee56f3c7b7ce621034ec3ecbc8e13f1/fe7e78b89e1581ff15c4d2797662516f281a33bd https://gist.github.com/martinjacobd/3ee56f3c7b7ce621034ec3e... Since your C program is already in memory, you have access to the C standard library and don't have to worry about linking or object formats but you'll have to worry about parameter passing and FFI. My toy JIT compiler based on this idea is here https://github.com/samsquire/compiler https://github.com/samsquire/compiler but it is incomplete.
- grumpyprole 3y ago
  Compiling to LLVM IR is much easier than machine code and would still be satisfying I think.
kwhitefoot 3y ago
Nim compiles to C. It seems very useful to me. It produces small and fast executables. But is a sophisticated language much too big to be used a tutorial.
- orthoxerox 3y ago
  Yes, and like I've mentioned in another comment, it's not a trivial transformation. A tutorial for a transpiler doesn't have to be sophisticated, but it shouldn't be trivial, or your students will miss the point.

bvan 3y ago

Nicely done. I enjoyed reading this.

khaledh 3y ago

There's virtually unlimited resources (books, tutorials, code) on how to build the front-end (lexer, parser) of a compiler, less on semantic analysis, and very little on the back-end (codegen). A program that doesn't emit at least VM bytecode should not be called a compiler, but rather a transpiler. I wish tutorial writers focused more on the backe-end. There's a lot of topics to be covered there that usually don't get the deserved attention: intermediate language, single-static assignment (or a similar IR representation), converting certain patterns to assembly, instruction selection, register allocation, instruction encoding, object/executable file creation. The latter in particular deals with how to structure the program into code sections and map them to virtual memory areas. You also have to deal with symbol tables and symbol resolution (at the linking phase).

grumpyprole 3y ago
Agree that compiling to at least a bytecode is preferable. If we don't mind dealing with only expressions or reading Haskell, this one is even tinier: https://tinyurl.com/47stkzvv https://tinyurl.com/47stkzvv
samsquire 3y ago
I am a beginner to programming language implementation but here's what I learned. The first two chapters of the LLVM tutorial are good enough to learn the idea of how to implement lexing and parsing: https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index... I wasn't targeting LLVM so I didn't do much except skim the LLVM stuff. This document is good at explaining Pratt parsing which is useful to understand how to parse expressions with precedence. https://abarker.github.io/typped/pratt_parsing_intro.html https://abarker.github.io/typped/pratt_parsing_intro.html At university I wrote a poor motorola 68000 emulator so I had a motorola CPU textbook, so that's how I learned how encoding of instructions worked. I wrote a Java SWING GUI tool to create the opmasks for each instruction component. It was a strange way of doing it but it worked. For AMD64 x86_64 I wrote some GNU Assembler and then reviewed the generated machine code with the following commands. Put C you want the assembly for in example.c: gcc -o example example.c Put your GNU Assembler in example.S gcc -o example example.S Then run and review example-text to see the machine code and opcodes beside the assembly. objdump -dj .text example > example-text I used this page to work out the Mod/RM format for opcodes. https://www.cs.uaf.edu/2016/fall/cs301/lecture/09_28_machinecode.html https://www.cs.uaf.edu/2016/fall/cs301/lecture/09_28_machine... I have a barebones toy compiler here that compiles a simple mathematical expression to assembly: I do simple live range analysis and register allocation. I use A Normal Form as my representation. https://replit.com/@Chronological/Compiler3 https://replit.com/@Chronological/Compiler3 I have the beginnings of a toy JIT compiler here which generates some machine code for MOVs and ADD but I haven't implemented much else... I need to implement C FFI. http://github.com/samsquire/compiler http://github.com/samsquire/compiler For code how I generate an "add" instruction: https://github.com/samsquire/compiler/blob/main/jitcompiler.c#L1210 https://github.com/samsquire/compiler/blob/main/jitcompiler.... I use a case statement to match on the registers opcodes for source/destination and literally insert opcode bytes into a malloced array. You essentially end up with a nested switch statement.

z3t4 3y ago

When people talk about Rust and it's main advantage is no GC I think of FreeBASIC which is much easier, and also has no GC.

sarupbanskota 3y ago

You should submit this to https://github.com/codecrafters-io/build-your-own-x https://github.com/codecrafters-io/build-your-own-x

dang 3y ago

Discussed at the time: Let's make a Teeny Tiny compiler - https://news.ycombinator.com/item?id=23441767 https://news.ycombinator.com/item?id=23441767 - June 2020 (44 comments)