Beware of the Train

I've got a problem: I've had an idea I want to write about, but it depends on two or three other ideas I wanted to write about but never got around to. So I'm going to write this post in a top-down, Wirthian fashion, stubbing out those other posts: maybe, if there's enough interest, I'll come back and write them properly and replace the stubs here with links. OK with everyone?

Right, on with the motley.

Stub post no. 1
Extreme Programming (XP), whether intentionally or unintentionally (and my money is on "intentionally, but try getting them to admit it") is really good for getting work out of people who are bright but have short attention spans. This is a Good Thing. It's most obvious in the case of pair programming - imagine saying to your partner "Y'know, this is kinda hard. Let's surf Reddit for a while" - but actually, most XP practices have this benefit. Short feedback cycles, concrete rewards, definite "next moves" (given by failing tests and the "simplest thing that could possibly work" approach) - all of these things have the effect of maintaining flow and reducing the incentive to slack off. It's programming as a highly addictive game. Dynamic languages work well with this approach, because they make it as easy as possible to get something up and running, and to test the things you've written.

Stub post no. 2
Haskell is the opposite. It encourages deep thinking, and everything about the language makes it as hard as possible to get something running unless it's just right. Screw up, and you're not presented with a running program and a failing test that you can run in the debugger; you're presented with an unfriendly compiler message and a bunch of dead code that you can't interrogate in any meaningful way. After a morning hour few minutes of this (usually involving no small loss of hair), the consultant Barbie that lives in my head invariably says "Statically-typed pure functional programming is hard. Let's go shopping!" And I, fed up and mindful of my scalp, agree. This is why I am no good at Haskell.

Stub post no. 3
Everything I read by or about the climber Dave MacLeod (blog) makes me more inspired by him. Partly for his visionary climbs, but mostly for his approach to choosing, training for and tackling really hard problems, which I think should generalise really well, if only I could put my finger on what exactly it is. It helps that he's a really friendly, pleasant guy in person. Check out the BAFTA-winning film Echo Wall that he and his wife made about his preparation for his first ascent of the trad route of the same name. If you're in Edinburgh, you can borrow my DVD, I'm positively eager to lend it out.

Anyway, something Dave wrote about training (which I can't be arsed to find right now) said that in order to train effectively, you have to be constantly pushing yourself in some way: either in terms of power, or stamina, or technique, or fear¹, or whatever. You have to find your comfort zone and then consciously go beyond it, in whichever direction you wish to improve. As you improve, your comfort zone shifts, and you need to keep pushing yourself harder and harder in order to continue to improve. But (and here's the interesting bit), he said that if you do this for long enough, your whole conception of comfort shifts, and you start to feel uncomfortable if you aren't pushing yourself in some way.

So, here's the thought I had. Maybe all the Haskellers have been training themselves Dave MacLeod-stylee, and now only feel comfortable pushing themselves really hard, and that's why they like using such a bloody difficult language.

¹ About a year and a half ago, I was seconding a route called Dives/Better Things (Hard Severe) in Wales, and got to a bit that was a bit too hard and a bit too scary. I floundered around for a bit, getting more and more freaked out, and then said to myself "What would Cale Gibbard do? He'd pause for a bit, think really hard, work out exactly what to do next, and then do that. OK. Do that, then." I have no idea if Cale climbs, but it did the trick. Cale, if you're reading, thanks for that :-)

Whenever I spot myself doing something repeatedly on a computer, I try to automate it. Consequently, I have a directory full of random little scripts, and a long list of aliases in my .bash_profile, all of which arose because I had to do something lots of times. Often, these scripts and aliases call other ones which I wrote earlier, as I spot higher-level patterns in what I'm doing. But every time, I have to fight against the False Laziness that tells me not to bother, I'll only have to do it once or twice more, and it's not worth the effort of doing it right.

So yesterday I added the following line to my .bash_profile:

alias viprof="vim ~/.bash_profile && source ~/.bash_profile"

We'll see how it works out.

In my thesis, there are a lot of places where I write expressions like

f1 x ... x fn

or

 (Σ y1, ... , Σ yn) 

or something similar. The code to generate this is repetitive. It would be nice to abstract out the general pattern of "list of things indexed from 1 to n, combined using some binary operation". But there's a problem: the indexing can occur anywhere in what might be quite a complicated expression. Rather than handing our "one to n" macro an ordinary TeX expression, we need to hand it an expression with placeholders: that is, we need to hand it a macro. Then our one-to-n macro can invoke the macro we handed it with the arguments "1" and "n" to generate the code we want.

