Re: Converting languages to a purely functional form

On Thu, 15 Jul 2003, 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.
>
> 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.
>
> 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.


There hasn't been all that much research in this area (although from
experience there's a lot of interest in bridging the gap between the
two research groups - functional and imperative, so this will
hopefully change.)


Make sure that you read:


          Chakravarty, Keller, Zadarnowski "A Functional Perspective on
          SSA Optimization Algorithms" (COCV 2003)


          Appel "SSA is functional programming" (ACM SIGPLAN Notices 33, 1998)


          Kelsey "A correspondence between continuation passing style and
          static single assignment form" (ACM SIGPLAN Notices 30, 1995)


All should be googlable. For the first one, check out:
http://www.cse.unsw.edu.au/~patrykz/ssa-lambda/ which includes a link to a
little lab toolkit for playing with functional representations that I wrote
for the COCV paper.


Basically, you're right that lambda calculus is great for representing
data-flow information - in fact, most modern compilers are heading
that way already (SSA, VDGs, VSDGs are all functional languages on
drugs.) You're wrong about goto's and breaks - semantically they're
just tail-calls, and in our work we use a variant of direct-style
lambda calculus (ANF) that distinguishes them from proper function
calls, so translating ANF to assembly language is an almost-trivial
1-to-1 mapping (the hard part is dealing with register allocation,
which I'm investigating now.) Remember: at the end of the day, in a
low-level IR you don't have loops anyway; just jumps (tail-calls.)


Pat.


-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Patryk Zadarnowski University of New South Wales
<pat@jantar.org> School of Computer Science and Engineering
<patrykz@cse.unsw.edu.au> Programming Languages and Systems Group
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

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