Re: [Caml-list] Cyclic ?!

[John Max Skaller <skaller@ozemail.com.au>]

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