1
$\begingroup$

I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional program/style I mean one in which all objects are immutable and functions are pure, and so forth.

The only example I've seen so far of translating imperative code to functional code is for highly specific and simple code. In particular, the example that seems to be used a lot is the factorial function, and translating iteration into recursion:

//imperative -- iteration
int factorial (n)
   for i=1;i<n;i++
      x=x*i;
   end for
   return x;

//functional -- recursion
int factorial (n)
    if (n==1) return 1; else return factorial (n-1) * n

However, this is such a specific example of a function (the factorial), that it doesn't make it clear to me how in general to translate core constructs in imperative style to functional style. e.g. can we always translate a for loop into recursion?

I'm looking for a comprehensive textbook or other resource that in generality shows how to translate imperative code to functional code

  • How do we translate the basic building blocks of imperative code to functional code? Can we even do this in general?

  • How do we translate some examples of not-completely-trivial (e.g. not the factorial function) programs?

  • Especially interesting, are there fully general automated algorithms for doing these translations? Are they actually used? I can imagine that some compilers do something like this.

  • (perhaps also interesting, the opposite, translating functional code to imperative code.)

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ I think you need to be more specific. Translating to pure functions is always trivially possible: just express every imperative statement as a (State -> State) function. The other direction is also done by any existing compiler of any pure functional language. $\endgroup$
    – Dmitri Urbanowicz
    Commented Mar 1, 2020 at 8:11
  • $\begingroup$ Are you familiar with the State monad? If not, read that first and come back asking more. (Because the state monad is not the whole story, we also need to deal with local state.) $\endgroup$
    – Andrej Bauer
    Commented Mar 1, 2020 at 9:36
  • $\begingroup$ I believe the right question is why, not how. (a) A program in a high-level language in any style is translated into machine code (processor's PL) in order to be executed, and machine code is imperative. So you do not need this translation for PL implementation. (b) I do not think that any style is superior to others. What style is the best depends on the problem at hand. Hence translation likely will not improve the quality of a code. $\endgroup$
    – beroal
    Commented Apr 10, 2020 at 15:35
  • $\begingroup$ @beroal, for me, my why is simple: I just like to know how to write a program that I know how I would write it imperatively, how to write it functionally instead. A textbook on how to translate would clarify this for me. $\endgroup$
    – user56834
    Commented Apr 10, 2020 at 17:40
  • $\begingroup$ But why do you need to write it functionally? $\endgroup$
    – beroal
    Commented Apr 13, 2020 at 13:08

2 Answers 2

Reset to default
2
$\begingroup$

There probably are automated ways of doing it, but the result will be a unreadable mess. You have to understand what the imperative program is doing and rethink it as a functional program. Not easy.

The point is that many imperative algorithms have a recursive idea behind them (think binary search, mergesort, quicksort, any tree walking), there it is recognizing that starting point and write it functionally.

First rule I try to impress on my students: Programs aren't for the computer's consumption, they are principally for ḧuman understanding. Humans will have to write it, and modify it if it turns out wrong (be it a bug or a change in requirements). Today the human's time is much more valuable than the computer's (How much does a computer cost? How much does it's time cost, assuming a life of two years? Take any random program, how often will it have to be run to make up for your salary of a week, if that is what it takes to make it twice as fast?).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you! Do you know of a good textbook that explains how to do these translations in a good way? $\endgroup$
    – user56834
    Commented Mar 2, 2020 at 5:40
  • $\begingroup$ There is no translation. As this answer says: you need to understand the original problem, then solve the problem in a functional manner. Any sort of "translation" will at best be non-idiomatic and un-elegant, but more likely be completely unreadable. $\endgroup$
    – Jörg W Mittag
    Commented Mar 8, 2020 at 8:52
  • $\begingroup$ @JörgWMittag, I am just using the word "translation" for this process of "understanding the original problem and solving it in a functional manner", but ok I'll not use that word, and instead call it "redesign" or something. Is there a good textbook on this? $\endgroup$
    – user56834
    Commented Mar 11, 2020 at 6:02
1
$\begingroup$

The lambda calculus is Turing-complete. The proof of this fact gives an automated way to convert imperative code to functional code. The resulting functional code will be a mess and not understandable to humans, but it exists, and the translation is purely automatic.

In general, the strategy is to implement an interpreter for a Turing machine (or any other Turing-complete computing platform, such as a small CPU) in the lambda calculus. This is a straightforward matter of programming. See e.g. https://stackoverflow.com/q/9619139/781723, Why are functional languages Turing complete?.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.