[TYPES] CPS and accumulators

[Marco Devillers]

Ah well, since I responded anyway to the other question, I might as
well respond to this.

Transforming general recursion to tail recursion is an optimization
generally used in compilers for functional languages which has proven
its merit. I.e. the task is to get rid of all those pesky intermediate
stack frames build up if you would translate the code naively such
that you end up with jumps and hardly any, to no, stack.

If you don't assume a stack machine, but a graph rewrite machine, like
-what, was it again, early Haskell, possibly early pre-ABC Clean- no
stack frames are build, or put differently, all stacks frames are in
the heap and may be discarded when not referenced anymore.

The latter gives a more simple translation, but I am unaware what
price, if any, you pay for that particular set-up. I only know, mostly
observe, that Lisp (ML?) compilers seem to favor getting rid of general
recursion by CPS transform such that it can be translated easier to an
intermediate machine, but it is the intermediate machine which defines
what transform you need.

It may be that a translation to hyper-combinators for a GRS allocates
just as much in the heap as a translation with CPS to a more
traditional intermediate machine does.

The essential part is that you want to translate from a system with
operational semantics where naive rewriting is hard to implement
(efficiently or robust) to a system where individual rewrites are
easily implemented (and are efficient and robust). CPS does that,
hyper-combinators too, I tried some other forms myself.

Fine-tuning the transform and the accompanying intermediate machine is
-was?- probably worth a thesis by itself. There is a lot of work in
the early eighties on that.

*Giuseppe, there was a typo in the previous mail :)