Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Imperative Haskell

vaibhavsagar.com

Post reply on HN
Print view View original

11–20 of 73 posts

Re: Imperative Haskell

#11

Post by cousin_it »

runeks wrote: post #3

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 de…

Purity is tricky to define. For example (stolen from Reddit user gasche), if you can measure how much time a computation takes, then Haskell is impure, because a lazy value takes longer to compute the first time than the second. You could try to patch it up by saying the impurity must be observable via pure code, but that makes the definition circular. And that raises another problem, where printing to standard output becomes "pure" if the standard output can't be observed by pure code (which is true in Haskell).

Another problem with seeing purity as fundamental is that our physical reality isn't a persistent data structure (past states aren't accessible), so the best algorithms possible won't treat it as one. Among the tons of papers describing fast algorithms, practically none are using purity, unless they required purity to begin with.

And there's a third problem, specific to Haskell, that might interest you. The article is using ST to implement an impure computation. You'd think that ST itself can be implemented in pure Haskell, maybe with the usual logarithmic slowdown. But unfortunately no one knows how to do it, and there's a strong suspicion that the (pure) type signature of runST has no pure implementation at all, even with quadratic or exponential slowdowns. The reason is tricky to explain, but it's well covered on StackOverflow and Reddit.

(That's not even going into the issues of quicksort. Suffice to say that a pure quicksort is hard to write, ST or no. The problem is that you need good pivot selection to prevent the quadratic worst case, but randomized pivot selection will lead to observable impurity in the output, because quicksort isn't stable. So you must use something like median of medians, making the algorithm much slower and more complicated.)

Re: Imperative Haskell

#13

Post by flavio81 »

runeks wrote: post #3

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 de…

Python (in its CPython) incarnation is pretty slow usually. You can use PyPy (a JIT implementation of most of the Python spec) for dramatically more speed, but the code needs to be ported to work under PyPy.

The real comparison should be a language that is both functional and imperative and that allows you to write as brief a source code as you can do in Haskell.

Such a language is Common Lisp, and it will compile directly to machine language doing many optimizations.

Re: Imperative Haskell

#14

Post by vaibhavsagar »

lgas wrote: post #8
runeks wrote: post #3

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 de…

I tried to do some quick benchmarks: % make hs Results: [25872791,24253954,21258158] make hs 6.53s user 3.99s system 245% cpu 4.282 total % make py 24029582 25343914 20814678 make py 22.37s user 0.11s system 99% cpu 22.593 total You can see the code as tested here[0]. I am not an expert on either Haskell or Python performance, all I did was use -O for python3 and -O2 for GHC. This was on a 2.8 GHz Core i7 Macbook, FW…

I took `contents` from here[0] but I like your random ints much better!

[0]: https://github.com/vaibhavsagar/thursday-presentations/blob/...

Re: Imperative Haskell

#15

Post by smilliken »

cousin_it wrote: post #11
runeks wrote: post #3

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 de…

Purity is tricky to define. For example (stolen from Reddit user gasche), if you can measure how much time a computation takes, then Haskell is impure, because a lazy value takes longer to compute the first time than the second. You could try to patch it up by saying the impurity must be observable via pure code, but that makes the definition circular. And that raises another problem, where printing to standard outpu…

> if you can measure how much time a computation takes, then Haskell is impure

gettimeofday requires IO, so the computation would depend on dynamic inputs, but that doesn't make it impure. If the program knows how long one of its computations took, that's only because an oracle (outer layer of abstraction) told it.

> Another problem with seeing purity as fundamental is that our physical reality isn't a persistent data structure

I like this line of reasoning, but would take the opposite conclusion. The universe is symmetric with respect to time, and indeed, information is conserved. Past states aren't easily accessible, but they have not been erased. This sounds like a fine working definition for persistent data structures.

> there's a strong suspicion that the (pure) type signature of runST has no pure implementation

Interesting, thanks for bringing it up!

Re: Imperative Haskell

#16

Post by masklinn »

flavio81 wrote: post #13
runeks wrote: post #3

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 de…

Python (in its CPython) incarnation is pretty slow usually. You can use PyPy (a JIT implementation of most of the Python spec) for dramatically more speed, but the code needs to be ported to work under PyPy. The real comparison should be a language that is both functional and imperative and that allows you to write as brief a source code as you can do in Haskell. Such a language is Common Lisp, and it will compile di…

