Re: Converting languages to a purely functional form

Dobes Vandermeer <dobes@dobesland.com> wrote
> Purely functional programs are, as far as I can tell, much easier to
> operate on programmatically than regular procedural ones. Loops,
> destructive updates, etc. make many kinds of very powerful analyses
> rather difficult.
>
> This makes a pure functional language useful as a kind of intermediate
> representation.
|
> To eliminate destructive updates, you'd have to change every function so
> that it took in each global/member variable it read, and returned every
> one that it wrote.


Take a look at http://www.inf.ethz.ch/research/dissertations/show.php?type=diss&what=11024&lang=en


Marc Brandis' dissertation is focusing on creating an optimizing
Oberon compiler that use Static Single Assignment as an intermediate
form.


His compiler transforms the Oberon program into SSA by using an
algorithm that creates a new variable for each modification, then
applies its optimizations, and transforms the parse tree back into
a form that uses destructive updates. The reason for using SSA
was specifically that it allow program analysis and transformations
for the purpose of optimization to be simplified dramatically in
some cases.


> To eliminate loops, you'd have to replace them with tail-recursive
> function calls.


I'm not so sure this would help you significantly with
transformations.
As long as loops are single entry/single exit they are fairly easy to
deal with.


> To eliminate goto & break you'd have to add conditionals to escape and
> enter blocks.


The above mentioned dissertation took a shortcut here, and just
removed the offending features from the language... Obviously that
won't be an option for everyone :)


> The main problem here, is that once you've analysed all the data flow
> information you get from this conversion, you'd want to be able to
> generate efficient code anyway; e.g. you's still want to generate loops,
> not tail-recursive function calls. This might entail some serious
> additional optimizations/analyses just to get back where you started.
>
> Thoughts/Comments/References?


As I mentioned, I'm not sure what you gain from removing loops. If
you don't your main problem is destructive updates, and there the work
that has been done on static single assignment helps a lot.


Essentially transforming from SSA to a form that allows destructive
updates is a matter of applying an algorithm similar to register
allocation, and can leverage much of the research that have been done
on that subject.


The primary difference is that each time you find a case that would
cause register spill, you treat the memory it spills to as a
"secondary" register set that happen to be mapped to memory, and which
have the property that cases that would cause spills from it cause you
to expand the set.


Once you're done, you will have a new symbol table that represents
the storage requirements of the function.


This method has the potential added advantage that memory can be
reused for multiple variables through a function if the code is
ordered in a way that leave certain variables unused through parts of
the function, so this process might reduce your stack usage as well as
an added bonus.


Vidar

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