9 ms·

Imperative Haskell

149 points by rutenspitz 9y ago

aetherspawn 9y ago
Is the ST performance better or worse than the purely functional approach? It actually looks pretty good, not really any more verbose than Java to be honest.
- chrisdone 9y ago
  Direct mutations for a mutating algorithm is certainly faster than rebuilding a data structure representing a set of variables. Most of the time. Though, there are exceptions where they're equivalent thanks to GHC's optimizations (e.g. splitting up a record's fields into n registers).
- Tarean 9y ago
  Some algorithms require mutation to have a decent time complexity and ST allows you to implement those. There is a tiny cost for each mutable memory location since the garbage collector has to work around then. A single array won't even be measurable, though. Also, there are some referentially transparent algorithms that can't be implemented via ST - like laziness.
- vaibhavsagar 9y ago
  This might help answer your first question: https://medium.com/@jonathangfischoff/are-mutable-references-in-haskell-fast-f095f4144977 https://medium.com/@jonathangfischoff/are-mutable-references...
runeks 9y ago
As far as I'm concerned, purity is more fundamental than impurity, because we can always emulate impurity using a pure language (as is shown in this article), but it's not possible to emulate purity using an impure language. This only leaves us with the challenge of performance. While we can always describe e.g. x86 assembly in terms of a pure intermediate representation language (e.g. GHC Core), transforming this description back into equally performant x86 doesn't seem easy. Also, anyone care to produce some benchmarks comparing the imperative Python/Haskell quicksort implementations? They look so similar, it'd be quite interesting to see how well GHC can optimize this sort of stuff.
- nine_k 9y ago
  > it's not possible to emulate purity using an impure language It sounds as if a pure language cannot be implemented in terms of an impure language. E.g. a pure language won't be implementable in an instruction set of any modern CPU. I must be missing something.
  - Retra 9y ago
    The CPU instructions are pure functions over the state of the machine. :)
    - TheCoreh 9y ago
      Only if you ignore cosmic rays :)
      - pka 9y ago
        Then every CPU instruction is just (Universe -> Universe) :D
  - inimino 9y ago
    In this context, purity means the contract between caller and callee. You can write the same code, but you can't rely on the enforcement of the same contract unless it is built into the language.
  - T-R 9y ago
    Impurity is a lack of constraints. You can, with impure code, write an interpreter for a language that constrains code to being pure, and implemented correctly, you can then depend on code written in that langauge to be pure. His point is that there's no lost benefit in calling pure code from impure code - the code is already unconstrained. Calling impure code from pure code, though, means you've lost the purity constraint, which means you've lost the nice emergent properties you get from that constraint. Even if you write 'pure' code in an impure environment, you can't depend on it being pure, because that constraint isn't actually enforced. No matter how pure I try to keep my Javascript, I can never depend on it being pure - there could be a bug, or someone could add impurity at the bottom of the callstack, breaking referential transparency.
