[Caml-list] Proposal for extensible open datatypes

[Caml-list] Proposal for extensible open datatypes

[Leo P White]

Hi all,

I have made a small extension to OCaml to allow open datatypes (like exn) 
to be created by the programmer. A patch and more details are available at 
http://sites.google.com/site/ocamlopen/.

The basic syntax is:

  open type foo

  open type 'a bar

  extend foo with Foo1 of int

  extend foo with Foo2 of string

  extend 'a bar with Bar of int * 'a


Open GADTs can also be created (with two possible syntaxes):

  open type 'a gadt

  extend 'a gadt with A : int -> int gadt

  extend string gadt with B of string


Although open types are in some ways similar to polymorphic variants, they 
are more similar to ordinary variants:

    * Constructors for open types can be used anywhere that an ordinary 
variant
      constructor can be used.

    * Constructors for open types have a single type, which can make them 
less
      prone to errors than polymorphic variants

    * Constructors for open types are associated with modules, so they can 
be
      hidden by signatures.

    * Open types can be Generalized Abstract Data Types

My original motivation for this was wanting to allow arbitrary data to be 
attached onto various points of a very large data structure (an AST). This 
can be done using local exceptions, but I wanted these values to have their 
own type. I think it might also be useful, when using GADTs to represent 
types, to allow these representations to be extended for user defined 
types.

Regards,

Leo

Re: [Caml-list] Proposal for extensible open datatypes

[Andrej Bauer]

I would be interested to hear what propeties of Ocaml you had to give
up to get this interesting extension working? For example, what
happens with checking for exhaustivness of match? Caml performs
various optimizations in pattern matching, why are those still ok now
that new alternatives may appear later?

With kind regards,

Andrej

Re: [Caml-list] Proposal for extensible open datatypes

[Andreas Rossberg]

On Jan 6, 2012, at 07.26 h, Andrej Bauer wrote:
> I would be interested to hear what propeties of Ocaml you had to give
> up to get this interesting extension working? For example, what
> happens with checking for exhaustivness of match? Caml performs
> various optimizations in pattern matching, why are those still ok now
> that new alternatives may appear later?

One such type is already in ML, for historical reasons it happens to  
be named exn. Consequently, you don't really give up anything, your  
questions already apply to the exception type. Exhaustiveness simply  
requires a catch-all in all pattern matches over this type. More  
difficult is irredundancy, because constructors can be aliased without  
the type system tracking that (and it cannot across module  
boundaries). You have to give up there.

Generalising exn this way is an old idea, e.g. we implemented it in  
Alice ML. The standard reply to requesting such an extension is that  
it's not really needed, because you can already do everything using  
exn (though without custom type distinctions, and minus GADTs in OCaml).

/Andreas

Re: [Caml-list] Proposal for extensible open datatypes

[Leo P White]

On Jan 6 2012, Andreas Rossberg wrote:

>On Jan 6, 2012, at 07.26 h, Andrej Bauer wrote:
>> I would be interested to hear what propeties of Ocaml you had to give
>> up to get this interesting extension working? For example, what
>> happens with checking for exhaustivness of match? Caml performs
>> various optimizations in pattern matching, why are those still ok now
>> that new alternatives may appear later?
>
>One such type is already in ML, for historical reasons it happens to  
>be named exn. Consequently, you don't really give up anything, your  
>questions already apply to the exception type. Exhaustiveness simply  
>requires a catch-all in all pattern matches over this type. More  
>difficult is irredundancy, because constructors can be aliased without  
>the type system tracking that (and it cannot across module  
>boundaries). You have to give up there.
>
>Generalising exn this way is an old idea, e.g. we implemented it in  
>Alice ML. The standard reply to requesting such an extension is that  
>it's not really needed, because you can already do everything using  
>exn (though without custom type distinctions, and minus GADTs in OCaml).

Yes, it uses the same same pattern matching as exn. This means that a 
catch-all pattern is required for exhaustiveness, and if-then-elses are 
used instead of jump tables.

The problem would become a bit more interesting if ordinary variant types 
could also be made open, thus allowing types to have both ordinary 
constructors and extensions, but the patch doesn't support that yet.

Leo