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

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

Expand Messages
  • giangiammy
    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
    • Show all 11 messages in this topic