2.1 Hierarchy-Builder in a nutshell

Hierarchy-Builder extends Coq with commands to define hierarchies of mathematical structures and is used in the Mathematical Components (hereafter, MathComp) library (Mahboubi & Tassi, Reference Mahboubi and Tassi2022). The commands are designed so that hierarchies can evolve (e.g., by splitting a structure into smaller structures) without breaking existing code. In addition to commands to build hierarchies, Hierarchy-Builder also checks their validity by detecting missing interfaces (Saito & Affeldt, Reference Saito and Affeldt2022, Sect. 6) or competing inheritance paths (Affeldt et al., Reference Affeldt, Cohen, Kerjean, Mahboubi, Rouhling and Sakaguchi2020).

Each mathematical structure is presented as three layers: a carrier, operations, and properties. This layering is standard in mathematics,Footnote ⁴ thus enabling a straightforward translation of textbook definitions of structures.

The main concept of Hierarchy-Builder is the one of factory. This is a Coq record defined by the command HB.factory that packs operations and properties for a carrier, providing an interface to the theory of the corresponding mathematical structure.

Mixins (defined by the command HB.mixin) are the factories that are used to provide the primitive definition of mathematical structures; factories other than mixins are rather used to provide alternative definitions to the primitive ones.

Structures (defined by the command HB.structure) pack a carrier with one or more factories (intuitively, forming a sigma-type) to form an actual mathematical structure. More precisely, the command

equips A with the interfaces (factories) or structures f1, f2, $\ldots$ , fn. Concretely, it creates a Coq Record with a parameter corresponding to A in which each field is one of the interfaces applied to the parameter, a dependent pair whose first field corresponds to A and whose second field is an instance of the record mentioned just above, a module that contains the Record and the dependent pair, and unification hints (Cohen et al., Reference Cohen, Sakaguchi and Tassi2020, Sect. 3.2). In fine, Hierarchy-Builder commands compile mathematical structures to packed classes (Garillot et al., Reference Garillot, Gonthier, Mahboubi and Rideau2009), but the technical details (Coq modules, records, coercions, implicit arguments, canonical structures instances, notations, etc.) are hidden to the user.

One can associate builders to a factory by using the HB.builders command that opens a Coq section importing the factory, where one defines instances of mixins (the “builders”), before ending with the HB.end command. See Sect. 2.3 for an example.

Factories (including mixins) are to be eventually instantiated (command HB.instance) with concrete objects. Instances are registered with .Build functions that are provided automatically for each factory by Hierarchy-Builder.

2.2 Functors and natural transformations

Our hierarchy of interfaces of effects starts with capturing the notion of functors on the category of sets. In our Coq definition, the domain and codomain of functors are fixed to Coq’s native type : this a predicative type that can be interpreted as the universe of sets in set-theoretic semantics.Footnote ⁵

Using Hierarchy-Builder, we define functors by the mixin isFunctor (line 1). The carrier is a function F of type Type -> Type (line 1) that represents the action on objects and the operator actm (line 2) represents the action on morphisms. The functor laws appear in lines 3 and 4 (they correspond to the standard definitions, see Table 1 for details):

Table 1. Algebraic laws used in this article.Footnote ⁶ See Monae (2018), file hierarchy.v) for the code.

Given a functor F and a function f (seen as a morphism), we denote by F # f the action of F on f, as a notation for @actm F _ _ f (where the prefix @ is a Coq modifier to make all the arguments of a function explicit).

As explained in Section 2.1, the mixin isFunctor only provides an interface, the type of functors is defined by a Hierarchy-Builder structure Functor that can be seen as a sigma-type of a carrier F satisfying the interface isFunctor:

Hierarchy-Builder uses Coq modules to implement structures. Here, the type of functors is accessible as Functor.type; the pragma defines a shorthand for this type, and this is actually the preferred way to refer to it.

We can now create instances of the type functor. For example, we can equip idfun, the standard identity function of Coq, with the structure of functor by using the HB.instance command (line 5 below). It is essentially a matter of proving that the functor laws are satisfied, which is trivial (lines 3, 4):

Similarly, we define an instance for the Coq composition of function (notation \o):

We now define natural transformations. Given two functors F and G, we formalize the components of natural transformations as a family of functions f, of type A, F A -> G A (we note this type F ~~> G for short) that satisfies the following predicate (recall that \o denotes function composition):

Natural transformations are defined by means of the mixin and the structure below:

In Monae, we note F ~> G instead of nattrans F G for the type of natural transformations from F to G.

2.3 Formalization of monads

We now formalize monads. A monad extends a functor with two natural transformations: the unit ret (line 2 below) and the multiplication join (line 3). They satisfy three laws (lines 7–9, see Table 1). Furthermore, we add to the mixin an identifier for the bind operator (line 4, hereafter noted >>= or >> when the right-hand side ignores its input) and an equation that defines bind in term of unit and multiplication (line 6). Note however that this does not mean that the creation of a new instance of monads requires the (redundant) definition of the unit, multiplication, and bind (this is explained below):Footnote ⁷

The fact that a monad extends a functor can be observed at line 1 with the of keyword. Also, when declaring the structure at line 12, the & mark indicates inheritance w.r.t. all the mixins on which the mixin isMonad depends on. Hereafter, we also use the notation Ret instead of ret; this is for technical reasons that have to do with the setting of implicit arguments.

The above definition of monads is not the privileged interface to define new instances of monads. We also provide factories with a smaller interface from which the above mixin is recovered. For example, here is the factory to build monads from the unit and the multiplication:

This corresponds to the textbook definition of a monad, since it does not require the simultaneous definition of the unit, the multiplication, and bind. We use the HB.builders command (Section 2.1) to show that this lighter definition is sufficient to satisfy the isMonad interface.

Similarly, there is a factory to build monads from the unit and bind only (and that in particular does not require naturality of operators):

