12 ms·

Mutable Algorithms in Immutable Languages, Part 1

119 points by zik 12y ago

transfire 12y ago
Oh, that is rich.
- dllthomas 12y ago
  I'm not at all sure what you are trying to communicate, here.
- tel 12y ago
  Does it not seem possible to you? Hopefully by part 3 I'll be able to poke very precisely at the seam between mutable and immutable algorithms and unlock how to pick between them with greater refinement.
  - rwosync 12y ago
    I'm glad that you've taken the time to write more. Your posts have been very articulately stated, especially the one on type systems.
    - tel 12y ago
      Thanks! It means a lot to hear. It's also quite motivating :)
JoshTriplett 12y ago
This seems like a reimplementation of ST using an unspecified State Mem.
- tel 12y ago
  It's not yet, but—to cheat a bit here—eventually we're going to use `Mem` to get quite intimate with `ST` and show why it's important to use `ST` perhaps more often than people even anticipate. If you'd like, try to instantiate something along the lines of `Mem (State (IntMap v))`. It's slightly trickier than it looks due to some typing issues (which don't matter, but I'll save the reveal). It's also likely to be slightly buggy.
tel 12y ago
After someone asked for it in /r/haskell I added a link to the complete code for this post. https://github.com/tel/tel.github.io/tree/master/public/code/MutableImmutable/Part1 https://github.com/tel/tel.github.io/tree/master/public/code... Thus far there are no dependencies on outside libraries (though eventually I'll have to use `containers`) so you can just drop it into GHCi and play around!
tlarkworthy 12y ago
Looking forward to seeing where this goes. This well recieved paper[1], discusses converting reference & set type mechanics into persistent and partially persistence data structures. The model is quite similar to what is going on here. It be great to write algorithms and convert them to immutable, mutable or partially mutable at will. [1] http://www.cs.cmu.edu/~sleator/papers/Persistence.htm http://www.cs.cmu.edu/~sleator/papers/Persistence.htm
- tel 12y ago
  I was considering implementing something similar to the Overmars methods mentioned on page 90. Maybe I'll read this paper and see if I can tack it on at the end... Thanks for the link!
joe_the_user 12y ago
Hmm, Now, this and other articles about the difficulty of writing standard algorithms in functional languages makes me want to see FP's pitch be unbundled. The thing is that FP is pitched as a useful thing to learn to get an insight into programming, improve your mental fitness, see things at a higher level and so-forth. But it's also pitched as a way to be more productive and effective as a programmer. Effectively, it's sold as an exercise cycle and a real bicycle, a way to improve yourself and good way to get somewhere. Now, I'll acknowledge that functional programming probably is great for the higher-level view of programming and such. But the challenges outlined in this article makes me doubtful fp is a productivity tool, a system which will allow some large number of programmers to make a large step in productivity. I mean, if fp doesn't make simplistic programming faster and stands in the way of a large number of algorithmic approaches, it seems your productivity would consistently hobbled. Is there a counter-argument to this problem?
- comex 12y ago
  The standard counter-argument is that by enforcing purity, Haskell improves encapsulation and the ability to reason about the program (see paeans about equational reasoning [1]), and prevents all the myriad classes of bugs associated with mutable state - thus greatly improving productivity. (The same applies to its more precise type system in general.) I'm not sure how much I believe it, but some people swear by it... [1] http://www.haskellforall.com/2013/12/equational-reasoning.html http://www.haskellforall.com/2013/12/equational-reasoning.ht...
- tel 12y ago
  It depends on your toolbox. FP (Haskell-FP anyway) appears at first to hobble a lot of mutable algorithms, but (a) it has its own toolbox which has its own strengths and (b) you can embed mutability in such a way to use all of your standard mutable algorithms just the same. From a personal perspective, I program a lot in Haskell and I find it perfectly fluent. Just don't expect to take an algorithm predicted on assumptions of a particular memory model and translate it unmodified without at least using the embedding trick I mentioned above. --- Fortunately, you're in luck. The whole point of this series is to culminate in a description of the "embedding trick" I referenced above. Part 2 is written and being edited now. It introduces a slow, simple, buggy way of writing Union/Find "purely". Part 3 will fix the bug and then explore a fast embedding trick.
