Translating imperative to functional code

Question

I need to write a program that will translate imperative code to pure functional style. I'm not worried about I/O - I have some solutions in mind for that - but I do need to deal with heap objects as well as local variables.

I suppose it could be done by passing a TheWorld object with every function call and return, and then optimizing from there, trying to remove that parameter from functions where it's not used etc. But is there a known better way of doing it?

Magnet

Out of interest, why do you need to do this? – Kept

@Marcin, it is a common approach to static analysis, for example. Btw., was it your downvote? – Cerveny

What I'm trying to do is automatic code analysis, optimization and parallelization, for which I need to solve the problem 'what function does this chunk of code compute', which it seems to me is equivalent to the problem of translating it into pure functional form. – Magnet

@rwallace: Seems like a reasonable approach. Is this going to be public in any way (because I'd be curious to see what you come up with)? – Kept

Yes, it's going to be published as open source once I've got something working. – Magnet

have you got something working? :) – Roadwork

@ErikAllik Unfortunately not yet; it turns out there are a number of other problems that need to be solved before that can be done in a useful way. – Magnet

I see! like what problems? – Roadwork

@ErikAllik Too big a discussion to fit in stackoverflow comments :-) but one issue is that of bootstrapping - it does no good to write a superoptimizer in a style that implicitly assumes it will be compiled with a superoptimizer. – Magnet

oh, right, if superoptimization is your goal, then yes — my goal is simply mapping e.g. a restricted subset of Python code to a Haskell DSL, so that people can effectively write with Haskell semantics but using Python's syntax and some of its more basic idioms. – Roadwork

Answer 1

As SK-logic points out, you can represent you imperative program in SSA form.

However, rather than applying the CPS transform, you can directly transform the imperative SSA representation into an equivalent purely functional program in "Administrative Normal Form" -- a restricted functional language, based on the algorithm published by Zadarnowski et al.

The two languages are given by:

See: "A Functional Perspective on SSA Optimisation Algorithms", which gives algorithms for automatically translating programs in SSA form to ANF.

Tonguelashing

Answer 2

There is a number of ways to do such a translation efficiently. First, it worth doing an SSA transform with a consequent CPS transform: this way you'd get a bunch of trivial mutually recursive functions out of an imperative code with variables and branches. Function calls (and even virtual calls) can also be CPS-ed easily, by passing a continuation parameter instead of relying on an implicit stack semantics.

Arrays can be handled the same way as variables, prior to an SSA transform all the array access should be replaced with get and update function calls, which should have an implicit copy semantics (but beware of an aliasing in this case). Same for structures.

And only for those cases where it is impossible to maintain a copying semantics you need to have this TheWorld object which should keep all the allocated objects and should be copyied entierly each time you're modifying one of them.

Cerveny

Upvoted, seems like a reasonable approach, though one thing I don't quite get, is there a reason for wanting to CPS everything? Functional programming normally relies on an implicit stack semantics after all, doesn't it? I haven't personally worked with CPS before, but the references I've seen to it, typically suggest it's used for the reverse, compiling functional code to an imperative target platform? – Magnet

@rwallace, it is much easier to reason about an explicit CPS rather than an implicit stack. And SSA is already equivalent to CPS, you only have to infer the values liveness ranges to transform from one to another. – Cerveny

CPS is definitely easier to reason about than an implicit stack with all the machinery of an imperative programming language, but is CPS really easier to reason about than pure lambda terms? If so, why? – Magnet

@rwallace, it is mainly a practical observation. Having an explicit continuation at any point allows to easily predict, what values from the current context are captured and going to be used further. And another reason is that you'd need another step to do a reverse transformation if you've already done an SSA memory to register promotion. – Cerveny

Answer 3

In many functional programming languages, it's possible to replace a series of local variable assignments with a series of let expressions.

For example, this C function could be translated in this way:

int example(int a,int b){
    a += 1;
    b += 2;
    if(a == 1){
        b += 1;
    }
    else if(b == 1){
        a += 1;
    }
    return a + b;
}

An equivalent function in the Futhark programming language could be written like this, using a record data structure to store the local variables:

let example a b =
    let vars = {a,b} in
    let vars = vars with a = vars.a + 1 in
    let vars = vars with b = vars.b + 2 in
    let vars = (if vars.a == 1 then
        let vars = vars with b = vars.b + 1 in
        vars
    else if b == 1 then
        let vars = vars with a = vars.a + 1 in
        vars
    else
        vars)
    in vars.a + vars.b

In some cases, it's also possible to convert a series of imperative statements into a single arithmetic expression. In Prolog, this can be done by replacing subterms:

:- use_module(prolog_vars_list).
:- set_prolog_flag(double_quotes, chars).
:- initialization(main).

main :- 
    To_solve = (Z=11,
    Z=Z*2,
    A=1+A,
    A=A+2,
    A = Z+1,
    A = A * 2,
    A=A+3+Z+P),

    run_imperative(To_solve,B),
    
    %print the input
    writeln(To_solve),
    
    %now print the output
    writeln(B).

run_imperative(A,B) :- imperative_to_declarative(A,_=B).

imperative_to_declarative((A,B,C),D1) :- 
imperative_to_declarative((B,C),D),imperative_to_declarative((A,D),D1).

imperative_to_declarative((A=A1,B=B1),(_=C)) :-
    replace(A,A1,B1,C).

replace(Subterm0, Subterm, Term0, Term) :-
        (   Term0 == Subterm0 -> Term = Subterm
        ;   var(Term0) -> Term = Term0
        ;   Term0 =.. [F|Args0],
            maplist(replace(Subterm0,Subterm), Args0, Args),
            Term =.. [F|Args]
        ).

There are also several ways to to implement while-loops using monads or recursion.

Cortese