% 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)