Friday, May 09, 2008

Haskell - Academia goes Bowling

True to my promise, I've spent a little time looking into Haskell. I've read some intros on the web, and I have even gone as far as to download HUGS an interactive interpreter, and I have started to work through a tutorial. I'm still on the first chapter so it's still early days.

First impressions are that I like it. Haskell as you would expect is very mathematical, with terms like "currying", "list comprehensions" and "guards" to learn, so I had half made my mind up not to like it. Then I started to use HUGS and actually started writing some Haskell code. The code itself is quite readable, helped by prefix notation and type inferencing I think.

Keen to get to the point (and not wanting to have to learn a bunch of mathematical theories to do so), I sought out a real world example of a Haskell program. Thankfully I didn't have to look far. Ron Jefferies has produced a number of very good articles where he walks through his experiences coding up a Bowling Game program using TDD and a number of different languages. The Haskell example (produced by an academic), drew a lot of interest, especially since Ron spoke disparagingly about it.

The program uses pattern matching and recursion, avoiding loops. Ron's point was that the recursive implementation although succinct, said nothing about the "tenness" of a game of bowling. For those who don't know a game of Bowling always consists of ten frames. This "tenness" of the problem wasn't expressed anywhere in the solution. A number of academics jumped in defending recursion and offering recursive solutions of their own. Until one guy found out that there was actually a bug in most of the implementations presented.

I'll leave the reader to follow the debate, but what all these academics had missed, and Ron with his practical instincts had sensed is that the programmer is always the weak link. Any solution that doesn't fit with the way the programmer thinks about the problem will prove difficult for the programmer to verify in his own mind. Hence the missed bug, despite, many "clever eyes" over the code. Ron's summary is that Haskell forces you to think the way it thinks (mathematically) rather than allowing you to express things the way you think.

Gilad makes the same point about pure functional languages. In contrast, pure object orientated languages allow you to model the world the way it is. Haskell encourages you to create a stateless functional model, which by itself is useless for real world problems, but supposedly great for verification tools. Where your pure functional solution meets the real world, for things like user I/O, you must fall back to impure actions. Impure imperative behaviour can be isolated from the rest of your code using Monads. I don't yet fully understand Monads, but they appear to be a way of representing an underlying type (e.g an Integer) by wrapping it in a new type (called a Monad) that provides additional values that transmit information about side effects. So for example "Nothing" (NaN) is a valid value for a Maybe Monad, which can be used as a wrapper type for Integers. So functions that return Monads are able to communicate side effects to other calling functions (meaning that the side effect is no longer a "side effect" but a legitimate return value) . I will blog more about Monads once I fully understand them.

So where are all these great verification tools? With the exception of a type system there doesn't seem to be any built into the language itself. So you end up with a program that is hard for the programmer to check himself, and which can't be fully checked by the compiler. So what's the point?

As an academic exercise, Haskell is interesting and I guess it will float the boat of the mathematically inclined, as a practical tool though, it wouldn't be at the top of my list. I'm still going to play with it some more though, and I'll let you know if I change my mind.

Updated 11th May 2008
Corrected my description of Monads after feedback from the Haskell community. I found Daniels comment on Monads particularly useful. It prompted me to read further and improve my own understanding. I don't pretend that my description of Monads is complete, and I would refer a reader interested in a complete explanation to look here.

12 comments:

Neil Mitchell said...

The process of writing verification tools is hard, but the work in underway. I have done some myself, at http://www-users.cs.york.ac.uk/~ndm/catch/. There are others, such as the Sound Haskell and ESC/Haskell work. Haskell is just beginning to hit the main steam, proper proving about Haskell is a few steps behind. You can also have QuickCheck/SmallCheck/Lazy SmallCheck/Reach for automated testing of properties, which usually is good enough.

dibblego said...

Since you are a beginner, you can be forgiven for a couple of mistakes. That Haskell is a "stateless functional model" is not only not useless, but it makes other uncontrolled side-effecting systems look quite useless. Second, Monads are not impure, not even the one that allows you to interact with I/O.

Keep it up ;)

