ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Jeremy Yallop]

I'm pleased to announce an initial release of `deriving', a system for
constructing functions automatically from type definitions.

Deriving extends OCaml with two new operations: a syntax for calling
an "overloaded" function at a particular type:

    C.function<t> v

and the `deriving' construct found in Haskell (and Clean) for
requesting that the implementation generate an instance of an
overloaded function from a type definition:

    type t = r
      deriving (C1, C2)

Deriving provides functions for pretty-printing, dynamic typing,
type-safe structure-sharing marshalling, SML-style equality,
mapping, and more.  Functions can be generated for most OCaml types,
including records, standard and polymorphic variants, tuples, mutually
recursive types, and types that use abstract type constructors defined
elsewhere.  A few more exotic constructs, such as private types and type
replication, are supported.  Derived functions are also extensible: the
user can choose to supply an implementation at a particular type if the
generated version is not to his taste.

You can find deriving (along with preliminary documentation and tests)
at

    http://code.google.com/p/deriving/

Note: you'll need OCaml 3.10.

Some examples of use follow.

Pretty-printing:

    Show.show<int> 3
    =>
    "3"

    let factors = [(10,[2;5]); (11, []);  12, [2;3;4;6]]
    Show.show<(int * int list) list> factors
    =>
    "[(10,[2; 5]); (11, []);  12, [2; 3; 4; 6]]"


    type 'a tree = Leaf of 'a | Branch of 'a tree * 'a * 'a tree
        deriving (Show, Typeable, Eq, Shelve)

    type point = { x : float; y : float }
        deriving (Show, Typeable, Eq, Shelve)

    let points = Branch (Leaf {x=0.0;
                               y=0.0;},
                         {x=2.0; y=2.0},
                         Branch (Leaf {x=1.0; y=1.0},
                                 {x=1.0; y=0.0},
                                 Leaf {x=0.0; y=1.0}))

    Show.show<point tree> points
    =>
    "Branch
       (Leaf {x =193.11; y =132.13}, {x =211.91; y =201.11},
        Branch
          (Leaf {x =113.12; y =1.}, {x =12.7; y =44.1}, Leaf {x =0.; y 
=13.41}))"

Dynamic typing:

    let items =
       [Typeable.mk<int> 3;
        Typeable.mk<float> 3.0;
        Typeable.mk<string tree> (Leaf "three")]
    =>
    [<abstr>; <abstr>; <abstr>]

    Typeable.cast<int> (List.hd items)
    =>
    Some 3

    Typeable.cast<float> (List.hd items)
    =>
    None


Dynamic typing again:

    type 'a seq = [`Nil | `Cons of 'a * 'a seq]
        deriving (Typeable)

    let l = `Cons (3, `Cons (2, `Cons (1, `Nil)))

    Typeable.cast<[`Cons of int * 'a|`Nil] as 'a>
      (Typeable.mk<int seq> l)
    =>
    Some (`Cons (3, `Cons (2, `Cons (1, `Nil))))

Serialisation (marshalling):

    Shelve.shelveS<point tree> points
    =>
 
"\007\003\t\128\128\128\128\128\128\128\248?\t\128\128\128\128\128\128\128\128@\001\000\005\000\001\008\000\001\n\001\003\004\t\003\000\001\012\001\003\006\011\005\005\002\002\000\002\000\002\002\000\000\002\001\001\002\002\002"

    Shelve.unshelveS<point tree> (Shelve.shelveS<point tree> points)
    =>
    Branch
      (Leaf {x =193.11; y =132.13}, {x =211.91; y =201.11},
       Branch
         (Leaf {x =113.12; y =1.}, {x =12.7; y =44.1}, Leaf {x =0.;
                                                             y =13.41}))


    Shelve.unshelveS<int> (Shelve.shelveS<point tree> points)
    =>
    *** Exception

For more see the documentation and test suite.

Comments, bug reports, and other feedback will be most welcome.

Jeremy.

Re: [Caml-list] ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Nicolas Pouillard]

On 6/20/07, Jeremy Yallop <jeremy.yallop@ed.ac.uk> wrote:
> I'm pleased to announce an initial release of `deriving', a system for
> constructing functions automatically from type definitions.
>

Great, that's really amazing!

No doubt, there is a new camlp4 hacker in the community :)

Cheers,

-- 
Nicolas Pouillard

Re: [Caml-list] ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Jeremy Yallop]

Joel Reymont wrote:
> 
> On Jun 20, 2007, at 1:14 AM, Jeremy Yallop wrote:
> 
>> Serialisation (marshalling):
>>
>>    Shelve.shelveS<point tree> points
>>    =>
>> "\007\003\t\128\128\128\128\128\128\128\248?\t\128\128\128\128\128\128\128\128@\001\000\005\000\001\008\000\001\n\001\003\004\t\003\000\001\012\001\003\006\011\005\005\002\002\000\002\000\002\002\000\000\002\001\001\002\002\002" 
>>
> 
> Aha! Now I can implement a Sexp library for 3.10!
> 
> What is the difference between pickling and shelving, though?