The definition of monad (interface isMonad) that we presented here is an improvement compared to the original formalization (Affeldt et al., Reference Affeldt, Nowak and Saikawa2019, Sect. 2.1) because there is now an explicit type of natural transformations (for ret and join) and because Hierarchy-Builder guarantees that monads instantiated by factories do correspond to the same type monad. See Monae (2018, file monad_model.v) for many instances of the monad structure handled by the isMonad_ret_bind factory.

2.4 Nondeterminism monad

In the previous section, we explained the case of a simple extension: one structure (the one of monads) that extends another (the one of functors). In this section, we explain how a structure combines several interfaces.

The nondeterminism monad extends both the failure monad and the choice monad. The failure monad failMonad extends the class of monads (Section 2.3) with a failure operator fail (line 2 below) that is a left-zero of bind (line 3). This is the same extension methodology as in Section 2.3:

The choice monad altMonad extends the class of monads with a choice operator alt (line 2 below, infix notation: [ ~ ]) that is associative (line 3) and such that bind distributes leftward over choice (line 4):

See Tables 1 and 2 for the definition of the predicates associative and left_distributive, respectively.

Table 2. Algebraic laws defined in MathComp.

The nondeterminism monad nondetMonad defined below extends both the failure monad and the choice monad (as can be seen at line 2 below, see also Figure 2) and adds laws expressing that failure is an identity of choice (lines 3, 4):

Fig. 2. Hierarchy of effects for the nondeterminism monad.

As a result, a nondeterminism monad can be regarded both as a failure monad or as a choice monad.

2.4.1 Assertions in monadic programs

The introduction of the failure monad already allows for the definition of reusable library functions.

Given a failure monad M, it is customary to define assertions as follows. A computation guard b of type M unit fails or skips according to a boolean value b:

An assertion assert p a is a computation of type M A that fails or returns a according to whether p a is true or not (pred is the type of boolean predicates in MathComp):

It turns out that in practice it is even useful to define a dependently typed assertion that fails or returns a value together with a proof that the predicate is satisfied:

The notation {a | p a} is for a dependent pair whose constructor is exist. To demonstrate the usefulness of dependently typed assertions, we need a bit of context that will be provided by a concrete example in Section 4.3.1.

2.5 Exception monad

Similarly to the nondeterminism monad that extends the failure monad in the previous section, the exception monad can be defined by extending the failure monad with a catch operator and four laws:

See Table 2 for the definitions of the generic predicates used in this interface. As for an application, we send back the reader to the fastprod example explained in Figure 1 (Section 1).

2.6 State monad

The state monad is certainly the first monad that comes to mind when speaking of effects. It denotes computations that transform a state (type S below). It comes with a get operator to yield a copy of the state and a put operator to overwrite it. These functions are constrained by four laws (Gibbons & Hinze, Reference Gibbons and Hinze2011) that appear below at lines 4–8:

2.7 Array monad

The array monad extends a basic monad with a notion of indexed array (Mu & Chiang, Reference Mu and Chiang2020, Sect. 5.1). Intuitively, it is a generalization of the state monad (Section 2.6). It provides two operators to read and write indexed cells. Given an index i, aget i returns the value stored at i and aput i v stores the value v at i. These operators satisfy the laws of Table 3. For example, aputput means that the result of storing the value v at index i and then storing the value v’ at index i is the same as the result of storing the value v’. The law aputget means that it is not necessary to get a value after having stored it provided this value is directly passed to the continuation. Other laws can be interpreted similarly.

Table 3. The laws of the array monad.

In Monae, the array monad is formalized by extending the base monad with the following mixin:

Note that the type of indices is an eqType, that is, a type with decidable equality, as required by the laws of the array monad.

Using the array monad, we can write various functions that manipulate arrays. For example, in any context where S : and I : eqType, we can swap the contents of two cells by combining aget and aput:

Specializing the type of indices to nat, we can also recursively call the aput operator to write a list xs to the array starting from the index i:

The SSReflect construct if x $\mathit{pat}$ performs matching on x w.r.t. the pattern $\mathit{pat}$ .

2.8 Probability monad

Before defining the probability monad, we define a type {prob R} with R a type for real numbers to represent “probabilities,” that is, real numbers between 0 and 1. This definition comes with a notation p%:pr such that the type {prob R} is automatically inferred based on the shape of the expression p. For example, 1%:pr represents the real number 1 seen as a probability.

In order to define the interface of the probability monad in a modular way, we introduce as an intermediate step the interfaces of “convex monads,” that is, an interface that provides a family of binary choice ${\cdot}\triangleleft{p}\triangleright{\cdot}$ operators parameterized by probabilities p (see line 3 below). These choice operators satisfy the axioms of convex spaces (Jacobs, Reference Jacobs2010, Def. 3):

• ${a}\triangleleft{1}\triangleright{b} = a$ (line 4),

• ${a}\triangleleft{p}\triangleright{b} = {b}\triangleleft{\bar{p}}\triangleright{a}$ where $\bar{p} \overset{\text{def}}{=} 1 - p$ (skewed commutativity, line 6),

• ${a}\triangleleft{p}\triangleright{a} = a$ (idempotence, line 7), and

• where $\mathrm{s}{p},{q} \overset{\text{def}}{=} \overline{\bar{p}\bar{q}}$ and $\mathrm{r}{p},{q} \overset{\text{def}}{=} \frac{p}{\mathrm{s}{p},{q}}$ (quasi associativity, line 8).

Note that at line 6, the notation r. stands for $\bar{r}$ .

The probability monad merely extends the convex monad by adding the axiom that bind left-distributes over probabilistic choice (line 3):

2.8.1 Probability and nondeterminism

