Re: Converting languages to a purely functional form

Joachim Durchholz <joachim.durchholz@web.de>
17 Jul 2003 00:34:40 -0400

          From comp.compilers

Related articles
Converting languages to a purely functional form dobes@dobesland.com (Dobes Vandermeer) (2003-07-15)
Re: Converting languages to a purely functional form joachim.durchholz@web.de (Joachim Durchholz) (2003-07-17)
Re: Converting languages to a purely functional form derkgwen@HotPOP.com (Derk Gwen) (2003-07-17)
Re: Converting languages to a purely functional form dobes@dobesland.com (Dobes Vandermeer) (2003-07-21)
Re: Converting languages to a purely functional form pat@jantar.org (Patryk Zadarnowski) (2003-07-21)
Re: Converting languages to a purely functional form vidar@hokstad.name (2003-07-21)
Re: Converting languages to a purely functional form lars@bearnip.com (2003-07-23)
Re: Converting languages to a purely functional form rivers@dignus.com (Thomas David Rivers) (2003-07-23)
[1 later articles]
| List of all articles for this month |

From: Joachim Durchholz <joachim.durchholz@web.de>
Newsgroups: comp.compilers
Date: 17 Jul 2003 00:34:40 -0400
Organization: Compilers Central
References: 03-07-098
Keywords: analysis, functional
Posted-Date: 17 Jul 2003 00:34:39 EDT

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.


Just my 2c.


> 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.)
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.


The advantages of functional programming come from better abstraction
facilities, i.e. they are in the domain of the human mind, so a
functional language doesn't "get [you] back where you started" (except
if you narrow the perspective down to compilers).


The efficiency problems are compensated because all data can be shared,
so the need for copying data is greatly reduced; this effect increases
with software size, and can range from overcompensation to not-quite
compensation to truly horrendous performance (in which case one rewrites
the algorithm: it's always possible to gain at least acceptable
performance).
Sharing will happen only if the programmer uses it, so it's unlikely
that an automatic transformation of imperative programs will gain many
advantages.


Just my 5c.


Regards,
Jo


Post a followup to this message

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