Re: Converting languages to a purely functional form

Joachim Durchholz wrote:
>
> Dobes Vandermeer wrote:
> > This makes a pure functional language useful as a kind of intermediate
> > representation.
>
> Agreed.
>
> > 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.
> >
> > To eliminate loops, you'd have to replace them with tail-recursive
> > function calls.
> >
> > To eliminate goto & break you'd have to add conditionals to escape and
> > enter blocks.
>
> Agreed.
> BUT: I'd expect that a program transformed in this way is just as
> difficult to optimize as in original form. Transformation into a
> functional equivalent will just make the interdependencies explicit,
> they still have to be taken into account.


Well, I suppose loop-invariant removal and strength-reduction might
become more difficult!


I was thinking about compile-time garbage collection when I came up with
this idea -- compile-time garbage collection becomes feasible when you
have all this information.


> > 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.
>
> Tail call elimination is trivial in functional languages. (Well, nearly
> so: there's a lot of devils in the details. But it doesn't require
> global analysis.)


Well, ideally you'd eliminate the extra stack frame/parameter list not
just for loop's recursive calls, but also for the loop's entry/exit in
the function it was originally defined in. Maybe its still trivial, I
haven't looked into it.


> IIRC, regaining in-place updates is undecidable in general, can still be
> done, but is difficult to do well. It can require global analysis, so in
> a world of third-party libraries in binary form, this will quickly hit
> limits.


Well, if you've preserved the semantics of the in-place updates, and
you're doing compile-time re-use analyses, then replaced fields could be
re-used with their new value, as long as code isn't transformed to keep
a field "live" beyond its assignment.


I think the conversions I was talking about earlier already require
global information; to support destructive updates any updated field has
to be returned from the function would normally destructively update it,
and global variables would have to be passed in if the function might
need their value. This includes the transitive closure of the same
properties for all functions potentially called by a function as well.


CU
Dobes

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