Modular Explicits in OCaml › Functors [abs-functors]

Patrick Ferris

Functors are perhaps the second most prevalent feature of OCaml when it comes to code reuse. In the OCaml sense, a functor is a module that is parameterised by other modules. Set.Make is a functor that requires a module adhereing to the Set.OrderedType interface.

module IntSet = Set.Make (Int)
module StringSet = Set.Make (String)

Functors make it a lot easier to write implementations that depend on a large variety of functionality. Set.OrderedType is relatively tame in this sense, only needing a type t and a compare : t -> t -> int function.

Irmin, on the other hand, has functors that require users to provide Schemas. I have more thoughts about this API design in my Irmin retrospective.

It is important to consider the runtime costs of functors too. Whilst most of the time functors are instantiated at the toplevel, it does not come for free. You can have a play around with js_of_ocamlopt and see the generated output for how functors are applied.

Context

Modular Explicits in OCaml [modular-explicits]

Patrick Ferris

Abstraction, in OCaml, often refers to hiding a particular type's implementation using a signature. For example:

module S : sig
  type t
  val add : t -> t -> t
end = struct
  type t = int
  let add = Int.add
end

In this post, however, I use abstraction to refer to the notion of code-reuse. Using features of the OCaml language to allow one piece of code to be used across different implementations or instantiations of a particular kind of value.

The goal of this post is to eventually discuss OCaml 5.5's modular explicits which is yet another feature that can allow a single piece of code to be used in various situations.

Polymorphism [abs-polymorphism]

Patrick Ferris

The most prevalent kind of abstraction is polymorphism. For example, List.length will work for all lists regardless of what kind of elements the list contains. However, polymorphism requires you to keep the polymorphic part of the type at arm's length. This can lead to suboptimal performance and/or limited usefulness.

List.mem is a good example; in order to be polymorphic List.mem relies on Stdlib.(=), the polymorphic equality operator. In turn, this operator achieves its polymorphism by performing a structural comparison of the runtime representation of its arguments.

A common way to overcome this is to use higher-order functions (functions that take functions as arguments).

# let rec mem ?(eq=Stdlib.(=)) v = function
  | [] -> false
  | x :: xs -> eq v x || mem ~eq v xs
val mem : ?eq:('a -> 'a -> bool) -> 'a -> 'a list -> bool = <fun>
# let mem_int_list = mem ~eq:Int.equal
val mem_int_list : int -> int list -> bool = <fun>

This works well in plenty of cases (List.map, Hashtbl.iter, etc.), however, it doesn't scale well from a user's perspective if the body of the function requires lots of specific functions (e.g. compare, length, pp). At the same time, we want to avoid the precarious duck-typing of something like Python too.

Functors [abs-functors]

Patrick Ferris

module IntSet = Set.Make (Int)
module StringSet = Set.Make (String)

Irmin, on the other hand, has functors that require users to provide Schemas. I have more thoughts about this API design in my Irmin retrospective.

First-class Modules and Existentials [abs-fcm-exist]

Patrick Ferris

Sitting somewhere inbetween polymorphism and functors are first-class modules with existentials. This is a rather advanced use of OCaml's type system to be able to pack together a value of a particular type alongside a module that works with those kinds of values.

