From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA20864; Sun, 18 Aug 2002 18:13:56 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA20799 for <caml-list@pauillac.inria.fr>; Sun, 18 Aug 2002 18:13:55 +0200 (MET DST)
Received: from mail2.tpgi.com.au (mail.tpgi.com.au [203.12.160.58])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g7IGDrj17810
	for <caml-list@inria.fr>; Sun, 18 Aug 2002 18:13:54 +0200 (MET DST)
Received: from ozemail.com.au (syd-ts14-2600-184.tpgi.com.au [203.213.82.184] (may be forged))
	(authenticated (0 bits))
	by mail2.tpgi.com.au (8.11.6/8.11.6) with ESMTP id g7IGDkf13912;
	Mon, 19 Aug 2002 02:13:46 +1000
Message-ID: <3D5FC7B9.9060602@ozemail.com.au>
Date: Mon, 19 Aug 2002 02:13:45 +1000
From: John Max Skaller <skaller@ozemail.com.au>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2.1) Gecko/20010901
X-Accept-Language: en-us
MIME-Version: 1.0
To: Oleg <oleg_inconnu@myrealbox.com>
CC: caml-list@inria.fr
Subject: Re: [Caml-list] Cyclic ?!
References: <200208150218.WAA22018@hickory.cc.columbia.edu>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

Oleg wrote:

> Hi
> 
> I'm puzzled by the following compiler behavior:
> 
> If I define bin_tree as
> 
> type 'a bin_tree = 
>            Empty
>          | Node of 'a bin_tree * 'a * 'a bin_tree
> 
> the compiler accepts it. OTOH if I define it as
> 
> type 'a bin_tree = ('a bin_tree * 'a * 'a bin_tree) option
> 
> It gives an error: "The type abbreviation bin_tree is cyclic".
> Why??? And what's the difference between the two, really?


No semantic difference at all.
But there is a syntactic difference:
ocaml (without -rectypes) only allows cycles across
"object boundaries", that includes across variant
constructor names.

In the 'option' case,
the constructor name in 'option' type (namely "Some")
isn't explicitly separating the LHS and RHS parts of
the declaration. The syntax checker doesn't know
what 'option' is yet, it's just an arbitrary
polymorphic type: it could be:

	type 'a option = 'a

in which case, there really is an error.
Note that a polymorphic type (like option)
could be abstract -- in which case we
don't know it's internals, and there is no
choice but to reject the above style
in that case (assuming we want to enforce the
'no recursion except across object boundaries' rule).

So it seems the check is done *before* the lookup
for the meaning of 'option' which is why
I called it a 'syntax check' -- it is based
entirely on the shape of the declaration
in the abstract -- without considering the meaning
of the subterms.

This makes the rule robust in the face of
substitution (changing 'option' to 'id' for
example, where 'a id = 'a)


-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners