Access the result of a function with dynamic parameters


#1

I want to allow consumers of a library to create “factory functions”. I have a module type like:

module type Factory  = sig
  type t
  val createItem : t
end

Then create a function createFactory like:

let createFactory (type a) fn =
  (let boundFunc = fn in (module
     struct type t = a
     let createItem = boundFunc end
) : (module Factory with type t = a))

And consumers can create factories like:

module IntFactory = (
  val createFactory (fun ~one -> fun ~two -> fun () -> one + two)
)

and then can be used like:

let test = IntFactory.createItem ~one:1 ~two:2 ()

I would like to find a generic way to access the results of these calls to createItem of the different factories and pack them in a new type. I’ve tried many different attempts, but I’m not sure this is possible without changing the factory signature to include a helper function that applies over the returned value of createItem to perform the wrapping.

Is it possible to add a wrap function to the Factory module type that takes the output produced by each createItem call and wraps it into, say, a variant type without changing the signature of the fn function passed to createFactory?


#2

For that I think it can be done using private extensible types. Here’s an example if I correctly understood what you want to achieve:


module Wrapper : sig
  type t = private ..
  module type Factory = sig
    type wrapped = t = private ..
    type t
    type wrapped += Wrap : t -> wrapped
    type creator
    val createItem : creator
    val wrap : t -> wrapped
  end with type wrapped := t
  type ('a, 'b) aux = (module Factory with type creator = 'a and type t = 'b)
  val createFactory : 'a -> (module Factory with type creator = 'a and type t = _)
end = struct
  type t = ..
  module type Factory = sig
    type wrapped = t = private ..
    type t
    type wrapped += Wrap : t -> wrapped
    type creator
    val createItem : creator
    val wrap : t -> wrapped
  end with type wrapped := t
  type ('a, 'b) aux = (module Factory with type creator = 'a and type t = 'b)
  let createFactory (type a b) (create : a) =
    (module struct
      type t += Wrap : b -> t
      type t = b
      type creator = a
      let createItem = create
      let wrap x = Wrap x
    end : Factory with type creator = a and type t = b)
end

module Int_factory = (val (Wrapper.createFactory (fun ~one ~two -> one + two) : (_, int) Wrapper.aux))

module String_factory =
  (val (Wrapper.createFactory (fun ~one ~two ~three -> one ^ two ^ three)  : (_, string) Wrapper.aux))

let vs =
  [Int_factory.(wrap @@ createItem ~one:1 ~two:2); String_factory.(wrap @@ createItem ~one:"1" ~two:"2" ~three:"3")]

let print =
  Format.(pp_print_list
            ~pp_sep:pp_print_newline
            (fun fmt ->
               function
               | Int_factory.Wrap i -> pp_print_int fmt i
               | String_factory.Wrap s -> pp_print_string fmt s
               | _                     -> assert false))

let () = Format.printf "%a\n" print vs


#3

Thanks a lot @schrodibear! This is definitely in the direction of what I want to achieve. I am not familiar with private extensible types, so I can just grasp at a rudimentary level the solution you posted, but I have a few related questions:

  • Is the nested Factory module needed because of the double abstraction? (the creator type a and the output from the creator t)
  • Why is the unification in type wrapped = t = private .. needed?
  • Is the type annotation : (_, string) Wrapper.aux) needed because of the Wrap GADT?
  • Would there be a way to remove this annotation?

Related to the last point, I wonder how much the solution could be simplified if the factories were all returning a simple type (e.g. ints) instead of having to support multiple types. Would that remove the need for some of the local abstract types?


#4

The Factory module type can be factored out e.g.

module type Factory = sig
  type wrapped = private ..
  type t
  type wrapped += Wrap : t -> wrapped
  type creator
  val createItem : creator
  val wrap : t -> wrapped
end
module Wrapper : sig
  type t = private ..
  module type Factory = Factory with type wrapped := t
  (* ... *)

But it’s not possible to integrate the substitution wrapped := t directly into the module type (module Factory with type creator = 'a and type t = 'b) like ... and type wrapped := t. Currently OCaml only permits equality constraints in first-class module types, not destructive substitutions (:=), so a intermediate module type is needed, or the wrapped type will remain in the modules produced by createFactory, although it shouldn’t be a problem if those types will all be equal to Wrapper.t.
Actually, you can work-around this restriction by using a functor:

module Factory (W : sig type t = private .. end)= struct
  module type S = sig
    type t
    type W.t += Wrap : t -> W.t
    type creator
    val createItem : creator
    val wrap : t -> W.t
  end
end

module Wrapper : sig
  module T : sig
    type t = private ..
  end
  type t = T.t
  type ('a, 'b) aux = (module Factory (T).S with type creator = 'a and type t = 'b)
  val createFactory : 'a -> ('a, _) aux
(* ... *)

If you mean the type manifest = private .., it’s just to allow to extend the type t using the alias wrapped (type wrapped += Wrap : t -> wrapped), and is only used because of the name collision (type t in the Factory vs. type t in the outer Wrapper module) to be able to express the type of the extension constructor Wrap. E.g. it’s not needed if you use a functor as above.

