Our big software project uses Git (the version control system) in a CVS mode, with a single central repository to which we push commits (after they pass the check-in test suite). This can be good, because it forces us to fix small but annoying things -- like setting the correct e-mail address! I was testing on a different machine than my usual development workstation; I made some commits there, and then pushed to my workstation's local repository (Git shines for stuff like this). Then, I activated the check-in tests, but the push failed: my e-mail address wasn't set! (The tests check for that -- handy!)
While I had set my e-mail address for Git correctly on my workstation, I hadn't set it on the other machine. There were seven commits sitting on my workstation (where I run the check-in test suite) with the wrong e-mail address. Here's how I started the fix. First, I ran
$ git rebase -i HEAD~7
which let me fix up the last 7 local commits. "-i" means "interactive," so Git fired up a text editor and let me decide which commits to change (and how). I then repeated the following three tasks seven times:
$ git commit --amend --reset-author
(Edit the commit message -- no author e-mail address here, but it gets fixed due to "--reset-author")
$ git rebase --continue
That fixed it! There's probably an easier way, but I was pleased.
11 October 2010
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.
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.
Subscribe to:
Posts (Atom)
