API Design

“Siren: a hypermedia specification for representing entities”

Abstract syntax vs. concrete syntax vs. semantics vs. constraints:

Kernel stuff

Path numbering

Problem: sum-of-products types, are great but, when implemented via graphs of pointers to a struct of fields, have poor data density + locality of reference

Solution: observe that, given a value of some some-of-products type, there is a unique path to every field of that value. Number these paths. Then invert the representation: instead of storing pointers to a struct of fields, add a “path number” field to the struct and then pack the structs.

General technique to improve data density + locality of reference

Intimately related to information theory, and succinct data structures (see also Vitter)

Especially cute example: Linear Quadtrees

Results in parallel-friendly structures (installation instructions); i.e., insertion == sorting

For quadtrees, path numbers can be calculated directly from fixed-point representations of coordinates.

Path numbers can be computed via bithacks

Ability to trade space for time: path numbers are permutations of the bits of the coordinates.

“Intel IA-64 and IA-32 Architectures Optimization Reference Manual”

- Appendix C gives reference latencies and throughputs (i.e., issue rates) for the complete instruction set

Functors, categories, embeddings!

Media-types and profiles accomplish the same results, which are to communicate a pull-back from syntax to semantics. The point of the profiles is that we can have multiple such pull-backs.