taeric 12y ago
For a fun mutable algorithm to test this with, I'd be interested in seeing an implementation of Knuth's Dancing Links. For that matter, I'm curious on any performance comparisons between algorithms such as the DLX and any "FP" equivalent. This already exist?
- jerf 12y ago
  Sticking to traditional computer science (i.e., ignoring constants, caching, and other details, and just sticking to Big-O analysis), it is easy to show, or indeed easy to simply see that any mutable algorithm can be represented in a purely functional way by creating a balanced tree that represents memory and can be written to and read from by index. All reading and writing operations that treat the tree as simply an expanse of RAM are O(log n), vs. O(1) of direct RAM access. Therefore, pure functional programs can simulate any impure algorithm with a slowdown no worse than a log n factor. Again, let me emphasize this is a worst-case analysis. Many common algorithms are equivalent regardless, and that's part of the reason tel specifically names Union/Find as such an algorithm, as it's actually somewhat rare to encounter one where there isn't a Big-O equivalent algorithm that is pure. Pure functional algorithms often require some modestly clever amortization to get there, but that's perfectly valid both in theory and in practice (many beloved "imperative" structures have amortized complexities, too, including such basics as a hash table). In practice pure functional can sometimes come with larger constants; whether they hit you in practice depends on your use case and, often, sensitivity to garbage collection pauses. In light of all that, I think it would be fair to say that your question is somewhat ill-defined. You can really only compare particular algorithms against each other, because there's no trivial equivalence between "imperative" and "pure functional" algorithms. Plus, the barrier between the two in practice is quite fungible... especially in a garbage-collected imperative language nothing stops you from using a "functional" algorithm, and every practical "functional" language will give you a way of running "imperative" algorithms directly. (Yes, even Haskell. But tel is building up to that. I won't give it away yet. Stay tuned.)
  - taeric 12y ago
    My question may have been ill defined, but your answer was awesome. :) I have to confess your "easy to show/see" isn't immediately obvious to me yet. However, that is as likely because I haven't tried hard to see as anything else. This post is between other things I'm trying to get done. Poorly already, digging into this is something I fear would not help. I am interested, though, so more pointers and explanations would be greatly appreciated.

119 points by zik 12y ago

transfire 12y ago

Oh, that is rich.

dllthomas 12y ago
I'm not at all sure what you are trying to communicate, here.
tel 12y ago
Does it not seem possible to you? Hopefully by part 3 I'll be able to poke very precisely at the seam between mutable and immutable algorithms and unlock how to pick between them with greater refinement.
- rwosync 12y ago
  I'm glad that you've taken the time to write more. Your posts have been very articulately stated, especially the one on type systems.
  - tel 12y ago
    Thanks! It means a lot to hear. It's also quite motivating :)

JoshTriplett 12y ago

This seems like a reimplementation of ST using an unspecified State Mem.

tel 12y ago
It's not yet, but—to cheat a bit here—eventually we're going to use `Mem` to get quite intimate with `ST` and show why it's important to use `ST` perhaps more often than people even anticipate. If you'd like, try to instantiate something along the lines of `Mem (State (IntMap v))`. It's slightly trickier than it looks due to some typing issues (which don't matter, but I'll save the reveal). It's also likely to be slightly buggy.

tel 12y ago

After someone asked for it in /r/haskell I added a link to the complete code for this post. https://github.com/tel/tel.github.io/tree/master/public/code/MutableImmutable/Part1 https://github.com/tel/tel.github.io/tree/master/public/code... Thus far there are no dependencies on outside libraries (though eventually I'll have to use `containers`) so you can just drop it into GHCi and play around!

tlarkworthy 12y ago

Looking forward to seeing where this goes. This well recieved paper[1], discusses converting reference & set type mechanics into persistent and partially persistence data structures. The model is quite similar to what is going on here. It be great to write algorithms and convert them to immutable, mutable or partially mutable at will. [1] http://www.cs.cmu.edu/~sleator/papers/Persistence.htm http://www.cs.cmu.edu/~sleator/papers/Persistence.htm

tel 12y ago
I was considering implementing something similar to the Overmars methods mentioned on page 90. Maybe I'll read this paper and see if I can tack it on at the end... Thanks for the link!

joe_the_user 12y ago

