|Converting languages to a purely functional form email@example.com (Dobes Vandermeer) (2003-07-15)|
|Re: Converting languages to a purely functional form firstname.lastname@example.org (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 email@example.com (Patryk Zadarnowski) (2003-07-21)|
|Re: Converting languages to a purely functional form firstname.lastname@example.org (2003-07-21)|
|Re: Converting languages to a purely functional form email@example.com (2003-07-23)|
|Re: Converting languages to a purely functional form firstname.lastname@example.org (Thomas David Rivers) (2003-07-23)|
|Re: Converting languages to a purely functional form email@example.com (Joachim Durchholz) (2003-07-25)|
|From:||Patryk Zadarnowski <firstname.lastname@example.org>|
|Date:||21 Jul 2003 21:38:48 -0400|
|Posted-Date:||21 Jul 2003 21:38:48 EDT|
On Thu, 15 Jul 2003, Dobes Vandermeer <email@example.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
> 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
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.)
Patryk Zadarnowski University of New South Wales
<firstname.lastname@example.org> School of Computer Science and Engineering
<email@example.com> Programming Languages and Systems Group
Return to the
Search the comp.compilers archives again.