I've learned. I'll share.

January 7, 2008

Monads in Python (with nice syntax!)

Update: I've been informed that I didn't clearly explain what monads are and what the code examples are supposed to do. Sorry. I guess I assumed too much preexposure to monads. If you're no familiar with them, there are already so many tutorials on monads that I'll simply direct you to two of my favorites: spacesuits and wikipedia. I've also added more explanations of what the code snippets are supposed to do. I hope that helps.

Update 2: By popular demand, I'm including some code that you can actually run :). See the bottom of the article.

Recently, I used monads in production code for a soon-to-be-publically-released application. Although many think they are strange, estoric, and perhaps useless, monads were the best way to solve the problem. My code is not in Haskell; it's in Python. I'm not doing anything wierd like IO in a purely functional way; I'm just parsing a file.

The crazy, unexpected conclusion I came to is that you can and should use monads in your code in almost any programming language. There are two parts to this: "can" and "should". I think I'll save "should" for another article. Right now, I'm excited to show you how you can.

As a preview for "should", please consider that you may be using monads already without knowing it. LINQ in C# is a monad (pdf), so if you've ever used it, you've used a monad. The C# guys used monads for queries for the same reason I'm using for them for parsing: they're the right tool for the job. But unlike them, I can't change the syntax of the programming language.

The biggest challange with using monads in a "normal" programming language is that monads involve lots of closures. This is exactly the same problem you run into with CPS, which isn't surprising since a monad's "bind" operator is CPS and since continuations can be implemented with monads. By the way, if your programming laungage doesn't have closures (meaning you are stuck programming in C, C++, or Java), then monads are probably out of the question. Assuming you have closures and use them with monads directly, you end up with code like the following. It's python using the Maybe monad to handle divide by zero errors. I'm using ">>" (__rshift__) overloaded to mean "bind".

def mdiv(a, b):
    if b == 0:
        return Nothing
    else:
        return Something(a / b)

def with_maybe():
    return \
    mdiv(2.0, 2.0)    >> (lambda val1 :
    mdiv(3.0, 0.0)    >> (lambda val2 :
    mdiv(val1, val2)  >> (lambda val3 :
    Something(val3))))                       

That's not very pretty. We need a way to clean that up. How we can do so depends on the programming language. Haskell has "do" syntax built-in, which makes monadic code look like an impertive language or even a list comprehension. Ruby and Scheme have call/cc which makes it trivial to wrap a bind call with a continuation to make any monadic code look "normal". C# has LINQ, which is practically Haskell's do notation with funny names.

But I'm using python. What does python have? Luckily for me, in python 2.5 they added bidirectional generators, and I found a way to use them to make something like "do" notation. Now we can write the above code like this (@do and mreturn are defined later):

@do(Maybe)
def with_maybe(first_divisor):
    val1 = yield mdiv(2.0, 2.0)
    val2 = yield mdiv(3.0, 0.0)
    val3 = yield mdiv(val1, val2)
    mreturn(val3)

I even copied the names "do" and "return" from Haskell, although I had to spell "return" as "mreturn". All you really have to remember is that "yield" means "bind" and that the end result is a monad. There are limitations to this technique, but it's working very well for me so far. I've implemented the Maybe monad, the Error monad, the StateChanger monad, and the Continuation monad (which will require another article to explain). I particularly like the continuation monad because it allows me to write callcc, which lets me do threadless actors (message passing) in python:

from collections import deque

class Mailbox:
    def __init__(self):
        self.messages = deque()
        self.handlers = deque()

    def send(self, message):
        if self.handlers:
            handler = self.handlers.popleft()
            handler(message)()
        else:
            self.messages.append(message)

    def receive(self):
        return callcc(self.react)

    @do(ContinuationMonad)
    def react(self, handler):
        if self.messages:
            message = self.messages.popleft()
            yield handler(message)
        else:
            self.handlers.append(handler)
           done(ContinuationMonad.zero())

@do(ContinuationMonad)
def insert(mb, values):
    for val in values:
        mb.send(val)

@do(ContinuationMonad)
def multiply(mbin, mbout, factor):
    while True:
        val = (yield mbin.receive())
        mbout.send(val * factor)

@do(ContinuationMonad)
def print_all(mb):
    while True:
        print (yield mb.receive())

original   = Mailbox()
multiplied = Mailbox()

print_all(multiplied)()
multiply(original, multiplied, 2)()
insert(original, [1, 2, 3])()

