Non-linear continuations considered harmful

[Eric W. Biederman]

I+fare+WANT@tunes.NO.org.SPAM (fare@tunes.org) writes:

> 
> I _naively_ believed that the above loops (where ... did not modify n)
> where essentially equivalent, the former being a "lower-level" version
> of the latter, into which the latter would actually compile, with the
> (loop) being a mere goto, etc. I sincerely believed that Scheme made
> iteration and tail-recursion equivalent. How stupid I was!
> 
> Then, I tried to actually implement a Scheme compiler,
> and I was struck by reality:

Fare begins to see the light.

First consider the macro expanded version of your code:
i.e. With variables and iteration done complete with lambda

(lambda ()
	((lambda (n loop) (loop loop))
	(* 1024 1024 1024 1024)
	(lambda (the-loop)
		(if (not (zero? n))
			(begin
				(set! n (- n 1))
				(the-loop the-loop))
			nil))))

(lambda ()
	((lambda (loop) (loop loop (* 1024 1024 1024 1024)))
	(lambda (the-loop n)
		(if (not (zero? n))
			(the-loop the-loop (- n 1))
			nil))))

With everything expanded many more functions appear and the scope of
n becomes clear.  In the version with assignment it's longer life
is simply because it is in a larger scope. 

Fare activation frames do not need to be read-only.

Using a stack in scheme to hold activation frames is a practical optimization
but because of (call/cc) and other closures it is tricky.

However for a simple implementation consider placing all of the activation
frames on the garbage collected heap.  This frees the compiler from worrying
about the lifetime of activation frames.

Note: It is still important in this contect to do proper tail recursion
optimization, otherwise the examples above will die due to lack of heap space.

Basically proper tail recursion means that when b is the final function
called by a, that when b is activated there are not references to a's 
activation frame in the closure b is passed.

Allocation of activation frames on a stack, and combinding stack
frames are important optimizations.  Allowing good cache hit rates,
and better memory usage.  Unfortunantely I just know the basics.

Eric