2
$\begingroup$

Can we implement every algorithm using only immutable variables such that their space and time complexity is the same as using mutable variables?

$\endgroup$
  • 1
    $\begingroup$ Depending on exactly what you mean by 'algorithm', I suspect the 'negative result' mentioned at cs.stackexchange.com/q/18262/755 might constitute a proof that the answer is 'no', but I haven't checked the details. $\endgroup$ – D.W. Feb 25 '18 at 4:06
4
$\begingroup$

Probably not, but I don't know if this has been definitely proven, and it depends on what you'll allow as "using only immutable variables".

In 1997 Pippenger published Pure versus Impure Lisp (Technical Report). This paper gives a negative answer when the programming language is Lisp with and without mutation (RPLACA and RPLACD) under some restrictions, namely the program consumes and produces sequences of atoms, and the program must be on-line meaning given potentially unbounded sequences as input, the program must output the $n$th output before consuming the $(n+1)$-th input. One thing to note, is that there is an unlimited supply of atoms, so each individual atom can contain an arbitrary amount of information. That said, it is difficult to get information out of an atom as it only supports equality. Part of the motivation for the first restriction is, as discussed in the papers introduction, "pure Lisp" can't make cyclic structures. If we allowed arbitrary structures as output, then there would be some (representations of) outputs that "pure Lisp" would simply be unable to make.

Now this is all well and good but also published the same year by Bird, Jones, and de Moor we have the paper More Haste, Less Speed: Lazy versus Eager Evaluation (PDF). This implements Pippenger's counter-example in the lazy language Haskell (but a lazy version of Lisp could also easily have been used) with the desired performance guarantees. (Not mentioned, but laziness also allows us to make cyclic structures.) That said, lazy evaluation, i.e. call-by-need not call-by-name, is usually internally implemented via mutation, but this internal mutation is unobservable from the language. I don't believe either paper discusses space usage.

More practically speaking, array algorithms are often the bread-and-butter of imperative programming, while in (pure) functional programming mutable arrays are awkward. (Graph algorithms are another area where pure functional programming struggles.) I'm pretty sure no one has demonstrated how to implement a persistent array with $O(1)$ lookups and updates to all versions. We can make persistent arrays with $O(1)$ lookups and updates to the latest version (and slower lookups/updates for older versions). Haskell's DiffArray implements this, though again the implementation utilizes mutation, but again this is not observable to the program. Since imperative programs are forced to use (mutable) data structures in a single-threaded manner anyway, this should allow any imperative array algorithm to be implemented in Haskell with no asymptotic slow-down (from the array at least).

The question gets murkier as we allow more features in the language. For example, the Clean programming language, another pure, lazy functional language introduced around the same time as Haskell, never had any trouble with arrays. Clean supports uniqueness typing which can guarantee that the reference you have to a data structure is the only reference. This allows operations to be implemented with in-place updates. The interface, though, is the same as the immutable interface except for an extra typing discipline. In particular, the updates could be implemented in an immutable fashion without the program being able to tell the difference.

Theoretically, I believe the question is still open, but it depends on what you consider the machine model. In some machine models it is answered. Practically, it's pretty clear that mutation is sometimes the only reasonable approach, but purely functional interfaces to mutation and mutable structures blur things a bit.

$\endgroup$
  • $\begingroup$ Excellent answer. Could you elaborate on "the updates could be implemented in an immutable fashion without the program being able to tell the difference"? There would be a difference in space usage, right? $\endgroup$ – user23039 May 23 '18 at 6:45
  • $\begingroup$ @Keelan Not really. Worst-case scenario you need twice as much space. Namely you need the old and new versions simultaneously in memory, but the old version becomes garbage immediately after the update is complete. So the difference is space usage is a constant factor, and unless you have a single array that makes up a significant factor of your space usage (not counting what it might point at) it will not significantly increase your space usage. $\endgroup$ – Derek Elkins May 23 '18 at 7:31
  • $\begingroup$ Ah right. So in the end you will only notice that the program is slower, because of all the array copying and garbage connecting. Thanks! $\endgroup$ – user23039 May 23 '18 at 7:34

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.