[Caml-list] extensible records again

[Caml-list] extensible records again

[Michael Vanier]

Hi everyone,

I sent some email to this list a while back asking for advice on how to
handle a problem which called for extensible records.  I got some good
suggestions involving polymorphic variants, but it turns out that the
best proposed solution won't work because of problems with polymorphic
references.  I'll recap the problem here and (once again) ask for advice from
the experts.
 
I've written a dynamically-typed language in ocaml, and I want to be able to
add new types to the language without having to add new primitive types to
the system.  So, for instance, my basic type definition looks something like
this:
 
    type data =
        Int of int
      | Float of float
      | ...
 
Now I want to add a type for (say) files.  I don't want this to be a type
at the same level as ints or floats, because I want users to be able to add
their own types to the language without hacking the core type definition.
I can do this as follows:
 
    (* types.mli *)
    type data =
        Int of int
      | Float of float
      | ...
      | Extension of exn
 
    (* files.ml *)
    exception File of out_channel
                                                                                        
    let close (d : data) =
      match data with
        Extension ext ->
          (match ext with
              File f -> (* close the file *)
            | _ -> raise (Failure "invalid type")))
        | _ -> raise (Failure "invalid type")
                                                                                        
This is OK, but it abuses the exception system.  I asked for ways to get the
same result with polymorphic variants.  A suggested approach (thanks to
Aleksey Nogin) was this:
                                                                                        
