typegist design notes

Representation

The type representation is similar to Balestrieri et al.'s low level view (§2.3.4). However the representation is not extensible, a few case are dropped, some representations are unified, some specializations are added.

Here are a few salient points:

• Tuples, records and variant cases are distinguished at the top-level but they all share a single representation: a product of fields representation. This economical uniformity benefits both processors and the programmer's mind.
• The product of fields representation does not go through tuples, it stores a deconstruction of the type into its (ordered) fields and a constructor to recreate it from its fields. Thus rather than providing conversion to/from a multi-dimensional tuple, the user provides field projectors and a constructor that creates values from the fields. This representation is rather natural and a good fit for abstract records since APIs usually already provide a constructor and field accessors. It is however more painful for variant cases which are usually deconstructed via pattern matching, having a quick way of devising these projectors would be useful.
• The representation of variants is different from Balestrieri et al. Each variant case is a product of fields and a constructor name. We store an ordered list of cases and one function that returns an index list of cases given a value (instead of one function per case that tests if a value has the case).
• The representation of abstract types can expose more than one public representation (or none). Public representations have a version label which allows to interact with systems still using the previous representation.
• Balance between specialisation and generalisation. We have a few cases that represent OCaml types directly. For example Typegist.Type.Gist.Variant_like.t, has one case for arbitrary variants and other cases for common Stdlib variant types like lists. If there's no interest in the specialisation a generic view can easily be obtained with Typegist.Type.Gist.Variant_like.to_variant. Similar schemes are provided by Typegist.Type.Gist.Map_like.t, Typegist.Type.Gist.Array_like.t. Scalar values are all grouped under Typegist.Type.Gist.Scalar.t for which a few generic operations are provided in Typegist.Type.Gist.Scalar.
• The representation is a closed variant. Not really convinced by this aspect of the design in Balestrieri et al. Extensibility creeps into all processor which need an optional argument for dealing with extensions and entail runtime errors on unsupported extensions. Having a closed core with a view and breaking at compile time the rare times a case will really need to be added seems a better course of action.

Metadata

The representation is decorated with type-indexed existential metadata. This allows generic functions to be customized. See for example the keys in Typegist.Fun.Generic. We use an ad-hoc type level defunctionalization of Yallop et al. for two parameters to allow metadata dictionaries to be polymorphic on the type of represented types and fields (the reason why we have to parameters: one for the product type and another for the field type). Two remarks:

• You really do want metadata on fields. We tried to push the metadata in the gist of the type of the field but it becomes messy and somehows denatures what a gist is for (a type definition). For example you end up modifying a standard Typegist.Type.Gist.int to add metadata for the field which is a bit weird.
• It's unclear whether you really want the two parameter dependence (the product type and the field type) for metadata dictionaries. We do have an example in Jsont_typegist where a member map can be specified to replace the derived one, but arguably we could have done without: only the accessor uses the product type but it's not super interesting to override that, in fact formally you'd rather reuse the type gist one. Also for Typegist.Fun.Generic.Fmt we ended up expressing it on the product so that Typegist.Fun.Generic.Fmt.ignore can elide the whole binding for records.

Regarding metadata placement, we went through a couple of designs before settling on this one. But those were rather the result of a confused mind about what type gists were really:

1. Have the metadata everywhere in the nodes and the (leaves of the) leaves of the representation. This is painful for processors which have to do the lookups in every leaves. It also increases ambiguities for users and processors as to where metadata should be specified; there's too many places where it can be specified.
2. A single case Meta of 'a Meta.t * 'a t in the toplevel expression variant (it seems that's what LexiFi does). This makes less lookups but it means that gist processors need to thread and maintain a metadata context and make sure they don't apply to the wrong gist.
3. Using a classical AST approach where you have a type for type expressions and a type for an expression decorated with metadata.

In the end we went with 3. since this allows us to also add a couple of things we ended up needing like a Type.Id on every expression node to allow to identify them for Typegist.Type.Gist.rebinding and all sorts of other munging operations you may be interested in doing to get coherent gists.

Compiler or metaprogramming ideas

Assuming you are devising type gists by hand or macros or mixture thereof, a few meta protractions could be useful to have. If we have source-level macros then you could streamline gist definitions while retaining their flexibility if you need to. Most type gist definitional patterns can be seen the cookbook blueprints.

1. DRY naming protractions. Stuff to access the names you define as strings in the representation so that there is a single source of truth rooted in the OCaml type definition. That's mostly constructor names, record field names, type names and module names (__MODULE__ is rather __COMPILATION_UNIT__ and given the terrible mess dune does to source files it would likely not be that useful).
2. Product constructors. Given a tuple, record or variant case be able to reify a function that constructs it in the order of its fields. It seems we might get something for variants at least.
3. Fields. A way to enumerate the fields of a tuple, record or variant case. Access their name, type and a function to project them from the product.
4. Cases. A way to enumerate the cases of a variant in order (and in turn the fields of their product see last point)