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 :-)

There was a recent mailing list post by Andrew Coppin (which received some discussion on programming.reddit) in which he bemoans the way that GHC, when presented with reasonable-looking code, can suddenly and mysteriously decide that it needs to allocate gigabytes of memory, slowing your system to a crawl for ages (I've had similar problems myself). Andrew's example was the following:

I offer up the following example:

mean xs = sum xs / length xs

Now try, say, mean [1.. 1e9], and watch GHC eat several GB of RAM. (!!)

This is not so mysterious when you remember that Haskell uses linked lists as its native list structure, and so the only way to calculate length xs is to traverse the list a second time: the runtime system "helpfully" keeps around the copy of xs that it generated while calculating sum xs, and you have a space leak. But what to do about it?

( The story so far )

( Doing it in Perl )

( Doing it in Ruby )

( Take-home messages )

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?

My post about design patterns and if-statements in Smalltalk yesterday got a very pleasing reaction, garnering some informative comments from knowledgeable people and making the front page of programming.reddit. I guess I should have checked my facts on Smalltalk semantics more carefully before clicking "Post" :-) One comment that particularly interested me was this one (sadly anonymous), which shows a rather cute trick for using Smalltalk-style keyword methods in Haskell:

data Then = Then
data Else = Else

if' :: Bool -> Then -> a -> Else -> a -> a
if' True Then t Else f = t
if' False Then t Else f = f

Now that's pretty cool, and could even be useful for DSL implementation¹. But there's a problem. See the repeated code?

data Then = Then
data Else = Else

Here, let me show it to you the way it looks to me:

data Then = Then
data Else = Else

Literally half the elements that aren't pure syntax on those lines are repeated. What I'd like to do is define a keyword function, and then just write

keyword Then
keyword Else

Or, better,

keywords Then Else

Not a big deal, you might think, but what if you were writing a whole EDSL with many keywords? Or many different EDSLs? And it's not just the repetition: by defining a keywords function, I'd move the code up an abstraction level, making my intent clearer. We could of course write

data Keywords = Then | Else

but then we lose the benefit of compile-time syntax checking of our EDSL. Well, I guess our pseudo-keywords are syntactic sugar anyway, so it doesn't really matter. But still.

A few days ago, someone asked me for an example of code that's repetitive in Haskell but wouldn't be in Perl, and here's one. In Perl, and probably in Python, I could write a keywords function. It would be ugly, and would involve hairy symbol-table hacking or calls to eval, but the user wouldn't need to know that and I'd only need to write it once (never mind the fact that the "pseudo-keyworded functions" pattern wouldn't actually make any sense in Perl...). In Lisp or Ruby, I wouldn't need to write it at all, because I could use symbols instead. But perhaps this kind of thing (and other, more egregious examples) are just the price we pay for Haskell's type system, and are more than balanced out by greater opportunities for concision and abstraction elsewhere?

Nah, bollocks to that. We can do better.

( Template Haskell to the rescue! )

The final version of Main.hs is here, and the final version of Keyword.hs is here. Not entirely straightforward, but we pretty much got there in the end. Would it be worth posting these code samples to the TH wiki, and perhaps linking here? Anyway, it's nice to have finally got this simple stuff to work: hopefully I'll be able to get some more difficult things to work soon, and this should reduce the amount of frustration and needlessly duplicated code in my Haskell programming experience.

¹ Did you know you can do this in (plain) TeX, too?

\def\fred #1 barney #2 betty{#1#2}

\fred Hello there, barney Wilma betty !

produces "Hello there, Wilma!".

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?

This afternoon I gratefully took possession of the copy of Iverson's A Programming Language which the library had been holding for me. Within two sentences, he'd managed to say something so thought-provoking that I felt compelled to ( post about it here. )

An email from the people to whom I applied:

( I missed the point entirely, it seems :-( )

I wouldn't mind so much if they'd asked for a "Personal Statement" or something - to me, the term "Research Proposal" suggests that it should mainly be about the research that you propose to undertake. But apparently not. I've got until, er, tomorrow to submit another one :-(

In other news, hearken ye programmers unto Steve Yegge's latest drunken blog rant. I've been having similar thoughts myself, related to Bad Things that have happened to me with big codebases: it's a large part of why I'm so interested in the APL family*. But I'd like to stick my neck out and say that the way Steve feels about Java is the way I feel about Haskell.

* I note in passing that that page comes up first in a Google search for "APL lesson" - epic win!

Another one for the "using computers to investigate trivial mathematics" file...

I had another meeting with my STEP student today, who showed me the following problem: find a simple expression for the sum of the squares of the nth and (n-1)st Fibonacci numbers. In other words, what is F_n² + F_n-1²? We're taking the zeroth Fibonacci number to be 0, and the first to be 1.

( My conjectured answer, and some supporting evidence )

I still can't see a proof, but no doubt one will occur to me in the morning...

In other news, I've been playing around a bit more with the Catalan numbers - in fact, I briefly thought they might have something to do with my actual research, and got very excited, but on further reflection I don't think they're very helpful. But it seems likely that the reason the "naive" J code hung didn't have all that much to do with the naiveté of the algorithm - using the same algorithm, and on the same machine, MIT Scheme (interpreted) was able to calculate the 100,000th Catalan number in around 100s, with no paging or machine-locking, and Python was able to calculate it in under 20s! It seems to me that J is using either a poor bignum implementation, or (more likely) a very poor implementation of the binomial coefficients - I discussed this with my father (we're that kind of family), and he suggested that it's probably written recursively, and thus consumes vast amounts of stack space. Easy enough to fix, if only the J interpreter weren't closed-source...

Short version: I'm going to write a mildly cool and somewhat useful utility in Ruby which shows off Ruby's reflection capabilities and has something to do with my PhD thesis.

OK, first ( some (not really necessary) mathematical background )

OK, that's the maths out of the way, on to the code. The ability to do categorical composition of functions is useful, so maybe the multicategorical kind would be useful too? Ideally, we'd like a compose function which took a function f and a list of functions g₁, g₂, ... g_n, and returned the function f.(g₁,...g_n) which takes (x₁¹, ... x_n^m_n) to f(g₁(x₁¹ ... x₁^m₁) ... g₁(x_n¹ ... x_n^m_n)) Unpleasant multiple sequences seem to be an unfortunate fact of life when dealing with this stuff. Anyway, here's ( an implementation in Ruby )

I'm sure this code can be improved, and I'd love to hear how. I don't think it's possible to write a function like this in vanilla Haskell, and writing one in Template Haskell is beyond my template-fu. It would be possible in Perl, but because of Perl's eccentric argument-passing conventions, you'd have to manually pass the arities in. This also uglifies the code somewhat.