Beware of the Train

I did warn you...

A while back, markdominus wrote an article about the Design Patterns movement, in which he claimed that design patterns are basically signs of weaknesses in programming languages; if a language forces you to implement the same pattern of code over and over in different programs, that's a sign that your language is insufficiently high-level with respect to problems that your users actually encounter, so language designers should focus on patterns as places where their languages could be improved. This prompted some reaction in the tech blogosphere, including this response from Ralph Johnson, one of the authors of the original Design Patterns book. Dominus responded here, correcting some of Johnson's misunderstandings and commenting further; in fact, though, they're mostly in agreement (and I'm pretty much in agreement with them both, FWIW).

Everyone up to speed? Good.

Something Dominus didn't seem to get was Johnson's distinction between things that are in the language and things that are in the library. Johnson seems to think that there's a three-tier hierarchy:

1) Language features
2) Library code (available to every application)
3) User code (must be written for each application).

He claims that it can be a good tradeoff to leave something as a pattern, because the alternative might be to overcomplicate the standard library or, even worse, the language itself - he seems to have visions of a language with decorator, abstractFactory etc. as keywords. Dominus largely refutes this claim in his response. But more interestingly, Dominus thinks that the distinction between 1 and 2 is basically artificial - is C's printf (or Haskell's standard prelude) part of the language or the library? It might matter to language implementers, but to the average programmer, the distinction's pretty unimportant. Now, this is a good point, but I think I can see what Johnson's getting at. Remember that Johnson's a Smalltalker. Let's consider (finally) how Smalltalk handles if-statements, which in most languages are built-in syntactic elements of the language.

In Smalltalk, booleans (ie, True or False) are objects: specifically, they're instantiations of the abstract base class Boolean, or rather of its two subclasses True and False. So every boolean has type True or False, and no actual member data. Bool has two virtual functions, ifTrue: and ifFalse:, which take as their argument a block of code. Both True and False override these functions; True's version of ifTrue: calls the code it's passed, and False's version does nothing (and vice-versa for ifFalse:). Here's an example:

a < b
  ifTrue: [^'a is less than b']
  ifFalse: [^'a is greater than or equal to b']

Those things in square brackets are essentially anonymous functions, by the way. Except they're objects, because everything is an object in Smalltalk. Now, what's happening there is that we call a's "<" method, with argument b; this returns a boolean. We call its ifTrue: and ifFalse: methods, passing as arguments the code we want executed in either case. The effect is the same as that of the Ruby code

if a < b then
  puts "a is less than b"
else
  puts "a is greater than or equal to b"
end

but what other languages do with special syntax, Smalltalk does as a special case of method-dispatch. (Code samples from here). This completely blew me away when someone (pdcawley?) first told me about it. Haskell does something similar, of course. [Edit: no it doesn't - see comments. But it could. I've also got some details of the Smalltalk wrong.]

Now, back to Johnson. Smalltalk's designers had three choices: bake special syntax for if-statements into the language, implement it in Smalltalk library code in terms of more general concepts that were part of the language, or force the programmer to do the work him/herself every time (using, I dunno, computed gotos or something). They made the unusual choice to go for the second option. While this doesn't matter if all you want are if-statements, it affects the language in other ways: the powerful abstraction mechanism needed to do this is available to the user to define new features.

This, I think, is the real distinction between "language" and "library": if the feature in question could have been implemented by your users using a combination of other features, it might as well be part of the library. Smalltalk's if-statements pass this test, as do (say) Lisp's looping constructs. Haskell's monads fail, because of do-notation: if a Haskell programmer wanted to add similar syntax for (say) comonads, would they be able to? I don't think so, and so it follows that monads are actually baked into the language. Several of Perl's built-in functions do things that user functions wouldn't be able to do, and thus should count as part of the language, even though they feel like part of a library.

So here's where it applies to design patterns: if your programmers find themselves having to implement essentially the same code over and over again, it's because you don't provide powerful enough abstraction mechanisms for programmers to write library modules that would do the job for them. Programmers are (rightly) lazy, and don't do work many times if they can do it once and then use that solution over and over again. So the fact that it's a design pattern means that it can't be in the library, and your language needs fixing: either by special-casing extra language features in or (preferably) by making your abstraction features more powerful, so the necessary library code can be written.

Did anyone else know that Emacs' Calc mode is effectively a full-featured computer algebra system? Symbolic manipulation, vectors, matrices, calculus, graphing (provided via gnuplot), all the stuff you'd expect.

No gamepad integration that I could see, though :-)

No thesis today - I had a six hour job interview through in Edinburgh, for the maths consultancy people (who, it turns out, are university friends of my Canadian friend Jeff - small world!). The interview went reasonably well, though it could have been better - I was a bit stressed out by the whole interview situation and wasn't as sharp as I could have been. The maths questions (all based on tasks they've actually encountered in the field) were completely outside my area, and hence somewhat challenging for me, but I managed to come up with not-entirely-stupid answers to them without too many hints. The programming questions were mostly straightforward (what does this bit of recursive Prolog do, implement the following standard mathematical functions in Java, write a simple method against this random spec), apart from one where I had to find an error in some threaded Java code. Did I mention that I've never written threaded code before, and I don't speak Java very well? Then they gave me lunch, then brought me back to the office and asked me all the questions from the first round again. Apparently the answer I gave to the "where would you like to be in five years?" question was very good :-)

