By Eunice Chen and Brandon Wu, December 2020
Sometimes, we are interested in developing large projects. Large codebases are oftentimes convoluted and impenetrable to outside scrutiny, being solely understandable by the original author. It is thus in our best interest to develop good coding practices - consisting of clean, commented code that communicates its cause clearly, as well as a modular structure that allows understanding what each part of the codebase should do. For instance, we would not want to simply dump all of our code into a single file with thousands of lines - instead, what we oftentimes may do is decompose it into constituent parts, each part of which has a certain purpose, such as parsing, maintaining certain data structures, or other purposes, depending on the use case.
In this chapter, we will discuss SML's module system, which allows for safe, powerful abstraction of code. We will discuss the power that data abstraction grants us as code designers, as well as the clean ways that we can compose them in order to encapsulate common design patterns.
Oftentimes as programmers, we are tasked with writing code that matches a specification. This specification can vary in rigor and mathematical formality, but the general idea is that oftentimes it exists. When we are asked to write a function to compute the first \( n \) Fibonacci numbers, it does not necessarily matter how we go about implementing this function, so long as it exhibits the proper input-output behavior. In other words, we would like it so that all functions implementing a given specification have extensionally equivalent behavior to what we should expect them to do.
NOTE: Sometimes, there are constraints beyond simply being the same "mathematical function" - that is, defining the same outputs on the same inputs. Sometimes we are asked for the implementation of a function, running in only less than \( O(n^2) \) asymptotic time. Even in cases like these, however, there are always still superficial differences that our implementation allows for - for instance, when writing the Fibonacci function, it is unlikely that it should matter whether we calculate the value of \( f(n-1) \) or \( f(n-2) \) first.
This should not be an unfamiliar idea - this is exactly the concept of referential transparency, which says that we can swap "equals-for-equals" whenever discussion the equality of expressions. Under the eyes of the language, equal expressions are just that - equal, and there is no need to disambiguate them.
This idea, however, is rather limited in scope. What if we would like to deal with a function that depends upon another function? Then we cannot freely make the swap between functions, and substitute a function into a context where its dependencies do not exist. Indeed, we cannot perform such a substitution at all in the case where a function is in any way defined beyond its own function body itself.
We don't want to outlaw such practices, however - we simply need to make our abstraction boundaries more explicit. When we have a package or otherwise standalone bundle of software, we should be able to use all of its components that are muutally dependent on each other - not just make our distinctions at the function level. We will do so using SML's module system.
SML takes both the ideas of the specification and the implementation and provides a way of codifying both within the language itself. Of course, it is rather difficult to say "implement the list reversal function in \( O(n) \) asymptotic time in \( n \), the length of the list" in code, so SML will only deal with specifications at the type-level. That is, within SML itself, a specification for a function is simply a type for that function.
The term for a specification in SML is called a signature. Consider the following specification and implementation of a package for modular arithmetic. Note that the comments are optional.
signature MOD_ARITH = sig (* ENSURES: mod_add n x y = (x + y) mod n *) val mod_add : int -> int -> int -> int (* ENSURES: mod_sub n x y = (x - y) mod n *) val mod_sub : int -> int -> int -> int (* ENSURES: mod_times n x y = (x * y) mod n *) val mod_times : int -> int -> int -> int end
This signature defines three functions, all of which have type
int -> int -> int -> int, which takes in the modulus of the operation, as well as the two
operands to the operation to be performed. While we would like an implementation
of this signature to also display the behavior outlined in the comments,
realistically there is no way to verify that this is true (why?), so the best that we
can do is ensure that an implementation provides functions with the correct
Note also that this syntax is slightly different than that you have seen before
- we use
valas if we were going to produce a val binding (with an associated type annotation), however we do not actually give it any definition. In truth, you cannot define a value in the signature itself, since it's impossible in general to check if two values are the same. You can, however, define a
typewithin a signature (or leave it definitionless, as we will see later in the chapter).
An implementation of
MOD_ARITH (called a structure, or module) might look as follows:
structure ModArith : MOD_ARITH = struct fun mod_add n x y = (x + y) mod n fun mod_sub n x y = mod_add n x (~y) fun mod_times n x y = case Int.compare (x, 0) of LESS => mod_add n (mod_times n (x + 1) y) (~y) | EQUAL => 0 | GREATER => mod_add n (mod_times n (x - 1) y) y end
NOTE: By convention, structure names are usually capitalized, and signature
names are usually all-capitals. Additionally, it is totally fine to declare a
structure's values with
fun instead of
val, even if it says
val in the
fun is just shorthand for producing a function value binding
We will go over the precise meaning of the usage of the colon symbol in the
above structure later in the chapter. For now, the meaning of this code snippet
is to produce a structure ascribing to the
MOD_ARITH signature, or in other
words, implementing the
MOD_ARITH specification. We see that it contains three
declarations, those being the functions declared in the signature itself. A key
note is that ascribing to a signature is akin to a contract - any structure
ascribing a signature must implement all the requisite components described by
the signature, or it will fail to ascribe, and result in a compile-time error
(similar to an ill-typed program).
It is not, however, the case that a structure cannot provide more information than is strictly necessitated by the signature. Additional helper functions and value bindings can be freely instantiated within a structure without affecting ascription. Thus, honoring a contract only entails satisfying the terms agreed to in the signature, without comment on going over. We will explore this idea more later in the chapter when we discuss information hiding.
Using structures should be something that you are already familiar with - you do
it every time that you invoke
Int.compare. To use the fields of a structure,
you access them using the name of the module, followed by a dot, followed by the name of whatever
you are trying to access. Thus, calling
Int.compare means to access the function named
compare implemented within the structure named
Int, which is provided as
part of the Standard ML Basis Library. To use the structure that we have just
implemented, we would similarly call
ModArith.mod_add, for instance.
It is important to know that although a structure may contain values, a
structure is not a value. Structures and signatures exist on another "level"
of syntax outside that of expressions and values, and should not be mixed
interchangeably with them. For instance, it would be nonsense to write
val x = ModArith, as you cannot bind
ModArith to a value identifier.
It is often useful when thinking of structures and signatures to think of them as "elevated types and values", as there is a neat correspondence between the two. A structure is really just a package of values (among other things, as we will see later) that must "type-check" in that it must successfully ascribe to its signature. As such, a structure can be regarded as a "bundle of values", and a signature as a "bundle of types". This only skims the surface at what can be done with modules, but it is a handy perspective to have.
Ultimately, the main goal that we seek to achieve with modules is, in fact, modularity. As alluded to previously in this chapter, we have mentioned how we would like to be able to swap out certain implementations for others as necessary, to enforce clean boundaries of code dependency and produce more maintainable code. As it stands, we have only seen modules used for conveniently wrapping our code, however in this section we are going to discuss how modules allow us to maintain multiple implementations of the same specification.
Consider the following signature for performing geometric operations on the Cartesian plane:
signature GEOMETRY = sig type point val origin : point val rotate : point -> real -> point val get_x : point -> real val get_y : point -> real val get_dist : point -> real end
Suppose that we are interested in performing operations on points within the Cartesian plane. Then, we may be interested in a structure ascribing to this signature. The question then becomes - how should this signature be implemented? We have previously discussed swapping out more code for more efficient implementations, however in that case we clearly consider one unilaterally superior to the other.
In this signature, note that we have left the type of
point abstract, meaning that it
is up to the structure to define what precisely the type of
point is - it is
not decided by the signature. In this case, there are at least two discrete ways
that we can consider points on the Cartesian plane - as rectangular or polar coordinates.
Consider the following structures ascribing to the
structure RectGeo : GEOMETRY = struct (* pair of (x, y) coordinates *) type point = real * real val origin = (0.0, 0.0) fun rotate (x, y) r = (x * Math.cos r) + (y * Math.sin r) fun get_x (x, y) = x fun get_y (x, y) = y fun get_dist (x, y) = Math.sqrt (Math.pow (x, 2.0) + Math.pow (y, 2.0)) end ```sml structure PolarGeo : GEOMETRY = struct (* pair of (d, theta), where d is distance from origin and theta is angle from 0 degrees *) type point = real * real (* theoretically here theta could be anything *) val origin = (0.0, 0.0) fun rotate (d, theta) r = (d, theta + r) fun get_x (d, theta) = d * (Math.cos theta) fun get_y (d, theta) = d * (Math.sin theta) fun get_dist (d, theta) = d end
It should be relatively clear that these are two perfectly valid ways of representing an (albeit limited) implementation of coordinate geometry. Both have their own strengths and weaknesses, such as rectangular coordinates having more convenient access to computing the x and y coordinates of a given point, and polar coordinates more easily rotating points about the origin and calculating the distance of a point from the origin. As such, it comes down to context to determine which should be used in any given circumstance.
In this case, modules allow a convenient way of swapping out code without having
to bother with poring through to find dependencies. If we are using the
PolarGeo structure, and instead find ourselves wishing that we were using
rectangular coordinates instead - no problem! We can simply load the other
structure instead. In this case, we have moved dependencies and code reuse to a
static, compile-time check, much in the same way that we moved type-checking to
a static, compile-time check. This is a recurring theme, that we can avoid
deferring errors to runtime to instead try and catch them earlier, in order to
write cleaner and less error-prone code.
At this point, we have discussed how to use modules for enforcing "contracts" between parties interested in some kind of software, as well as how it can assist in code reuse and statically enforcing code dependencies. Another use of modules in the SML module system is information hiding.
It is sometimes said that one of the greatest ideas in computer science is abstraction. Whether it is focusing on developing an algorithm to solve a problem, a piece of software for a given client, or trying to interface with some existing computer system, it is often the case that it is only prudent to focus on those details that are relevant to the problem. It takes time and mental energy to internalize every last detail of a codebase, and it is a waste of time to try and do so every time that one wants to make a patch. As such, we rely on abstraction in order to keep the amount of relevant information low.
Consider the computer. It is a complicated, convoluted work of machinery and circuitry - at its most fundamental level being comprised of logic gates and incredible networks of interacting parts. Although an action as simple as opening up a notepad seems very intuitive to the user, under the hood it is anything but. The key, however, is that the user of a computer need not understand the underlying hardware and circuitry - indeed, they need not even know what circuitry is! In the general case, the user of a computer does not really know how it functions.
Yet again, it is also unlikely that it is important for you to know. A user of a computer does not need to know precisely how it works to know that they can type a query into Google. The only details that are relevant to the user are the devices that allow interfacing with the inner hardware (the mouse and keyboard, among other things), and less so the precise configuration of the microchips inside of the machine.
When writing code, we would like to maintain the same practice. We would like to write clear, concise, and maintainable code (for the unfortunate souls who have to go back and read it afterwards), so it is important to lessen the burden on the code-reader who comes after (which might be you!). With modules, we will be able to create enforced abstraction boundaries that allow programmers to only consider the interface of a given module, much in the same way that a computer-user needs only consider the physical interface of the device.
The first example of this phenomenon of information hiding is through the contents of a structure that are available for use. We have spoken of signatures as an interface, a sort of lens through which we view the contents of a structure. This metaphor is further strengthened by the fact that a signature literally does dictate what information the user of a structure is able to see. In any structure ascribing to a given signature, the only data able to be used by an outside client are those described within the signature.
Practically, this means that the use of "helper functions" in the implementation of a structure is hidden from the client. This means that in the following signature and structure:
signature REVERSE = sig val reverse : 'a list -> 'a list end structure Reverse : REVERSE = struct fun trev  acc = acc | trev (x::xs) acc = trev xs (x::acc) fun reverse L = trev L  end
only the value
reverse is visible to the user of the
Reverse structure. This
can be convenient in enforcing abstraction, because we could be writing a
program that uses helper functions that have certain preconditions. Through
restricting the usage of those helper functions, the client is blocked from
constructing certain inputs to those functions that may violate those
preconditions, resulting in unallowed behavior.
We have used the term "ascription" several times so far in this chapter, referring to how a structure "implements" a signature, similarly to how a value has a certain type. In reality, there are two kinds of ascription: transparent and opaque. To demonstrate the difference, we will consider the following implementation of 2D arrays.
signature ARRAY = sig type 'a array val new : int * int -> 'a -> 'a array val get : 'a array -> int * int -> 'a array val set : 'a array -> int * int -> 'a -> 'a array end structure RectArray : ARRAY = struct type 'a array = 'a list list fun row 0 v =  | row n v = v :: row (n - 1) v fun new (0, width) v =  | new (height, width) v = row w v :: new (height - 1, width) v fun get A (y, x) = List.nth (List.nth (A, y), x) fun set A (y, x) v = let val row = List.nth (A, y) in List.update (A, y, List.update (row, x, v)) end end
This implementation of arrays uses a 2D list in order to create a rectangular
array, with separate access to each row. There is one "creator" function,
which constructs a new array, and get the "getter" and "setters" of
set, which allow manipulation of an existing array. The structure
thus ascribes to the
ARRAY signature, and because of its usage of the colon
symbol, it transparently ascribes to the
ARRAY signature. We are now ready
to discuss precisely what this means.
[Transparent ascription]: Ascribing a structure to a signature where all abstract types are visible to the user of the structure.
We have previously discussed the existence of abstract types, which are type
declarations in the signature that is being ascribed to. For instance, the type
'a array is an abstract type, because it is not concretely defined within
the signature. However, if we had instead replaced that line in the
type 'a array = 'a list list, it would no longer be abstract
(and note that this would have the consequence that any structure ascribing to
ARRAY must use the representation of a 2D list for its arrays).
What precisely does it mean for the type of
'a array to be visible to the user
of the structure? We know that the user of a structure should only be aware of
what is in the signature of a structure, and nothing more. This is not strictly
true - if we have a transparently ascribed structure like
RectArray, then the
user of the
RectArray structure can treat the
'a RectArray.array type as
'a list list, and thus be privy to the "internals" of the
structure, even though it is not explicitly defined within the structure.
We will now compare this to if we had instead used opaque ascription. Consider
the following two implementations of the
structure ListArray :> ARRAY = struct type 'a array = 'a list * int fun gen 0 v =  | gen n v = v :: gen (n - 1) v fun new (height, width) v = (gen (height * width) v, width) fun get (A, w) (y, x) = List.nth (A, w * y + x) fun set (A, w) (y, x) v = List.update (A, w * y + x, v) end structure RectArray :> ARRAY = struct type 'a array = 'a list list fun row 0 v =  | row n v = v :: row (n - 1) v fun new (0, width) v =  | new (height, width) v = row w v :: new (height - 1, width) v fun get A (y, x) = List.nth (List.nth (A, y), x) fun set A (y, x) v = let val row = List.nth (A, y) in List.update (A, y, List.update (row, x, v)) end end
Note that the latter implementation is exactly the same as the previous
RectArray structure, with the exception that is now opaquely ascribed. This
is from using
:> between the structure and signature names, which signals
opaque ascription rather than transparent ascription.
[Opaque ascription]: Ascribing a structure to a signature where all abstract types are hidden to the user of the structure.
By "hidden", we mean precisely in the same way that the abstract types are
"visible" in transparent ascription. Abstract types are truly that, abstract,
and thus the user of either the
ListArray structure are
incapable of knowing precisely what either the
'a ListArray.array or
'a RectArray.array types are. The only way to construct a value of type
'a array, from either structure, is by using either respective
new function, and
similarly with manipulating an existing array.
Why would we want to have opaque ascription? This is precisely for the reason
that we have been motivating for the entire chapter, which is abstraction. A
fundamental idea of having a powerful type system is to make illegal states
unrepresentable. Instead of having a precondition that must be obeyed in a
given function, we instead would like it so that the type system enforces these
preconditions for us instead - similarly to how for a function of type
int -> int with precondition "TRUE", if we were to instead write it in a dynamically
typed ("typeless") language, we may instead say that it has a precondition that
its input is an integer. This is then just an extension of that idea to more
general representation invariants.
By representation invariant, we typically mean some invariant of a data
structure that qualifies it to truly be an "instance" of that data structure.
For instance, in the
RectArray structure, we use a 2D list to represent a
given array, however it is not the case that all values of type
'a list list
correspond to an array of
'a values. For instance, is
[[1, 2, 3], [4, 5]] a
RectArray were to be transparently ascribed, a client could construct an
illegal instance of an
'a RectArray.array, and thus produce undefined behavior
when interfacing with it using functions like
set. By opaquely
ascribing it to its signature, however, we ensure that the only way that you
can produce and manipulate arrays is internally, through the structure itself,
so as long as the structure's functions preserve representation invariants,
there will be no way of producing an illegal state.
Another motivation is that, ultimately, it isn't important for the client to
know how arrays are implemented - this is an example of information hiding.
If a client wants some implementation of the
ARRAY signature, it likely isn't that
important to them whether or not it is implemented as a one-dimensional or two-dimensional
list, so long as it provides certain functionality (which, while limited in this example,
could be extended). We can thus ensure that it is completely impossible to distinguish
RectArray, at least in terms of their input-output behavior. This benefits abstraction in
that now the client does not have to think about the fiddley details of
implementation, but instead focus purely on the interface.
We thus see that transparent ascription is useful for cases where knowing a representation is totally fine (or when debugging), but opaque ascription is in general the best approach when constructing a library. To clients of a given software package, it is best to enforce abstraction.
In this chapter, we have explored the powerful benefits that are given by SML's module system, particularly in terms of information hiding, abstraction, and modularization. While modules are in themselves of significant theoretical interest, there are many practical applications to their use, and they offer a clean and concise way to structure large codebases. In the next chapter, we will explore functors, which are like a higher-order structure that allows us a greater degree of freedom in structuring our code.