Wednesday, February 28, 2007

Monads in C, pt. II

This is a quick followup to a post on reddit. This time a crude approximation to the Maybe monad implemented in C:


include <stdio.h>

typedef struct {
int something;
int just;
} MaybeInt;

MaybeInt returnMaybe(int i)
{
MaybeInt r;
r.something = 1;
r.just = i;
return r;
}

MaybeInt nothing()
{
MaybeInt r;
r.something = 0;
return r;
}

MaybeInt bind(MaybeInt (*f)(int),MaybeInt x)
{
if (x.something)
{
return f(x.just);
} else
{
return nothing();
}
}

MaybeInt print(int i)
{
int written = printf("%d\n",i);
if (written>=0)
{
return returnMaybe(written);
} else
{
return nothing();
}
}

MaybeInt printplus_bad(int i)
{
MaybeInt x = print(i);
return print(x.just); /* cheating! */
}

MaybeInt printplus(int i)
{
MaybeInt x = print(i);
return bind(print,x);
}


Again the idea is that printplus() is a version of printplus_bad() that uses just the two function bind/return interface to the MaybeInt type to achieve its effect. This time, instead of simply tainting IO with a particular type, the Maybe monad is able to deal gracefully with failure. If, for some obscure reason, printf() fails, returning an integer less than zero, it returns an object representing this fact. If, as in printplus(), you have two calls to print() in a row, bind() handles all the plumbing for you automatically. The really important thing is this: the implementation of printplus() is identical to my previous example, and yet the semantics is quite different because printplus() is able to bail out early. This bailing out is completely hidden inside bind().

I hope that this gives some hint of what monads can do to even hardcore non-functional programmers. If not, I'll probably write another example soon.

(Remember of course that this isn't meant to be practical code. It was a response to someone who wanted to at least some some C code for monads to get an idea of what they're about.)

6 comments:

Anonymous said...

Well, all these C functions are eager. Isn't it the main point that Haskell functions are lazy? Or it doesn't really matter?

sigfpe said...

Monads work in eager or lazy languages, it makes little difference. In a sense monads are just mathematical constructions defined by some equations, so what matters is what things evaluate to, not the order they're evaluated in.

Having said that...in Haskell there is a nice way to use monads to make it convenient to write strict code even though the language is lazy.

Michael said...

Thanks for the nice post!

Pete said...

This code is dangerous and will likely crash since you are returning pointers to memory allocated on the stack!

Pete said...

D'oh, ignore that last comment, I mistakenly thought it was returning a pointer to the structure not a copy. :-/

Anonymous said...

Nice, this code is good to show that monads can be implemented in C.
If anyone wants to refine it, one way is to embed it in a macro, in order to use any other type.
More laborious option is to implement manifest types.
Want it lazy? Implement lambda calculus including an eta-conversion, fixed point combinators, ...
Good idea for course semester project.
See the wizard book for manifest types and Essentials of Programming Languages Friedman et al, not the last edition, the black cover, to implement lambda-calculus

Blog Archive