technology from back to front

Archive for May, 2006

A two-player real-time puzzle game

ScreenshotSeven years ago, I wrote a two-player puzzle game in Python. I recently dug it up again and Matthias persuaded me to make a first release available here.

Both players sit at the same keyboard.


The object of the game is to take over all the other player’s

The board is made up of a grid of movable “tiles”. Each tile on the
board is one of three colours: red for the red player, blue for the
blue. One player moves using the arrow keys, the other using W, A, S,
and D. When a player moves, they swap places with a tile; thus by
moving about the board they move the tiles around, as in Sam Loyd’s
“15 puzzle”.

Certain tiles are “generators”. The neutral-coloured generators do
nothing. The red and blue generators periodically produce “pulses” of
their own colour. These pulses travel along the pipelines on the
board. When they hit a neutral-coloured tile or a tile of their own
colour, they set the tile to their own colour and carry on; when they
hit a tile of another colour they stop. If they hit a blank tile, a
generator, or a player, they always stop. When a pulse stops, the
generator that produced it makes another pulse (unless it’s turned
neutral in the meantime).

Certain tiles slow players down. If a player moves through a tile of
another colour, or a tile containing a pulse, they will be frozen in
place for a second before they can make another move. Players cannot
move through each other.

If a player has no generators of their colour and no pulses of their
colour on the board, then no tiles can ever be changed to their colour
again and they lose.

Certain tiles are placed deterministically; the rest are random but
symmetrical. Press “r” a few times to restart the game and see what
sort of board positions are possible.

“p” pauses the game. “q” quits.


Thus far I’m the only person who’s ever really learned to play this,
so I don’t really know how to play it well, but a few things are worth
pointing out. But racing to turn as many generators as possible your
colour at the start of the game will fill the board with tiles of your
colour, and thus slow your opponent down; you can then work on trying
to turn their generators to your side.

Play with it on your own for a bit before trying against an opponent.


I don’t know if I’ll ever work on this again. If I do, the two
obvious improvements to make would be a port to SDL, and network play.

Paul Crowley

What would you do with a ball of string and a pair of scissors?

