[Caml-list] "map"-ing parameterized class types

[Caml-list] "map"-ing parameterized class types

[Spiros Eliopoulos]

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

Hey List,

I'm trying to create a "container" class[0] that can store a value of type
'a, and transform that value to another value of type 'b. I'm trying to do
this by including a "map" method in the container that applies a function
to the value and returns a new instance of container with the transformed
value. Despite the annotations, the types aren't working out as I expected:

  class ['a] container (v:'a) = object
    method map (f:'a -> 'b) : 'b container = new container (f v)
  end;;
  (* class ['a] container : 'a -> object method map : ('a -> 'a) -> 'a
container end  *)

I gather I'm either doing something wrong, or it's not possible. I suppose
my question, which one is it? and if I'm doing something wrong, some
guidance would be appreciated. Thanks!

-Spiros E.

[0]: Note that this is a minimal, contrived example of my actual problem.
The actual problem came up while writing js_of_ocaml bindings.

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

Re: [Caml-list] "map"-ing parameterized class types

[Jeremy Yallop]

On 19 October 2015 at 17:58, Spiros Eliopoulos <seliopou@gmail.com> wrote:
> I'm trying to create a "container" class[0] that can store a value of type
> 'a, and transform that value to another value of type 'b. I'm trying to do
> this by including a "map" method in the container that applies a function to
> the value and returns a new instance of container with the transformed
> value. Despite the annotations, the types aren't working out as I expected:
>
>   class ['a] container (v:'a) = object
>     method map (f:'a -> 'b) : 'b container = new container (f v)
>   end;;
>   (* class ['a] container : 'a -> object method map : ('a -> 'a) -> 'a
> container end  *)
>
> I gather I'm either doing something wrong, or it's not possible. I suppose
> my question, which one is it?

It's not exactly possible, but there are workarounds.

The reason the types don't work out as you expect is that structural
types (objects, classes, polymorphic variants) in OCaml are required
to be "regular".  A parameterised type t is regular if every
occurrence of t within its own definition is instantiated with the
parameters.  For example, the following type (t1) is regular:

   # type ('a, 'b) t1 = [`A of ('a, 'b) t1];;
   type ('a, 'b) t1 = [ `A of ('a, 'b) t1 ]
     type ('a, 'b) t1 = [`A of ('a, 'b) t1]

but this one (t2) isn't, because the order of parameters is reversed

   # type ('a, 'b) t2 = [`A of ('b, 'a) t2];;
   Characters 5-38:
     type ('a, 'b) t2 = [`A of ('b, 'a) t2];;
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   Error: In the definition of t2, type ('b, 'a) t2 should be ('a, 'b) t2
     type ('a, 'b) t2 = [`A of ('b, 'a) t2]

and this one (t3) isn't, either, because the parameters are
instantiated with concrete types

   # type ('a, 'b) t3 = [`A of (int, string) t3];;
   Characters 5-43:
     type ('a, 'b) t3 = [`A of (int, string) t3];;
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   Error: In the definition of t3, type (int, string) t3 should be ('a, 'b) t3

As the output shows, OCaml rejects the non-regular definitions for t2
and t3.  Your example code also attempts to define a non-regular type,
but since the type variable 'b is available for unification, OCaml
doesn't need to reject the definition altogether.  Instead, 'b is
unified with the class parameter 'a to produce a regular type which is
acceptable to OCaml (but which doesn't do what you want).

How might we side-step the regularity constraint?  One approach is to
arrange things so that the recursion passes through a non-structural
type, such as a variant or record.  In an imaginary extension to OCaml
with support for groups of mutually-recursive types and classes we
could write something like this:

   class ['a] container (v:'a) = object
     method map : 'b. ('a -> 'b) -> 'b container_aux =
       fun f -> { container = new container (f v) }
   end
   and 'a container_aux = { container: 'a container }

In today's OCaml we can achieve a similar effect by routing all the
recursive references through a recursive module, albeit at a rather
heavy syntactic cost:

   module rec R:
   sig
     class ['a] container : 'a ->
       object
         method map : 'b. ('a -> 'b) -> 'b R.container_aux
       end
     type 'a container_aux = { container: 'a container }
   end =
   struct
     class ['a] container (v:'a) = object
       method map : 'b. ('a -> 'b) -> 'b R.container_aux =
         fun f -> { R.container = new R.container (f v) }
     end
     type 'a container_aux = { container: 'a container }
   end

which at least achieves the desired effect:

   # let c = new R.container 3;;
   val c : int R.container = <obj>
   # (c#map string_of_int).R.container;;
   - : string R.container = <obj>

Re: [Caml-list] "map"-ing parameterized class types

[Spiros Eliopoulos]

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

Thank, Jeremy, for the great explanation and possible work around.
Unfortunately for me, the workaround won't be possible to use for the
js_of_ocaml use case I have in mind. At least not without sprinkling
Obj.magic everywhere, which is what I'm trying to avoid.

Based on your workaround, I thought I might be able to create my own
workaround with code that looked something like this:

  module rec R : sig
    class type ['a] container1 = object
      method map : ('a -> 'b) -> 'b R.container2
    end
    class type ['a] container2 = object
      method op : 'a R.container1
    end
  end = struct
    ...
  end

But of course the type system complained that:

  Error: In the definition of R.container2, type
       'b R.container1
       should be
       'a R.container1

I thought this might be for a different than the one you mentioned, but
upon further reflection and a single unrolling of the types, it seems to be
the regular type constraint that's causing this error as well.

Well, back to drawing board. Thanks again.

On Mon, Oct 19, 2015 at 2:14 PM, Jeremy Yallop <yallop@gmail.com> wrote:

> On 19 October 2015 at 17:58, Spiros Eliopoulos <seliopou@gmail.com> wrote:
> > I'm trying to create a "container" class[0] that can store a value of
> type
> > 'a, and transform that value to another value of type 'b. I'm trying to
> do
> > this by including a "map" method in the container that applies a
> function to
> > the value and returns a new instance of container with the transformed
> > value. Despite the annotations, the types aren't working out as I
> expected:
> >
> >   class ['a] container (v:'a) = object
> >     method map (f:'a -> 'b) : 'b container = new container (f v)
> >   end;;
> >   (* class ['a] container : 'a -> object method map : ('a -> 'a) -> 'a
> > container end  *)
> >
> > I gather I'm either doing something wrong, or it's not possible. I
> suppose
> > my question, which one is it?
>
> It's not exactly possible, but there are workarounds.
>
> The reason the types don't work out as you expect is that structural
> types (objects, classes, polymorphic variants) in OCaml are required
> to be "regular".  A parameterised type t is regular if every
> occurrence of t within its own definition is instantiated with the
> parameters.  For example, the following type (t1) is regular:
>
>    # type ('a, 'b) t1 = [`A of ('a, 'b) t1];;
>    type ('a, 'b) t1 = [ `A of ('a, 'b) t1 ]
>      type ('a, 'b) t1 = [`A of ('a, 'b) t1]
>
> but this one (t2) isn't, because the order of parameters is reversed
>
>    # type ('a, 'b) t2 = [`A of ('b, 'a) t2];;
>    Characters 5-38:
>      type ('a, 'b) t2 = [`A of ('b, 'a) t2];;
>           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>    Error: In the definition of t2, type ('b, 'a) t2 should be ('a, 'b) t2
>      type ('a, 'b) t2 = [`A of ('b, 'a) t2]
>
> and this one (t3) isn't, either, because the parameters are
> instantiated with concrete types
>
>    # type ('a, 'b) t3 = [`A of (int, string) t3];;
>    Characters 5-43:
>      type ('a, 'b) t3 = [`A of (int, string) t3];;
>           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>    Error: In the definition of t3, type (int, string) t3 should be ('a,
> 'b) t3
>
> As the output shows, OCaml rejects the non-regular definitions for t2
> and t3.  Your example code also attempts to define a non-regular type,
> but since the type variable 'b is available for unification, OCaml
> doesn't need to reject the definition altogether.  Instead, 'b is
> unified with the class parameter 'a to produce a regular type which is
> acceptable to OCaml (but which doesn't do what you want).
>
> How might we side-step the regularity constraint?  One approach is to
> arrange things so that the recursion passes through a non-structural
> type, such as a variant or record.  In an imaginary extension to OCaml
> with support for groups of mutually-recursive types and classes we
> could write something like this:
>
>    class ['a] container (v:'a) = object
>      method map : 'b. ('a -> 'b) -> 'b container_aux =
>        fun f -> { container = new container (f v) }
>    end
>    and 'a container_aux = { container: 'a container }
>
> In today's OCaml we can achieve a similar effect by routing all the
> recursive references through a recursive module, albeit at a rather
> heavy syntactic cost:
>
>    module rec R:
>    sig
>      class ['a] container : 'a ->
>        object
>          method map : 'b. ('a -> 'b) -> 'b R.container_aux
>        end
>      type 'a container_aux = { container: 'a container }
>    end =
>    struct
>      class ['a] container (v:'a) = object
>        method map : 'b. ('a -> 'b) -> 'b R.container_aux =
>          fun f -> { R.container = new R.container (f v) }
>      end
>      type 'a container_aux = { container: 'a container }
>    end
>
> which at least achieves the desired effect:
>
>    # let c = new R.container 3;;
>    val c : int R.container = <obj>
>    # (c#map string_of_int).R.container;;
>    - : string R.container = <obj>
>

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

Re: [Caml-list] "map"-ing parameterized class types

[Mikhail Mandrykin]

On Monday, October 19, 2015 04:15:54 PM Spiros Eliopoulos wrote:
> Thank, Jeremy, for the great explanation and possible work around.
> Unfortunately for me, the workaround won't be possible to use for the
> js_of_ocaml use case I have in mind. At least not without sprinkling
> Obj.magic everywhere, which is what I'm trying to avoid.
> 
> Based on your workaround, I thought I might be able to create my own
> workaround with code that looked something like this:
> 
>   module rec R : sig
>     class type ['a] container1 = object
>       method map : ('a -> 'b) -> 'b R.container2
>     end
>     class type ['a] container2 = object
>       method op : 'a R.container1
>     end
>   end = struct
>     ...
>   end
> 
> But of course the type system complained that:
> 
>   Error: In the definition of R.container2, type
>        'b R.container1
>        should be
>        'a R.container1
> 
> I thought this might be for a different than the one you mentioned, but
> upon further reflection and a single unrolling of the types, it seems to be
> the regular type constraint that's causing this error as well.

It seems this is essentially not the workaround that was pointed out, as the 
suggestion was:
>> One approach is to
> > arrange things so that the recursion passes through a *non-structural
> > type*, such as a variant or record. 
And an object type 'a container2 is a structural type. As far as I understand, 
the semantics for type-checking of structural type abbreviations is the same 
as if all those abbreviations were expanded. So introducing a new class ['a] 
container2 doesn't help, because its corresponding object type ends up being 
expanded while type-checking ['a] container1 anyway and leads to essentially  
the same error. The regularity restriction seems to also arise from the same 
expansion semantics where we would need to infinitely expand the structural 
type abbreviation while checking itself and therefore would be unable to write 
recursive structural types altogether, but the issue is addressed by replacing 
the whole abbreviated type application with a type variable e.g. 'a container1 
= 'self and using this 'self in place of all regular self-references. Thus the 
type can remain structural (it's still possible to write it down without 
naming it)  despite the self-references e.g. ( < get : 'a; map : 'self > as 
'self). For irregular self-references this doesn't work (if 'a container = 
'self then what's 'b container or how to designate it to avoid infinite 
expansion?).

Just in case an another possible work-around would be to use an abstract type 
instead of a concrete nominal type as a proxy. This can be a little bit more 
suitable as an abstract type can be later bound to the same structural type 
and wrapping/unwrapping would become identity in the implementation. This is 
more heavyweight, though, e.g:

module type S = sig
  type 'a c'
  val new_c : 'a -> 'a c'
end

module rec F' :
  functor (M : S) -> sig
    class ['a] c : 'a -> object
        method get : 'a
        method map : 'b. ('a -> 'b) -> 'b M.c'
      end
  end =
  functor (M : S) -> struct
    class ['a] c (a : 'a) = object
      method get = a
      method map : 'b. (_ -> 'b) -> 'b M.c' = fun f -> M.new_c (f a)
    end
  end

module rec F : sig
  type 'a c'
  class ['a] c : 'a -> object
      method get : 'a
      method map : 'b. ('a -> 'b) -> 'b F.c'
    end
  val new_c : 'a -> 'a F.c'
  val self_cast : 'a c' -> 'a c
end = struct
  module F' = F'(F)
  class ['a] c = ['a] F'.c
  type 'a c' = 'a c
  let new_c a = new F.c a
  let self_cast (x : 'a c') = (x : 'a c)
end

let () =
  let c1 = new F.c 1 in
  Printf.eprintf "%d\n" c1#get;
  let c2 = F.self_cast @@ c1#map (string_of_int) in
  Printf.eprintf "%s\n" c2#get

Here F.self_cast is actually an identity function an is only used to help 
type-checking.

-- 
Mikhail Mandrykin
Linux Verification Center, ISPRAS
web: http://linuxtesting.org
e-mail: mandrykin@ispras.ru

Re: [Caml-list] "map"-ing parameterized class types

[Glen Mével]

Le 20/10/2015 13:57, Mikhail Mandrykin a écrit :
> Just in case an another possible work-around would be to use an abstract type 
> instead of a concrete nominal type as a proxy. This can be a little bit more 
> suitable as an abstract type can be later bound to the same structural type 
> and wrapping/unwrapping would become identity in the implementation. This is 
> more heavyweight, though, e.g:
> 
> module type S = sig
>   type 'a c'
>   val new_c : 'a -> 'a c'
> end
> 
> module rec F' :
>   functor (M : S) -> sig
>     class ['a] c : 'a -> object
>         method get : 'a
>         method map : 'b. ('a -> 'b) -> 'b M.c'
>       end
>   end =
>   functor (M : S) -> struct
>     class ['a] c (a : 'a) = object
>       method get = a
>       method map : 'b. (_ -> 'b) -> 'b M.c' = fun f -> M.new_c (f a)
>     end
>   end
> 
> module rec F : sig
>   type 'a c'
>   class ['a] c : 'a -> object
>       method get : 'a
>       method map : 'b. ('a -> 'b) -> 'b F.c'
>     end
>   val new_c : 'a -> 'a F.c'
>   val self_cast : 'a c' -> 'a c
> end = struct
>   module F' = F'(F)
>   class ['a] c = ['a] F'.c
>   type 'a c' = 'a c
>   let new_c a = new F.c a
>   let self_cast (x : 'a c') = (x : 'a c)
> end

nice solution! just saying, it can be simplified, with no need for functor:

    module rec F :
    sig
      class ['a] c : 'a -> object
        method get : 'a
        method map : 'b. ('a -> 'b) -> 'b F.t
      end
      type 'a t
      val make : 'a -> 'a t
      val cast : 'a t -> 'a c
    end =
    struct
      class ['a] c x = object
        method get = x
        method map : 'b. ('a -> 'b) -> 'b F.t = fun f -> F.make (f x)
      end
      type 'a t = 'a c
      let make x = new c x
      let cast x = x
    end

-- 
Glen Mével

Re: [Caml-list] "map"-ing parameterized class types

[Oleg]

The question was about creating a class of the following type

>      class type ['a] container : 'a ->
>        object
>          method map : 'b. ('a -> 'b) -> 'b container
>        end

with a mapping method that makes a container of a different
type. Jeremy Yallop has explained very well the class of exactly such
type is not possible. The following is perhaps the simplest workaround
requiring neither modules nor other higher-class artillery. It should
have been possible even in OCaml 3.10 or earlier.

The idea was inspired by some high-falutin' Math, namely, left Kan
extension from Category Theory. I actually don't know CT but I think I
got the gist of the left Kan extension: rather than execute an an
operation, just collect all the needed arguments and declare the
operation performed. The recent paper on Freer monads (Haskell
Symposium 2015) used two instances of this new kind of laziness.

Here is the whole solution

    type 'a cont_proxy = P of 'a

    class ['a] container (x : 'a) = object
      method get_x = x
      method map' : 'b. ('a -> 'b) -> 'b cont_proxy = fun f ->
        P (f x)
    end

The class container has one argument, which is the value needed to
construct the container. The data type cont_proxy contains all the
information needed to construct the container, but not the container
itself (for one, the container type is not yet defined when we
declared P). The method map' doesn't actually construct anything; it
merely returns the data needed for the construction.

The map itself is then easy to define:

    let map : ('a -> 'b) -> ('a container -> 'b container) = fun f c ->
      match c#map' f with
        P x -> new container x

let c = new container 3
    val c : int container = <obj>
let _ = c#get_x
    - : int = 3
let c' = map string_of_int c
    val c' : string container = <obj>
let _ = c'#get_x
    - : string = "3"

Re: [Caml-list] "map"-ing parameterized class types

[Jacques Garrigue]

Hi Oleg,

The externalizing solution has been known since the beginning of
OCaml, but it is nice to know that it has such a cute name…

Jacques

On 2015/10/23 00:04, Oleg wrote:
> 
> The question was about creating a class of the following type
> 
>>     class type ['a] container : 'a ->
>>       object
>>         method map : 'b. ('a -> 'b) -> 'b container
>>       end
> 
> with a mapping method that makes a container of a different
> type. Jeremy Yallop has explained very well the class of exactly such
> type is not possible. The following is perhaps the simplest workaround
> requiring neither modules nor other higher-class artillery. It should
> have been possible even in OCaml 3.10 or earlier.
> 
> The idea was inspired by some high-falutin' Math, namely, left Kan
> extension from Category Theory. I actually don't know CT but I think I
> got the gist of the left Kan extension: rather than execute an an
> operation, just collect all the needed arguments and declare the
> operation performed. The recent paper on Freer monads (Haskell
> Symposium 2015) used two instances of this new kind of laziness.
> 
> Here is the whole solution
> 
>    type 'a cont_proxy = P of 'a
> 
>    class ['a] container (x : 'a) = object
>      method get_x = x
>      method map' : 'b. ('a -> 'b) -> 'b cont_proxy = fun f ->
>        P (f x)
>    end
> 
> The class container has one argument, which is the value needed to
> construct the container. The data type cont_proxy contains all the
> information needed to construct the container, but not the container
> itself (for one, the container type is not yet defined when we
> declared P). The method map' doesn't actually construct anything; it
> merely returns the data needed for the construction.
> 
> The map itself is then easy to define:
> 
>    let map : ('a -> 'b) -> ('a container -> 'b container) = fun f c ->
>      match c#map' f with
>        P x -> new container x
> 
> let c = new container 3
>    val c : int container = <obj>
> let _ = c#get_x
>    - : int = 3
> let c' = map string_of_int c
>    val c' : string container = <obj>
> let _ = c'#get_x
>    - : string = "3"