In `deriving' Pickle is a fairly naive value-oriented serialiser.  It 
doesn't do any structure sharing: the same value can be repeated several 
times in the output.  It doesn't preserve cycles, so it's not available 
for mutable values.  You can customize Pickle by writing your own 
definition for a particular type.

Shelve handles cycles correctly and minimises values so the output is 
potentially much smaller.  It also provides a different means of 
specialization: by giving a custom definition of equality for a type you 
can increase opportunities for sharing.  It's currently rather slow for 
large values, but I expect that to change in the next release.  Shelve 
is built on top of Pickle, FWIW.

The choice of names is pretty arbitrary: I wrote Pickle first, then I 
needed another name when I wrote Shelve.

Jeremy.

Re: ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Stefan Monnier]

> In `deriving' Pickle is a fairly naive value-oriented serialiser.

That's an unfortunate choice.  Traditionally, "pickling" was always used for
the structure&cycle preserving form of serialization.  Sometimes "marshalling"
was used to describe the naive no-sharing kind of serialization.

Nowadays, it seems that "pickling" is not used very often and "marshalling"
tends to take care of sharing and cycles as well, tho.

Still, in my mind "pickling" implies "the non-naive kind of serialization".


        Stefan

Re: [Caml-list] Re: ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Jeremy Yallop]

Stefan Monnier wrote:
>> In `deriving' Pickle is a fairly naive value-oriented serialiser.
> 
> That's an unfortunate choice.  Traditionally, "pickling" was always used for
> the structure&cycle preserving form of serialization.  Sometimes "marshalling"
> was used to describe the naive no-sharing kind of serialization.
> 
> Nowadays, it seems that "pickling" is not used very often and "marshalling"
> tends to take care of sharing and cycles as well, tho.
> 
> Still, in my mind "pickling" implies "the non-naive kind of serialization".

Interesting.  Of course, the name "Marshal" is already taken by the 
OCaml standard library.  Do you have any other suggestions for a name 
for naive serialisation?  "Serialise"/"Serialize", perhaps?

Re: [Caml-list] Re: ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Eric Cooper]

On Wed, Jun 20, 2007 at 08:38:20PM +0100, Jeremy Yallop wrote:
> Do you have any other suggestions for a name for naive
> serialisation?  "Serialise"/"Serialize", perhaps?

Dump?

-- 
Eric Cooper             e c c @ c m u . e d u

Re: [Caml-list] Re: ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Nicolas Pouillard]

On 6/20/07, Eric Cooper <ecc@cmu.edu> wrote:
> On Wed, Jun 20, 2007 at 08:38:20PM +0100, Jeremy Yallop wrote:
> > Do you have any other suggestions for a name for naive
> > serialisation?  "Serialise"/"Serialize", perhaps?
>
> Dump?
>

+1

Pickle -> Dump
Shelve -> Pickle

Would be better...

My 0.02€

-- 
Nicolas Pouillard

Re: [Caml-list] Re: ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Jeremy Yallop]

Nicolas Pouillard wrote:
> On 6/20/07, Eric Cooper <ecc@cmu.edu> wrote:
>> On Wed, Jun 20, 2007 at 08:38:20PM +0100, Jeremy Yallop wrote:
>> > Do you have any other suggestions for a name for naive
>> > serialisation?  "Serialise"/"Serialize", perhaps?
>>
>> Dump?
> 
> +1
> 
> Pickle -> Dump
> Shelve -> Pickle

Thanks for the suggestions, everyone.  I've uploaded a new version of 
deriving with the name changes you suggested.  There are a few other 
changes: the interfaces of Dump and Pickle are now compatible, deriving 
should now work on 64-bit platforms, and there's a fix for a quotation 
that was causing compilation problems.

I've only had one report of unsuccessful compilation.  I'd be very 
interested to hear if anyone else had problems building deriving or 
running the tests.  Reports of success are welcome too, of course.

Jeremy.

Re: [Caml-list] ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Jon Harrop]

On Wednesday 20 June 2007 01:14:42 Jeremy Yallop wrote:
> I'm pleased to announce an initial release of `deriving', a system for
> constructing functions automatically from type definitions.
>
> Deriving extends OCaml with two new operations: a syntax for calling
> an "overloaded" function at a particular type:
>
>     C.function<t> v
>
> and the `deriving' construct found in Haskell (and Clean) for
> requesting that the implementation generate an instance of an
> overloaded function from a type definition:
>
>     type t = r
>       deriving (C1, C2)
>
> Deriving provides functions for pretty-printing, dynamic typing,
> type-safe structure-sharing marshalling, SML-style equality,
> mapping, and more.

I don't know how I managed to miss this awesome announcement!

The idea of retrofitting equality types onto OCaml interests me greatly. Any 
chance you could elaborate on how this is done and what errors look like? :-)

Many thanks,
-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e

Re: [Caml-list] ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Jon Harrop]

On Sunday 15 July 2007 05:03:16 Jon Harrop wrote:
> The idea of retrofitting equality types onto OCaml interests me greatly.
> Any chance you could elaborate on how this is done and what errors look
> like? :-)

Incidentally, another rather cool application of this kind of functionality 
would be to mimic .NET's PropertyGrid class. This class uses reflection to 
convert a data structure into a Windows Forms control that allows you to edit 
that data structure.

This is quite profilic in the developer-facing GUIs from Microsoft, such as 
the properties subwindow that you get in Visual Studio's GUI designer. 
Essentially it provides a very easy way to lash up totally unergonomic GUIs. 
An idea that is very close to my heart. ;-)

You could take an OCaml data type and translate it into GTK widgets that let 
you edit its contents.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Jeremy Yallop]

Jon,

Apologies for the delay in replying!

Jon Harrop wrote:
 > On Wednesday 20 June 2007 01:14:42 Jeremy Yallop wrote:
 > > Deriving provides functions for pretty-printing, dynamic typing,
 > > type-safe structure-sharing marshalling, SML-style equality,
 > > mapping, and more.
 >
 > I don't know how I managed to miss this awesome announcement!
 >
 > The idea of retrofitting equality types onto OCaml interests me
 > greatly. Any chance you could elaborate on how this is done and what
 > errors look like?  :-)

Sure!  I suppose "SML-style equality" can be understood to include
various things:

   (1) an equality predicate that tests for physical equality at mutable
       types and structural equality at immutable types.

         SOME 3 = SOME 3
         => true

         SOME (ref 3) = SOME (ref 3)
         => false

   (2) a compile-time error if you try to use equality at a type for
       which it's not defined (an abstract or functional type)

         - op o = op o;;
         stdIn:4.1-4.12 Error: operator and operand don't agree
         [equality type required]

   (3) a means to write functions that are polymorphic over equality
       types:

         - fn x => x = x;;
         val it = fn : ''a -> bool

With `deriving' you get (1) and (2).  You can simulate (3) using
functors if you squint a bit.  In all cases you have to be explicit
about types, i.e. you have to write

    Eq.eq<int ref option> (Some (ref 3)) (Some (ref 3))

