![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
should laziness only apply to pure things? eg if a function has side-effects, should its output always be computed eagerly even in a situation where, if it had no side effects nor nondeterminism, it would have been computed lazily?
clearly if this is so, some attention must be paid to which statemask is relevant for this decision
---
so i guess if functions are or can be lazy in any argument, then we effectively already have operative/vau stuff that Kernel talks about, right?
some disagreement:
" Yes, the option for lazy evaluation with sensitivity to lexical scope is one of their interesting benefits.
No, it's not *quite* Haskell for with FEXPRs, you have something lacking in Haskell: a deep equivocation of data structures (e.g., structures formed from constants and from CONS) with code (that which can be evaluated) that is nicely (simply, directly, usefully) related to the rest of the language. For high-falutin' theory stuff, have a look at appendix C of The Revised^-1 Report on the Kernel Programming Language. "Code == Data" is pretty deep and hairy in some ways and on the other hand intuitively simple and tractable in others. It's deeply part of what makes a lisp dialect a lisp dialect. Round about the time of the Revised Revised Report on Scheme the demi-gods of Scheme standardization shoved aside "Code == Data" -- initially appearing to merely postpone the topic but in the past decade seemingly intent on killing it entirely. And this in spite of mounting evidence that the rationales they offer for doing so simply don't add up. But enough about "them"....
FEXPRs are not quite simply "lazy evaluation" in the sense of "normal order reduction of lambda calculus terms" because they add concepts like data structures (such as cons pairs) and first class environments. "
oh, i think the difference is that Kernel operatives are actually call-by-text, not call-by-need:
" There is an adjective call-by-text in the literature meaning what is here called operative; but the Kernel term applicative has no equivalent of the form call-by-X . Adjectives call-by-X are used in general to specify when the operands are evaluate d to arguments, as call-by- value (eager) or call-by-name (lazy) ([CrFe?91]); but applicative is intended to mean only that the combiner depends on the arguments, without any impl ication as to when the arguments are computed. " -- Revised^-1 Report on the Kernel Programming Language section 1.3.1 pdf page 16
http://lambda-the-ultimate.org/node/3861#comment-58187 says "By peeking inside operands, for example, an operative can distinguish between whether '1+1' or '2' was used in some external component."
---
i guess our requirement is:
non-strict (unevaluated infinite sequences or undefined arguments do not cause hangs or undefined results), and in practice lenient, but furthermore:
the time and space spent by creating/passing a very large unevaluated argument is bounded by O(log(argument_size)). This is needed to ensure that our lenient evaluation does not evaluate too much when passed eg all possible paths through a chess game
(do we really want undefined arguments not to cause an error? mb..)
---
" Sequences
Both Clojure and F# are great for composing functional pipelines that work on sequences.
Both offer lazily evaluated sequences. Clojure’s lazy sequence results are cached by default whereas F# has Seq.cached. Clojure’s lazy sequences are usually realized in chunks, and so can have some unintended consequences if you mix side-effects with laziness.
There’s another notable difference I’d like to highlight. Take these similar examples:
[0..10]
| > Seq.map (fun x -> x + 1) |
| > Seq.filter (fun x -> (x % 2) = 0) |
| > Seq.sum |
(->> (range 0 11) ;; upper bound is exclusive (map inc) (filter even?) (apply +))
In both languages, map and filter will each create intermediate lazy sequences to be evaluated later during summation. There is a cost associated with those intermediate sequences/thunks. Clojure has the concept of transducers, but I’m not aware of any similar idea in F#. Transducers compose operations on sequences such that no additional intermediate sequences are required — the transducer functions are composed and applied in one pass.
(transduce (comp (map inc) (filter even?)) + (range 0 11))
The transducer example is ~7x faster than the original Clojure example! It’s too large a topic to explore in this post, but transducers are a nice tool to have, and there are other power tools in Clojure’s reducers. " [1]
---
" Reuse I've saved my biggest gripe of strict evaluation for last. Strict evaluation is fundamentally flawed for function reuse. What do I mean? I will illustrate with and example. Consider the any function is Haskell:
any :: (a -> Bool) -> [a] -> Bool any p = or . map p
It's quite natural to express the any function by reusing the map and or functions. Unfortunately, it doesn't behave like we would wish in a strict language. The any function should scan the list from the head forwards and as soon as an element that fulfills the predicate is found it should return true and stop scanning the list. In a strict language this would not happen, since the predicate will be applied to every element before the or examines the elements.
So we are forced to manually fuse the two functions, doing so we get:
any :: (a -> Bool) -> [a] -> Bool any p = foldr False (\ x r -> p x
| r) |
or :: [Bool] -> Bool or = foldr False (
| ) |
foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)
But the misery doesn't end here. This still doesn't do the right thing, because the strict language will recurse all the way down the list since it will call foldr before f. So we either have to fuse again, or invent a new version of foldr that delays the recursive call. One more fusion gets us to
any p [] = False any p (y:ys) = y
| any p ys |
So where's the function reuse? Nowhere in sight.
With strict evaluation you can no longer with a straight face tell people: don't use recursion, reuse the recursion patterns in map, filter, foldr, etc. It simply doesn't work (in general).
Using macros doesn't really save us this time, because of the recursive definitions. I don't really know of any way to fix this problem short of making all (most?) functions lazy, because the problem is pervasive. I.e., in the example it would not be enough to fix foldr; all the functions involved need to be lazy to get the desired semantics.
I find this the biggest annoyance with strict evaluation, but at the same time it's just an annoyance, because you can always rewrite the code to make it work. But strict evaluation really, fundamentally stops you from reusing functions the way you can with laziness.
As an aside, the definition of any doesn't work in SML for another reason as well, namely the value restriction. But that's just a language wart, like the monomorphism restriction in Haskell. " [2]
---
winterkoninkje 6 points · 8 years ago
That's one of my big disagreements with him.
The strict-by-default style is easy to reason about superficially, but is extremely problematic for large-scale semantic reasoning. The lazy-by-default style requires you to pay attention to a lot of things you can ignore in SBD, but it allows you to perform large-scale reasoning which enables you to perform non-trivial program transformations (e.g., list fusion, array recycling). So, for my money, LBD is the only viable choice.
That said, Haskell's laziness (or rather, the strictness associated with it) can be problematic semantically. Just look for any number discussions about polymorphic seq breaking everything. While LBD is much better than SBD, I think it would be better still if strictness properties were expressed in the type system so that we could reason about them explicitly rather than implicitly.
apfelmus 5 points · 8 years ago
He probably means that laziness is not the a natural cost model to teach to first year students.
The implications of laziness on modularity are pervasive, however. Strict evaluation makes it much more difficult to implement your own control structures, e.g. for monads >>, when etc. level 3 notfancy 3 points · 8 years ago
s/difficult/ugly in my opinion: you have to thunk everything explicitly, but it is not more difficult in principle than converting from DS to CPS.
level 3 stephentetley 2 points · 8 years ago
This doesn't tally with my experience, but then most of the software I write doesn't work on huge amounts of data.
On Stack Overflow, I do see a lot of problems where people expect lazy evaluation to be magic and work within a low memory profile when they are using data types - e.g. trees or graphs - that don't naturally stream (unlike lists). In a strict language they would still have the same problems. level 4 Tekmo 3 points · 8 years ago
Most of the software I write does work with a lot of data, and I do manage to get it to work. The problem is not the language so much as the compiler since it's not easy to tell how it will spot optimization opportunities. Even the most minor of changes to the code can make it miss an opportunity to fuse or garbage collect. level 5 stephentetley 2 points · 8 years ago
Yes - that's true. I'd overlooked the list fusion case, where you have to be careful abut "good producers / good consumers".
level 1 fixedarrow 2 points · 8 years ago
Is it really as bad as the following quote suggests?
[...Haskell's...] unfortunate commitment to laziness, which results in an unusable cost model for both time and, especially, space
level 2 Tekmo 5 points · 8 years ago
It's only a slight exaggeration. You have to spend a lot of time learning how to make non-trivial Haskell programs not produce space leaks. level 3 tibbe 5 points · 8 years ago
You have to spend lot of time to learn anything new. The more interesting question is: once you spent time learning to reason about laziness, is it still difficult? level 4 winterkoninkje 3 points · 8 years ago
By the time I started writing non-trivial Haskell programs I've never had problems dealing with major space leaks. Then again, I was reading papers about list fusion and the performance hacks in ByteStrings? from pretty near the beginning (as well as papers about how to use laziness effectively), so I've always had these sorts of ideas at the forefront of my thinking about Haskell.
Other than the initial learning pains, I honestly don't understand what it is that people find so problematic. Maybe I'm just being dense.
hmm, seems like what we need for our lenient evaluation is to focus on these three use cases:
1) support infinite lists: fib n = fibs!!n fibs = 0 : 1 : zipWith (+) fibs (tail fibs) https://www.reddit.com/r/haskell/comments/qrf54/why_does_foldr_work_on_infinite_lists_but_not/
2) support efficient composition of reusable functions with short-circuit evaluation even if an inner function would otherwise iterate over the entire input: any :: (a -> Bool) -> [a] -> Bool any p = or . map p
3) remove the need for the user to reason about when/where to add strictness annotations and whether to use foldr vs foldl vs foldl' to avoid stack overflows: https://wiki.haskell.org/Foldr_Foldl_Foldl%27
4) space leaks: http://blog.ezyang.com/2011/05/space-leak-zoo/ http://blog.ezyang.com/2011/05/anatomy-of-a-thunk-leak/
(i guess #4 is actually more than one sub-case)
Note that #1 alone could be solved by making strict the default and then marking some values as 'lazy' e.g. clojure's lazy sequences, python's iterators. #3 and #4 alone could be solved by making everything strict (and is foldl also required for #3, not foldr'? Does foldr' even make sense?).
Note that all of these have to do with loops/cycles of some sort.
1) When evaluating an infinite list, the computer passes thru (loops thru) the same code over and over as it creates new list items.
2) When evaluating an inner function which should be 'fused' with an outer short-circuit function, the computer loops thru the same code over and over as it creates new list items.
3) When creating a space leak or stack overflow, the computer loops thru the same code over and over as it creates new thunks
This is the motivation for the sort of strategy i described before, where the computer starts with a default of either strict or lazy (not sure which one is best), but then checks itself when it finds itself looping for more than a few iterations. If it is defaulting to strict and looping through strictly evaluating things that may not be needed, it switches to lazy; but if it is defaulting to lazy and looping through creating thunks that are piling up on the stack or elsewhere, it switches to strict.
In other words, if the computer finds itself iteratively doing work that wouldn't be done in the other mode, or piling up thunks that wouldn't pile up in the other mode, then it switches.
The obvious failure mode here is if both modes are looping (which i think they often would be in a trivial and easy to solve way, but i bet sometimes they both loop in a hard to solve way? just totally guessing here, this requires more thought).
More generally, the goal is to have #1 and #2 like laziness gives you, but to have the compiler and/or the runtime do the thinking that the programmer must in Haskell to fix #3 and #4.
So i think the thing to do is first just sit down and write out some examples of #1 #2 #3 and find a lenient strategy that works for them. Next, dig into #4 and pull out some simple examples and make the strategy work for those too.
---
