Hacker News new | past | comments | ask | show | jobs | submit login
IO evaluates the Haskell heap : in pictures (ezyang.com)
31 points by dons on April 24, 2011 | hide | past | favorite | 13 comments



As someone who is relatively familiar with evaluation in Haskell I'm enjoying this series, but if I didn't already understand most of it I doubt I would get anything out of it. Real World Haskell has a more concrete chapter on profiling: http://book.realworldhaskell.org/read/profiling-and-optimiza.... The Haskell wikibook also has a fairly comprehensive chapter on laziness: http://en.wikibooks.org/wiki/Haskell/Laziness.


It's an interesting charge. Here’s my personal experience with the two cited resources, back when I was learning Haskell. YMMV.

RWH’s “Here’s how you get the job done” style exposition did a reasonably good job of making me feel comfortable turning on profiling of my Haskell programs, but didn’t give me much sense at all of why the particular examples they chose were particularly representative of space leaks. I went on to do some amount of performance tuning of some data structures http://blog.ezyang.com/2010/03/the-case-of-the-hash-array-ma... ... but I still managed to miss some really obvious performance bugs that Tibell caught later when he revamped my benchmarks http://blog.johantibell.com/2011/03/video-of-my-hashing-base... . I just didn’t know where to look! All I had were a bunch of patterns: "watch out for lazy folds", "using bang patterns can be a good thing", without any particular mental model of how to deduce these things from just looking at code.

To be honest about the Wikibooks article... I found it hard to read. (Which is terrible, since it's a wiki, and if I don't like it, I should improve the article...) Exactly why is hard to pinpoint. It might be statements like "Haskell values are highly layered"; it might be the fact that none of the examples are in motion (they don’t show before-and-after; the actual operation of the program!); it might be that in many respects, its coverage is incomplete.

Obviously, this series isn’t going to be the be-all, end-all reference for laziness. While it would be extremely gratifying to see other people take up the ghosts and presents metaphor, I’ll be content if people walk away with a sort of visceral feeling about all the churning that goes on under the hood when they write a functional program, so that it’s not surprising when a trace statement shows up much later than you expect it and so that it’s not a matter of trial-and-error inserting bang-fields and seqs.


Really, my reason for saying I wouldn't learn anything is because I personally learn better from concrete examples. That's why I like the RWH chapter. It gives you knowledge of how GHC represents your program, and helps you use that to change your program accordingly. Perhaps I should have reserved my criticism for the end of the series. Hopefully you will show us how to apply your model to our real programs. For instance, I think it would be neat to have a simple example of, say, folding a list. Show us what happens when we make a field strict. Show why `True || undefined` doesn't blow up. Just some suggestions.

I agree with you on the wikibooks article. I included it so someone reading my comment would have a place to go for the rest of the story that RWH doesn't talk about.

(By the way you might want to reformat your links, HN seems to have misinterpreted them.)


Good suggestions, and I hope to do them.


As someone who is not, I wholeheartedly agree. Amusing pictures, but I feel no more enlightened.


I'd love to know if you could characterize the feeling more precisely :-)


I essentially know zero Haskell, so consider me below a n00b for reader-level. I may not be your target. And I may be making massive, not-even-beginner-level mistakes in my understanding. Feel free to tell me so, or resort to "it's complicated, read book X", I'll do so if I have time :)

The first two articles in the series (which I read after posting the comment - I never knew Haskell worked that lazily, so that was a bit enlightening) seem aimed at a pretty introductory crowd. Text and images flowed together well, and they were easy to understand. Though I don't follow the "gift card" vs "thunk" differentiation - you have this in the first article:

>... the Haskell heap is a heap of presents (thunks).

>... Presents tend to have names, and sometimes when you open a present, you get a gift card (data constructor) telling you where the rest of your presents are.

And in the second, you have this for "indirection":

>Unlike gift-cards, you have to open the next present (Haskell doesn’t let you evaluate a thunk, and then decide not to follow the indirection...)

"gift-cards" are never explained as having any properties, and it seems to be saying they are the contents of (some) thunks. Which you can't see without evaluating, which would force you to follow the indirection, which means gift-cards do what? Describe indirection without forcing you to follow them? If the heap is thunks, this seems contradictory.

---

I think the part that lost me the most was the end of the 3rd article, with this:

>If you’re unsure when a thunk is being evaluated, add a trace statement to it, and add some extra print statements in your IO code to separate various stages of your program. If ghosts are being lazy behind your back, the trace statement won’t show up in the right place.

Followed by the images showing no trace output. Given the opening, and the "ghost" retrieving the result, and that Mr. Trace is "lazy"... it, too, seems contradictory. I want to think it has already been evaluated, so the trace won't be triggered, but the ghost and "lazy" is implying otherwise given the earlier examples. And "won't show up in the right place" doesn't seem to be supported in a useful way by zero trace statements. Though it also sounds like evaluating the package somehow retrieved the value of X without triggering the trace around it, which seems like it would make Haskell horrifyingly difficult to debug.

That may all be resolved by my better understanding the system, or a different image, or more text following it - "won't show up in the right place" is a bit of a comprehension-cliffhanger to end on. I'm not entirely sure. Overall though, the third seems more fractured than the first two, especially around using terms and behavior that aren't really explained.


Ah yes, I've failed to say anything about what data constructors are. I've updated that paragraph with a little more text.

The end of the 3rd article is confusing, because the text and images don't match up! I've tried to reword the paragraph a little bit.

I’ve re-edited the third post for flow and cohesion. I hope you like it!


Data constructors still seem vague to me, I don't follow how a gift card specifying another present is different than a ghost specifying another present. I understand that it is, but not how, even metaphorically. Or is it that the only difference is that one is required to be followed and one is not? And in that case, why not make everything optional, and prevent unexpected explosions?

The 3rd does read better, and that extra paragraph helps. I still think a different image / an example of or reason for the trace happening later would be good, as it still seems like X was opened and used (in getting the "2") but no trace output was generated. Kind of. Otherwise, why are they expecting X to be opened? If it's an item in a list that's unnecessary and therefore un-touched, that would make sense, but that doesn't seem to be the situation from the image. Or does it just take time for the trace output to be spat out?


The idea is that a gift card is "good enough"; some useful information can be derived from it, whereas an indirection is never "good enough"; if you're told your present is in another castle, you're no better for the wear: it's as if you've accomplished nothing at all. I think I might be able to capture that in a small pastiche.

That was the original idea for the comic. But it seemed like it would be really complicated, so I simplified it (but failed to update the text :-). But the simplification really fails to capture why you might expect x to be evaluated, even when it's not. It's all a bit dodgy. I'll sleep on it and see if I come up with anything better. It's certainly not the case that the trace output "takes time."


>It's certainly not the case that the trace output "takes time."

That's what I figured, just wanted to throw out the possibility :) I'll happily keep reading, you've got me interested, at the very least. Want me to send you critiques if I come up with them? On blog / email?


Either's fine. :-)


I think the section of the Wizard book (SICP) on streams may also prove helpful to those trying to gain a deeper understanding of lazy evaluation.

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: