Compilers

Discuss compilers and share compiler books. >Have you ever developed your own compiler? >Have you ever worked on or contributed to a compiler? >Are you compiler-curious? What compiler ideas do you have? Tell us about your experiences, frameworks, languages, architectures, etc. (But keep it productive, don’t make rant posts about how your favorite language/framework is god sent and everything else is garbage. No one is going to rewrite anything because of your autism. No one is going to follow your suggestions if it doesn’t solve their problems.) Two books and one tutorial: >Modern Compiler Implementation in (C, Java, ML) This is a theoretical book on how compilers are implemented. Useful if you are not familiar with compiler theory. > LLVM Techniques, Tips, and Best Practices Clang and Middle-End Libraries How LLVM works and how to use it. Not very good but the best I could find. >LLVM kaleidoscope Short LLVM tutorial with C++ and Ocaml versions. Not great. Me: I’m currently contributing to an open source LLVM compiler. It’s written in C++ and as of now we are only targeting aarch64 and x86_64. It has been fun and the community support is amazing, makes me wanna work more on it. Besides that I’ve only done toy compilers with lllvm and toy interpreters in python. One problem is: the LLVM docs are terrible. I’ve read a few of those O’Rilley books but they were not great either. If anyone knows good llvm books or resources I would love to know.

Interesting stuff to me: SBCL, SICL/Cleavir, Clasp and Cranelift.

>>32327 Lisp REPLs are definitely interesting, of those I only know of SBCL and Clasp.

I just want HolyC compiler/interpreter for Linux.

>>32338 Shouldn't be that hard. C is a simple language and AFAIK HolyC doesn't drift too much from it. Also didn't terry develop TempleOS from Ubuntu?

>>32341 >Also didn't terry develop TempleOS from Ubuntu? It's a bit complicated. At first, TempleOS was actually a DOS (TASM) program (and later FreeDOS). Later, Terry indeed used Ubuntu but he compiled everything using TempleOS VM (both VMWare and Qemu) >https://web.archive.org/web/20131217163421/http://www.templeos.org/Wb/Demo/MakeDistro.html Also while looking through the archives, I found these: >https://web.archive.org/web/20160727002917/http://www.templeos.org/Wb/Doc/HolyC.html >https://web.archive.org/web/20160727002811/http://www.templeos.org/Wb/Doc/FAQ.html

What should I know going into a compiler class so that I'm successful? I originally was going to do a lot of statistics electives but I'm retooling for a more generic CS degree. My current choice for technical electives are Interpreters, Compilers, Networking, Databases, and Operating Systems 2, Numerical Analysis I & II and Mathematical Logic, any other suggestions? I would like to do some more computer architecture besides the required one but I can only do about 7 electives, so something has to go for that to happen.

Also you can find write you a scheme v2 by googling it. I don't believe it's available as a PDF just a web page

>>32350 As of lectures: Dragon Book. If you want to be a compiler's demigod and do esoteric languages for fun and profit you might be interested in: [If you are suicidal] - first order logic -> set theory -> formal deduction -> automated theorem proving. The last one might require some topology too. [if you are less suicidal] numeric methods -> so you can write own Mathematica/Octave. If you combine both you can create own Wolfram Alpha. LOL xD You know – you can create dedicated languages that do many different stuff instead of being general purpose - like LOGO, Prolog, SQL, or some operations on graphs. Possibilities are endless.

>>32396 Sounds like I will be doing a lot of this, the path I'm taking has mathematical logic, automata theory, and some numerical analysis before compilers, so I think I'll be ready. Thanks!

I made a compiler for a small subset of ML for my compilers class in college. We had to write it in Haskell. Perfect language for writing a compiler -- if I ever want to write a compiler again it will be ML-like just because it will be more pleasant to write a self-hosted compiler.

>>32401 Lainon who has worked professionally with haskell for compilers before. I actually find MLs to be a weak choice compiler wise. Note how passes are written within an ML style compiler. You either end up over constraining or under constraining the domain due to the limited nature of ML style ADTs.

>>32402 I have no idea what you mean by this. Like you can't write a type system that radically deviates from the Haskell type system?

