Re: Language features for compiler writing was: Java compiler courses

Chris F Clark <cfc@shell01.TheWorld.com> writes:


> Again, let me preface my comments, by saying I think a functional
> programming language like ML or Haskell is probably a best language
> for a first compiler construction course (and perhaps a best first
> language in general). Having said that, I want to backtrack and argue
> some other points (and in the end ask a question).
>
> Not to pick on this particular post, but it brings up issues I want to
> address, so it's the candidate of choice.
>
> torbenm@app-7.diku.dk (Torben Ęgidius Mogensen) writes:
>
>> C is a horrible language for writing compilers due to bad
>> infrastructure for tree and list structures (i.e., GC, polymorphism
>> and pattern matching).
>
> You can get polymorphism, by using C++ as your C. You should be able
> to get pattern matching from your compiler-compiler (or other) add-on
> tool. I don't know that you can in many cases, but you should be able
> to get it, and if you can't that's a fault in the tool chain.


These are all true, but I find that "it's not in the language, but
external tools might/do have it" is not a very good defense for a
language.


> That leaves GC. You can get GC by going to Java (or C# or even
> "managed C++"). More importantly, you can get poor-person's GC in a
> variety of means (the Boehm collector) or a variety of coding
> conventions.


True. Andrew Appel uses this appraoch in "Modern Compiler
Implementaion in C". It has a bit of the above flavour, though.


> Here is the point I want to debate/discuss. What C and its semantic
> (if not syntactic) cousins Pascal and PL1/G have is the ability to
> create a modify complex graph structures (with complex vertexes and
> edges) in place (i.e. by side-effect). (This ability exists in all
> languages where one can explicitly manipulate pointers and not just
> lists.) Now this may be a dubious advantage, but it does make certain
> things work well. There are times I would trade GC for this
> advantage. Now, perhaps this just shows my age. Moreover, I don't
> like trading pointers for higher-order-functions.


SML and O'Caml both have updatable pointers, so you can build and
manipulate graph structures to your heart's content. I agree that
Haskell is a bit lacking here, but people find other structures to
use. Chris Okasaki's book shows a variety of efficient fully
functional data structures.


> So, this is the question, is there an FP technique that allows
> inidividual elements of an array (list, bag, someother roughly
> equivalent structure) to be addressed and arbitrary (i.e. cyclic)
> graphs to be constructed (and rearranged) on-the-fly, but where
> unreferenced elements get collected? If so, where can I learn about
> it?


In SML and similar langauges with updatable references, you can build
and manipulate graph nodes and edges directly. If a part of the graph
becomes unreachable from the root set, it is GC'ed. In Haskell, this
gets a bit more tricky (which is why I use SML for compilers).


Torben

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