How about making a [non-alternating knot]( with projection of minimal crossing number (which, incidentally, is [eight](

A non-alternating knot with projection of minimal crossing number

(Thanks to [David Snyder]( who told us this.)


Cryptanalysis of Py

LShift developer Paul Crowley presented a seminar on the cryptanalysis of the stream cipher Py at the Information Security Group of Royal Holloway, University of London.

In Paul’s talk the approach originally presented at SASC was covered in more detail.


Linux on Palm Tungsten T3

The folks at HackNDev have managed to port Linux to the Tungsten T3! It’s primitive at the moment – no support for the off button, slightly flaky SD card driver – but boots easily enough to a graphical environment you can actually use. The one (expected) downside is that it wipes your RAM, so you need to hard-reset to get back to PalmOS, and restore from backup to get your PalmOS information back.

Thanks to the folks in #hackndev on for helping me get Linux booting on my T3.

I’ll be interested to follow the work on the power-button support and other hardware-level features: I’d eventually like to get Squeak running.


Icing: Lightweight web development in Scheme

As part of a recent development project, we’ve assembled pieces from SISCweb, SSAX and SXPath, and some of our own code to build a simple web-development framework we’ve tentatively named Icing.

Icing, so far, consists of:

* a simple bean-like layer atop raw SQL, with an S-expression based SQL syntax and objects representing table rows;

* a small library (not quite the same as SISCweb’s approach) to allow pattern-matching on the URLs of incoming requests, and to allow attaching handlers to matched URLs;

* libraries for using JavaMail to construct and send arbitrary MIME multipart message parts and for using BouncyCastle‘s PGP implementation with JavaMail to build PGP MIME email bodies and attachments; and

* a XSLT-template-based Model-View-Controller-plus-Workflow framework for structuring applications. HTML templates (with special attributes and with optional embedded XSLT instructions) form the View; Scheme code forms the Controller; the DB layer referred to above forms the core of the Model; and SISCweb’s support for continuation-based web programming forms the Workflow.

The software is still being hammered into shape; we’re currently in the process of documenting it, packaging it conveniently for use in other applications, and deciding how we want to release it — it could be released as a thing-in-itself, bundling together a collection of third-party libraries, or we could instead take Icing to pieces, and fold some of the parts back into SISCweb (if SISCweb’s author, Alessandro Colomba, approves, of course).

I’ve made the slides from the presentation on Icing I gave last week available. They’re the only real documentation the code has at present, but ought to give a feel for the kind of approach we’re taking with it.


Critique of the CCR

There was quite a lot of excitement about Microsoft’s [Concurrency and
Coordination Runtime
(CCR)]( when it
surfaced back in December. Recently several people asked me my opinion
about this technology.

According to the above link the CCR
> is super cool stuff and represents a really innovative
> approach to making managed threaded programming more readily
> understandable and predictable.

Does the CCR live up to this promise? I don’t think so.

The CCR borrows many ideas from [process
algebras](, which are are
a great formalism for defining the semantics of concurrent programs
and reason about them. However, the CCR introduces several novel
constructs, such as joins and choices with a dynamically determined
number of participants, that are not found in existing process

I doubt that it is possible to construct a formal semantics that
captures all the CCR constructs and lets us reason about concurrency
in the same manner and with the same rigour as offered by most process
algebras. Consequently the CCR is built on shaky foundations and all
CCR-based programs are essentially meaningless – they mean *something*
but both tools and humans are going to have a hard time figuring out
what that is.

Even if the CCR had a well-defined semantics, it would be next to
impossible to verify that its implementation is faithful to it. The
CCR is implemented in C# and uses .Net classes. Hence to verify the
correctness of the CCR one has to model the semantics of C# and a
substantial chunk of the .Net libraries. That is hard. It is actually
possible to carry out a reasonably thorough verification of some C#
libraries, but the success of such a venture crucially depends on the
libraries being small, having been written with the semantics in hand
and with verification in mind. that is clearly not the case for the

The difficulties don’t stop there. The CCR is a library rather than a
language and its use is tightly interweaved with the rest of a
program. Therefore, in order to reason about the concurrency aspects
of CCR-based programs one has to reason about the entire
program. Performing any kind of static analysis on C#-based programs
is extremely difficult. The language is unwieldy and does not
encourage the style of programming that makes sophisticated analysis

From my own experience I know that static analysis of programs with a
concurrency model that is loosely based on process algebras is
*essential* if one wants to have any hope of writing correct
code. Even if there are no tools one should at least be able to reason
about the program mentally. That is impossible with the CCR.

To summarise: The CCR has no defined semantics, its implementation is
unverifiable, and CCR-based programs are not amenable to static


Proliant DL380 and Linux

I bought a Proliant DL380 on eBay for £27. Its got a couple of 866MHz Pentium 3s, 512Mb of RAM and two very fast 18Gb SCSI drives. It’s a first generation, which is sometimes called G1, but mostly just omits the generation in documentation. That makes it annoyingly difficult to Google for.

I couldn’t get Linux (Debian testing) to recognise the RAID controller. If I loaded cpqarray, the device seemed to get detected, but could not then detect any drives. I noticed an IDE connector on the mother board, so I figured I’d just replace the SCSI disks with a couple of cheap IDE disks. So I ordered them, and they duly arrived.

The first time I booted, they didn’t get detected by Linux, and access to the CD drive slowed down a lot. At this point I decided I’d have to get the setup CD (there is no BIOS configuration tool in the BIOS itself). You can get that here. I was a bit perturbed to find the BIOS help said that IDE fixed disks are unsupported. I guess I should have read the manual first.

Anyway, I had them set up as master and slave, and changed them to cable sensing, just in case Linux might detect them anyway. This had the result that I got /dev/hda with 3 cylinders and a correctly detected /dev/hdb. Unfortunately the performance problem was even worse this time.

I decided to try and work out if the RAID controller could be disabled, so I could see the SCSI disks under linux. I couldn’t just move the disks from the RAID controller to the non-raid controller, since they have 80pin SCSI connectors. There is a dip switch block, which I can’t find any documentation for. I decided not to mess with that. Instead, I removed a little daughter card from over near the SCSI connectors. It might be a mini-PCI card. Anyway, that turns out to be the RAID controller. With it removed, Linux detects the SCSI card it was using, and I am left with two SCSI drives I can use software RAID on.

Unfortunately, that’s less disk space than I need, so I still need to figure out how to get my IDE drives to work. At least it will boot debian now. I guess I’ll use a PCI IDE adaptor. Maybe even an IDE RAID controller.

If anyone knows what the DIP switches on the MB do, I’d be delighted to know.


Hacking on core Squeak

Today, attempting to port SPrevayler to Squeak 3.9, I ran into a problem with the FilePlugin. It turns out the problem is already covered by a test case in the image, and that the test case is currently failing, at least on Linux on the versions of the VM I tried (3.7-7, 3.9-7, and svn trunk).

The problem is that FilePlugin is caching the DIR\* for the directory that was just deleted, and deleting the directory doesn’t invalidate the DIR\* cache. Adding a check against lastPathValid and lastPath in dir_Delete solves the problem. Hopefully the fix will be included in mainline builds soon.



Colour Terminals in (X)Emacs

Some Unix command line tools display text in colour, if you run them in the right kind of terminal, of which the Emacs shell isn’t one. So far this had not really bothered me since in most cases the colours do not convey all that much information. However, recently I was playing with Maude, which colours terms for debugging purposes. There is no easy alternative for getting hold of the same information.

A few minutes of googling and experimenting produced the magic Emacs command

(require 'ansi-color)

followed by customisation of the ansi-color-for-comint-mode variable (setting it to t) or calling (ansi-color-for-comint-mode-on). This applies across all comint sessions, not just shell sessions, so it also affects things like the interactive Maude mode.

Under Emacs one can go further with M-x ansi-term, which creates a fully-fledged ansi terminal inside an emacs buffer. Finally we can run Emacs inside Emacs inside Emacs …! Ansi-term is not available for XEmacs, probably because it is some ghastly hack.


Exporting Squeak Presentations to HTML+PNG

I’ve been using Squeak‘s BookMorph to assemble presentation materials
recently, but there’s been no way to export the presentation for the
benefit of those without a Smalltalk image – until now. I just
implemented a trivial little method on BookMorph that exports all its
pages to PNG files, and writes a small HTML index file.

Here’s one I prepared earlier:

(the presentation itself isn’t done, and won’t mean much outside LShift at the moment, but it’s enough to demo the idea.)

Here’s the method I wrote:

| fileName indexPageStream |
‘Exporting ‘, pages size printString, ‘ pages to PNG’
displayProgressAt: Sensor cursorPoint
from: 1 to: pages size
during: [:progressSetter |
pages doWithIndex: [:page :i |
progressSetter value: i.
fileName := self externalName, '_',
(i printStringLength: 3 padded: true), '.png'.
PNGReadWriter putForm: page imageForm onFileNamed: fileName.]].

indexPageStream _ FileStream newFileNamed: self externalName, ‘.html’.
indexPageStream nextPutAll: ‘…‘.
“html and javascript elided – have a look at the example.”
indexPageStream close.




You are currently browsing the LShift Ltd. blog archives for May, 2006.



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