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?

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.