Beware of the Train

I've recently submitted a couple of talk proposals to upcoming conferences. Here are the abstracts.

Machine learning in (without loss of generality) Perl

London Perl Workshop, Saturday 24th November 2012. 25 minutes.

If you read a book or take a course on machine learning, you'll probably spend a lot of time learning about how to implement standard algorithms like k-nearest neighbours or Naive Bayes. That's all very interesting, but we're Perl programmers - all that stuff's on CPAN already. This talk will focus on how to use those algorithms to attack problems, how to select the best ML algorithm for your task, and how to measure and improve the performance of your machine learning system. Code samples will be in Perl, but most of what I'll say will be applicable to machine learning in any language.

Classifying Surfaces

MathsJam: The Annual Conference, 17th-18th November 2012. 5 minutes.

You may already know Euler's remarkable result that if a polyhedron has V vertices, E edges and F faces, then V - E + F = 2. This is a special case of the beautiful classification theorem for closed surfaces. I will state this classification theorem, and give a quick sketch of a proof.

Here are some bits of code I've released recently:

UK mountain weather forecast aggregator

The Mountain Weather Information Service do an excellent job, providing weather forecasts for all the mountain areas in the UK - most weather forecast sites only give forecasts for inhabited areas, and the weather at sea level often differs in interesting ways from the nearby weather at 1000m. However, their site's usability could be better. They assume that you're already in an area and want to know what the weather's going to be like for the next couple of days¹, but it's more normal for me to know what day I'm free to go hillwalking, and to want to know where I'll get the best weather.

So I decided to write a screen-scraper to gather and collate the information for me. I'd heard great things about Python's BeautifulSoup library and its ability to make sense of non-compliant, real-world HTML, so this seemed like a great excuse to try it out; unfortunately, BeautifulSoup completely failed me, only returning the head of the relevant pages. Fortunately, Afternoon and ciphergoth were on hand with Python advice; they told me that BeautifulSoup is now largely deprecated in favour of lxml. This proved much better: now all I needed to handle was the (lack of) structure of the pages...

There's a live copy running at mwis.assyrian.org.uk; you can download the source code from GitHub. There are a bunch of improvements that could be made to this code:

1. The speed isn't too bad, but it could be faster. An obvious improvement is to stop doing eight HTTP GETs in series!
2. There's no API.
3. Your geographic options are limited: either the whole UK, or England & Wales, or Scotland. Here in the Central Belt, I'm closer to the English Lake District than I am to the North-West Highlands.
4. The page design is fugly severely functional. Any design experts wanna suggest improvements? Readability on mobile devices is a major bonus.
5. MWIS is dependent on sponsorship for their website-running costs, and for the English and Welsh forecasts. I don't want to take bread out of their mouths, so I should probably add yet more heuristics to the scraper to pull out the "please visit our sponsors" links.
6. Currently all HTML is generated with raw print statements. It would be nicer to use a templating engine of some sort.

A possible solution to (1) and (2) is to move the scraper itself to ScraperWiki, and replace my existing CGI script with some JavaScript that pulls JSON from ScraperWiki and renders it. Anyway, if anyone feels like implementing any of these features for me, I'll gratefully accept your patches :-)

git-deploy

While I was developing the MWIS scraper, I found it was annoying to push to GitHub and then ssh to my host (or rather, switch to a window in which I'd already ssh'ed to my host) and pull my changes. So I wrote the World's Simplest Deployment Script. I've been finding it really useful, and you're welcome to use it yourself.

[In darcs, of course, one would just push to two different repos. Git doesn't really like you pushing to non-bare repositories, so this isn't such a great idea. If you want to know what an industrial-strength deployment setup would look like, I suggest you read this post about the continuous deployment setup at IMVU.]

bfcc - BrainF*** to C compiler

I was on the train, looking through the examples/ directory in the LLVM source tree, and noticed the example BrainF*** front-end. For some reason, it hadn't previously occurred to me quite how simple it would be to write a BF compiler. So I started coding, and had one working by the time I got back to Glasgow (which may sound a long time, but I was on my way back from an Edinburgh.pm meeting and was thus somewhat drunk). You can get it here. aaroncrane suggested a neat hack to provide O(1) arithmetic under certain circumstances: I should add this, so I can claim to have written an optimising BF compiler :-)



All of these programs are open source: share and enjoy. They're all pretty much trivial, but I reckon that creating and releasing something trivial is a great improvement over creating or releasing nothing.

¹ Great Britain is a small, mountainous island on the edge of the North Atlantic. Long-term weather forecasting is a lost cause here.

Last November a few of us from Glasgow.pm went to the North-West England Perl Mongers Hackathon, kindly hosted by Shadowcat Systems at their offices in Lancaster. The following are my notes on the day; I'd intended to present them at Glasgow.pm's December meeting, but the weather meant it was put off until the January meeting last night.

