5 ms·

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 t

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.

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.