[Caml-list] What is an applicative functor?

[Caml-list] What is an applicative functor?

[Dawid Toton]

What does it mean that a functor is applicative?
Is there any analogy between applicative functors in OCaml and the 
Applicative type class of Haskell?
Dawid

Re: [Caml-list] What is an applicative functor?

[Gerd Stolpmann]

Am Donnerstag, den 07.04.2011, 23:12 +0200 schrieb Dawid Toton:
> What does it mean that a functor is applicative?

Roughly: If you apply a functor twice with the same input modules, the
opaque types in the output remain compatible. For instance:

module S1 = Set.Make(String)
module S2 = Set.Make(String)

Now, S1.t and S2.t are type-compatible, although this type is opaque.
(E.g. you can do S1.empty = S2.empty.)

Compare this with:

module Make(X : sig end) = struct type t = Variant end
module M1 = Make(struct end)
module M2 = Make(struct end)

Now, M1.t and M2.t are incompatible - for nominal types like variants
the functors aren't applicative, and each instance is a thing of its
own:

# M1.Variant = M2.Variant;;
Error: This expression has type M2.t but an expression was expected of
type M1.t

Gerd


> Is there any analogy between applicative functors in OCaml and the 
> Applicative type class of Haskell?
> Dawid
> 


-- 
------------------------------------------------------------
Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

[Caml-list] Re: What is an applicative functor?

[Dawid Toton]

Thanks for the very quick answer.
Does it mean that I can render a module to be not applicative by adding 
a record type to it? This would break some existing code which relies on 
equality of some other types?

On 2011-04-07 23:49, Gerd Stolpmann wrote:
> Am Donnerstag, den 07.04.2011, 23:12 +0200 schrieb Dawid Toton:
>> What does it mean that a functor is applicative?
> Roughly: If you apply a functor twice with the same input modules, the
> opaque types in the output remain compatible. For instance:
>
> module S1 = Set.Make(String)
> module S2 = Set.Make(String)
>
> Now, S1.t and S2.t are type-compatible, although this type is opaque.
> (E.g. you can do S1.empty = S2.empty.)
But sometimes it doesn't work this way:

module Make2(X : sig end) = struct type s end
module M1 = Make2(struct end)
module M2 = Make2(struct end)
let g (a : M1.s) (b : M2.s) = a = b;;

Error: This expression has type M2.s but an expression was expected of 
type M1.s

> Compare this with:
>
> module Make(X : sig end) = struct type t = Variant end
> module M1 = Make(struct end)
> module M2 = Make(struct end)
>
> Now, M1.t and M2.t are incompatible - for nominal types like variants
> the functors aren't applicative, and each instance is a thing of its
> own:
>
> # M1.Variant = M2.Variant;;
> Error: This expression has type M2.t but an expression was expected of
> type M1.t
>
Honestly, I don't get it:

module Make(X : sig end) = struct type t = Variant end
module Empty = struct end
module M1 = Make(Empty)
module M2 = Make(Empty)
     ;;
M1.Variant = M2.Variant
     ;;

Toplevel responds with:

module Make : functor (X : sig  end) -> sig type t = Variant end
module Empty : sig  end
module M1 : sig type t = Make(Empty).t = Variant end
module M2 : sig type t = Make(Empty).t = Variant end
#   - : bool = true

So I get applicative functor with a nominal type?

>> Is there any analogy between applicative functors in OCaml and the
>> Applicative type class of Haskell?
I have some idea of it: we consider two types that play nicely together. 
I pass them through a functor. If the functor is applicative, the two 
resulting types also play nicely the same way as the original ones.
Dawid

Re: [Caml-list] Re: What is an applicative functor?

[Gerd Stolpmann]

Am Freitag, den 08.04.2011, 02:44 +0200 schrieb Dawid Toton:
> Thanks for the very quick answer.
> Does it mean that I can render a module to be not applicative by adding 
> a record type to it? This would break some existing code which relies on 
> equality of some other types?
> 
> On 2011-04-07 23:49, Gerd Stolpmann wrote:
> > Am Donnerstag, den 07.04.2011, 23:12 +0200 schrieb Dawid Toton:
> >> What does it mean that a functor is applicative?
> > Roughly: If you apply a functor twice with the same input modules, the
> > opaque types in the output remain compatible. For instance:
> >
> > module S1 = Set.Make(String)
> > module S2 = Set.Make(String)
> >
> > Now, S1.t and S2.t are type-compatible, although this type is opaque.
> > (E.g. you can do S1.empty = S2.empty.)
> But sometimes it doesn't work this way:
> 
> module Make2(X : sig end) = struct type s end
> module M1 = Make2(struct end)
> module M2 = Make2(struct end)
> let g (a : M1.s) (b : M2.s) = a = b;;
> 
> Error: This expression has type M2.s but an expression was expected of 
> type M1.s