rather than (say)

    Eq.eq (Some (ref 3)) (Some (ref 3))

Specifying types is perhaps a bit of a nuisance, but to make up for it
you get a bit more flexibility: equality can be customized at
particular types.  For example, if you define an abstract type of
integer sets represented as unordered lists then you can give an
appropriate definition of equality rather than just inheriting the
definition for lists:

    module IntSet : sig
      type t
        deriving (Eq)

      val empty : t
      val add : int -> t -> t
      ...
    end =
    struct
      type t = int list
      module Eq =
      struct
        type a = t
        val eq l r = (List.sort compare l) = (List.sort compare r)
      end

      let empty = []
      let add item set = item :: set
      ...
    end

and your definition will be used whenever sets are compared

    module I = IntSet

    Eq.eq<I.t list> [I.add 1 (I.add 2 I.empty)]
                    [I.add 2 (I.add 1 I.empty)]
    => true

If you just want the "standard" definition of equality for your types
you can add `deriving (Eq)' to the definition and you'll be able to
use Eq.eq at that type.

    type colour = Red | Green | Blue
        deriving (Eq)

    Eq.eq<colour> Red Blue
    => false

    type a = A of int list | B of a
        deriving (Eq)

    Eq.eq<a> = B (A [1;2;3]) = B (A [1;2;3])
    => true

As the IntSet example suggests, `deriving' works by generating a
module definition for each derived function at each type.  For
example, for the `colour' type, you'll get a definition that looks
something like this:

    module Eq : Eq.Eq with type a = colour
    struct
      type a = colour
      let eq l r = match l, r with
        | Red, Red
        | Green, Green
        | Blue, Blue -> true
        | _ -> false
    end

which conforms to the signature for `Eq':

   module type Eq =
   sig
     type a
     val eq : a -> a -> bool
   end

More complicated types give rise to more complicated definitions: for
instance, a parameterized type will generate a functor whose argument
is a module that implements Eq for the type parameter.  Constructing
instances of `Eq' at instantiated types is then just a matter of
functor application: the definition at `int option ref' is obtained by
the fragment

   Eq_ref(Eq_option(Eq_ref))