# type 'a data = Int of int | Ext of 'a;;
type 'a data = Int of int | Ext of 'a
# let open_file f =
      match f with
         Ext `File f -> print_string ("Opening file" ^ f)
       | _ -> raise (Invalid_argument "open_file")
   ;;
val open_file : [> `File of string] data -> unit = <fun>
# let run ( f :  [> ] data -> unit) = f (Ext (`Foo 1));;
val run : ([> `Foo of int] data -> unit) -> unit = <fun>
# run open_file;;
Exception: Invalid_argument "open_file".
 
 
So I tried this.  Aside from the pain of having to change data to 'a data in
lots of places (which I can live with), I got bitten by the polymorphic
reference limitation.  Specifically, I have a mutable stack of data values
which became a mutable stack of 'a data values, but the function which
creates the mutable stack is of type '_a data, so it doesn't type check.  I
can't figure out any way around this.  Basically, my main data type _cannot_
be parameterized.  I would like to be able to say something like
 
# type data = Int of int | Ext of [> ];;
Unbound type parameter [..]
 
but this doesn't work either, as you can see.  Is there any way to get the
effect that I want?
 
Thanks in advance,
 
Mike
 

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

Re: [Caml-list] extensible records again

[Oleg Trott]

Michael Vanier wrote:

>[...] I want users to be able to add
>their own types to the language without hacking the core type definition.
>  
>

Note that in a language like Scheme, users can not add new types other 
than by combining the primitives. So, I suppose you aren't really 
talking about language users, but those who extend the language.

The obvious thing to do is to use polymorphic variants. E.g.

(* "core language" *)

let plus a b =
   match (a, b) with
   |  (`Int x), (`Int y) -> `Int (x + y)
    (*  ... *)
   |  _ -> failwith "runtime type error: argument is not a number"

>I can do this as follows:
> 
>    (* types.mli *)
>    type data =
>        Int of int
>      | Float of float
>      | ...
>      | Extension of exn
> 
>    (* files.ml *)
>    exception File of out_channel
>                                                                                        
>    let close (d : data) =
>      match data with
>        Extension ext ->
>          (match ext with
>              File f -> (* close the file *)
>            | _ -> raise (Failure "invalid type")))
>        | _ -> raise (Failure "invalid type")
>                                                                                        
>This is OK, but it abuses the exception system.  I asked for ways to get the
>same result with polymorphic variants.  A suggested approach (thanks to
>Aleksey Nogin) was this:
>                                                                                        
># type 'a data = Int of int | Ext of 'a;;
>type 'a data = Int of int | Ext of 'a
># let open_file f =
>      match f with
>         Ext `File f -> print_string ("Opening file" ^ f)
>       | _ -> raise (Invalid_argument "open_file")
>   ;;
>val open_file : [> `File of string] data -> unit = <fun>
># let run ( f :  [> ] data -> unit) = f (Ext (`Foo 1));;
>val run : ([> `Foo of int] data -> unit) -> unit = <fun>
># run open_file;;
>Exception: Invalid_argument "open_file" 
>  
>


(* language exension example, adding "files" *)

let open = function `File f -> open_file f | _ -> failwith "runtime type 
error: argument is not a file"


HTH
Oleg

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

Re: [Caml-list] extensible records again

[Michael Vanier]

> Date: Sun, 21 Mar 2004 03:08:23 -0500
> From: Oleg Trott <oleg_trott@columbia.edu>
> 
> Michael Vanier wrote:
> 
> >[...] I want users to be able to add
> >their own types to the language without hacking the core type definition.
> >  
> >
> 
> Note that in a language like Scheme, users can not add new types other 
> than by combining the primitives. So, I suppose you aren't really 
> talking about language users, but those who extend the language.

Exactly.  The analogy I give is with a language like python, where you can
add new types at the C level.  Of course, this can be done in e.g. PLT
scheme or guile or perl or ruby as well.

> 
> The obvious thing to do is to use polymorphic variants. E.g.
> 
> (* "core language" *)
> 
> let plus a b =
>    match (a, b) with
>    |  (`Int x), (`Int y) -> `Int (x + y)
>     (*  ... *)
>    |  _ -> failwith "runtime type error: argument is not a number"
> 
> >I can do this as follows:
> > 
> >    (* types.mli *)
> >    type data =
> >        Int of int
> >      | Float of float
> >      | ...
> >      | Extension of exn
> > 
> >    (* files.ml *)
> >    exception File of out_channel
> >                                                                                        
> >    let close (d : data) =
> >      match data with
> >        Extension ext ->
> >          (match ext with
> >              File f -> (* close the file *)
> >            | _ -> raise (Failure "invalid type")))
> >        | _ -> raise (Failure "invalid type")
> >                                                                                        
> >This is OK, but it abuses the exception system.  I asked for ways to get the
> >same result with polymorphic variants.  A suggested approach (thanks to
> >Aleksey Nogin) was this:
> >                                                                                        
> ># type 'a data = Int of int | Ext of 'a;;
> >type 'a data = Int of int | Ext of 'a
> ># let open_file f =
> >      match f with
> >         Ext `File f -> print_string ("Opening file" ^ f)
> >       | _ -> raise (Invalid_argument "open_file")
> >   ;;
> >val open_file : [> `File of string] data -> unit = <fun>
> ># let run ( f :  [> ] data -> unit) = f (Ext (`Foo 1));;
> >val run : ([> `Foo of int] data -> unit) -> unit = <fun>
> ># run open_file;;
> >Exception: Invalid_argument "open_file" 
> >  
> >
> 
> 
> (* language exension example, adding "files" *)
> 
> let open = function `File f -> open_file f | _ -> failwith "runtime type 
> error: argument is not a file"
> 
> 
> HTH
> Oleg
> 

I don't know if I can do this.  I have a top-level "data" type which all
data objects must be instances of.  So in the case above, "open" would be a
function which took an argument of type "data".  The question is then: how
do I specify the "data" type without explicitly making it polymorphic?

Mike

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

Re: [Caml-list] extensible records again

[Oleg Trott]

Michael Vanier wrote:

>>Date: Sun, 21 Mar 2004 03:08:23 -0500
>>From: Oleg Trott <oleg_trott@columbia.edu>
>>
>>
>>    
>>
>>Note that in a language like Scheme, users can not add new types other 
>>than by combining the primitives. So, I suppose you aren't really 
>>talking about language users, but those who extend the language.
>>    
>>
>
>Exactly.  The analogy I give is with a language like python, where you can
>add new types at the C level.  Of course, this can be done in e.g. PLT
>scheme or guile or perl or ruby as well.
>
>  
>
>>The obvious thing to do is to use polymorphic variants. E.g.
>>
>>(* "core language" *)
>>
>>let plus a b =
>>   match (a, b) with
>>   |  (`Int x), (`Int y) -> `Int (x + y)
>>    (*  ... *)
>>   |  _ -> failwith "runtime type error: argument is not a number"
>>
>>    
>>
>>>
>>>      
>>>
>>(* language exension example, adding "files" *)
>>
>>let open = function `File f -> open_file f | _ -> failwith "runtime type 
>>error: argument is not a file"
>>
>>
>>HTH
>>Oleg
>>
>>    
>>
>
>I don't know if I can do this.  
>
If you mean that your program won't type-check, then yes, it will, e.g.

let x = `Int 3
let y = `File f (* f is something that open_file accepts *)
let z = plus x y
let _ = open y
let _ = open (plus x z)

All of this will type check, and will give run-time "type" errors 
instead (as a dynamically typed language should)

>I have a top-level "data" type which all
>data objects must be instances of.  So in the case above, "open" would be a
>function which took an argument of type "data".  The question is then: how
>do I specify the "data" type without explicitly making it polymorphic?
>  
>
You simply don't need to declare "data" (which is trying to emulate 
Lisp's type T). In fact, in your case, I believe it's more convenient 
not to create an artificial distinction between the "core types" and 
"other types": suppose someone extended your language with "files", and 
you later decide to add "file" to your "core types". You'll have to 
redefine "data" and refactor a lot of your base code to do it, unless 
you just use polymorphic variants, as suggested (in which case there is 
no special distinction between "core types" and "other types").

HTH
Oleg

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

Re: [Caml-list] extensible records again

[skaller]

On Mon, 2004-03-22 at 03:10, Oleg Trott wrote:
> Michael Vanier wrote:
> 
>  In fact, in your case, I believe it's more convenient 
> not to create an artificial distinction between the "core types" and 
> "other types": suppose someone extended your language with "files", and 
> you later decide to add "file" to your "core types". You'll have to 
> redefine "data" and refactor a lot of your base code to do it, unless 
> you just use polymorphic variants, as suggested (in which case there is 
> no special distinction between "core types" and "other types").

However there IS a reason for making the distinction sometimes,
namely performance.

My Vyper interpreter (a Python interpreter written in Ocaml)
used a type like

type PyObject = Int of int | Float of float |
String of string | PyClass of pyclass

which deliberately distinguished simple types
so that a fast match could be used to perform
common calculations:

match o1, o2 with
| Int i, Int j -> Int (i + j)
....

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] extensible records again

[Oleg Trott]

skaller wrote:

>On Mon, 2004-03-22 at 03:10, Oleg Trott wrote:
>  
>
>>Michael Vanier wrote:
>>
>> In fact, in your case, I believe it's more convenient 
>>not to create an artificial distinction between the "core types" and 
>>"other types": suppose someone extended your language with "files", and 
>>you later decide to add "file" to your "core types". You'll have to 
>>redefine "data" and refactor a lot of your base code to do it, unless 
>>you just use polymorphic variants, as suggested (in which case there is 
>>no special distinction between "core types" and "other types").
>>    
>>
>
>However there IS a reason for making the distinction sometimes,
>namely performance.
>
>My Vyper interpreter (a Python interpreter written in Ocaml)
>  
>
                                                           ^^^^^^^^^^

Compared to the interpretation overhead, I don't think you'll see any 
difference in performance, not by a long shot.

If I were writing a dynamically-typed language implementation in O'Caml, 
I'd _compile_ it _to_ O'Caml (as opposed to interpreting the language) 
In fact, except for EVAL and CALL/CC, it's probably very trivial to 
write a Scheme-to-OCaml compiler, and get the performance on par with 
decent native-code Scheme compilers.

>used a type like
>
>type PyObject = Int of int | Float of float |
>String of string | PyClass of pyclass
>
>which deliberately distinguished simple types
>so that a fast match could be used to perform
>common calculations:
>
>match o1, o2 with
>| Int i, Int j -> Int (i + j)
>....
>
>  
>

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

Re: [Caml-list] extensible records again

[skaller]

On Mon, 2004-03-22 at 04:36, Oleg Trott wrote:

> >My Vyper interpreter (a Python interpreter written in Ocaml)
>                                                            ^^^^^^^^^^
> 
> Compared to the interpretation overhead, I don't think you'll see any 
> difference in performance, not by a long shot.

In Vyper it was quite significant.

> If I were writing a dynamically-typed language implementation in O'Caml, 
> I'd _compile_ it _to_ O'Caml (as opposed to interpreting the language) 

Unfortunately, Ocamlopt isn't capable of dynamic loading. 
This was one of the reasons for abandoning Vyper.

The other was the difficulty of providing stackless operation,
i.e. the inability to provide a continuation passing based
implementation. This could probably have been done if I'd
implemented a significantly more complex system than the 
simple mapping of functional code to functional code I actually
provided.

Don't be confused here: The task was to provide a Python
system, not an arbitrary interpreter.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] extensible records again

[Ville-Pertti Keinonen]

On Mar 21, 2004, at 7:36 PM, Oleg Trott wrote:

> If I were writing a dynamically-typed language implementation in 
> O'Caml, I'd _compile_ it _to_ O'Caml (as opposed to interpreting the 
> language) In fact, except for EVAL and CALL/CC, it's probably very 
> trivial to write a Scheme-to-OCaml compiler, and get the performance 
> on par with decent native-code Scheme compilers.

