Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • giangiammy
    ... 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
    • 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
      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
      > 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
    • giangiammy
      ... 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
      • 0 Attachment
        --- 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
        > his home page
        >
        > 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
      • Ryan Tarpine
        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
        • 0 Attachment
          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
        • Stalkern 2
          ... 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
          • 0 Attachment
            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
          • Stalkern 2
            ... Yes... in Scheme! :-( I ll try to manage it... thank you Ryan Ernesto
            Message 5 of 11 , Sep 3, 2002
            • 0 Attachment
              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
            • Ryan Tarpine
              ... 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
              • 0 Attachment
                >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
              • giangiammy
                ... ***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
                • 0 Attachment
                  --- 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.