04 October 2010

Larval sparse matrices?

John Rose's post on "larval objects in the JVM" suggests a type distinction between "larval" and "adult" objects.  Larval objects are mutable, suitable for in-place updates and for use as scratch computation, but are not safe for sharing by multiple threads in the same shared-memory space.  Adult objects are immutable and safe to share in parallel, but "changing" them requires copying, which can be expensive.  His examples mainly involve small objects, like complex numbers or dates.  However, he does suggest a "large-scale" example of a database, where the default state is immutable ("adult"), but a mutable API can be made available by request.

This pattern of a "larval" initialization stage -- too complex and incremental to handle in a constructor -- followed by a "publish" command (we call it "fillComplete") that transforms the data structure into its "adult" state -- is more or less how sparse matrices are used in practice.  The data for the sparse matrix is processed in "element" form (more or less equation by equation), and then "assembled" into the optimized data structure.  Changing the optimized final data structure can be expensive and may require re-optimization.  Thus, we like to think of it as immutable when optimized.

The problem is, the sparse matrix API contains operations for the "larval" stage, which are either invalid or expensive when the matrix is in its "adult" stage.  Rather than discouraging users from doing the wrong thing, it would be nice for the API to forbid invalid operations syntactically (not by throwing an exception and frustrating new users with a mysterious error message), and also make clear which operations are allowed but undesirable due to their cost.  Making it syntactically harder to do suboptimal things is a good way to intimidate nonexpert programmers from doing them!

John mentions the library solution to this problem: "builder" objects or functions, like Java's StringBuilder.  They take as input some number of updates, applied incrementally.  When the user signals that all updates are done, they produce a "final" immutable object.  In the case of sparse matrices, that would mean users can only call mutating methods on the "SparseMatrixBuilder" object.  To mutate a "finished" sparse matrix, they would have to request a "builder."

The problem with this approach is the ability to request a builder, after the original completion of the immutable object.  It means that immutable objects can change state.  It also means that the immutable object (which is now only immutable in terms of its API) and the mutable "view" coinhabit the same scope.  Now the state of the "immutable" object depends on the semantics of view updates.  Do they happen as soon as the update methods are called?  (Simultaneity doesn't mean much in the context of multiple threads.)  Do they get accumulated and applied in batches?  Do they involve an asynchronous call to some remote compute device, like a GPU?  Programmers shouldn't be depending on these sorts of semantics.  It's better to avoid the mess and forbid changing immutable objects back into mutable ones, or return to the original solution and provide only a single object type with immutable and mutable states.

What's missing here is a "rebinding syntax" that prevents programmers from accessing the supposedly immutable object while it's in a mutable state.  This is a good use case for the "WITH-" Lisp idiom, or for Python's context guards:  the mutable view created by the "with" isn't allowed to escape its scope.

No comments: