Sometimes after a particularly fraught bug stomping session you make a frivolous offhand remark to a colleague, for example “I will write a macro that converts lisp definitions in prefix form so that arithmetic looks like how it was taught to you in school” or “I won’t let my unit test really be an integration test ever again”. Today after wrestling with Ruby I mentioned a mild dislike for monkey patching as often used in Ruby and the idea for King Kong was born.

If you don’t like monkey patching in Ruby, then King Kong is the solution. He is a very large primate who likes to have his own way. If you define a class and then monkey patch it King Kong will eat it, it will be gone, no longer available for your use. Fortunately King Kong can’t use source code control systems (yet!) so you can correct your error and ponder his subtle ways.

We shall start by writing a spec:

require "rspec"
require "king-kong"

class X
    def x()
        "x"
    end
end

describe "King Kong" do

    it "does not allow monkey patching" do
        Object.const_defined?("X").should == true

        class X
            def x()
                "not x"
            end
        end

        Object.const_defined?("X").should == false
    end
end

Now we define King Kong!

class Class
    @@method_history = {}

    def method_added(method_name)
        @@method_history[self] ||= {}
        if @@method_history[self][method_name] then
            puts “King kong is the top primate\nHe has eaten your class!”
            Object.send(:remove_const, self.name)
        else
                @@method_history[self][method_name] = true
        end
    end
end

Run the spec, spec passes, job done! This code is licensed as is and probably shouldn’t be run in production, or even your QA environment but you are welcome to run it on your development machine for minimal comedic effect.

King Kong is a fine example of Ruby meta-programming and an excellent addition to your arsenal of offensive programming tools taking a large amount of inspiration from tools like Guantanamo. Marvel at how easy it is to completely annihilate a class from existence in Ruby, if that was Java you would have to give a class loader or something a walloping with a GreasySpannerFactory to achieve the same thing.

Remember sometimes monkey patching is a solution and some times it is the cause of the problem!

If you want to take a more serious approach to this problem you might want to look here.

A while back I did a post talking about working with MDF and a laser cutter. In that, I was using a program to generate the design for a sculpture and feeding the design to a laser cutter. This time around, the design is fairly simple and doesn’t need much computer help to build it, but there’s a few different options for how things can look, and so I’d like to be able to preview it beforehand. Previously, I was using Blender, but that’s a bit heavyweight for my little netbook, and given I’m just using it for viewing rather than editing, there are better options, and so I’m having a look at one of those along the way as well.

My tool of choice for today is the Python Computer Graphics Kit a.k.a. cgkit (I’ve put together a Debian packaged version while doing this). The documentation is a bit variable, but they’ve got a nice little viewer program that we can hack away at and use to make a tool to do what we want. Read more…

At LShift we like to program on blackboards using untyped lambda calculus, and we enter code into a computer only once we have a truly generic solution to a problem. However, most of the time we need to earn money so that we can eat and wear clothes other than LShift t-shirts - this usually involves compromising our principled approach and using "real" programming languages and libraries.

This can be quite painful! In my experience all real world projects need to produce output for a customer and this usually uses a technology called "mail merge" but as we are technical people we use the more technical name of "templating" (If you are elderly and not a computer scientist it is best to think of it as mail merge, this will have been an activity you read about in PCW magazines when you were a spotty teenager and hoped to never carry out and now looking back over your illustrious career you have realised that you have spent most of your time performing mail merge poorly). Templating sucks!

As we are rapidly moving into Movember I will briefly describe templating with mustache (this is how colonial people spell moustache, but searching for moustache on github will produce an excellent Clojure library not a templating system). I propose that if you are programming in Ruby, Mustache sucks less than ERB and will support my proposal with some examples.

As I said previously templating sucks! It especially sucks if you care about the formatting of your output which is why I call templating mail merge. If you received a printed letter from your electricity supplier and it went,

Dear    Valued 
     Customer, 
Your request for
 a further three phase supply to your premises
is denied
  as we fear that you have upset the villagers with your reanimation experiments.

you would probably be wondering about the extra spaces and carriage return in the text. Most of the time in HTML you wouldn’t notice because browsers eat whitespace, however if you were templating printed material or code it can be quite painful.