There are strong parallels with Haskell's type classes in all this:
module signatures fulfill the role of classes, modules of instances,
and so on.  (The correspondence between modules and classes is
explored in various places in "the literature", e.g. Dreyer, Harper,
and Chakravarty's POPL 2007 paper, "Modular Type Classes").

Your question about error messages is a good one.  Syntactic
abstractions tend to be particularly leaky, so it shouldn't come as
too much of a surprise if the implementation is exposed occasionally
when you write the wrong thing.  Nonetheless, I think error messages
are generally fairly good.  If you misspell a type name then you get a
reasonable message

    Eq.eq<color> Red Blue
    =>
    File "color.ml", line 6, characters 2-14:
    Unbound type constructor color

An attempt to derive a class at a type that's not supported by
`deriving' results in a quite specific message.  For example,

    type 'a t = A | B of ('a * 'a) t
      deriving (Eq)
    =>
    File "nonreg.ml", line 3, characters 0-48 (end at line 4,
                                               character 15):
    The following types contain non-regular recursion:
       t
    deriving does not support non-regular types

or

    type t = int -> int deriving (Eq)

    File "fun.ml", line 2, characters 0-33:
    Eq cannot be derived for function types

Using an overloaded function at a type that doesn't match the annotation
results in just the error you'd expect:

    Eq.eq<int list> 0 1

    File "intlist.ml", line 4, characters 24-25:
    This expression has type int but is here used with type int list

If you forget to add `deriving Eq' to your type definition then the
error message is a little obscure when you come to use the type:

    type 'a t = A | B of 'a t

    Eq.eq<int t list>

    File "t.ml", line 8, characters 0-17:
    Unbound module Eq_t

I hope this helps a bit.  The documentation on the website gives more
examples.  There'll also be a paper out soon which should explain
things in more depth.

Jeremy.

Re: [Caml-list] ANN: pretty-printing, type-safe marshalling, dynamic typing for free.

[Jon Harrop]

On Thursday 19 July 2007 01:20:48 you wrote:
> Sure!  I suppose "SML-style equality" can be understood to include
> various things:
>
>    (1) an equality predicate that tests for physical equality at mutable
>        types and structural equality at immutable types.
>
>          SOME 3 = SOME 3
>          => true
>
>          SOME (ref 3) = SOME (ref 3)
>          => false

I forgot about this. I prefer OCaml's approach (physical and structural) 
actually. I use physical equality a lot as an optimization and I think that 
makes sense in an impure FPL.

>    (2) a compile-time error if you try to use equality at a type for
>        which it's not defined (an abstract or functional type)
>
>          - op o = op o;;
>          stdIn:4.1-4.12 Error: operator and operand don't agree
>          [equality type required]

This is what I was thinking of.

>    (3) a means to write functions that are polymorphic over equality
>        types:
>
>          - fn x => x = x;;
>          val it = fn : ''a -> bool

and this.

> With `deriving' you get (1) and (2).  You can simulate (3) using
> functors if you squint a bit.  In all cases you have to be explicit
> about types, i.e. you have to write
>
>     Eq.eq<int ref option> (Some (ref 3)) (Some (ref 3))
>
> rather than (say)
>
>     Eq.eq (Some (ref 3)) (Some (ref 3))
>
> Specifying types is perhaps a bit of a nuisance, but to make up for it
> you get a bit more flexibility: equality can be customized at
> particular types.

Ah, I did not realise you had to add type annotations everywhere by hand. I 
was rather hoping you could spot existing incorrect applications like:

  lazy 3 = lazy 3

This is simply because I want to apply it to an existing code base.

> I hope this helps a bit.  The documentation on the website gives more
> examples.  There'll also be a paper out soon which should explain
> things in more depth.

That's great, thank you. This is a beautiful piece of work but I think what 
I'm after requires a different approach.

I'm not quite sure how it could be done, short of altering the type system in 
the OCaml compiler. Maybe by adding a phantom type variable to every type, 
but I think that would require higher-order types:

  val ( = ) : [> `eq] 'a -> [> `eq] 'a -> bool

F# takes the Haskell approach of carrying an equality function in a dictionary 
with every type. That is a burden but it is probably a preferable solution 
overall (you just override the equality type when necessary). Some 
inconsistencies remain though, as you don't want to create a new list type 
every time you use a different comparison function, so Set assumes the 
equality from the dictionary whereas List.sort still uses an explicitly 
specified total order.

I can't believe how often I fall for this stupid bug. Even my first attempt at 
writing a GUI Sudoku solver for the OCaml Journal made the classic mistake of 
applying = to a pair of Maps. It would be very nice indeed if OCaml would 
catch such errors...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e