- View SourceIl Thursday 29 August 2002 11:40, giangiammy ha scritto:
> Fist of all let me say what I mean for "continuation":

_1 Do you have a link-ography for Continuation Passing Style? Could you

>

>

> let f a b k =

> let r = doSomething a b in

> k r

>

>

> the function f is called with some parameter, and the last one is the

> "continuation" k. The idea is that k is "what I want to do when f has

> completed her work".

please tell the list?

_2 I found on http://www.swiss.ai.mit.edu/projects/amorphous/hlsi

m/node92.html several interesting expression :

"Continuation passing style is a style of writing programs where the events

in the future, i.e. the rest of the computation, is passed as an explicit

parameter. The value passed as this parameter is the continuation. A

continuation is a procedure that takes the value of the current expression

and computes the rest of the computation. Procedures do not return values;

instead, they invoke the continuation with the result. If a program is fully

CPS converted then there are no subproblem procedure calls. Every procedure

call is tail call, and the program's `control memory' is not stored in some

invisible stack but explicity as the continuation." "A program can be

converted to CPS relatively easily" [...] "We CPS convert fib, adding k as

the additional continuation parameter. We do not CPS convert the primitive

procedure calls to <, + and -" [...].

These lines make me think that continuation-passing is like making parameters

explicit, e.g. something that one does more or less finely when

testing/debugging. What do you think of this? Isn't CPS a technique for

readability?

--------------

The link above says that:

(define (fib n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))

--------------

becomes, CPS-wise:

(define (fib k n) (if (< n 2) (k 1) (fib (lambda (fib-of-n-1) (fib (lambda

(fib-of-n-2) (k (+ fib-of-n-1 fib-of-n-2))) (- n 2))) (- n 1))))

--------------

As far as I know, this should be Scheme and this should turn in Ocaml into:

#let rec standardFib n =

if (n < 2) then

1

else

(standardFib (n - 2) + standardFib (n - 1));;

val standardFib : int -> int = <fun>

--------------

becoming, CPS-wise:

# let rec cpsFib aFun n =

if (n < 2) then

aFun 1

else

((cpsFib aFun (n - 2)) + (cpsFib aFun (n - 1)));;

val cpsFib : (int -> int) -> int -> int = <fun>

--------------

Now, let's imagine to have aFun print its argument. E.g.:

# let tellerFun =

fun n -> (

print_endline (Format.sprintf "n is %d" n);

n

) ;;

val tellerFun : int -> int = <fun>

--------------

And let's apply it:

# cpsFib tellerFun 5;;

n is 1

n is 1

n is 1

n is 1

n is 1

n is 1

n is 1

n is 1

- : int = 8

--------------

Why is n always 1?

Because only

aFun 1

ever brings to a full application of aFun (the second argument is otherwise

kidnapped by the function cpsFib).

Actually we could have written, giving different argument types to cpsFib and

the function:

# let rec cpsFib1 anyFun n =

if (n < 2) then

(

anyFun ();

n (*just for respecting the type of the other branch*)

)

else

((cpsFib1 anyFun (n - 2)) + (cpsFib1 anyFun (n - 1)));;

val cpsFib1 : (unit -> 'a) -> int -> int = <fun>

and

# let tellerFun1 =

fun () -> print_endline "Hello";;

val tellerFun1 : unit -> unit = <fun>

and get

# cpsFib1 tellerFun1 5;;

Hello

Hello

Hello

Hello

Hello

Hello

Hello

Hello

- : int = 5

--------------

Why are there 8 instances of 1?

Because you need the two previous fibonacci numbers of one to get the

fibonacci number of that one. Since this is recursive, you must go backwards

for every number from that one down to 1.

I.e. for 8,7,6,5,4,3,2,1: these are eigth numbers.

--------------

This way, using continuations as the above quoted link said, it seems to me

that one can have a much better insight in computing mechanisms. In the above

example, the printing continuation acts only in terminating conditions; one

could set up continuations, i.e. next things-to-do, acting in non terminating

conditions.

What for? To keep order and knowledge of the programmed matter.

I hope that I'll find better examples for continuations-passing style, e.g.

using assignations by reference and seeing the following states of the

environment.

Two more remarks:

_most of the material about cps seems to be written in Scheme

_maybe "debuggers" exploit cps?

_how do you call a programming style where *everything* is made explicit,

just because computing is distributed? isn't it akin to cps, on a bigger

scale?

Ciao

Ernesto - View Source--- In ocaml_beginners@y..., "Ryan Tarpine" <rtarpine@h...> wrote:
> >From: Stalkern 2 <stalkern2@t...>

***how do you "linearize" a function?***

>Il Monday 02 September 2002 02:57, giangiammy ha scritto:

>>

>> (* continuation passing style *)

>> (1) let rec fibk n k =

>> (2) if n < 2 then

>> (3) k 1

>> (4) else

>> (5) fibk (n-1) (fun fibnm1 ->

>> (6) fibk (n-2) (fun fibnm2 ->

>> (7) k (fibnm1 + fibnm2))) ;;

>>

>

>My first question is:

>

I have not a format method. Sorry. The idea is the following:

line 1: define a function fibk to compute fibonacci's n-th number,

and when you are done, give it to k

line 5: to compute fib(n), compute fib (n-1), and when you are done,

give the result, which is fibnm1=fib(n-1), to a function

line 6: this function has to compute fibnm2=fib(n-2), and when

it has the result,

line 7: compute fib(n-1)+fib(n-2) and giver it to the function k

This linearization is needed as Fibonacci's computation requires

2 consecutive values, so I need to explicity write 2 consecutive

continuation.

Saying the same in other words, to compute fib(n), I compute

fib(n-1), when I have it, I continue the computation with the

1st continuation (line 5), which computes fib(n-2) and when

I have it, I continue with the 2nd continuation (line 6),

which complete the procedure, adding the 2 values, and calling

the user given continuation k.

N ote that I have 2 nested continuations: this is needed

as I need 2 values of Fibonacci's sequence to compute the next

one, and only in the inner continuation I have them.

I hope not to have make the all more obscure than before :-)

> ________

Every time I try to trace a program of this sort, if I'm able

> I have:

>

> # fibk 5 (fun anyArg -> anyArg);;

> anInnerArg1 is 1

> anInnerArg2 is 1

>

> anInnerArg1 is 2

> anInnerArg2 is 1

>

> anInnerArg1 is 1

> anInnerArg2 is 1

>

> I sum these 2 and ... + anInnerArg1 is 3

> +---------+ anInnerArg2 is 2

> |

> | + anInnerArg1 is 1

> | +-+ anInnerArg2 is 1

> | |

> | + +-> anInnerArg1 is 2

> | +-+ anInnerArg2 is 1

> | |

> ... I obtain this +-> | anInnerArg1 is 5

> +-----> anInnerArg2 is 3

>

>

> - : int = 8

>

>

> ***Could you explain this? Are these couples the "states" of the

> continuation?***

to trace it correctly, after some minutes I forget it ...

Anyway, this trace gives you an idea of the sequence of computations,

that is to compute the 8, you need the 5 and 3, to compute the

3 you need 1 and 2, and to compute the 2 you need 1 and 1.

On the other side, to compute the 5 you need the 2 and the 3,

and so on.

More than state, I would call these values as intermediate

executions.

By the way, thankt to "Ryan Tarpine" <rtarpine@...>,

for the reference: interesting paper, mainly for the

"automatic CPS translation procedure", even if the mathematical

notation if quite criptical :-(

bye

Gianluca