Thanks. I probably mixed it up also with the implementation of the compiler targeting C of Chicken Scheme, which basically just converts everything to continuation-passing style.
I think my point still holds that tail recursion in the case I posted does not improve performance. At least the timing numbers say so. Of course, the memory consumption may be larger with the non-tail version, as I suppose each continuation frame contains more information than a number. On Sat, 2014-03-29 at 08:06 -0400, Prabhakar Ragde wrote: > 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
