package mugen

  1. Overview
  2. Docs
Universe levels and universe polymorphism


Dune Dependency






This package implements the generalization of Conor McBride’s crude but effective stratification. The theory behind the design is discussed in the POPL 2023 paper “An Order-Theoretic Analysis of Universe Polymorphism.”

Published: 29 Dec 2022



# ♾️ mugen 無限: Universe Levels

A vast generalization of [Conor McBride’s crude but effective stratification]( We replace natural numbers with what we call _displacement algebras_, the minimum algebraic structure to use McBride’s scheme. Our POPL 2023 paper [“An Order-Theoretic Analysis of Universe Polymorphism”]( explained the theory behind our design.

## Stability

⚠ The API is experimental and unstable. We will break things!

## Components

- [Mugen.Shift]( example displacement algebras
- [Mugen.ShiftWithJoin]( example displacement algebras with joins
- [Mugen.Syntax]( syntax of universe levels
- [Mugen.Semantics]( smart builders and comparators

## Philosophy and Beliefs in this Experiment

1. The distinguished level variable for top-level definitions should be explicit in the core language for clean semantics. (It can remain implicit in the surface language.)
2. One-variable universe polymorphism with cumulativity is enough. Typical ambiguity (as in Coq) and multi-variable universe polymorphism (as in Agda) are overkill.
3. It is convenient to have the top level for type checking. However, end users should not be allowed to write the top level, and shifting the top level is forbidden.

## Displacement Algebras

In Conor McBride’s notes, it was noted that any class of strictly monotone operators on levels closed under identity and composition will work. We codified such a class as a displacement algebra. The classic displacement operators may be recovered by using the following module with non-negative numbers:

- [Mugen.Shift.Int](

## How to Use It

### Installation

You need OCaml 4.13 or later. Here is the fastest way to install the library with OPAM 2.1:

opam pin mugen git+

### Example Code

module I = Mugen.Shift.Int
module M = Mugen.Syntax

(* The type of universe levels, using integers as displacements and strings as variable names. *)
type ulevel = (I.t, string)

(* The level representing "x + 10" *)
let l : ulevel = M.Free.(shifted (var "x") (I.of_int 10))

### Documentation

[Here is the API documentation.](

Dependencies (2)

  1. ocaml >= "4.13"
  2. dune >= "2.0"

Dev Dependencies (2)

  1. odoc with-doc
  2. bwd >= "2.1" & with-test

Used by





Innovation. Community. Security.