How would you handle interactive sessions?

Anyway, I'm pretty sure call/cc is far easier than getting good 
performance, all you need to do is use CPS, which is simple and 
efficient in OCaml.  If you want the code to run fast, you need to do 
something to make function calls more direct (no lists or arrays of 
arguments)...

The native-code Scheme compilers I've tried aren't too impressive, they 
can produce fast code but not safely and/or not with the full language 
semantics, one of the things restricting them is using C as an 
intermediate language (OCaml as an intermediate language would suffer 
from most of the same problems).  Decent Common Lisp systems work far 
better, producing native code directly, even in interactive sessions.

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

Re: [Caml-list] extensible records again

[Oleg Trott]

Ville-Pertti Keinonen wrote:

>
> On Mar 21, 2004, at 7:36 PM, Oleg Trott wrote:
>
>> If I were writing a dynamically-typed language implementation in 
>> O'Caml, I'd _compile_ it _to_ O'Caml (as opposed to interpreting the 
>> language) In fact, except for EVAL and CALL/CC, it's probably very 
>> trivial to write a Scheme-to-OCaml compiler, and get the performance 
>> on par with decent native-code Scheme compilers.
>
>
> How would you handle interactive sessions?


It would have the same limitations as OCaml, obviously: interactive in 
bytecode only (this has long been one of my biggest gripes about OCaml, 
actually). FWIW, I don't think writing a Scheme-to-OCaml compiler is a 
very useful waste of one's time, just that it should be about as easy as 
writing an interpreter for Scheme in OCaml.

Cheers,
Oleg

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

Re: [Caml-list] extensible records again

