Haskell, guarantees and pusillanimity

[pozorvlak]

Many times in the course of my Haskell apprenticeship, I've had conversations of the following form:

Me: I want to do X in Haskell, but the obvious thing doesn't work. How do I do it?
Sensei (usually Duncan or totherme): Oh no, you can't do that! If you could do that, then you could have a transperambic Papadopolous twisted asiatic sine-curve freezeglargle Windhoek chromium bebop.
Me: Er, come again?
Sensei: well, [note of horror creeps into voice] it would be really bad! You could get [thing that doesn't sound all that bad, really].
Me: But that's a good thing/Nah, that would never happen/would never happen in real-world code/that's a price I'd gladly pay.

The classic example being, of course:

Me: I want integer-parametrized types for this code I'm writing. Doing without requires you to either write infinitely many lines of code, or write your own run-time type-checking code. This is bad and ugly.
Duncan: But if you did that, your type language wouldn't be computable!
Me: Er, so?
Duncan: Well, it would be Turing-complete.
Me: That's a good thing, surely?
Duncan: No! [note of horror] It would suffer from the halting problem! You could have compilations that would never finish!
Me: [see above responses]

Edit: Duncan denies having said this. To be fair, it was in 2003, so I may have misremembered.
Further edit: I've remembered a better example.

As I've mentioned a few dozen times, I'm coming from a language community that positively embraces ambiguity and irregularity; furthermore, I've been heavily influenced by Paul Graham and his "expressiveness and power above all!" doctrine of language design (and as it turns out, non-terminating compilations are a rare but not unknown problem with Lisp macros, which Lispers accept as a price worth paying). Now, acquiring a new way of thinking about programming is a major part of the reason I'm learning Haskell in the first place, but the frequency with which I'd butt up against some daft-seeming restriction, and the frequency with which I'd be told that this was to prevent something that either seemed harmless or which I knew to be useful, has led me to occasionally lose the humility appropriate to one of my experience.

Previously, I could only think of three reasons for this phenomenon:

1. Sheer endemic pusillanimity on the part of the entire Haskell community.
2. Sheer ignorance on the part of same (not very likely, really)
3. (More charitably) Haskell development is mostly in the hands of academics: hence, language features that allow you to write cool compilers get prioritized over those that allow you to write cool programs.

Now, I think 3) is part of it, but recently totherme sent me a link to a couple of articles that suggests a more interesting possibility: Haskell users prefer guarantees to expressivity. This is reasonably clear in the case of (say) the type system, or referential transparency, but I think it reflects a deeper attitude, that maybe isn't widely understood explicitly.

Here are the links: Does Haskell need macros?
Haskell, bondage-and-discipline and separation-of-concerns programming.

The first article says that Haskell doesn't need macros, because it can already do most of what they provide and the pain they cause outweighs the additional gain. He undermines himself somewhat by ignoring the fact that Haskell already has not one but two macro systems (Template Haskell and cpp, which is used heavily in a lot of Haskell library code), and by seriously underestimating the power of macros. But I digress. His conclusion is revealing: "Macros are quite a painful cost to a language, they reduce the assumptions that people can make and require people to play hunt the macro. Haskell really doesn't need them!"

The second article supports my thesis even more clearly: it's a discussion of the kind of things that can be done once you can guarantee that your language has laziness, referential transparency, etc. Another revealing quotation:

The second thing that purity affords us is that entire programs are mathematical structures themselves and can be manipulated not only in the sense above but also in that theorems satisfied by specific functions can be employed to optimize code — not anymore in the heuristic-working-in-the-dark sense of ordinary optimizing compilers, but in the sense of understanding the actual structure to be done.

This is in particular reference to the functoriality of the List datatype: we know that (map f).(map g) = map (f.g), and so we can apply this transformation wherever we like, reducing two loops into one. Undeniably cool stuff, and Haskell's performance in the Great Computer Language Shootout provides further ammunition. While one could do this kind of thing for imperative languages, Haskell's comparatively simple mathematical structure allows us to prove many more theorems with human-sized brains, and to implement them with compilers more simply. As the author puts it: "giving up destructive updates becomes closer to a doctor advising you to give up trans fats in the name of your health and all the other fun things you can do with a healthy life."

I've heard Haskell described in the following way:

<skew> Besides, don't think aircraft carrier, think mecha. The type system is a great amplifier of careful reasoning and propagator of intent. If somebody starts muttering about bondage, just tell them "those straps are there so the servos can follow *me*".

I haven't yet found this to be true, but maybe the second article could be summarized as "You can't move your legs more than twenty degrees because we needed the room for the flight system. Stop complaining that you can't walk properly, because we've used the extra space afforded to give you something better."

This approach to language design has been tried before (albeit sometimes by accident). For instance, Fortran's lack of dynamic memory allows for some crazy optimising compilers: speed of the order of ten times that of gcc-produced code is not unknown. SQL's basis in relational algebra allows for some nifty query optimisation (and rhetoric very similar to that which you hear from Haskellites). The theory of regular expressions is rooted in the mathematical theory of automata, and many implementations have used this.