Lets look at an example of this using ERB. We will define a simple Ruby class to hold sections that have a name and may contain subsections.

class Section
  attr_reader :name, :subsections
  def initialize(name, subsections = nil)
    @name  = name
    @subsections = subsections
  end
end

Here is the ERB to render the output:

<% s.sections.each do |section| %>
This is section <%= section.name %>
<% if section.subsections %>
  <% section.subsections.each do |subsection| %>
  This is subsection <%= subsection.name %>
  <% end %>
<% end %>
<% end %>

Which I render like this:

template1 = ERB.new(File.read("simple1.erb"), 0, '<>')
puts "======================================"
puts template1.result
puts "======================================"

To produce:

======================================
This is section one
This is section two

  This is subsection two-a

This is section three

======================================

That output doesn’t look brilliant to me! I can feel a bug being raised in the issue tracker already, it really shouldn’t have those empty lines in the output.

If I modify the ERB I can do better:

<% s.sections.each do |section| %>
This is section <%= section.name %>
<% if section.subsections %>
<% section.subsections.each do |subsection| %>
  This is subsection <%= subsection.name %>
<% end %>
<% end %>
<% end %>

Which produces:

======================================
This is section one
This is section two
    This is subsection two-a
This is section three
======================================

Perfect output, but the ERB template looks a bit fragile, three end tags all in a row with no indentation to guide you will probably lead to difficult maintenance. The ERB templates I am currently maintaining are much more complex than the one I have used here and indentation really does help to make them readable.

Now for mustache! The template looks like this:

{{#sections}}
This is section {{name}}
  {{#subsections}}
  This is subsection {{name}}
  {{/subsections}}
{{/sections}}

We have to do a small amount more work to generate the output like this:

class Simple < Mustache
  self.template_path = File.dirname(__FILE__)

  def sections
    Array[
      Section.new("one"),
      Section.new("two", Array[Section.new("two-a")]),
      Section.new(”three”)]
  end
end

s = Simple.new
puts “======================================”
puts s.render
puts “======================================”

The code produces perfect output:

======================================
This is section one
This is section two
    This is subsection two-a
This is section three
======================================

The template also looks more maintainable than the equivalent ERB. However, you can still break the output quite easily with a very small change like this:

{{#sections}}
This is section {{name}}
  {{#subsections}}This is subsection {{name}}{{/subsections}}
{{/sections}}

Which produces this broken output:

======================================
This is section one

This is section two
    This is subsection two-a
This is section three

======================================

So it is best to keep your mustache sections on seperate lines to avoid extraneous whitespace. In summary mustache is probably easier and will produce cleaner output that ERB if you are performing a mail merge. Additionally mustache is cross-platform and has support for a large range of esoteric languages if you are tired of programming in Ruby.

Clojure has an interesting implementation of a Huet-style zipper. I started translating it to Smalltalk, and in the process discovered a number of things not really related to zippers. Given that the end result ends up looking very similar to something we’ve already seen , let’s talk more about the translation process itself. Read more…

Continuing on from my post a few months ago about playing with my Kindle, I’ve now amassed a fair number of books, and managing it is starting to be a bit of an issue. The main way to do this is with collections of books. However, Amazon in their infinite wisdom have decided not to provide any sort of tool for managing these outside of the Kindle itself, and the interface is somewhat lacking and slow for doing any sort of mass changes.

Life isn’t all that bad, as it turns out the collections are stored in a simple JSON file as “collections.json” in the “system” folder on your Kindle. It does however use various ways to generate a GUID for an ebook to store each collection, so we’re going to need a bit of help to figure out what those GUIDs are, and having someone else do the drudge work of working with the JSON would be nice. Enter Kindelabra (yes, that’s the author’s chosen spelling…). Primarily, it’s a little Python/Gtk app for managing collections, but there’s also a reasonable library sitting behind it that we can play with. I found a bit of the functionality was buried in the GUI as opposed to being in the library, but that was easily enough tidied up. Read more…

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.

Read more…

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 ax² + bx + c the one-hole context of c is ax² + 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“.

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?

Read more…

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!

mercurial-server on mentors.debian.net.