Simple Observers in Haskell

I’ve just uploaded version 0.0.1 of the simple-observer package to hackage, the Haskell package repository.

This is an implementation of the Observer design pattern in Haskell. I am not the originator or even main author of the code in this package; that is Dutch computer scientist Bastiaan Heeren, who wrote the original as part of an exercise for some students. But recently I was doing some GUI programming with wxHaskell (which I’ve found to be great, by the way) and found myself hankering for an observer or something MVC-ish, and my googling led me to his code. I used it, and then thought it might be worth releasing to the world at large — particular as it’s not wx-specific, or even GUI-specific, really. Bastiaan tells me he’s happy for me to do so, so here it is. I’ve changed names, separated it into two modules, and replaced IORef with MVars in order to better support multi-threaded use — but at heart it’s identical to Bastiaan’s code.

The basic idea is that an observable is a piece of mutable state, and when it’s changed, a list of observer functions are called in sequence, and passed the new value. For wx programming – which is anyway quite stateful and not very idiomatically functional – I’ve found it to be quite effective. Here’s a small example which illustrates basic use…

My GUI has a start/stop button, which toggles a running flag. When running is true, the button says “stop”, and certain things happen in the app’s idle handler (to run whatever is supposed to be running); when running is false, the button says “start”, and certain other things happen in the app’s idle handler. So here’s how we set it up:

In my app’s setup phase, I create running, which is initially false, using createSub :: a -> IO (Sub a):

    running <- createSub False

Later on (actually in a different function, which receives running as a parameter), I create the start/stop button and use running‘s current value to initialise its appearance:

     r <- getValue running
     btnRunStop <- button p [text := runStopBtnTxt r, on command := runStopClicked running]

Here, runStopBtnTxt :: Bool -> String just returns “start” or “stop” appropriately. We use it elsewhere, which is why it’s factored out. When the button is clicked, runStopClicked toggles the state of running (and does other stuff not shown here):

    runStopClicked :: Sub Bool -> -> IO ()
    runStopClicked running = do r <- getValue running
                                running `setValue` not r

(This would actually be neater using changeValue :: Sub a -> (a -> a) -> IO (), but in the real version I use r later on, so this I need the getValue anyway.)

So this setValue call will cause all of running‘s observers to be called with not r. The last thing we should do, then, is attach an observer:

    addObserver running (\x -> btnRunStop `set` [text := runStopBtnTxt x])

addObserver :: Sub a -> (a -> IO ()) -> IO () takes an observable subject and an observer function, and attaches that function to the subject’s list of observers. Here, the observer function just updates the text.

(It’s worth noting that the observer’s type is a -> IO () not Sub a -> IO () — i.e. observers receive values, not subjects. The subtext is that an observer shouldn’t modify the subject it’s observing, lest ye loop infinitely; you can get round this by passing the subject proper as an earlier argument, and provided it used setValue' not setValue you’d be fine — but I don’t know of any reason why you’d want to do this.)

The first win here is that the button’s on command function doesn’t need the button as a parameter, because it’s not directly updating the button text. The deeper win is relatively cheap and clean separation of concerns: the button only toggles the running value, and (separately) stuff happens when running changes. If some other mechanism (eg some network event) could also cause running to change, we’d already be dealing with it The Right Way: just add another observer. Without observers, if our reaction code was in the button’s on command handler, we’d need to call that, or factor the reaction code out, in order to deal with it then. This way’s clearly nicer. But hey, you’re reading a blog post containing type signatures, so I presumably don’t really need to explain separation of concerns, or the observer pattern, to you. :-)

I’m aware that there are more sophisticated approaches to this problem. I’m reliably informed that Functional Reactive Programming (FRP) subsumes observer quite naturally, but I don’t understand it enough to comment. Tom Lokhorst tells us that Erik Meijer & Co. at Microsoft have a good handle on this, as discussed in this entertaining video. Alternatively, if we like message-passing as our basic computational model, an implementation in CHP might be just the ticket — and that certainly looks like an impressively powerful approach. However, in my case, I wanted to keep things in a single thread as much as possible, because Haskell’s GUI frameworks (and indeed wx across all languages?) seem to interact with multi-threading in non-simple manners. This is also pretty much why I decided against implementing Neil Brown’s suggestion that the observers should be run in their own threads. Of course, if an observer wants to fork a thread, it absolutely can, and I may find myself doing this in my app soon — but I didn’t quite see the utility of baking it in. That’s probably my sequential imperative background showing through, and hopefully one day I’ll shake it off and welcome our new, multi-threaded masters. To conclude, everything mentioned in this paragraph is why I decided to release this as simple-observer.

Anyway, hopefully somebody will find this useful.

Alan Dix on “Language and Action: sequential associative parsing”

Alan Dix on the difference between how humans parse language, and how machines do so — and associated impacts on interaction. Interesting stuff, as ever.

If Philosophers Were Programmers

If Philosophers Were Programmers [brunns].

Nice to see that Wittgenstein (or at least, one of the Wittgensteins) is also a Haskell man…

Strength in weakness: judo design

The bin purge continues: Strength in weakness: judo design. Alan’s a clever and interesting fellow.

Years ago I also read about a programme to strengthen bridges as lorries got heavier. The old arch bridges had an infill of loose rubble, so the engineers simply replaced this with concrete. In a short time the bridges began to fall down. When analysed more deeply the reason become clear. When an area of the loose infill looses strength, it gives a little, so the strain on it is relieved and the areas around take the strain instead. However, the concrete is unyielding and instead the weakest point takes more and more strain until eventually cracks form and the bridge collapses. Twisted ropes work on the same principle.

How to use git and svn together

How to use git and svn together — or more properly, how to use git on an svn repository. I’ve been doing this for a couple of things, having switched my brain and day-to-day work patterns from svn to git, and it works nicely. I haven’t tried anything nontrivial such as branching, mind. Anyway, putting it here because some friends were asking about it.

Neil Mitchell on F# from a Haskell perspective

Neil Mitchell on the F# language [dons].

Real Life Tron on an Apple IIgs

I can’t remember where I saw this, but: Real Life Tron on an Apple IIgs.

Arrows in JavaScript

Arrows in JavaScript.

Arrows generalise computation schemes from the sequential version provided by monads, and are thus hard to bend one’s head around. It’s interesting to see them in JS.

SPJ/Haskell interview in Australian Computerworld

Simon Peyton Jones interview in Australian Computerworld [via galois].

A nice interview discussing various aspects of the history and philosophy of Haskell. SPJ sees purity, monads, and type classes as Haskell’s key aspects, and mentions a number of interesting other ideas along the way (along with uniqueness typing as seen in Clean, and functional reactive animation, which I first came across back when I was investigating music in Haskell).

More generally, this looks like a good series to keep an eye on: also contains interviews on Forth, JavaScript, Lua and other more boring languages such as C++. Shame there’s no obvious feed.

sshfs with RSA keys on OS X using MacFUSE

MacFUSE is nifty, and in particular supports sshfs for mounting filesystems from ssh-accessible remote boxes.

However, I found today that using the GUI always asks you for your “ssh password”. I don’t use a ssh password; indeed, all my boxes have password tunneling disabled: you can only log in via keys. The GUI didn’t/doesn’t seem to be key-aware.

Thankfully, the command-line version (sshfs-static) mentioned on the wiki page linked above is aware – so I succeeded in mounting my remote fs using:

Applications/sshfs.app/Contents/Resources/sshfs-static om: om \
-oreconnect,volname=om

I’ve set up an alias for that in my .zshrc and am now in sshfs happiness land.

(Oh yes, perhaps I should have mentioned: I’m using OS X now, for my desk/laptop needs at least. More on this as time progresses, no doubt.)

Other good reasons: the existence of Python, Ruby, Haskell, Smalltalk, …

There are many, many reasons why you should never ever accept a job which involves programming in C++ [via TR].

Oyster cracked

Oyster (and others) cracked [smallcool] — another lovely example of “don’t invent your own crypto algorithm”, it seems.

… We argue that this is a gross over-estimate and present an attack that recovers secret keys within minutes on a typical desktop PC or within seconds on an FPGA. Our attack exploits statistical weaknesses of the cipher.

One way not to conduct Internet voting

USA Democratic Party “global primary” for Democrats Abroad badly run, insecure, untrustworthy — just like almost all (all?) electronic voting systems in use today.

There are well-known risks at every stage of the episode, so I repeat: that whole process was neither secure nor well-run; moreover, its collection of personal information using unsecured Web pages exposed participants to the risk of information theft, and delivering notionally secure information by email is painfully bad judgment. The episode proves nothing except that well-intentioned people continue to make elementary but serious errors in designing and setting up processes that must be safe at every step if they are to be meaningful.

Don’t like getting to sleep at night? Read the RISKS digest avidly.

Some handy tools: cstream, lsof, iftop, …