[Ville-Pertti Keinonen]

On Mar 22, 2004, at 11:32 AM, Oleg Trott wrote:

> Ville-Pertti Keinonen wrote:
>> How would you handle interactive sessions?

...after writing this, I realized that the obvious - if the compiler 
isn't a crippled implementation, you can implement a read-eval-print 
loop in a few lines of Scheme. ;-)

> It would have the same limitations as OCaml, obviously: interactive in 
> bytecode only (this has long been one of my biggest gripes about 
> OCaml, actually). FWIW, I don't think writing a Scheme-to-OCaml 
> compiler is a very useful waste of one's time, just that it should be 
> about as easy as writing an interpreter for Scheme in OCaml.

You still need eval.  For a straightforward implementation, the code 
difference between an interpreter and a compiler would be small enough 
that you could have both and use the interpreter for the interactive 
top-level and eval.

But still, I think any trivial implementation of Scheme in OCaml is 
going to be far from optimal (e.g. you'd have to do something nasty to 
avoid having ints both tagged and boxed), which is part of the reason 
why I implemented an interpreter (which could probably be turned into a 
simple compiler in a day or two), along with the fact that the main use 
is embedding in native compiled OCaml programs to make them scriptable 
(and since it ended up being considerably faster than e.g. guile, it's 
definitely not bad for that purpose).

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

Re: [Caml-list] extensible records again

[Michael Vanier]

> From: skaller <skaller@users.sourceforge.net>
> Date: 22 Mar 2004 04:06:18 +1100
> 
> On Mon, 2004-03-22 at 03:10, Oleg Trott wrote:
> > Michael Vanier wrote:
> > 
> >  In fact, in your case, I believe it's more convenient 
> > not to create an artificial distinction between the "core types" and 
> > "other types": suppose someone extended your language with "files", and 
> > you later decide to add "file" to your "core types". You'll have to 
> > redefine "data" and refactor a lot of your base code to do it, unless 
> > you just use polymorphic variants, as suggested (in which case there is 
> > no special distinction between "core types" and "other types").
> 
> However there IS a reason for making the distinction sometimes,
> namely performance.
> 
> My Vyper interpreter (a Python interpreter written in Ocaml)
> used a type like
> 
> type PyObject = Int of int | Float of float |
> String of string | PyClass of pyclass
> 
> which deliberately distinguished simple types
> so that a fast match could be used to perform
> common calculations:
> 
> match o1, o2 with
> | Int i, Int j -> Int (i + j)
> ....
> 

Is the code for Vyper still available?

Also, is there really any significant speed difference between polymorphic
variants and regular variants?  How would this compare to using exceptions
as an extensible variant type?

Mike


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

Re: [Caml-list] extensible records again

[skaller]

On Mon, 2004-03-22 at 09:35, Michael Vanier wrote:

> Is the code for Vyper still available?

No, it was deleted from Sourceforge and I have no copy.

> Also, is there really any significant speed difference between polymorphic
> variants and regular variants?  

It is hard to say, but I would tend to ignore the performance
issue, at least at first. For some types such as:

	'a option

where you have a

	match x with Some y -> ... | None 

inside a tight loop there may be a small difference.
I haven't done any serious performance tests though.

> How would this compare to using exceptions
> as an extensible variant type?

I thought exceptions were just a weak form of
polymorhic variant.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] extensible records again

[Michael Vanier]

> Date: Sun, 21 Mar 2004 11:10:32 -0500
> From: Oleg Trott <oleg_trott@columbia.edu>
> 
> Michael Vanier wrote:
> 
> >>Date: Sun, 21 Mar 2004 03:08:23 -0500
> >>From: Oleg Trott <oleg_trott@columbia.edu>
> >>
> >>
> >>    
> >>
> >>Note that in a language like Scheme, users can not add new types other 
> >>than by combining the primitives. So, I suppose you aren't really 
> >>talking about language users, but those who extend the language.
> >>    
> >>
> >
> >Exactly.  The analogy I give is with a language like python, where you can
> >add new types at the C level.  Of course, this can be done in e.g. PLT
> >scheme or guile or perl or ruby as well.
> >
> >  
> >
> >>The obvious thing to do is to use polymorphic variants. E.g.
> >>
> >>(* "core language" *)
> >>
> >>let plus a b =
> >>   match (a, b) with
> >>   |  (`Int x), (`Int y) -> `Int (x + y)
> >>    (*  ... *)
> >>   |  _ -> failwith "runtime type error: argument is not a number"
> >>
> >>    
> >>
> >>>
> >>>      
> >>>
> >>(* language exension example, adding "files" *)
> >>
> >>let open = function `File f -> open_file f | _ -> failwith "runtime type 
> >>error: argument is not a file"
> >>
> >>
> >>HTH
> >>Oleg
> >>
> >>    
> >>
> >
> >I don't know if I can do this.  
> >
> If you mean that your program won't type-check, then yes, it will, e.g.
> 
> let x = `Int 3
> let y = `File f (* f is something that open_file accepts *)
> let z = plus x y
> let _ = open y
> let _ = open (plus x z)
> 
> All of this will type check, and will give run-time "type" errors 
> instead (as a dynamically typed language should)
> 
> >I have a top-level "data" type which all
> >data objects must be instances of.  So in the case above, "open" would be a
> >function which took an argument of type "data".  The question is then: how
> >do I specify the "data" type without explicitly making it polymorphic?
> >  
> >
> You simply don't need to declare "data" (which is trying to emulate 
> Lisp's type T). In fact, in your case, I believe it's more convenient 
> not to create an artificial distinction between the "core types" and 
> "other types": suppose someone extended your language with "files", and 
> you later decide to add "file" to your "core types". You'll have to 
> redefine "data" and refactor a lot of your base code to do it, unless 
> you just use polymorphic variants, as suggested (in which case there is 
> no special distinction between "core types" and "other types").
> 
> HTH
> Oleg
> 