Because the input module is not the same. It relies on module paths to
check identities.

> > Compare this with:
> >
> > module Make(X : sig end) = struct type t = Variant end
> > module M1 = Make(struct end)
> > module M2 = Make(struct end)

My error. This is of course not the same effect.

> >
> > Now, M1.t and M2.t are incompatible - for nominal types like variants
> > the functors aren't applicative, and each instance is a thing of its
> > own:
> >
> > # M1.Variant = M2.Variant;;
> > Error: This expression has type M2.t but an expression was expected of
> > type M1.t
> >
> Honestly, I don't get it:
> 
> module Make(X : sig end) = struct type t = Variant end
> module Empty = struct end
> module M1 = Make(Empty)
> module M2 = Make(Empty)
>      ;;
> M1.Variant = M2.Variant
>      ;;
> 
> Toplevel responds with:
> 
> module Make : functor (X : sig  end) -> sig type t = Variant end
> module Empty : sig  end
> module M1 : sig type t = Make(Empty).t = Variant end
> module M2 : sig type t = Make(Empty).t = Variant end
> #   - : bool = true
> 
> So I get applicative functor with a nominal type?

I think so. I remembered it the wrong way. There is a paper from XL
about this, see [5] in http://caml.inria.fr/about/papers.en.html.

Gerd



> 
> >> Is there any analogy between applicative functors in OCaml and the
> >> Applicative type class of Haskell?
> I have some idea of it: we consider two types that play nicely together. 
> I pass them through a functor. If the functor is applicative, the two 
> resulting types also play nicely the same way as the original ones.
> Dawid
> 


-- 
------------------------------------------------------------
Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] What is an applicative functor?

[Andreas Rossberg]

On Apr 7, 2011, at 23:49, Gerd Stolpmann wrote:
> module Make(X : sig end) = struct type t = Variant end
> module M1 = Make(struct end)
> module M2 = Make(struct end)
>
> Now, M1.t and M2.t are incompatible - for nominal types like variants
> the functors aren't applicative, and each instance is a thing of its
> own:

Nitpick: the Make functor is still applicative. All functors in OCaml  
are applicative. The fact that you get different results above is  
caused by the way you apply the functor, not by the way it is defined.

"Applicative" distinguishes functor semantics in OCaml from that in  
SML, where functors are "generative", i.e. you always get new types  
when you apply them.

Aside: In general, you really want to have both: functors with impure  
bodies better be generative, while functors with pure bodies should be  
applicative. The absence of generative functors in OCaml also is the  
reason that you cannot unpack a first-class module in a functor body  
(non-locally), because that is unsound with applicative semantics.

/Andreas

Re: [Caml-list] What is an applicative functor?

[Alain Frisch]

On 04/08/2011 08:50 AM, Andreas Rossberg wrote:
> Nitpick: the Make functor is still applicative. All functors in OCaml
> are applicative.

Nitpick²: except if you compile with -no-app-funct.

> Aside: In general, you really want to have both: functors with impure
> bodies better be generative, while functors with pure bodies should be
> applicative.

I'm not sure the benefits of applicative functors are worth the extra 
complexity they induce, especially if you want to support applicative 
functors in the same system as well. As far as I understand, applicative 
functors are useful primarily to give precise types to higher-order 
functors (which are rare enough).

It would be interested to see how much effort would be needed to adapt 
large code bases to compile with -no-app-funct (it probably amounts to 
giving a name to the result of a few functor applications).



Alain

Re: [Caml-list] What is an applicative functor?

[Jacques Garrigue]

On 2011/04/08, at 17:04, Alain Frisch wrote:

> On 04/08/2011 08:50 AM, Andreas Rossberg wrote:
>> Nitpick: the Make functor is still applicative. All functors in OCaml
>> are applicative.
> 
> Nitpick²: except if you compile with -no-app-funct.
> 
>> Aside: In general, you really want to have both: functors with impure
>> bodies better be generative, while functors with pure bodies should be
>> applicative.
> 
> I'm not sure the benefits of applicative functors are worth the extra complexity they induce, especially if you want to support applicative functors in the same system as well. As far as I understand, applicative functors are useful primarily to give precise types to higher-order functors (which are rare enough).
> 
> It would be interested to see how much effort would be needed to adapt large code bases to compile with -no-app-funct (it probably amounts to giving a name to the result of a few functor applications).

