LoCal: A Language for Programs Operating on Serialized Data
TL;DR: They created a functional programming language which uses an in-memory representation of data structures that avoids pointers, instead organizing object trees in preorder, much like most serialization formats would use.<p>To support access patterns that aren&#x27;t strictly preorder, the compiler (optionally?) injects offsets into the structure, to allow &quot;skipping over&quot; branches to get to the one you want.<p>Apparently, any value can optionally be a pointer, in order to allow for aliasing. But this is the exception rather than the norm. Aliasing is of course critical to allow data structures to be updated -- in the FP copy-on-write sense, where you clone and update all objects on the path from the root to the modified one.<p>This seems to be a nice fit for functional programming and is pretty cool in that context. I suspect it would be a lot more difficult to take this approach in an imperative model.<p>Amusingly, in a way this is the opposite of what Cap&#x27;n Proto does (disclosure: I&#x27;m the author of Cap&#x27;n proto). LoCal is a programming language whose in-memory representation looks like a serialization format (preorder; no pointers). Cap&#x27;n Proto is a serialization format which looks like an in-memory representation (arbitrary order; using pointers).<p>They have a table of benchmarks showing LoCal being faster than Cap&#x27;n Proto. It would be nice to see code for these benchmarks. It sounds like the test case is a binary tree. This is an almost pathologically pointer-heavy use case, and as a result would tend to show LoCal in the best possible light and Cap&#x27;n Proto in the worst. Cap&#x27;n Proto will spend 8 bytes on every pointer; LoCal will spend zero.<p>I take issue with the &quot;treeInsert&quot; benchmark, in which the paper claims Cap&#x27;n Proto is O(n) whereas LoCal is O(log(N)). It sounds like for some reason the authors decided they needed to copy the entire Cap&#x27;n Proto message before they could mutate it. Cap&#x27;n Proto supports in-place mutation, so should be O(log(N)) reads and O(1) writes (compared to O(log(n)) reads and writes for LoCal). (Admittedly in-place modification of files loaded from disk is tricky to set up at present, but this is an implementation limitation, not a theoretical one -- and it&#x27;s not clear to me that this test was loading files from disk anyhow.)<p>Maybe they decided that a complete copy was needed in order to get FP copy-on-write semantics, but that&#x27;s not really true either. In principle, it would be possible to create a Cap&#x27;n Proto implementation that can start from a file on disk and modify it in an object-by-object copy-on-write way, appending new&#x2F;modified objects to the end of the file in order to avoid destroying any information. At present this hasn&#x27;t been implemented, but that&#x27;s largely because no one has had a pressing need for it, to my knowledge.