The essence of a zipper is a “one-hole context” – the context of a value in some structure, together with that value – and a means of moving from one one-hole context to another. What do we mean by a one-hole context? That structure you obtain by pulling out a single element in a structure, and replacing it with a “hole”, a placeholder. A variable, if you like. For example, in the algebraic expression ax2 + bx + c the one-hole context of c is ax2 + bx + _. A zipper thus represents a focus on some part of a data structure.
We can easily store the how-we-got-here state by having the contexts be a recursive type: each context stores a reference to the previous context of the zipper (and we can mark the first context with some marker type).
In particular, we see that Huet’s zipper is essentially a per-type manual reification of the Kiselyov-Shan zipper: instead of keeping the how-did-we-get-here information in the recursive context type, we can keep that information on the stack, in the form of partial continuations. Each continuation forms a one-hole context into which we can plug a value. The act of plugging in a value returns us a new (one-hole context, current value) pair, into which we can plug our next value.
The really nice thing about the Kiselyov-Shan zipper is that the zipper and traversal have no knowledge about the other, allowing each to vary independently.
I found it much harder to implement the Kiselyov-Shan zipper for a few reasons. I had to write my own control operator, and partial continuations are tricky to get right: I had to remember when debugging not only where I was but how I got there in any piece of code. My debugging ability was greatly reduced by the fact that I was manipulating the stack directly and thus couldn’t rely on the stack to remind me how I ended up at a particular piece of code. Bad Things can happen. I often had to force-kill my image because I’d made the wrong move in my self-brain surgery: an over-eager capture of a continuation can cause serious disruption.
Implementing a Huet-style zipper, in contrast, was a lot more manual labour, but the process felt almost automatic. Which is a hint: I could probably automate or generate a large part of implementing the zipper.
 See Conor McBride’s “The Derivative of a Type is the Type of its One Hole Context“.
Thanks to the patient work of Jakub Wilk, mercurial-server 1.2-1 has hit the Debian “unstable” repository, where all being well it should make its way into testing, stable, Ubuntu and so forth. Jakub stepped in at the last minute when I discovered that the project’s previous sponsor, Steve Kemp, had resigned as a Debian developer in April.
I’d like to arrange a longer-term Debian sponsor for mercurial-server now, in advance of the next release, so that we can make sure we fix any issues with the package in advance and we’re ready when release time comes. If there are any Debian developers out there who use mercurial-server, please do get in touch – thanks!
The good fellows in Haskell land came up with a nice idea one day: instead of relying on a programmer writing well-thought out tests, with test data designed to flush out edge cases, they realised that people aren’t very good at finding bugs in their own code. The real world is too random, too crazy, to leave us alone. Things break in production for reasons we would never anticipate. So why don’t we, as part of our testing process, throw some randomness at our tests?
So that’s just what QuickCheck does. You specify a property – something you hold to be true for all your Foos – and QuickCheck will test your property by generating test cases. If it finds a counterexample, it figures out a minimal version of that counterexample and prints it out.
Good ideas tend to spread: JUnit 4.0 has
@Theory annotations – tests that take a single parameter. You define a
@DataPoint, and your test runner tests your theories against your supplied data source. QuickCheck’s also been ported to Scala, in the form of ScalaCheck.
So why shouldn’t Smalltalkers also have some fun?
Version 1.2 of mercurial-server is now available. This fixes a security problem, adds compatibility with Mercurial 1.9 and fixes incompatibilities with older versions of Python, adds MQ compatibility, and some other minor things.
Unfortunately it may not immediately enter Debian, because my former sponsor is no longer a Debian developer. If you’re an official Debian developer and you’d like to sponsor this package, please get in touch – thanks!
You are currently browsing the LShift Ltd. blog archives for September, 2011.