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

Expand Messages
• ... 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
• 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,

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• ... 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
• 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....?!

Ciao,
Oliver
• On Sat, Oct 01, 2005 at 01:23:42PM +0200, Oliver Bandel wrote: [...] ... Ciao, Oliver
Message 3 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
• ... 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
• 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.
• . . . 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
• 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
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@...
• ... 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
• 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:

> 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.
• . . . ... 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
• 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
• ... 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
• 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
• 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
• 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.