Wednesday, July 30, 2003

Eric Tiedemann convinced me to take a closer look at Haskell Monads, a way to inject imperative programming features into a purely functional language. I've always been skeptical about monads. They seem like sleight-of-hand. A pure functional language has no imperative features. Monads give you imperative features. So how do you preserve pure functionality with imperative features?

It's a trick. The imperative features are delayed until you reach the top level, which is allowed to perform imperative features. To guarantee that none of the imperative actions are performed before then, the type system is constructed in a way that you can produce an action, you can compose actions, but you cannot execute an action.

The trouble with this is that any imperative feature taints interfaces. If someone way down in the call chain needs to write some data somewhere, then that function needs to change its type to mark it as imperative. Then everything that calls that function needs to change -- they need to be rewritten to handle that imperative action and they also need to propagate it upwards. And on and on upwards to lots of functions. That's really awful -- you can't encapsulate imperative features.

To address this problem, Haskell had to add a way to execute an action without propagating it upwards. Its use is discouraged, but it's there.

My sense is that monads have to be there not because it's a purely functional language but because it's a lazy-evaluation language. With lazy evaluation, constructing the value a = [1.5/0.0, print 5] doesn't evaluate any of the elements of the list. Instead, we don't divide by zero until you need to access a[0] and we don't print a value until you need to access a[1]. It's really hard to reason about programs when you don't know when things are going to happen. So Haskell needs a way to channel the imperative features and exceptions into some mechanism that behaves like a conventional ("strict evaluation") language.

But if instead we had a strict pure functional language, the order of evaluation could be specified precisely. Thus, you don't need to have a top-level imperative strict evaluation language on top of your purely functional language. It may still be of some use to separate the imperative and functional parts of the language, but it's less of a win.

Something to ponder: since imperative functions taint all their callers, you might end up with lots and lots of imperative functions. Instead of annotating lots functions as imperative, how about annotating some functions as being purely functional ("pure")? Unlike Haskell monads, in which you have to explicitly convert between the two types of functions, we can use subtyping to express the relationship. A pure function type is a subtype of its corresponding imperative function type. This gives us the proper constraints:

  1. Context requires an imperative function. We have an imperative function. Fine.
  2. Context requires an imperative function. We have a pure function. Fine.
  3. Context requires a pure function. We have a pure function. Fine.
  4. Context requires a pure function. We have an imperative function. Type error.

(The golden rule of subtyping: the type of the value you have needs to be a subtype of the type required by the context.)

I certainly find functional programming appealing. But the programs I write tend to be imperative. It's not that I'm writing in the wrong style -- it's that I really want to perform imperative actions, like writing to a database. So I need a language that addresses the needs I have when programming, not a language that is really elegant.

Scheme is a language that lets me do what I want to do. If I have a need for an imperative program, it lets me express that directly. If I have a need for a functional program, it lets me express that too. Related reading: Oleg's site (incredibly cool site, btw) explains how to implement monads in Scheme.

Saturday, July 19, 2003

I tried to cancel my Discover Card. It took 15 minutes of the guy trying to convince me that there's no harm in keeping it, "just in case", that I should use it for everything, that their cash back thing is worth it, that it's accepted virtually everywhere, that it'd ruin my credit history if I cancelled this card, etc. Sheesh. Based on this experience, I'm not going to ever get a Discover Card again.


Friday, July 04, 2003

For the Americans out there celebrating July 4, here's a reminder of why we are celebrating.

Friday, July 04, 2003

I've found that I post to my internal blog at work, but I don't post as much to my externally visible blog. Why is that? I suspect that internally, I know my audience―my coworkers―and we have a lot to talk about. But externally, I don't know the people reading my blog, and I don't know what we might have in common. So it's hard to think of things to say. I happen to be this way in offline life too. I say a lot to people I know but I find it hard to talk to people I don't know.