Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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!

like image 271
Shon Avatar asked Sep 04 '16 04:09

Shon


1 Answers

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.

like image 97
Andreas Rossberg Avatar answered Oct 02 '22 12:10

Andreas Rossberg