Unix tools, and how I use them at Andrew Birkett’s blog, the latest addition to my feedspace.

There’s some really nice stuff here I didn’t know about. cstream, iftop, and less -S are all new to me. watch is, of course, indispensible.

Slide40 – presentations with 8 bit style

Slide40 example slide

From the same good people who brought you the lambda calculcus in a can [ultimate].

Easily fixing stuck pixels

Fix stuck/dead pixels on your monitor with Killdeadpixel

Awesome — supposedly can often fix stuck pixels with minimal effort on the part of the human. Almost makes me wish I had one to try it out on… ;-)

More infinite list tomfoolery in Haskell

More infinite list tomfoolery in Haskell — the one for pi’s particularly “WTF?”.

The Great Escape

Today I wanted to search a large number of text files for a particular sequence of characters. Naturally the tool to use for such a job is grep, as any phule kno.

Unfortunately, the text I wanted to search for was \' — that’s a backslash followed by a single quote. This is mildly problematic because each of these characters has special meanings either for grep or the shell or both.

Long story short, this is what I need to type:

grep \\\\\' *

That’s five backslashes followed by a quote. :-)

WTF? Well: grep uses \\ (two backslashes) to match a single slash, but so does the shell (zsh in this case) so if I entergrep \\' *, the shell would interpret the \\ as meaning “one backslash please” and pass just that one to grep. Unfortunately grep would interpret the backslash as escaping the following character, rather than a literal backslash. Thus, in order to actually give grep the two backslashes it needs in order to match one, I have to type four. Then we also need \' to match the quote character, because a quote on its own is interpreted by the shell as, well, a quote (ie starting a string) — so this final backslash is eaten by the shell in order to pass that quote to grep directly. grep doesn’t treat the quote specially of itself, so finally we have what we want. Sweet.

You have got to love the command line.

Notes: Tony Sale on WW2 codebreaking and Colossus rebuild

Earlier this evening I went to a great lecture by Tony Sale, on “Code Breaking in World War 2″.

He discussed Enigma, and how it was broken, then the Lorenz cipher/machine, and how that was broken, and then the Colossus, leading to the Colossus rebuild project. He should know about this stuff: he started the project.

I took some notes if anyone is interested [PDF, 76Kb] (naturally, these are rough notes, may contain errors, are my own, etc.). You might also want to check out codesandciphers.org.uk which includes a virtual Colossus.

SAGE: open source mathematics software with python scripting

It’s possible (with fingers etc. crossed) that by the end of the year my job will have altered somewhat and I’ll be spending some of my time, amongst other things, doing the kinds of things one generally uses Mathematica and Matlab for. This would be a departure, but no doubt an interesting one.

And what should come steaming over the horizon into my view at this moment? Ah look, it’s SAGE, “Open Source Mathematics Software” in exactly that flavour, with scripting in Python. Maybe it’s half-baked rubbish, maybe it’s slick and up to the job; maybe I’ll never know. Maybe, just maybe, I’ll be checking it out by the end of the year. For now: noted.

The multi-touch-shiny train is gathering steam – all aboard!

At the intersection of hack and wow: Low-Cost Multi-touch Whiteboard using the Wiimote — ooh, that’s just lovely [paulmiller].

And in other multi-touch news, it appears Nokia may have something very shiny indeed up their sleeve, namely taking the “touch” out of “multi-touch” with 3D gesture tracking based on ultrasonic transducers [reddit].

Three or more transducers arrayed around a perimeter of the mobile device create a 10-20 cm working volume of space above the display, where user finger locations and their movements in real time can be detected using triangulation techniques. These movements can then be interpreted as various three dimensional gestures.

Colossus reborn

Colossus reborn.

How to disable underscore subscript in TeX mode in emacs

After some random recent upgrade, emacs started doing something annoying: when in TeX mode (eg when editing LaTeX docs, which I do a lot), it would treat every underscore in the document as a signal that the next symbol should be subscripted, and display it as such: the character would be offset vertically using font-lock magic. This is very annoying, because underscore only means subscript in maths mode; the rest of the time, it’s wrong and silly to visibly subscript the thing. In general, I don’t want emacs to do such semi-WYSIWYG-ness – syntax highlighting is about as much as I need, thank you.

Anyway, how to turn it off is non-obvious, and required several increasingly imaginative google search strings. In the end I came across this recent thread on gnu.emacs.help, one of whose posts suggested that turning down font-lock-maximum-decoration from “maximum” is the right thing to do. Yep, that works: I changed it to “nil” and now I’m happy.

Won’t somebody please think of the children?

Wifi routers: silent, blinking death?

(I may get round to writing something actually meaningful and/or profound at some point – but not right now.)

3 magnets + 40,000 pendula + 2 hits of acid = wow

Movie here. Psychedelic!

visualising the motion of 40,000 pendula under the influence of 3 magnets using Haskell. Shiny.

What’s going on here? OK, so it’s not 40,000 pendulums “all going at once”, because obviously they’d bounce off each other. ;-) What we have is a 200×200 grid (ie 40,000 pixels), and for each pixel we define a pendulum. At a given time, a given pixel’s colour represents the corresponding pendulum’s distance, at that time, from each of the 3 magnets (the pixel’s RBG components represent the three distances). Each pendulum’s movement is affected only by the magnets, ie the pendula are independent of each other. Hey presto, psychadelica-a-go-go.

Primes one-liner in Haskell – oh my!

mux on #haskell pasted what is perhaps the most beautiful code I’ve ever seen in my life:

      <mux> > nubBy(((>1) .) . gcd) [2..]