If I understand you correctly, then you're arguing that *all* my "core
types" should be implemented using polymorphic variants.  This is an
interesting idea, which I'll consider.  I think the problems I'm having
have a lot to do with trying to mix polymorphic and regular variant types,
which seems somewhat unnatural anyway.

Mike

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

Re: [Caml-list] extensible records again

[skaller]

On Mon, 2004-03-22 at 09:34, Michael Vanier wrote:

> If I understand you correctly, then you're arguing that *all* my "core
> types" should be implemented using polymorphic variants.

I use Polymorphic Variants almost exclusively in Felix.
They're more flexible but also give nastier error messages.

The main downside is that to make covariant subtyping
you need to use fixpoints, which is fine for a single
parameter but unworkable for a more complex term
structure.

It would be interesting if Camlp4 could solve this problem
somehow.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] extensible records again

[Michael Vanier]

> From: skaller <skaller@users.sourceforge.net>
> Date: 22 Mar 2004 14:31:16 +1100
> 
> On Mon, 2004-03-22 at 09:34, Michael Vanier wrote:
> 
> > If I understand you correctly, then you're arguing that *all* my "core
> > types" should be implemented using polymorphic variants.
> 
> I use Polymorphic Variants almost exclusively in Felix.
> They're more flexible but also give nastier error messages.
> 
> The main downside is that to make covariant subtyping
> you need to use fixpoints, which is fine for a single
> parameter but unworkable for a more complex term
> structure.

Forgive my ignorance, but what do you mean by this?

Mike

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

Re: [Caml-list] extensible records again

[skaller]

On Mon, 2004-03-22 at 16:54, Michael Vanier wrote:

> > The main downside is that to make covariant subtyping
> > you need to use fixpoints, which is fine for a single
> > parameter but unworkable for a more complex term
> > structure.
> 
> Forgive my ignorance, but what do you mean by this?

At the moment you can do this:

type x = [`A | `B ]
type y = [a | `C ]

so that y is a subtype (extension) of x.

You can even match:

match aY with
| #x as xv -> xv
| _ -> failwith "Not an x"

to reduce aY to an x.

This works fine as written because y is a 'flat'
extension of x: the type constructors are invariant
in their arguments (vacuously in the example, since
none of the constructors have any arguments).

But now consider a recursive type:

type x = [`A of x | `B]
type y = [ `A of y | `B | `C of y]

Jacques Garrigue showed me a solution using fixpoints
where the you don't want to write out all the terms
of x in y again:

type 't x1 = [`A of 't | `B]
type 't x2 = [`C of 't] (* the extension *)

type 't y1 = ['t x1 | 't x2] (* combine the parts *)
type x = 't x1 as 't (* fixate *)
type y = 't y1 as 't

A real world example: terms of some language
may included 'syntactic sugar' which can be removed
recursively by rewriting rules/term reductions.
For example Felix uses an extended type term which
allows lambda abstractions in types.

We'd like to indicate *statically* that a term
has been reduced. The difficulty is that there
seems to be an almost combinatorial explosion
in how much you have to write in the number
of parameters. In the above example there is only 
one, indicated by 't.

In Felix, I want to partition expressions, types,
patterns, statements, and a few other kinds of terms
into one or more classes and use some combinations
of these: but all these terms are mutually recursive:
statements can contain expressions and types and patterns,
patterns have 'when' expressions, types may contain
"typeof(expression)" as a type, and statements can
be considered as expressions..

So I end up with a rather large number of parameters
on each of the fine grained components I want to combine:
something like:

type 'expr 'typ 'pat 'stat expr1 = ....
...
type 'expr 'typ 'pat 'stat typ1 = ...
...

In the 'flat' case I don't have to write out the
parameters. And if I forget the covariant refinement
and just use the supertype everywhere, losing the 
benefit of extra static type checking, I can just
declare all these terms once and make them all
mutually recursive.

I want to have my cake and eat it too :D
I want to write:

type x = [`A of x | `B ]
type y = [a | `C ]

and have it 'know' that the `A in type y takes
an y argument, not an x. Perhaps this can be done as so:

type x = [`A of +x | `B ]

where the '+' indicates that the argument is covariant.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] extensible records again

[Jacques Garrigue]