> the code needs to be ported to work under PyPy.

The only incompatibility is the `.copy()` calls which should be replaced by `list(contents)`, then it'll be cross-compatible between P2 and P3.

Here's what I get with that (on a 2010 MBP) using the random generation of lgas above (1M random ints):

    > time python2.7 qs.py
    python2.7 qs.py  41.92s user 0.37s system 98% cpu 42.837 total
    > time python3.6 qs.py
    python3.6 qs.py  42.99s user 0.32s system 98% cpu 44.047 total
    > time pypy qs.py
    pypy qs.py  3.27s user 0.12s system 94% cpu 3.603 total
There's a fair bit of variation but pypy is between 3.4 and 4

Re: Imperative Haskell

#17

Post by bojo »

lgas wrote: post #10
lgas wrote: post #8

Earlier quoted context omitted.

I tried to do some quick benchmarks: % make hs Results: [25872791,24253954,21258158] make hs 6.53s user 3.99s system 245% cpu 4.282 total % make py 24029582 25343914 20814678 make py 22.37s user 0.11s system 99% cpu 22.593 total You can see the code as tested here[0]. I am not an expert on either Haskell or Python performance, all I did was use -O for python3 and -O2 for GHC. This was on a 2.8 GHz Core i7 Macbook, FW…

I was playing around a little more and I noticed that stack sets the following ghc-options by default: -threaded -rtsopts -with-rtsopts=-N which I assumed explained some of the speedup, so I disabled them and got a reduction to 99% cpu as expected, but unexpectedly the single threaded version was about twice as fast: % make hs Results: [24605537,25150983,21576960] make hs 3.13s user 0.07s system 99% cpu 3.211 total

Depending on your problem you can actually lose performance with a multi-threaded app due to the context switching overhead.

Re: Imperative Haskell

#18

Post by cousin_it »

smilliken wrote: post #15
cousin_it wrote: post #11

Earlier quoted context omitted.

Purity is tricky to define. For example (stolen from Reddit user gasche), if you can measure how much time a computation takes, then Haskell is impure, because a lazy value takes longer to compute the first time than the second. You could try to patch it up by saying the impurity must be observable via pure code, but that makes the definition circular. And that raises another problem, where printing to standard outpu…

> if you can measure how much time a computation takes, then Haskell is impure gettimeofday requires IO, so the computation would depend on dynamic inputs, but that doesn't make it impure. If the program knows how long one of its computations took, that's only because an oracle (outer layer of abstraction) told it. > Another problem with seeing purity as fundamental is that our physical reality isn't a persistent dat…

> The universe is symmetric with respect to time, and indeed, information is conserved. Past states aren't easily accessible, but they have not been erased. This sounds like a fine working definition for persistent data structures.

That line of research exists, but it's different from persistent data structures. The search term is "reversible computing", and the main idea is that you never erase bits because that would irreversibly increase entropy. One difference is that persistent data structures allow access to past states in O(1), while reversible computing requires you to spend time on uncomputing. Right now it's mostly a curiosity because it requires hardware that doesn't exist, so I'd be wary of using it as a foundation of CS. It might well become important in the future though, due to lower energy requirements.

Re: Imperative Haskell

#19

Post by chrisdone »

aetherspawn wrote: post #2

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.

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).

Re: Imperative Haskell

#20

Post by lmm »

cousin_it wrote: post #11
runeks wrote: post #3

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 de…

Purity is tricky to define. For example (stolen from Reddit user gasche), if you can measure how much time a computation takes, then Haskell is impure, because a lazy value takes longer to compute the first time than the second. You could try to patch it up by saying the impurity must be observable via pure code, but that makes the definition circular. And that raises another problem, where printing to standard outpu…

A pure language is one in which replacing any subexpression of any expression with the evaluation of that subexpression yields an equivalent expression.

Of course this means "pure" is not an absolute term but rather relative to a given definition of "equivalent". But this isn't circular and is practically useful: if you're working in a context where precise execution time matters (e.g. cryptography) you really do need to use a different concept of "pure" language from what you would use in a more "normal" context where two programs that produce the same output are equivalent even if they take a different amount of time to execute.

Post reply on HN