This is quite a common thing to want to do in computer programming. It goes under various names, but probably the most common is "callback". More precisely, the callback is the piece of code accepted by the one-to-n macro, which it then invokes. Callbacks are very generally useful - they're the standard way of writing code for graphical user interfaces (if you've ever written an event handler in VB or an ActionListener in Java, you were writing callbacks), but they're also used for XML processing (via SAX) and all sorts of other things. Ruby's iterators and Smalltalk's if-statements take callbacks. If you've ever used the map function in Perl or Lisp or Python or Haskell, you were writing a callback. But can we write callback-based code in TeX?

Well, ( yes, as it turns out. )

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.]

Those of you who do scientific computation may be interested in this link:

Bye Matlab, hello Python, thanks Sage.

Short version: Sage is a bundle of all of the various numeric/scientific/graphing tools for Python, made easy to download and install (even if you don't have root access, apparently). According to the blogger linked above, it's now good enough to serve as a replacement for Matlab (and it has ambitions to be a replacement for Maple and Mathematica too, though I don't know how far along it is). It integrates with R, Gap, etc. And because it's Python, you get a real, high-level, well-designed programming language with a proper environment to do your coding in.

In other news, wormwood_pearl finished her Finals yesterday. As you can imagine, we're both pretty relieved. There's no tradition of meeting people outside Finals here like there is in Oxford, but I went along with a bottle of champagne anyway - and only then remembered that public drinking is against Glasgow bylaws. Drat it. We went out to lunch, the bottle went into the Department fridge, and we subsequently went round to her sisters' and drank it there while watching Layer Cake. Because we're that exciting.

=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.

For the past couple of years (longer, actually), I've been thinking a lot about this business of static and dynamic typing in programming languages. Here's my current position on the matter.

Static and dynamic typing encourage and reward quite remarkably different approaches to the creation of software: everything from the nitty-gritty, (sit and think?)-edit-(compile?)-run-(test?)-(debug?)-(repeat?) cycle to the design (at all levels) of the software to be created, taking in every aspect of the tools and process used to support this design and implementation. Also, the choice of static or dynamic typing is best understood as part of a larger attitude towards development. Unfortunately, the use of a dynamic mindset with a static language not only means that you can't take advantage of the tools available (or even see why they'd be useful), it actively hinders success. The same is true for approaching a dynamic language with a static mindset.

I would therefore like to propose Pozorvlak's Conjectures:

1. If you find that a modern dynamic type system causes more problems than it solves, you're probably doing it wrong.
2. If you find that a modern static type system causes more problems than it solves, you're probably doing it wrong.

For instance, I find Haskell's type system causes me many more problems than it solves. Discussions with more expert Haskell users suggest that I am indeed doing it wrong. This guy, on the other hand, finds that "the dynamic languages stick out like sore thumbs because of the whole class of dynamic run time errors that show up that don't even appear in the statically typed languages". If you find this, I claim that it's because your code is not polymorphic enough¹. You can get away with having code which only accepts data of very restricted types when the compiler does all the checks for you statically. When it doesn't, you're better off writing code that behaves well for a wider class of inputs, and dynamic languages give you much more facility to do this. Once you learn to code like this, your problems largely go away. As a bonus, your code becomes more flexible, and whole classes of techniques become possible that would have been literally unthinkable before. Similar claims, it appears, can be made for static languages: at the higher levels of mastery, one can use a static type system as a theorem-prover to establish some quite nontrivial properties of your program automatically and across the entire codebase. This allows for some excitingly different approaches to program development.

A corollary is that if you ever finding yourself saying that your port of Feature X to Language Y is better than the original Feature X solely because it's (statically|dynamically) typed and the original Feature X was the other one, you should probably save your breath. It will probably also be worth your while to go back and determine what advantages the opposite choice of typing regimen gave to Feature X's users.

¹ A less interesting, but probably valid conjecture is that you're also not testing enough, or at least testing the wrong things. But this can't be the only answer. Dynamic programmers, in general, are not idiots; they are usually also Lazy, in the good sense. They're smart enough to work out that writing the equivalent isa_ok() test every time they would have written a type declaration in Java or whatever is no time-saver at all. Hence, they must need less type information overall for their code to be correct.

A guy on Reddit pointed me at this article today. It's the Wikipedia biography of the Welsh computer scientist Donald Davies. Like my father, he was from the Rhondda Valley; he was the co-inventor of packet-switched networks (like this big one you're using right now); and he once found a bug in Alan Turing's code, before the first computer had been built :-)

I think he may be my new hero.

In other news:

