Translating imperative to functional code

user_45843 0
Viewed 2837

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?

code-translation compiler-construction functional-programming
3 Answers

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.

user_9750970
Related