From: skaller <skaller@users.sourceforge.net>

> At the moment you can do this:
> 
> type x = [`A | `B ]
> type y = [x | `C ]
> 
> so that y is a subtype (extension) of x.
> 
> You can even match:
> 
> match aY with
> | #x as xv -> xv
> | _ -> failwith "Not an x"
> 
> to reduce aY to an x.

[...]
Let me just add a pointer to the concrete description of how you can
do this with recursive types:
http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/papers/fose2000.html

It describes in detail the steps to build extensible recursive
datatypes.

> In Felix, I want to partition expressions, types,
> patterns, statements, and a few other kinds of terms
> into one or more classes and use some combinations
> of these: but all these terms are mutually recursive:
> statements can contain expressions and types and patterns,
> patterns have 'when' expressions, types may contain
> "typeof(expression)" as a type, and statements can
> be considered as expressions..
> 
> So I end up with a rather large number of parameters
> on each of the fine grained components I want to combine:
> something like:
> 
> type 'expr 'typ 'pat 'stat expr1 = ....
> ...
> type 'expr 'typ 'pat 'stat typ1 = ...
> ...

The mixin2.ml code on the above page gives an example of you can do
it using classes. Note that this solves only the problem for
functions, not for types.

Another approach, which could maybe solve the problem with type
parameters, would be to use recursive modules: define all your
sublanguages as functors, and close the recursion with a recursive
module definition. Recursive modules are a new feature in ocaml 3.07,
but I think they can help for such problems.
However, there is a difficulty, as all modules in a recursive
definition must have an explicit signature, and the language of module
types seems to be weaker than the language of modules.
The fact one has to duplicate all type definitions is bothering too.

> type x = [`A of +x | `B ]
> type y = [x | `C ]

might be encoded as

module type Xrec = sig type t end
module X0(Xrec : Xrec) =
  struct type t0 = Xrec.t type t = [`A of t0 | `B] end
module type Xsig = sig type t0 type t = [`A of t0 | `B] end
module rec X : (Xsig with type t0 = X.t) = X0(X)
module Y0(Xrec : Xrec) =
  struct
    module XY = X0(Xrec)
    type t0 = Xrec.t
    type t = [XY.t | `C]
  end
module type Ysig = ???
module rec Y : (Xsig with type t0 = Y.t) = Y0(Y)

Jacques Garrigue

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

Re: [Caml-list] extensible records again

[Julien Signoles]

> > type x = [`A of +x | `B ]
> > type y = [x | `C ]
>
> might be encoded as
>
> module type Xrec = sig type t end
> module X0(Xrec : Xrec) =
>   struct type t0 = Xrec.t type t = [`A of t0 | `B] end
> module type Xsig = sig type t0 type t = [`A of t0 | `B] end
> module rec X : (Xsig with type t0 = X.t) = X0(X)
> module Y0(Xrec : Xrec) =
>   struct
>     module XY = X0(Xrec)
>     type t0 = Xrec.t
>     type t = [XY.t | `C]
>   end
> module type Ysig = ???
> module rec Y : (Xsig with type t0 = Y.t) = Y0(Y)

(* [...] *)
module type Ysig = sig
  module XY : Xsig
  type t0
  type t = [ XY.t | `C]
end
module rec Y : (Ysig with module XY = X0(Y) and type t0 = Y.t) = Y0(Y)

What do you think about this signature ? But perhaps I misunderstand
somethink: I think you don't use t0 in Y0 and Ysig because t0 is enclosed
in XY. I would write somethink like:

(* [...] *)
module Y0(Xrec : Xrec) = struct
  module XY = X0(Xrec)
  type t = [XY.t | `C]
end
module type Ysig = sig
  module XY : Xsig
  type t = [ XY.t | `C]
end
module rec Y : (Ysig with module XY = X0(Y)) = Y0(Y)


Julien
-- 
mailto:Julien.Signoles@lri.fr ; http://www.lri.fr/~signoles
"In theory, practice and theory are the same,
but in practice they are different" (Larry McVoy)

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

Re: [Caml-list] extensible records again

[Jacques Garrigue]

From: Julien Signoles <Julien.Signoles@lri.fr>
> I think you don't use t0 in Y0 and Ysig because t0 is enclosed
> in XY. I would write somethink like:
> 
> (* [...] *)
> module Y0(Xrec : Xrec) = struct
>   module XY = X0(Xrec)
>   type t = [XY.t | `C]
> end
> module type Ysig = sig
>   module XY : Xsig
>   type t = [ XY.t | `C]
> end
> module rec Y : (Ysig with module XY = X0(Y)) = Y0(Y)

Nicer. I didn't know that you could specify modules inside a signature
through functor application. Looks powerful.
This allows this even more modular encoding:

open Printf
module type Xt = sig type t end
module type Xrec = sig module T : Xt val show : T.t -> string end
module X0t (Xt : Xt) = struct type t = [`A of Xt.t | `B] end
module X0(Xrec : Xrec) =
  struct
    module T = X0t(Xrec.T)
    let rec show = function
        `A x -> "A" ^ Xrec.show x
      | `B -> "B"
 end
