Mutable Algorithms in Immutable Languages, Part 1

http://tel.github.io/2014/07/12/mutable_algorithms_in_immutable_languges_part_1/

by zik • 12 years ago

119 41 12 years ago

tel.github.io

transfire• 12 years ago

Oh, that is rich.

dllthomas7• 12 years ago

I'm not at all sure what you are trying to communicate, here.

tel10• 12 years 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• 12 years 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.

JoshTriplett• 12 years ago

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

tel10• 12 years 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.

tel10• 12 years 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...

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• 12 years 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

tel10• 12 years 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• 12 years 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• 12 years 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.ht...

tel10• 12 years 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.

judk• 12 years ago

When will Haskell have a standard library that provides fast embedding, so programmers don't have to resort to creative tricks to get working algorithms at readkanky

DerpDerpDerp2• 12 years ago

I do work in Haskell.

At the end of the day, you still write some stateful, imperative code.

It's just that your utility/work functions are pure, which means that you have predictable side-effects: you've stuck them all in one (imperative) place, or perhaps a couple places, but you're guaranteed to know where they are because the type system enforces notating which code has the ability to cause side effects. (Makes it easy to grep on type signatures, for example.)

Most of my workload is dominated by high level concerns: correctness, large-scale data flow, coordination of state, and security.

The purity of functions means that I explain all of the constraints/solutions of those problems in pieces, which I then compose with a clear data flow between them (since they can't have shared, mutable state), and only at the end, lift them to operate on the state of the system (in a stateful, imperative block).

This way of programming gives me much more confidence in replacing pieces of the code without worrying about the side effects, because the side effects are predictably related to that code.

At the end of the day, that predictability of side effects makes the majority of my work MUCH easier, even if it adds complexity to some low level data manipulation.

I easily write 10x the high level code I do low level code, so a 20% savings on that code, even if I double the complexity of low level code, is a net savings on my time/effort.

tl;dr: Functional programming is a productivity booster if most of your work is of a high level nature, even if it makes low level manipulations harder to do. Interfacing with low level imperative code can be (and is) regularly done, to get the best of both worlds.

ScottBurson• 12 years ago

This is certainly an intriguing answer, and makes me want to try Haskell sometime, but it also makes me wonder if I can't get the same benefits, with a little effort and discipline, in a "semi-functional" language such as something in the ML family or even (if I can live without static typing) Lisp.

In fact, I've always made a point, when working in a semi-functional language, of writing as much code functionally as possible. My experience is that it has the same benefits as you describe. So I don't know how much more there is to be gotten by actually switching to Haskell. My guess is, most of the additional benefit would come from the type system. But maybe I would be motivated to write even more code functionally.

taeric8• 12 years 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• 12 years 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.)

taeric8• 12 years 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.

Mutable Algorithms in Immutable Languages, Part 1

Related Stories