>>32412 No, what I'm expressing, is that the ML ADT interpretation of a compiler leaves you in a very bad place. Let us consider a simple transformation. Let us say, case is the base branching primitive in your language, and you want to turn if into it. [code] -- Starting AST -- Let us say case is not in data AST = Function AST [AST] | If AST AST AST .... -- New AST data AST' = Function' AST' [AST'] | Case AST' (M.Map Natural AST' ... -- Now let us write a pass on this ifToCase :: AST -> AST' ifToCase (If p t e) = Case .... ifToCase (Function f xs) = Function (ifToCase f) (map ifToCase xs) .... [\code] In the ADT style of passes you can't do incremental changes to an ADT, instead you must copy everything over whole sale. What this means is that every node of your context must switch over. Where this really fails, is when you want to store this data, or do any infrastructure. [code] data Context ast = M.Map Symbol ast [\code] The context of your language would likely be parametrized over the AST representation at any given point. But further think of any higher order functions you may create for your original AST, you can't reuse it for AST' as it's a fundimentally different shape. Due to this, the ML community has come up with many ways to avoid making easy to understand small passes. I saw one compiler just throw out trying to constrain the environment entirely by having 1 AST that has dynamic flags that switch. It is needless to say that all of these are less safe than using a language like lisp, because at least you can abstract over these issues and make transformations more safe structurally. I can go on for quite a while about this issue (Some compilers try Tagless final, Haskell internally uses trees that grow, maybe you try to parameterize your AST, either way it always comes up more cmoplicated than it ought to be costing 10 to 100x more code while making the code less safe).

>>32392 This is extremely interesting, I didn’t know it existed. Thanks!

>>32418 If you take a crack at either of those, let me know how you give it. I'm a self learner exclusively, no academic background and these are my introductions to compilers. I recently got pointed to some stuff with compilers and static program analysis working in Haskell so I'm trying to improve in both those areas.

If anyone can point me towards some good books and resources for intermediate language design, that would be much appreciated. Preferably relatively low level intermediate language design, so three address code and such.

Interesting LLVM tutorial, guy builds a mini lisp https://www.youtube.com/playlist?list=PLlONLmJCfHTo9WYfsoQvwjsa5ZB6hjOG5

I did once implement this CYK algorithm for a school assignment in a course on formal languages, but left college before I was able to do the proper compilers course. To me, however, parsing something still feels a bit like black magic and I'm quite curious about it. I always thought about this general approach of programming the notion of a grammar in general and then applying it to CYK, which apparently generates a parser for that grammar after you do some treatment to it, but reading a few pages of the Dragon Book it looks like one can actually hard-code the parsing algorithm for a given grammar; however, following the logic of doing such a thing completely escapes me... so at the end of the day I have no intuitive understanding of how parsing works.

>>33387 You expect it to be a self repeating tree and thus recursive descent parsers make sense. This probably doesn’t answer your question because I’m not sure what you consider having “a good intuition” is.

>>32311 I want to use some sort of trie (radix tree even) as an AST for my language. I think it would be cool and possible faster for compilation if you could store already evaluated sequences of code. Is there anything that i'm overlooking?

OP here, still working on that same compiler, it’s opening ports in academia and I’m very happy with the momentum the project has. This link is interesting: https://lowlevelbits.org/how-to-learn-compilers-llvm-edition/

>>32311 >Two books and one tutorial: >Modern Compiler Implementation in (C, Java, ML) Avoid both the Java and C version. It was first written in SML and then the code was modified to work for C and Java. They are both horrible and should be avoided at all cost.

Worked for a while on the compiler for a proprietary SQL flavor at a corp everyone here has heard of. It was actually mostly a systems programming role, since a compiler for a database that complex has to also deal with transpiling and distributed environments / a lot of networking code in general. Frontend was written in Flex and Bison, probably due to the compiler's age. It was still nice seeing stuff I used for class in an actual production environment though. Sadly I didn't get to work on the optimizer. We had a very cool fuzzing system for testing based on genetic algorithms, not popular today ofc but it consistently picked up on buggy interactions between the compiler and uncommon system configurations. >>32398 Automata theory / grammars will be the most relevant for a uni course on compilers. Reading up on some basic type theory is a nice complement to that.

Currently looking for any material that will give a good foundation, even if basic Is the dragon book still good or are there other books that do a better job at explaining the theory? >LLVM While the concept sounds interesting it sounds like it's geared towards being productive and achieving X as quickly as possible, while you could probably learn from it. I just want to really understand from the bottom up

>>38925 The key is lots of switch statements while iterating over elements in an array. Null terminated arrays are convenient as the end of the array is just a case instead of having to check the array's size every time you want to look at the next Char/LexerToken/Statement/ExpressionToken.

>>38925 >Dragon Book Not a good resource. Spends most time on parsing and is generally pretty outdated.

Spent a bunch of time at one point working on a (proprietary, alas) C compiler for an embedded microprocessor with a batshit crazy instruction set. We had started with something Clang+LLVM-based, but very quickly ran into impedance mismatches. Things like "surely you can access arbitrary stack locations" and "surely address spaces are purely an optimization" and "surely compare exists without jump" and "surely signed comparisons exist" and "surely every instruction touches a known subset of registers" and such. We also crashed tablegen more times than I care to admit. We ended up giving up and writing our own C89 compiler essentially from scratch with a bunch of "optimal" bruteforcing. Had a bunch of fun features like automatically allocating registers to global variables and extensive WPO. It always compiled a whole program at once and would do fun things across functions like removing dead register writes at the end of functions, allowing functions to clobber registers if the caller didn't mind, coordinating register allocations across functions, changing calling conventions to avoid stack temporaries, etc. All the sorts of things that people normally do by hand for microcontrollers that are infeasible to do well for larger "normal" applications - we were actually significantly beating our previous expert-written assembly code, mainly due to the compiler being able to handle absolutely crazy register allocation restrictions. And when I say crazy I mean it. We were farming out to a sat solver for some of it, because we had things like "if there exists some register with a constant value C, and register Q is allocated to C registers above register R, you can save an instruction". Then the hardware project was canned lol

>>32311 I wrote a Lisp to RISCV assembly compiler for my compilers class in compsci. After graduation i still worked on it for a while, but could never get past function calls and all the context switching thing. eventually got bored and moved on

>>32311 For the compiler for my language I went with "Sea of Nodes" to represent parsed programs, which is a form SSA but in a way I find easier to grasp and reason about than other forms. Each node represents a single operation. Instead of specifying registers as inputs (and outputs) you specify nodes as dependencies. An advantage is that it is easy to perform optimizations while building the graph. For example, before adding a "Or" node I can check if the inputs are constants and perform the calculation right there. There is also no need for a dead code elimination pass, since unused nodes are automatically unlinked and simply don't get traversed. It is also trivial to deduplicate. Just check if a specific node exists before adding it. Picsrel, all in a single pass. (admittedly I haven't yet checked if the generated graphs are correct though).