Looking for Examples of Different Modules Implementing the Same Signature

Community
1

Hi! I’m working on a tool, Mica, which automates differential testing for two OCaml modules implementing the same signature (e.g. finite sets implemented using lists & AVL trees respectively). Specifically, Mica uses QuickCheck to test if two modules are observationally equivalent.

We demo’ed Mica at the ICFP '23 Student Research Competition (poster), and we’re now hoping to try out a new version of Mica on modules taken from real-world OCaml code.

If you know of real-world examples where the same module signature is implemented differently across different modules, please comment below! Alternatively, if you know of pairs of OCaml libraries that have roughly the same functionality (e.g. Yojson & Ezjsonm both provide similar JSON-handling functionality), that also works!

We’re hoping to compile a list of modules/libraries that have roughly the same functionality, such as:

Thanks!

2

One example is the signature of a hash algorithm in ocaml-nocrypto/src/nocrypto.mli at ed7bb8d911dc340e36d85d335d9edb8339f0932d · mirleft/ocaml-nocrypto · GitHub

And all the modules which implement it below: ocaml-nocrypto/src/nocrypto.mli at ed7bb8d911dc340e36d85d335d9edb8339f0932d · mirleft/ocaml-nocrypto · GitHub

1 Like
3

Not exactly sure if this is what you want but I’m working on a library that implements numpy’s random module bitgenerator interface here: GitHub - zoj613/bitgenerators: Psuedo-random number bitgenerators for OCaml users.. There are several modules of psuedo-random number generators implementing the same interface outlined here: bitgenerators/lib/common.ml at 79ff5defe360b7a5c513de505f95594fad02f948 · zoj613/bitgenerators · GitHub

1 Like
4

In dolmen I have a custom implementation of maps of strings using a trie (inspired by this paper). These can easily be compared to the maps from the stdlib.

More specifically:

  • I define a common reduced interface for maps here (note that this lacks quite a few common functions, such as remove that I don’t use in that project for now)
  • The custom Map over strings is implemented here
  • I have a module to wrap and expose maps with the correct interface here
  • I have some qcheck tests to verify that my custom implementation is correct by comparing it to the maps from the stdlib
1 Like
5

Thank you all, much appreciated! These are all great examples – I think @zozozo’s Map implementation might be the easiest to test using our tool but I’ll also try the other!

1 Like
6

Good to know ! If you have any questions/remarks about my implementation, don’t hesitate !

7

You could perhaps compare

  • Set.Make(Char) (i.e. the generic Set implementation in the standard library instantiated for characters) with
  • Charset (a specialized implementation of sets of characters that uses intrinsics and other optimizations)
2 Likes
8

Thanks Jeremy! That reminds me, I should also look at your ocaml-integers library and see how it compares to Int32 / Int64 modules in the standard library.

9

Another one to consider: safe-string-buffer closely follows the interface of the standard library Buffer module, but uses a different representation (a list of immutable string values rather than a single mutable bytes array).

1 Like
10

Thank you! Looking forward to trying it out.