Tpf — minimalist datatype-generic programming

%%VERSION%%

Tagless/trivial polytypic functions (Tpf) is a simple and idiomatic library for datatype-generic programming in OCaml.

Generic programming is all about not writing the same old equal again.

Datatype-generic (or polytypic) programming is solving this at the language level.

Tpf allows you to write functions that work on a wide range of unrelated data types. Such functions require only the base language, need no runtime, and seamlessly interoperate with the rest of OCaml. Tpf works in the same stage as the rest of your program, and doesn't rely on meta-programming.

Tpf is closely related to other well-known datatype-generic approaches. It shares the underlying data model with SYB, and uses the spiny encoding. This is a manifest representation, like the one GHC.Generics use. It arises as an adaptation of approaches like these to a language without overloading, giving it an idiomatic flavor, and lending the name.

Tpf has no dependencies and is distributed under the ISC license.

Installation

Tpf can be installed with opam:

opam install tpf
opam install tpf-ext       # Install the optional support for third-party libs
opam install tpf-deriving  # Install the optional PPX deriver

If you don't use opam consult the tpf.opam file for build instructions.

Documentation

The documentation and API reference is automatically generated by odoc from the interfaces. It can be consulted online.

Library layout

Tpf contains several optional libraries and sub-libraries:

• opam package tpf contains the core library.
• opam package tpf-ext adds support for various third-party libs.
• opam package tpf-deriving contains the generic deriver. It is worth pointing out that Tpf can be used without PPX.

Quick start

Consult the quick start section of the documentation.

Performance

Tpf is glacially slow...

You can write a generic function that, for example, counts the number of recursive occurrences, and use this function to measure the length of a list.

It takes about 5x the time it takes List.length.

Of course it does. List.length compiles to a 4-instruction loop. The Tpf version reconstructs the entire list (albeit lazily), and explores every field of every block in it.

... and Tpf is lightning fast!

If you use the industry-leading PPX-based Sexplib deriver, ppx_sexp_conv, and compare the performance of derived conversion functions (sexp_of_tweedledum / tweedledum_of_sexp) to the performance of a Tpf-based generic version, the ratio is about 1.25. Generic version is 25% slower.

If you compose these conversion functions with something that interacts with the actual bytes, the overall performance hit of using generics drops to just below 10%.

Incidentally, most attempts at writing a generic printer will end up being faster than hand-written printers, as CamlinternalFormat.make_printf is a formidable opponent.

Tpf is usable.

Clearly, whether the overhead introduced by generic functions is significant depends entirely on what they are doing. And whether this ends up being prohibitive, depends entirely on your use-case.

It doesn't cost much to try.

Compared to alternatives

PPX deriving

The use cases of ppx_deriving overlap with those of Tpf, even if the two approaches are meant to do different things.

• Tpf is generally slower, especially when consuming values.
• Tpf is less flexible, as it can not extend the language.
• Tpf does not care about hygiene.
• Tpf requires no tooling or external support.
• Tpf makes it infinitely easier to write generic functions.

OCaml SYB

(As seen here.)

• Tpf does not require a patched compiler.
• Tpf has no concept of overloading, so the user is responsible for manually specifying what to do at contained types.
• Tpf is faster because the manifest representations and internalized recursion turn out to be.
• Tpf is typically easier to write generic functions for. But their expressivity is still exactly the same.

Generic programming in OCaml

(As seen here.)

Tpf is tagless. It strictly avoids type reflection, which leads to a number of differences that make Tpf feel more natural to an OCaml programmer.

• Tpf generic functions are parametrically polymorphic.
• Tpf does not essentially depend on PPX extension points.
• Tpf does not import its private overloading semantics into your programs.
• Tpf does not hide the fact that a particular function is not implemented at a particular type from the type checker.
• Tpf is decidedly minimalist.