[racket] Tail recursive module cons

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