Re: Why ML/OCaml are good for writing compilers

Amit Patel looked at AST's used in a compiler written in C and wrote:
> I was one of three students in my compilers class that used ML instead
> of C. I didn't know ML at the time, but I had to learn it and
> compilers simultaneously. Some time later, I looked at what C
> compiler code looked like, and I was *shocked*. It was incredibly
> ugly in comparison to what I had seen in ML.
. . .
> Perhaps some other structure would have worked better, but I haven't
> seen any parse tree representation in C or C++ that's both type safe
> and feels "right".
. . .
> ML's data structures (tagged unions) are *perfect* for representing
> abstract syntax trees, but I think pattern matching is the real win
> here.


Personally, I agree with your analysis of the data structure problem.
However, I would like to note that it is not unique to ML, although
some characteristics of ML are well suited to it. You can build the
same data structure (a tagged union) in C++ (C, Pascal, . . .). In
addition, with C++ you can use virtual member functions to help with
the selection problems, so that each type of node can return exactly
the right field (or calculation) for each type of query. With non-oo
languages virtual member functions can be simulated to get the same
effect.


In any case, several parser generators support building tagged union
AST's. The two I am most familiar with are Cocktail and Yacc++. At
the OOPSLA workshop on object-oriented compiling techniques I wrote
about the Yacc++ AST model (and compared it to the Cocktail model, as
they have some slight differences). The other day I ran across a copy
of that paper on the web--I thing Doug Lea had it saved somewhere.


BTW, the down-right model of AST's you saw in the compiler written in
C, may have been an artifact of PCCTS use. PCCTS has built-in support
for creating AST's of that type. While I prefer the tagged union
model, the down-right model has its advantages also. BTW, I have heard
the PCCTS model for AST's called "lispy" due to the fact that it is
similar to the conventions for cons-cells in lisp (down=car,
right=cdr).


Disclaimer: I was one of the co-authors of Yacc++, so it reflects my
biases and thus I am biased toward the choices it makes.


-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres
--

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