1. The night before, I met up with my friend Caroline for a drink. We hadn't seen each other for a couple of years, and it turned out that we had a lot of catching up to do, so one drink turned into two, which turned into five, which turned into a gig. Then I got up very early and got on one of these, which made me feel like this.
   
   So, Lesson Learned number 1: do not go out and get steaming the night before the Hackday, especially if you're travelling there by a very juddery train.


2. Some Modern Perl modules have very long dependency lists: Task::Kensho, for instance, depends on all of these modules. CPAN is great, but installing and testing all of those modules takes a long time. So, Lesson Learned number 2: if the project you're going to be working on has some dependencies, or is planned to have some dependencies, then find out what they are and install them beforehand. Dually, if you're running a hackday project and you plan to depend on some module or other, tell people about it and encourage them to install it in advance.


3. Lesson Learned number 3: you're going to need a version control repository sooner or later - you might as well set it up in advance and write the URL on the whiteboard for everyone to see when they come in. For a Hackday setup it's probably better to use a push model than a pull-request model; GitHub will support this, but you need to create a Hackday user and add everyone's ssh public keys to its keychain.


4. Communication is really hard. My first commit was at 16.47 because we spent so long arguing about what exactly Oyster was meant to do and how it was meant to work. Most of the time this was because there were people still arguing about things that I'd thought were settled.
   
   So, Lesson Learned number 4: this is one of those cases where it's better to make a decision now than to make the best decision when it's too late and everyone's gone home. And when you've made your decision, communicate it clearly.


5. Other lessons learned: Shadowcat (and NWE.pm more generally) are great people, Osfameron is a dude, pizza is tasty, and hackathons are great fun.

Thanks once again to the Shadowcat team for a great day.

I've updated the JSON utilities first described here. Changes:

• jd outputs JSON, as it should really have done all along. It's now an even thinner wrapper around Makamaka Hannyaharamitu's excellent JSON module :-)
• jf now has a -p option that pretty-prints its output directly.
• jf can now handle several field specifiers at once, and preserves enough of the structure of the input to contain them all. Here's an example:

  $ curl -s -upozorvlak:<my password here> http://api.twitter.com/1/statuses/mentions.json \
  | jf -p user/name user/screen_name text
  [
     {
        "text" : "@pozorvlak I have to admit that if you have polymorphism then
                 things like +. are particularly pointless.",
        "user" : {
           "name" : "Christopher Yocum",
           "screen_name" : "cyocum"
        }
     },
     {
        "text" : "@pozorvlak Huh, I still like the safety that static typing gives you.",
        "user" : {
           "name" : "Christopher Yocum",
           "screen_name" : "cyocum"
        }
     }
  ... etc ...
  ]

  The XPathy syntax is due to Leon Timmermans.

You can download the source or check it out from GitHub. All suggestions (or better, patches!) gratefully received.

So, what else could I do to make these useful? One option would be to allow a wider range of XPath selectors - currently only the child axis is supported - but I'm not sure how to do that and preserve the structure of the input, which is essential for the kind of thing I use jf for. I could certainly document the programs better. For now, though, I think I'll email Makamaka and ask if he'd be interested in including jf in the JSON.pm distribution.

This post is a mea culpa, an admission of failure: if any of you have read my stuff thinking that I know what I'm talking about when it comes to programming, this is your chance to recalibrate. I'm posting in the hopes that by writing this particular ultra-basic technique down in public, I'll never ever ( forget about it )

[The full, working version of PS3 Remuxatron (by Mat Brown, GPLed) is here.]

=pod

... do not be alarmed.

What happened was that I was talking on Reddit with Masklinn about Literate Programming, and s/he wanted to know if there were any systems other than Literate Haskell which allowed for blog posts which are valid code. "Hrmmm," I thought, "I don't see any obstacle to ( doing that with POD... )

Right, back to work.

As I may have mentioned once or twice before, I'm writing up my thesis. This is an intensely slow and depressing process, and the temptation to slack off is overwhelming. Being a geek, I decided to write some code to help me. Writing code rather than writing thesis is still slacking off, obviously, but it's slacking off to a useful end. Writing blog posts about writing code that's meant to help me write my thesis is another matter...

( Read more... )

I'm going to make what should be an uncontroversial statement: if you don't understand and use monads, you are at best a quarter of a Haskell programmer. A corollary of this is that, since using monad transformers is the only (or at least the approved) way to use two or more monads together, if you don't understand and use monad transformers you are at best half a Haskell programmer.

[Another corollary is that I am, at best, about an eighth of a Haskell programmer: though I understand monads well on a theoretical level, I invariably emerge defeated from any attempt to bend them to my will.]

But we'll come back to that later.

Something I've been thinking about for a while is this whole business of ( designing languages to make programs shorter. )

