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”
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.