3 ms·

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

jpolitz 10y ago
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 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.)
- ilostmykeys 10y ago
  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... :)
  - jpolitz 10y ago
    > 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 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.

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 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.)

ilostmykeys 10y ago
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... :)
- jpolitz 10y ago
  > 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 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.