Thursday, June 16, 2005

Real world PL design

Let's say I have an imperative language, and I can do all kinds of icky things with it: send messages to a server in Norway, create and mutate reference cells, abort and resume captured continuations. But I find there are large subsets of my program that are pure--no mutation, no I/O, no side effects in general, just functions. I'd love to be able to use laziness for these portions of the program. For one thing, it adds a kind of whole-program optimization, avoiding unnecessary computation and fusing traversals of compound data structures. This alleviates me of a whole bunch of manual optimization. Furthermore, it also allows me to operate on infinite data structures like streams.

Now, since the lazy evaluation strategy doesn't have a clear, sequential operational model, I don't want to use any of the side effects in the lazy portions of the program. I'd like the type system to help me make sure that any effects in the language are restricted to the imperative world, and the lazy world is only allowed to use the pure subset of the language. So we add a simple effect system to the language: an imperative expression of type α is given type Effect α. Then all the imperative language features and standard libraries have this type, and the lazy portions of the program, which cannot have type Effect α for any α, can't touch them.

This is preamble, I suppose, to three points.

1. Monads should be introduced as a customizable effect system. My story above is how I think we should introduce monads. If nothing else, as Simon PJ knows, you're bound to scare people if you use terminology from category theory. For crying out loud, it's okay to have a good theoretical model, but you don't have to confuse the language with the theory! Even when you want people to be able to introduce their own effects into the language, you don't have to call them monads. Just call them effects! This also solves the "what exactly is a monad? Can I hold one in my hand? Is it a value? Is it a type?" problem: I bet people are already comfortable with the idea of an effect as an intangible thing, even though it is something you can "add" to a language by extending the core semantics.

2. The imperative part of a language is important. I think it's the wrong way around to treat the pure functional part of the program as the main part. The imperative part is just as fundamental. It's not the gutter where you sweep all the ugly bits. (The addition of forkIO must really be cognitive dissonance for the monks of pure FP...) Especially when you start having things like concurrency, you really want to put as much care and design into the impure part of the language as the pure part. I'd rather think about embedding pure, lazy languages into general-purpose languages than the other way around.

3. Combining effects is both hard and necessary. Monads are a great abstraction for designing effects. Type classes work fine for modelling individual effects on top of a pure core language, if you really only want to dabble with small doses of individual effects here and there. But monads are notoriously hard to combine, as are language features in general. Making the programmer invent a general purpose PL every time they want these effects is a waste of effort. Notice that the IO monad contains mutable state, concurrency, exceptions and non-termination in addition to actual I/O. That's because, as I said, the imperative fragment of a language is important, and all these effects have proven to be useful and important features of impure languages.

Now, if you rid Haskell entirely of monads and put all the effects into the top-level language, you wouldn't be able to experiment with new language features and effects. And I like the idea of a customizable effect system. So I guess I don't dislike Haskell's monads, but I think they're overblown. What I'm saying is, there's real-world PL design hiding in the IO monad. No pun intended.

2 comments:

Jacques Carette said...

I agree with you wholeheartedly on this. I have been arguing the same position (from my convenient pulpit of teaching a PL course).

Your point of separating the theory and the name given to the concept when it is implemented in a PL needs to be shouted much louder. Terminology (and notation) are important! Picking a name which is suggestive of an analogy with something already known (like effect instead of monad) is one of the most important choices to be made when designing a language. Of course, reasoning by analogy can lead one astray, but since there is a background theory to rely on, that is not such a big deal.

Question: What should a Monad Transformer be called? While Effect Combinator would be correct, it is still not right. A Monad Transformer does indeed combine effects, but I have yet to come up with a suggestive name for it!

Dave Herman said...

Thanks!

Terminology (and notation) are important!

Yep, names should matter to people, and names shouldn't matter to computers (cf. α-equivalence).

What should a Monad Transformer be called?

Effect Transformer?
Effect Builder?
Effect System Transformer?
Effect System Combinator?
Effect System Builder?

I'm not sure. Is your objection to "Effect Combinator" that it sounds like it combines an individual instance of an effect rather than the family of all such effects, or is it that it's not a true combinator since you don't in general get out a monad on the other end?