Applicative functors have other advantages, like the fact you can refer to a
type produced by a functor without having really applied it.

For instance think of the following functor definition

   module F(O : Set.OrderedType)(S : sig type t = Set.Make(O).t val union : t -> t -> t end) = ...

If you want to do the same thing with generative functors, I believe you have to
pass the result of Set.Make(O) around physically.
I do think this is a significant weakness.

Jacques Garrigue

Re: [Caml-list] What is an applicative functor?

[Jacques Garrigue]

On 2011/04/08, at 17:20, Jacques Garrigue wrote:

> On 2011/04/08, at 17:04, Alain Frisch wrote:
>> I'm not sure the benefits of applicative functors are worth the extra complexity they induce, especially if you want to support applicative functors in the same system as well. As far as I understand, applicative functors are useful primarily to give precise types to higher-order functors (which are rare enough).
>> 
>> It would be interested to see how much effort would be needed to adapt large code bases to compile with -no-app-funct (it probably amounts to giving a name to the result of a few functor applications).
> 
> Applicative functors have other advantages, like the fact you can refer to a
> type produced by a functor without having really applied it.
> 
> For instance think of the following functor definition
> 
>   module F(O : Set.OrderedType)(S : sig type t = Set.Make(O).t val union : t -> t -> t end) = ...
> 
> If you want to do the same thing with generative functors, I believe you have to
> pass the result of Set.Make(O) around physically.
> I do think this is a significant weakness.

Another example of that is my conversion-based version of the expression problem.

	http://www.math.nagoya-u.ac.jp/~garrigue/papers/mixmod.ml.txt

With -no-app-funct, most of the code is refused.
Note that -no-app-funct not only refuses paths of the form F(X).t, but also F(X).S (i.e. a functor returning a signature).
Actually, I wonder why it does refuse it syntactically, whereas potentially problematic signatures are very few.

Jacques Garrigue

Re: [Caml-list] What is an applicative functor?

[Alain Frisch]

On 04/08/2011 10:20 AM, Jacques Garrigue wrote:
> Applicative functors have other advantages, like the fact you can refer to a
> type produced by a functor without having really applied it.
>
> For instance think of the following functor definition
>
>     module F(O : Set.OrderedType)(S : sig type t = Set.Make(O).t val union : t ->  t ->  t end) = ...
>
> If you want to do the same thing with generative functors, I believe you have to
> pass the result of Set.Make(O) around physically.
> I do think this is a significant weakness.

I can imagine uses for:

module F(O : Set.OrderedType)(S : Set.S with type elt = O.t) =

but I don't see a real-life case where one would want functor F to know 
that the type S.t was really produced by applying Set.Make.  Do you have 
a specific example in mind?


Alain

Re: [Caml-list] What is an applicative functor?

[Jacques Garrigue]

On 2011/04/08, at 17:44, Alain Frisch wrote:
> On 04/08/2011 10:20 AM, Jacques Garrigue wrote:
>> Applicative functors have other advantages, like the fact you can refer to a
>> type produced by a functor without having really applied it.
>> 
>> For instance think of the following functor definition
>> 
>>    module F(O : Set.OrderedType)(S : sig type t = Set.Make(O).t val union : t ->  t ->  t end) = ...
>> 
>> If you want to do the same thing with generative functors, I believe you have to
>> pass the result of Set.Make(O) around physically.
>> I do think this is a significant weakness.
> 
> I can imagine uses for:
> 
> module F(O : Set.OrderedType)(S : Set.S with type elt = O.t) =
> 
> but I don't see a real-life case where one would want functor F to know that the type S.t was really produced by applying Set.Make.  Do you have a specific example in mind?

Well, union was maybe not the right name for a new function, but imagine that you want
sets with an extra operation. With generative functors, your have to have pass around the
full implementation of sets. With applicative functors you just need to pass the extra
operation, using the standard implementation of sets for other operations.
I don't know whether this example is very useful.
My other example using a functor returning a signature is maybe more important.
To some extent one can do the same thing using destructive substitution, but before
them there was no easy way to define signatures modularly using generative functors.

Jacques Garrigue

Re: [Caml-list] What is an applicative functor?

[Julien Signoles]

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

Hello,

2011/4/8 Alain Frisch <alain.frisch@lexifi.com>