Last, we briefly mention the interface of a monad that mixes probability and nondeterminism: the geometrically convex monad (Cheung, Reference Cheung2017). Its interface just adds the right-distributivity of probabilistic choice over nondeterministic choice to the probability monad:

The dependencies of the geometrically convex monad are displayed in Figure 3. The formalization of this monad is the topic of previous work (Affeldt et al., Reference Affeldt, Garrigue, Nowak and Saikawa2021) which explains that the construction of its model is important but not trivial.

Fig. 3. Hierarchy of effects for the probability monad and the geometrically convex monad.

The complete hierarchy of effects discussed in this article is displayed in Figure 4. Monae actually contains a few more experimental interfaces (see Monae, 2018).

Fig. 4. The complete hierarchy of effects discussed in this article (as generated by the command HB.graph of Hierarchy-Builder).

3.1 Monad transformers

Monad transformers is a well-known approach to combine monads (Liang et al., Reference Liang, Hudak and Jones1995) that is commonly used to write Haskell programs. The interest in extending Monae with monad transformers is twofold: it provides an application of monadic equational reasoning (e.g., Jaskelioff’s theory of modular monad transformers has been formalized in Monae Affeldt & Nowak, Reference Affeldt and Nowak2020), and monad transformers can be used to formalize concrete models of monads (as we will see in Section 5.2.2).

Similarly to functors, monads, and interface for effects, monad transformers can be formalized in terms of Hierarchy-Builder interfaces and structures. Given two monads M and N, a monad morphism is a function M ~~> N (see Section 2.2 for the definition of ~~>) that satisfies the laws of monad morphisms (Benton et al., Reference Benton, Hughes and Moggi2000, Def. 19) (Reference JaskelioffJaskelioff, 2009a , Def. 7):

Table 4 provides the definitions of the laws. An important property of monad morphisms is that they are natural transformations so that we define the type of monad morphisms using the interface of monad morphisms and the interface of natural transformations (Section 2.2):

However, since the laws of monad morphisms imply naturality, a monad morphism can be defined directly by a factory with only the laws of monad morphisms:

Upon declaration of this factory, we can use the HB.builders command of Hierarchy-Builder to declare instances of the monad morphism and of the natural transformation interfaces.Footnote ⁹ Like for monads in Section 2.3, we are again in the situation where the textbook definition ought better be sought in factories rather than in the mixins used to formally define it in the first place.

Table 4. Algebraic laws for monad morphisms.

A monad transformer t is a function from monad to monad such that for any monad M it returns a monad morphism from M to t M (Benton et al., Reference Benton, Hughes and Moggi2000, Sect. 3.3) (Reference JaskelioffJaskelioff, 2009a , Def. 9):

Going one step further, we can define functorial monad transformers (Reference JaskelioffJaskelioff, 2009a , Def. 20) (Functorial and FMT in Figure 4) and revise the formalization of Jaskelioff’s modular monad transformers using Hierarchy-Builder following Affeldt & Nowak (Reference Affeldt and Nowak2020), see Monae (2018) for details.

3.1.1 Example: The state monad transformer

We explain how we instantiate the type of monad transformer with the example of the state monad transformer. Let us assume some type S : for states and some monad M. First, we define the action on objects of the monad transformed by the state monad transformer:

We also define the unit and the bind operator of the transformed monad:

Second, we define the monad morphism that will be returned by the lift operator of the monad transformer. In Coq, we can formalize the corresponding function by constructing the desired monad assuming M (in a Coq ) and using the factory isMonad_ret_bind from Section 2.3. It suffices to prove the laws of the monad:

Then we define the lift operation as a function that given a computation m : M A returns a computation in the monad MS:

We can finally prove the lift operations satisfy the monad morphism laws of Table 4:

The state monad transformer is defined as an alias stateT to which the type monadT is associated:

Here, the alias stateT is necessary because isMonadT is expecting a transformer of type monad -> monad. However, when MS is first defined, it is not yet known that its return type is monad. After instantiation with isMonad_ret_bind.Build, this information can be inferred; the alias stateT records the result of this inference for Hierarchy-Builder.

One should wonder what is the relation between the monads that can be built with the state monad transformer and the state monad of Section 2.6. In fact, we can define a Put and a Get operations for a monad MS S M so that it satisfies the laws of state monads:

Section 5.2.2 provides an example of application of the state monad transformer (MS): we use it to extend the option monad and build the model of the typed store monad.

3.2 A model of the probability monad

As explained in Section 2.8, a probability monad has to turn each input type into a convex space and provide the bind operator in a way that is compatible with the convex space structure. We can achieve these two requirements by, for an input type A, constructing the type {dist A} of finitely supported distributions over A (Affeldt et al., Reference Affeldt, Nowak and Saikawa2019, Sect. 6.2) (Infotheo, 2018):

\[ \mathrm{supp}(f) \overset{\text{def}}{=}\overset{\text{def}}{=} \left\{x \in \texttt{A} \; \middle| \; f(x) \not= 0 \right\}.\]

Technically, we need A to satisfy the axiom of choice to let the finitely supported function have a canonical list representation (appearing as type annotations $\texttt{A : choiceType}$ in the code Infotheo, 2018).

To complete this definition into a functor, and furthermore, a monad, we can use the factory isMonad_ret_bind defined in Section 2.3, which requires us only to provide the two monadic operators ret and bind and to prove that they satisfy the needed laws.

The bind operator computes the weighted sum out of a given distribution $p : M(A)$ and a monadic function $g : A \to M(B)$ , returning a new distribution with probability mass function:

\[ b \longmapsto \sum_{a \in \mathrm{supp}(g)} p(a) \cdot g(a,b).\]

This function is implemented by the following code (Infotheo, 2018, file fsdist.v]:

The resulting operator can be proved to satisfy the monad laws, for example, associativity

follows from the distributivity of multiplication over big sum, and computation on big unions, both handled by MathComp’s big operator library.

