using less stack

Olaf Chitil
Wed, 20 Mar 2002 19:05:37 +0000

> with the cpsfold I get
> f x1 a (\y1 -> f x2 y1 (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4)
> so x1 and a are available immediately for f to use, and f x1 a is the
> outermost expression so will be evaluated first.

Yes, however, if f just calls its continuation without forcing the
evaluation of at least its second argument, e.g.
  f x y k = k (g x y)
you get

f x1 a (\y1 -> f x2 y1 (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4))))
=> f x2 (g x1 a) (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4)))
=> f x3 (g x2 (g x1 a)) (\y3 -> f x4 y4 (\y4 -> y4)))
=> f x4 (g x3 (g x2 (g x1 a))) (\y4 -> y4)
=> g x4 (g x3 (g x2 (g x1 a)))

like the foldr.

>  > larger    x y   = if x > y then x   else y
>  > cpslarger x y k = if x > y then k x else k y

Yes, with this definition of `cpslarger' no stack is used, because the
comparison forces evaluation.

  cpslarger x y k = k (larger x y)
it does not work.

Still, if your definition of cpslarger is natural for your application,
it is a nice solution of the problem.


 Dept. of Computer Science, The University of York, York YO10 5DD, UK. 
 Tel: +44 1904 434756; Fax: +44 1904 432767