Hmm, Now, this and other articles about the difficulty of writing standard algorithms in functional languages makes me want to see FP's pitch be unbundled. The thing is that FP is pitched as a useful thing to learn to get an insight into programming, improve your mental fitness, see things at a higher level and so-forth. But it's also pitched as a way to be more productive and effective as a programmer. Effectively, it's sold as an exercise cycle and a real bicycle, a way to improve yourself and good way to get somewhere. Now, I'll acknowledge that functional programming probably is great for the higher-level view of programming and such. But the challenges outlined in this article makes me doubtful fp is a productivity tool, a system which will allow some large number of programmers to make a large step in productivity. I mean, if fp doesn't make simplistic programming faster and stands in the way of a large number of algorithmic approaches, it seems your productivity would consistently hobbled. Is there a counter-argument to this problem?

comex 12y ago
The standard counter-argument is that by enforcing purity, Haskell improves encapsulation and the ability to reason about the program (see paeans about equational reasoning [1]), and prevents all the myriad classes of bugs associated with mutable state - thus greatly improving productivity. (The same applies to its more precise type system in general.) I'm not sure how much I believe it, but some people swear by it... [1] http://www.haskellforall.com/2013/12/equational-reasoning.html http://www.haskellforall.com/2013/12/equational-reasoning.ht...
tel 12y ago
It depends on your toolbox. FP (Haskell-FP anyway) appears at first to hobble a lot of mutable algorithms, but (a) it has its own toolbox which has its own strengths and (b) you can embed mutability in such a way to use all of your standard mutable algorithms just the same. From a personal perspective, I program a lot in Haskell and I find it perfectly fluent. Just don't expect to take an algorithm predicted on assumptions of a particular memory model and translate it unmodified without at least using the embedding trick I mentioned above. --- Fortunately, you're in luck. The whole point of this series is to culminate in a description of the "embedding trick" I referenced above. Part 2 is written and being edited now. It introduces a slow, simple, buggy way of writing Union/Find "purely". Part 3 will fix the bug and then explore a fast embedding trick.

taeric 12y ago

For a fun mutable algorithm to test this with, I'd be interested in seeing an implementation of Knuth's Dancing Links. For that matter, I'm curious on any performance comparisons between algorithms such as the DLX and any "FP" equivalent. This already exist?

jerf 12y ago
Sticking to traditional computer science (i.e., ignoring constants, caching, and other details, and just sticking to Big-O analysis), it is easy to show, or indeed easy to simply see that any mutable algorithm can be represented in a purely functional way by creating a balanced tree that represents memory and can be written to and read from by index. All reading and writing operations that treat the tree as simply an expanse of RAM are O(log n), vs. O(1) of direct RAM access. Therefore, pure functional programs can simulate any impure algorithm with a slowdown no worse than a log n factor. Again, let me emphasize this is a worst-case analysis. Many common algorithms are equivalent regardless, and that's part of the reason tel specifically names Union/Find as such an algorithm, as it's actually somewhat rare to encounter one where there isn't a Big-O equivalent algorithm that is pure. Pure functional algorithms often require some modestly clever amortization to get there, but that's perfectly valid both in theory and in practice (many beloved "imperative" structures have amortized complexities, too, including such basics as a hash table). In practice pure functional can sometimes come with larger constants; whether they hit you in practice depends on your use case and, often, sensitivity to garbage collection pauses. In light of all that, I think it would be fair to say that your question is somewhat ill-defined. You can really only compare particular algorithms against each other, because there's no trivial equivalence between "imperative" and "pure functional" algorithms. Plus, the barrier between the two in practice is quite fungible... especially in a garbage-collected imperative language nothing stops you from using a "functional" algorithm, and every practical "functional" language will give you a way of running "imperative" algorithms directly. (Yes, even Haskell. But tel is building up to that. I won't give it away yet. Stay tuned.)
- taeric 12y ago
  My question may have been ill defined, but your answer was awesome. :) I have to confess your "easy to show/see" isn't immediately obvious to me yet. However, that is as likely because I haven't tried hard to see as anything else. This post is between other things I'm trying to get done. Poorly already, digging into this is something I fear would not help. I am interested, though, so more pointers and explanations would be greatly appreciated.