'How to use higher order functors properly?' or 'How to have serious fun with funsigs?'

Question

Motivation

For the life of me, I cannot figure out how to use higher order functors in SML/NJ to any practical end.

According to the SML/NJ docs on the implementation's special features, it should be possible to specify one functor as an argument to another by use of the funsig keyword. Thus, given a signature

signature SIG = sig ... end

we should be able to specify a functor that will produce a module satisfying SIG, when applied to a structure satisfying some signature SIG'. E.g.,

funsig Fn (S:SIG') = SIG

With Fn declared in this way, we should then (be able to define another functor that takes this functor as an argument. I.e., we can define a module that is parameterized over another parameterized module, and presumably use the latter within the former; thus:

functor Fn' (functor Fn:SIG) =
struct
...
structure S' = Fn (S:SIG')
...
end

It all looks good in theory, but I can't figure out how to actually make use of this pattern.

Example Problems

Here are two instances where I've tried to use this pattern, only to find it impracticable:

First attempt

For my first attempt, just playing around, I tried to make a functor that would take a functor implementing an ordered set, and produce a module for dealing with sets of integers (not really useful, but it would let you parameterize sets of a given type over different set implementations). I can define the following structures, and they will compile (using Standard ML of New Jersey v110.7):

structure IntOrdKey : ORD_KEY
= struct
    type ord_key = int
    val compare = Int.compare
end

funsig SET_FN (KEY:ORD_KEY) = ORD_SET

functor IntSetFn (functor SetFn:SET_FN) =
struct
    structure Set = SetFn (IntOrdKey)
end

But when I actually try to apply IntSetFn to a functor that should satisfy the SET_FN funsig, it just doesn't parse:

- structure IntSet = IntSetFn (functor ListSetFn);
= ;
= ;;
stdIn:18.1-24.2 Error: syntax error: deleting  RPAREN SEMICOLON SEMICOLON
- structure IntSet = IntSetFn (functor BinarySetFn) ;
= ;
= ;
stdIn:19.1-26.2 Error: syntax error: deleting  RPAREN SEMICOLON SEMICOLON

Second attempt

My second attempt fails in two ways.

I have defined a structure of nested modules implementing polymorphic and monomorphic stacks (the source file, for the curious). To implement a monomorphic stack, you do

- structure IntStack = Collect.Stack.Mono (type elem = int);
structure IntStack : MONO_STACK?
- IntStack.push(1, IntStack.empty);
val it = - : IntStack.t

and so forth. It seems to work fine so far. Now, I want to define a module that parameterizes over this functor. So I have defined a funsig for the Collect.Stack.Mono functor (which can be seen in my repo). Then, following the pattern indicated above, I tried to define the following test module:

(* load my little utility library *)
CM.autoload("../../../utils/sources.cm");

functor T (functor StackFn:MONO_STACK) =
struct
    structure S = StackFn (type elem = int)
    val x = S.push (1, S.empty)
end

But this won't compile! I get a type error:

Error: operator and operand don't agree [overload conflict]
  operator domain: S.elem * S.t
  operand:         [int ty] * S.t
  in expression:
    S.push (1,S.empty)

uncaught exception Error
  raised at: ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27
             ../compiler/TopLevel/interact/evalloop.sml:44.55
             ../compiler/TopLevel/interact/evalloop.sml:292.17-292.20

Yet, inside functor T, I appear to be using the exact same instantiation pattern that works perfectly at the top level. What am I missing?

Unfortunately, that's not the end of my mishaps. Now, I remove the line causing the type error, leaving,

functor T (functor StackFn:MONO_STACK) =
struct
    structure S = StackFn (type elem = int)
end

This compiles fine:

[scanning ../../../utils/sources.cm]
val it = true : bool
[autoloading]
[autoloading done]
functor T(<param>: sig functor StackFn : <fctsig> end) :
         sig
           structure S : <sig>
         end
val it = () : unit

But I cannot actually instantiate the module! Apparently the path access syntax is unsupported for higher order functors?

- structure Test = T (functor Collect.Stack.Mono);
stdIn:43.36-43.43 Error: syntax error: deleting  DOT ID DOT

I am at a lost.

Questions

I have three related questions:

1. Is there a basic principle of higher-order functors in SML/NJ that I'm missing, or is it just an incompletely, awkwardly implemented feature of the language?
2. If the latter, where can I turn for more elegant and practicable higher order functors? (Hopefully an SML, but I'll dip into OCaml if necessary.)
3. Is there perhaps a different approach I should taking to achieve these kinds of effects that avoids higher order functors all together?

Many thanks in advance for any answers, hints, or followup questions!

Answer 1

Regarding your first attempt, the right syntax to apply your IntSetFn functor is:

structure IntSet = IntSetFn (functor SetFn = ListSetFn)

The same applies to your application of the Test functor in the second attempt:

structure Test = T (functor StackFn = Collect.Stack.Mono)

That should fix the syntax errors.

The type error you get when trying to use your stack structure S inside functor T has to do with the way you defined the MONO_STACK funsig:

funsig MONO_STACK (E:ELEM) = MONO_STACK

This just says that it returns a MONO_STACK structure, with a fully abstract elem type. It does not say that its elem type is gonna be the same as E.elem. According to that, I would able to pass in a functor like

functor F (E : ELEM) = struct type elem = unit ... end

to your functor T. Hence, inside T, the type system is not allowed to assume that type S.elem = int, and consequently you get a type error.

To fix this, you need to refine the MONO_STACK funsig as follows:

funsig MONO_STACK (E:ELEM) = MONO_STACK where type elem = E.elem

That should eliminate the type error.

[Edit]

As for your questions:

1. Higher-order functors are a little awkward syntactically in SML/NJ because it tries to stay 100% compatible with plain SML, which separates the namespace of functors from that for structures. If that wasn't the case then there wouldn't be the need for funsigs as a separate namespace either (and other syntactic baroqueness), and the language of signatures could simply be extended to include functor types.

2. Moscow ML is another SML dialect with a higher-order module extension that resolves the compatibility issue somewhat more elegantly (and is more expressive). There also was (now mostly dead) ALice ML, yet another SML dialect with higher-order functors that simply dropped the awkward namespace separation. OCaml of course did not have this constraint in the first place, so its higher-order modules are also more regular syntactically.

3. The approach seems fine.