1. 72
  1. 19

    Speaking of “mind-bendy”, the formal version of “write an interpreter, then change it to a compiler” is called the Futamura projection, and it will really bake your noodle.


    1. 4

      And if that’s interesting, also check out “tracing JITs”, which are a somewhat different (and currently I think more popular) way to turn an interpreter into a compiler.


      1. 1

        If I did bootstrapping, that’s what I was going to do. It seemed like it might let me dodge most of learning assembly past whatever was in the interpreter. Modified version just creates different combos of same instructions which are strings. Probably still need a tool to generate the rest of the ASM file. Can’t be as hard as really learning compilers and assembly.

        1. 2

          You should take a look at RPython.


        2. 1

          Does f2c fall into this as well? The old AT&T Fortran to C compiler thing?

          1. 2

            I don’t think that involved an interpreter — it was just a compiler with a C back end (what the kids today might call a “transpiler”, though I find that term ill-defined and confusing).

        3. 3

          Wrote my comment and saw yours. The PE book is on my bucket list: https://www.itu.dk/~sestoft/pebook/pebook.html.

        4. 8

          If you haven’t come across it, I also highly recommend Bob Nystrom’s book Crafting Interpreters, available for free. It has two parts: first he goes over building a tree-walking interpreter in Java then he goes over building a bytecode compiler & VM in C.

          This second part is still a work-in-progress but he’s kept a strong pace, last chapter was released about a week ago.

          Thank you for the great write up. I’m on a similar learning path and I really enjoyed it and got me excited to write my own compiler as well!

          1. 6

            I’m hoping to get the chapters done by the end of 2019. If you’re impatient, all of the code for the entire book is already done. (In fact, I wrote all of the code and carefully split it into chapters before I wrote the first sentence of prose.)

            You can see it all here: https://github.com/munificent/craftinginterpreters/tree/master/c

            1. 2

              Thanks! I had briefly noticed Crafting Interpreters before, but I’m glad to hear it’s worth a second look.

              Thanks for the kind words, and I hope you will continue on your journey!

            2. 6

              Really nice post, regarding:

              Writing C code and trying to keep it indented was a bit of a pain and I wish I would have done something else. I believe some compilers write ugly code and then “pretty it up” with a library before writing it out. This is something to explore!

              you can use clang-format.

              1. 3

                Cool, I’ll check it out! It’d be nice to find some library code or something I can depend on cross-platform though. Maybe I’ll consider writing my own bit of C tidying code.

                1. 3

                  There’s also indent, multiple forks of it actually. Most advanced are (in no particular order) GNU indent, FreeBSD indent(1), and cindent.

                  1. 2

                    Oh cool! This looks like something I can use!

                2. 2

                  The nice thing about writing your compiler in elisp is you have all the indenting functionality you could ask for all built-in.

                  (please don’t do this)

                  1. 2

                    Steve Yegge famously(?) wrote a JavaScript Parser / analysis engine in Elisp to make js2-mode.el. Can’t be that bad. :)

                3. 3

                  Good stuff. Outputting machine code for amd64 isn’t too bad, you only need a small subset and the Intel manual is pretty good. Writing a JIT might be a nice next step, sort of combining an interpreter and a compiler. Unfortunately there isni’t much information out there about JITs.

                  1. 2

                    Working with incremental compilation really got me thinking about JITs. Definitely something I’m interested in learning more about!

                  2. 2

                    This compilator produce program for RISC-V or x86?

                    1. 3

                      I think it uses Tiny C Compiler which generates x86

                      1. [Comment from banned user removed]

                        1. 5

                          Yes it is a compiler, it just uses tiny C as an intermediate language and TIny C as its backend.

                    2. 2

                      Great write-up. With a bit more mind bending one gets to partial evaluation and the Futamura projections. Your steps by step guide sounds very much like writing a partial evaluator that specializes the interpreter but instead of doing it with code it is done by a human.

                      1. 1