Date: 26 Nov 1997 13:06:33 -0000
From: Wolfram Kahl <kahl@diogenes.informatik.unibw-muenchen.de>
To: caml-list@inria.fr
Subject: Recursive types in OCaml/OLabl-1.06
After porting my project from OLabl-1.05 to OLabl-1.06,
I have been bitten by the change of policy wrt. recursive
types, too. I have solved my problems, and I enjoy the
new features --- many thanks to all involved for this
nice system!
Nevertheless I have some ideas about recursive types.
Xavier Leroy wrote:
> The point I'm trying to make here is that pretty much all the time,
> recursive types can be avoided and clarity of the code can be improved
> by using the right concrete types (sums or records) to hide the
> recursion, rather than using generic sum or product types such as
> "option" and "*", then obtain the desired recursive structure by using
> recursive type expressions.
I agree that this is essentially true,
but I shall argue that the use of generic sum or product types such as
"option" and "*" also has its advantages, which lie mainly in the
domain of code reuse,
and I shall propone a variant that might be able to give us
the best of both worlds ;-)
I need recursive types essentially for being able to
establish bidirectional links between different kinds
of mutable records (NOT objects -- motivated mainly by the absence
of typecase expressions), but it happens
that there is also a variant inside the path of the
recursion, so I dealt with the problem at the point.
Recapitulating an argument that already has been
discussed to a certain degree in the last few days,
I would like to write something like:
@O@<rectest1.mli@>==@{@-
type x = x option
@}
(This message can be used as an input file for FunnelWeb;
the passage above then defines the contents of the
FunnelWeb ``O''utput file @{rectest1.mli@}.)
Actually this concrete example is not at all interesting for me,
but I think that for illustrating my point, nothing is gained
by a more realistic variant example.
Testing this in OLabl-1.06 (all those tests give exactly
the same results with OCaml-1.06),
the command @{olablc -c rectest1.mli@} reports:
@$@<rectest1 output@>@Z==@{@-
File "rectest1.mli", line 1, characters 4-17:
The type abbreviation x is cyclic
@}
Obviously it is not a good idea to write
@O@<rectest2.mli@>==@{@-
type x = None | Some of x
@}
which is accepted, but gives bad name clashes
with the original constructors of @{option@}.
So in order to get a viable solution that
still reasonably fits into my other facilities for
handling values of type @{option@}
(this is the code reuse argument --- if my variant
is more complicated, I do not want to duplicate
all the code I have for handling it ---
even though I could easily do it with FunnelWeb :-),
I am forced to write:
@O@<rectest3.mli@>==@{@-
type x = NoneX | SomeX of x
val x_of_option : x option -> x
val option_of_x : x -> x option
@}
This is accepted, and I have to use the
adaptation functions all over the place.
This is essentially the solution that has been
recommended before, and I use it, too
(though not (yet) for @{option@}).
======================================================
As a new alternative which I think should be viable,
I would be happy if I could make the first variant
more explicit, resorting to the possibility of
``reexported variant types'':
@O@<rectest4.mli@>==@{@-
type x = x option = None | Some of x
@}
But again, @{olablc -c rectest4.mli@} gives:
@$@<rectest4 output@>@Z==@{@-
File "rectest4.mli", line 1, characters 4-36:
The type abbreviation x is cyclic
@}
Has this possibility already been considered
in that context? Would accepting this break
something else? Are ``reexported variant types''
allowed to instantiate type variables anyway?
Should they be allowed to do so?
=========================================================
By the way, when I define a polymorphic (mutable record)
type inside a big recursive type definition,
and use different instances of this type inside
the same recursive type definition,
I get an error along the lines of (since I already have adapted
my code, I cannot reproduce it right now):
``<<Instance3>> should be an instance of <<Instance1>>=<<Instance2>>''
which I conclude has something to do with lacking
support for polymorphic recursion.
However, I do not find any documentation for this
anywhere in the manual --- is this on purpose?
(The equality <<Instance1>>=<<Instance2>> is actually
only an assumption on the part of the compiler
which would, in the situation I encountered,
turn out to be invalid later.)
(The use of the keyword @{lazy@} and the
module @{Lazy@} are also not documented...)
Best regards,
Wolfram
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:13 MET