type set = Set : ((module Set.S with type t = 'a) * 'a) -> set
let size (Set ((module S), s)) = S.cardinal s

Packaging up integer sets is fairly straight-forward.

# let int_empty_set = Set ((module IntSet), IntSet.empty)
val int_empty_set : set = Set (<module>, <poly>)

From a user's perspective we are now closer to the realm of dynamic typing. Indeed, existentials are the way to do that in OCaml.

# type any = Any : 'a -> any
type any = Any : 'a -> any
# let any v = Any v
val any : 'a -> any = <fun>

Getting back into a typed world often involves some type witness gymnastics or runtime exceptions. Used sparingly, however, it can be very effective particularly when a user is none the wiser about the use of FCMs and existentials. I have made use of this trick to package together Irmin stores with implementations.

You could not, however, simply return the value that was packed away inside the existential.

# let woops (Set (_, s)) = s
Line 1, characters 26-27:
Error: The value s has type $a but an expression was expected of type 'a
       The type constructor $a would escape its scope
       Hint: $a is an existential type bound by the constructor Set.

There is also a runtime cost to the packing (and unpacking) of the module, not to mention the need for the extra allocation to create the existential in the first place. This will likely not be too significant, but is worth considering.

Modular Explicits [abs-modular-explicits]

Patrick Ferris

OCaml 5.5 has module-dependent function types also known as modular explicits. The type of a function can now depend on types that come from a module that is also part of the function definition.

# let set_length : (module S : Set.S) -> S.t -> int =
  fun (module S) v -> S.cardinal v;;
val set_length : (module S : Set.S) -> S.t -> int = <fun>
# set_length (module IntSet) IntSet.empty;;
- : int = 0
# set_length (module StringSet) StringSet.empty;;
- : int = 0

In fact, we can now return values of a particular type that depends on a particular module!

# let empty_set : (module S : Set.S) -> S.t = 
  fun (module S) -> S.empty;;
val empty_set : (module S : Set.S) -> S.t = <fun>
# empty_set (module IntSet);;
- : IntSet.t = <abstr>
# empty_set (module StringSet);;
- : StringSet.t = <abstr>

Or, we can dynamically select implementations and values.

# let with_impl : 
    config:string -> ((module S : Set.S) -> S.t -> 'a) -> 'a = 
  fun ~config fn ->
  match String.lowercase_ascii config with
  | "string" -> fn (module StringSet) StringSet.empty
  | "int" -> fn (module IntSet) IntSet.empty
  | c -> invalid_arg c
val with_impl : config:string -> ((module S : Set.S) -> S.t -> 'a) -> 'a =
  <fun>

This is like a more usable version of the FCM-existential trick, though does require more manual type annotations on functions. For instance, I tried switching out OBuilder's use of existentials with modular explicits:

-type builder = Builder : (module Obuilder.BUILDER with type t = 'a) * 'a -> builder
-
 let log tag msg =
   match tag with
   | `Heading -> Fmt.pr "%a@." Fmt.(styled (`Fg (`Hi `Blue)) string) msg
   | `Note -> Fmt.pr "%a@." Fmt.(styled (`Fg `Yellow) string) msg
   | `Output -> output_string stdout msg; flush stdout

-let create_builder store_spec conf =
+let create_builder :
+  Store_spec.store Lwt.t -> Native_sandbox.config ->
+    ((module B : Obuilder.BUILDER) -> B.t -> 'a) -> 'a Lwt.t =
+  fun store_spec conf fn ->
   store_spec >>= fun (Store_spec.Store ((module Store), store)) ->
   let module Builder = Obuilder.Builder (Store) (Native_sandbox) (Docker_extract) in
   Native_sandbox.create ~state_dir:(Store.state_dir store / "sandbox") conf >|= fun sandbox ->
   let builder = Builder.v ~store ~sandbox in
-  Builder ((module Builder), builder)
+  fn (module Builder) builder

I think the code is more pragmatic; there is no longer an indirection via a type called builder. The extra type annotations do add a little noise. Roll on modular implicits.

Irmin Retrospective [irmin-retro]

August 7, 2025
Patrick Ferris

Irmin is an OCaml library for building branchable and mergeable data stores. The data is mergeable in the sense of mergeable replicated data types.

I have been using Irmin for over five years to build different kinds of interesting data stores including:

A simple markdown-based note-taking web application.
A content-addressed database.
Mentoring an intern who worked on Irmin in the browser.
Most recently, an Irmin-backed shell session manager.

I was asked to provide some feedback recently on Irmin, so I thought writing a little retrospective here would be a good way to do that. The remit for the retrospective was about improving Irmin, so the content is focussed on pain points and areas of improvement.

(* An in-memory Irmin store *)
module Store = Irmin_mem.KV.Make(Irmin.Contents.String)

What is Irmin?

August 7, 2025
Patrick Ferris

Irmin, at its simplest, is a key-value database. Users associate keys with values and can query and update these bindings.

Additionally, this database supports versioning. This means independent snapshots of the database can coexist and users can switch between them and update them without fear of interfering with other versions.

Different versions of the database can be combined by merging. When you set up your instance of an Irmin database, you also provide it with a merge function.

# #show_type Irmin.Merge.f;;
type nonrec 'a f =
    old:'a Irmin.Merge.promise ->
    'a -> 'a -> ('a, Irmin.Merge.conflict) result Lwt.t

Design and API

August 7, 2025
Patrick Ferris

Irmin's API is very git-inspired. There is a large overlap of shared vocabulary and concepts: repositories, branches, commits, heads etc.

Probably the most confusing aspect of this is the notion of a Store. When I was describing Irmin above, I used the term database to help distinguish between some of these concepts. In Irmin's documentation, it is used for multiple related (but different) concepts. In "Creating a Store" stores refer to the entire database, whereas in the Irmin API docs we have that:

There are two kinds of store in Irmin: the ones based on persistent named branches and the ones based temporary detached heads.

For Irmin library users, a Store.t can be thought of as a checkout of the database at a particular revision. This may be from a branch or a specific commit.

# Store.of_branch;;
- : Store.repo -> string -> Store.t Lwt.t = <fun>
# Store.of_commit;;
- : Store.commit -> Store.t Lwt.t = <fun>

The overloading of the term is confusing. I think it leaves users unsure about what other people might mean when they say "store". Being careful with these terms, and the contexts in which they are used, would help avoid this confusion.

Module and Functor Soup

August 7, 2025
Patrick Ferris

Undoubtedly for a majority of use-cases and users, Irmin is over-functorised. Nearly every module requires that you must apply some functor to access any useful code. In general, a user will have to interact with the Schema module when describing the types they want to instantiate their store with.

To counteract this, Irmin has plenty of KV modules that provide a Make functor that only requires a user to provide a suitable content module for their store (i.e. something that provides a type, a runtime representation of that type and a merge function).

# #show_module Irmin_mem.KV;;
module KV :
  sig
    type endpoint = unit
    type metadata = unit
    type hash
    type info = Store.info
    type ('h, _)contents_key = 'h
    type 'h node_key = 'h
    type 'h commit_key = 'h
    module Make : (C : Irmin__.Contents.S) ->sig ... end
  end

I think it is fair to say the documentation is hard to follow as it is a module and functor soup. For example, looking at irmin.3.11.0, starting at the toplevel documentation page our path to finding this paricular module and functor is as follows:

We jump into Irmin_mem from the nicely written landing page.
We scroll down to find the KV module.
We now make sense of the module's signature by following the KV_maker link.
We see a Make (C : Contents.S) : sig ... end at the end of the module, and we navigate through that.
Finally we have come to our journey's end, and find the schema module with type constraints like type Branch.t = string.

There is a big assumption there that you know what the Schema module is telling you and how it relates to your "store".

There is a counter-argument here, in that Irmin is incredibly flexible in terms of what you can use as types for your keys, branches, hashes etc. I was quite easily able to produce Irmin stores that use CIDs (self-describing content identifiers) for example.

I think there is a middle ground. For Irmin to be usable it needs to reduce the complexity of the API. The complexity is due to, in large part, over-functorisation. If the functors cannot be removed then perhaps better documentation or more introductory libraries like irmin-containers would be helpful. Perhaps a standalone library that acts as an interface to Irmin stores would be helpful. I find myself time and again implementing something like that.

Backends Galore

August 7, 2025
Patrick Ferris

Irmin has plenty of backends including a git-compatible one, a MirageOS backend, an in-browser IndexedDB backend and even a FoundationDB backend.

Irmin needs to have fewer, better tested backends. Of course, some of these are likely driven by funding and use-case specific details. However, I think by focusing on a few key backends and striving for solid performance but also strong consitency guarantees, Irmin would become a more viable candidate for potential users. I also believe the browser backend plays a key part to making this work in order to facilate local-first applications.

Syncing Remote Stores

August 7, 2025
Patrick Ferris

The synchronisation mechanisms in Irmin are powerful, but often the API is very confusing. For example, with the git-compatible Unix backend, nested deep in the documentation is the function required to create a remote endpoint. Once they have found this function, using it is not easy as it requires them to learn about the Mimic.ctx, which is an abstraction of the networking stack!

Do Fewer Things and Do Them Well

August 7, 2025
Patrick Ferris

Irmin is simultaneously a database that supports: content-addressing, merging, key-value lookup, branches, transactions, complete OS portability etc. I think, in short, it tries to do too many things and comes up short on some of them in ways that really matter.

When building the content-addressed database I needed strong guarantees about some atomic actions to perform on the underlying store. For example, setting the value and accessing the commit associated with it which was not possible with the API at that time in an atomic way. This kind of missing functionality is probably only understood after users stumble across it, but it also makes the library feel less focused and ready for production use-cases.

Documentation

August 7, 2025
Patrick Ferris

It will probably come as no surprise that one of the main limitations of using Irmin is the lack of documentation and tutorials. This is a particular pain point as the API is not very straightforward.

A while back, I started an Irmin book intending to help document the kinds of things real-world users would need in order to use Irmin in earnest. For example: ways to deal with type migrations or primers on runtime types. I still believe this sort of work would be invaluable, but there is a large cost to completing it, and it is not clear if there is enough interest in the project to warrant such an effort.

The tutorials on the irmin website are still good starting points for most new users. But they quickly lack the depth for real-world scenarios.

Feature Wishlist

August 7, 2025
Patrick Ferris

What follows are additional ideas for improving Irmin.

Heterogeneous Stores

August 7, 2025
Patrick Ferris

For all of [Irmin]'s abstraction and functorisation, there is a very clear missing feature for lots of first-time users of the library: you can only store values of a single type.

This leads to a few common workarounds:

Storing a serealised version of your values, essentially escaping the type-system and implementing a form of dynamic typing.
Growing your value to hold lots of different types via some large variant type.

Both of these options are feasible and have been used in practice. However, they are workarounds. A long time ago CraigFe created an RFC for heterogeneous stores, which I think about a lot. The main idea is to augment Irmin paths (keys) to be GADTs that carry type information about the kinds of values they access (similar to heterogeneuous variants of other data structures). Something like this alongside a simplified API would make Irmin more appealing as a library for persistent data storage.

Real-world Retrospectives

August 7, 2025
Patrick Ferris

This echos some thoughts from the Documentation section. There are some very real-world Irmin use-cases out there. For example, for a long time (I'm not sure if this is still the case) parts of the Tezos blockchain were using Irmin which uses the irmin-pack backend. Does this make irmin-pack the best tested backend and perhaps should be the default backend for new users? Or is it hyper-specific to the Tezos use case? There are blogs on tarides.com about the irmin-pack backend, but they might be outdated and should not be the first place to find advice on which Irmin backend to use.

Active Development and Engagement

August 7, 2025
Patrick Ferris

As far as I know, Irmin was at the forefront of technologies that have come to be described as local-first. There is a growing interest in this area (particularly as it acts as a counter-argument to an increasingly online, centralised model). I highly recommend reading Ink & Switch's essay on the matter. And it would be great to see more research via Irmin at things like the lofi unconference and the PLF workshop at SPLASH 2023!

Thank you for reading! And thank you to all the Irmin contributors. I hope this might be useful in the future for building the next-generation Irmin!

reference. Irmin [irmin]

https://irmin.org

Irmin is an OCaml library for building mergeable, branchable distributed data stores.