Anyway, the company looks really cool, and the people all seemed to be good guys, so fingers crossed on that one. They've got another couple of people to interview, and they'll get back to me some time in March.

totherme kindly drew my attention to this blog post today. The author, Slava Akhmechet, tries to explain away that horrible feeling of unproductivity and frustration that I know so well from my attempts to use Haskell: his claim is that it's just that my expectations are miscalibrated from using imperative languages. A Haskell solution to a given problem, he claims, will take the same amount of thought as a solution in another language, but much less typing: by simple statistics, therefore, you're going to spend a lot of time staring at the screen not doing anything visible, and this can feel very unproductive if you're not used to it.

As an example, he gives the code

extractWidgets :: (Data a) => a -> [String]
extractWidgets = nub . map (\(HsIdent a)->a) . listify isWidget
    where isWidget (HsIdent actionName)
              | "Widget" `isSuffixOf` actionName = True
          isWidget _ = False

Bleh! :-( This function takes a parse tree representing some Haskell code, and extracts all the identifiers ending in "Widget", then removes the duplicates. Slava challenges any Java programmers reading to do the same in five lines or fewer.

( Pointless language pissing match, including some Arc coding )

On language concision in general: I typically find that Haskell requires fewer lines for a given program, but Perl requires fewer characters, and they both use about the same number of tokens. Lisp is longer and messier than Haskell for easy problems, but quickly gains ground as the problems get harder.¹ The APL family own on all three axes. This is extremely unscientific, of course, and because I don't know much APL/J I can't be sure how it extends to harder problems. I did once email Paul Graham asking why, if succinctness was power, he didn't switch to a member of the APL family; he has yet to reply, but I don't attach any great significance to this.

And having got all that stuff out of my head, I'm going back to bed. Hopefully I'll be able to sleep this time :-)

¹Fun exercise: translate the example code in On Lisp into Haskell (or Perl, Ruby, etc.). It really helps you to get to grips with the material in the book. I found that the Haskell solutions were shorter and cleaner than the Lisp solutions up until about a third of the way through the book, at which point Lisp started to catch up with a vengeance: shortly thereafter, he was doing things in a few lines of Lisp that simply couldn't be done in finitely many lines of Haskell. I'd be very interested to see solutions written by someone who knew what they were doing, though!

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

I'm in the middle of writing up a research proposal for a postdoc position I'm applying for. I've had enough of categorification for a while, and it struck me that doing formal semantics for a simple language in the APL family (J, K, A+, Matlab...) could be both Fun and Interesting. Some poking around on Google and MathSciNet suggests that nobody's done anything in this vein before - I've downloaded all the relevant looking papers (all three or four of them), and intend to read them this evening after climbing :-)

The trouble is that I've never written anything like this before. Some of you, I know, have: does this look remotely sane? Does the topic sound interesting? The second section, you'll be pleased to hear, is very much a zeroth draft at this stage :-)

Perhaps you've had this experience:

You have a problem, which you've bashed your head against for ages. You can't see what to do about it. Finally, you decide to ask a friend, or email the lecturer, or put it up to your boss, or whatever. You get hold of him/her, and start explaining your problem. But by the time you're halfway in, the very act of explaining your problem forces you to clarify it in your own mind, and the solution becomes obvious to you. You drift off, mid-sentence. "Sorry," you say, "I've just seen what to do. Sorry to bother you."

Your friend was acting as a debugging teddy. The term comes from a university computer room back in the Dark Ages of computing which kept an actual teddy bear for this purpose: you were required to explain your problem to the teddy before you were allowed to ask an actual human being. At the startup where totherme and I used to work, we had a talking Yoda doll. But Master Yoda wasn't so good, precisely because he could talk and not just act as a sounding-board for your own thoughts: at one point, Management discovered that Master Yoda had been making major architectural decisions, and replaced him with a life-size cardboard cutout of Buffy the Vampire Slayer.<sup>1

1</sup> She had business cards and everything. "Buffy Summers, [company] Ltd. Pensions Advisor (stakeholder)".

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

SICP section 2.4 set off my wheel-reinvention alarms in a big way. It discusses writing code to use complex numbers in a representation-agnostic way; your complex numbers can be either in polar (r, θ) form or rectangular (x + i y) form, and ideally you'd like not to care. Their solution? "Tag" each number with its representation, by passing around pairs whose first element is a symbol: either 'rectangular or 'polar. Your procedures to (say) find the magnitude of your complex numbers first check the symbol and then (in a nice, generic, data-driven, extensible way) dispatch the correct procedure given the representation you're using.

Which is all very well, but isn't this... y'know... a type system? Given that Scheme obviously has some sort of type system in place so it can complain when I try to add 1 to "fred", aren't we reinventing a pretty large wheel? Is this, in fact, final and clinching proof of Smith's (First) Law?

Well, yes and no. Yes, we are implementing a simple type system, but given that the main thrust of the book is how to write interpreters and compilers, that's a pretty useful thing to know. It's also interesting to see how you can whip up your own type system (and module system) atop pairs and lambdas. It's a very simple type system, but it's not too hard to see how, with a slightly more complicated data structure storing your dispatch tables and possibly some macros to take away the busywork, you could implement inheritance, generics... even something like Frink's physical units tracking. And you could mix and match such systems throughout your program. I can't decide if that would be really really cool, or a maintenance and reuse nightmare :-)