![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
chancho 1412 days ago
| link |
This is an interesting read. One part jumped out at me (sorry for the long quote)
The purpose of the technical problem was to assess more directly candidates ability to write Haskell programs that can be used to solve real world problems, where memory usage and performance are important. The problem was all about evaluation order and memory behaviour. We started by asking candidates to look at a short program and say what shape they would expect the heap profile to be. That would then lead on to a discussion of what things are evaluated at what stage and how much memory they are taking in the meantime. For the final step we asked candidates to rewrite the program to run in constant space. We felt overall that the technical problem was quite useful and we allowed it to become a significant factor in our final decision making process.
The choice of problem is based on our belief that a good understanding of evaluation order is very important for writing practical Haskell programs. People learning Haskell often have the idea that evaluation order is not important because it does not affect the calculated result. It is no coincidence that beginners end up floundering around with space leaks that they do not understand.
I've written a lot of C++ and a fair amount of Haskell, and this kind reasoning about the evaluation order and space usage of Haskell a program is no less of a black art than pointer arithmetic or manual memory management in C++. In both cases, it's too steep of a learning curve to just be able to write practical programs, which is why garbage collected languages have displaced C++ in many domains.
It's particularly damning to say that "good understanding of evaluation order is very important for writing practical Haskell programs" because the easiest evaluation order to understand is strict evaluation order. In that sense, lazy evaluation is to strict evaluation as manual memory management is to garbage collection, except that the latter is supposed to be an improvement on the former.
wnoise 1412 days ago
| link |
I would actually say that pointer arithmetic and manual memory management are _easier_ than managing space by controlling evaluation order.
The real benefit of lazy-evaluation is that it decouples generation from consumption in a very thorough way. Unfortunately it often doesn't scale up as space leaks attest. I'm starting to think that in the large it should be feasible to replace it with CSP-like channels, though this is essentially boiler-plating the runtime code, it gives far more fine control.
I'd say also say that automatic memory management is similar. The downside to manual is not all the debugging difficulties per se, but the fact that you do have to decide who allocates, who deallocates, and that these decisions are highly coupled and can greatly impact the choice of feasible data structures.
prodigal_erik 1412 days ago
| link |
I see one major difference: a Haskell program with optimization mistakes will run slowly and waste memory, its performance will improve as you fix them, and eventually you can stop because it's sufficient. A C++ program with any memory mistakes whatsoever will blow up randomly, and will continue doing so after you give up trying to make it perfect (which is hardly ever feasible) and ship unstable crap like the rest of the industry.
http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/
" Abstract Type says: April 25, 2011 at 4:53 pm
I’m not sure that I’ve made the argument well, but I wanted to separate issues, and to argue that the black box view of laziness is appropriate for managing interaction (and not relevant to supporting coinductive types in the pure part). "
---
" In a lazy language non-termination is a value, whereas in an eager language it is an effect. In particular, variables in a lazy language range over computations, including the non-terminating computation, whereas in a strict language they range only over values " -- http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/#comment-798
---
http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html
" Lazy bindings any subexpression can be named and "pulled out", modulo name capture, of course. ...
Lazy functionsEven strict languages like ML and C have some lazy functions even if they don't call them that, like SML's if, andthen, and orelse
...
For some language constructs the solution adopted by Smalltalk (and later Ruby), i.e., a very lightweight way on constructing closures is acceptable. So, for instance, I could accept writing
... myAnd x {y} ...(In SML you could make something using functors, but it's just too ugly to contemplate.)
... Lazy constructors Lazy constructors were sort of covered in what Bob claimed to be the point of laziness, so I'll just mention them for completeness. Sometimes you need them, but in my experience it's not very often.
...
Cyclic data structures.... Sometimes you really want cyclic data structures. An example are the Haskell data types in Data.Data that describe data types and constructors. A data type descriptor needs to contain a list of its constructors and a constructor descriptor needs to contain the data type descriptor. In Haskell this can be described very naturally by having the two descriptors reference each other. In SML this is not possible. You will have to break the cycle by somthing like a reference (or a function). In OCaml you can define cyclic data structures in a similar fashion to Haskell, so this isn't really a problem with strict languages, but rather a feature that you can have if you like. Of course, being able to define cyclic data leads to non-standard elements in your data types, like
data Nat = Zero | Succ Zero
omega :: Nat
omega = Succ omegaSo having the ability to define cyclic data structures is a double edged sword. I find the lack of a simple way to define cyclic data a minor nuisance only.
...
ReuseI'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,
any p [] = False any p (y:ys) = y
| any p ys |
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).
... 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. ...
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.
...
ComplexityAnother complaint Bob Harper had about lazy evaluation is the difficulty of finding out the complexity of functions. I totally agree that the space complexity is very messy in a lazy language.
" -- http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html
" Blogger Existential Type said...
I think the only serious gripe is what you call your biggest gripe, and I must say that I envy this in Haskell. As you know, in the eager world we tend to write out our own recursive functions, rather than use combinators. You give part of the reason; the other part is that deforestation and related transformations are not valid, at least not in the presence of effects. (But, as I've pointed out before, dual transformations that are valid in ML are not in Haskell. You basically trade strictness conditions for totality conditions.) I've made my peace with this, but I agree that you have a point (ahem).
Monday, May 2, 2011 at 7:56:00 PM GMT+1" -- http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.htmlBlogger Frank Atanassow said...
It seems like you and Bob would both be pretty happy with a call-by-name language: you get predictable interaction with effects, full beta-reduction and a reasonable parallel cost model.
I don't have any experience programming with call-by-name, but on the surface it seems like you could program pretty much as in Haskell, except you would want to memoize some thunks when terms get duplicated. Or am I missing something?
Monday, May 2, 2011 at 10:24:00 PM GMT+1 Blogger Lennart said... @Frank I have no experience with a pure call-by-name language so I don't know how painful it would be. I suspect it's not pleasant.
Monday, May 2, 2011 at 10:37:00 PM GMT+1 Blogger Greg Morrisett said...I don't think you should dismiss a language where there is a pure (total) core functional language, and where all effects, including non-termination and exceptions, are banished to a secondary language (e.g., monad). An example is Coq + the Ynot monad.
There, you get the best of both worlds. You get to evaluate the pure fragment CBN, CBV, or CB-need or however you see fit. (Though I think I prefer a cost model that leans towards CBV to avoid the space problems Bob mentioned. However, to support control-abstraction, which I also think is important, you might lean towards CBN or CB-need.) You get to factor everything out with "let" if you like. You get to do de-forestation. The compiler doesn't have to do strictness analysis. You can add "strictness" annotations to types or calls to seq and have it not break all of those nice properties Haskell folks claim they have for small programs, but never have for big ones.
There are other advantages. Integrating dependent types is easier. Embedding DSLs with control requirements that rule out divergence or exceptions becomes possible. And you get to do Curry-Howard, something you can't pull off in Haskell at all, and in ML only when you do silly things like restrict dependencies to A-normal form (c.f., Leroy's modules.)
Tuesday, May 3, 2011 at 3:58:00 AM GMT+1 Blogger Lennart said... @Greg I didn't in any way mean to dismiss languages with a total core, I only meant to say that I wasn't talking about those languages. Indeed, I have for a long time wished for such a language for exactly the reasons you outline. (Also, as a compiler writer I love the idea that evaluation order is left up to me rather than the language spec.)
Tuesday, May 3, 2011 at 8:42:00 AM GMT+1 Blogger Alastair Reid said... I think Scala has an interesting approach to defining your own control constructs. It lets you declare a function parameter as call by name and it automatically inserts a lambda round the actual parameter and an application round uses of the formal parameter.
Just one of Scala's tricks to make it easier to implement EDSLs.
Tuesday, May 3, 2011 at 9:18:00 AM GMT+1 Blogger Frank Atanassow said...@Lennart Just an aside, but: I would love it too, but even with a total core, I don't think it is practical to let the user choose an evaluation regime.
For example, Brian Howard published a type system (1995, I think) for inductive/coinductive types and total functions which can encode Ackermann's function, so you could write programs that, even for very small inputs, probably would not terminate before the universe ends: efficiency would still be an unavoidable issue.
I think any non-tiny program would need to be written with an evaluation order in mind.
Tuesday, May 3, 2011 at 12:57:00 PM GMT+1 Blogger martin said...Lennart, I think re-use falls short in Haskell as well as in ML. The core of the problem is that functions such as any, map, fold are defined on a particular concrete datatype. With lazy lists as the datatype you get some useful composition laws that you don't get with strict lists.
But you can achieve much higher reusability if collection methods are defined uniformly over strict as well as lazy collections. In Scala, map, fold, exists are methods that work on any kind of collection. They are strict for strict collections and lazy for lazy collections. And it's perfectly possible to abstract and write your own operations that have the same adaptive behavior.
So then the only re-use argument in favor of laziness is that refactorings like the one you describe are efficient only if one assumes the collection is lazy. In other words, by restricting the domain to lazy structures you get more performance-preserving transformations. For me that argument is not so convincing. Sure, you need to work harder to write utility functions that perform unformly well on strict as well as lazy collections. But once that's done these functions will be more reusable and therefore ultimately more useful.
Tuesday, May 3, 2011 at 3:16:00 PM GMT+1 Blogger Lennart said...@Martin I don't totally agree with that. The definition 'any p = or . map p' is just the wrong one for a strict language. It doesn't matter if 'or' and 'map' are overloaded for different kinds of collections, it's still wrong for strict collections. (BTW, Haskell has this kind of reuse if you use Traversible etc.)
But I do agree that Haskell is lacking in reuse, but my gripe is more about mapM vs map etc.
Tuesday, May 3, 2011 at 4:46:00 PM GMT+1 Blogger Edward Kmett said...@Martin
In Haskell, we have Data.Foldable ( http://www.haskell.org/ghc/docs/7.0.3/html/libraries/base-4.3.1.0/Data-Foldable.html ), which affords 'container-centric' opportunities to optimize folds in general and ( http://www.haskell.org/ghc/docs/7.0.3/html/libraries/base-4.3.1.0/Data-Traversable.html ) which provides monadic and applicative traversals in the same spirit.
This in turn provides the opportunity to optimize any, all, etc.
Tuesday, May 3, 2011 at 10:55:00 PM GMT+1Blogger Lennart said...
@Frank I have some minimal experience with call-by-name, and frankly I find it difficult to use. For instance, the function that doubles a number:
dbl x = let x' = x in x' + x'
Wednesday, May 4, 2011 at 4:58:00 PM GMT+1 Blogger Andreas said... I agree with most of your post, but I never found the argument about custom control operators particularly convincing. If anything, they would rather be an argument for call-by-name -- laziness may happen to work for `if', but what about, say, `while'? Of course, if your only effect is non-termination you might not care, but in general?
Friday, May 13, 2011 at 8:11:00 PM GMT+1Blogger shelby said...
Appreciated this article. Some points:
1. Lazy also has latency indeterminism (relative to the imperative world, e.g. IO monad).
2. For a compiler strategy that dynamically subdivided map for parallel execution on multiple cores requires it not be lazy.
3. any = or . map is not "wrong" for eager (strict) evaluation when there is referential transparency. It is slower in sequential time, but maybe faster in parallel execution.
4. Wikipedia says that for Big O notation, 0(n) is faster than O(n log n) = O(log n!). @Lennart, I think you meant to say that O(n) is faster than O(n log n).
5. Given that laziness causes space and latency indeterminism, if the main reason to use lazy is to avoid the performance hit for conjunctive functional composition over functors, then only functions which output applicable functors need apply laziness. As @martin (Odersky) suggested, provide lazy and eager versions of these functions. Thus eager by default with optional lazy annotations would be preferred.
Sunday, July 31, 2011 at 11:26:00 PM GMT+1 BloggerBlogger shelby said... ... Could you tell me why lazy (with optional eager) is better for you than referentially transparent (RT) eager (with optional lazy), other than the speed of conjunctive (products) functional composition? Your lazy binding and lazy functions points should be doable with terse lazy syntax at the let or function site only, in a well designed eager language. Infinite lazy types can be done with the optional lazy in an eager language with such optional lazy syntax. Those seem to be superficial issues with solutions, unlike the debugging indeterminism, which is fundamental and unavoidable.
...
Blogger augustss said... But debugging and error messages are indeed better in a strict language. That said, I hardly ever use a debugger in Haskell. Proper stack traces on errors is what I really miss in Haskell. Thursday, August 4, 2011 at 12:26:00 AM GMT+1
Blogger Existential Type said...
Lennart's right that in a lazy language it is quite easy to define functions that rely on their arguments not being evaluated prior to the call. If laziness were a type, and if the syntax were civilized, then it wouldn't be so different in an eager language, eg writing %e to mean that e should be suspended (and memoized).
In my mind however the conditional branch is not an example of this phenomenon. The expression "if e then e1 else e2" is short-hand for a case analysis, which binds a variable (of unit type) in each branch. So the conditional is not "lazy" at all; rather, it is an instance of the general rule that we do not evaluate under binders (ie, evaluate only closed code).
Monday, August 15, 2011 at 10:16:00 AM GMT+1Blogger shelby said... ...
Eager is an *inductive* evaluation model, meaning we run the leaves as we as build the nested function tree of runtime possibilities.
Lazy is a *coinductive* evaluation model, meaning we run the leaves as needed from the nested function tree of runtime possibilities.
Eager can't instantiate coinductive types, such as bottom (i.e. the entire Universe) or any infinite type, but it can instantiate inductive types such as the natural numbers.
Lazy can instantiate coinductive types, such as bottom and infinite types, but it can't instantiate inductive types such as the natural numbers.
See Harper's explanation:
http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/#comment-798
Eager does not have conjunctive products, so we can't do general function composition (e.g. or . map p) without potentially doing evaluation that is not shared (i.e. required) by the conjunctive result.
Lazy does not have disjunctive sums, so we can't do logic such as:
((if ... then 1 else 2),3) == if ... then (1,3) else (2,3)
For example, if we only evaluate the second element in a lazy language and if ... has an exception, then the left version will not generate the exception, but the right version will.
I suppose most people think rather inductively.
And models can be used in eager to provide conjunctive products for some cases.
Sunday, October 7, 2012 at 11:02:00 AM GMT+1Blogger Márton Boros said...
Fexprs can be used to abstract control structures in a strict language. Fexpr vs lazy?
Monday, January 28, 2013 at 2:38:00 PM GMT Blogger augustss said... Show me a live language that has fexpr. :)
Monday, February 18, 2013 at 5:18:00 PM GMT Blogger Unknown said... "a live language that has fexpr" -- R, the statistics package.
Sunday, July 28, 2013 at 6:11:00 AM GMT+1---
" R does not prevent the declaration of ambiguous multi-methods. At each method call, R will attempt to find the best match between the classes of the parameters and the signatures of method bodies. Thus add(r, l) would be treated as the addition of two “Point” objects. The resolution algorithm differs from Clos’s and if more than one method is applicable, R will pick one and emit a warning. One unfortunate side effect of combining generic functions and lazy evaluation is that method dispatch forces promises to assess the class of each argument. Thus when S4 objects are used, evaluation of arguments becomes strict " -- http://r.cs.purdue.edu/pub/ecoop12.pdf
---
---
" when your components are written in a lazy fashion, you get far greater compositionality than than you otherwise would. (If you don't know what I'm talking about, one good paper on this is "Why Functional Programming Matters", by John Hughes, which actually goes so far as to take the viewpoint that laziness plays an essential role in gaining the benefits of functional programming.) If instead, you are simply allowed to construct lazy things, but your libraries are full of things which end up forcing their evaluation anyway, then nearly all the benefit is gone, save for a few small cases where you end up implementing an entire system with your own lazy or partially lazy structures. " -- http://www.reddit.com/r/programming/comments/pylx/ask_reddit_why_is_ocaml_faster_than_haskell/cq1c8
---
" consider writing a program that implements the AI for some game. With nonstrict semantics, you can write the code which generates a full game tree, and then separately write code which searches through it in various ways. You don't end up mashing the tree generation code into the search code. " -- http://www.reddit.com/r/programming/comments/pylx/ask_reddit_why_is_ocaml_faster_than_haskell/cq5ok
[–]gogath 3 points 7 years ago
"In a pure (referential transparent) functional language you can't create circular structures without lasyness. So if you want to enjoy the benefits of referential transparency and also want circular data structures, you need lasyness." -- http://www.reddit.com/r/programming/comments/pylx/ask_reddit_why_is_ocaml_faster_than_haskell/cq5hz
---
" The problem is with the use of tail recursion for iteration. A properly tail recursive implemen- tation prevents tail calls from needlessly filling up memory with trivial stack-frames; but if lazy argument evaluation is practiced naively, then memory may fi ll up instead with lazily unevaluated expressions. This was the original reason why Scheme opted f or eager argument evaluation; [SuSt?75, p. 40] notes, “we ...experimentally discovered how call-by -name screws iteration, and rewrote it to use call-by-value.” That paper discusses the issue in more d etail on [SuSt?75, pp. 24–26]. " -- https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf
---