> On 04/08/2011 10:20 AM, Jacques Garrigue wrote:
>
>> Applicative functors have other advantages, like the fact you can refer to
>> a
>> type produced by a functor without having really applied it.
>>
>> For instance think of the following functor definition
>>
>>    module F(O : Set.OrderedType)(S : sig type t = Set.Make(O).t val union
>> : t ->  t ->  t end) = ...
>>
>> If you want to do the same thing with generative functors, I believe you
>> have to
>> pass the result of Set.Make(O) around physically.
>> I do think this is a significant weakness.
>>
>
> I can imagine uses for:
>
> module F(O : Set.OrderedType)(S : Set.S with type elt = O.t) =
>
> but I don't see a real-life case where one would want functor F to know
> that the type S.t was really produced by applying Set.Make.  Do you have a
> specific example in mind?
>

I just try to compile Frama-C (http://frama-c.com) with the option
-no-app-funct in order to discover where/why we need applicative functors (I
knew that we use them somewhere).
I found three different patterns:

1) module M = F(G(X))

Without applicative functors, we get the error "The parameter cannot be
eliminated in the result type. Please bind the argument to a module
identifier.". That is easy to fix by introducing an intermediate module.

2) module F(X:...) = G(H(X))

Without applicative functors, we again get the error about parameter
elimination. But I see no workaround to eliminate it without changing the
signature of F. So IMHO that is a use case where applicative functors are
useful.

3) type t = F(X).t
    type u = { a: t }
These declarations are in a single .mli file without a corresponding .ml
file. G(X).t is an abstract type. Generators of values of type u are in a
module F while users of type u are others modules. Also we have to solve an
usual issue with mutual dependencies between F and its users. But the type u
is one of the most useful type in Frama-C. Thus standard solution to the
mutual dependencies issues which use polymorphism or functor are too heavy
here. That is the lightweight solution that we found.

To summarize:
- case 1 may be easily solved by writting 2 lines of code instead of 1
- case 2 and 3 may be circumvented for sure, but the solutions that I have
in mind are heavy

To conclude, there are only few use case where applicative functors are
useful in an application like Frama-C (where there are thousands of functor
applications). But IMHO that are enough cases to answer: yes applicative
functors are (sometimes) useful.

--
Julien

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

Re: [Caml-list] What is an applicative functor?

[Alain Frisch]

On 04/08/2011 01:25 PM, Julien Signoles wrote:
> 2) module F(X:...) = G(H(X))
>
> Without applicative functors, we again get the error about parameter
> elimination. But I see no workaround to eliminate it without changing
> the signature of F. So IMHO that is a use case where applicative
> functors are useful.

I'd be interested to see a full example for this case.


-- Alain

Re: [Caml-list] What is an applicative functor?

[Julien Signoles]

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

Hello Allain,

2011/4/8 Alain Frisch <alain.frisch@lexifi.com>

> On 04/08/2011 01:25 PM, Julien Signoles wrote:
>
>> 2) module F(X:...) = G(H(X))
>>
>> Without applicative functors, we again get the error about parameter
>> elimination. But I see no workaround to eliminate it without changing
>> the signature of F. So IMHO that is a use case where applicative
>> functors are useful.
>>
>
> I'd be interested to see a full example for this case.
>

Download sources of Frama-C here :
http://frama-c.com/download/frama-c-Carbon-20110201.tar.gz
The use case is in module State_builder :

src/project/state_builder.ml:
(* ... *)
module Caml_weak_hashtbl(Data: Datatype.S) =
Weak_hashtbl(Weak.Make(Data))(Data)
(* ... *)

Do you see any workaround to compile this code with -no-app-funct (and as
most as possible without changing API)?

--
Julien

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

Re: [Caml-list] What is an applicative functor?

[Julien Signoles]

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

2011/4/11 Julien Signoles <julien.signoles@gmail.com>

> Hello Allain,
>
> 2011/4/8 Alain Frisch <alain.frisch@lexifi.com>
>
>> On 04/08/2011 01:25 PM, Julien Signoles wrote:
>>
>>> 2) module F(X:...) = G(H(X))
>>>
>>> Without applicative functors, we again get the error about parameter
>>> elimination. But I see no workaround to eliminate it without changing
>>> the signature of F. So IMHO that is a use case where applicative
>>> functors are useful.
>>>
>>
>> I'd be interested to see a full example for this case.
>>
>
> Download sources of Frama-C here :
> http://frama-c.com/download/frama-c-Carbon-20110201.tar.gz
> The use case is in module State_builder :
>
> src/project/state_builder.ml:
> (* ... *)
> module Caml_weak_hashtbl(Data: Datatype.S) =
> Weak_hashtbl(Weak.Make(Data))(Data)
> (* ... *)
>
> Do you see any workaround to compile this code with -no-app-funct (and as
> most as possible without changing API)?
>

