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

Re: "ocaml_beginners"::[] mutually recursive definition of non-function values

Expand Messages
  • Seth J. Fogarty
    ... Not if you know the semantics of let rec, and the way lists (or tuples) are allocated. let rec x = y does the following: Defined a memory space for x. In
    Message 1 of 15 , Sep 30, 2005
    • 0 Attachment
      On 9/30/05, Oliver Bandel <oliver@...-berlin.de> wrote:
      > On Fri, Sep 30, 2005 at 03:00:27PM +0300, dmitry grebeniuk wrote:
      > > dg> (last example I've seen was something like:
      > > dg> let loop_forever func =
      > >
      > > dg> let rec cycled_list = () :: cl
      > >
      > > dg> in
      > > dg> List.iter func cycled_list
      > > dg> )
      > >
      > > Sorry, I meant "let rec cycled_list = () :: cycled_list".
      >
      > strange, that this is allowed!

      Not if you know the semantics of let rec, and the way lists (or
      tuples) are allocated.

      let rec x = y
      does the following:
      Defined a memory space for x. In OCaml, this must be a pointer (I think).
      Evaluates y and stores it in the heap.
      Alters the value of x to point to y.

      Lists are (I think?) tuples of pointers in the heap. They MAY be an
      array of two pointers on the stack, but this does not sound right to
      me. So what happens is:

      cycled_list is allocated space as a pointer. Call this location '15'
      () :: cycled-pointer is evaluted...
      the head of this is evaluated to the location of (). Say it's at '2'
      The tail of this is evaluated to the locatin of cycled_list. This is '15'.
      This tuple is placed in the heap, say at location '2050'.
      The value stored at location 15 is set to 2050.

      So now we have:
      2 -> unit
      15 -> 2050
      2050 -> 2, 15

      2050 is a valid list. it points to the head and the tail. The tail is
      a pointer to another list. This list resides in location 2050.

      Now I may be wrong here: it is possible that we can allocate 15 to
      store both values. Then instead of having 15 POINT to the list, it
      actually stores both pointers. So we set it to 2, 15, and things look
      like below.

      2 -> unit
      15 -> 2, 15

      But the important thing to realize is that the value of a list is it's
      location. We don't need to know the CONTENTS of the location to
      evaluate it.

      Contrast this with numbers: the value of a number is not it's
      location, but it's value.


      --
      Seth Fogarty sfogarty@[gmail.com|rice.edu|livejournal]
      Neep-neep at large AIM: Sorrath
      "I know there are people in this world who do not love their fellow
      human beings - and I hate people like that" --Tom Lehrer.
    • Radu Grigore
      ... Nice explanation. I think it would have been easier to follow if you would have used sequential addresses 0, 1, 2, 3, ... or maybe a_0, a_1, a_2, ... .
      Message 2 of 15 , Oct 1, 2005
      • 0 Attachment
        --- "Seth J. Fogarty" <sfogarty@...> wrote:
        > Not if you know the semantics of let rec, and the way lists (or
        > tuples) are allocated.

        Nice explanation. I think it would have been easier to follow if you
        would have used sequential addresses 0, 1, 2, 3, ... or maybe a_0,
        a_1, a_2, ... . People tend to remember this kind of numbers easier
        than 2050 and 15.

        regards,
        radu

        __________________________________________________
        Do You Yahoo!?
        Tired of spam? Yahoo! Mail has the best spam protection around
        http://mail.yahoo.com
      • Oliver Bandel
        ... I doubt it is. It explains what is going on internally with memory allocation and so on. But it does not explain why it is allowed to do such definitions
        Message 3 of 15 , Oct 1, 2005
        • 0 Attachment
          On Sat, Oct 01, 2005 at 12:06:01AM -0700, Radu Grigore wrote:
          > --- "Seth J. Fogarty" <sfogarty@...> wrote:
          > > Not if you know the semantics of let rec, and the way lists (or
          > > tuples) are allocated.
          >
          > Nice explanation.

          I doubt it is.
          It explains what is going on internally with memory allocation and so on.
          But it does not explain why it is allowed to do such definitions in the
          language.

          If internal memory allocation is used as explanation for what
          syntactical/grammatical constructs are allowed in a high-level
          language like Oaml, then IMHO something goes wrong.

          =============================================================
          # let rec cycled_list = () :: cycled_list;;
          val cycled_list : unit list =
          [(); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); (); ();
          (); (); (); (); (); (); (); (); (); (); (); ...]
          #
          =============================================================




          How long is that list?

          =============================================================
          # let x = let rec cycled_list = () :: cycled_list in List.length cycled_list;;

          =============================================================

          ...runs and runs and runs...

          What's going on there?
          Does OCaml use lists that are too long as if they were
          lazy? Or does it turn them automagically into a lazy list?


          Is there something of the FP-knowledge that I miss here?

          Can this behaviour (above example) be used on all types,
          not only unit? If not: why does Ocaml as a high-level language
          (not as a thingy with a certain implementation and running on
          an operating system with certain memory allocation mechanisms)
          behave differently for these or that types, when using a
          "common", allowed syntactical construct?!

          Can this lead to undefined behaviour of the "high-level" language?

          If such constructs are leading to strange behaviour (or machine independent),
          it maybe makes sense to disallow recursive values if not functions/types.
          But if one disallows that definition of recursive "simple"-values,
          there is a gap between first-class non-function values and first-class
          function-values.

          So it must be allowed?
          But if it is allowed, the language will be machine dependent,
          and behaves strange here....?!

          So, what can be said about THIS question?

          Ciao,
          Oliver
        • Oliver Bandel
          On Sat, Oct 01, 2005 at 01:23:42PM +0200, Oliver Bandel wrote: [...] ... Ciao, Oliver
          Message 4 of 15 , Oct 1, 2005
          • 0 Attachment
            On Sat, Oct 01, 2005 at 01:23:42PM +0200, Oliver Bandel wrote:
            [...]
            > Can this lead to undefined behaviour of the "high-level" language?
            >
            > If such constructs are leading to strange behaviour (or machine independent),

            ===> machine dependent.

            > it maybe makes sense to disallow recursive values if not functions/types.
            > But if one disallows that definition of recursive "simple"-values,
            > there is a gap between first-class non-function values and first-class
            > function-values.

            Ciao,
            Oliver
          • Seth J. Fogarty
            ... These aren t syntatic constructs, they are semantic ones. And, IMO, using the idea of locations in semantics is perfectly valid. For OCaml it is even
            Message 5 of 15 , Oct 2, 2005
            • 0 Attachment
              On 10/1/05, Oliver Bandel <oliver@...-berlin.de> wrote:
              > On Sat, Oct 01, 2005 at 12:06:01AM -0700, Radu Grigore wrote:
              > > --- "Seth J. Fogarty" <sfogarty@...> wrote:
              > > > Not if you know the semantics of let rec, and the way lists (or
              > > > tuples) are allocated.
              > >
              > > Nice explanation.
              >
              > I doubt it is.
              > It explains what is going on internally with memory allocation and so on.
              > But it does not explain why it is allowed to do such definitions in the
              > language.
              >
              > If internal memory allocation is used as explanation for what
              > syntactical/grammatical constructs are allowed in a high-level
              > language like Oaml, then IMHO something goes wrong.

              These aren't syntatic constructs, they are semantic ones. And, IMO,
              using the idea of 'locations' in semantics is perfectly valid. For
              OCaml it is even necessary, to explain the difference between = and
              ==.
              =============================================================
              > How long is that list?

              It has infinite length and extremely finite size (1 element).

              > ...runs and runs and runs...
              >
              > What's going on there?
              > Does OCaml use lists that are too long as if they were
              > lazy? Or does it turn them automagically into a lazy list?

              No, the list is simply cyclic. It is a directed graph of three
              elements which contains a cycle.

              > Is there something of the FP-knowledge that I miss here?

              Nope.

              > Can this behaviour (above example) be used on all types,
              > not only unit?

              Yes it can. You can create arbitrary cyclic lists, in fact.

              > Can this lead to undefined behaviour of the "high-level" language?

              No, the behavior is /very/ well defined. Just not terribly useful.

              > If such constructs are leading to strange behaviour (or machine independent),
              > it maybe makes sense to disallow recursive values if not functions/types.

              Types are not values (sadly) in OCaml. But if you take an expression
              who's value is /not/ a location (integer, float, etc), you will find
              that this behavior is not allowed.

              let rec a = 1 + a
              This kind of expression is not allowed as right-hand side of `let rec'

              > But if one disallows that definition of recursive "simple"-values,
              > there is a gap between first-class non-function values and first-class
              > function-values.

              Yes, this is frustrating. But this gap already exists in terms of
              equality. Type classes /might/ aleviate some of this.

              > But if it is allowed, the language will be machine dependent,
              > and behaves strange here....?!

              The language is /not/ machine dependent on this matter, as far as I know.

              --
              Seth Fogarty sfogarty@[gmail.com|rice.edu|livejournal]
              Neep-neep at large AIM: Sorrath
              "I know there are people in this world who do not love their fellow
              human beings - and I hate people like that" --Tom Lehrer.
            • a22_19_22
              . . . No, the behavior is /very/ well defined. Just not terribly useful. I gotta put my $.02 in here (I think there was a brief mention of cyclic lists in this
              Message 6 of 15 , Oct 2, 2005
              • 0 Attachment
                . . .
                No, the behavior is /very/ well defined. Just not terribly useful.

                I gotta put my $.02 in here (I think there was a brief mention of
                cyclic lists in this forum a week or two ago). Cyclic lists can be
                very useful, just not very often. Off the top of my head:
                1) Cyclic permutations of lists of letters (or small integers
                representing letters) for classic crypto systems such as Caesar
                ciphers and Vigenere tableaux (no modular arithmetic required as
                with cycling around arrays),
                2) Math theory says that the continued fraction representation (CF) of
                an irrational root of a quadratic polynomial (called a quadratic
                surd) is eventually periodic; for example, the CF of sqrt(14) is
                [3;1,2,1,6,1,2,1,6, ...]
                It's easy enough to compute two finite lists, the leading aperiodic
                part ([3] above) and the periodic part ([1;2;1;6] above). When you
                want to compute a finite approximation to sqrt(14), you have to run
                along the aperiodic part, [3], and then around and around the
                periodic part [1;2;1;6] until the stopping criterion is met.

                I found it *very* convenient to represent the CF as a pair made up
                of an ordinary list for the aperiodic part and a circular list for
                the periodic part.

                OCaml does make it harder (needlessly IMHO) to use circular lists by
                raising an exception if the list arguments to two-list iterators such
                as List.map2 and List.fold_left2 are not of the same length. When
                lists of different length are allowed, it can be convenient to map or
                fold over an ordinary list and a circular list. You could even get
                around the restriction by combining a finite list and a circular list
                into a finite list of pairs for use by List.map or List.fold_left,
                except that List.combine ALSO requires its arguments to be of equal
                length *sigh*. NOTE: Due I think to its lazy lists, the Haskell zip
                and zipWith functions don't have this silly restriction.

                FWIW,

                -- Bill Wood
                bill.wood@...
              • Seth J. Fogarty
                ... Well, I stand gladly corrected. ... These shouldn t be terribly hard to rewrite this way... it s a bit of a strange way of thinking about them, but it s
                Message 7 of 15 , Oct 2, 2005
                • 0 Attachment
                  On 10/2/05, a22_19_22 <a22_19_22@...> wrote:
                  > . . .
                  > No, the behavior is /very/ well defined. Just not terribly useful.
                  >
                  > I gotta put my $.02 in here (I think there was a brief mention of
                  > cyclic lists in this forum a week or two ago). Cyclic lists can be
                  > very useful, just not very often. Off the top of my head:

                  Well, I stand gladly corrected.

                  > OCaml does make it harder (needlessly IMHO) to use circular lists by
                  > raising an exception if the list arguments to two-list iterators such
                  > as List.map2 and List.fold_left2 are not of the same length. When
                  > lists of different length are allowed, it can be convenient to map or
                  > fold over an ordinary list and a circular list.

                  These shouldn't be terribly hard to rewrite this way... it's a bit of
                  a strange way of thinking about them, but it's very doable. Map and
                  fold are four-line functions, and I doubt map2 and fold2 are much
                  longer.

                  --
                  Seth Fogarty sfogarty@[gmail.com|rice.edu|livejournal]
                  Neep-neep at large AIM: Sorrath
                  "I know there are people in this world who do not love their fellow
                  human beings - and I hate people like that" --Tom Lehrer.
                • a22_19_22
                  . . . ... Well, I m glad to hear it :-) . . . ... It depends on what you get used to, I guess. Common Lisp supports variable-arity functions, so mapping a
                  Message 8 of 15 , Oct 2, 2005
                  • 0 Attachment
                    . . .
                    > Well, I stand gladly corrected.

                    Well, I'm glad to hear it :-)

                    . . .
                    > These shouldn't be terribly hard to rewrite this way... it's a bit of
                    > a strange way of thinking about them, but it's very doable. Map and
                    > fold are four-line functions, and I doubt map2 and fold2 are much
                    > longer.

                    It depends on what you get used to, I guess. Common Lisp supports
                    variable-arity functions, so mapping a k-ary function over k lists is
                    no problem; furthermore, lists of differing lengths are supported.

                    Scheme, on the other hand, supports k-ary functions for map, but the
                    lists must be of the same length.

                    Haskell supports zip/zip3,.../zip6 which are variants of OCaml's
                    List.combine for combining 2/3/.../6 lists; the lists may be of
                    different lengths. The composition of map with zip<N> implements
                    mapping a N-ary function over N lists.

                    SML only supports zipping two lists into a list of pairs, but it has
                    two flavors, zip and zipEq; zipEq requires the lists to be of the same
                    length but zip doesn't. Like Haskell, composing map with zip
                    implements mapping a 2-ary function over two lists.

                    I sorta grew up with Common Lisp, and Haskell was my first "modern
                    functional programming language", so you can see where I'm coming from.

                    I looked at the implementations of combine, exists2, for_all2,
                    fold_right2, fold_left2, iter2 and map2 in Extlib.List; they all used
                    the pattern

                    | [], [] -> <handle end>
                    | h1::t1, h2::t2 -> <handle middle and recur>
                    | _ -> raise Different_list_size ..."

                    This could be easily replaced by

                    | [], _ | _, [] -> <handle end>
                    | h1::t1, h2::t2 -> <handle middle and recur>

                    so I don't think it's an implementation issue.

                    -- Bill Wood
                  • Brian Hurt
                    ... No, they re not: let rec fold_left2 f init alist blist = match alist, blist with ... ;; let rec fold_right2 f alist blist init = (* NOT tail recursive *)
                    Message 9 of 15 , Oct 2, 2005
                    • 0 Attachment
                      On Sun, 2 Oct 2005, Seth J. Fogarty wrote:

                      > On 10/2/05, a22_19_22 <a22_19_22@...> wrote:
                      >> . . .
                      >> No, the behavior is /very/ well defined. Just not terribly useful.
                      >>
                      >> I gotta put my $.02 in here (I think there was a brief mention of
                      >> cyclic lists in this forum a week or two ago). Cyclic lists can be
                      >> very useful, just not very often. Off the top of my head:
                      >
                      > Well, I stand gladly corrected.
                      >
                      >> OCaml does make it harder (needlessly IMHO) to use circular lists by
                      >> raising an exception if the list arguments to two-list iterators such
                      >> as List.map2 and List.fold_left2 are not of the same length. When
                      >> lists of different length are allowed, it can be convenient to map or
                      >> fold over an ordinary list and a circular list.
                      >
                      > These shouldn't be terribly hard to rewrite this way... it's a bit of
                      > a strange way of thinking about them, but it's very doable. Map and
                      > fold are four-line functions, and I doubt map2 and fold2 are much
                      > longer.

                      No, they're not:

                      let rec fold_left2' f init alist blist =
                      match alist, blist with
                      | (ah::at), (bh::bt) -> fold_left2' f (f init ah bh) at bt
                      | _ -> init
                      ;;

                      let rec fold_right2' f alist blist init =
                      (* NOT tail recursive *)
                      match alist, blist with
                      | (ah::at), (bh::bt) -> f ah bh (fold_right2' f at bt init)
                      | _ -> init
                      ;;

                      let map2' f alist blist =
                      let rec loop accum alist blist =
                      match alist, blist with
                      | (ah::at), (bh::bt) -> loop ((f ah bh) :: accum) at bt
                      | _ -> List.rev accum
                      in
                      loop [] alist blist
                      ;;


                      Brian
                    • dmitry grebeniuk
                      Shalom, Oliver. OB I doubt it is. OB It explains what is going on internally with memory allocation and so on. OB But it does not explain why it is allowed
                      Message 10 of 15 , Oct 2, 2005
                      • 0 Attachment
                        Shalom, Oliver.

                        OB> I doubt it is.
                        OB> It explains what is going on internally with memory allocation and so on.
                        OB> But it does not explain why it is allowed to do such definitions in the
                        OB> language.

                        Because this definition is valid definition of recursive value.
                        Any programming language must have recursive values: in C/C++ it is
                        done using pointers, in perl -- using references, in OCaml -- using
                        "let rec". Sometimes it's very nice to have such lists.
                        You often use recursive functions, so why there should not be
                        recursive values?

                        OB> Can this behaviour (above example) be used on all types,
                        OB> not only unit?

                        Of course. unit list is just an example of cycled list. You can
                        also construct more interesting lists:

                        let a = 1 :: (let rec b = 2 :: c and c = 3 :: b in b);;

                        OB> Can this lead to undefined behaviour of the "high-level" language?

                        No any undefined behaviour. Just note that recursive data
                        structures should be treat specially, not with List.length. For
                        example, a "Torture and hare algorithm":

                        let list_is_inf lst =
                        let rec inner a b =
                        if a == b then true
                        else
                        match a with
                        [] -> false
                        | [ah] -> false
                        | ah :: at ->
                        match b with
                        [] -> false
                        | [_] -> false
                        | bh :: bm :: bt -> inner at bt
                        in
                        match lst with
                        [] -> false
                        | [h] -> false
                        | a :: (b :: _ as tl) -> inner lst tl

                        let rec cl = () :: cl

                        let _ = Printf.printf "cl is infinite: %b\n" (list_is_inf cl)

                        OB> But if it is allowed, the language will be machine dependent,
                        OB> and behaves strange here....?!

                        There is no any machine-dependency.

                        --
                        WBR,
                        dmitry mailto:gds-mlsts@...
                      Your message has been successfully submitted and would be delivered to recipients shortly.