data structure lockin

[Anil Madhavapeddy <anil@xxxxxxxxxx>]

There's a great talk by Dan Bernstein about data structure lockin that's 
worth reading through here:
http://cr.yp.to/talks/2012.10.22/slides.pdf

> Inadequate modularization has locked us into many bad
> data-structure decisions.
> 
> “We propose instead that one begins with a list of difficult
> design decisions or design decisions which are likely to
> change. Each module is then designed to hide such a decision
> from the others.”
>
> —David L. Parnas, “On the criteria to be used in decomposing
> systems into modules,” 1972

Modules are one area where OCaml rules supreme, but our libraries
are currently only sporadically functorised across data structures.
This is primarily because polymorphic hashtables are quick and
easy, but luckily refactoring them is also quite easy. Something
I've been thinking about is to build a quick-test system for
stressing data structures in interesting ways, in order to expose
weaknesses such as hash collision denial-of-service attacks well
in advance of anything actually being deployed.

See this for another excellent blog post about similar model-checking
approaches to the problem, but this time for distributed systems:
http://blog.incubaid.com/2012/10/25/caulking-your-distributed-algorithm-implementation/

-anil