## 428Re: "ocaml_beginners"::[] I/O -> imperative? functional? with loops or recursion

Expand Messages
• Sep 1, 2002
• 0 Attachment
--- 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

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
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
> environment.
In my opinion, CPS should not be used with assignation by reference:
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
• Show all 11 messages in this topic