Wednesday, November 5, 2008

Haskell for C# Programmers Part 2: Understanding IO

One of the most difficult things for C# developers to understand about Haskell is the way in which it performs stateful tasks such as IO. In part 1 I explained the difference between methods and pure functions. Pure functions always return the same value if passed the same arguments and don't change the state of the system. C# methods that change state (ex. change a global variable, return a pseudo-random number, write to disk) are considered "impure." In C# we can create both pure functions and methods. In Haskell it is only possible to create pure functions. This might seem strange. After all without impure operations you can't even generate a random number. That would make for a pretty dull poker game eh?

"Who cares about purity?"

Impure programs are a lot like machines with moving parts. Every time you look at them they are in a different state. In contrast pure programs are like machines with no moving parts. They are, on close inspection, just formulas executed by the computer. Want to take a guess which machine is more reliable?

In addition to the benefits of clarity and increased reliability it turns out that compilers can also make certain types of optimizations if they can be sure that code is pure. That's one of the reasons Haskell can be very fast despite the fact that it is such a high-level language.

"That's all well and good but I need to change state!"

Indeed you do. We don't want to get rid of state (we can't) but we DO want to separate the pure operations from the impure ones. Haskell allows you to perform impure actions, but it forces you to bundle them up together and execute them at the end of your program. Conceptually a Haskell program is a pure function that creates an impure program and runs it.

"Weird."

Not at all. It's very similar to what C# developers are now used to doing with Linq all the time. Take the following program:

var evenNumbers = from x in Enumerable.Range(0,100) where x % 2 == 0 select x*x;

What is the value of evenNumbers? It isn't a bunch of computed numbers stored in memory. It's a sequence which, when traversed, will generate those numbers. The Range function returns a sequence. This sequence is wrapped inside of another sequence by the Where function. Finally that sequence is wrapped inside of another sequence by the Select function. Only when we traverse the Sequence do the functions in the Select and Where sequences actually execute.

foreach (var num in evenNumbers) { System.Console.WriteLine("{0}", num); }

Linq allows us to combine a bunch of sequence operations together and then run them later. Imagine if we could use Linq to combine a bunch of stateful operations (ex. IO, random number generation) together then run them later. Surprisingly we can.

"I thought this post was about Haskell."

It is. Bear with me. Let's write some C# code that reads a url from the console, downloads the HTML, and then writes it to the console. However instead of doing things the typical C# way we'll do things the Haskell way. Let's start by defining a type called IO.

public delegate T IO<T>();

Our IO type is similar to IEnumerable. When it's run it will perform an operation and return the resulting value.  An IEnumerable is run with GetEnumerator and an IO is run by, well, running it.  The principle difference between the two are that a traversing a sequence doesn't necessarily have side-effects while running an IO function does.  Also an IO returns only one value while sequences return many.

Let's define a function that reads a string from the console. Since this function changes state it will return IO<string> instead of string. By returning a function that does the work instead of just doing it right away we can delay this operation and group it with others.

// Returns a function which, when executed // will get an address from the console // and return it. static IO<string> GetAddressFromConsole() { return () => Console.ReadLine(); }

Pretty straightforward right? Notice how easy this is thanks to C#'s lambda expressions and type inference. Now we'll write a method that retrieves the HTML for a given address.

static IO<string> GetHtml(string url) { return () => { string html = null; using (WebClient client = new WebClient()) { html = client.DownloadString(url); } return html; }; }

Once gain retrieving information from the internet involves IO so we again wrap the work in an IO function in order to delay its execution. The last basic function we need to create is one that writes a string to the console:

static IO<object> WriteToConsole(string value) { return () => { System.Console.WriteLine(value); // We have to return a value so we just return null return null; }; }

Notice that all of these functions are pure! They don't do work, they create functions that do work when they are called. That's how Haskell keeps its hands clean. Now that we've built our basic functions we're ready to write our program.

static IO<object> RealMain(string[] args) { return from address in GetAddressFromConsole() from html in GetHtml(address) from _ in WriteToConsole(html) select _; }

This function will retrieve a URI from the console, retrieve the HTML for that URI, write it to the console, and return null because the last operation, writing to the console, has no return value. Notice that our Main function is an IO function as well! This Linq usage may appear strange to you.  I had to write some code so that Linq knew how to compose our IO objects together but I'll explain that later.

"OK now what?  When do we actually do something?"

Now that we've composed all of these functions together into one IO function it's just a matter of running it. 

// This function is generated by Haskell automatically static int Main(string[] args) { var IO = RealMain(args); try { IO(); // IO operations are lazily executed in sequence return 0; } catch (Exception) { return -1; } }

"Hold on.  I thought you said that Haskell couldn't perform impure operations."

I lied. It does exactly ONE impure operation.  Once all your impure operations are bundled together into one IO function that function is run.  The only difference is that Haskell automatically generates the code above.  It is implicit. Now without further ado let's look at the Haskell equivalent of the code above.  Hopefully it will be much easier to understand now.

let GetHtml :: string -> IO string GetHtml = --This definition is not relevant now let GetAddressFromConsole = getLine --this is a built-in function that reads from the console let WriteToConsole = putStr --this is a built-in Haskell function that writes to the console main :: IO () main = do address <- GetAddressFromConsole () html <- GetHtml(address) WriteToConsole html

Monads

Now that you understand that Haskell handles IO the same way C# handles sequence operations you may have started to wonder what other types of operations can be composed in this manner. Both IO object and IEnumerable are examples of Monads and there's nothing scary about them other than the name.  Monads are the important idiom to understand if you want to write Haskell programs. Next time I'll explain how they work and how I managed to use Linq to sequence our IO monad.

12 comments:

Anonymous said...

Excellent explanation, thanks!

Anonymous said...

I'm beginning to see the light! thanks for the explanation.

(a little typo: in the Haskell program GetHtml takes address as parameter)

Judah Gabriel Himango said...

I think I'm beginning to understand. Thanks Jafar!

Jafar Husain said...

danice: Fixed. Thanks.

André Cardoso said...

I think I was understanding the idea with returning functions, to remain pure, but how does that cope with debugging?
Is it necessary to debug expressions (losing the stack trace, or at least the function definition) in one huge expression?

thejoshwolfe said...

Great explanation of Haskell IO! This clears up a lot of confusion for me.

Anonymous said...

Hi Jafar,

This is really a wonderful explanation!

But, can you make it clear how to define a SelectMany extension method for IO<T>?
The statements from *** from*** select *** needs a SelectMany for IO<T>.

Thanks

Affordable Luxurious Wedding Dress Blog said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.

About Me

My photo
I'm a software developer who started programming at age 16 and never saw any reason to stop. I'm working on the Presentation Platform Controls team at Microsoft. My primary interests are functional programming, and Rich Internet Applications.