module rec X : (Xrec with module T = X0t(X.T)) = X0(X)
module Y0t(Xt : Xt) = struct type t = [X0t(Xt).t | `C] end
module Y0(Xrec : Xrec) =
  struct
    module T = Y0t(Xrec.T)
    module XY = X0(Xrec)
    let rec show = function
        #XY.T.t as x -> XY.show x
      | `C -> "C"
  end
module rec Y : (Xrec with module T = Y0t(Y.T)) = Y0(Y)

Note of course that this is not very interesting on this simple
example. Using that many modules only gets useful if you have several
mutually recursive types.

Jacques Garrigue

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

Re: [Caml-list] extensible records again

[Martin Jambon]

On Sat, 20 Mar 2004, Michael Vanier wrote:

> So I tried this.  Aside from the pain of having to change data to 'a data in
> lots of places (which I can live with), I got bitten by the polymorphic
> reference limitation.  Specifically, I have a mutable stack of data values
> which became a mutable stack of 'a data values, but the function which
> creates the mutable stack is of type '_a data, so it doesn't type check.  I
> can't figure out any way around this.  Basically, my main data type _cannot_
> be parameterized.

Keep your code polymorphic: create your stack in the same compilation
unit as the full type instanciation.
Then you have to pass your stack as a parameter
to all functions that use it.

I guess this is more or less what you do:

(* a.ml *)
let stack =
  let st = Stack.create () in
  Stack.push (`Int 1) st;
  st
(* compiler complains about '_ *)


(* b.ml *)
let some_function x =
   match Stack.pop stack with
       `Int i -> print_int i
     | `Custom s -> print_string s
     | _ -> ()


Instead you should write:

(* a.ml *)
let init_stack () =
  let st = Stack.create () in
  Stack.push (`Int 1) st;
  st


(* b.ml *)
let some_function stack x =
  match Stack.pop stack with
      `Int i -> print_int i
    | `Custom s -> print_string s
    | _ -> print_float x

let _ =
  let stack = A.init_stack () in
  some_function stack 1.2


I hope it answers your question...

Martin


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

Re: [Caml-list] extensible records again

[Michael Vanier]

Interesting.  I'll try it.  Thanks!

Mike

> Date: Sun, 21 Mar 2004 16:53:38 +0800 (HKT)
> From: Martin Jambon <martin_jambon@emailuser.net>
> Cc: caml-list@inria.fr
> 
> On Sat, 20 Mar 2004, Michael Vanier wrote:
> 
> > So I tried this.  Aside from the pain of having to change data to 'a data in
> > lots of places (which I can live with), I got bitten by the polymorphic
> > reference limitation.  Specifically, I have a mutable stack of data values
> > which became a mutable stack of 'a data values, but the function which
> > creates the mutable stack is of type '_a data, so it doesn't type check.  I
> > can't figure out any way around this.  Basically, my main data type _cannot_
> > be parameterized.
> 
> Keep your code polymorphic: create your stack in the same compilation
> unit as the full type instanciation.
> Then you have to pass your stack as a parameter
> to all functions that use it.
> 
> I guess this is more or less what you do:
> 
> (* a.ml *)
> let stack =
>   let st = Stack.create () in
>   Stack.push (`Int 1) st;
>   st
> (* compiler complains about '_ *)
> 
> 
> (* b.ml *)
> let some_function x =
>    match Stack.pop stack with
>        `Int i -> print_int i
>      | `Custom s -> print_string s
>      | _ -> ()
> 
> 
> Instead you should write:
> 
> (* a.ml *)
> let init_stack () =
>   let st = Stack.create () in
>   Stack.push (`Int 1) st;
>   st
> 
> 
> (* b.ml *)
> let some_function stack x =
>   match Stack.pop stack with
>       `Int i -> print_int i
>     | `Custom s -> print_string s
>     | _ -> print_float x
> 
> let _ =
>   let stack = A.init_stack () in
>   some_function stack 1.2
> 
> 
> I hope it answers your question...
> 
> Martin
> 
> 

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

Re: [Caml-list] extensible records again

[skaller]

On Sun, 2004-03-21 at 17:21, Michael Vanier wrote:

> I've written a dynamically-typed language in ocaml, and I want to be able to
> add new types to the language without having to add new primitive types to
> the system. 

See Felix. The core system has NO primitive types,
not even bool: all primitive types are added by the user
(as bindings to C types).

>  
> Now I want to add a type for (say) files.  I don't want this to be a type
> at the same level as ints or floats, because I want users to be able to add
> their own types to the language without hacking the core type definition.
> I can do this as follows:
>  
>     (* types.mli *)
>     type data =
>         Int of int
>       | Float of float
>       | ...
>       | Extension of exn

You can just use:

	| Extension of string * address

where address is a machine address of some binary
data. What it is is completely irrelevant, since the
operations on user defined primitive data type
can only be specified in one way: by providing
C functions which manipulate that type.


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

Re: [Caml-list] extensible records again

[Achim Blumensath]

Michael Vanier wrote:
> I've written a dynamically-typed language in ocaml, and I want to be able to
> add new types to the language without having to add new primitive types to
> the system.

This weekend I have done something like this in ant:

   www-mgi.informatik.rwth-aachen.de/~blume/pub/ant-current.tar.bz2

The type declarations are in

  VM/Types.ml  and  VM/Opaque.ml

and an example showing how to define your own type in

  Markup/ALBindings.ml

Achim
-- 
________________________________________________________________________
                                                              | \_____/ |
   Achim Blumensath                                          \O/ \___/\ |
   LaBRI / Bordeaux                                          =o=  \ /\ \|
   www-mgi.informatik.rwth-aachen.de/~blume                  /"\   o----|
____________________________________________________________________\___|

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

Re: [Caml-list] extensible records again

[Michael Vanier]

Achim,

I took up your suggestion and downloaded your code.  In Opaque.ml I see
this mysterious declaration:

type opaque 'a =
{
  data      : !'b . 'b;
  type_info : type_info 'a
}
and type_info 'a =
{
  apply   : opaque 'a -> 'a -> 'a;
  compare : opaque 'a -> opaque 'a -> bool;
  unify   : opaque 'a -> opaque 'a -> bool
};
 
I realize that this uses the revised syntax, but I can't find any
documentation on what "!'b . 'b" is supposed to mean.  It looks like a
universal quantifier on 'b -- correct?

Mike

> Date: Mon, 22 Mar 2004 09:13:55 +0100
> From: Achim Blumensath <blume@labri.fr>
> Mail-Followup-To: caml-list@inria.fr
> 
> Michael Vanier wrote:
> > I've written a dynamically-typed language in ocaml, and I want to be able to
> > add new types to the language without having to add new primitive types to
> > the system.
> 
> This weekend I have done something like this in ant:
> 
>    www-mgi.informatik.rwth-aachen.de/~blume/pub/ant-current.tar.bz2
> 
> The type declarations are in
> 
>   VM/Types.ml  and  VM/Opaque.ml
> 
> and an example showing how to define your own type in
> 
>   Markup/ALBindings.ml
> 
> Achim
> -- 
> ________________________________________________________________________
>                                                               | \_____/ |
>    Achim Blumensath                                          \O/ \___/\ |
>    LaBRI / Bordeaux                                          =o=  \ /\ \|
>    www-mgi.informatik.rwth-aachen.de/~blume                  /"\   o----|
> ____________________________________________________________________\___|
> 
> -------------------
> 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
> 

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

Re: [Caml-list] extensible records again

[Achim Blumensath]

Michael Vanier wrote:
> I took up your suggestion and downloaded your code.  In Opaque.ml I see
> this mysterious declaration:
> 
> type opaque 'a =
> {
>   data      : !'b . 'b;
>   type_info : type_info 'a
> }
> and type_info 'a =
> {
>   apply   : opaque 'a -> 'a -> 'a;
>   compare : opaque 'a -> opaque 'a -> bool;
>   unify   : opaque 'a -> opaque 'a -> bool
> };
>  
> I realize that this uses the revised syntax, but I can't find any
> documentation on what "!'b . 'b" is supposed to mean.  It looks like a
> universal quantifier on 'b -- correct?

Yes, it is mentioned in the manual at the end of section 1.5.
The usual syntax is 'b . 'b without the !.

Achim
-- 
________________________________________________________________________
                                                              | \_____/ |
   Achim Blumensath                                          \O/ \___/\ |
   LaBRI / Bordeaux                                          =o=  \ /\ \|
   www-mgi.informatik.rwth-aachen.de/~blume                  /"\   o----|
____________________________________________________________________\___|

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

Re: [Caml-list] extensible records again

[Marcin 'Qrczak' Kowalczyk]

W liście z sob, 20-03-2004, godz. 22:21 -0800, Michael Vanier napisał:

> I've written a dynamically-typed language in ocaml, and I want to be able to
> add new types to the language without having to add new primitive types to
> the system.

When I had this problem, I found no satisfactory type-safe way, and had
resorted to Obj.magic.

Each object type has a common first field which points to a descriptor.
The descriptor contains type id (unique integer) and implementation of
operations common to all objects (in my case it's only application to a
sequence of arguments; for performance there are separate entries for
known small numbers of arguments and one entry taking a list).

Type ids for new types are allocated dynamically, using a global
counter. I ignore the possibility of wraparound, one would have to make
2**(word_size-1) new types (possible, as types can be defined locally
and then forgotten, but improbable).

The OCaml type which can represent an arbitrary object is a record type
consisting of the descriptor only. Other types are longer records, which
are Object.magic'ed to and from the generic type. Having the descriptor
alone you can apply common operations or check the type.

Unfortunately I found no other representation which is as flexible and
as efficient. It must support performing common operations without
knowing the type, taking some type id suitable for indexing a
dictionary. New types must be definable without having to change the
interpreter modules, and they can be defined both in OCaml code and from
my language. Objects should not require much indirection or duplication.

(The interpreter is now dead, I used it to bootstrap a compiler.)

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/


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