deleted 9y ago
[deleted]
_pmf_ 9y ago
That's Haskell I can understand.
fizixer 9y ago
The first code block reads like a definition, or the 'what' of quicksort, which has to be fleshed out using the 'how' of quicksort. And it just so happens that 'what' is declarative, and 'how' is imperative (i.e., do this, do that, that's how). Speaking of which, there is a definition of, not quicksort, but sort itself, and it goes something like this: 'sort is a map that takes a sequence S of orderable items, to one of its permutations P such that for every two adjacent elements e1, e2 in P, e1 < e2' I'm not familiar with Haskell syntax but I'm sure this definition can be encoded in Haskell. Actually imperatively speaking, this is a sort algorithm itself, the very less discussed (probably because of very high complexity) 'permutation sort', i.e. you keep permuting the input sequence and keep checking your e1/e2 condition until it is satisfied. So we can define sort, but then we can specify a language to not compute based on that definition but instead pick from one of the preferable computation schemes that are also defined in that langauge (quicksort, mergesort, etc, etc). But then we specify not to use the definition of that scheme but instead use an algorithm for it (e.g., the imperative algorithm for quicksort). I guess this is a form of semantic layering, something that I'm interested in as a topic of study.
- heavenlyblue 9y ago
  It would also be interesting to extend this language to the one that also has partial conditions satisfied, e.g.: - We have a set S of tuples (a,b,c) sorted by (a,b) - We would like to sort S by (a,b,c) - Therefore we only need to only sort subsets (a,b,cx) By the way, permutation sort would be reducing the sorting algorithm to a problem of search in the configuration space of N variables. Speaking generally, you may reduce any problem to a search problem; so this doesn't only work for sorting.
- infinisil 9y ago
  That's where formal proofs come into play, because you need to somehow show that the implementation actually does what the definition states. Since Haskell isn't a proof checker you can't use it for this. The newish and very promising looking language Idris [1], which is very similar to Haskell, can actually do this because of having dependent types. Upon a quick search I found this great example [2] of a proof that insertion sort does indeed return the list sorted, all in the type system. I can really recommend Type Driven Development [3], a recently released book on development in Idris. [1]: https://www.idris-lang.org/ https://www.idris-lang.org/ [2]: https://github.com/davidfstr/idris-insertion-sort https://github.com/davidfstr/idris-insertion-sort [3]: https://www.manning.com/books/type-driven-development-with-idris https://www.manning.com/books/type-driven-development-with-i...
marcosdumay 9y ago
The article is assuming a little too much when it's claimed that the first implementation doesn't sort in place. It's not clear how GHC would optimize this (even more if you don't use the unsorted list for anything else), and it would be interesting to see the benchmarks for that version too.
mrout 9y ago
No offence to the author, but this is rather awful code. comparisons += (end-start-1) That isn't counting comparisons. It's not incrementing a counter every time you do a comparison. Don't pretend it's counting comparisons. This article is just typical 'pure functional propaganda' IMO. There's no actual justification for anything it's saying. It provides a bunch of convoluted, overly complicated Haskell code to do something trivial and then makes unfounded claims about impurity like >Why don't we do this all the time, when Haskell is at least a serviceable imperative language? Because writing imperative programs is hard! They don't compose as well, have less useful type signatures, and are harder to reason about. Getting away from those things is why we have Haskell to begin with! Writing imperative programmes is not hard. Imperative programmes compose very well, as anyone that's every used the bloody Unix commandline knows well. And no, you can't argue that it's a 'pure interface'. rm isn't pure. chmod isn't pure. The programmes aren't implemented in pure languages. And Haskell is an awful imperative language. I want evidence that someone, in real life, actually thinks that this: else do wOnStack <- elem w <$> readSTRef stack when wOnStack $ do vLowLink <- fromJust . I.lookup v <$> readSTRef lowlinks modifySTRef' lowlinks (I.insert v $ min vLowLink (fromJust wIndex)) is an acceptable way to implement this: else if (w.onStack) then v.lowlink := min(v.lowlink, w.index) endif compared to this: elif w.onStack: v.lowlink = min(v.lowlink, w.index) then you're in denial.

149 points by rutenspitz 9y ago

Is the ST performance better or worse than the purely functional approach? It actually looks pretty good, not really any more verbose than Java to be honest.

chrisdone 9y ago
Direct mutations for a mutating algorithm is certainly faster than rebuilding a data structure representing a set of variables. Most of the time. Though, there are exceptions where they're equivalent thanks to GHC's optimizations (e.g. splitting up a record's fields into n registers).
Tarean 9y ago
Some algorithms require mutation to have a decent time complexity and ST allows you to implement those. There is a tiny cost for each mutable memory location since the garbage collector has to work around then. A single array won't even be measurable, though. Also, there are some referentially transparent algorithms that can't be implemented via ST - like laziness.
vaibhavsagar 9y ago
This might help answer your first question: https://medium.com/@jonathangfischoff/are-mutable-references-in-haskell-fast-f095f4144977 https://medium.com/@jonathangfischoff/are-mutable-references...

runeks 9y ago

As far as I'm concerned, purity is more fundamental than impurity, because we can always emulate impurity using a pure language (as is shown in this article), but it's not possible to emulate purity using an impure language. This only leaves us with the challenge of performance. While we can always describe e.g. x86 assembly in terms of a pure intermediate representation language (e.g. GHC Core), transforming this description back into equally performant x86 doesn't seem easy. Also, anyone care to produce some benchmarks comparing the imperative Python/Haskell quicksort implementations? They look so similar, it'd be quite interesting to see how well GHC can optimize this sort of stuff.

nine_k 9y ago
> it's not possible to emulate purity using an impure language It sounds as if a pure language cannot be implemented in terms of an impure language. E.g. a pure language won't be implementable in an instruction set of any modern CPU. I must be missing something.
- Retra 9y ago
  The CPU instructions are pure functions over the state of the machine. :)
  - TheCoreh 9y ago
    Only if you ignore cosmic rays :)
    - pka 9y ago
      Then every CPU instruction is just (Universe -> Universe) :D
- inimino 9y ago
  In this context, purity means the contract between caller and callee. You can write the same code, but you can't rely on the enforcement of the same contract unless it is built into the language.
