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

Chris F Clark <cfc@shell01.TheWorld.com> wrote:
> 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?


All functional programming languages support bona fide mutable graphs,
but if you want a "true FP technique", then you may find the following
paper interesting:


http://www.eecs.harvard.edu/~nr/pubs/zipcfg-abstract.html


An Applicative Control-Flow Graph Based on Huet's Zipper


Norman Ramsey and Joćo Dias


We are using ML to build a compiler that does low-level
optimization. To support optimizations in classic imperative
style, we built a control-flow graph using mutable pointers
and other mutable state in the nodes. This decision proved
unfortunate: the mutable flow graph was big and complex, and
it led to many bugs. We have replaced it by a smaller,
simpler, applicative flow graph based on Huet's (1997)
zipper. The new flow graph is a success; this paper presents
its design and shows how it leads to a gratifyingly simple
implementation of the dataflow framework developed by
Lerner, Grove, and Chambers (2002).


Their graphs are not cyclic data structures, since a reference from
one basic block to another are represented by a label which must be
looked up from a map, but that doesn't seem to be a great hindrance,
since basic blocks eventually need explicit labels anyway.




Lauri

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