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

[stronae.livejournal.com]

Well, let me introduce myself. I'm stronae, and I'm a Scheme programmer. :) I came to Haskell via its functional core and its type system, so that's how I relate to it. You don't need to convince me about Haskell's virtues; I already believe, but my problem is that doing easy things is harder in Haskell. For example:

I agree that the things you provide above are no worse than each other, but consider: both are way worse than

(random 6)

which requires no knowledge whatsoever.

Maybe most people who learn Haskell get subject to Monads vs. Functionality early, so whipping out a side-effect is effortless to them. When I first learned about Monads, they were quirky, and alien, and despite looking high and low on the web, there really wasn't anything out there to get me functional enough (if you'll pardon the pun) to do everyday things. Nevermind that most of the tutorials have you attempt to learn about the Monad At Large, and only after you've digested that, you could then proceed to the IO monad, which is what I was (apparently) interested in in the first place. Suffice it to say, it's a painful way to go. (If you happen to know of a sane and rational tutorial, feel free to mention it. :))

I would agree with the thread below, where you state that it's easier to just not understand them so much and just use them. But to 'just use' requires a certain knowledge of the syntax, when x <- (f 5) is required versus x = (f 5), that an if/then command is available but you have to provide your semicolon, and so on. Not a big deal in the long run, but to a novice user, it's nontrivial.

[totherme.livejournal.com]

Hey :) I'm totherme, good to meet you :)

I guess I learned haskell the Bird way - which isn't the way I think many hackers learn to code. We started with calculating interesting things, rather than with doing interesting things. It was quite a while before we bothered with monads at all, because there was plenty of other interesting stuff to do. This isn't a very "practical" way of doing things, of course - since pretty well all practical programmes require IO. Having said that, I think it's a good way of learning how functions work.

You're certainly right when you say that most haskell docs about monads try to teach you about monads in general. I think you're probably right when you suggest that this is suboptimal for a large percentage of people. I also think it's understandable - monads are a really cool abstraction, and most of the community are bursting with a joyous desire to share them with the world :)

(I've heard people suggest that they could be as ubiquitous as Objects in OO lanugages - a cool way of chopping stuff up, to be used everywhere - not just a weird hack to let you do IO)

From this point of view, I really like sigfpe's tutorial: You Could Have Invented Monads.

Having said that, it's probably as freaky to learn about monads this way as it is to learn about Objects for the first time... You remember learning/teaching that concept? Trying to understand/get across the difference between a class and an object, the meaning of instantiation, of inheritance, static things that live in all objects of a class at once, the "is a" relationship that inheritance should model... It's complex stuff - and a lot of people just want to write short, simple things. These are folk that don't need monads any more than they need a full object system. This is why languages like python and ruby allow you to write simple scripts, despite being OO languages.

From that point of view, the tutorial I like is dons' Programming Haskell series. He pretty well just tells you how to do things - in real contrast to the way I was taught. It looks like good stuff to me - but I'm not the target audience any more, and I haven't tried that tute out on any novices yet.

Now - those two links are both for someone who's doing their own thing, and needs to learn IO or monads in haskell - they're not full tutorials for teaching haskell. I'd feel wrong if I didn't at least mention YAHT. Where the above links are fairly to the point, YAHT is comprehensive. If someone asks me "What should I read to learn haskell?" - that's what I point them at. It's probably not relevant to this thread, but I like linking to it :)

As for the issue of haskell's syntax being different from most imperative languages - yeah, it is. This certainly does make it tougher to switch from imperative programming to haskell programming. I think the syntax is quite reasonable, and find that people who've never coded before don't have any problem with it. I've also heard some maths types (usually who've done little or no other coding) comment how easy it is to translate maths syntax into haskell syntax... So I guess those are the target audiences for the syntax: new coders and old mathematicians ;) For existing coders, I guess the best option is to point at the tour of the syntax, and hope it's user friendly enough :S

[pozorvlak.livejournal.com]

Have you seen Monads as Containers (http://www.haskell.org/haskellwiki/Monads_as_Containers)? Or is that the kind of thing you're complaining about - starting with monads in general and then specialising to IO? IO isn't the easiest one to start with if you want to understand the concept in general, I think.

Do you know about the use of monads in algebra, and in particular things like the "free group" monad? For me, a lot of enlightenment came from comparing the Haskell definition with the categorical one, and the rest came from thinking about algebraic examples.

Monad transformers, on the other hand, I still don't really get. Just Doing It will help, for sure, but it would really help if I knew what they were meant to be mathematically. Distributive laws?

[stronae.livejournal.com]

Have you seen Monads as Containers? Or is that the kind of thing you're complaining about - starting with monads in general and then specialising to IO? IO isn't the easiest one to start with if you want to understand the concept in general, I think.

Haven't seen it yet, no. But you guessed it: I tend to believe that I shouldn't have to learn a whole body of theory (up front) just to print something to screen. :) I'm happy to learn the theory later, when I'm more conversant with the syntax and aware of what I should be looking for, but don't make me pull out my hair for "hello world" on Day One.

I guess, in the end, every tutorial out there is perfect for exactly one person: the person who wrote it. Each will be "good enough" for more people, but it's hard to find the right tutorial for the things you're missing, and what's good for one person (or class) might not work well with another person.

Do you know about the use of monads in algebra, and in particular things like the "free group" monad? For me, a lot of enlightenment came from comparing the Haskell definition with the categorical one, and the rest came from thinking about algebraic examples.

I'm in a Homological Algebra course now, so we'll eventually get to categories. If we touch upon what you mention, I'm sure I'll be doing the comparisons implicitly. :)