Browse Groups

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

(11)
• NextPrevious
• ... Well, starting from the fibonacci example here my exercises: (* standard recursive: nothing to say *) let rec fibr n = if n
Message 1 of 11 , Sep 1, 2002
View Source
--- 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
• ... Sorry, but in my last message I forget to insert the link I spoke of : http://theory.lcs.mit.edu/~athena/hacks/pipe.ml bye Gianluca
Message 2 of 11 , Sep 2, 2002
View Source
--- In ocaml_beginners@y..., "giangiammy" <giangiammy@y...> wrote:
> --- In ocaml_beginners@y..., Stalkern 2 <stalkern2@t...> wrote:

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

Sorry, but in my last message I forget to insert the link
I spoke of :

http://theory.lcs.mit.edu/~athena/hacks/pipe.ml

bye
Gianluca
• All of you really piqued my interest, and made me look into CPS (which I always heard people talking about in comp.lang.functional). The best explanation I
Message 3 of 11 , Sep 2, 2002
View Source
All of you really piqued my interest, and made me look into CPS (which I
always heard people talking about in comp.lang.functional). The best
explanation I found quickly was at

http://www.cs.utah.edu/classes/cs6520/cps.pdf

It has a few examples they work out step by step.

Very interesting... when learning about writing functions to be
tail-recursive, you find out that you can't do things like 'map' without
returning your answer backwards. With CPS you can get the correct result
without reversing your list at the end!

>From: Stalkern 2 <stalkern2@...>
>
><snip>
>
>you show that the function has been "linearized", also introducing some
>kinds
>of inner arguments.
>
>My first question is:
> ***how do you "linearize" a function?***
>

The above PDF gives almost exact steps to do this. I hope it helps you as
much as it did me :)

Ryan Tarpine, rtarpine@...
"To err is human, to compute divine. Trust your computer but not its
programmer."
- Morris Kingston

_________________________________________________________________
MSN Photos is the easiest way to share and print your photos:
http://photos.msn.com/support/worldwide.aspx
• ... OK, this is *really* senseful, it sounds like CPS, and shows that I don t know Scheme ;-) So by writing continuation as you did, e.g. something like let
Message 4 of 11 , Sep 2, 2002
View Source
Il Monday 02 September 2002 02:57, giangiammy ha scritto:
> (* 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.

OK, this is *really* senseful, it sounds like CPS, and shows that I don't know
Scheme ;-)
So by writing continuation as you did, e.g. something like

let rec fibk n aFun =
if (n < 2) then
(aFun 1)
else
fibk (n - 1) (
fun anInnerArg1 ->
fibk (n - 2) (
fun anInnerArg2 ->
aFun (anInnerArg1 + anInnerArg2)
)
) ;;

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

you show that the function has been "linearized", also introducing some kinds
of inner arguments.

My first question is:
***how do you "linearize" a function?***

You turned
fibr (n - 1) + fibr (n - 2) into
fibk (n-1) (<a function using fibk, n, and two intermediate arguments> )

________
Now if I write :