PWBDecker said...

I just learned Haskell last term for a functional programming class. I was already familiar with (what I thought was) functional programming via Common Lisp. I have to agree that Haskell's pure functional system is a little abstract for the tedium of typical coding, but I think one of the most interesting features of Haskell is the fact that because it's a purely functional language you can set a compiler flag and make your code SMP compatible. In a few years systems will have a few dozen cores (Intel's new chip has 80 I believe) and by that point you'll have one guy maintaining a system in C++/MPI and another guy maintaining some elegant system in a Haskell-style derivative. Then we'll see who's on top.

Don Stewart said...

If you're going to look at Haskell seriously, install GHC, the state of the art compiler, with its SMP runtime, and performant native code generator, and rich set of libraries available from hackage.haskell.org

Then perhaps drop by http://haskell.org/haskellwiki/Haskell_in_industry the industry page, to get a flavour for what people are using Haskell for in the real world.

Jonathan said...

Haskell is not a 'mathematical' language, it is a functional language. Currying, list comprehensions and guards are not mathematical concepts, they are computer science concepts.

Haskell is also a normal programming language, used by normal people in industry. I am fed up with the idea that it is some kind of academic language for academics to wank over. It's not my 'favourite language', but I feel inclined to defend it from some of the misconceptions.

Haskell does not force you to think the way it thinks, and you can model states without using monads. And monads are not 'impure', or some sort of fix for anything lacking. Monads are purely functional.

You may also wish to know that loops and recursion are the same thing. They're not related to each other and they're not similar. They are exactly the same. When I write a loop in java (and yes, I like java, despite how un hip it is at the moment) and when I write a recursive function in haskell, I'm doing the exact same thing.

And who actually cares how objectively good a language is? I'll write a good program in any programming language you throw at me. Just don't start having a go at a language you don't really understand properly.

Paul said...

Hi All,

Thanks for the responses. 5 responses in a couple of hours, that's a record a sign that Haskell has a vibrant community which has got to be a plus for any language. For those who sent links, Thanx. I am a mewbie and I still have a lot to learn.

Has for the usefulness of a pure functional model, I was merely quoting from the tutorial I'm following:


"For instance, a function that prints something to the screen is said to be side-effecting, as is a function which affects the value of a global variable.) -- of course, a programming language without side effects would be horribly useless; Haskell uses a system of monads to isolate all impure computations from the rest of the program and perform them in the safe way"

http://en.wikibooks.org/wiki/Haskell/YAHT/Preamble

If the above statement is wrong, then please say why?


I am keeping an open(ish) mind. I do think that the bowling example is informative though. I agree that Haskell is great for tools and machines (verification, concurrent computation etc). I'm questioning how suitable it is for people.

All input and opinions welcomed.

Thanks again,

Paul.

dbpatt said...

I'm new to haskell too, so I'll step aside if someone who understands this better wants to give it a shot, but -

the IO monad isolates impure actions from the rest of the program - this is true. that is sort of what monads can be thought to do - box in something or another - in this case, it boxes in 'the world' (or, the state of the world).

this means that not only is the rest of your program pure, but so is the IO Monad, because it handles input/output like a functional program should (each IO action can be thought to create a new state of the world, thus given a given state of the world, and an action, the resulting state of the world is always the same). that's really all it means to be pure - that given the same inputs, you always get the same outputs.

with regards to not having verification frameworks - I think if you work with it a little, you would be shocked how well being purely functional and strongly typed does to make sure things work as they should. It is possible to create runtime bugs, but difficult.

cheers, and stick with it!

Paul said...

Hi dbpatt,

I've updated my post to provide a better description of the role of Monads.

"boxing in the world" and isolating it from the rest of your program seems unfortunate to me. Coming from a pure OO background, I like the idea of modeling the world, and bringing the world into my program, rather than trying to keep it out.

I guess it depends on the nature of the problem. My experience over the years is that computers are being asked to address higher level, people centric problems. Examples like "manage my customers" or "improve communication and information flow amongst my departments" come to mind.

These types of problem aren't mathematical, and definitely aren't deterministic. They are complex, with the biggest difficulty being modeling the problem in a way that is stable to change in the real world. Hence the OO idea of modeling real world abstractions and many things in our world are stateful.

As I understand it, pure functional languages excel in problem spaces that map well to pure functions or can be made to map to pure functions. When the problem isn't a natural fit what happens?

I guess the only way to find out is to try it for myself. So I intend to stick at it. Thanks for the encouragement.

dbpatt said...

(my name is daniel by the way, thought google would expand that, but no. also, I show up under the handle dbpatterson here and there).

I think I may have mis-explained, or you may have misconstrued my comments about 'the world'...

you are totally free to model the world in haskell - obviously it will be a little different than in an OO context, but it is still very much a real situation. haskell may be well suited to theoretical applications (and is used in lots of math heavy financial stuff), but, for example, my website is written in haskell, and I am in the progress of writing a haskell wrapper around a JSON api - both very real world and non-theoretical applications, which I think haskell works well for.

really, anyone who is writing complicated software needs to keep track of places where things can be inconsistent - if it is consistent, it would have been caught the first time, and would never become a bug. in a purely functional context, where functions can not modify or depend on external variables (something that good programmers tend towards anyway), the only place where things can be inconsistent is when dealing with input, when depending on things that concern the ever changing world outside the program.

so if you want to think of haskell IO in the simplest way possible, all this monad stuff serves to do is identify every place where you deal with the world. now the way it is represented in a purely functional way is that the entire state of the world is considered to exist as an entity, that is modified every time you do something using it (what I was explaining in the last post).

representing it this way doesnt stop you from using it, it just makes sure you are explicit about it. in this way it is very very helpful, because if something is inconsistent, some sort of funny bug, it HAS to be a problem with something IO related.

glad you're going to stick with it! drop by #haskell on irc.freenode.net or the haskell-cafe mailing list... always a solution (even for stupid questions) somewhere.

Greg said...

1. Haskell forces you to think a different way. Yes. And I would say that indisputably you write better programs when you think that way. It's up to you whether you want to learn to think that way.

2. In what way is an OO model of the world a better model of "how it is" than a functional model? I don't understand how you gauge that.

Paul said...

Hi Greg,

I'll take each one of your points in turn:

1. I agree that Haskell helps you write code in a more "mathematically verifiable way". Is this way better? Well I think it depends on the problem. If the problem is a natural fit then undoubtedly yes. If the way us humans tend to think about the problem is stateful, then I'm not sure. In the end the translation from the problem space to the solution space is an intellectual activity performed by humans. If the way we express our solution makes it difficult for us to reason about it's correctness, then the Haskell way may not be better. Ron Jefferies has written several imperative versions of the Bowling Game. I believe all the imperative programs were bug free.

2. OO is not Java, or C++ :) We need to go back to a language like Smalltalk to understand what I mean. Alan Kay recognised that encapsulated state allowed us to create encapsulated abstractions (his analogy was biological cells) that hid their insides and communicated with each other through messages. This metaphor allows us to directly model virtually anything in the real world. Even functions (lamda expressions) in Smalltalk are modeled as Objects with no state that understand the message "value".

Each object represents a "thing" which can optionally contain state. Pure OO languages like Smalltalk and Self, took this idea even further with the concept of liveliness, where objects are always alive (resident in memory) even during development, so you could edit your program whilst it was running (Chunks of code (Classes) are Objects too). In the same way you would change the furniture in your bedroom whilst still living in it. This idea leads to the concept of mode less software (no edit/run modes) which again is analogous to the real world. We live in a world of things, concepts and actions, where time never stops. All of which can be readily modelled with Objects.

The downside is that state and side effects make the code less (mathematically) verifiable. Hence my interest in Haskell. Gilad Bracha is working on an OO language called Newspeak that is purely functional if you choose to avoid the use of a single operator. I have blogged on Newspeak if you are interested.

Saurabi said...

this tutorial is soo cool, this is the first time that I understand this, for sure I gonna buy viagra and take another reading of this interesting theme.