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

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

Expand Messages
  • 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 1 of 15 , Oct 1, 2005
    View Source
    • 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 2 of 15 , Oct 1, 2005
      View Source
      • 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 3 of 15 , Oct 1, 2005
        View Source
        • 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 4 of 15 , Oct 2, 2005
          View Source
          • 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 5 of 15 , Oct 2, 2005
            View Source
            • 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 6 of 15 , Oct 2, 2005
              View Source
              • 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 7 of 15 , Oct 2, 2005
                View Source
                • 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 8 of 15 , Oct 2, 2005
                  View Source
                  • 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 9 of 15 , Oct 2, 2005
                    View Source
                    • 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.