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

51–60 of 73 posts

Re: Imperative Haskell

#51

Post by skybrian »

ridiculous_fish wrote: post #29
chrisdone wrote: post #23

Earlier quoted context omitted.

> Purity is tricky to define. I think it's pretty easy. Purely functional (it's important to retain the word "function") means that we have a language in which the value of a function application "f x" depends only on the body expression of "f" and the function argument "x". That's why we say "purely" functional, because it's just functions of this flavor. In types, f : X -> Y means that for all terms in X, f x maps…

Is a function like trace pure in your definition? trace's side effects seem to fall into the "unobservable implementation detail" category next to the missile launches.

It's not observable to the calling function (the return value didn't change) so it doesn't count.

Perhaps a way to think about it is as a way defining the contract between a library function and its callers regarding what substitutions are permissible. For example, substituting a faster algorithm is likely observable to the end user, but the calling function will continue to return the same value so it's a compatible substitution.

Similarly, turning on compiler optimizations or debug logging should not be a correctness issue, though it certainly matters or we wouldn't do it.

Re: Imperative Haskell

#52

Post by AnimalMuppet »

empath75 wrote: post #41
enqk wrote: post #21

Earlier quoted context omitted.

> The universe is symmetric with respect to time, and indeed, information is conserved. Bringing a snowflake back to its previous shape after it has melted?

Congrats, you've discovered entropy. The reason time seems to flow in one direction is only because there was an extremely low entropy state at the beginning.

Yes, but entropy means that the universe is not symmetric with respect to time, doesn't it? That is, enqk's statement is in fact a refutation of smilliken's claim. Dismissing it with "Congrats, you've discovered entropy" doesn't answer it at all.

Re: Imperative Haskell

#53

Post by arnarbi »

fizixer wrote: post #31

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…

I can't find it now, but there is this article/blog somewhere where the author writes only two functions: One tests if a list is sorted and the other generates a seemingly unspecified permutation of a list.

Then they combine the two in some simple way, and out pops a sorting function with no "how" specification. Due to laziness, the testing function "drives" how the permutation function picks its elements and the whole thing devolves to selection sort.

If anyone remembers the source for this, please post it.

Re: Imperative Haskell

#54

Post by charlieflowers »

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…

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

Purity is a simplification of the real world, in the same way that the abstract ideal of a circle is a simplification of objects in the real world.

But that simplification yields great benefits (kind of in the same way that ideal geometric shapes allow mathematical reasoning). It seems to describe the simplifications that the real world "approaches" (like a mathematical limit).

So it does seem fundamental. But yet not "real." I don't think those are contradictory.

It makes intuitive sense that non-purity could open up algorithmic possibilities, some of which would be faster. But that doesn't really touch on whether purity is "fundamental" in the sense described above.

Re: Imperative Haskell

#55

Post by sidek »

AnimalMuppet wrote: post #52
empath75 wrote: post #41

Earlier quoted context omitted.

Congrats, you've discovered entropy. The reason time seems to flow in one direction is only because there was an extremely low entropy state at the beginning.

Yes, but entropy means that the universe is not symmetric with respect to time, doesn't it? That is, enqk's statement is in fact a refutation of smilliken's claim. Dismissing it with "Congrats, you've discovered entropy" doesn't answer it at all.

Entropy is not due to the equations of our universe, but rather the initial conditions. So the asymmetry might be apparent but the equations might still be symmetric. Related is the idea of spontaneous symmetry breaking.

Of course, we don't have time symmetry in the equations anyway because of the weak force. But because the weak force is weak//doesn't matter much for the physics of many systems, we can often write the equations of physics as a time-symmetric term which essentially decides the motion plus a very small time-asymmetric term. So we can deal with the small term using techniques like perturbation theory, and use time symmetry for the rest.

Re: Imperative Haskell

#56

Post by [deleted] »

AnimalMuppet wrote: post #52
empath75 wrote: post #41

Earlier quoted context omitted.

Congrats, you've discovered entropy. The reason time seems to flow in one direction is only because there was an extremely low entropy state at the beginning.

Yes, but entropy means that the universe is not symmetric with respect to time, doesn't it? That is, enqk's statement is in fact a refutation of smilliken's claim. Dismissing it with "Congrats, you've discovered entropy" doesn't answer it at all.

[deleted]

Re: Imperative Haskell

#57

Post by etatoby »

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…

> it's not possible to emulate purity using an impure language

The fact that Haskell code is routinely compiled into machine language, which is the most impure and imperative kind of code possible, disproves your point.

Re: Imperative Haskell

#58

Post by etatoby »

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…

Oh come on, how can you expect similar execution time between a compiled language like Haskell and an interpreter like Python? I would be very surprised if the latter was not several times slower, purity or not.

If anything, you may want to compare compiled Haskell code to an impure, imperative language that is also strongly typed, compiled to machine language, and garbage collected, like Go.

Re: Imperative Haskell

#59

Post by lgas »

etatoby wrote: post #58
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…

Oh come on, how can you expect similar execution time between a compiled language like Haskell and an interpreter like Python? I would be very surprised if the latter was not several times slower, purity or not. If anything, you may want to compare compiled Haskell code to an impure, imperative language that is also strongly typed, compiled to machine language, and garbage collected, like Go.

I didn't expect similar execution time between them, not sure where you got that idea.

Re: Imperative Haskell

#60

Post by AnimalMuppet »

sidek wrote: post #55
AnimalMuppet wrote: post #52

Earlier quoted context omitted.

Yes, but entropy means that the universe is not symmetric with respect to time, doesn't it? That is, enqk's statement is in fact a refutation of smilliken's claim. Dismissing it with "Congrats, you've discovered entropy" doesn't answer it at all.

Entropy is not due to the equations of our universe, but rather the initial conditions. So the asymmetry might be apparent but the equations might still be symmetric. Related is the idea of spontaneous symmetry breaking. Of course, we don't have time symmetry in the equations anyway because of the weak force. But because the weak force is weak//doesn't matter much for the physics of many systems, we can often write t…

> Of course, we don't have time symmetry in the equations anyway because of the weak force.

Could you expand on what you mean here? I've expected for a while that there was going to be something non-time-reversal-symmetric with the weak force, on the basis of parity violation (space-reversal doesn't give you the same equations) plus relativity (space and time are the same thing, at least kind of). But getting there directly from parity violation might require a faster-than-light frame of reference to observe it from, which is... let's just say it's experimentally difficult.

How does the weak force break time symmetry?

Post reply on HN