The ret operator embeds a given point $a : A$ into M(A) as the distribution concentrated on the singleton $\{a\}$ (a.k.a. Dirac’s delta), whose probability mass function is

\[ x \longmapsto \begin{cases} 1 & \text{if $x = a$}, \\ 0 & \text{otherwise}. \end{cases}\]

The corresponding code in Infotheo (2018) is straightforward:

The other monad laws involving both ret and bind are proved similarly as above:

We can then pack these definitions and proofs into a monad by applying the builder function from the factory isMonad_ret_bind as follows (Monae, 2018, file proba_monad_model.v) :

Observe that, to define the monad, we need to convert T : Type into a choiceType before feeding it to {dist _} (line 1). For that purpose, we assume the generic axiom of choice additionally to Coq’s type theory in the form of a function:

Composing {dist _} and choice_of_Type, we obtain the object part of the model M of the probability monad ( $M(T) \overset{\text{def}}{=} \texttt{\{}\texttt{dist}\ (\texttt{choice_of_Type}(T))\texttt{\}}$ ).

At this point, we have completed the monad structure on our construction. Since finitely supported distributions carry the convex space structure (thus, easily endowed with a convex monad (Section 2.8) structure), the remaining task is to prove the left-distributivity law of bind over the probabilistic choice:

Packing this additional law using the mixin isMonadProb, we finally complete the model of the probability monad:

4.1 Plus monad and plus array monad

First, we extend the hierarchy of Section 2 with the plus monad and the plus array monad. It extends the nondeterminism monad of Section 2.4.

We define the plus monad following Pauwels et al. (Reference Pauwels, Schrijvers and Mu2019) and Mu & Chiang (Reference Mu and Chiang2020) (see Mu & Chiang, Reference Mu and Chiang2020, Sect. 2). It extends a basic monad with two operators: failure and nondeterministic choice. These are the same operators as the nondeterminism monad (Section 2.4). It, however, satisfies more laws than the nondeterminism monad: (1) failure and choice form a monoid, (2) choice is idempotent and commutative, and (3) failure and choice interact with bind according to the laws of Table 5. We take advantage of existing monads to implement the plus monad. Indeed, we observe that most laws are already available. The monad failMonad (Section 2.4) provides the left_zero law. The monad failR0Monad is used to define the interface of backtrackable state (Affeldt et al., Reference Affeldt, Nowak and Saikawa2019, Sect. 3.2) (nondetStateMonad in Figure 4) and in (Affeldt & Nowak, Reference Affeldt and Nowak2020); it introduces the right_zero law. The monad altMonad (Section 2.4) introduces nondeterministic choice and the left_distributivity law. The monad altCIMonad extends altMonad with commutativity and idempotence of nondeterministic choice. In other words, only the right-distributivity law is missing from previous work.

Table 5. The third set of laws satisfies by the plus monad (see Section 4.1) ([~] is the notation for nondeterministic choice, Section 2.4).

We therefore implement the plus monad by extending the monads mentioned above with the right-distributivity law, as shown in Figure 5. First, we define the intermediate prePlusMonad by adding right-distributivity to the combination of nondetMonad and failR0Monad (recall that alt is the identifier behind the notation [ ~ ]):

Fig. 5. Hierarchy of effects for the plus monad and the plus array monad.

Then, plusMonad is defined as the combination of nondetCIMonad and prePlusMonad:

Plus array monad

The plus array monad is a straightforward extension (Mu & Chiang, Reference Mu and Chiang2020, Sect. 5): it combines the plus monad with the array monad of Section 2.7:

4.2 Commutativity of nondeterministic computations

In monadic equational reasoning, it often happens that one needs to show that two computations commute, in particular in presence of nondeterminism. The following predicate (Reference MuMu, 2019a , Def. 4.2) defines the commutativity of two computations m and n in Monae:

The need to show commutativity occurs in particular when dealing with state (be it as in a state monad or in an array monad) and nondeterminism. For example, commutation is possible when a computation in the plus array monad is actually using only nondeterministic operations and therefore does not access the array. To capture computations that are actually using only nondeterministic operations, we define a predicate that characterizes syntactically nondeterminism monads. They are written with the following (higher-order abstract Pfenning & Elliott, Reference Pfenning and Elliott1988) syntaxFootnote ¹⁰ where each constructor reflects the eponymous monadic construct:

Let sem be a function that computes the semantics of the above syntax in the nondeterminism monad:

Using the above syntax, we can for example write a predicate that captures computations in a plusMonad that are semantically just computations in the nondeterminism monad:

Recall that the notation {m | P m} is for dependent pairs, as already explained in Section 2.4.1.

Eventually, it becomes possible to prove by induction on the syntax (and using the laws of the plus monad) that two computations m and n in the plus monad commute when m only uses nondeterministic operators:

Using this lemma, to show that two computations in the plus monad commute, it suffices to show that one of the two satisfies the predicate plus_isNondet. When a computation does satisfy this predicate, it is good practice to prove it right away and register this fact as a hint in Coq so that when one uses the lemma plus_commute generated subgoals are discharged automatically. Section 4.3.3 provides a concrete example.

4.3 Quicksort derivation

This section formalizes the setting of Mu & Chiang (Reference Mu and Chiang2020). First, we specify sorting functions. Second, we define quicksort using the array monad. Finally, we state the goal of the derivation of quicksort using refinement.

4.3.1 Nondeterministic computation of permutations

We formalize a function qperm that computes nondeterministically permutations. In the following, M is assumed to be of type altMonad (Section 2.4).

The first step is to define a function that splits a list nondeterministically. This is a structurally recursive function that can be encoded using the command of Coq. Recall that [∼] is the notation for nondeterministic choice:

