"Immediate" method of translating arbitrary mutable program to equivalent unmutable program?

Consider the following program in "mutable style":

x=1
x=f(x);
x=f(x);

We can rewrite this in "immutable style" without changing the higher-level structure of the program:

x1=1
x2=f(x1);
x3=f(x2);

We turned it into an immutable style program by only making "local changes": We simply took the mutable variable $x$ and changed the program wherever $x$ appeared to make it immutable.

Question: Can we in general turn an arbitrary mutable program into an immutable program by only making local changes, so that the higher level structure of the program stays the same?

• Obviously this will depend on the language. You may assume any language features you want. e.g. this answer talks about monads (though it's not clear to me whether they can always be used to translate programs using only local changes).

The state monad allows us to translate any stateful (you call it "mutable") program to a pure one. The changes required to the program are "local" in the sense that you only need to make superficial changes to the syntax, assuming you use Haskell-style do notation. For example, the following is the Haskell translation of your program into a pure program:

do x <- 1
   x <- f x
   x <- f x

You think you can make your transformation by renaming variables, but this will not do when recursion or loops are involved. For example, it is not clear how to use your idea here:

s = 0
i = 0
while (i < n) do
   s = s + i
   i = i + 1
done

Following your scheme we get the non-sensical:

s1 = 0
i1 = 0
while (i1 < n) do
   s2 = s2 + i1
   i2 = i2 + 1
done

You need to think more carefully about your idea (and I don't see how to make it work).

StackExchange Computer Science Q#106646, answer score: 3