- --- In ocaml_beginners@y..., Stalkern 2 <stalkern2@t...> wrote:
> Il Thursday 29 August 2002 11:40, giangiammy ha scritto:

Well, starting from the fibonacci example here my exercises:

(* standard recursive: nothing to say *)

let rec fibr n =

if n < 2 then 1 else fibr(n-1) + fibr(n-2) ;;

(* continuation passing style *)

let rec fibk n k =

if n < 2 then

k 1

else

fibk (n-1) (fun fibnm1 ->

fibk (n-2) (fun fibnm2 ->

k (fibnm1 + fibnm2))) ;;

let k = (fun x -> Printf.printf "%d\n" x) ;;

the interpreters says:

# fibk 10 k;;

89

- : unit = ()

#

Here I have a CPS Fibonacci, which is the translation of the

presented scheme code.

The consideration we can do are:

1 - the continuation is what I want to be executed when the function

is done: if my code, or in this case your code, calls the

continuation

more than once, something is wrong.

2 - the code you wrote for cpsFib, is not CPS style (please, consider

that everytime I say "it is not ...", I mean "for what is my

understanding, it is not ...": as a matter of fact, I could have

misunderstood everything about continuation: let's try to

clarify something by discussion :-)

By the way you noted that> ... the printing continuation acts only in terminating conditions ...

in CPS continuation must be used in each step.

3 - aFun in cpsFib code is just passed over from a recursion step

to another, but it is not used as "whatToDoAfter...", with

the exception of the last step: that's the reason why you see

a lot of one.

4 - By the way, the application of continuation to Fibonacci's

function does not respect what you report for continuation

description from the www.swiss.ai.mit.edu: it says

"Procedures do not return values", while you compute fib (n-1),

wait its result, compute fib (n-2), wait its result and sum

the 2 values.

4bis - by the way, if by link-ography you mean bookmark-ology, I

haven't any.

I have seen a very interesting, even if I am not able

to understand the code, example by Matteo Frigo, in

his home page

xxxxxxxx

related to a pipe implementation using continuation:

if someone looks at this code, and understand it, please

give a word!

4ter - I do not agree very much with the reported description of

continuation, or at least, I uderstand the continuation

in a different way (but I'm just taking in consideration what

you are reporting, as I'm not on line: I'll check that

site as soon as possible)

5 - going on with the example of fibonacci's code, let see the

code fibk I reported: this, for what I understand, is the

correct translation from scheme: here you see that I call

fibk (n-1) with a continuation: this continuation is the

operation I must accomplish when I have found the (n-1)

Fibonacci's number: and what I must do is to call

fibk (n-2), with another continuation, and this second

continuation is what to do when I have the (n-2)

Fibonacci's number: the action is to call the supplied

continuation k, giving her the sum of the 2 fibonacci's

number.

In this way, if I supply a funcion such as tellerFun

as k, it is only invoked 1 time, at the end of the

computation.

6 - I do not consider continuation passing a way to make

parameters explicit: parameters are already explicit:

I mean, I can use function with global variables, in

this way the parameter I use in a function are not

explicit, and I must read all the code to understand

what are the parameters used, while if I use a clean

programming style, giving to all the function the

needed parameters in its calling line, this is what

I mean to make the parameters explicit.

But what is my idea of continuation: good question:

imagine a long hall, in a hospital, for example:

you are in the hall, you enter the 1st room in the left,

then exit and return in the hall; you go on 4 meters,

and enter the 2nd room on the left, then exit and

return in the hall, and go on in the 3rd room, and so

on. This is what I call imperative style hospital visit.

Now, let see a continuation passing style hospital visiting:

I am in a long hall, I enter in the 1st room on the left,

then I exit the room, but not using the same port I entered,

the one which brings to the hall, but anothe door, which

brings me directly to the 2nd room; then, I exit the 2nd

room using another door to go to the 3rd room, and so on...

That is in continuation passing style, I go from room to room,

accordingly to the path I mean to follow, but I avoid

entering the hall every time as I really do not care

to visit the hall.

The hall is my main path: I follow it from start to end,

visiting all the room, but I can, more efficiently visit

all the room, and following the same logical path, getting

directly to the room. In this way my path is less explicit,

I could exit a room using a door which brings me away

from the hall, and I could get lost, as I do not check

if I am in a room near the hall for each step.

This is a more powerful structure, as I could, depending

on what I find in the room, selecting a different path

"on the run", that is, without the need to return to

the hall after each room visit.

This is more powerful, but you can get lost more easily:

if you follow the hall, you always know where you are,

if you g ofrom room to room, and you do not know very well

the hospital, you can get lost!

A CPS style make something more explicit? it make more

explicit the action I must accomplish next, but making

it explicit means that you can change it on the fly,

you do not have an "anchor" or an "hall" to refer to:

that "anchor" is the stack.

In my experience, I see CPS a very powerful idea, and

the code can be very compact and efficient: I'm not

saying that without stack we are lost (the stack

has given me a lot of trouble in the past, and I

am very happy to abandon it) but you must understand

very well the code to manage CPS, and i found CPS

programs more difficult to debug.

It could just be that I was born, as a programmer,

with Basic, pascal, C, all imperative, and I

get acquainted to functional programming just

recently: it would be useful to hear from someone

who learn to program with funcional languages only.

7 - you ask me what I think about CPS as a technique for

readibility: the code I write for fibk is correct

(it prints the correct values), CPS style, but for

me it is not very intuitive to read (euphemistically

speaking :-)

8 - by the way, I got anothe solution to CPS(?) Fibonacci:

let rec fibx n k =

if n < 2 then k 1 0 else k (fibx (n-1) k) (fibx (n-2) k) ;;

the interpretes says:

# fibx 10 (+);;

- : int = 89

what is this?

It is not CPS, as I do not give a "continuation" but

an "intermediat-ation": the k is not what to do at the

end of the computation, but keeps part of the computation.

I do not know if this is some well known programming

style, if it is something with a name, or if it is

just a delirium of inexperience :-)

9 -> 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

In my opinion, CPS should not be used with assignation by reference:

> environment.

the main idea of CPS is to get along not only all the data, but

all the code too: the difficult part is to get along all the code,

but if you get along alla the code, and let back the data with

assignation by reference, is does not worth to use CPS.

For example, you could use continuation in a plotting program to

avoid to keep static variables: every time you plot a point you

call the continuation with updated current x and y and every other

needed parameter, such as the scake if you use autoscale, and so

on: in this case continuation is used with the only reason to

eliminate every static variables.

This is a good programming style, even if not very intuitive

(nor very readable, at least for me).

Two more remarks:

- it seems to me that the last note of your mail point to something

interesting, but I have not understand it very well, probably as

it's 2AM.

- the argument worth the discussion, but know let me go to sleep ;-)

good night

Gianluca - --- 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