[clean-list] Transform to CPS

[Jerzy Karczmarczuk]

Erik Zuurbier wrote:

 > Does anybody of you know of a systematic way to transform a function
 > (and its context) to a version using continuations - assuming that
 > performance improves? And is there a way to systematically identify
 > opportunities for such transformations?
 >
 > For instance, I know how to write a function that lists all items of a
 > tree:
 >
 > :: Tree a = Nil | Node (Tree a) a (Tree a)
 >
 > tree2list :: (Tree a) -> [a]
 > tree2list Nil = []
 > tree2list (Node left a right) = (tree2list left) ++ [a] ++ (tree2list
 > right)
 >
 > and then how to speed this up using a continuation:
 >
 > tree2list` :: (Tree a) [a] -> [a]
 > tree2list` Nil cont = cont
 > tree2list` (Node left a right) cont = tree2list` left [a:tree2list`
 > right cont]
 >
 > to be called with an empty list as its second parameter.
 >
 > But identifying and carrying out this transformation to me looks more
 > like black magic than a craft.


Well, first of all, I wouldn't call this transformation a 'continuation',
this is a variant of optimization with an accumulating parameter. It is
quite simple to do when you have an *associative* operator involved, here
the concatenation. The same principle can be used to optimize the power,
the factorial, etc. All has been formalized by Darlington and Burstall
many years ago.

I can - just for some general culture - give you a meta-recipe which I use
with my students (if all of us are in good mood...)

Say,
fac n = if n==0 then 1 else n*fac(n-1)

(sorry for some haskellianisms on the Clean list...)

1. GENERALIZE
Introduce a more general function with such semantics:

    facc n s = s * fac n

MIND YOU! This is *not* its definition, but its conceptual meaning. In
fact, the real definition is inverted:

fac n = facc n 1

2. UNFOLD

facc n s = if n==0 then s*1 else s*n*fac(n-1)
          = if n==0 then s else facc (n-1) (n*s)

That's it. Note how the associativity came into play.

For your trees the generalization stage is

trlist' t buf = tree2list t ++ buf
and you follow the same reasoning.

===



The CPS transformation - *not unrelated* to the accumulating parameter
stuff, would mean

      faccps n cnt = cnt (fac n)

fac n = faccps n id   where    id x = x

faccps n cnt = if n==0 then cnt 1 else cnt (n*fac(n-1))
              = if n==0 then cnt 1 else faccps (n-1) (cnt . (n *))

In such a way it became tail-recursive, but the cost is high, it
generates growing thunks on the heap, so this cost is comparable
with the stack-based approach. But now it can be further
improved...

I suggest that you look not only some papers and sites on the CPS
conversion, but also on some ancient and venerable work done by
Burstall and Darlington on program improvement.

JACM '1977

Something on-line
http://citeseer.nj.nec.com/burstall77transformation.html
http://www.diku.dk/topps/activities/pgmtrans/
    (here you might find a pdf [at DIKU] with some stuff)


Claus Reinke makes some parallels with the differential lists in
Prolog. I would be a bit careful here. The incomplete structures
in Prolog may be used in such a way, they are able to transform
copying_and_copying_and_copying append into something like
append! (in Scheme), but their traditional usage requires the
existence of a "non-instantiated logical variable", which does not
exists in functional languages. So, the parallels, analogies, etc.
are not very natural, and require some skills, while - it seems -
you want samething quite automatic and straightforward. I *do not*
criticize Claus, I just suggest that it might not be the most
natural way. At any rate, it was not so clear for my students,
although they grasped the idea quite quickly.




Jerzy Karczmarczuk

Oh, my goodness, now I see the remaining postings. Richard O'Keefe
quotes D&B as well. Oh well, I send it anyway...