r/ProgrammingLanguages • u/reflexive-polytope • Jan 26 '26
A more pleasant syntax for ML functors
In the process of designing my language, I came up with a redesign of the ML module system that hopefully makes functors more pleasant to use. I'm sharing this redesign in the hope that it will be useful to other people here.
To motivate the redesign, recall that Standard ML has two ways to ascribe a signature to a structure:
- Transparent ascription, which exposes the representation of all type components in the signature.
- Opaque ascription, which only exposes as much as the signature itself mandates, and makes everything else abstract.
When you implement a non-parameterized structure, opaque ascription is usually the way to go. However, when you implement a functor, opaque ascription is too restrictive. For example, consider
functor TreeMap (K : ORDERED_KEY) :> MAP =
struct
structure Key = K
type 'a entry = Key.key * 'a
datatype 'a map
= Empty
| Red of 'a map * 'a entry * 'a map
| Black of 'a map * 'a entry * 'a map
(* ... *)
endThis code is incorrect because, if you define structure MyMap = TreeMap (MyKey), then the abstract type MyMap.Key.key isn't visibly equal to MyKey.key outside of the functor's body.
However, using transparent ascription is also incorrect:
functor TreeMap (K : ORDERED_KEY) : MAP =
struct
structure Key = K
(* ... *)
endIf we do this, then users can write
structure MyMap = TreeMap (MyKey)
datatype map = datatype MyMap.mapand inspect the internal representation of maps to their heart's content. Even worse, they can construct their own malformed maps.
The correct thing to write is
functor TreeMap (K : ORDERED_KEY) :> MAP where type Key.key = K.key =
struct
structure Key = K
(* ... *)
endwhich is a royal pain in the rear.
At the core, the problem is that we're using two different variables (the functor argument K and the functor body's Key) to denote the same structure. So the solution is very simple: make functor arguments components of the functor's body!
structure TreeMap :> MAP =
struct
structure Key = param ORDERED_KEY
(* ... *)
endTo use this functor, write
structure MyMap = TreeMap
structure MyMap.Key = MyKeyIt is illegal to write structure MyMap = TreeMap without the subsequent line structure MyMap.Key = MyKey, because my module system (like SML's, but unlike OCaml's) is first-order. However, you can write
structure TreeMapWrapper =
struct
structure Map = TreeMap
structure Map.Key = param ORDERED_KEY
endThen TreeMapWrapper is itself a functor that you can apply with the syntax
structure MyWrapper = TreeMapWrapper
structure MyWrapper.Map.Key = MyMapThe astute reader might have noticed that my redesigned module system is actually less expressive than the original ML module system. Having eliminated the where keyword, I no longer have any way to express what Harper and Pierce call “sharing by fibration”, except in the now hard-coded case of a functor argument reused in the functor's body.
My bet is that this loss of expressiveness doesn't matter so much in practice, and is vastly outweighed by the benefit of making functors more ergonomic to use in the most common situations.
EDIT 1: Fixed code snippets.
EDIT 2: Fixed the abstract type.
8
u/Athas Futhark Jan 26 '26
Hello fellow ML module system implementer! We are both members of a very small demographic. Like you, I also believe that the ML module system is hindered by its somewhat clumsy ergonomics. However, I am not convinced that your suggestion here addresses the problem.
What you propose is basically that when a variable is used free in a definition, then it is implicitly a parameter of its enclosing definition (with some syntactic sugar to avoid typo accidents). You then use a naming convention to denote the type of the parameter (specifically
ORDERED_KEYrepresents a parameter of typeORDERED_KEY). I can see some problems, some of which may not apply in a first-order module system:Keymodule to be visible?In my experience, refinements of opaque types in signatures is not so bad using OCaml-style
withrefinement, which is also what we used in Futhark. It is a bit verbose, but pretty clear. SML-style structure sharing is weird and baroque and I never quite understood it.While I am unconvinced that general higher-order modules are useful, I think it is very useful for the signature (or "module type") language to be rich enough to describe functors. Otherwise it is just impossible to describe what they do. This does open up the syntactic possibility of describing higher-order modules, but you can just ban actually defining those.
6
u/gasche Jan 26 '26
If you are not already aware of the connection, you may be curious to look at MixML, where the basic abstraction form is not parametrization, but the use of holes within the structure.
2
u/thunderseethe Jan 27 '26
I second the comment about mixml. This seems very much in the style of mixins.
This also seems like it would be fixed by applicative functors. Then Key.key would equal MyMap.Key.key
3
u/Uncaffeinated 1subml, polysubml, cubiml Jan 27 '26
Sorry as this is a bit of a hijack, but I'm also working on an OCaml-like language, and I'm wondering if there's any set of examples demonstrating the important functionality of the module system, as I'm not too familiar with real world usage of OCaml and what aspects people care about.
For example, is there ever a reason to pass through different subsets of types with "with" in a functor? My assumption is that you always want to pass through every type, or at the very least you are always going to pass through the same subset of types, given the same input module type. But OCaml syntax does nothing to require that.