¹ There really ought to be a word that means "would never use a twopenny word when a half-crown word would do", but I can't think of one. English grads? Edit: sesquipedalian! Of course! Thanks, fanf! (Originally, I used "prolix")
² I actually came up with this list by thinking about languages whose users were the most passionate. But they're also extremely concise, which I think is a large part of the reason for the passion. If I were focusing purely on concision, I should probably consider Forth, but I don't know enough about it.
³ J has "boxed arrays" too, which are something like two-dimensional s-expressions, but let's leave those aside for now.
⁴ You might want to raise this objection against Smalltalk, too: objects are members of classes, which are something like types. Now, I've hardly used Smalltalk, so I'm probably talking out of my elbow, but: since everything is an object, and the language has powerful reflection features and duck typing, we can in fact write generic operators that work for objects of many or all classes. But maybe I'm entirely wrong about Smalltalk programming: in which case, please delete all references to the language from my argument.
⁵ Do you find yourself wanting to go out and strangle small fluffy animals every time you have to type out an instance declaration that would be entirely unnecessary in a duck-typed language? I do. Particularly when it doesn't work and spits out some ludicrous error message at me, telling me that I've encountered another stupid corner case of the typeclass system.
⁶ I learned to my surprise the other day that I'm a member of the Geometry and Topology research group, and not the algebra research group as I'd always assumed - apparently universal algebra is now considered a branch of geometry!

Bloody Haskell: it's like a scab I can't stop picking at.

Prompted by something on Reddit, I started thinking about libraries to pluralize (English) words, like the table-name generator in Ruby on Rails or Damian Conway's (rather more complete-looking) Lingua::EN::Inflect for Perl. Such things seem to be called "inflectors". My question is, what would be the idiomatic interface for a Haskell inflector? The obvious thing would be something like

    pluralize :: Inflector -> String -> String

where Inflector is some sort of data structure holding configuration data: classical versus modern plurals, any custom cases, etc. But following on from our earlier discussion of high- and low-level type-checking, it occurred to me that there's a constraint here: only singular nouns should be pluralized. So should we then have

    newtype Singular = String
    newtype Plural = String

    pluralize :: Inflector -> Singular -> Plural

? Or even

module Inflect (makeSingular, pluralize)
    data Singular = Singular String
    data Plural = Plural String

    makeSingular :: String -> Singular
    -- error-checking code goes here, to check that the string passed
    -- is a single word, or something

    pluralize :: Inflector -> Singular -> Plural

so we don't export the constructors for Singular or Plural, ensuring that one can only construct them using our interface? But wouldn't this make client code far uglier than necessary? Should one then provide both options, tagging one as unsafe?

    module Inflect (makeSingular, pluralize, unsafePluralize)
    data Singular = Singular String
    data Plural = Plural String

    makeSingular :: String -> Singular
    -- error-checking code goes here

    unsafePluralize ::Inflector -> String -> String

    pluralize :: Inflector -> Singular -> Plural
    pluralize i (Singular s) = Plural (unsafePluralize i s)

Thoughts?

Implementation-defined languages come in for a lot of flak. Users of certain languages will point to their language's standards document as if it were self-evidently proof of greater inherent worth: a language that's defined by its implementation, it is implied, is always going to be a bit non-U. It may train itself out of its dropped H's and tendency to mispronounce the word "scone"¹, but it will never have the true breeding that comes from a standards document.

Which is daft, because implementation-defined languages ( have some important advantages )

By the way, I'm not saying that all specifications are bad (a good one is an excellent thing to have) or that specification-defined languages have no advantages - I'm assuming that the advantages of specification-defined languages are so well-rehearsed that I don't need to repeat them. Anyone needing further enlightenment is encouraged to go to comp.lang.scheme and say "I think spec-defined languages suck!" :-)

Now for the second part of my rant: Haskell, as we know it today, is an implementation-defined language, defined by the latest CVS snapshot of GHC. "But what about the Haskell Report, and the Revised Report, and Haskell prime, and Hugs, and, er, those other implementations?" I hear you cry. Well, what about them? Every time I asked some question, it seemed, the answer would begin with "first download the latest version of GHC, then turn on these extensions..." A spec for a language that people don't actually use is - well, not useless, if it's sufficiently close to a language that they do use, but it ain't a specification as I understand the term. Everyone in the Haskell community seems to track the latest version of GHC for its new features. This is not spec-like behaviour. Now, as I said above, I don't think that implementation-defined languages are bad: quite the reverse. I just think it would save everyone a lot of bother and false superiority if the community could admit this to itself and to outsiders.

¹ The O is short: "scone" rhymes with "gone", not "groan". Unless you're talking about the town in Scotland, when it rhymes with "boon". People who insist on mispronouncing this word around me will have their scones taken away from them and donated to the Pozorvlak Pedant-Feeding Drive.