Looking this case in details, there is actually one workaround.

src/project/state_builder.ml:
(* ... *)
module Caml_weak_hashtbl(Data: Datatype.S)(Info: Info_with_size) = struct
  module W = Weak.Make(Data)
  include Weak_hashtbl(W)(Data)(Info)
end
(* ... *)

There is still the issue with diamond import in libraries like mentionned by
Andreas.

Sorry for the noise,
Julien

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

Re: [Caml-list] What is an applicative functor?

[rossberg]

> On 04/08/2011 10:20 AM, Jacques Garrigue wrote:
>> Applicative functors have other advantages, like the fact you can refer to
>> a
>> type produced by a functor without having really applied it.

I agree with Jacques. My primary argument for applicative functors is
diamond import in libraries. Assume you have a set functor in a library A
(e.g. the stdlib). Then there are two seperate libraries B and C, perhaps
from different sources. Both need to use sets. And you want to use B and C
and pass sets from one to the other.

Without applicative functors, there are 3 possibilities:

1. Both B and C instantiate the Set functor separately and export the result
-- then you have to convert between the incompatible set types all the time.

2. Both B and C functorize all their modules over a Set instance -- I think
it's obvious that this doesn't scale.

3. A mixture of (1) and (2).

Basically, this is the higher-order functor example in disguise, but dressed
up in a more "real world" fashion.

I believe avoiding this kind of road block is important for modularity. In
ML, we don't really make that much use of functors, mainly because they are
relatively heavyweight syntactically. But if you look at other languages,
e.g. Haskell or C++, then their libraries heavily rely on type classes, resp
templates, being "applicative" (with fairly bogus semantics in the latter
case). So if we claim that ML modules are superior, I think we need
applicative functors (besides generative ones).

/Andreas

Re: [Caml-list] What is an applicative functor?

[Julien Signoles]

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

2011/4/8 <rossberg@mpi-sws.org>

> > On 04/08/2011 10:20 AM, Jacques Garrigue wrote:
> >> Applicative functors have other advantages, like the fact you can refer
> to
> >> a
> >> type produced by a functor without having really applied it.
>
> I agree with Jacques. My primary argument for applicative functors is
> diamond import in libraries. Assume you have a set functor in a library A
> (e.g. the stdlib). Then there are two seperate libraries B and C, perhaps
> from different sources. Both need to use sets. And you want to use B and C
> and pass sets from one to the other.
>

That is exactly the third issue that we have in Frama-C and that I
previously mentioned in my answer to Alain.

--
Julien

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

Re: [Caml-list] What is an applicative functor?

[Lucas Dixon]

Hi,

On 08/04/2011 09:43, rossberg@mpi-sws.org wrote:
>> On 04/08/2011 10:20 AM, Jacques Garrigue wrote:
>>> Applicative functors have other advantages, like the fact you can refer to
>>> a
>>> type produced by a functor without having really applied it.
>
> I agree with Jacques. My primary argument for applicative functors is
> diamond import in libraries. Assume you have a set functor in a library A
> (e.g. the stdlib). Then there are two seperate libraries B and C, perhaps
> from different sources. Both need to use sets. And you want to use B and C
> and pass sets from one to the other.
>
> Without applicative functors, there are 3 possibilities:
>
> 1. Both B and C instantiate the Set functor separately and export the result
> -- then you have to convert between the incompatible set types all the time.
>
> 2. Both B and C functorize all their modules over a Set instance -- I think
> it's obvious that this doesn't scale.

What do you feel is the problem is with scaling this up? (maybe I'm 
being dumb, but I don't see what the issue is...)

I see that you have to pay some syntax for using functors that share a 
Set, and for later functors that build on B or C. You can make a 
sub-structure for the types you use, and then a bit of signature sharing 
magic, and it can be done fairly reasonably, I think.

It does seem to me that if your type is always going to be the same, 
then you can just define it first, and then parametrise what you do with 
it... or even just refer to it later...

A fun idea is to provide some syntax for implicit module 
parametrisation: have a union-style semantics for when overlapping 
implicit modules are imported. (just some lightweight syntax for the above).

But do you think there is an implementational problem with this 
functorisation in terms of scaling it up?

I've built a fairly large (for SML, it's 40k lines) of fairly heavily 
functorised code (approx 10 functors deep), essentially using this 
approach. It pushes the PolyML compiler a bit, and requires some 
slightly frustrating extra 'Sharing'-substructures, but otherwise works 
ok. The sharing substructures would disappear if we had a sensible 
signature language.

