Yuhao Dong wrote:
The thing is, Racket's "stack" is a list of continuations. I don't see how explicitly keeping the "stack" in an accumulator would help. Stack overflow won't be a problem since the "stack" is a list on the heap, and unless memory runs out you wont overflow.
I think that tail recursion doesn't help at all, and introduces conceptual overhead. Racket doesn't use the stack, and converts to continuation-passing, which is surprise-surprise *tail recursive* at runtime anyway.
Yuhao, I think you got some of these ideas from lectures I gave almost exactly a year ago, but you may have forgotten or misunderstood some points I made at the time:
* Simply making an interpreter tail-recursive does not guarantee that that the interpreted program will use memory wisely. It only ensures that there is no stack overhead due to recursive applications of the interpreter itself (either through tail-call optimization [TCO] in the language the interpreter is written in, or trampolining/looping in a language that does not support TCO).
* The way in which we made the interpreter tail-recursive, by using a zipper on the AST which introduced a list of continuations to manage control, did ensure that if the interpreted program was tail-recursive, the list of continuations would not grow. We could see this by looking at the interpreter code and noting that continuations grow only when arguments are evaluated down to values and not when a function is applied to a value. However, if the interpreted program is not tail-recursive, the list of continuations will grow, because of the pending computation in the interpreted program. Furthermore, because that list of continuations is on the heap instead of the stack, there will be overhead associated with allocation and garbage collection.
* The development in lecture was an illustration of one way of achieving the goal of TCO in an imperative implementation that could be understood after six months of exposure to functional programming in Racket. But Racket itself has a more sophisticated implementation that incorporates more advanced ideas and optimizations. It does use the stack as well as the heap, but not in the simple way that a direct translation of the naive (non-tail-recursive) interpreter would.
I hope that helps clarify things. The lecture material was my attempt at giving you a sense of the ideas behind Racket's implementation, but it was not a description of what Racket actually does under the hood. That would probably take a whole course on its own, and a better teacher. --PR
____________________ Racket Users list: http://lists.racket-lang.org/users