• I've just finished Portal. It was great, but far too short :-( If you haven't played it yet, then you should go and buy/download a copy right now, and cover your ears and sing "La la la la la..." until it's loaded to avoid being spoilered like I was. The puzzles are still a lot of fun, but the plot and jokes would have been a lot better if I hadn't half-known they were coming.
  [And I didn't find "The Cake is a Lie!", even though I was looking out for it...]
• Spent a lot of time sitting at the computer today, but didn't get any thesis done. Bah.
• After a similarly unproductive morning yesterday, I went to the climbing wall, and had quite a good session: I did two 6as (which is good, for me), led a widely-agreed-to-be-undergraded 5+, and finally knocked off a 5+ with a big scary overhang that had been tormenting me for months. Yay!
• This may be the most awe-inspiring programming war story I've ever read.
• Letter from Linacre: I didn't get the job. Never mind.
• The winter mountaineering course I was booked on next weekend has been cancelled due to lack of interest. Just when the snow's started up again! I'm much more annoyed about that than about the rest, to be honest.

Ah well, tomorrow will be better. Anyway, have a look at this video, which is the trailer for one of the films I saw at the mountain film festival on Saturday:



That sea arch he's climbing up the underside of, by the way, is provisionally graded as a French 9b :-)

A comparison of the Haskell argmunger with its Arc equivalent (or even its Perl equivalent) should make something clear. It's been claimed that Haskell doesn't need macros, because most of the things that Lispers need macros for can be done in Haskell using lazy evaluation and so on. But the argmunger example makes it clear that there are things for which Lispers don't need macros and Haskellers do - if not Template Haskell macros, then SYB or DRiFT or some other macro-like facility.

Lispers often say that coding in other languages feels like manually generating macroexpansions. I'm nobody's idea of a Lisp hacker, but I often feel like this when I'm writing Haskell. Which is why I'm learning about Template Haskell even though I'm not yet au fait with things like do-notation and monad transformers, which most Haskell experts would probably consider more basic. Would you choose before or after you'd walked to Moscow to staunch the blood from your severed arm?

[The hope was that this post would come in three somewhat independent sections: one pure programming, in which we develop a small utility in Template Haskell; one largely mathematics, at the upper-level high school to beginning undergraduate level, wherein we describe another approach to constructing our utility; and one purely mathematical, more sophisticated but fairly handwavy, wherein I relate all this stuff to my research interests and describe where it leads. The idea was that you could skip the code and jump to the maths, or read the code and skip the maths, or whatever. However, just the first section has now taken far longer than I'd budgeted, both in time and in space, so I'll save the other two for a later post.]

In a recent post, Hitesh Jasani writes about Haskell's flip operator, which takes a function f and returns a function which behaves like f with the order of its first two arguments reversed. So (flip f) x y z w = f y x z w (we write function application without brackets, as is customary in Haskell). I pointed out to Hitesh that actually, we could write such a function in almost any language which supports higher-order functions, and in dynamic languages (like Perl or Lisp) we can go further, and write a function argmunge, which accepts two functions and permutes the arguments of the first one (the "victim") according to the second (the "munger"). So

(argmunge f g) x1 x2 x3 x4 ... = f xg 1 xg 2 xg 3 xg 4  ...

Here's an implementation of argmunge in Perl, and some code to exercise it:

sub argmunge {
    my $func = shift;
    my $munger = shift; # not necessarily a permutation
    return sub { $func->(@_[@$munger]); }
}

sub myprint {
    print "Called with args ".join(", ", @_)."\n";
}

argmunge(\&myprint, [2,5,5,6])->(0,1,2,3,4,5,6);
argmunge(\&myprint, [3,2,1])->("fred", "barney", "betty", "wilma");

When run, this displays

Called with args 2, 5, 5, 6
Called with args wilma, betty, barney

Here we don't pass the munger in as a function, but rather as a list of values [g(0), g(1), ..., g(n)]. I'm prouder of that code than I probably should be, because it relies on some nice Perl features to work as it does; namely, Perl's argument-passing convention (in which all arguments are passed to a function as a single array called @_), list slicing (in which you can index into a list with another list), and list flattening (in which inclusion of one list in another splices the inner list into the outer list, resulting in a flat list). I remarked that it wouldn't be possible to write a general argmunger in Haskell, because the type of the result depends crucially on the actual value of the munging function. It ought to be possible to write one in a dependently-typed language like Cayenne - anyone care to do so?

[Edit: it's possible to write an even nicer version in Arc.]

Anyway, it may not be possible in vanilla Haskell, but ( it is possible using templates. )

The final code can be found here. As always, all suggestions for how I could improve my code or my development practices are gratefully received!