The return type of the splits function is M (seq A * seq A). We now write another function splits_bseq with the same semantics but whose return type contains size information that is useful to establish the termination of functions calling it. The return type of this new function is M ((size s).-bseq A * (size s).-bseq A), where s is the input list and n.-bseq A is the type of lists of size less than or equal toFootnote ¹¹ n:

Provided that one ignores the notations and lemmas about bounded-size lists, the body of this definition is the same as the original splits. The notation [bseq of [::] is for an empty list seen as a bounded-size list. The lemma widen_bseq captures the fact that a m.-bseq T list can be seen as an n.-bseq T list as long as m <= n:

Since leqnSn n is a proof of n <= n.+1, we understand that widen_bseq (leqnSn _) turns a n.-bseq list into an n.+1.-bseq list. The notation [bseq of x :: ys] is a MathComp idiom that triggers type inference using canonical structures to build a n.+1.-bseq list using the fact that ys is itself a n.-bseq list.

We can now write a function qperm that computes permutations nondeterministically. For this purpose, we use the Coq Equations command (Sozeau, Reference Sozeau2009; Sozeau & Mangin, Reference Sozeau and Mangin2019) that provides support to prove the termination of functions whose recursion is not structural:

The annotation wf (size s) lt indicates that the relation between the sizes of lists is well founded. The function liftM2 is a generic monadic function that lifts a function h of type A -> B -> C to a monadic function of type M A -> M B -> M C. Once the Equations command is processed, Coq asks for a proof that the size of the arguments are indeed decreasing. This fact is provable thanks to the additional type information returned by splits_bseq. Under the hood, Coq uses the accessibility predicate (Bertot & Castéran, Reference Bertot and Castéran2004, Chapter 15). Note that qperm is not the most obvious definition for the task of generating nondeterministically permutations, but it is a good fit to specify quicksort (Mu & Chiang, Reference Mu and Chiang2020, Sect. 3).

Specification of sorting functions The function qperm provides a way to specify sorting functions. Indeed, it suffices to generate all the permutations and filter the sorted ones. Let use assume that M has type plusMonad (Section 4.1) and that T is an ordered type (as defined in MathComp). We can use the generic MathComp predicate sorted and define an obviously correct sorting “algorithm” using qperm, the Kleisli symbol >=>, and the assertion assert of Section 2.4.1:

4.3.2 In-place quicksort

We can now formally define quicksort following Mu & Chiang (Reference Mu and Chiang2020).

The partition step is performed by the function ipartl, which uses the array monad (Section 2.7). The parameter T below is a generic ordered type for the array contents:

The call ipartl p i ny nz nx partitions the subarray ranging from index i (included) to index i + ny + nz + nx (excluded) and returns the sizes of the two partitions. For the sake of explanation, we can think of the contents of this subarray as a list ys ++ zs ++ xs; ys and zs are the two partitions and xs is yet to be partitioned; ny and nz are the sizes of ys and zs. At each iteration, the first element of xs (i.e., the element at index i + ny + nz) is read and compared with the pivot p. If it is smaller or equal, it is swapped with the element following ys and partition proceeds with a ys enlarged by one element (see Section 2.7 for the aswap function). Otherwise, partition proceeds with a zs enlarged by one element.

Note that since ipartl is written as a computation in the array monad, it represents a total function giving a single result; in particular, it cannot result in failure in the sense of failMonad.

Quicksort is not structurally recursive, and its definition in Coq using a shallow embedding therefore requires care to convince the termination checker that it is really terminating. Here, we formalize it using the Fix definition from the Coq.Init.Wf module for well-founded fixpoint of the standard library of Coq.Footnote ¹² First, we write using the command for dependent-type programming (The Coq Development Team, 2024, Chapter Program) an intermediate function iqsort’ that implements the same logic as the intended quicksort function except that it does not call itself recursively but instead calls a parameter function (f at line 3 below). The function iqsort’ takes as input a pair of an index and of a size (ni); it is a computation of the unit type. The parameter function f takes as an additional argument a proof that the size of the input list is decreasing. These corresponding proofs appear as holes (the _ syntax) to be filled by the user once the declaration is processed. The code selects a pivot (line 6), calls the partition function (line 7), swaps two cells (line 10), and then calls the parameter function on the partitioned arrays (we explain below the use of the plus array monad):

The partition function is not exactly the ipartl function that we explained at the beginning of this section but a dependently-typed version dipartl that extends its return type to a dependent pair of type dipartlT:

The parameters y, z, and x are the sizes of the lists input to ipartl and this dependent type captures at the level of types that the sizes returned by the partition function are smaller than the size of the array being processed. The dependently typed version of ipartl is obtained by means of the predicate for dependently typed assertions of Section 2.4.1:

Finally, the wanted iqsort function can be written using Fix. This requires a (trivial) proof that the order chosen for the measure is well founded:

The example of in-place quicksort is an example of the unfortunate but unavoidable fact that programs must be terminating to be shallow-embedded and verified in a proof assistant. Understanding the support such as the Equations command or the Fix construct in Coq as well as the need to sometimes reflect size information at the level of types is important in practice and the in-place quicksort provides a good example. In theory, sized types have been shown to be useful to guarantee the termination of programs such as quicksort (Barthe et al., Reference Barthe, Grégoire and Riba2008). However, as of today, it appears that users of the Coq proof assistant still need a support library to prove termination manually, since there are indications that sized types for Coq might not be practical (Chan et al., Reference Chan, Li and Bowman2023).

The use of dipartl in lieu of ipartl explains why iqsort uses the plus array monad, which is the only array monad that provides the failure operator needed by dassert. Yet, its semantics does not rely on the fail operator. Indeed, it can be shown that, even though dipartl is written using dassert, it is the same computation as ipartl ignoring the proof part of dipartlT:

The standard way to take the first projection of a dependent pair in MathComp is the sval function. We can use this fact to show that the recursive call of iqsort can be captured by the following equation that uses ipartl (in the array monad) instead of dipartl:

This provides an evidence that iqsort cannot fail in any reasonable model where fail is distinct from other operations.

4.3.3 Statement of the derivation of quicksort

To state the correctness of iqsort, Mu & Chiang (Reference Mu and Chiang2020) define a notion of program refinement that relates two monadic computations using nondeterministic choice:

As the notation indicates, m1 ‘<=‘ m2 represents a relationship akin to set inclusion, which means that the result of m1 is included in the one of m2: we say that m1 refines m2.

The specification of the derivation of quicksort can now be written as a refinement relation between, on the one hand, a program that writes a list to memory (see Section 2.7) and then calls iqsort, and, on the other hand, a call to slowsort (see Section 4.3.1) followed by a program that writes the result to memory (Mu & Chiang, Reference Mu and Chiang2020, Eqn 12):

The complete formal proof can be found in Monae (2018, file example_iquicksort.v). Let us illustrate this formal proof with an excerpt. In the course of deriving in-place quicksort, Mu & Chiang (Reference Mu and Chiang2020) mutate an array ${\textit{ys}}{+\!+}{\textit{zs}}{+\!+}[\textbf{x}]$ to ${\textit{ys}}{+\!+}[\textbf{x}]{+\!+}{\textit{zs'}}$ where ${\textit{zs'}}$ is a permutation of ${\textit{zs}}$ by swapping $\textbf{x}$ with the leftmost element of ${\textit{zs}}$ . This is formalized by the following refinement relation (Mu & Chiang, Reference Mu and Chiang2020, Eqn 11, p. 12):

In Monae, we formalize the above relation as the following lemma (where M is the plus array monad):

There is almost a one-to-one match with the pencil-and-paper version just above (the only difference is that we found it slightly more practical to have the index i as a parameter instead of an arithmetic expression). Incidentally, the proof of the above lemma provides an application of commutativity (Section 4.2):

This proof step can be performed as a single tactic provided that qperm has been proved to satisfy the plus_isNondet predicate of Section 4.2 and that this fact has been registered as a hint in Coq.

5.1 Representation of OCaml types

The typed store having heterogeneous contents, we need a concrete representation of OCaml types in order to handle the dynamic typing required to access it. In CoqGen, this is achieved through an inductive type ml_type of syntactic type representations (as plain terms), and a computable function coq_type, interpreting them into Coq types in the style of a Tarski universe (Aczel, Reference Aczel1977; Martin-Löf, Reference Martin-Löf1984), which can be abstracted as the following module interface from the source code of CoqGen (CoqGen, 2021):

The loc identifier above is for memory locations. The interpretation function coq_type (Garrigue & Saikawa, Reference Garrigue and Saikawa2022) is parameterized by a monad N, used to translate function types. Concrete definitions for ml_type and coq_type are generated by the CoqGen compiler. The presence of the Tarski universe is the main difference with other transpilers from functional programming languages to Coq, such as coq-of-ocaml (Claret, Reference Claret2018) and hs-to-coq (Spector-Zabusky et al., Reference Spector-Zabusky, Breitner, Rizkallah and Weirich2018).

In CoqGen, the concrete monad used to run programs is obtained as a fixpoint involving coq_type, which enables higher-order stores but requires bypassing the so-called strict-positivity requirement of inductive types, inducing a logical inconsistency. As far as the primary goal of CoqGen is concerned, this is a reasonable choice because type soundness is not directly affected.

In the context of Monae, we restrict ourselves to programs that do not store functions that themselves access the store; there is therefore no need for higher-order stores and we can work in a consistent setting.

5.2 Designing an equational theory from an implementation

As CoqGen itself is built around a monad which models OCaml computations, it seemed natural to use Monae for reasoning with it. While CoqGen supports a large subset of OCaml, including references and exceptions, here we limit ourselves to references, with reference creation, access, and update.

5.2.1 Interface for effects

In Monae, these effects are introduced as follows, starting with our Tarski universe. The ml_nonempty and val_nonempty fields are only here to make the construction of the monad model easier:

See Monae (2018, file hierarchy.v). Note that, in order to preserve the soundness of our logic, we do not take a fixpoint so that this interface uses two different monads: M for computations using the typed store and N for computations by values in the store.Footnote ¹³

5.2.2 Definition of the model

The next step is to provide a model for this monad. We started with the model from CoqGen but soon realized that it would be difficult to use it to prove laws, as it required too many internal invariants. Fortunately, we could quickly come up with an alternative model, whose semantics is essentially identical, but which does not require explicit invariants:

See Monae (2018, file monad_model.v). Here, we just reuse the state monad transformer of Monae (Section 3.1.1), applied to the option monad, to allow computations to fail. Interestingly, failure is only an internal feature of the model and does not appear in the interface: correctly translated OCaml programs never fail on memory access, and none of the laws we present here mentions failure.Footnote ¹⁴ The state itself is a list of dynamically typed values (binding) combining a type representation and a value of this type. The type loc will contain a position in this list. The definitions of cnew and cget are introduced by Let as we only need them to define an instance of our interface. In the implementation of cnew, we generate a new reference cell by adding a new value at the end of the list, using the rcons operation. Since we use the length of the list as location, we can be sure that this location was invalid before calling cnew. We also show the code for cget, which demonstrates how we access the store using a standard library function, nth_error, which returns None if the index is out of the list. We then use coerce T v, which uses the decidable equality of ml_type to coerce a value to an expected type but again returns None if the dynamic type representation for v is not T. We can see that cget T r will only succeed on a store st if r is a valid location which contains a value of type T. The implementation of cput is similar to cget.

5.2.3 Extending the interface with laws

We move to the next step of our methodology: from this model, we infer useful laws which we will prove and add to the interface.

Adapting an existing theory As a starting point, we mimicked the array monad, which already contains laws for aput and aget (see Table 6). The only difference is that now types may differ, so we only show rules cgetputskip, cputC and cputgetC, as cputput, cputget, cgetget, and cgetC are identical to their array monad counterparts.

Table 6. Laws adapted from the array monad.

The most interesting change may be cgetputskip. Since our judgments do not include a context part, we cannot guarantee that access to r will be valid for any store. So the left-hand side might fail and is not equivalent to skip. As a first approximation, we replace it with a call to cget, which would exhibit the same failure and ignore its result by composing with skip. We will see later that this can be seen as a separate operation, which checks the validity of a reference. For cputC, there are two changes. The first one is that we have a specific notion of identity for locations, which allows us to compare locations of different types. The second one is that, if we want to check the equality of the updated values, we need to use the John Major equality (McBride & McKinna, Reference McBride and McKinna2004), which can still be written (but not proved) whenever the types differ. The law cputgetC is almost unchanged, but we added a variant of it, cgetputC, where the result of cget is ignored, and which requires no side condition.

Inferring new laws through experimentation We then went on and added rules for cnew. The intuition is that they should be similar to rules for cput, as they define the contents of a reference, but there appears a new difficulty, as there is no way to refer to the location of this reference before it is created. This is only after experimenting with sample programs that we realized that this could be exploited the other way around: if a reference is valid before the creation of another one, then they cannot be equal. And since the only way to check validity is through an operation in the monad, we introduced $\texttt{cchk}~ r$ as an abbreviation for ${\texttt{cget}~r}\gg{\texttt{skip}}$ . We show in Table 7 a non-exhaustive list of laws involving cnew and cchk. Note that some rules are intended to be used in the opposite direction, for instance, cnewchk allows to introduce a new cchk, which cchknewC duplicates under another cnew. The law cchknewE uses the same mechanism to infer an inequation between locations, which can in turn be assumed to prove that continuations $k_1$ and $k_2$ are equal (possibly using rules cputC or cputgetC).

Table 7. Laws for cnew and cchk (excerpt).

5.3 Examples

During this process, we verified a number of example programs (Monae, 2018, file example_typed_store.v): cyclic lists, fibonacci, and factorial, all implemented in OCaml using references, and transpiled using CoqGen. Let us consider the verification in Coq of the following implementation of cyclic lists in OCaml:

Generating the corresponding Coq formalization is as easy as running ocamlc -c -coq cycle.ml.Footnote ¹⁵ We only have to annotate uses of coq_type with the appropriate monad (M or N, while CoqGen only uses M):

Note that rlist, being defined before coq_type_nat, has to take two parameters corresponding to the same type, which are later related by coq_type.

As for the correctness statement, we will only check that the list created by cycle is indeed a cycle of length 2:

We show the derivation of this equality in Table 8, where we use the under tactic (Martin-Dorel & Tassi, Reference Martin-Dorel and Tassi2019) to perform rewriting under $\lambda$ -abstractions provided an appropriate extensionality lemma. Written as a proof script it is just 8 lines long.

Table 8. Derivation of rtl_tl_self.

Freshly inserted subexpressions are underlined. The notation stands for Cons _ _ x y.

We have also proved the same result for cycles of length n. In that case, it requires several lemmas, which together take about 60 lines to prove. We hope to be able to eventually improve scalability.

6.1 Formalization of monads in Coq

Monads have been widely used to model programming languages with effects in the Coq proof assistant.

The main motivation is the verification of programs. For example, monads have been used in Coq to verify low-level systems (Jomaa et al., Reference Jomaa, Nowak, Grimaud and Hym2018), to verify effectful Haskell programs (Christiansen et al., Reference Christiansen, Dylus and Bunkenburg2019), or for the modular verification of low-level systems based on free monads (Letan et al., Reference Letan, Régis-Gianas, Chifflier and Hiet2018). More directly related to the application of Section 4, Sakaguchi provides a formalization of the quicksort algorithm in Coq using the array state monad (Sakaguchi, Reference Sakaguchi2020, Sect. 6.2). His formalization is primarily motivated by the generation of efficient executable code. This makes for an intricate definition of quicksort (e.g., all the arguments corresponding to indices are bounded). Though his framework does not prevent program verification (Sakaguchi, Reference Sakaguchi2020, Sect. 4), it seems difficult to reuse it for monadic equational reasoning (the type of monads is specialized to state/array and there is no hierarchy of monad interfaces).

Monads have also been used in Coq to reason about the meta-theory of programming languages. For example, Delaware et al. (Reference Delaware, Keuchel, Schrijvers and d. S. Oliveira2013) formalize several monads and monad transformers in Coq, each one associated with a so-called feature theorem. When monads are combined, these feature theorems can then be combined to prove type soundness

There are of course formalizations of monads in other proof assistants. To pick one example that can be easily compared with a formalization in Monae, one can find a formalization of the Monty Hall problem in Isabelle/HOL (Cock, Reference Cock2012) using the pGCL programming language (to compare with Affeldt et al., Reference Affeldt, Garrigue, Nowak and Saikawa2021, Sect. 2.3).

The idea to use packed classes (Garillot et al., Reference Garillot, Gonthier, Mahboubi and Rideau2009) to represent a hierarchy of monad interfaces has been experimented in Affeldt et al. (Reference Affeldt, Nowak and Saikawa2019). Packed classes are known to scale up to deep hierarchies of interfaces, but their direct usage involves a mix of techniques that lead to verbose code. The tool Hierarchy-Builder (Cohen et al., Reference Cohen, Sakaguchi and Tassi2020) provides automation to hide technical details from the user. It is also more robust. Indeed, we discovered that our previous work (Affeldt & Nowak, Reference Affeldt and Nowak2020, Fig. 1) lacked an intermediate interface, which required us to insert some type constraints for type inference to succeed (see Hierarchy Builder, Reference Builder2021 for details). Hierarchy-Builder detects such omissions automatically. The better-known type classes have been reported to replace packed classes in many situations, so they might provide an alternative to formalize hierarchies of monad interfaces; they have been used for this purpose to a lesser extent in related work (see, e.g., the accompanying material of Mu & Chiang, Reference Mu and Chiang2020).

The application of Section 4 is a formalization of Mu & Chiang (Reference Mu and Chiang2020) which comes with an Agda formalization as accompanying material. The latter contains axiomatized facts (Saito & Affeldt, Reference Saito and Affeldt2022, Table 1), including the termination of quicksort, that are arguably orthogonal to the issue of quicksort derivation but that reveals practical issues directly related to monadic equational reasoning. We completed (and actually reworked from scratch) their formalization using Monae. To complete Mu and Chiang’s formalization, we needed in particular to formalize a thorough theory of nondeterministic permutations (Saito & Affeldt, Reference Saito and Affeldt2022, Sect. 5.1). It turns out that this is a recurring topic of monadic equational reasoning. They are written in different ways depending on the target specification: using nondeterministic selection (Gibbons & Hinze, Reference Gibbons and Hinze2011, Sect. 4.4), using nondeterministic selection and the function unfoldM (Reference MuMu, 2019a , Sect. 3.2), using nondeterministic insertion (Mu, Reference Mu2019, Sect. 3), or using liftM2 (Mu & Chiang, Reference Mu and Chiang2020, Sect. 3). The current version of Monae has now a formalization of each.

6.2 About monadic equational reasoning

Gibbons and Hinze seem to be the first to synthesize monadic equational reasoning as an approach (Gibbons & Hinze, Reference Gibbons and Hinze2011; Gibbons, Reference Gibbons2012; Abou-Saleh et al., Reference Abou-Saleh, Cheung and Gibbons2016). This viewpoint is also adopted by other authors (d. S. Oliveira et al., 2012; Chen et al., Reference Chen, Hong, Lengál, Mu, Sinha and Wang2017; Mu, Reference Mu2019,a; Pauwels et al., Reference Pauwels, Schrijvers and Mu2019; Mu & Chiang, Reference Mu and Chiang2020) that we have already mentioned in Section 1.

Applicative functor is an alternative approach to represent effectful computations. It has been formalized in Isabelle/HOL together with the tree relabeling example (Lochbihler & Schneider, Reference Lochbihler and Schneider2016). This work focuses on the lifting of equations to allow for automation, while our approach is rather the one of MathComp: the construction of a hierarchy of mathematical structures backed up by a rich library of definitions and lemmas to make the most out of the rewriting facilities of SSReflect.

6.3 About monad transformers

The idea to formalize monad transformers using packed classes was experimented by Affeldt & Nowak (Reference Affeldt and Nowak2020) who formalize Jaskelioff’s theory of modular monad transformers.

Huffman formalizes three monad transformers in the Isabelle/HOL proof assistant (Huffman, Reference Huffman2012). This experiment is part of a larger effort to overcome the limitations of Isabelle/HOL type classes to reason about Haskell programs that use (Haskell) type classes. In the dependent-type theory of Coq, we could formalize a much larger theory, even relying on extra features of Coq such as impredicativity and parametricity (see Affeldt & Nowak, Reference Affeldt and Nowak2020 for details).

Maillard proposes a meta-language to define monad transformers in the Coq proof assistant (Maillard, Reference Maillard2019, Chapter 4). It is an instance implementation of one element of a larger framework to verify programs with monadic effects using Dijskstra monads (Maillard et al., Reference Maillard, Ahman, Atkey, Martínez, Hritcu, Rivas and Tanter2019). Their Dijkstra monads are based on specification monads and are built using monad morphisms. Verification of a monadic computation amounts to type it in Coq with the appropriate Dijkstra monad. Like Jaskelioff’s theory of modular monad transformers, the lifting of operations is one topic of this framework, but it does not go as far as the deep analysis of Jaskelioff (Reference JaskelioffJaskelioff, 2009a ,b; Jaskelioff & Moggi, Reference Jaskelioff and Moggi2010).

There are also formalizations of monads and their morphisms that focus on the mathematical aspects, for example, UniMath (Voevodsky et al., Reference Voevodsky, Ahrens and Grayson2014). However, the link to the monad transformers of functional programming is not done.

6.4 About equational theories for ML with references

The typed store monad, particularly when it is extended with a crun operation to observe a result discarding the contents of the store, is very similar to the ST monad of Haskell (Launchbury & Jones, Reference Launchbury and Jones1994). While we could not find a description of the equational theory of the ST monad per se, there is a line of work on models for state using the same operations. This includes theories for local state, which allow partially or completely discarding the state, and for global state, which do not allow this. The state of the art for local state is work by Kammar et al. (Reference Kammar, Levy, Moss and Staton2017), which builds on work by Staton (Reference Staton2010) to provide a theory for full ground state, where one can put reference cells in the store, but not functions, that is, basically the same restriction as us, but we are currently limited to global state. Note that they do not explicitly provide an equational theory, but their model supports nominal equational reasoning in the style of Staton (Reference Staton2010), that is, using judgments with a context that makes valid references explicit. This is different from our plain equational reasoning, which does not rely on such a context. For global state, Sterling et al. (Reference Sterling, Gratzer and Birkedal2022) recently proposed a model for higher-order state, that is, allowing functions in the store, using synthetic guarded domain theory. They went on to develop a program logic based on it (Aagaard et al., Reference Aagaard, Sterling and Birkedal2023), based on separation logic. It allows equational reasoning to some extent, but again it relies on a separation logic context when expressing equations. Moreover, equations contain extra tick operations, to account for guardedness.