<lambdabot>  [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,...

(Number two in an ongoing series of jaw-dropping Haskell one-liners which began with the fibonacci series.)

Haskell packages gotcha: global vs. per-user package databases

This morning, I was having a problem involving Haskell’s Cabal build system. Since it’s something which could conceivably affect others, and since googling on the error text didn’t help me, I’m going to report my experience for the benefit of future travellers/googlers.

I was trying to (re)build xmonad, and got the following error:

[gimbo@orb xmonad] runghc -v Setup configure 
   Could not find module `Distribution.Simple':
       Use -v to see a list of the files searched for.
Read the rest of this entry »

Python-style string split (and strip / trim) in Haskell

Haskell’s an incredible language but I’m repeatedly struck by (what I perceive as) gaps in its standard libraries (though as proven yesterday I could know them better). For example, there aren’t any cross-platform file path manipulation routines in the style of python’s os.path (though not for long, thanks to Neil Mitchell). Another lacking area seems to be string manipulation.

Today, I needed to split a string up according to some token, where that token is itself a string, not a single character. Thus, a split in the style of python’s strings’ built in split() method. That is, I wanted to be able to do this:

*StringSplit> split ", " "one, two, three, four"
["one","two","three","four"]
*StringSplit> split "an" "banana"
["b","","a"]

To my amazement, this isn’t a standard library function, and I couldn’t find hundreds of examples of how to do it via google. I couldn’t even find one! I could find a number of variants where the token is just a single Char, usually utilising takeWhile and the like. Gladly this led me to a reasonable (I hope) solution. This example splits on Chars but in the comments I was introduced to unfoldr, which looked tantalisingly close to what I wanted. All I needed to do now was write the function unfoldr calls. About half an hour and much hoogling later, hey pesto:

module StringSplit where

import List

-- | String split in style of python string.split()
split :: String -> String -> [String]
split tok splitme = unfoldr (sp1 tok) splitme
    where sp1 _ "" = Nothing
          sp1 t s = case find (t `isSuffixOf`) (inits s) of
                      Nothing -> Just (s, "")
                      Just p -> Just (take ((length p) - (length t)) p,
                                      drop (length p) s)

All of the complexity is in sp1 (short for “split once”), which performs a single split. sp1‘s type is String -> String -> Maybe (String, String); the section (sp1 tok) then has the right type for unfoldr (sections just seem to be cropping up everywhere lately, eh?). The point of sp1 is to split s at the first occurrence of t. It does this by using inits to build all prefices of s and finding the first one having t as a suffix. If found, it splits the string at the token, throws the token away, and return the (before, after) pair. If the token isn’t found, it just returns s paired with an empty string; that gets passed by unfoldr to sp1 on the next call, causing sp1 to return Nothing, causing unfoldr to finish – whew!

That last bit sounds a bit complicated, but it was necessary to fix a bug present in my first implementation of sp1:

sp1' t s = case find (t `isSuffixOf`) (inits s) of
               Nothing -> Nothing
               Just p -> Just (take ((length p) - (length t)) p,
                               drop (length p) s)

This misses the final substring, so split "n" "banana" would return ["ba", "a"] instead of ["ba", "a", "a"]. Hence the whole empty string/Nothing/stop machinery.

I could not have written this code two weeks ago, I think. Thus, I’m sure there are better ways to do this, and would love to hear them – and any criticism. I was a wee bit worried about using inits and find in this way for finding a substring (no standard substring function?). Haskell’s lazy nature ought to help me here though: inits will only build the entire list of prefices if t isn’t in s at all. For anything I’m planning to use this for, it ought to be fine; it’s probably not the best general way to do it though.

Postscript

For good measure, since I had to implement it later that evening, here’s a string.strip() (aka trim):

strip :: String -> String
strip s = dropWhile ws $ reverse $ dropWhile ws $ reverse s
    where ws = (`elem` [' ', '\n', '\t', '\r'])

I’m particularly proud of the ws part. :-) Look at me, all full of Haskell pride. ;-)

Postpostscript

I realised I can generalise split beyond strings, to work on lists of anything of class Eq:

-- | A function inspired by python's string.split().  A list is split
-- on a separator which is itself a list (not a single element).
split :: Eq a => [a] -> [a] -> [[a]]
split tok splitme = unfoldr (sp1 tok) splitme
    where sp1 _ [] = Nothing
          sp1 t s = case find (t `isSuffixOf`) $ (inits s) of
                      Nothing -> Just (s, [])
                      Just p -> Just (take (length p - length t) p,
                                      drop (length p) s)
*StringSplit> split [2,3] [1,2,3,4,3,2,1,2,3,4]
[[1],[4,3,2,1],[4]]

More playing with sections (and flip) in haskell

Last week I wrote about sections in Haskell, and discovered flip. Today I hit upon a problem which got me thinking about them again, leading to one of those wonderful moments when Stuff You Just Learnt turns out to be exactly what you need to solve the problem you’ve got right now. (Then you blog about it and find an Even Better Way, as it turns out.)

I’ve been writing some file-manipulation code, and along the way had written the following function:

-- | Check if a given string (subject) ends with another (target).
endswith :: String -> String -> Bool
endswith sub tgt = drop (length sub - length tgt) sub == tgt

(Actually I’ve forgotten now whether I wrote this myself or found it somewhere, but it’s clearly not a new problem. If anyone knows a source for the above code, please do tell so I can attribute it. Anyway…)

So then you can do:

*Ew> endswith "banana" "na"
True
*Ew> endswith "banana" "moo"
False

So far so good. Later, I had a list of filenames, and I wanted to filter it down to just those ending with a particular suffix. Initially, unthinkingly, I tried:

*Ew> filter (endswith "na") ["banana", "cat", "iguana", "mastodon"]
[]

Spot the cunning use of a section. Actually not so cunning, as it turns out – the empty list is not the result I was hoping for! The problem is that the first parameter of endswith is the subject (the string to be searched) not the target (the string to be searched for) so the section (endswith "na") is not the function which checks if a string ends with “na”. It’s the function which, given a string, checks if “na” ends in that string:

*Ew> (endswith "na") "banana"
False
*Ew> (endswith "na") "a"
True
*Ew> (endswith "na") "na"
True

My first reaction was to just swap the parameters around. Let’s call this version endswith'. It’s exactly the same as endswith except for the parameter order:

endswith' :: String -> String -> Bool
endswith' tgt sub = drop (length sub - length tgt) sub == tgt

Then (endswith' "na") is the section I’m looking for, and in particular works as I want under filter:

*Ew> (endswith' "na") "banana"
True
*Ew> filter (endswith' "na") ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

I only use endswith in a couple of places, so this change was totally viable. Lesson learnt (or so I thought): you have to think carefully about parameter order when writing functions, because some sections will be more useful than others. Obviously with endswith, the section with bound target is more generally useful than the section with bound subject.

Later, I realised this lesson is bogus, or at least not very strong. I mean, there’s probably something in it, but I didn’t actually have to swap the parameters to make my filter work. That’s exactly what flip does:

*Ew> ((flip endswith) "na") "banana"
True
*Ew> filter ((flip endswith) "na") ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

What’s going on here? (flip endswith) is endswith with the parameters flipped. Thus ((flip endswith) "na") is exactly the same function as (endswith' "na") which, as we saw above, does what I want. So in the end, I didn’t have to replace endswith with endswith' to get my filter to work – I could just flip it. Bearing in mind I didn’t even know flip existed a week ago, I felt pretty smug to realise this. :-)

The next question on my mind is what you might call “generalised sections for multi-parameter functions”… If I have a 4-parameter function and I want to build a section where 2 of the parameters are bound (say), and it’s not the first two, how do I do it? Stupid toy example:

f :: Int -> Int -> Int -> Int -> Int
f a b c d = a + b + c + d

Can I make a section representing f with b fixed at 3, and d fixed at 5, say? I know I can do this:

g :: Int -> Int -> Int
g a c = f a 3 c d

but can we do it inline, as it were, as with the section approach? Answers on a postcard to the comments page, please! :-) I suspect currying‘s going to wind up in there somewhere…

Postscript

That’s all I originally intended to blog about; when chasing links to support this post, however, I read this and learnt two more interesting things.

First, someone has, of course, solved this problem already, and I can just use isSuffixOf to get this job done (Strings in haskell are Lists of Chars). So now I get to throw endswith away – w00t, less code. A fundamental lesson: once the language starts making sense, learn what’s in the standard libraries!

Second, thanks to Haskell’s ability to deal with functions in infix form, the section (isSuffixOf "na") can also be written as ("na" `isSuffixOf`) which is, I suppose, more natural (provided you’re not scared off by the backticks, which I’m trying not to be). Then we have:

*Ew> filter ("na" `isSuffixOf`) ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

Sweet.

Installing Haskore (Haskell/CSound) under FreeBSD

I’ve spent most of today looking at Haskore, which appears to be the most well-developed kid on the block for doing Csound type things using Haskell (and indeed, doing music type things using Haskell). Here are my notes on finding/installing it, which experience wasn’t completely straightforward…

Read the rest of this entry »

Playing with sections in Haskell

Consider the function (:) in Haskell…

Hugs> :t (:)
(:) :: a -> [a] -> [a]

So, (:) is a polymorphic function which takes an element of some type, and a list of elements of that type, and returns a list of elements of that type. In particular, it prepends the singleton element onto the list. For example:

Hugs> 'c' : "ello"
"cello"

Now for the fun part.

Hugs> :t ('c':)
('c' :) :: [Char] -> [Char]

Here, we see that ('c':) is a function which takes a list of characters (ie a string) and returns another one. As you might expect, it prepends it with a 'c':

Hugs> ('c':) "ello"
"cello"

('c':) is an example of a section: we “partially evaluate” a function by providing only some of its parameters, which yields a new function. Obviously this is only possible if we have higher-order functions in our language.

We can take the section “on the other side” of the :, and define the function which takes a character and prepends it onto the string "ello"

Hugs> (:"ello") 'c'
"cello"

What’s its type?

Hugs> :t (:"ello")
flip (:) "ello" :: Char -> [Char]

Interesting. The type is as we would expect (Char -> [Char]), but what’s this flip thing?

Hugs> :t flip
flip :: (a -> b -> c) -> b -> a -> c

So flip takes a function with type signature (a -> b -> c) and returns an equivalent function with type signature (b -> a -> c) – OK, simple enough. But why did hugs introduce it here, I wonder, though, why didn’t hugs just do what ghci does, and say:

Prelude> :t (:"ello")
(:"ello") :: Char -> [Char]

? I say: shrug.

In other news, I’ve just discovered Neil Mitchell’s Haskell blog. I met Neil at BCTCS 05 in Nottingham, and again at BCTCS 06 in Swansea (though at that time I felt like I was moving away from TCS). He’s a thoroughly nice bloke, and clearly knows considerably more about Haskell than I do, thus, a good blog to find. I enjoyed:

I think I was quite a bit less successful at explaining this one. The only way you can show sequence is not necessary is by writing an OS, a compiler, a web server etc in Haskell – all of which have been done. Unfortunately I only had a small piece of paper so couldn’t write any of those.

Neil Mitchell, “Describing Haskell to an Ada programmer”.

(The section saga continues here.

There’s no escape

SQL injection attacks in a nutshell.

All about python and unicode

Handy for future reference and pointing confused ASCII-loving students at: all about python and unicode, just the thing to explain the mysteries of unicode in a friendly manner, especially, er, if you know python.

One for Rich

Brings a nostalgic tear to the eye, is what it does

Threads should pass messages, not share memory

Highly recommended reading for any of my students out there: a comparison of message-passing concurrency vs. shared-memory concurrency, with a healthy dose of historical perspective. The author introduces Erlang-style concurrency in a Java-ish setting, and does so quite well, to my mind.

Reading the introductory remarks about candidates in interviews, I was pleased, nay, smug to realise that – albeit inadvertantly – I came to multi-threaded programming via the message-passing route, and would probably have made him quite happy if he’d interviewed me. Back when I worked at Frontier I did my first multi-threading work, in Python, and made heavy use of its excellent Queue class for inter-thread communication. Queue provides a thread-safe message passing mechanism, hiding all the nasty details of locking from me, which was exactly what I was looking for. My threads shared almost no state, and what state they did share was mostly Queue objects. They communicated by passing messages through Queues (messages could be anything, and often were), and it was all lovely and clean.

Why did I go down that route? No genius; I just got lucky (yeah, lucky in that I was using Python not Java or C or C++). I had excellent advice from the good folk on comp.lang.python/python-list: this was the way to proceed. Of course, looking back I realise many of these guys knew all about message passing vs shared memory, they knew about Erlang, they knew about Haskell, hell some of them even knew about Lisp. A community as smart and welcoming as that one is a precious resource for a budding programmer.

Anyway, this led to two strongly noticeable results.

First, my code worked well, and didn’t suffer from mysterious hard-to-debug race conditions, etc. It “just worked”, as is often the way with Python.

Second (confession time), I didn’t actually learn properly about semaphores, monitors, shared memory concurrency and all its ridiculous fiddly baggage until I came to teach them in the Operating Systems module at Swansea! By then I’d already formed a strong sense that high-level languages (and Python in particular) made life so much sensibler, so the shared memory stuff slotted quite readily into the mental space of “low level stuff which has to be understood, but is best done by software not humans” (like much of that module).

I was discussing this whole issue with one of my students earlier in the week. If she closed her app’s main window while a worker thread was running, the program would exit uncleanly. This being Python, it was nothing more drastic than an exception/traceback, but she found this properly displeasing and wanted to clean it up (good, I said). It turned out that the main thread wasn’t waiting for the worker to finish: it exited immediately, cleaning up all data, including data the worker was trying to update. Hence, exception city. I showed the simple fix (make the main thread wait for the worker to finish, using a shared boolean “I’m not dead yet” variable), but then I tried to persuade her that message-passing concurrency was the way to go for all inter-thread communication. Even, said I, right down to the (frequent, many) interface updates caused by the worker thread. That is, I suggested, the worker shouldn’t update the GUI component directly, because the GUI is owned by the main thread. Instead, the worker should pass messages to the main thread telling it what updates to perform, and the main thread should poll for these messages and do the updates. I don’t think I sold her on it entirely, but maybe I planted sump’n.

(Caveat: yes, if performance really matters – eg you’re doing volume graphics – this may be poor advice. For the other 95% of us, however…)

eBay architecture notes

Quite interesting rough notes on eBay’s architecture – (horizontal) scalability is the watchword, with J2EE on Oracle being the central technologies. Interesting (but not entirely surprising) to see that most of the work is done application-level [raganwalk].

The Quest of the Algorithm of the Chimes of the Bells of the Clock of the Long Now

I’m on a bit of a quest at the moment, which is turning up all sorts of interesting bits and bobs (and distracting me nicely from the work I should be doing today).

Yesterday I listened for the first time to Danny Hillis‘ 2004 Long Now seminar on “Progress on the 10,000 Year Clock” (listen here). Like most of these seminars (which I really should write about in more detail some time) it’s well worth a listen, bristling with neato facts, insights, and mind-expanding ideas. (A less time-consuming but still usefully detailed introduction to the clock project can be found here.) One of the things which particularly caught my imagination was the discussion of the bells. Apparently His Enoship noticed that the number of days in 10,000 years is almost exactly equal to the number of permutations of ten things (365 x10000 = 3650000; 10! = 3628800) – so the idea is that once per day these ten bells will chime in a certain order, never heard before, never to be heard again. (Eno has released a CD of “bell studies”, which is on its way to me even as I type.) Hillis invented an algorithm for the ordering of the chimes, so we know what ordering will be played for any day in the next 10,000 years (Eno’s CD plays the sequences for January 7003) and as you’d expect, people have run with this idea. I have an itch to run with it too, probably (predictably) in Haskell.

So where’s the algorithm? I haven’t found it yet, to my great surprise. :) I would have expected it to be fairly easily available, but apparently not. It might be in Stewart Brand’s book about the clock (also on its way to me), but I sure don’t see it anywhere online. However, there are a couple of implementations floating around, so perhaps some reverse engineering is in order…

Sean Burke has created a web page for exploring the bell patterns, with visualisations and MIDI downloads – code in Perl (and a Postscript (!) version here). Not fancying reverse-engineering the Perl too much, I wrote and asked Sean if there was a better source for the algorithm. Apparently Danny’s original version is in Mathematica. I haven’t found it, but Sean says he’ll send me what he can find in a few days. Otherwise, I guess I’ll keep digging, ask around on the Long Now forums, etc.

Sean pointed out that, when reverse engineering, “there’s understanding, and there’s understanding”, and pointed me at this fantastic war story, which sounds like a Daily WTF candidate to me. I’ve been there in the past, and in my case it was spaghetti Perl I was banging my head against – not pleasant. Still, the whole process of reverse engineering, of picking apart the code slowly, gradually and gently teasing the tangled knot open, can be a wonderful thing in itself. Or it might just turn out that the Mathematica code is clean and easily Haskellised. I doubt it, though, from what I’ve seen of Mathematica. :-) I expect it’ll live in a much lower-level domain than I want to work in, which is, of course, more than half the fun. If I can take an esoteric algorithm in a difficult language and translate it into beautiful and readable higher-order code, that’d be something worth writing about. So, watch this space (but don’t, of course, hold your breath).

In the mean time, as I said, the search is turning up all sorts of cool stuff. We present:

Another version of the algorithm, by Joe McMahon, in OS X/AppleScript discussed here, here & here (code via that last link). Interesting mention of ChucK too, which looks quite shiny (though again, maybe a little low-level for my taste).

Prototype chime generator diagram – I would wear a t-shirt with that on it.

An interview with Alan Kay from two weeks ago, which also points at the Kay-says-it’s-a-must-read Doug Engelbart essays (and no, I must confess, I hadn’t heard of Engelbart).

Pop culture lives in the present; it doesn’t really live in the future or want to know about great ideas from the past. I’m saying there’s a lot of useful knowledge and wisdom out there for anybody who is curious, and who takes the time to do something other than just executing on some current plan. Cicero said, “Who knows only his own generation remains always a child.” People who live in the present often wind up exploiting the present to an extent that it starts removing the possibility of having a future.

Stewart Brand meets the Cybernetic Counterculture – whee, the 60s!

(These last two via this del.icio.us page on “admirable people”.)

woof

woof – very handy for occasional one-shot (or multi-shot) file serving. Put it somewhere in your path and every now and then it will make you happy.

Woof (Web Offer One File) tries a different approach. It assumes that everybody has a web-browser or a commandline web-client installed. Woof is a small simple stupid webserver that can easily be invoked on a single file. Your partner can access the file with tools he trusts (e.g. wget). No need to enter passwords on keyboards where you don’t know about keyboard sniffers, no need to start a huge lot of infrastructure, just do a

$ woof filename

and tell the recipient the URL woof spits out. When he got that file, woof will quit and everything is done.

Haskell study plan

Haskell study plan [smallcool].

autopushd in zsh – make cd behave like pushd always

I’ve just been exposed to one of those delightful little hacks that are both forehead-slappingly simple/obvious and yet so powerful and clearly “right” that I just know I’m going to be using it for the next n years. Allow me to share.

In every Unix shell I’ve ever seen, one uses the “cd” command to change directory, moving around the directory structure.

cd has no memory of where you were before. Some shells add a stack-based history via the commands “pushd” and “popd” (which I only discovered in 2004). If you pushd to a directory (eg pushd /some/distant/directory), you can subsequently get back to where you were before very easily by just entering popd; furthermore, such calls can be nested arbitrarily deeply (that’s what the stack is for). This is, on occasion, tremendously helpful, and can save a lot of typing/thinking.

The insight: why bother with cd, then? Why not just always pushd around the place? That way, you’ve always got the possibility of using popd to get back to where you were before easily and quickly. There are two possible reasons why not. First the stack takes up some space in memory. Feh, no problem – it’s not that big, and I never have a shell open long enough for it to become a problem. Second, pushd is a few more keystrokes than cd, and my habits have cd hardwired into them.

Thus, the hack: alias cd to pushd. But wait! Don’t do that!

Since I use zsh, I don’t even need to alias it. I can use the zsh config option “autopushd” to make cd always behave like pushd. Hell, yeah! I just add the following to ~/.zshrc:

setopt autopushd

and hey pesto:

# Start by going to some fairly deeply nested directory
[gimbo@mane ~] cd work/teach/cs-238/current 

# Now I cd (but really pushd) to some other, also deeply nested, directory
[gimbo@mane current] cd ~/work/research/mphil/tools/HetCATS/CspCASL
[gimbo@mane current] pwd
/home/gimbo/work/research/mphil/tools/HetCATS/CspCASL

# In the words of Baloo: take me home, daddy!  (This next line doesn't work without the autopushd trickery)
[gimbo@mane current] popd
~/work/teach/cs-238/current ~
[gimbo@mane current] pwd
/home/gimbo/work/teach/cs-238/current

Update 2007-02-24: Will has just pointed out to me that “cd -” will take you back to where you were before, so repeatedly issuing cd - allows you to flip between two places easily – which is of course a common use case. Neato!

[gimbo@orb ~] cd /tmp 
[gimbo@orb /tmp] cd -
~
[gimbo@orb ~] cd -
/tmp
[gimbo@orb /tmp]

hpDJ: an automated DJ with floorshow feedback

Here’s a little gem for anyone else out there interested in dance music, DJ’ing, and computers: hpDJ: An automated DJ with floorshow feedback. Basically, it describes a system which allows one to define a “qualitative tempo trajectory” for a DJ set, then chooses tracks to fit the trajectory (the words “partial ordering” occur at this point, but that’s as close as we get to TCS), and automatically beatmatches/timestretches/mixes the tracks accordingly. Towards the end it considers the performance and “collaborative consumption as composition” possibilities, with genetic algorithms and the like, but the bit which impressed me the most was on the mixing, where the opportunities afforded by doing the job in software are recognised and made the most of.

However, because hpDJ operates in the pure software realm of digital signal processing (DSP), it is possible to create as many sweepable band-pass/cut filters as is desired for any particular cross-fade from one track to another. As with traditional hardware mixers, each DSP filter can have variables that control the degree of attenuation or boost, and its center-frequency. In addition to this, the shape of the DSP filter’s transfer function (e.g. the nature and rate of the fall-off or boost) and its bandwidth can also be under automatic control. Recording studios do have filters with these added controls, but such filters (known as a Parametric EQ) are too expensive to be built into each channel of professional mixing desks on a many-per-channel basis.

Thus, it becomes possible to specify hpDJ so that it analyses the audio frequency-time spectrogram for the incoming and outgoing tracks in the cross-fade, and uses a number of heuristics to determine how many DSP Parametric EQ filters are necessary and what their settings should be. This can be used to, for instance, selectively suppress the frequencies for a synthesizer melody-line in one track, attempting to make that melody “disappear” while keeping the bass-guitar and percussion elements in place during the cross-fade. By employing simple heuristics for detecting when one component of one track “clashes” with another component of the other track, such aesthetically unpleasant clashes (which may remain despite perfect beat-matching) could be automatically eliminated by hpDJ.

Note that this is all happening automatically (except maybe setting some initial loose parameters at the start) – very impressive.

Although this was published only in 2005 (I spotted it in this book on this man‘s desk), much of this was apparently done around 2000 or so. Thus, I wonder what goodies they’re cooking up in Bristol even as I type. Dave Cliff’s “inventor profile” page doesn’t really bring us up to speed, I feel… Aha! He’s moved to Southhampton.

Finally, I note that this is the first paper I’ve ever seen which opens with a Sisters of Mercy quote. Rock on.

Haskell and Category Theory

An introduction to Category Theory from a Haskell point of view. As always, monads are where your brain starts hurting.

Autoattach / automount encrypted home partition in FreeBSD using GBDE

I’ve just set up one of my laptops, running FreeBSD, so that /home is encrypted using GBDE, and is auto-attached/mounted/fsck’d at boot time. The instructions in the FreeBSD handbook aren’t completely clear, so here are some notes on how I did it.

Actually, most of those instructions are very clear, provided you don’t care about attaching at boot time. Indeed, I’ve had an encrypted partition which I attach/detach by hand, for about a year now, for which those instructions were perfectly adequate. Unfortunately, the section on “Automatically Mounting Encrypted Partitions” leaves out two important details which conflict with the rest of the chapter: your lock file’s name needs to end in the text “.lock”, and you need to be careful where you put it. This was confusing, and in some ways what you have to do to get automounting working contradicts the other examples in the chapter.

Anyway, long story short, I had to dig into /etc/rc.d/gbde to work out what had to be done, and here it is… A summary of how to set up an auto-attaching encrypting home partition on FreeBSD using GBDE:

(I did this as pretty much the first thing after a fresh install, before I’d even created any users. Needless to say, then, all of this happens as root.)

Here’s how /etc/fstab looked before I started:

# cat /etc/fstab
# Device        Mountpoint         FStype    Options   Dump Pass#
/dev/ad0s1b     none               swap      sw        0    0
/dev/ad0s1a     /                  ufs       rw        1    1
/dev/ad0s1e     /tmp               ufs       rw        2    2
/dev/ad0s1f     /usr               ufs       rw        2    2
/dev/ad0s1g     /usr/home          ufs       rw        2    2
/dev/ad0s1d     /var               ufs       rw        2    2
/dev/acd0       /cdrom             cd9660    ro,noauto 0    0

Unmount /home because I’m about to blat it completely:

# umount /usr/home

Create a directory to contain the lock files:

# mkdir /etc/gbde

Initialise the partition for GBDE. I used a use sector size of 2048 (which matches the UFS fragment size). Note that the lock file’s name ends in .lock; this is not how the main body of the GBDE instructions in the handbook does it, but it’s necessary to get /etc/rc.d/gbde to attach it properly on boot up:

# gbde init /dev/ad0s1g -i -L /etc/gbde/ad0s1g.lock
Enter new passphrase:
Reenter new passphrase: 

Attach the encrypted partition to the kernel for the first time (entering the passphrase previously specified), and write the filesystem:

# gbde attach /dev/ad0s1g -l /etc/gbde/ad0s1g.lock
Enter passphrase: 
# newfs -U /dev/ad0s1g.bde 
/dev/ad0s1g.bde: 6632.5MB (13583360 sectors) block size 16384,
                 fragment size 2048 using 37 cylinder groups of
                 183.77MB, 11761 blks, 23552 inodes.  with soft
                 updates
super-block backups (for fsck -b #) at:
 160, 376512, 752864, 1129216, 1505568, 1881920, 2258272, 2634624,

*SNIP*

Test the mount:

# mount /dev/ad0s1g.bde /usr/home

Assuming that looks good (eg in df), unmount it and detach it:

# umount /usr/home
# gbde detach /dev/ad0s1g

Now we’re ready to set it up for auto-attaching. We need to alter /etc/rc.conf and /etc/fs.tab

# tail -n 3 /etc/rc.conf
gbde_autoattach_all="YES"
gbde_lockdir="/etc/gbde"
gbde_devices="ad0s1g"

We need the gbde_lockdir line because otherwise it looks for the lock files just in /etc, I think.

# grep home /etc/fstab
/dev/ad0s1g.bde /usr/home          ufs       rw        2    2

Now when I boot, it asks for the passphrase, attaches the encrypted partition, and mounts it – automatically – then it gets fsck’d with everything else. It doesn’t automatically detach upon halting the system, but I guess that’s no problem. :-)

The only thing I don’t totally like is that if I get the passphrase wrong (3 times), it doesn’t attach or mount the encrypted partition (obviously), but then of course it fails filesystem checks completely and the boot process dumps down to single user mode, messily. Not completely unreasonable, I guess, but still a bit annoying.

Anyway, anyone now stealing my (crappy) laptop will have a much harder time of getting at the data on it (the interesting data, anyway). Whee!

Foozles!

Yikes. This is waaaaay too close to home: Foozles – a programming language feature comin’ atcha soon! [wadler]

2013: Francoise Boisbleu proves that under a certain formulation, Foozles are a categorical dual to Aspects, which gets everyone terribly excited.

It certainly would.

Classic comment / code impedance mismatch

Awesome, almost Dadaist WTF:

// MUST be set to 1!
Params->ParentalLevel = 3;  // QA now insist this is set to 2.

Made me laugh out loud, anyway.

Why the iPhone puts Java into the past tense (apparently)

In Which I Think About Java Again, But Only For A Moment [smallcool].

Me, I defected long ago. I’m another of those Apple Java engineers who dropped out. I spent five years as a raving Java fanboy, but I gave up after optimizing AWT, implementing drag and drop, and trying to make 1,200 pages of crappy APIs do the right thing on the Mac. Then I took a one-week Cocoa training course, and wrote the first prototype of iChat.

Desktop Java never worked because Sun tried to build their own OS on top of the real OS, duplicating every API and feature. This led to terrible bloat, making every app as heavyweight to launch as Photoshop. Worse, the GUI portions of the Java platform are awful, because Sun is a server company with no core competency at GUIs. The APIs are too clumsy to code to, and compared to any decent Mac app, the results look like a Soviet tractor built on a Monday.

He almost makes me want to get a Mac, ditch BSD and emacs, and start writing Cocoa apps – except that then life would just be too darn easy, and I’d never hear the end of it from TR (or Bash, probably).

It’s always somewhat depressing, or at least downheartening, to see someone like this tell me I shouldn’t be using emacs. It always makes me wonder if, maybe, they’re right – maybe out there there’s an editor that’ll do everything emacs does for me, but somehow nicer, more productive. Usually, as far as I can tell, that means the editor does IDE-like things such as autocompletion, code browsing, etc. – and yes, that’s stuff I just don’t use when coding. But gosh darn it, I’ve tried a lot of editors and nothing has ever come close, for me, to the feeling of power and (welcome) flexibility emacs gives me. Effortlessly editing multiple files in multiple split views in multiple windows (across multiple virtual desktops), powerful and easy regexp and macro capabilities, and (as one of the commenters on the linked article says) just doing The Right Thing with indentation in Python, Java, C, Haskell, … So the downheartening aspect is the tantalising feeling that there’s something else out there I should be using, but I just can’t find it! Of course, not using a Mac probably doesn’t help me, here. ;-)

I haven’t listened to Depeche Mode for a while, mind…

Oh, and here‘s another “Java is rubbish” story (comparing EJB lines of code with python/django) from the same source.

You can’t beat python for seeing in the new year…

Gimbo’s New Year’s Eve 06/07: human_twister.py

Postgres for the win!

Anyone who has ever argued against Postgres on performance grounds should go and read this, then eat their hats. Unsurprisingly, the real lesson is the classic: know your tools and know your data.

Fibonacci series one-liner in Haskell

Here’s a beautiful example of why Haskell is the most advanced programming language on the planet – a one-line definition of the entire fibonacci series:

fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist))

Stunning. Note that that is not a function to calculate the nth fibonacci number: it really is a definition of the entire series. If you want the nth fibonacci number, look up the nth element of that list. Let’s see you do that in Java! (Or C#)

(Via the introductory series on Haskell at the rather good Good Math, Bad Math (more on the author here).)

Rock on, young stunningly-good-looking Management Consultant!

Joel on management consultancy – golden. The crux: “

The whole fraud is only possible because performance metrics in knowledge organizations are completely trivial to game.

Follow-up 2006-11-29: We’re from Harvard and we cost too much for you – balanced, insightful.

Rails vs Django

Rails vs Django [smallcool].

Interesting and balanced. I tried Django about a year ago and did indeed get going with it quite quickly, although the lack of migration was a big pain in the butt, and sounds like a killer feature in Rails.

Alison Goldfrapp just doesn’t get monads

I’ve just realised that Goldfrapp’s song “Strict Machine” is actually a rant against haskell, or possibly miranda. One can hope that it’s the Python or Ruby runtime she’s in love with, but somehow you just know it’s the JVM, in all its baroque 80s-retro glory. Silly girl.

I blew her a kiss once, you know. I got a cold stare in return.

Logo in Javascript

cs fd 70 repeat 11 [ repeat 17 [ rt 226 fd 75 ] fd 75 ]

Thanks, TR! How lucky the children whose first language was Logo.

Comparison of Haskell and Scheme

Here’s a nice comparison of Haskell and Scheme [raganwald]. Not a “vs”, but a thoughtful, informed, and reasoned look at a number of their respective features.

I’m still on my Haskell learning curve, and I can vouch for the incomprehensibility of monads. Thankfully I haven’t had to do anything yet that required actually understanding them, though I have used them… :-)

This paragraph grave me pause:

If you’ve got a class full of first year computer scientists, you can teach them to read and understand the full formal semantics of Haskell. You can make it completely non-mysterious. Everything can be explained by the standard lambda calculus α, β, and η rules, with no hidden complexities. It’s all remarkably straightforward.

In fact, it made me sigh, imagining first years getting formal semantics, lambda calculus, and even, well, Haskell. Another world…

“Intuitive” means “familiar”

Jef Raskin (12 years ago): “Intuitive” means “familiar” [raganwald]

His story of the Finnish teacher doesn’t surprise me. In my first job (ie in about 1995 or so) a colleague reported showing one of the admin girls a mouse (upon upgrading her computer from DOS to Windows), and her doing exactly the same thing: lifting the mouse up and waving it around in the air. You’d have a hard time reproducing this result now, I guess, because even someone who’s never used a mouse (think: your gran) has probably seen them used on TV, for example.

Brazil collision: Too much precision a bad thing?

Insightful and non-intuitive – just the way I like it: increased precision in avionics arguably increases the risk of mid-air collision.

Design patterns as responses to programming language deficiencies

We teach a third-year/MSc module called “Design Patterns and Generic Programming”. Instantiated by Oliver Kullman, and now taught by Chris Whyley, it introduces these topics in the context of C++ (and is, for most of our students, their first exposure to that language).

On Friday I suggested something to Chris which I’d been mulling over for a while, namely an “anti-patterns” lecture at the end of the module. It would be “anti” in two senses… First, a discussion of the idea of antipatterns: things to avoid. Second, and more interestingly, a discussion of the idea that patterns are just a stop-gap response (albeit a highly rational one) to deficiencies in your programming language, and that more advanced languages make them trivial or meaningless. Chris thought this sounded good, so now I’ve got to gather my thoughts. In timely fashion, along comes this piece (via raganwald) expounding the very same idea. (Disclosure: it’s not my idea, it’s something I’ve been seeing mulled over and expressed in varying depth and eloquence on the blogosphere of late.) This post is particularly interesting in that it looks for pre-GoF patterns, recognising that patterns aren’t a specifically Object-oriented phenomenom, but rather a general software development phenomenom, and we can excect to see new patterns in the future, as the patterns of today fade into the undistinguished background.

4 TFTs… That’s just being greedy!

Drool…

Tail call optimisation at Raganwald

I command all of my students reading this to go and read this piece on tail call optimisation. If you’re anything like me, you’ll need to read it at least twice, write out the ruby examples by hand so they actually enter your brain (maybe I just needed more coffee), and follow many of the links for further explanation. It will be well worth it. This man has intelligent things to say, with which it is worth being familiar, if not intimate.

The Daily WTF

In the spirit of the RISKS Digest, with which regular Gimbolanders will be familiar, The Daily WTF looks like it’s worth reading to remind oneself of the crazy and unexpected stuff that can go wrong, and the stupid stupid STUPID!!! things our beloved colleagues sometimes force us to endure [raganwald].

The other reason to read WTF right now is that picture of Boomer in their sidebar – miaow.

And in other JVT news…

Wow. JVT gets a mention on Lambda The Ultimate. Proof that he’s made it.

Next step: Thumbnail for JVT Must Prove P=NP

Security Engineering: free to download

Oh, happy day! Ross Anderson‘s classic work “Security Engineering: A Guide To Building Dependable Distributed Systems” is now free to download. Yay!

This might explain why the publishers didn’t send me an inspection copy when I asked them for one about six months ago…

“Ridiculously easy” distributed programming with Ruby

MapReduce for Ruby: Ridiculously Easy Distributed Programming [raganwald]

Great for tasks which trivially parallelise, anyway.

How to make a corporate butt pucker

How to make a corporate butt pucker – sounding the death knell of “Enterprise Development” with a capital E and a capital D. Good. [raganwald]

Computational Theology – made up name!

Reading this eWeek article on Sun’s desire to support dynamic languages better on the JVM (via lambda) I was struck by the following sentence:

Gilad Bracha, a computational theologist at Sun delivered a presentation called “Dynamically Typed Languages on the Java Platform” at the Lang.NET 2006 Symposium here on August 1, and said Sun plans to broaden its support for dynamic or scripting languages.

Exqueeze me? Computational Theologist?

Perhaps, I mused, this had something to do with computing The Nine Billions Names of God (not something I’d use Java for, I think). Or maybe some other scripture-related buffoonery such as finding predictions of Lady Diana’s death in Moby Dick… So I googled for it.

Nope, turns out it’s something Gilad Bracha made up because the task of interpreting natural language specifications of languages and virtual machines reminded him of Talmudic scripture interpretation.

Oh, how I laughed. It is, from one point of view, a beautifully subversive move on Brachca’s part – perhaps a first step in decoupling the word theology from anything to do with God or gods, which is bound to annoy existing theologians and is thus worthwhile. Also, I can completely see what he means in that most natural language specifications I’ve seen are full of ambiguities, irreconcilable contradictions, and just bad thinking. I leave the reader to close the loop on this analogy.

On the other hand, I’m cautious about welcoming the use of the word, and its associations, anywhere near computer science. If science and reason free us from having to use religious dogma to explain the world, and if mathematics is the language of science, and if computer science is simply one form of mathematics – all of which I believe – then religious tools and terminology are a poor fit to the domain, if you ask me.

By the way, I’m not saying in the previous paragraph that I believe science makes religion completely unnecessary, or proves it to be hogwash. I don’t believe that for one moment – although some people do, and you can say what you like about science being their religion. I believe the rational worldview and the religious one are two orthogonal ways of looking at the world. Anything we can explain or deduce with science, religion has nothing to say about; for me, religion lives in the gaps between the theorems, in the undecidable propositions, in the time between the end of this universe and the start of the next, in the unknowable, in the sublime.

Click survey

Click survey – cool.

Searching for symbols via Google is hard

Hokay. Google is without a doubt the single most useful and successful tool ont’Internet, a marvellous success story and something most of us would miss deeply until the happy day it’s superseded by something Even Better. It’s fast, it’s got a nice simple interface, and most of the time it “just works” and gives you what you want.

Unfortunately, some of the time, it really doesn’t “just work” (for me, at least) and in an apparently non-fixable way. I usually hit this when I’m doing programming-related searches.

Read the rest of this entry »

wmii FreeBSD and xmms plugins (in ruby)

A few days ago I started using wmii, with Mauricio Fernandez’ ruby scripting magic, and oh it’s fun.

The status bar monitors that come in Mauricio’s code don’t work for me, however, because I’m running FreeBSD not Linux, and things like uptime and battery status get report differently. Also, there wasn’t any xmms control/monitoring. I have now fixed both of these problems, and invite others to partake of the goodness.

So: wmii-freebsd@gimbo.org.uk.rb – a ruby/wmii plugin defining status bar monitors which work under FreeBSD.

And: wmii-xmms@gimbo.org.uk.rb – a ruby/wmii plugin defining an xmms status bar monitor, and some key bindings for simple control of xmms (play/pause; next; previous; forward 5 secs; back 5 secs; toggle shuffle; er, that’s it).

Status bar screenshot:

ruby wmii freebsd/xmms status bar monitors

From left to right: xmms monitor displaying track name, time elapsed, shuffle status (“>” is normal, “@” is shuffle); current master volume; the “-N-” is a standard plugin so I say nothing here; temperature and CPU speed; load averages; uptime (h:mm); battery status and time remaining; date/time.

Comments, suggestions, bugfixes, criticisms of my appalling ruby code all welcome.

Web hosting: Nearly Free Speech

Interesting: nearlyfreespeech.net provide (US-based) web hosting on a pay-for-usage basis. $1.00 per gigabyte transferred, and $0.01 per megabyte-month of disk storage.

Gimboland currently consists of about 200MB of storage, and about 1.5GB per month bandwidth (somehow!). So that’d be about $3.50 per month. Not bad.

OTOH I’m only paying $11.95 per month now, which with the current exchange rate is still fairly peanuts. Plus I get to pay by direct debit, which nearlyfreespeech.net don’t seem to support. I’ve been pretty happy with webquarry‘s hosting, so I’m in no hurry to jump ship for the sake of a couple of quid per month. I may yet change my mind about this, however.

Anyway, in the meantime, maybe someone else will find this interesting/useful…?

wmii is better than ion

In August 2002, I started using ion as my window manager (and last year, upgraded to ion3). Today, I stopped using it.

ion beats the crap out of conventional window managers: placing and resizing windows is so tedious (not to mention 20th century ;-) ). It’s lightweight, maximises screen real estate, and has great keyboard support, all of which appeal to me. Until today, I’d have recommended it to anybody.

I did, however, have the following problems with ion: 1) Lua: yick and oh my god, yuck. What an awful language, but you’re stuck with it for configuration/control. 2) The documentation: there, but not very helpful. Too referencey, too automatically produced. 3) Tuomo (the author): sorry, but that is one surly gringo, and heaven help you if you disagree with him. None of these are killers (except maybe lua), but they’re the reasons I’m happy to leave ion behind.

Thus, introducing wmii, which is superficially similar to ion but has a number of features which really set it apart. The most important is its Plan9-inspired approach to control, which allows any language for configuration. You know what’s coming next? Ah yes, we can configure & control wmii using ruby [via the immortal _why].

There are other good reasons to use wmii, but that one is probably sufficient for me – and it speaks of a thoughtful and open design which can only bode well. The wmii codebase really is tiny, by the way – it compiled in no time at all. I started using it this afternoon and I don’t see any reason to stop: it’s easy enough to pick up, although I’ll be tweaking the config for the next week or so. Using Ruby – w00t!

The BigBook Technique

Engineering Management Hacks: The BigBook Technique – poetic. [raganwald]

Run a web server on your mobile phone

Now you can run apache on your Nokia S60, complete with mod_python. Neato. [matt]

Windows Vista shaping up to be a user _and_ security nightmare!

Microsoft Vista’s Endless Security Warnings

The feature is called User Account Protection (UAP) and, as you might expect, it prevents even administrative users from performing potentially dangerous tasks without first providing security credentials, thus ensuring that the user understands what they’re doing before making a critical mistake. It sounds like a good system. But this is Microsoft, we’re talking about here. They completely botched UAP.

w00t.

Calmly seeking powerpoint diagram extraction tool

Does anyone know of a tool which can extract the diagrams from a Powerpoint presentation and turn them into something sensible and open, preferably SVG (but EPS or even PDF would do I guess)? Ideally a tool which can do this for all of the diagrams in a presentation in a single pass, but even a solution that requires manual intervention for each diagram would be better than nothing… Thanks!

“Always on” password autocompletion in Firefox

A handy feature in most web browsers is the ability to remember usernames and passwords for sites you visit often, so you don’t have to keep typing them in – the browser just fills it in for you. Some sites don’t like you doing this, however. If the input tag of the password field contains the attribute autocomplete=”off”, that’s an instruction to the browser not to allow this handy feature for that field, so you have to type in the password by hand every time.

This is arguably quite a good idea, and reduces the chance that a user in an internet cafe will thoughtlessly click “remember” and partially open up their bank account to the next customer. There are some interesting thoughts on the topic here, but that’s not what this post is about.

What this post is about: the intranet at work is one of these security-minded sites that disables autocomplete, which is really really annoying (they also have a brain-dead policy on password expiration, but that’s another story). At certain times of year I have to use this site a lot – it forgets you’re logged in between sessions, and I find myself repeatedly typing the password.

Well, no more. Have I moved to Opera, which ignores autocomplete=”off” altogether? No, of course not – I’ve found a Firefox extension which does the job for me.

Introducing ketjap, which can apparently do a number of quite funky things but which in particular can rewrite tag attributes arbitrarily using a set of prevalue/postvalue rules. So I defined I rule which acts on input tags, on their autocomplete attribute, turning a prevalue of off into a postvalue of on. Et viola, it works. The next time I visited our intranet and entered my username/password, firefox offered to remember the password for me, and I gratefully agreed to its welcome proposal.

Actually, I was a little confused at first, because I looked at the page source, expecting ketjap to have changed that, but that’s not what happens – it seems it alters firefox’s interpretation of the source on the fly, leaving the source untouched. Neato in extremis.

Now I invite members of the public to point out the page in Firefox’s preferences where I could have just ticked a box to make this happen. ;-)

The Waterfall model has always been evil

This is very interesting… Common wisdom has it that the waterfall model is the “old way” of doing things, a respected technique from times past, but that these days we’re (struggling to) move towards more agile, iterative methods of software development. Accoding to this, however (and the wikipedia article agrees), the paper that first described the waterfall model actually described it as a bad practice, and went on to advocate an iterative approach, attempting to formalise practice which had been around since the 1950s. Alas, subsequent papers largely missed the point that a purely sequential waterfall was a bad idea, and it got enshrined as “software best practice” of the 1970s. We’re still trying to recover.

Bugs in embedded systems can be naaaasty

In 2003, the pacemaker of a woman in Japan was accidentally reprogrammed by her rice cooker.

Computers are getter smaller and smaller; embedded systems are getting more and more powerful. That means two things. First, what you can do on a computer of given size n is increasing over time: maybe five years ago it was just a microprocessor with 4KB of RAM running custom-built assembly code, whereas maybe in five years it’ll have a gig of RAM and be running OpenBSD or (shudder) Windows. It’ll have more features, more complexity, more failure modes, less security, and in essence, we won’t understand it any more. Second, the smallest systems producable are getting smaller all the time: today you can put that custom-built system with 4KB of RAM into a smaller space than you could five years ago, and in five years time it’ll be smaller yet. That means computers are appearing in more and more places, and more invisible.

The interesting part is when you put these trends together, so you end up with millions of systems flowing through your bloodstream, all running Windows 2020 (or whatever). Yay.

Understanding Ruby blocks, Procs and methods

Understanding Ruby blocks, Procs and methods.

Scripts in ruby a la python’s __name__ == ‘__main__’ idiom

A common idiom in python is to check the special variable __name__ to see if the current module is being run as a script or not. For example:

class Foo:
    ...

def bar():
    ...

if __name__ == '__main__':
    bar()

Here, if the module is run as a script (ie passed directly to the python interpreter), then __name__ has the value “__main__”, this is detected, and (in this case) the bar() function is called. On the other hand, if the module is just imported from some module, __name__ has a different value (the name of the module file, I think?), and bar() doesn’t get called.

This is nice for a number of reasons – for example, you might put unit tests into bar().

How to do this in Ruby? It’s not in FAQ, which surprised me. I was about to ask on ruby-talk but then remembered the biggest FAQ of them all, and turned to google. Aha (and eek, what a horrible mailing list interface). Anyway, it’s:

if __FILE__ == $0
    bar()
end

OK, so why does this work?

$0 contains the name of the script being executed – ie, the name of the file that was passed to the interpreter. Whatever code you’re executing, this value never changes over a particular run of ruby. On the other hand, __FILE__ is always the name of the current source file. If the two match, then the current source file is the one that was passed to the interpreter.

I guess that’s pretty clear. Cool.

Gimbo tries Evolution and is put off by silent failure

I use mutt for email, but I’ve been toying with the idea of moving to Evolution. I can work very quickly in mutt, but I’ve been wondering about going graphical for a while, and I’ve heard good things about Evolution recently so I thought I’d give it a try.

Well, it’s OK, but I’m not completely convinced. There are a number of little things, but here’s what really bugs me…

I have a local spool mailbox with 74 messages marked for deletion, and, well, they’re just sitting there, marked but undeleted. How do I get rid of them? The “File->Empty Trash” menu item works in other mailboxes (eg an IMAP one), but these guys are refusing to go. This would be merely mildly annoying were it not for the thing that really worries me: it fails silently. I click “Empty Trash”, and nothing happens – no error dialog, no status message, nothing written to stdout.

Another one: I select “Help->Contents” to get some help and… nothing happens. No help, no error dialog, nothing to stderr, just another silent failure. This is probably, I guess, because I’m not actually running gnome. But if it’s not going to work, it shouldn’t be on offer. We can do better than this, people.

Silent failure is always a really bad sign because it makes debugging (and thus fixing) so much harder. The fundamental reason why I use Unix rather than Windows is that it puts me in control, and when things go wrong, I can usually track down the errors and fix them. You have to be choosy about the software you use, because a hell of a lot is crap and doesn’t actually help you, but there’s enough which does it properly to make the effort worthwhile.

Unfortunately it’s starting to look like Evolution isn’t one of them, which really surprises me given the people I’ve heard positive testimony from. :(

So, I might perseverse, or I might give GNUMail.app a try, or I might just stick with mutt because it does rather rock. Any other suggestions?

Oh yeah: another reason I like the look of Evolution is for its calendering. I have yet to find a decent calendaring app, which just astounds me. Sunbird looked half decent for a while but then switched from nice open iCalendar format to some stupid binary format, and (here’s the clincher) no longer even runs on my system. It doesn’t start, and it does so silently.

Why is so much software so bad?

Update, a few minutes later: aha, it’s “Folder->Expunge” to clear the deleted messages. I wasn’t seeing failure, I was just asking it to do the wrong thing. Still, this does raise the question: why does “File->Empty Trash” work in the other mailbox? And the help still fails silently. Pah. ;-)

Why the Sony Ericsson w800i sucks

GOD DAMN it!

I used to own a Sony Ericsson k700i and it was a great little phone except that it really sucked in that it only had capacity for 100 text messages. Never mind it had 64Mb or so for photos and music – 100 short messages is all you’re getting, buckaroo!

Well, I upgraded recently to the super shiny w800i – this is the Walkman branded thing, and it’s a very very nice phone. Great interface, great camera, records sound, blah, blah, blah. Oh yeah, and it’s got a little stick in the side which gives it a memory of 512Mb. Half a gigabyte. Double the memory of the laptop I’m typing on right now, in fact.

The bastard thing has just cheerfully told me “Text memory over 95% full – delete some messages now?” No you fucker! I don’t want to delete some messages now!!! Your memory is empty you stupid piece of shit!

Apologies for the swearing but god damn it I’m angry. I mean, I knew the salesman with the Toni and Guy haircut had no fucking clue what he was talking about when he said it didn’t have this text/sms memory limit problem, but all the same, I really thought they’d have sorted this stupid stupid bug out by now. There is absolutely no excuse for this kind of shoddy programming in a product this advanced.

GaaaaaaaaAAAAAAAAAAHHHHHHHHHHHHHHHHHHH!!!

/me goes and kills someone

Students: if you ever do this, you are compelled to commit seppuku

Lesson one in security: deny by default, allow with care. It is entirely brain dead for your login logic to be “if the logged_in cookie is false, they’re not logged in, otherwise they are”, rather than “if the logged_in cookie is true, they’re logged in, otherwise they’re not”.

The wacky world of Thorsten Altenkirch

The wacky world of Thorsten Altenkirch [via ping/will]

A blurry Thorsten Altenkirch at BTCTCS 2005

Cheers, Thorsten!

(For balance, here’s the perfectly sensible world of Thorsten Altenkirch.)

Erlang tutorials

Erlang tutorials.

Erlang looks very exciting. I’m still trying to crowbar Haskell into my brain – and reaching the conclusion that my brain needs inflating a little before it will fit. But Erlang is calling.

Video eavesdropping demo at CeBIT 2006

Video eavesdropping demo at CeBIT 2006 – 25 metres, no wires: sweet.

Lessons from the Sony CD DRM Episode

Lessons from the Sony CD DRM Episode, (PDF, 154KB, 27 pages) [schneier].

Abstract: In the fall of 2005, problems discovered in two Sony-BMG compact disc copy protection systems, XCP and MediaMax, triggered a public uproar that ultimately led to class-action litigation and the recall of millions of discs. We present an in-depth analysis of these technologies, including their design, implementation, and deployment. The systems are surprisingly complex and suffer from a diverse array of flaws that weaken their content protection and expose users to serious security and privacy risks. Their complexity, and their failure, makes them an interesting case study of digital rights management that carries valuable lessons for content companies, DRM vendors, policymakers, end users, and the security community.

That’s “Sony” DRM technology actually brought to you by a company with offices near here, who came to the department and did a presentation at an event organised by IT Wales las year. They certainly did seem very impressive, and IIRC their CTO spoke highly of his programmers’ abilities. Only goes to show, I guess. (Some retrospectively amusing quotes in this article, I thought.)

Crash Bandicoot was written with Lisp

WTF? Crash Bandicoot was written with Lisp??? Seems everybody’s talking about how great Lisp is lately…

And on the subject of games, these are pretty cool too.

Don’t Invent XML Languages

I saw this a while ago and meant to blog it, if only for the super useful/interesting “Big Five” list of XML uberlanguages whose existence means it’s best if you Don’t Invent XML Languages [lambda]. Of the Big Five, the one I’m interested in Right Now is DocBook.

Gaah, I’m tracking STABLE, but should probably be tracking security… :-/

Nice explanation of FreeBSD release versions.

Handy dandy Subversion tools

Some Subversion-related tools I need to keep in mind, though not use right now: SvnReporter; svn-copy-register and svn-import-releases. That is all.

Apache vs Yaws

Apache vs Yaws. (Executive summary: Apache dies at 4,000 concurrent requests; Yaws is still working fine at 80,000.)

Yaws is written in Erlang, which seems to be far-and-away the best language around at the moment for concurrency.

Learn Python in 10 minutes

Learn Python in 10 minutes.

Hofstadter on the Turing Test

A Coffeehouse Conversation on the Turing Test by Douglas Hofstadter. I believe I shall enjoy this with a coffee and a large sandwich of some description tomorrow. Goodnight!

Classic Texts in Computer Science

Classic Texts in Computer Science.

So long, and thanks for the Ph.D.!

A CS graduate school survival guide: “So long, and thanks for the Ph.D.!”, which includes the marvellous Richard Feynman Problem Solving Algorithm: 1) Write down the problem. 2) Think very hard. 3) Write down the solution.

It Is Pretty Much a Bad Idea to Expose Raw SQL…

On the joy of SQL injection attacks: Fun Things I Found Out About Your Company With Administrator Access to your Database [python-url].

Also includes a link to a guide to such attacks, for the uninitiated.

Uniquely Addressing

Nice (short) database design war story.

Markdown

Being a plain-text luddite, this looks nifty: markdown [43folders].

Markdown is a text-to-HTML conversion tool for web writers. Markdown allows you to write using an easy-to-read, easy-to-write plain text format, then convert it to structurally valid XHTML (or HTML). Thus, “Markdown” is two things: (1) a plain text formatting syntax; and (2) a software tool, written in Perl, that converts the plain text formatting to HTML.

Countering Trusting Trust through Diverse Double-Compiling

I haven’t yet had chance to read this properly, but it’s very exciting and impressive, and will no doubt be essential supplementary reading on the security course I’m teaching next term: Countering Trusting Trust through Diverse Double-Compiling.

Update 2006-01-26: Bruce Schneier’s lucid explanation.

more retro »