Created
March 5, 2026 16:30
-
-
Save andrejbauer/99b7b0e28544d6cd7d361d3908d13f81 to your computer and use it in GitHub Desktop.
How to implement in OCaml a trusted kernel that can also expose its internal structure safely
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (* We want to implement a trusted kernel which is the only module that can | |
| produce values of some abstract type jdg, but at the same time we want to be | |
| able to expose the values of type jdg so they can be inspected, tested, etc. | |
| In some cases OCaml private types will do the job, but not always. Here is a | |
| solution that uses OCaml modules. The idea is as follows: | |
| 1. Implement an untrusted transparent kernel which makes everything visible. | |
| 2. Using signatures, create a trusted opaque version of the transparent kernel | |
| with an additional expose function that maps opaque values to non-opaque values. | |
| The following modules are easy to distribute into several files as follows: | |
| * Untrusted -> untrusted.ml | |
| * UnitTest -> unitTest.ml | |
| * TRUSTED -> trusted.mli | |
| * Trusted -> trusted.ml | |
| *) | |
| (* A non-trusted transparent implementation of the kernel. *) | |
| module Untrusted = | |
| struct | |
| type jdg = | |
| | BaseTy | |
| | ArrowTy of jdg * jdg | |
| let base = BaseTy | |
| let arrow s t = ArrowTy (s, t) | |
| end | |
| (* Unit tests work with the untrusted kernel because | |
| they need access to the internal structure. *) | |
| module UnitTest = | |
| struct | |
| open Untrusted | |
| (* We might want to keep these out of the kernel. *) | |
| let rec size = function | |
| | BaseTy -> 1 | |
| | ArrowTy (s, t) -> 1 + size s + size t | |
| let rec height = function | |
| | BaseTy -> 1 | |
| | ArrowTy (s, t) -> max (height s) (height t) | |
| (* A sample test *) | |
| let height_leq_size j = (height j <= size j) | |
| end | |
| (* The trusted opaque kernel is the untrusted one made opaque by a signature, | |
| with an additional function that exposes the abstract values as transparent | |
| non-trusted ones. | |
| *) | |
| module type TRUSTED = | |
| sig | |
| type jdg | |
| val base : jdg | |
| val arrow : jdg -> jdg -> jdg | |
| val expose : jdg -> Untrusted.jdg | |
| end | |
| module Trusted : TRUSTED = | |
| struct | |
| include Untrusted | |
| let expose t = t | |
| end | |
| (* Example usage *) | |
| let _ = | |
| let open Trusted in | |
| (* create a trusted value j *) | |
| let j : Trusted.jdg = arrow base (arrow base base) in | |
| (* Run a unit test on the exposed j *) | |
| assert (UnitTest.height_leq_size (Trusted.expose j)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment