I understood Haskell once I internalized the actual purpose of non-strict semantics.
Abstractly your program is a tree rooted at main. In a language like C you concentrate on building trees knowing that you are going to touch every node. So you are trying to design small trees that have good execution semantics as well as being correct in the problem solving domain. You have to address the problem at 2 levels. Because C is strict every function you call will be evaluated before it can return some result.
Haskell is different you can build any tree you like because a node will only be evaluated if its result is required for the current context. You are free to work with models of data like "the integers" or "all possible game states".
Concretely in C if you wanted to find the smallest positive integer that satisfies some property P you would write something like
for (int i=1; ; i++) if (P(i)) return i;
This is a single node in your program tree which modifies a variable until a condition is met.
In contrast in Haskell you might do something like
find P [1..]
I would interpret this as find operating on an infinite lazy tree and discarding the infinite tail list (which is an infinite computation) once the result is found.
Applying this simple example, in Haskell you aren't concern with limiting the shape of your program's tree. You build the correct model for your program regardless of constraints like infinite lists or terminating searches early. You just allow non-strict evaluation to process your input data because you will never have to strictly generate an infinite integer list before scanning it.
At root non-strict semantics is just a reversal of the order of reduction of expressions.
That sounds like a good intuition to me. Strict is like push, because it gives you the result as soon as it's ready. Lazy (or perhaps more precisely non-strict) is like pull because you have to go and ask for the result.
Yes, and after years of struggling to find which should prevail, I recently heard the term of backpressure (used in reactive GUI IIRC) to be able to reason about things in both direction. Is there a middle ground for evaluation strategies ? Right now one can for strictness (in Haskell) or lazyness (in ml) but I never found a 'theory' about both.
Your intuition about a middle ground is interesting. Perhaps one of javascript's derivative languages could come up with some syntax to make using this more intuitive, because let's face it node.js streams would be easier to use if there were some way of plumbing them together that didn't look like Java from 1999.
I don't know node, but, conceptually, Arrows [1] map to the steam concept very well (as always in Haskell, they are more general). The sugar in Haskell to use them similar to do-notion is really a joy to use.
I was exposed to them in the Haskell music library Euterpea in the Haskell School of Music [2]. The signal processing API uses arrows.
> Perhaps one of javascript's derivative languages could come up with some syntax to make using this more intuitive
You might want to checkout purescript, which I'm pretty sure uses Monads to make stream interaction intuitive. No time for an example, but I believe there is one somewhere in the Purescript book[0].
Actually, Haskell is not a completely lazy language. It is (literally) "non-strict" and that means that it intersperses both modes.
GHC tries to do its best with its strictness analyzer; it looks it works in many simple cases, still blowing up in non-trivial places, producing space leaks. Although I must say that space leaks may be very well produced by a redundant strictness and people who want strictness by default seem a bit luddistic to me.
My ideal language (or rather its compiler/runtime) would do complete analyses of what strategy suits each part of the program. By the way I'm a little surprised by Haskell insistence on static analysis, disregarding tracing VM and automatic run-time profiling.
That's true. An obvious solution is "keep IO out of your lazy computations", which hopefully you can get some language help with. There are some attempts at other approaches as well.
Yes. Conduits and iteratees too, for that matter. And I believe, there was some talk about "Machines", which I did not understand at all. Am not sure what is the current status of that approach.
I thought conduits and io-streams are preferred over pipes.
io-streams is built specifically for IO and is in the IO monad. This allows for performance benefits as well as simplified API like using normal IO functions for error and resource handling (ex: `bracket` can be used)
R has lazy evaluation (but only at function arguments). That makes it an easy place to play with some of the effects of lazy evaluation (but not get too bogged down with issues like IO).
One thing that bothers me is, can I rely on the compiler making those optimisations? Which ones are guaranteed for me? Those are sort of important considerations, because it can mean the difference between a linear fibs and a quadratic fibs, or an O(nlogn) sort and a O(n²) sort.
24 comments
[ 4.4 ms ] story [ 60.4 ms ] threadThat's an interesting perspective, I've never seen it that way before. I would love to learn more about this, as a non-Haskeller.
Abstractly your program is a tree rooted at main. In a language like C you concentrate on building trees knowing that you are going to touch every node. So you are trying to design small trees that have good execution semantics as well as being correct in the problem solving domain. You have to address the problem at 2 levels. Because C is strict every function you call will be evaluated before it can return some result.
Haskell is different you can build any tree you like because a node will only be evaluated if its result is required for the current context. You are free to work with models of data like "the integers" or "all possible game states".
Concretely in C if you wanted to find the smallest positive integer that satisfies some property P you would write something like
This is a single node in your program tree which modifies a variable until a condition is met.In contrast in Haskell you might do something like
I would interpret this as find operating on an infinite lazy tree and discarding the infinite tail list (which is an infinite computation) once the result is found.Applying this simple example, in Haskell you aren't concern with limiting the shape of your program's tree. You build the correct model for your program regardless of constraints like infinite lists or terminating searches early. You just allow non-strict evaluation to process your input data because you will never have to strictly generate an infinite integer list before scanning it.
At root non-strict semantics is just a reversal of the order of reduction of expressions.
Beautiful comment btw.
And unix pipes, and node.js streams...
Your intuition about a middle ground is interesting. Perhaps one of javascript's derivative languages could come up with some syntax to make using this more intuitive, because let's face it node.js streams would be easier to use if there were some way of plumbing them together that didn't look like Java from 1999.
I was exposed to them in the Haskell music library Euterpea in the Haskell School of Music [2]. The signal processing API uses arrows.
[1] Generalizing Monads to Arrows. John Hughes. http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf
[2] http://haskell.cs.yale.edu/?post_type=publication&p=112
You might want to checkout purescript, which I'm pretty sure uses Monads to make stream interaction intuitive. No time for an example, but I believe there is one somewhere in the Purescript book[0].
0: https://leanpub.com/purescript/read
GHC tries to do its best with its strictness analyzer; it looks it works in many simple cases, still blowing up in non-trivial places, producing space leaks. Although I must say that space leaks may be very well produced by a redundant strictness and people who want strictness by default seem a bit luddistic to me.
My ideal language (or rather its compiler/runtime) would do complete analyses of what strategy suits each part of the program. By the way I'm a little surprised by Haskell insistence on static analysis, disregarding tracing VM and automatic run-time profiling.
That's not actually what "non-strict" means. https://wiki.haskell.org/Lazy_vs._non-strict
quoted in the paper "Monads are Trees with Grafting" by Dan Piponi
I thought conduits and io-streams are preferred over pipes.
1. Pipes | Conduit
2. io-streams (perhaps not in 1 only because of a lack of popularity and it is new)
3. Iteratees (have some issue Pipes/Conduit do not which I can't recall)
Not sure where Machines comes in here.
http://github.com/hosh/rlet