Re: [Caml-list] How to compare recursive types? Solution!

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

Jerome Vouillon wrote:

>
>Assume the following definition:
>  typedef y = int * y;
>Then "y" and "int * y" are not equal according to your algorithm.
>Is it what you expect?
>
It's what I expect from the algorithm, yes: the interpretation
would be a pair whose first component contains a y which
will be cyclic .. however none of the pointers in that cycle
point to the top level pair. Its a dubious distinction though ..
clearly I need to know that int * y is a subtype of y ..

>
>Why don't you make the pointers explicit in the type?  
>
The language does have pointers. I could ban type recursion
that does not go through a pointer, and that would make
sense (it is what C does). However, I allow unions like:

    union list = Empty |  Cons of int * list

where you can just write "list" instead of having
to specify a pointer .. part of the reason is that the
underlying implementation always uses a pointer
for constructor arguments, a single C type

  struct { int variant; void *data; }

is used for variant components. Now I am trying
to generalise that, to get rid of what might appear
as an inconsistency .. direct recursion is allowed
in one place but not another.

>Then, the two
>types definitions below would not define the same type
>  typedef x = ref(x) * int;
>  typedef y = (ref(y) * int) * int;
>while these two would define the same type
>  typedef x = ref(x) * int;
>  typedef y = ref(ref(y) * int) * int;
>
Yes .. but what would I do for the list?

To make matters worse, my pointers always
allow writing .. i'd have to adopt a second
kind that didn't like 'ref' .. the experience in
C/C++ with 'const' suggests it might be worth
trying to avoid this . . so I'm trying to use the
approach languages like ocaml use where the use of pointers is hidden ..
at the same time, I support overloading,
and expand types in structs (products)  to reduce the
cost of dereferencing and garbage collection.

Perhaps what I am trying to do is impossible.

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