- T-R 9y ago
  Impurity is a lack of constraints. You can, with impure code, write an interpreter for a language that constrains code to being pure, and implemented correctly, you can then depend on code written in that langauge to be pure. His point is that there's no lost benefit in calling pure code from impure code - the code is already unconstrained. Calling impure code from pure code, though, means you've lost the purity constraint, which means you've lost the nice emergent properties you get from that constraint. Even if you write 'pure' code in an impure environment, you can't depend on it being pure, because that constraint isn't actually enforced. No matter how pure I try to keep my Javascript, I can never depend on it being pure - there could be a bug, or someone could add impurity at the bottom of the callstack, breaking referential transparency.

deleted 9y ago

[deleted]

_pmf_ 9y ago

That's Haskell I can understand.

fizixer 9y ago

The first code block reads like a definition, or the 'what' of quicksort, which has to be fleshed out using the 'how' of quicksort. And it just so happens that 'what' is declarative, and 'how' is imperative (i.e., do this, do that, that's how). Speaking of which, there is a definition of, not quicksort, but sort itself, and it goes something like this: 'sort is a map that takes a sequence S of orderable items, to one of its permutations P such that for every two adjacent elements e1, e2 in P, e1 < e2' I'm not familiar with Haskell syntax but I'm sure this definition can be encoded in Haskell. Actually imperatively speaking, this is a sort algorithm itself, the very less discussed (probably because of very high complexity) 'permutation sort', i.e. you keep permuting the input sequence and keep checking your e1/e2 condition until it is satisfied. So we can define sort, but then we can specify a language to not compute based on that definition but instead pick from one of the preferable computation schemes that are also defined in that langauge (quicksort, mergesort, etc, etc). But then we specify not to use the definition of that scheme but instead use an algorithm for it (e.g., the imperative algorithm for quicksort). I guess this is a form of semantic layering, something that I'm interested in as a topic of study.

heavenlyblue 9y ago
It would also be interesting to extend this language to the one that also has partial conditions satisfied, e.g.: - We have a set S of tuples (a,b,c) sorted by (a,b) - We would like to sort S by (a,b,c) - Therefore we only need to only sort subsets (a,b,cx) By the way, permutation sort would be reducing the sorting algorithm to a problem of search in the configuration space of N variables. Speaking generally, you may reduce any problem to a search problem; so this doesn't only work for sorting.
infinisil 9y ago
That's where formal proofs come into play, because you need to somehow show that the implementation actually does what the definition states. Since Haskell isn't a proof checker you can't use it for this. The newish and very promising looking language Idris [1], which is very similar to Haskell, can actually do this because of having dependent types. Upon a quick search I found this great example [2] of a proof that insertion sort does indeed return the list sorted, all in the type system. I can really recommend Type Driven Development [3], a recently released book on development in Idris. [1]: https://www.idris-lang.org/ https://www.idris-lang.org/ [2]: https://github.com/davidfstr/idris-insertion-sort https://github.com/davidfstr/idris-insertion-sort [3]: https://www.manning.com/books/type-driven-development-with-idris https://www.manning.com/books/type-driven-development-with-i...

marcosdumay 9y ago

The article is assuming a little too much when it's claimed that the first implementation doesn't sort in place. It's not clear how GHC would optimize this (even more if you don't use the unsorted list for anything else), and it would be interesting to see the benchmarks for that version too.

mrout 9y ago

No offence to the author, but this is rather awful code. comparisons += (end-start-1) That isn't counting comparisons. It's not incrementing a counter every time you do a comparison. Don't pretend it's counting comparisons. This article is just typical 'pure functional propaganda' IMO. There's no actual justification for anything it's saying. It provides a bunch of convoluted, overly complicated Haskell code to do something trivial and then makes unfounded claims about impurity like >Why don't we do this all the time, when Haskell is at least a serviceable imperative language? Because writing imperative programs is hard! They don't compose as well, have less useful type signatures, and are harder to reason about. Getting away from those things is why we have Haskell to begin with! Writing imperative programmes is not hard. Imperative programmes compose very well, as anyone that's every used the bloody Unix commandline knows well. And no, you can't argue that it's a 'pure interface'. rm isn't pure. chmod isn't pure. The programmes aren't implemented in pure languages. And Haskell is an awful imperative language. I want evidence that someone, in real life, actually thinks that this: else do wOnStack <- elem w <$> readSTRef stack when wOnStack $ do vLowLink <- fromJust . I.lookup v <$> readSTRef lowlinks modifySTRef' lowlinks (I.insert v $ min vLowLink (fromJust wIndex)) is an acceptable way to implement this: else if (w.onStack) then v.lowlink := min(v.lowlink, w.index) endif compared to this: elif w.onStack: v.lowlink = min(v.lowlink, w.index) then you're in denial.