Imperative Haskell • Hacker News Board

Re: Imperative Haskell

#61

Post by platz » Wed, May 31, 2017, 6:08 PM UTC

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…

> randomized pivot selection

I don't see why this is an issue when pseudo-random generators are in fact deterministic yet for purposes of pivot selection the seed does not need to be fresh on each invocation barring an adversarial context, in which you'd just pass in the seed from the effectful part of the program.

Re: Imperative Haskell

#62

Post by skybrian » Wed, May 31, 2017, 8:18 PM UTC

lmm wrote: post #50

skybrian wrote: post #47

Earlier quoted context omitted.

Performance matters for any task that has a deadline, not just crypto and real-time stuff. That's why we make performance improvements, after all. I think it might be better to think of purity as a way of ensuring that performance and logical correctness are independent effects. Purity allows us to safely improve performance by making local substitutions of faster but logically equivalent code, without having to reas…

Performance matters a little bit - most of the time we don't make perfomance improvements. Really in a context where performance was of serious importance I would want to have an explicit model of it to be sure I could reason about it compositionally. I find any single effect is easy to reason about in isolation, it's the interaction that gets tricky. Viewing purity as isolating performance is just one perspective on…

Yes, compositional reasoning is important, but it depends on being able to substitute equivalent code. If you're too strict about what counts as equivalent (including performance in the type system, say) it would be harder to make local changes since fewer substitutions would be possible.

You can look at const correctness in C++, Java checked exceptions, async versus non-async functions [1], and Rust's ownership model as other examples where making fine distinctions for good reason has a side effect of making substitution harder - or perhaps safer, depending on your point of view.

If you need it, you need it, but when you don't, it's a luxury to be able to substitute whatever you like and see what happens.

[1] http://journal.stuffwithstuff.com/2015/02/01/what-color-is-y...

Re: Imperative Haskell

#63

Post by s_ngularity » Wed, May 31, 2017, 10:01 PM UTC

runeks wrote: post #48

nine_k wrote: post #4

Earlier quoted context omitted.

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

It's important that we separate the concept of a language and its implementation. You cannot define a pure language using an impure language, but what type of language you use to implement a pure language is up to you.

I fail to see how you couldn't specify a pure language using a pure subset of a sufficiently expressive impure language.

Re: Imperative Haskell

#64

Post by mrout » Wed, May 31, 2017, 10:13 PM UTC

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  readSTRef stack
        when wOnStack $ do
            vLowLink  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.

Re: Imperative Haskell

#65

Post by Veedrac » Wed, May 31, 2017, 10:27 PM UTC

masklinn wrote: post #16

flavio81 wrote: post #13

Earlier quoted context omitted.

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

PyPy supports Python 3, so you don't need to port it at all.

Re: Imperative Haskell

#66

Post by sidek » Wed, May 31, 2017, 10:28 PM UTC

AnimalMuppet wrote: post #60

sidek wrote: post #55

Earlier quoted context omitted.

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

The answer, as you point out, is that CP violation implies T violation. Experimentally testing T violation is much, much harder, and I don't think has really been done in many systems (look at Fitch and Cronin's work for an example), but we know CP violation implies it. So it's there. Or at least, to our best knowledge, it's there -- T violation is not very well understood.

Re: Imperative Haskell

#67

Post by Veedrac » Wed, May 31, 2017, 10:48 PM UTC

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…

    $ time make hs
    Results: [24639155,24977202,20874958]
    make hs  8.39s user 5.93s system 322% cpu 4.435 total

    $ time make py
    24894022
    25787638
    21979201
    make py  14.33s user 0.02s system 99% cpu 14.353 total

    $ time make py PYTHON=pypy3
    25059732
    25318854
    21254890
    make py PYTHON=pypy3  4.02s user 0.06s system 99% cpu 4.082 total

Re: Imperative Haskell

#68

Post by theoh » Thu, Jun 01, 2017, 1:45 AM UTC

theoh wrote: post #43

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…

But since Haskell of course compiles to C or C--, it obviously doesn't follow that you can't implement purity in an impure language -- just not at the level of the typical metacircular interpreter beloved of FP people. I'm not sure what you'r saying exactly. A related issue is the "monads let us do things that are difficult to express in other ways" argument of Wadler's paper Essence of Functional Programming. I beli…

Since I've got a stray downvote, let me clarify: I'm pro-FP. Purity amounts to referential transparency which is uncomplicated. Haskell and similar languages have the character of arithmetic expressions (no side effects) evaluated mechanically. This claim is uncontroversial and is supported by the well known papers of Strachey and Landin. Monads are useful but their use does represent a decision to bring "the awkward squad" of side effects etc. into the clean elegant world of calculating the value of expressions. Alternative approaches might see imperative code written separately from pure code.

It's surely a category error to say that purity is more essential than impurity. What's pure is the expression one types in, and its various reduced forms, culminating in a value. Impure is the messy causal world of real hardware and objects which have stubborn or mutable properties: the whole address-based system of letters in postboxes, for example. The world has state. That doesn't make the platonic ideal of an arithmetic expression any less real, but it's an abstraction of a certain circumscribed set of operations that we perform, typically on a blackboard or with pencil and paper. It's a tiny part of reality.

Re: Imperative Haskell

#69

Post by Retra » Thu, Jun 01, 2017, 3:12 AM UTC

runeks wrote: post #48

nine_k wrote: post #4

Earlier quoted context omitted.

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

It's important that we separate the concept of a language and its implementation. You cannot define a pure language using an impure language, but what type of language you use to implement a pure language is up to you.

Purity is not a really property of functions, but of optimizations. A pure function is simply those functions for which a "pure optimization" is desirable, and that ultimately depends on what you care about. Every impure function can become pure just by finding a context where the side-effects are moot. (Redirect all output to /dev/null and suddenly you won't care if your printf calls get elided or memoized.)

Re: Imperative Haskell

#70

Post by vaibhavsagar » Thu, Jun 01, 2017, 6:49 AM UTC

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.

This might help answer your first question: https://medium.com/@jonathangfischoff/are-mutable-references...