Hacker News Reader

Comment by millstone | Hacker News Reader

Data dependencies don't viably smuggle operation sequencing into Haskell. Consider e.g.:

   fma a b c = (a * b) + c

The sum depends on the product but this doesn't sequence anything: it may be compiled into a single fma machine instruction. More generally inlining, CSE, etc. can break apparent data dependencies.

It's simpler and cleaner to merely state that the Haskell runtime is written to execute IO actions in sequence.

View on HN

The data dependencies in how monads desugar does force the evaluation order, because the result of the first one is passed to the following one and so on and so forth. The desugaring turns each monadic action into a lambda with one argument.

I think that millstone (https://news.ycombinator.com/item?id=17646166 )'s point was that the sense in which desugaring of monads forces evaluation order is the same as the sense in which

    fma a b c = (a * b) + c

forces evaluation order: you need the result of `a * b` in `fma` in order to add `c` to it. One can argue whether both of these, or neither of these, have the evaluation order forced, but I don't think that it is reasonable to argue that one does and the other doesn't. (There is a slight artefact from the fact that addition is commutative, so that it makes no difference whether you compute `c` first and then add `a * b` to it or vice versa, but I think the idea should remain.)

To discuss this properly, you need to consider the evaluation strategy, which is part of the semantics of the language. Strict, lazy, call-by-need: things do get evaluated in a prescribed order, and sequencing using monads (predictably) involves strictness, meaning that a function argument is evaluated before the function.

These details of evaluation order are important to know, and they are not something to be argued about: they are well-specified and the compiler doesn't just casually make lazy code into strict code or vice versa. That would cause chaos. And what instruction set Haskell is being compiled to is totally irrelevant to this level of the language's semantics.

https://en.wikipedia.org/wiki/Evaluation_strategy

> To discuss this properly, you need to consider the evaluation strategy, which is part of the semantics of the language.

Yes, you are certainly right. I misread and thought incorrectly that the discussion was about whether certain constructs forced data dependencies in any theoretical language, not in the particular language Haskell.

> These details of evaluation order are important to know, and they are not something to be argued about: they are well-specified ….

While I take your meaning, I think that you don't mean literally what you said: they got to be well specified precisely by being argued about, and will hopefully get to be even better specified by continuing argument. They are certainly not for me to argue about, though.

>sequencing using monads (predictably) involves strictness,

Sequencing using the IO monad predictably involves strictness. There is nothing in the type of >>= that forces strictness. That is why, for example, you can usefully bind infinite lists in the list monad. So in e.g. [1..] >>= return . (+ 1), the list is not evaluated before the call to (+).

In fact, binding is not strict in the IO monad either (that's why lazy IO works). It's only the special magic world parameter that is, in effect, evaluated strictly.

Yes, monads don't imply strictness.

The idea of using a data dependency to force a certain order of evaluation predates monads and it predates laziness. So it is implemented accordingly, and any hoops that need to be jumped through in the implementation to make it work aren't magic—they are just necessary to express a long-established pattern.

What monads offer is a way of discreetly passing the state from one operation to the next (the State monad is the model for the IO monad). It removes the need for the programmer to think about that aspect of the plumbing, without creating magic elements in the language.

http://okmij.org/ftp/Computation/IO-monad-history.html

>So it is implemented accordingly, and any hoops that need to be jumped through in the implementation to make it work aren't magic—they are just necessary to express a long-established pattern.

The hoops are magic in the sense that they can't be expressed in Haskell 98 or Haskell 2010. A Haskell compiler is perfectly entitled to optimize out any dummy values which aren't used. That includes dummy world variables.

More generally, it simply isn't possible to use data dependencies -- even real data dependencies -- to control the order of side effects. The Haskell standards just don't provide the guarantees necessary to make that workable, for the reasons that millstone gave.

Yes, but there is no guarantee that the argument passed to that lambda will ever be evaluated. Consider e.g. the following expression in the identity monad:

do { x <- return [1..]; return 7 }

That evaluates to 7, and the infinite list is never evaluated. So the 'data dependency' that monadic bind gives you doesn't, in general, force evaluation order. It's only because the implementation details of the IO monad ensure that the dummy world parameter is always 'evaluated' that you get guarantees about evaluation order. Note that the dummy world parameter is just that -- a dummy -- and no computation actually depends on its value. It's pure compiler magic.

Reply on news.ycombinator.com