% Thoughts for October 27, 2012
% Michael Stone
% October 27, 2012
* API Design
* ["Designing Hypermedia APIs"](http://designinghypermediaapis.com/)
* ["The H-Factor"](http://www.amundsen.com/hypermedia/hfactor/)
* ["Using typed links to forms"](http://iansrobinson.com/2010/09/02/using-typed-links-to-forms/)
* ["Siren: a hypermedia specification for representing entities"](https://github.com/kevinswiber/siren)
* [discussion group](https://groups.google.com/forum/#!forum/siren-hypermedia)
* Abstract syntax vs. concrete syntax vs. semantics vs. constraints:
* [mnot: "Profiles"](http://www.mnot.net/blog/2012/04/17/profiles)
* [Google Service Discovery Documents](https://developers.google.com/discovery/v1/reference/apis)
* Kernel stuff
* ["EPOLL_CTL_DISABLE, epoll, and API design"](https://lwn.net/Articles/520198/)
* ["Why kernel-space sucks"](http://man7.org/conf/lcna2012/Why_kernel_space_sucks-2012-08-29.pdf)
* Path numbering
* Problem: [sum-of-products types](http://en.wikipedia.org/wiki/Algebraic_data_type),
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](http://www.inference.phy.cam.ac.uk/itprnn/book.pdf),
and [succinct data structures](http://en.wikipedia.org/wiki/Succinct_data_structure)
(see also [Vitter](http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf))
* Especially cute example: [Linear Quadtrees](http://www.acm.org/conferences/sac/sac2000/Proceed/FinalPapers/DB-27/node3.html)
* Results in [parallel-friendly structures](http://gcc.gnu.org/svn/gcc/branches/cilkplus/README.cilk)
([installation instructions](http://groups.csail.mit.edu/sct/wiki/index.php?title=Cilk_Plus_Installation_Guide)); i.e., insertion == sorting
* For quadtrees, path numbers can be calculated directly from [fixed-point](http://en.wikipedia.org/wiki/Fixed-point_arithmetic) representations of coordinates.
* [GCC fixed-point types](http://gcc.gnu.org/onlinedocs/gcc/Fixed_002dPoint.html)
* Path numbers can be computed via [bithacks](http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious)
* Ability to trade space for time: path numbers are permutations of the bits of the coordinates.
* [Okasaki](http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504)
* [Samet](http://www.amazon.com/Foundations-Multidimensional-Structures-Kaufmann-Computer/dp/0123694469)
* ["Intel IA-64 and IA-32 Architectures Optimization Reference Manual"](http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html)
* 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.
* [presheafs](http://en.wikipedia.org/wiki/Presheaf_%28category_theory%29)
* ["Cyberspace is not a warfighting domain"](http://moritzlaw.osu.edu/students/groups/is/files/2012/02/4.Libicki.pdf)