Generalized algebraic datatypes

Generalized algebraic datatypes

[Jacques Le Normand]

[-- Attachment #1: Type: text/plain, Size: 322 bytes --]

Dear caml-list,
I'm writing a toy compiler that compiles into ocaml and my toy compiler
supports Generalized Algebraic Datatypes, so I need to compile into a
language which also supports them.
Does ocaml support Generalized Algebraic datatypes? If not, are there any
caml based compilers that support it?
cheers
--Jacques

[-- Attachment #2: Type: text/html, Size: 343 bytes --]

Re: [Caml-list] Generalized algebraic datatypes

[Gabriel Kerneis]

On Mon, Apr 28, 2008 at 01:35:06AM -0400, Jacques Le Normand wrote:
> Does ocaml support Generalized Algebraic datatypes? 

No.

> If not, are there any caml based compilers that support it?

Some pieces of software (e.g. Ocsigen), which need GADT, use (very
carefuly crafted) "black magic" (Obj.magic) to get things compiled. 
You could probably do this in your "toy compiler", put you will loose 
the benefit of Ocaml's type-checking.

Regards,
-- 
Gabriel Kerneis

Re: Generalized Algebraic Datatypes

[Sylvain Le Gall]

On 31-10-2010, Lukasz Stafiniak <lukstafi@gmail.com> wrote:
> On Sun, Oct 31, 2010 at 3:35 PM, Sylvain Le Gall <sylvain@le-gall.net> wrote:
>> On 31-10-2010, Wojciech Daniel Meyer <wojciech.meyer@googlemail.com> wrote:
>>> bluestorm <bluestorm.dylc@gmail.com> writes:
>>>
>>>> It was actually the case in Caml Light : each datatype constructor
>>>> implicitly declared a constructor function with the same name. I
>>>> don't exactly know why this feature was dropped in Objective Caml,
>>>> but I think I remember (from a previous discussion) that people
>>>> weren't sure it was worth the additional complexity.
>>>
>>> Would that be not possible now with Camlp4 extension?
>>>
>>
>> I am pretty sure, it is possible to implement them with camlp4. Just a
>> matter of time -- and motivation.
>>
>> The only limitation I can see, is that the generated constructors won't
>> be capitalized. E.g.:
>>
>> type t = MyConstr | YourConstr of int
>>
>> =>
>>
>> type t = MyConstr | YourConstr of int
>>
>> let myConstr = MyConstr
>> let yourConstr i = YouConstr i
>>
>
> Why do you say so? HOL Light uses capitalized identifiers for values,
> for example. It's probably possible to do whatever one reasonably
> wants.
>

Function names and values are "low id" in OCaml (first letter must be
uncapitalized). If you try to define "let MyConstr = 0" in an OCaml
toplevel, you will get a syntax error... 

The code generated by camlp4 must be syntactically correct.

But maybe you are talking about a deeper integration?

E.g. whenever you encounter the constructor "YourConstr" in expr, you
transform it into "fun i -> YourConstr i". This should work but since
camlp4 is limited to a single module, you won't be able to use this
outside the module, because you won't have access to the definition of
YouConstr and won't be able to determine his arity...

But if you have an idea about how to solve this, just tell us.

Regards,
Sylvain Le Gall

Re: Generalized Algebraic Datatypes

[Sylvain Le Gall]

On 31-10-2010, Wojciech Daniel Meyer <wojciech.meyer@googlemail.com> wrote:
> bluestorm <bluestorm.dylc@gmail.com> writes:
>
>> It was actually the case in Caml Light : each datatype constructor
>> implicitly declared a constructor function with the same name. I
>> don't exactly know why this feature was dropped in Objective Caml,
>> but I think I remember (from a previous discussion) that people
>> weren't sure it was worth the additional complexity.
>
> Would that be not possible now with Camlp4 extension?
>

I am pretty sure, it is possible to implement them with camlp4. Just a
matter of time -- and motivation.

The only limitation I can see, is that the generated constructors won't
be capitalized. E.g.:

type t = MyConstr | YourConstr of int 

=>

type t = MyConstr | YourConstr of int

let myConstr = MyConstr
let yourConstr i = YouConstr i

Regards,
Sylvain Le Gall

Re: Generalized Algebraic Datatypes

[Stefan Monnier]

> type _ t =
>   | IntLit : int -> int t
>   | BoolLit : bool -> bool t
>   | Pair : 'a t * 'b t -> ('a * 'b) t
>   | App : ('a -> 'b) t * 'a t -> 'b t
>   | Abs : ('a -> 'b) -> ('a -> 'b) t 

> There's something "Haskellish" about this syntax, in the sense that type
> constructors are portrayed as being like functions.

Indeed IIRC OCaml does not accept "App" as an expression (you have to
provide arguments to the construct).  Maybe this is a good opportunity
to lift this restriction.

> While this does make sense in Haskell, in Ocaml it feels a bit out of
> place, because you cannot, for example, partially apply
> a type constructor.

The types above don't allow partial applications either.  They use the
OCaml/SML style of constructors were partial application is not possible
because the various arguments are not provided in a curried way.


        Stefan

Re: Generalized Algebraic Datatypes

[Sylvain Le Gall]

On 29-10-2010, Jacques Le Normand <rathereasy@gmail.com> wrote:
>
> I didn't know about this alternate syntax; can you please describe it?
> cheers
> --Jacques

It is on page 14:
http://gallium.inria.fr/~xleroy/talks/cug2008.pdf

And around 14:22 in the video:
http://video.google.com/videoplay?docid=1704671501085578312&hl=en#

Regards
Sylvain Le Gall

Generalized Algebraic Datatypes

[Jacques Le Normand]

[-- Attachment #1: Type: text/plain, Size: 422 bytes --]

Dear Caml list,

I am pleased to announce an experimental branch of the O'Caml compiler:
O'Caml extended with Generalized Algebraic Datatypes. You can find more
information on this webpage:

https://sites.google.com/site/ocamlgadt/


And you can grab the latest release here:

svn checkout https://yquem.inria.fr/caml/svn/ocaml/branches/gadts


Any feedback would be very much appreciated.

Sincerely,

Jacques Le Normand

[-- Attachment #2: Type: text/html, Size: 1266 bytes --]