Except, in all the above cases, it screws up. It turns out that you really need dynamic memory a lot of the time, so Fortran hackers just declare a big array and use it as a heap, with indexes as pointers. SQL turns out to be extremely painful for some surprisingly common operations. Vanilla regular expressions turn out not to be useful enough, and need extending. In most cases, you end up with something worse than if you'd just written a less restrictive language in the first place.

Haskellers are no doubt at this point jumping up and down and saying "But we have monads! Monads allow you to circumvent the restrictions in a controlled and type-safe way!" Well, some of the time. They don't, for instance, provide any help with the problem I mentioned at the beginning of this rant. Yes, monads are cool (hey, I'm a category theorist, I find it simply wonderful that a categorical tool invented for universal algebra has real-world applications in programming), and yes, they provide an elegant solution to the problem of isolating Naughty Code in Haskell, but no, they're not a solution to everything.

[Here's something that frequently bugs me: why can't you detect Bad Code when compiling, and then mark the code and anything that calls it as Bad unless the programmer has put in a "Badness ends here" marker? I'm thinking of code that presents a referentially transparent interface, but does state-y stuff internally. Is this fundamentally incompatible with first-class functions? Would it slow down compilation too much?]

So, Haskellers: am I right? More importantly, is this widely known? Is it explicitly written down anywhere? (The second article comes very close, but I don't think it gets there in full generality). Because it strikes me that it would be a good thing to tell newbies as early as possible, and also a good thing to have it explicit so it can be appealed to, or (better) debated.

Comments

[totherme.livejournal.com]

Except, in all the above cases, it screws up. It turns out that you really need dynamic memory a lot of the time...

I think it's worth trying to imagine what it would mean to not screw up. Is there an underlying assumption here, that there exists a holy-grail language, which can precisely and elegantly describe everything in the universe? Is it possible that the languages mentioned work well enough in their own domains, only to require hacks and/or extensions when you try to use them for something unexpected?

TBH - most of the time, I write pure, not extended regular expressions (I use macros, like \w \W and \s - but these fall well within the theory - being equivalent to pure regexps like [a..zA..Z0..9], etc). When I want to do more complex things, I tend to use different tools...

If we resign ourselves for a moment to working with a language that comes short of being the holy grail, then perhaps the interesting question is about the shape of the domain of that language?

Of course, most "general purpose" programming languages have quite funny shapes... I certainly think that there's a huge number of problems which can be more elegantly solved in haskell (using the wonderful guarantees it gives us) than in any other common current language...

[pozorvlak.livejournal.com]

I think it's worth trying to imagine what it would mean to not screw up.

That's an interesting question! And to be honest, I don't really know the answer. I guess by "screw up" I meant "the restrictions you enforce condemn the language to an excessively narrow niche, and make things that ought to be easy hard". So yeah, you could argue (as Duncan does, in fact) that Fortran is a great domain language for very fast numeric algorithms that don't need dynamic memory, and that we should only use it as an embedded DSL in some general-purpose language. But that's not how it actually gets used, most of the time. My comments about regexps are a bit dodgy, in that the only proof I know that Perl regexps have been extended is that you can embed arbitrary Perl code into a regexp :-) Do lookahead/lookbehind assertions fit the framework? The case I really wanted to talk about is Prolog, where you spend half your time second-guessing the optimizer and the other half the time writing Yet Another meta-interpreter (from my admittedly limited experience). Or think about SQL - surely you've had that experience where, no matter how far round you twist your brain, you can't write the query you're thinking of, but you can describe it in a simple sentence, and could write it straightforwardly in a more conventional language?

I certainly think that there's a huge number of problems which can be more elegantly solved in haskell (using the wonderful guarantees it gives us) than in any other common current language...
Quite possibly - I'm still trying to decide that :-) It seems that in many cases (Laziness? Referential transparency?) "guarantees over expressivity" gives the right (or at least a good) choice - the leverage you get outweighs the restrictions. But I'm really just trying to isolate the general design principle. Because I'm not convinced that it's such a great idea as a general principle, if your goal is to design a usable language. In the limit case, of course, it leads you to prefer the guarantee of program termination to the expressiveness of Turing-equivalence :-)

[totherme.livejournal.com]

SQL:

Peronally, the problems I think I've had most with SQL don't stem from its lack of expressivity as from its poor integration with the rest of the programming system... Getting no compile time checking over SQL which was all in strings in a java programme really sucked. Also, dumping java data into BLOBs, which are totally inaccessible to SQL queries was annoying....