let rec fibk n aFun =
if (n < 2) then
aFun 1
else
fibk (n - 1) (
fun anInnerArg1 ->
fibk (n - 2) (
fun anInnerArg2 ->
print_endline (Format.sprintf "anInnerArg1 is %d" anInnerArg1);
print_endline (Format.sprintf "anInnerArg2 is %d\n\n"
anInnerArg2);
aFun (anInnerArg1 + anInnerArg2)
)
) ;;
val fibk : int -> (int -> 'a) -> 'a = <fun>

________
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

anInnerArg1 is 3
anInnerArg2 is 2

anInnerArg1 is 1
anInnerArg2 is 1

anInnerArg1 is 2
anInnerArg2 is 1

anInnerArg1 is 5
anInnerArg2 is 3

- : int = 8

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

Thank you
Ernesto
• ... Yes... in Scheme! :-( I ll try to manage it... thank you Ryan Ernesto
Message 5 of 11 , Sep 3, 2002
View Source
Il Monday 02 September 2002 17:06, Ryan Tarpine ha scritto:
> The best
> explanation I found quickly was at
>
>
> http://www.cs.utah.edu/classes/cs6520/cps.pdf
>
>
> It has a few examples they work out step by step.

Yes... in Scheme! :-(
I'll try to manage it... thank you Ryan

Ernesto
• ... Sorry about that! I wasn t thinking correctly :) As an exercise for myself, I translated all the examples to OCaml. These should run without any changes,
Message 6 of 11 , Sep 3, 2002
View Source
>From: Stalkern 2 <stalkern2@...>
>...
> >
> > It has a few examples they work out step by step.
>
>Yes... in Scheme! :-(
>I'll try to manage it... thank you Ryan
>
>Ernesto
>

Sorry about that! I wasn't thinking correctly :) As an exercise for myself,
I translated all the examples to OCaml. These should run without any
changes, since I tested them myself. The main difference is that I used
pattern matching, which Lisp doesn't have. I could have used List.hd and
List.tl, but I thought it better not to. Here we go:

let rec sum n =
if n = 0 then 0
else n + (sum (n-1))
;;
sum 1000;;

let rec sum2 n r =
if n = 0 then r
else sum2 (n - 1) (r + n)
;;
sum2 1000 0;;

let rec make_list n =
if n = 0 then []
else n::(make_list (n - 1))
;;
make_list 1000;;

let rec make_list2 n r =
if n = 0 then r
else make_list2 (n - 1) (n::r)
;;
make_list2 1000 [];;

let rec snoc i = function
| [] -> [i]
| hd::tl -> hd::(snoc i tl)
;;

(*
snoc is reverse cons, which in OCaml is simply "::". An easier way to
OCaml-ize it is "let snoc i ls = ls @ [i];;" *)

let rec make_list3 n k =
if n = 0 then k []
else make_list3 (n - 1) (fun ls -> k (n::ls))
;;
make_list3 1000 (fun ls -> ls);;
(*
= make_list3 999 (fun ls -> (fun ls -> ls) 1000::ls)
= make_list3 998 (fun ls -> (fun ls -> (fun ls -> ls) 1000::ls) 999::ls)
...
= make_list 0 (fun ls -> ... (fun ls -> ls) 1000::ls) 999::ls) ... 1::ls)
= (fun ls -> ... (fun ls -> ls) 1000::ls) 999::ls) ... 1::ls) []
= (fun ls -> ... (fun ls -> ls) 1000::ls) 999::ls) ... 2::ls) [1]
= (fun ls -> ... (fun ls -> ls) 1000::ls) 999::ls) ... 3::ls) [2;1]
...
= (fun ls -> (fun ls -> ls) 1000::ls) [999..1]
= (fun ls -> ls) [1000..1]
= [1000..1]
*)

let rec dont_make_list n k =
if n = 0 then ()
else dont_make_list (n - 1) (fun ls -> k (n::ls))
;;
dont_make_list 1000 (fun ls -> ls);;

(*
Step 3:
Select a variable X and wrap the expression with (fun X -> ...)
(1 + (f x)) transforms to (f x (fun v -> 1 + v))
*)

let rec map f = function
| [] -> []
| hd::tl -> (f hd)::(map f tl)
;;

(*
CPS conversion:

let rec map2 f ls k = match ls with
| [] -> []
| hd::tl -> (f hd)::(map2 f tl)
;;

let rec map2 f ls k = match ls with
| [] -> k []
| hd::tl -> k ((f hd)::(map2 f tl))
;;

let rec map2 f ls k = match ls with
| [] -> k []
| hd::tl -> f hd (fun v -> k (v::(map2 f tl)))
;;
*)

let rec map2 f ls k = match ls with
| [] -> k []
| hd::tl -> f hd (fun v -> map2 f tl (fun v2 -> k (v::v2)))
;;

let rec filter f = function
| [] -> []
| hd::tl ->
if f hd then hd::(filter f tl)
else (filter f tl)
;;

let rec filter2 f ls k = match ls with
| [] -> k []
| hd::tl ->
(f hd (fun v ->
if v then filter2 f tl (fun v2 -> k (hd::v2))
else filter2 f tl k))
;;

It was definitely helpful for me to write those out! Now I'm going to try
my hand at the little exercise at the end... :)

Oh, I almost forgot; here's the exercise! It becomes a bit different from
the Lisp version because of OCaml's strong type checking; Lisp will let you
have a list of different-typed objects (i.e. the first item in a list is an
integer but the second item is another list) and that can be used to make
trees more easily.

type tree =
| Node of tree * tree
| Leaf of int
;;

let rec sum_tree = function
| Leaf x -> x
| Node (left,right) -> (sum_tree left) + (sum_tree right)
;;
sum_tree (Node (Node (Leaf 1,Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf
5))));;

Bye,

Ryan Tarpine, rtarpine@...
"To err is human, to compute divine. Trust your computer but not its
programmer."
- Morris Kingston

_________________________________________________________________
MSN Photos is the easiest way to share and print your photos:
http://photos.msn.com/support/worldwide.aspx
• ... ***how do you linearize a function?*** I have not a format method. Sorry. The idea is the following: line 1: define a function fibk to compute
Message 7 of 11 , Sep 3, 2002
View Source
--- In ocaml_beginners@y..., "Ryan Tarpine" <rtarpine@h...> wrote:
> >From: Stalkern 2 <stalkern2@t...>
>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:
>
***how do you "linearize" a function?***

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 :-)

> ________
> 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?***

Every time I try to trace a program of this sort, if I'm able
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
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.