Comment by jpolitz | Hacker News Reader

Comment by jpolitz | Hacker News Reader

Parent Full thread

I don't know what you mean by "it doesn't really matter." Surely there's a cost to using generators instead of regular function calls and returns, right? That's where the overhead would come from, because generators aren't free.

Right now, Pyret and GopherJS (the last time I checked in GopherJS's case) basically manually encode the `IteratorResult` type, and check for "stack unwind" vs "regular result" when each function call returns, if it might pause.

The first question for generators is if they are less overhead than this manual process. There's a bunch of other details, too, but this is the main one. And generators are certainly going to cause _some_ overhead over regular calls and returns, just like the manual checking of return values has overhead.

My original comment was about the lack of something like delimited continuations in JS, which would allow saving portions of the stack while intentionally minimizing the overhead of regular function calls. That's a well-fitting language-level solution to this issue.

Ah! You're right. Now I get what you mean. Thanks.

No problem. Thanks for asking bluntly about generators. It made me write some more experiments using them.

Right now, the main thing that I think stands in the way of them being a good solution for Pyret is that they have limited stack depth – about 7000 frames on Chrome Canary, for instance. One thing we get out of our strategy, which reifies stack frames onto the heap when pausing, is that we can simulate a much deeper stack.

See http://imgur.com/a/GaBg2 (I don't need to be able to do sum of ten million, but 10,000 would be nice! This is just so a non-tail-recursive map works over reasonable-sized lists; we'd rather not have the concept of tail recursion as a curricular dependency for working with that size of data.)

Pyret looks like a good endeavor.

Another dumb question: doesn't every recursive function have an iterative version? and in the case where you're transpiling to JS couldn't 'map' (whatever the syntax in Pyret) and other functional primitives be converted to imperative code? Generator functions are no different than regular functions when it comes to stack depth. I think that depends on the amount of memory you have, so different from machine to machine. I'm learning by asking dumb questions... :)

> doesn't every recursive function have an iterative version

True in the abstract, yes. But it's a sophisticated compiler indeed that turns something like a recursive binary tree traversal into a loop (it would need to synthesize the stack worklist).

In practice, it's easy to do this for tail recursion (and mutual tail recursion, with a little more sophistication). You can get slightly fancier with "tail recursion modulo cons," which is a little more clever and handles map. Beyond that, it's pretty gnarly to do a good transformation, because recursive code is implicitly using the stack in interesting ways.

> couldn't... functional primitives be converted to imperative code

Indeed, and we do write those in pure JS with carefully-crafted while loops to make those primitives more efficient. But if students are learning to write their own map, or another functional combinator on lists, those need to work, too, and will be implemented recursively by them.

> Generator functions are no different than regular functions when it comes to stack depth.

Yeah, stack depth in general is annoyingly low on modern browsers, IMO, so this isn't just a problem with generators. It's also unpredictable (http://stackoverflow.com/a/28730491/2718315). So we're working around the normal stack limit already. I was sort of hoping that when a generator's continuation was captured, it would stay heap-allocated and not "count" towards stack space when restarted, but that's not the case.

Reply on news.ycombinator.com