Non-linear continuations considered harmful

[Francois-Rene Rideau]

> Fare begins to see the light.
:-~

> 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.
Sure.

> Fare activation frames do not need to be read-only.
Well, they do if they are on stack and that continuation capture
consists in stack-copying. Or more precisely,
read-only and write-once variables may be put on stack and
destructively recycled/updated, but read/write variables must be on heap.
Alternately, read/write variables may be put on stack iff they are never
used with set!, but always with fluid-let instead (or fluid-set! ?).

> 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.
There is no semantic problem with having activation frames in heap,
only the fact that the possibility of _non-linear_ continuation capture
prevents a whole lot of optimizations with respect to merging frames
(and a globally copied stack
can be considered as a global merging of all frames).
But indeed, I wasn't clear on that topic in my previous message
(nor was it fully clear in my mind at the time).

> 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.
In this context, tail-recursion optimization consists not in reusing frames
(which is in general impossible, due to non-linear capture),
but just in short-circuiting the value of the continuation
in the new frame, so as to return directly to the caller's caller,
instead of returning to the caller,
who would in turn return an identical result to its caller.

> 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.
Yup.

> 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.
combining?
Anyway, it appears that things become very tricky in presence
of non-linear continuation capture...

[ "Faré" | VN: Уng-Vû Bân | Join the TUNES project!   http://www.tunes.org/  ]
[ FR: François-René Rideau | TUNES is a Useful, Nevertheless Expedient System ]
[ Reflection&Cybernethics  | Project for  a Free Reflective  Computing System ]
NOTE: No warranties, either express or implied, are hereby given. All
software is supplied as is, without guarantee.  The user assumes all
responsibility for damages resulting from the use of these features,
including, but not limited to, frustration, disgust, system abends, disk
head-crashes, general malfeasance, floods, fires, shark attack, nerve
gas, locust infestation, cyclones, hurricanes, tsunamis, local
electromagnetic disruptions, hydraulic brake system failure, invasion,
hashing collisions, normal wear and tear of friction surfaces, comic
radiation, inadvertent destruction of sensitive electronic components,
windstorms, the Riders of Nazgul, infuriated chickens, malfunctioning
mechanical or electrical sexual devices, premature activation of the
distant early warning system, peasant uprisings, halitosis, artillery
bombardment, explosions, cave-ins, and/or frogs falling from the sky.