best,
lucas

-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.

Re: [Caml-list] What is an applicative functor?

[Andreas Rossberg]

On Apr 13, 2011, at 04:36, Lucas Dixon wrote:
>> I agree with Jacques. My primary argument for applicative functors is
>> diamond import in libraries. Assume you have a set functor in a  
>> library A
>> (e.g. the stdlib). Then there are two seperate libraries B and C,  
>> perhaps
>> from different sources. Both need to use sets. And you want to use  
>> B and C
>> and pass sets from one to the other.
>>
>> Without applicative functors, there are 3 possibilities:
>>
>> 1. Both B and C instantiate the Set functor separately and export  
>> the result
>> -- then you have to convert between the incompatible set types all  
>> the time.
>>
>> 2. Both B and C functorize all their modules over a Set instance --  
>> I think
>> it's obvious that this doesn't scale.
>
> What do you feel is the problem is with scaling this up? (maybe I'm  
> being dumb, but I don't see what the issue is...)

The problem is that you need to turn every module using a functor into  
a functor itself, and eventually end up piling up the entire  
transitive closure of your dependency graph in your functor parameters.

My experience with the early MLKit, which used this so-called "closed  
functor style", was that it is horrible. You need lots of functor  
parameters, lots of structure nesting and reexporting (the sizes of  
signatures can grow exponentially!), and plenty of subtle sharing  
constraints. And when some new code you're writing does not type  
check, you sometimes spend considerable time figuring out whether that  
was a "real" error or you just forgot some type sharing somewhere.

/Andreas

Re: [Caml-list] What is an applicative functor?

[Lucas Dixon]

On 13/04/2011 03:23, Andreas Rossberg wrote:
> On Apr 13, 2011, at 04:36, Lucas Dixon wrote:
>>> I agree with Jacques. My primary argument for applicative functors is
>>> diamond import in libraries. Assume you have a set functor in a
>>> library A
>>> (e.g. the stdlib). Then there are two seperate libraries B and C,
>>> perhaps
>>> from different sources. Both need to use sets. And you want to use B
>>> and C
>>> and pass sets from one to the other.
>>>
>>> Without applicative functors, there are 3 possibilities:
>>>
>>> 1. Both B and C instantiate the Set functor separately and export the
>>> result
>>> -- then you have to convert between the incompatible set types all
>>> the time.
>>>
>>> 2. Both B and C functorize all their modules over a Set instance -- I
>>> think
>>> it's obvious that this doesn't scale.
>>
>> What do you feel is the problem is with scaling this up? (maybe I'm
>> being dumb, but I don't see what the issue is...)
>
> The problem is that you need to turn every module using a functor into a
> functor itself, and eventually end up piling up the entire transitive
> closure of your dependency graph in your functor parameters.

yes, the concept of module for SML is really a functor and dependencies 
are explicit.

> My experience with the early MLKit, which used this so-called "closed
> functor style", was that it is horrible. You need lots of functor
> parameters, lots of structure nesting and reexporting (the sizes of
> signatures can grow exponentially!),  and plenty of subtle sharing
> constraints.

My feeling was that a little improvement on the syntax of signatures and 
sharing would deal with these issues fairly easily.

In terms of growing exponentially: that sounds like a serious problem; I 
would expect it to grow linearly on the number of dependencies. Or did 
you mean to use exponentially informally; as in gets too bug too quick?

> And when some new code you're writing does not type check,
> you sometimes spend considerable time figuring out whether that was a
> "real" error or you just forgot some type sharing somewhere.

I ended up pushing improvements to the type-error printing which helped 
a lot in PolyML. That combined with a finding a style that works out not 
too hideously: I create a sub-structure, typically called "Sharing" to 
hold just types that are relevant to a particular module. I can then use 
sharing on this substructure to share all types and save the others 
painful problem to remember to share every type.

For example, see basic_graph.ML in Quantomatic code (a graph rewriting 
tool in SML):
http://isaplanner.svn.sourceforge.net/viewvc/isaplanner/trunk/quantomatic/core/graph/basic_graph.ML?revision=3017&view=markup

So my basic feeling is still that this is an issue of finding a little 
syntax sugar and then the functorial style could work well... (with the 
sub-structure style I find it bearable, and can even enjoy using functors).

I guess the prerogative is to write that sugar and then try re-tasting 
the functorial soup.

best,
lucas

-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.

Re: [Caml-list] What is an applicative functor?

[Andreas Rossberg]

On Apr 15, 2011, at 05.08 h, Lucas Dixon wrote:
> On 13/04/2011 03:23, Andreas Rossberg wrote:
>> My experience with the early MLKit, which used this so-called "closed
>> functor style", was that it is horrible. You need lots of functor
>> parameters, lots of structure nesting and reexporting (the sizes of
>> signatures can grow exponentially!),  and plenty of subtle sharing
>> constraints.
>
> My feeling was that a little improvement on the syntax of signatures  
> and sharing would deal with these issues fairly easily.

I think this is very much a semantic problem, but I still would be  
interested to hear what improvements you have in mind.

> In terms of growing exponentially: that sounds like a serious  
> problem; I would expect it to grow linearly on the number of  
> dependencies. Or did you mean to use exponentially informally; as in  
> gets too bug too quick?

No, I meant it literally. One common idiom with functors is to re- 
export all parameter structures in the result, in order to have a self- 
contained result signature (and ease sharing later on). When you  
continue doing that up the entire dependency graph, then signatures  
can grow exponentially (in the depth of the dependency chain).

>> And when some new code you're writing does not type check,
>> you sometimes spend considerable time figuring out whether that was a
>> "real" error or you just forgot some type sharing somewhere.
>
> I ended up pushing improvements to the type-error printing which  
> helped a lot in PolyML. That combined with a finding a style that  
> works out not too hideously: I create a sub-structure, typically  
> called "Sharing" to hold just types that are relevant to a  
> particular module. I can then use sharing on this substructure to  
> share all types and save the others painful problem to remember to  
> share every type.

Sure, such idioms can help, but I don't think they solve the general  
problem. The more dependencies you have (e.g. in some more top-level  
module) the more unstructured their relations become, and it is  
difficult to organize them in a useful way.

In a way, parameterizing out all imports is a kind of manual closure  
conversion. You wouldn't want to be forced to doing that in the small,  
and I don't see why you should in the large. I feel that it also  
exposes too much of what should be considered implementation details.

> yes, the concept of module for SML is really a functor and  
> dependencies are explicit.

I guess the underlying question is what constitutes a module? I think  
you have to distinguish modules (as individual abstractions) from  
components/libraries/packages/whatever you like to call them. The  
latter can consist of many modules. In that spectrum, there is a place  
for both definite and indefinite references to other modules. You  
often want the the latter when you cross boundaries to other  
libraries. But the current functor mechanism is not an adequate means  
for expressing them, because it cannot be used at that level.

/Andreas

Re: [Caml-list] What is an applicative functor?

[Till Varoquaux]

On Fri, Apr 8, 2011 at 2:50 AM, Andreas Rossberg <rossberg@mpi-sws.org> wrote:
> On Apr 7, 2011, at 23:49, Gerd Stolpmann wrote:
>>
>> module Make(X : sig end) = struct type t = Variant end
>> module M1 = Make(struct end)
>> module M2 = Make(struct end)
>>
>> Now, M1.t and M2.t are incompatible - for nominal types like variants
>> the functors aren't applicative, and each instance is a thing of its
>> own:
>
> Nitpick: the Make functor is still applicative. All functors in OCaml are
> applicative. The fact that you get different results above is caused by the
> way you apply the functor, not by the way it is defined.
>
> "Applicative" distinguishes functor semantics in OCaml from that in SML,
> where functors are "generative", i.e. you always get new types when you
> apply them.
>
> Aside: In general, you really want to have both: functors with impure bodies
> better be generative, while functors with pure bodies should be applicative.
> The absence of generative functors in OCaml also is the reason that you
> cannot unpack a first-class module in a functor body (non-locally), because
> that is unsound with applicative semantics.
>
> /Andreas
I tend to consider using Impure functors as very poor coding hygiene..
I am sure there are compelling use cases but I've yet to come across
one. Providing safer types for impure functors does not seem
compelling enough to justify having several kind of functors.
I am not really sure I want applicative functors (based upon my
experience they are pretty hard to explain and rarely buy me anything)
but I balk at the idea of having both applicative and generative
functors..

Till

>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] What is an applicative functor?

[Alain Frisch]

On 04/08/2011 06:43 PM, Till Varoquaux wrote:
> I tend to consider using Impure functors as very poor coding hygiene..
> I am sure there are compelling use cases but I've yet to come across
> one.

A functor that implements hash-consing over some type could be one such 
example:

module HashCons(X : Hashtbl.HashedType) : sig
   type s
   val mk: X.t -> s
   val get: s -> X.t
end = struct
   type s = X.t
   module H = Hashtbl.Make(X)
   let tbl = H.create 16
   let mk x = try H.find tbl x with Not_found -> H.add tbl x x; x
   let get x = x
end

The intention is that values of type s are physical equal whenever they 
wrap equal values of type t. Unfortunately, this invariant can be broken 
because the functor is applicative. It would be good to be able to mark 
it as being generative instead.


Alain

Re: [Caml-list] What is an applicative functor?

[Andreas Rossberg]

On Apr 8, 2011, at 18:43, Till Varoquaux wrote:
> I tend to consider using Impure functors as very poor coding hygiene..
> I am sure there are compelling use cases but I've yet to come across
> one. Providing safer types for impure functors does not seem
> compelling enough to justify having several kind of functors.

Alain gave a good example. An even simpler one is a generator for a  
type of abstract names. There are a number of others, e.g. modules  
accessing external resources. Even more uses potentially arise with  
first-class modules, which can take the role of powerful (probably  
stateful) objects, with functors being their constructors.

> I am not really sure I want applicative functors (based upon my
> experience they are pretty hard to explain and rarely buy me anything)
> but I balk at the idea of having both applicative and generative
> functors..

It doesn't have to be complicated, especially not for the user.  
Admittedly, previous approaches providing both made it much more  
complicated than necessary, with duplicated syntax and all -- all you  
really need is to have the type system track whether a module is pure.  
We have a relatively elegant formulation of such a system in our F-ing  
Modules framework (I just have to find the time to write that paper).

I don't think that pure functors are incredibly hard to explain either  
-- after all, even C++ programmers find them natural. Of course,  
terminology like "applicative" or "generative" is less helpful then it  
has to be.

/Andreas

Re: [Caml-list] What is an applicative functor?

[Lauri Alanko]

On Fri, Apr 08, 2011 at 08:50:52AM +0200, Andreas Rossberg wrote:
> Aside: In general, you really want to have both: functors with
> impure bodies better be generative, while functors with pure bodies
> should be applicative. The absence of generative functors in OCaml
> also is the reason that you cannot unpack a first-class module in a
> functor body (non-locally), because that is unsound with applicative
> semantics.

I'm not sure if there really is an "absence": functions over
first-class modules _are_ generative functors for all practical
purposes. The only problem is that they only support type constraints
for first-order types (and even this can be circumvented with a bit of
magic).


Lauri

Re: [Caml-list] What is an applicative functor?

[Guillaume Yziquel]

Le Saturday 09 Apr 2011 à 00:23:39 (+0300), Lauri Alanko a écrit :
> On Fri, Apr 08, 2011 at 08:50:52AM +0200, Andreas Rossberg wrote:
> > Aside: In general, you really want to have both: functors with
> > impure bodies better be generative, while functors with pure bodies
> > should be applicative. The absence of generative functors in OCaml
> > also is the reason that you cannot unpack a first-class module in a
> > functor body (non-locally), because that is unsound with applicative
> > semantics.
> 
> I'm not sure if there really is an "absence": functions over
> first-class modules _are_ generative functors for all practical
> purposes. The only problem is that they only support type constraints
> for first-order types (and even this can be circumvented with a bit of
> magic).

I've very curious about the "with a bit of magic" part...

> Lauri

-- 
     Guillaume Yziquel

Re: [Caml-list] What is an applicative functor?

[Andreas Rossberg]

On Apr 8, 2011, at 23:23, Lauri Alanko wrote:
> I'm not sure if there really is an "absence": functions over
> first-class modules _are_ generative functors for all practical
> purposes. The only problem is that they only support type constraints
> for first-order types (and even this can be circumvented with a bit of
> magic).

Well, true, but IMO the first-order limitation is a severe one. Also,  
you cannot abstract over signatures that way, but admittedly, there  
are very few practical uses of that in current OCaml. Not sure what  
"magic" you have in mind, though.

In practical terms, however, I don't think it is convenient enough to  
keep wrapping and unwrapping modules into first-class values just to  
emulate generative functors. Especially since this involves cumbersome  
type annotations.

/Andreas

Re: [Caml-list] What is an applicative functor?

[Stefan Holdermans]

Dawid,

> What does it mean that a functor is applicative?
> Is there any analogy between applicative functors in OCaml and the Applicative type class of Haskell?

There is no analogy; functors in Caml are quite different from functors in Haskell. In Caml, a Functor is a higher-order module, i.e., a module that takes other modules as input in order to produce a proper module. In Haskell, Functor is a type class: essentially, the collection of types of kind * -> * that come with a structure preserving, covariant map operation. Applicative functors are members of this collection that fulfill some extra requirements.

Cheers,

  Stefan