[racket] Tail recursive module cons

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