Re: Implementation Language Choice

Kevin Albrecht wrote:
> I am an experienced compiler/interpreter writer, but have always
> written my compilers in C/C++ so far. As almost everyone will admit,
> C/C++ are hardly ideal languages. I am considering writing my next
> compiler in some other language, but I am unsure of what language to
> use. What languages have others found useful as implementation
> languages?
>
> The following features are important to me in a choice for a better
> implementation language:
>
> * mature compiler(s) that produces native-code binaries
> * open source - preferable, but not 100% necessary


Several observations, which are related to the backend
(i.e. everything after the parser).


Optimizations have to be done *fast*; even when doing whole program
compilation of very large programs (100kloc+), users expect compile
times of at best a few minutes. And for the case of compiling single
large files (say 10kloc) people expect compile times to be
considerably under a minute, even with all optimizations turned on.


With the more aggresive optimizations, memory usage will be quite
large. If you're doing whole program analysis, you could easily
exceed 0.5 GB.


Both of these suggest that you need to worry about both performance
and memory usage. Of course, if you're dealing with small compile
units, and simple optimizations, then this may not be an issue.


Also, in the backend, you don't need too many data-types. For
instance, in our current compiler, other than collection classes, we
have 29 core data-structures (i.e. IRs + symbol-table). Not only is
there no inheritance, there is no opportunity for inheritance.


We have to do a little bit of work to get strongly typed collection
classes, but its relatively straight-forward.


In the backend, there are very few unions, and no anonymous unions.


Based on previous compilers, there is one place where unions, typed or
otherwise, would have been applicable - in the representation of
constants. We get away from that by a couple of things:
- In general, the IR is "strongly-typed" - i.e. if a constant appears at
some point, it can only be of a particular type.
- All constants are represented as strings. Thus, if an add has an
immediate argument, 4, it is represented by the string "4". This allows
us to treat all constants identically for the most part, at the cost of
having to convert from the string representation to the actual constant
when needed (though, of course, we do optimize this conversion).


Traversals are broken into two steps: we walk the IR, gathering all
elements into an array, and then iterate over the array. Thus, we do
things like:
      n = size_graph(G);
      nodes = alloca(n * sizeof(Node *));
      post_order_depth_first_walk(G, n, nodes);
      for( i = n-1; i >= 0; i-- ) { /* reverse post order dfs */
            do_something(nodes[i]);
      }


Summary: if you're worrying about the language in which to write a
compiler, you've probably got more serious problems. I've written about
7 serious compiler/interpreters/translators in C, LISP and C++, and IMO
C is the best language for writing compilers.


If I had to pick a second-best, it would probably be Ada-95.

Return to the comp.compilers page.
Search the comp.compilers archives again.