[haskell] About CPS form funtions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[haskell] About CPS form funtions

甜瓜
Hi,
I am confused by section 4.6 in Yet Another Haskell Tutorial written
by Hal Daume III.
The auther provides a CPS form of "fold" funtion, but I don't know:
1. How to transform a normal function into CPS function. I need some
hint in writting "cfold".
2. Why "cfold" is CPS form? In my mind, if a CPS funtion calls to
other CPS function, it must only feed that function with either direct
variables or continuations. But in the tutorial, cfold defines:
cfold f z l = cfold' (\x t g -> f x (g t)) z l
Note that the lambda function body is f x (g t);  which means call
g(t) first, and take the result, then call f(x, r). It is illegal in
CPS because g(t) will never return. This is not same with function f.
Here, f can be treated as atomic operation (belong the CPS system).

Anyone can help me? Thank you in advance.

---
melon
Reply | Threaded
Open this post in threaded view
|

[haskell] About CPS form funtions

wman
On Mon, Dec 8, 2008 at 1:40 PM, ?? <[hidden email]> wrote:

> Hi,
> I am confused by section 4.6 in Yet Another Haskell Tutorial written
> by Hal Daume III.
> The auther provides a CPS form of "fold" funtion, but I don't know:
> 1. How to transform a normal function into CPS function. I need some
> hint in writting "cfold".


Normal function(s) return value(s).

CPS functions take the same value and uses/throws it as a parameter/argument
to the "extra" argument, the Continuation.

so to transform a function into CPS just
1) make the function take one extra argument, the continuation (the "rest"
of the process, next function in chain)
2) instead of returning a value, apply the continuation to the value (call
the continuation with the result you would normally return)

Example (taken from http://en.wikibooks.org/wiki/Haskell/CPS , check it out)

square :: Int -> Int
square x = x ^ 2

main = do
  let x = square 4
  print x

in CPS :

squareCPS :: Int -> (Int -> a) -> a
squareCPS x k = k (x ^ 2)

main = squareCPS 4 print

which shows that here, the print function is the continuation for the square
function.
instead of returning the value (16, or 4*4 here), the CPS variant feeds the
value to the continuation (print here)

hope it helps.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20081208/448b7174/attachment.htm