Consider the following program in "mutable style":


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


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

Following your scheme we get the non-sensical:

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

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

  • $\begingroup$ my suggestion wasn't literally just to change variables everywhere. This was just a simple example. But if it's really true that the state monad can be used for arbitrary programs, then that answers my question, thanks! $\endgroup$ – user56834 Apr 8 '19 at 14:53
  • $\begingroup$ @user56834 The state monad interacts poorly with concurrent programs. $\endgroup$ – Derek Elkins left SE Apr 8 '19 at 15:09
  • $\begingroup$ @DerekElkins: State interacts poorly with concurrent programs. $\endgroup$ – Andrej Bauer Apr 8 '19 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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