A few months ago, I wrote a similar implementation of threadless actors in python. It used generators in a similar way, but it was 10 times as much code. I was shocked at how short this implementation ended up being. You might think that it's because the continuation monad implementation is big. Nope. It's just as short (Monad defined later, and Record defined here):

class ContinuationMonad(Record("run"), Monad):
    def __call__(self, cont = lambda a : a):
        return self.run(cont)

    def bind(self, bindee):
        return ContinuationMonad(lambda cont : self.run(lambda val : bindee(val).run(cont)))

    @classmethod
    def unit(cls, val):
       return cls(lambda cont : cont(val))

    @classmethod
    def zero(cls):
        return cls(lambda cont : None)

def callcc(usecc):
 return ContinuationMonad(lambda cont : usecc(lambda val : ContinuationMonad(lambda _ : cont(val))).run(cont))

So, you can use monads with elegant syntax in any language that has closures and any of the following:
  • do syntax (Haskell, C#)
  • call/cc (Scheme, Ruby)
  • bidirectional generators (Python 2.5, a future JavaScript?)
  • coroutines (Lua, Io)

The only think I haven't shown you is the implementation of Monad, @do, mreturn, and done. It has a few nasty details related to using generators and decorators in python, but here's the gist of it:

class Monad:
    def bind(self, func):
        raise NotImplementedError

    def __rshift__(self, bindee):
        return self.bind(bindee)

    def __add__(self, bindee_without_arg):
        return self.bind(lambda _ : bindee_without_arg())


@decorator_with_args
def do(func, func_args, func_kargs, Monad):
    itr = func(*func_args, **func_kargs)

    def send(val):
        try:
            monad = itr.send(val)
            return monad.bind(send)
        except MonadReturn, ret:
            return Monad.unit(ret.value)
        except Done, done:
            return done.monad

     return send(None)

def mreturn(val):
    raise MonadReturn(val)

def done(val):
    raise Done(val)

That's it. If you've made it all the way to the end of this long article, I hope you've found inspiration for using monads in your own applications, especially if you are coding in python. If so, here's some code that you can run:

import types

###### Base Monad and @do syntax#########

class Monad:
    def bind(self, func):
        raise NotImplementedError

    def __rshift__(self, bindee):
        return self.bind(bindee)

    def __add__(self, bindee_without_arg):
        return self.bind(lambda _ : bindee_without_arg())

def make_decorator(func, *dec_args):
    def decorator(undecorated):
        def decorated(*args, **kargs):
            return func(undecorated, args, kargs, *dec_args) 
        
        decorated.__name__ = undecorated.__name__
        return decorated
    
    decorator.__name__ = func.__name__
    return decorator

def make_decorator_with_args(func):
    def decorator_with_args(*dec_args):
        return make_decorator(func, *dec_args)
    return decorator_with_args

decorator           = make_decorator
decorator_with_args = make_decorator_with_args

@decorator_with_args
def do(func, func_args, func_kargs, Monad):
    @handle_monadic_throws(Monad)
    def run_maybe_iterator():
        itr = func(*func_args, **func_kargs)

        if isinstance(itr, types.GeneratorType):
            @handle_monadic_throws(Monad)
            def send(val):
                try:
                    # here's the real magic
                    monad = itr.send(val) 
                    return monad.bind(send)
                except StopIteration:
                    return Monad.unit(None)
                
            return send(None)
        else:
            #not really a generator
            if itr is None:
                return Monad.unit(None)
            else:
                return itr

    return run_maybe_iterator()

@decorator_with_args
def handle_monadic_throws(func, func_args, func_kargs, Monad):
    try:
        return func(*func_args, **func_kargs)
    except MonadReturn, ret:
        return Monad.unit(ret.value)
    except Done, done:
        assert isinstance(done.monad, Monad)
        return done.monad

class MonadReturn(Exception):
    def __init__(self, value):
        self.value = value
        Exception.__init__(self, value)

class Done(Exception):
    def __init__(self, monad):
        self.monad = monad
        Exception.__init__(self, monad)

def mreturn(val):
    raise MonadReturn(val)

def done(val):
    raise Done(val)

def fid(val):
    return val

##### Failable Monad ######

class Failable(Monad):
    def __init__(self, value, success):
        self.value   = value
        self.success = success

    def __repr__(self):
        if self.success:
            return "Success(%r)" % (self.value,)
        else:
            return "Failure(%r)" % (self.value,)    

    def bind(self, bindee):
        if self.success:
            return bindee(self.value)
        else:
            return self

    @classmethod
    def unit(cls, val):
        return cls(val, True)

class Success(Failable):
    def __init__(self, value):
        Failable.__init__(self, value, True)

class Failure(Failable):
    def __init__(self, value):
        Failable.__init__(self, value, False)

def failable_monad_examle():
    def fdiv(a, b):
        if b == 0:
            return Failure("cannot divide by zero")
        else:
            return Success(a / b)

    @do(Failable)
    def with_failable(first_divisor):
        val1 = yield fdiv(2.0, first_divisor)
        val2 = yield fdiv(3.0, 1.0)
        val3 = yield fdiv(val1, val2)
        mreturn(val3)

    print with_failable(0.0)
    print with_failable(1.0)

###### StateChanger Monad #########

class StateChanger(Monad):
    def __init__(self, run):
        self.run = run

    def bind(self, bindee):
        run0 = self.run

        def run1(state0):
            (result, state1) = run0(state0)
            return bindee(result).run(state1)

        return StateChanger(run1)

    @classmethod
    def unit(cls, val):
        return cls(lambda state : (val, state))

def get_state(view = fid):
    return change_state(fid, view)

def change_state(changer, view = fid):
    def make_new_state(old_state):
        new_state    = changer(old_state)
        viewed_state = view(old_state)
        return (viewed_state, new_state)
    return StateChanger(make_new_state)


def state_changer_monad_example():
    @do(StateChanger)
    def dict_state_copy(key1, key2):
        val = yield dict_state_get(key1)
        yield dict_state_set(key2, val)
        mreturn(val)

    @do(StateChanger)
    def dict_state_get(key, default = None):
        dct = yield get_state()
        val = dct.get(key, default)
        mreturn(val)

    @do(StateChanger)
    def dict_state_set(key, val):
        def dict_set(dct, key, val):
            dct[key] = val
            return dct

        new_state = yield change_state(lambda dct: dict_set(dct, key, val))
        mreturn(val)

    @do(StateChanger)
    def with_dict_state():
        val2 = yield dict_state_set("a", 2)
        yield dict_state_copy("a", "b")
        state = yield get_state()
        mreturn(val2)

    print with_dict_state().run({}) # (2, {"a" : 2, "b" : 2})

###### Continuation Monad #########

class ContinuationMonad(Monad):
    def __init__(self, run):
        self.run = run

    def __call__(self, cont = fid):
        return self.run(cont)        

    def bind(self, bindee):
        return ContinuationMonad(lambda cont : self.run(lambda val : bindee(val).run(cont)))

    @classmethod
    def unit(cls, val):
        return cls(lambda cont : cont(val))

    @classmethod
    def zero(cls):
        return cls(lambda cont : None)
    
def callcc(usecc):
    return ContinuationMonad(lambda cont : usecc(lambda val : ContinuationMonad(lambda _ : cont(val))).run(cont))
    
def continuation_monad_example():
    from collections import deque

    class Mailbox:
        def __init__(self):
            self.messages = deque()
            self.handlers = deque()

        def send(self, message):
            if self.handlers:
                handler = self.handlers.popleft()
                handler(message)()
            else:
                self.messages.append(message)

        def receive(self):
            return callcc(self.react)

        @do(ContinuationMonad)
        def react(self, handler):
            if self.messages:
                message = self.messages.popleft()
                yield handler(message)
            else:
                self.handlers.append(handler)
                done(ContinuationMonad.zero())

    @do(ContinuationMonad)
    def insert(mb, values):
        for val in values:
            mb.send(val)

    @do(ContinuationMonad)
    def multiply(mbin, mbout, factor):
        while True:
            val = (yield mbin.receive())
            mbout.send(val * factor)

    @do(ContinuationMonad)
    def print_all(mb):
        while True:
            print (yield mb.receive())

    original   = Mailbox()
    multiplied = Mailbox()

    print_all(multiplied)()
    multiply(original, multiplied, 2)()
    insert(original, [1, 2, 3])()

if __name__ == "__main__":
    failable_monad_examle()
    state_changer_monad_example()
    continuation_monad_example()

20 comments:

  1. Holy moly!

    This is a really nice way of doing it.

    I've been interested in using Monads in my Python code for some time (for parsing) and I think that I'm definitely going to use your approach.

    ReplyDelete
  2. I'm dying to know the should... all this functional stuff is quite confusing... I get the idea that I need to learn it, just need to make the jump (and it seems like a big one).

    ReplyDelete
  3. Can't you show full runnable source file? It will be a great help to know about the subject.
    Thanks in advance.

    ReplyDelete
  4. I've added fully runnable source to the bottom of the article.

    ReplyDelete
  5. In Monad.make_decorator, you're using the comparison (==) operator when I think you mean to use the assignment operator (=). "decorated.__name__ == undecorated.__name__" and "decorator.__name__ == func.__name__" should both be assignment.

    ReplyDelete
  6. Hi peter,

    Neat! I'm still going through the monad code, but I was interested in the use of Maybe and Failure. How easy is it to add these to unsafe code? And what sort of debugging output is attached to them? I guess I'm basically curious as to how functional programming does debugging.

    BTW, it inspired me to use a Python exception handling framework to get most of the benefits of the Maybe monad. The post is here.

    Looking forward to the should to know more.

    ReplyDelete
  7. You can not raise a NotImplementedError in code that is meant to demonstrate a proof-of-principle to be read on a blogpost.

    ReplyDelete
  8. brian: Abstract Base Classes. Google. Go now, you can make it.

    ReplyDelete
  9. hi, i just found this after implementing monads in python myself. i'd be interested in hearing what you think of my code. i took a completely different approach and i am not even sure i am "really" implementing monads - i don't try to use lambdas to bind the values, for example. on the other hand, it's a *lot* simpler :o)

    i don't completely understand what you've done, but when i have a spare moment i am going to go step-by-step through the details (i am returning to python after not using much for several years and generators are pretty much new to me).

    cheers,
    andrew

    ps http://acooke.org/cute/MonadsinPy0.html

    ReplyDelete
  10. Thank your for this great stuff!

    I'm writing a monad tutorial with examples in various languages. I would like to use your code to have the do-notation in the examples in python. Would you allow it ? And if yes, under which licence ?

    ReplyDelete
  11. I played a bit with your code and unfortunately yields are not good for all cases, for example it doesn't work with the List Monad.

    When you bind the monad 'm' with the function 'f'. 'f' can be called several times, this tipically the case with the List Monad.

    But with yields, the code:
    x = yield a
    y = yield b
    c
    Which should be equivalant to :
    a >>= (lambda x : b >>= (lambda y : c))

    So let's call 'f' = (lambda x : b >>= (lambda y : c)) . With the List monad, 'f' has to be called as many times as elements in a, which means 'x' has to take as many values as elements in 'a'. But the second time we use "send" to give a value to 'x' through the yield, it won't be another value to 'x' but the value to 'y'.

    So your code works well for monads where the binding fonction is called once and exactly once, otherwise you won't call the right yield.


    A solution would be to fork the generator as many time as values to give to 'x' but i couldn't get the library to work.

    Aanand uses a very nice approach in Ruby, it transform the abstract syntax tree at run time to replace the do-notations assginments by plain calls to bind. I tried to port it to python but ast is python looks to complex !! And i don't even now if it's possible to access the AST of an object what is needed to deal with alpha-conversion and avoid name capture.

    What would be great would be a python preprocessor, but i didn't find any.

    ReplyDelete
    Replies
    1. Use for...in : relevant stack overflow article http://stackoverflow.com/questions/2657068/idiomatic-python-times-loop

      Delete
  12. I've done something. It works in the simple examples i've tried but i'm very new to python so it might be only these examples. I encode a do-bloc as a string of the form

    """
    x <- a_expresion
    another_expression
    y <- again_one
    ...
    last_expression
    """

    And build the expression with bind from it and then evaluate it.

    I had a strange problem: if i use a do-block in a fonctoin which takes an argument, it can only be seen in the first statement of the do block :

    def test(x):
    return eval("mreturn(x)")

    will work, but :

    def test(x):
    return eval("mreturn(1).bind(lambda y : mreturn(x)")

    will fail saying "NameError: global name 'x' is not defined"

    I has to build a closure to the expression from the list of local names.
    Here is my code :




    #
    # MONAD LIST
    #

    def concat(x) :
    res = []
    for y in x :
    res.extend(y)
    return res


    class Monad:
    value=None
    def __init__(self,val):
    self.value=val

    @staticmethod
    def mreturn(self,val):
    raise NotImplementedError

    def bind(self, func):
    raise NotImplementedError

    def __ge__(self, bindee):
    return self.bind(bindee)

    # THE >> Haskell operator
    def __rshift__(self, bindee_without_arg):
    return self.bind(lambda _ : bindee_without_arg)


    class Liste(Monad):
    @staticmethod
    def mreturn(val) :
    return Liste([val])

    def bind(self,func):
    def fval(x):
    return func(x).value

    return Liste(concat(map(fval,self.value)))

    @staticmethod
    def zero():
    return Liste([])

    def run(self):
    return self.value


    #
    # THE DO NOTATION
    #

    import re
    import compiler


    # PARSE ASSIGNMENT "x <- m"
    doasgn = re.compile(r"^\s*(\w)+\s*<-\s*(.*)")
    # PARSE NON EMPTY LINES
    dostmt = re.compile(r"\S.*\S?")


    # BUILD THE BIND EXPRESSION FROM OF LIST OF DO-STATEMENTs
    def dolist(l):
    if len(l) == 1 :
    return l[0]
    else :
    mre = doasgn.match(l[0])
    if mre :
    g = mre.groups()
    return ("(" + g[1] + ").bind(lambda " + g[0] + " : " + dolist(l[1:]) + ")")
    else :
    return ("(" + l[0] + ") >> (" + dolist(l[1:]) + ")")


    # TRANSORM A DO BLOCK INTO A BIND EXPRESSION
    do = lambda s : dolist(dostmt.findall(s))
    # COMPILE A DO BLOCK INTO A CODE EXPRESSION
    cdo = lambda s : compiler.compile(do(s),'compiledo.py','eval')

    # PYTHON HAS PROBLEMS TO SEE LOCAL VARIABLES WHEN EVALUATING :
    #
    # def test(x) :
    # return eval(do("""
    # List.mreturn(x)
    # """)
    #
    # print test(5).run()
    #
    # Will give the good result but :
    #
    # def test(x) :
    # return eval(do("""
    # y <- .....
    # List.mreturn(x)
    # """)
    #
    # print test(5).run()
    #
    # Will give the error : NameError: global name 'x' is not defined
    # To avoid that, we build a closure from the list of local variables
    # with (lambda x : ...)(locals()["x"])
    # So x is in the context of the expression with the good value in locals

    def closure(v,m):
    l = v
    for x in m.keys() :
    l = "((lambda " + x + " : " + l + ")(m[\"" + x + "\"]))"
    return "(lambda m : " + l + ")"

    # JUST TO EVALUATE THE BLOCK
    def rundo(g,l,s):
    return eval(closure(do(s),l),g,l)(l)


    # A TEST :
    # Liste([a,.....]) will lift the list [a,....] into the monad
    def toto(x,y,z,d):
    l = test.rundo(globals(),locals(),"""
    a <- Liste([x , x + 1 ])
    b <- Liste([y , y + 1 ])
    c <- Liste([z , z + 1 ])
    Liste.mreturn(x + y + z + a + b + c + d)
    """)
    return l.run()


    print toto(1,10,100,1000)
    # WILL GIVE : [1222, 1223, 1223, 1224, 1223, 1224, 1224, 1225]

    ReplyDelete
  13. My blog has opened so many doors for me and has helped me land quite a few jobs. By being immersed in writing and showing initiative, having a blog has been a great platform and portfolio. And I would recommend to anyone looking to start or build a portfolio to have a blog. e sağlık

    ReplyDelete
  14. You should use functools.wrap or update_wrapper for your decoraters instead of manually playing with __name__

    ReplyDelete
  15. Have you looked into the possibility of using `>>=` operator (`__irshift__`) and `greenlet` for this, instead of the somewhat limited `yield`?

    ReplyDelete
  16. Hiya, I just came across this blog by dumb luck (was actually researching parsec at the time) and totally missed it when I wrote a similar piece (http://ra3s.com/wordpress/dysfunctional-programming/non-determinism-from-generators/).

    I noticed though that your monad decorator doesn't handle the multiple invocation case. You might want to take a look at what I did. I enjoy how you've generalized it to accept more than one monad.

    Also, you might be interested in trying out PyPy. Their generators can be cloned, which would be useful for multishot without the inefficiency in my technique.

    ReplyDelete
  17. Typo? "def failable_monad_examle()"

    Last time I checked, there was a 'p' somewhere in there.

    ReplyDelete

Blog Archive

Google Analytics