This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Polymorphic variants
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2002-04-27 (04:11) From: John Max Skaller Subject: Re: [Caml-list] How to compare recursive types? Solution!
```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 ..
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

```