No, unfortunately this is the primary problem here: It’s not possible to capture the “return type of any function type” in general by using only unification. E.g. _ -> 'rtype only works for functions with one unlabelled argument, one:_ -> two:_ -> 'rtype – for functions with two labelled arguments etc. And a first-class higher-kinded type 'rtype 'creator also cannot be used as first, they are not supported in OCaml and, more importantly, the restricted version of first-class higher-kinded types that is decidable and used e.g. in Haskell, relies on kinding restriction and so the type constructor -> that has kind * -> * -> * still can not be unified with a constructor 'creator with kind * -> * (the unification of such type 'rtype 'creator with some other type (e.g. int -> int) is an example of second-order unification problem, which is undecidable in general, even here we can see several solutions: 'rtyp = int, 'r creator = int -> 'r and 'rtyp = int -> int, 'r creator = 'r). So it’s not possible to faithfully represent the desirable type of function createFactory without resorting to some workarounds. The typical workaround for OCaml is using module language, where the user provides the solution to the unification problem explicitly be defining parametric types, e.g.

module Create_factory (M : sig type t type 'a creator val creator : t creator end) : sig
  include module type of M
  val wrap : t -> W.t
end

but then the type annotation overhead is even bigger (not only the return type, but the type of the entire function has to be given). I suggested a work-around with the annotation on the return type only. It’s also possible to use continuation-passing style as a work-around e.g.:

module Wrapper : sig
  module T : sig
    type t = private ..
  end
  type t = T.t
  type ('a, 'b) aux = (module Factory (T).S with type creator = 'a and type t = 'b)
  val createFactory : (('r -> 'r) -> 'a) -> ('a, 'r) aux
end = struct
  module T = struct
    type t = ..
  end
  type t = T.t = ..
  type ('a, 'b) aux = (module Factory (T).S with type creator = 'a and type t = 'b)
  let createFactory (type a r) (create : (r -> r) -> a) : (a, r) aux =
    (module struct
      type t += Wrap : r -> t
      type t = r
      type creator = a
      let wrap x = Wrap x
      let createItem = create (fun x -> x)
    end)
end

module Int_factory = (val Wrapper.createFactory (fun k ~one ~two -> k @@ one + two))

module String_factory = (val Wrapper.createFactory (fun k ~one ~two ~three -> k @@ one ^ two ^ three))

Now there’s no need in type annotation, but the functions passed to createFactory have to use the continuation instead of directly returning the result.

So if you fix either the return type or the “shape” of the creator function (say, only one parameter that can be a tuple, triple, record etc. e.g. (1, 2)) , then no workaround for higher-kinded types is needed (and so no annotations on the user side). But I think you’ll still need locally abstract types to be able to include the type of function parameter into the resulting module e.g. type param = a, where createItem has type a -> int (when defining the createFactory function).


#5

Thanks a lot for taking the time to write such a detailed explanation @schrodibear, I really appreciate it.

This is probably the part that is more confusing to me about the way OCaml allows to unify signatures of whole functions that include labelled arguments just fine, but from the moment one tries to locally abstract over a part of that signature, it doesn’t work.

This code won’t compile:

module type Factory = sig
  type t
  val createItem : t -> int
end

let createFactory (type a) (create: a -> int) =
  (module struct
    type t = a
    let createItem = create
  end : Factory with type t = a)
  
module Int_factory = (val (createFactory (fun ~one ~two -> one + two)))

I created an online example in https://sketch.sh/s/asBzVcz55qjdjpfSn3v2qH/ that shows this interactively.

How is OCaml able to unify the whole signature of the function? (which still includes labelled arguments). And why can’t it unify a subset of the signature?


#6

@schrodibear I am realizing now that the problem I just mentioned above might have nothing to do with your explanation about the problem of typing the “return type of any function type”. I am still wrapping my head around these concepts so I might be mixing some of the different parts of the problem, apologies for the confusion :sweat_smile:


#7

Maybe the associativity of the -> type constructor makes it confusing: It associates to the right and so 'a -> 'b -> 'c -> int is treated as ('a, ('b, ('c, int) arrow) arrow) arrow. So if we unify this with, say, 'd -> 'e, which is ('d, 'e) arrow we get the solution 'd = 'a and 'e = ('b, ('c, int) arrow) arrow = 'b -> 'c -> int. So we can only unify with the “postfix” of the signature. If function type constructors were treated differently, it would be possible to unify e.g. with the return type, but the right-associativity allows partial applications to be treated as normal functions and functions returning functions to be treated as functions with many arguments.


#8

@schrodibear Thanks! The implications of associativity make a lot of sense.

I find the continuation-passing style solution very interesting. Ultimately, I built upon this approach to create the API I was looking for. By leveraging the continuation passing style approach, I managed to avoid using functors, and be able to unify the types the way I needed just by using first class modules. In case you or others are curious, the solution is in https://sketch.sh/s/3SQyO9p2IXgm0mEBPNiKXW/ (originally written in Reason, but can be switched from the top bar to OCaml).

@schrodibear thanks again for all your help, I have learnt a ton from your explanations and examples!