I mean like: Wow

I've been reading the entire Internet trying to track down how people write compilers, more precisely, parsers and abstract transformers in C/C++.

One post claimed the roughly the following: Compiler construction is a well-defined and finished trivial field where grammar theory is fully developed and compiler writers know very well how to implement the various aspects of compilers.

Then I read various sources, even GCC and CLang. The parsing compiler theory, roughly described as: bottom-up parsing is the most general and serves all your needs, has been abandoned for hand-written PEG recursive descent parsers with infinite lookahead; moreover, all pretty LALR and other compiler generation tools have been abandoned and rot away. Nobody knows what the best manner of representing an AST in C++ is and people patch the weirdest solutions together to write recursive descent parsers. I haven't even started on semantic analysis.

If all problems are solved then all the code I just read doesn't show it.

Term Rewriting using the Visitor pattern ist Verboten

I've been looking into what the correct manner of downcasting is in C++. Unfortunately, downcasting is only allowed on pointer or reference types and then in a manner I don't really like yet.

Still, I need it. Rewriting a term is best done functionally for various reasons. If you cannot imagine why, and I've seen a lot of people advising against it, and you propose a visitor pattern then you're an idiot.

Not convinced you're an idiot? Even Stroustrup agrees on that.

Which is the problem with the Internet these days. It used to be that I could google or post a question to a mailing list and get an informed answer within a few hours. These days, with widespread programming education, the Internet is full of idiots and bad advice.

So I am not sure what the proper manner of downcasting terms in C++ is. Another small puzzle.

Rewriting Terms in C++?

Given that I am now writing a compiler in C++ the question of term rewriting and following RAII comes up. A typical scenario following RAII is given below.

Say your simple term language has elements like this:

class AppTerm: public Term {
public:
     AppTerm(const Term &l, const Term &r): _left(l), _right(r) {};

     Term left() {
         return _left;
     }

     Term right() {
          return _right;
     }
private:
     Term _left;
     Term _right;
}

Then, since most compilers do a lot of term rewriting, you'll have an enormous amount of code like:

Term rewrite_app(const AppTerm &t) {
     SomeResult r0 = rewrite_term(t.left());
     SomeResult r1 = rewrite_term(t.right());

     // do something

     return AppTerm(r0.value(), r1.value());
}

If I get C semantics right, then r0 and r1 will go out of scope and the resulting term will receive copies of whatever was constructed in the rewrite of both constituents of an application term.

I say it again: copies. Think about that for a moment. Copies.

If every copying rewrite function is going to copy entire terms for each intermediate step, as I think it will do when implemented naively, you're going to have one hell slow compiler.

Did I get C++ semantics right? The only way out is to use smart pointers it seems.

A C++ interpreter/compiler with an LLVM back-end

After an old-school bootstrap of the compiler I wrote, I decided I did it all wrong. Doing it right would imply creating an interpreter/compiler in C/C++.

The major lesson here: Despite academic enthusiasm, old-skool bootstrapping is awful and extending a bootstrap compiler is even more awful.

The major hurdle I needed to take: my language is that good that I didn't feel like doing it all in C/C++ again.

Last week, I took the plunge. Starting on an interpreter/compiler in C++ which will hopefully have an LLVM back-end.

There go another few years of my life. I feel good about it.

Elalang

I came across Elalang on LtU, which apart from meaning Hi language in Greek, has a lot more in common with my language than I thought. The language is a strict, sometimes lazy, dynamic variant of ML or Haskell. It runs on .Net by compiling to bytecode for the CLI.

The funny thing is that I designed the Hi language to be executable even if you erase all types. Apart from that that gave me the time to experiment with the typechecker while bootstrapping the language, it also means that when you would compare the informal cores of both languages, Ela Core would implement an extended form of the Hi language. Basically, untyped lambda calculus evaluated strictly with some Haskell class like mechanism for dynamic dispatch, where Ela Core would be more expressive since it allows to dispatch on the return type of functions. A good thing for generality, but something I didn't design into Hi since I wanted a simple mechanism to dispatch on the type of values; basically following OO in order to make it possible to bind to C++ libraries without too much problems. Hi has OO like interfaces, not Haskell, or Ela, like type classes.

(The meaning of the above: I could simply translate Hi to Ela with some syntactic transformation on the source code; i.e., almost by copy pasting Hi source code. The OO like interfaces also imply I can typecheck with an adaption of F<:. So I guess I should stop mucking about and just implement a version of that; mind you, not even that is trivial.)

I am not sure about robustness or performance of Ela. I read it emits bytecode for a stack machine, which shouldn't be possible, higher order programming implies you'ld normally want some kind of heap.

(What I forgot to say. I like Ela. The fact that it is a dynamic variant of Haskell is really, really nice. You can do tons of tricks you can't do in a strongly typed language, and the runtime performance penalty can't even be that big, in theory, since it's all tagged graph manipulation abstractly anyway.)

The Spinners-I'm Working my way through Types and Programming Languages

Functional Secrets at Intel