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

Re: "ocaml_beginners"::[] CPS unleashed?

Expand Messages
  • Remi VANICAT
    ... and I think you are wrong, it will use more place than the whole list. More precisely The closure will use 4 word, while the list use 3. In fact the main
    Message 1 of 10 , Sep 3, 2002
      Stalkern 2 <stalkern2@...> writes:

      > After a previous thread we know that the @ operator leads to non tail
      > recursive programs.
      > Gerd said "@ is O(n)", and by the way he said also, for a problem with reverse
      > lists, "One optimization would be to accumulate by "head :: accum" instead of
      > "accum @ [head]", and to reverse the resulting list afterwards (List.rev is
      > O(n), and tail-recursive)."
      >
      > Here http://www.cs.utah.edu/classes/cs6520/cps.pdf uses CPS, by writing:
      >
      >
      > let rec makeList3 =
      > fun n ->
      > fun aFun ->
      > if (n = 0) then
      > (aFun [])
      > else
      > (makeList3 (n - 1) (fun partialList -> aFun (n::partialList)));;
      >
      > _______________________
      > Actually a function is added, both fetching over the partialList and using it
      > to accumulate the main argument, while the main argument decreases.
      > I think that this function will take as much space as the whole list, because
      > it fetches the partialList around, but not more.

      and I think you are wrong, it will use more place than the whole
      list. More precisely The closure will use 4 word, while the list
      use 3.

      In fact the main concern if we compare to the Gerd solution :
      let rec makeList4 n acc =
      if n = 0 then List.rev acc
      else makeList4 (n - 1) (n::acc)

      is that the makeList3 will be less efficient in term of speed : the
      use of closure in place of "real function" is less efficient (at least
      when compiled with ocamlopt).


      [...]

      by the way, I believe that
      let rec makeList4 n acc =
      if n = 0 then List.rev acc
      else makeList4 (n - 1) (n::acc)

      is more easily readable than

      let rec makeList4 =
      fun n ->
      fun acc ->
      if n = 0 then List.rev acc
      else makeList4 (n - 1) (n::acc)

      because you remove the syntactic overhead that come from the fun an -> thing.
      --
      Rémi Vanicat
      vanicat@labri.u-bordeaux.fr
      http://dept-info.labri.u-bordeaux.fr/~vanicat
    • Stalkern 2
      ... What do you mean by word ? I can t see this. ... OK, I see that you can measure times exactly. Are you using a timer like the one that Doug Bagley s
      Message 2 of 10 , Sep 4, 2002
        Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
        > and I think you are wrong, it will use more place than the whole
        > list. More precisely The closure will use 4 word, while the list
        > use 3.
        >

        What do you mean by "word"? I can't see this.

        >
        > In fact the main concern if we compare to the Gerd solution :
        > let rec makeList4 n acc =
        > if n = 0 then List.rev acc
        > else makeList4 (n - 1) (n::acc)
        >
        >
        > is that the makeList3 will be less efficient in term of speed : the
        > use of closure in place of "real function" is less efficient (at least
        > when compiled with ocamlopt).
        >

        OK, I see that you can measure times exactly. Are you using a timer like the
        one that Doug Bagley's suggested once upon a time?
        >
        >
        > [...]
        >
        >
        > by the way, I believe that
        > let rec makeList4 n acc =
        > if n = 0 then List.rev acc
        > else makeList4 (n - 1) (n::acc)
        >
        >
        > is more easily readable than
        >
        >
        > let rec makeList4 =
        > fun n ->
        > fun acc ->
        > if n = 0 then List.rev acc
        > else makeList4 (n - 1) (n::acc)
        >
        >
        > because you remove the syntactic overhead that come from the fun an ->
        > thing.

        Hey hey, I started writing things like that to put some order.
        The synthetic style makes indentation useless and indendation helps
        readability and quick browsing.
        Moreover, extended writings like "fun n ->" etc. are meaningful in
        distinguishing clearly the name of a function and its arguments.
        In my opinion, "f(x) =" is clear, "f = fun x ->" is clear, but "f x =" is a
        shame.
        I'm not paid for the lines of code (then I'd change language!), nor for the
        contrary. I just think that a few recyclable bytes more can be used for
        pretty-printing, especially in this list.
        Apart from that, as a nominalist I can't stand the sight of neutral names. I
        praise the use of different sort of names for elements with different roles,
        so calling a function "k" is to me not only a matter of inadvertance but an
        attempt to fake the reality...
        Imagine that I write *mails in english* in a twelve-words, non new-lined
        zipped style. Would you read me?


        Bye
        Ernesto
        PS to take a look at the pragmatical aspects of speaking, one can read for
        instance "Ce que parler veut dire" by the philosopher Pierre Bourdieu.
      • Ryan Tarpine
        ... I am assuming he means words of memory? That while writing something in the CPS way does not use lots of stack space like a normal recursive function
        Message 3 of 10 , Sep 4, 2002
          >From: Stalkern 2 <stalkern2@...>
          >Subject: Re: "ocaml_beginners"::[] CPS unleashed?
          >
          >Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
          > > and I think you are wrong, it will use more place than the whole
          > > list. More precisely The closure will use 4 word, while the list
          > > use 3.
          > >
          >
          >What do you mean by "word"? I can't see this.

          I am assuming he means words of memory? That while writing something in the
          CPS way does not use lots of stack space like a normal recursive function
          often does, it needs quite a bit of heap space. More heap space than the
          resulting list will need. Possibly more heap space than the original
          function used stack space?

          >
          >...
          > > because you remove the syntactic overhead that come from the fun an ->
          > > thing.
          >
          >Hey hey, I started writing things like that to put some order.
          >...
          >

          To each his own, I say! It's much too easy to have your own opinions
          concerning OCaml's syntax. Let's not even get started over the revised
          syntax... ;)

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

          _________________________________________________________________
          Join the world�s largest e-mail service with MSN Hotmail.
          http://www.hotmail.com
        • Stalkern 2
          ... This is not only a matter of syntax, it s a matter of beginning with ocaml. In the ocaml-beginners list, that could be a harbour of peace e.g. for those
          Message 4 of 10 , Sep 4, 2002
            Il Wednesday 04 September 2002 13:41, Ryan Tarpine ha scritto:
            > It's much too easy to have your own opinions
            > concerning OCaml's syntax. Let's not even get started over the revised
            > syntax... ;)

            This is not only a matter of syntax, it's a matter of beginning with ocaml. In
            the ocaml-beginners' list, that could be a harbour of peace e.g. for those
            who have spent their life so far doing things completely different from fp
            and so on, one should find IMHO some ocaml-for-beginners or
            ocaml-for-advancing-from-the-beginner's-status.

            I'm really convicted about this learning-oriented aspect of this list;
            otherwise it could be called "ocaml-support" and close in a few mails. I
            don't have an extensive knowledge of Ocaml, but when I learnt something in
            Ocaml I write it here trying to explain it.
            We could also skip the Yahoo Archives, that are stuffed with ads, by putting
            the hundreds of messages that have been produced here so far on a site, ASA I
            have time to take a look at those php forum management programs. In the
            meanwhile, please don't get bothered by my idiot-proof pretty parsing, the
            intention is the same, to let anyone learn ocaml without too much pain.

            Cheers
            Ernesto
            PS BTW About pain I heard a joke: a sadist goes towards a masochist and plays
            like hitting him; the masochist says "Yes!" then the sadist stops and says
            "No-o!" (sorry it must be a side-effect of cps;-))) )
          • Remi VANICAT
            ... a word is 32 Bit on a 32 bit computer, 64 Bit on a 64 bit computer, and so one... ... I haven t measure the time. But I do know that call of closure is
            Message 5 of 10 , Sep 4, 2002
              Stalkern 2 <stalkern2@...> writes:

              > Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
              >> and I think you are wrong, it will use more place than the whole
              >> list. More precisely The closure will use 4 word, while the list
              >> use 3.
              >>
              >
              > What do you mean by "word"? I can't see this.

              a word is 32 Bit on a 32 bit computer, 64 Bit on a 64 bit computer,
              and so one...

              >
              >>
              >> In fact the main concern if we compare to the Gerd solution :
              >> let rec makeList4 n acc =
              >> if n = 0 then List.rev acc
              >> else makeList4 (n - 1) (n::acc)
              >>
              >>
              >> is that the makeList3 will be less efficient in term of speed : the
              >> use of closure in place of "real function" is less efficient (at least
              >> when compiled with ocamlopt).
              >>
              >
              > OK, I see that you can measure times exactly. Are you using a timer like the
              > one that Doug Bagley's suggested once upon a time?

              I haven't measure the time. But I do know that call of closure is less
              efficient than call to "real function" (I don't like this name,
              closure are function too, but I don't know how to name those, may be
              direct function ?). Well to be more precise :
              with ocamlopt (a list of 2000 element is created):

              -- makeList3: iterations:10000 avg time:3.400000E-01 msec
              -- makeList4: iterations:10000 avg time:2.260000E-01 msec

              with ocamlc :
              -- makeList3: iterations:10000 avg time:6.020000E-01 msec
              -- makeList4: iterations:10000 avg time:7.240000E-01 msec

              [...]


              > Hey hey, I started writing things like that to put some order.
              > The synthetic style makes indentation useless and indendation helps
              > readability and quick browsing.
              > Moreover, extended writings like "fun n ->" etc. are meaningful in
              > distinguishing clearly the name of a function and its arguments.
              > In my opinion, "f(x) =" is clear, "f = fun x ->" is clear, but "f x =" is a
              > shame.

              I strongly disagree. But it a question of taste. For me the fun x -> put
              a lot of unneeded things. The second problem is that it is not
              idiomatic ocaml code. idiomatic ocaml code make the code easier to
              read for other ocaml programmer, and if you are use to read idiomatic
              code, it make reading code of other more easy for you.

              > I'm not paid for the lines of code (then I'd change language!), nor for the
              > contrary. I just think that a few recyclable bytes more can be used for
              > pretty-printing, especially in this list.
              > Apart from that, as a nominalist I can't stand the sight of neutral names. I
              > praise the use of different sort of names for elements with different roles,
              > so calling a function "k" is to me not only a matter of inadvertance but an
              > attempt to fake the reality...

              are you talking of my use of aux ? I use aux function for local
              function when the name of the local function should be the same than
              the name of the global function :

              let sum n =
              let rec sum n accu =
              if n = 0 then accu
              else sum (n - 1) (accu + n) in
              sum n 0

              is correct, but I prefer the version with the aux function.


              --
              Rémi Vanicat
              vanicat@labri.u-bordeaux.fr
              http://dept-info.labri.u-bordeaux.fr/~vanicat
            • Stalkern 2
              ... Well, you know that one could rather write things like let sum n = let rec sum1 n accu = if n = 0 then accu else sum1 (n - 1) (accu + n) in sum n 0 and
              Message 6 of 10 , Sep 4, 2002
                Il Wednesday 04 September 2002 15:06, Remi VANICAT ha scritto:
                > let sum n =
                > let rec sum n accu =
                > if n = 0 then accu
                > else sum (n - 1) (accu + n) in
                > sum n 0
                >
                >
                > is correct, but I prefer the version with the aux function.

                Well, you know that one could rather write things like
                let sum n =
                let rec sum1 n accu =
                if n = 0 then accu
                else sum1 (n - 1) (accu + n) in
                sum n 0

                and this would carry more information than calling *every* auxiliary function
                "aux".

                BTW I was speaking about something else:
                imagine that one writes a book about a man and the man's first name is not,
                say, Ernesto but Médor (or other pet's name) or, say, "Car". I can tell you
                that either the reader can get puzzled, or Ernesto gets angry |:-[: :]

                That's it.
                BTW you're quite right from a structural point of view, as well as one could
                call "x" or "atasu" the structuralist "empty case" and apply this name to a
                whole world of unknown things, but pointers in my memory need some hints
                especially when I don't use ocaml for a while or plan to do so many things in
                my life that I'll forget everything as in that book by Garcia Marquez.

                Actually, do you mind "fun ->" - code? I can change it if we get a general
                agreement on syntactic sugar in this list. Or we can take as granted the
                advice of Ryan

                Greetings
                Ernesto
              • Remi VANICAT
                ... of course every auxiliary function shouldn t be called aux. The true is that, in the case of tail rec : let sum n = let rec aux n accu = if n = 0 then accu
                Message 7 of 10 , Sep 4, 2002
                  Stalkern 2 <stalkern2@...> writes:

                  > Il Wednesday 04 September 2002 15:06, Remi VANICAT ha scritto:
                  >> let sum n =
                  >> let rec sum n accu =
                  >> if n = 0 then accu
                  >> else sum (n - 1) (accu + n) in
                  >> sum n 0
                  >>
                  >>
                  >> is correct, but I prefer the version with the aux function.
                  >
                  > Well, you know that one could rather write things like
                  > let sum n =
                  > let rec sum1 n accu =
                  > if n = 0 then accu
                  > else sum1 (n - 1) (accu + n) in
                  > sum n 0
                  >
                  > and this would carry more information than calling *every* auxiliary
                  > function "aux".

                  of course every auxiliary function shouldn't be called aux. The true
                  is that, in the case of tail rec :

                  let sum n =
                  let rec aux n accu =
                  if n = 0 then accu
                  else aux (n - 1) (accu + n) in
                  aux n 0

                  do exactly the same thing than :

                  int f(int n) {
                  int accu = 0;
                  while (n <> 0) {
                  accu = accu + n;
                  n = n - 1;
                  };
                  return accu
                  }

                  (this is tail rec optimization)

                  so I see aux mostly as a keyword in my code (that is aux is the tail
                  rec function that do the job).

                  other auxiliary function should have more explicit name.

                  by the way, you should read http://caml.inria.fr/FAQ/pgl-eng.html for
                  guideline. The main thing I don't follow in those guideline is :

                  let f = function
                  | 0 -> ...
                  | 1 -> ....

                  I prefer to write it as :

                  let f x =
                  match x with
                  | 0 -> ...
                  | 1 -> ....

                  like that each function definition are of the form

                  let f x1 x2 ... xn =
                  ...

                  where n is the number of argument of f.
                  (and the fact is that both ocamlc and ocamlopt will compile the
                  2 function the same way).

                  (and may be some other small difference).

                  [...]

                  >
                  > Actually, do you mind "fun ->" - code? I can change it if we get a general
                  > agreement on syntactic sugar in this list. Or we can take as granted the
                  > advice of Ryan

                  I believe that for a lot of thing, it will be difficult (even
                  impossible) to agree on it. But I firmly believe that the best way to
                  write a function with two argument in ocaml is :

                  let f arg1 arg2 =
                  ...

                  --
                  Rémi Vanicat
                  vanicat@labri.u-bordeaux.fr
                  http://dept-info.labri.u-bordeaux.fr/~vanicat
                • Nicolas Cannasse
                  ... Notice that this definition is a little bit confuse for people used to programming in C/C++ under Windows because of the following : typedef unsigned short
                  Message 8 of 10 , Sep 4, 2002
                    > > Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
                    > >> and I think you are wrong, it will use more place than the whole
                    > >> list. More precisely The closure will use 4 word, while the list
                    > >> use 3.
                    > >>
                    > >
                    > > What do you mean by "word"? I can't see this.
                    >
                    > a word is 32 Bit on a 32 bit computer, 64 Bit on a 64 bit computer,
                    > and so one...

                    Notice that this definition is a little bit confuse for people used to
                    programming in C/C++ under Windows because of the following :

                    typedef unsigned short WORD; // 16-bit

                    I don't know about *Nix but that definition is largely used by most of the
                    Win32 API's.

                    Best regards,
                    Nicolas Cannasse
                  • Remi VANICAT
                    ... well : word A fundamental unit of storage in a computer. The size of a word in a particular computer architecture is one of its chief
                    Message 9 of 10 , Sep 4, 2002
                      "Nicolas Cannasse" <warplayer@...> writes:

                      >> > Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
                      >> >> and I think you are wrong, it will use more place than the whole
                      >> >> list. More precisely The closure will use 4 word, while the list
                      >> >> use 3.
                      >> >>
                      >> >
                      >> > What do you mean by "word"? I can't see this.
                      >>
                      >> a word is 32 Bit on a 32 bit computer, 64 Bit on a 64 bit computer,
                      >> and so one...
                      >
                      > Notice that this definition is a little bit confuse for people used to
                      > programming in C/C++ under Windows because of the following :
                      >
                      > typedef unsigned short WORD; // 16-bit
                      >
                      > I don't know about *Nix but that definition is largely used by most of the
                      > Win32 API's.

                      well :

                      word

                      <storage> A fundamental unit of storage in a computer. The
                      size of a word in a particular computer architecture is one of
                      its chief distinguishing characteristics.

                      The size of a word is usually the same as the width of the
                      computer's {data bus} so it is possible to read or write a
                      word in a single operation. An instruction is usually one or
                      more words long and a word can be used to hold a whole number
                      of characters. These days, this nearly always means a whole
                      number of {bytes} (eight bits), most often 32 or 64 bits. In
                      the past when six bit {character sets} were used, a word might
                      be a multiple of six bits, e.g. 24 bits (four characters) in
                      the {ICL 1900} series.


                      So the use of the term "word" for 16 bit value come from the time when
                      ix86 machine where 16 bit machine.

                      --
                      Rémi Vanicat
                      vanicat@labri.u-bordeaux.fr
                      http://dept-info.labri.u-bordeaux.fr/~vanicat
                    Your message has been successfully submitted and would be delivered to recipients shortly.