technology from back to front

Some reflective testing with gocheck

Last time
I wrote about custom gocheck checkers and wrote a checker that checked if a
slice of int contained a specific int – it would be nice to have a generic
contains checker and using the go reflection we can write one.

by
tim
on
30/09/11

The Essence of a Zipper

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.

Implementing Huet’s zipper means that we construct:

1. the set of possible one-hole context types [1],
2. define traversals through the structure,
3. and record the series of actions we took to arrive at this particular element in the 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).

Oleg Kiselyov and Chung-Chieh Shan show another way of deriving a zipper. Instead of type differentiating the structure,

1. define a traversal function on the structure,
2. define a map on that traversal,
3. “derive” the traversal through the use of partial continuations.

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.

[1] See Conor McBride’s “The Derivative of a Type is the Type of its One Hole Context“.

by
Frank Shearar
on
29/09/11

mercurial-server needs a long-term Debian sponsor

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!

by
Paul Crowley
on
14/09/11

Checking Squeak Quickly

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?

by
Frank Shearar
on
13/09/11

mercurial-server 1.2 released

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!

by
Paul Crowley
on
06/09/11

Categories

You are currently browsing the LShift Ltd. blog archives for September, 2011.

Archives

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060