The usual complaint about SQL is that you can't search for a substring, or a regex within a value. This is annoying, it's true - I don't understand what the reason for those original restrictions were and it's probably the case by now that a database could provide this functionality and still provide the guarantees that make the database worth using - but let's pretend for a moment that they couldn't. In that case, you have to pull everything out of the DB, and do the substring check in your general purpose langauge. Would you be better off without the database? If so, why are you using a database in the first place? It seems likely to me that you're actually gaining a lot from having the DB there, probably as a result of some guarantees it can give you (about concurrency, or guarantees allowing performance optimisations or whatever) - otherwise you wouldn't be using it. If that's the case, then you're not complaining that SQL restricts what you can do (relative to your general purpose language), you're complaining that it doesn't extend what you can do far enough. If the language can be made more expressive without sacrificing those guarantees, then that's great. But if allowing a substring match meant that concurrency didn't work any more, and the database was as slow and memory hungry as your general purpose language - what would be the point?

In the limit case, of course, it leads you to prefer the guarantee of program termination to the expressiveness of Turing-equivalence :-)

If the scale we're thinking of is the one that stretches from 0 guarantees to infinite guarantees (presumably some kind of constant statement, or something?), then I don't think limit case analysis is particularly useful. If guarantees were all I cared about, I'd bury the computer in my back garden - possibly after burning all the bits that would burn. Then I'd be absolutely sure that no bad things were going to happen. If I wanted no guarantees at all, I'd programme with "cat /dev/random > a.out"

The interesting thing about language design is finding sweet spots, where you have the guarantees you want, and the expressiveness you want (and it's not necessarily always a simple trade off between the two).

[pozorvlak.livejournal.com]

"Poor integration with the rest of the programming language" is definitely a problem with SQL. I've told you about the pain we had with schema mismatches between the (constantly-changing) database and the (permanently a few days behind) C++ layer when I was working on [classified]? I did suggest autogenerating the whole object-relational mapping layer, in the way that Ruby on Rails or Maypole do, but this was felt to be too much work :-(

I've been having a look, and can't find the specific problem that I'm thinking of - it was some feature that Mat wanted to add to Moblog (I think it was "Comments posted on (posts that you've commented on) since you last logged in") that we found we simply couldn't do in SQL. He had to set up a cron job to create an intermediate table. Possibly this was just a problem with MySQL (which at the time didn't support nested subqueries), but it was pretty lame.

[sethg]

Consider for a moment HTML. As a programming language, it's, well, not. But because the bulk of the Web is "written in" HTML (in the sense that HTML is what's exposed to the browser or other client), browsers can do start rendering a page before they've even read all of it, spiders can get useful information off the Web without having to embed a Turing-complete language interpreter, and pages written by newbies might look ugly but they communicate more or less what their authors intended and are very unlikely to crash your browser.

IIRC one of Richard Gabriel's complaints about Common Lisp is that because the standard allowed programmers so much flexibility, it was very difficult to write an optimizing Lisp implementation--which meant that novice-to-intermediate Lisp programmer would get lousy performance until they learned the optimization tricks of their particular implementation.

So I think that in general, constraints on the language end permit optimizations on the implementation end, and when a language user is doing things that don't continually bump into those constraints, that leads to happiness on the user end.

The proper way to accommodate users that do run into those constraints, IMHO, is to provide escape hatches to other languages: SCRIPT tags, the Haskell foreign function interface, PostgreSQL "createlang", etc.

[pozorvlak.livejournal.com]

Interesting, particularly about Common Lisp (does Scheme have this problem?). I wasn't for a moment trying to claim that "guarantees over expressivity" is never a good idea, I'm more trying to isolate the general principle so we can think about it - saying that it's always a good idea is probably just as stupid as saying it's never a good idea. As totherme says above, it's about finding the sweet spots.

And welcome! How did you find me?

[elvum.livejournal.com]

Is there an underlying assumption here, that there exists a holy-grail language, which can precisely and elegantly describe everything in the universe?

The lack of such a language is (as I believe you know), a source of continuing annoyance to me. Although you could argue that it could only exist in a universe where humans were capable of describing things precisely and elegantly in the first place. I expect it's all quantum.

[pozorvlak.livejournal.com]

Have you read Paul Graham's essay The Hundred-Year Language (http://paulgraham.com/hundred.html)? His basic contentions are that

1. While we can't program in the language they'll use in 100 years, we can try to predict its features, and this provides a useful heuristic for choosing languages to use or designing new languages
2. More powerful computers will demand languages that can provide a greater range of efficiencies: highly optimized for crypto/image rendering/etc, highly expressive but possibly highly inefficient for most stuff
3. "The desire for speed is so deeply engrained in us, with our puny computers, that it will take a conscious effort to overcome it. In language design, we should be consciously seeking out situations where we can trade efficiency for even the smallest increase in convenience."

... and a bunch of other stuff, most of it interesting.

Basically, he thinks that in a hundred years time, most people will be using a descendent of Lisp :-) But it's an interesting idea: if you're trying to design languages now, you should aim for the holy-grail language: even if you don't succeed, you're likely to get something better than if you'd just tried to write a slightly better Fortran (http://sig9.com/node/199).