I've learned. I'll share.

January 21, 2008

Garlic Programmers for Silver Code?

I just read Larry O'Brien's article about there being no silver programmers. He makes the case that although there may be great variance in programmer productivity, "the significant thing is not that some professional programmers are awesome, it's that some professional programmers suck". I admire Larry O'Brien greatly, and I think there is much wisdom in what he says here.

But I think he's missing something.

I have noticed a trend in my own productivity: my productivity varies greatly with the code base I'm working on. This variance may be greater than that between individual programmers. While many are rightly concerned with individual and team productivity, no ever talks about code base productivity. If we do, where does it lead us?

A few years ago, I was working for a small medical software company. One project was a new venture with a new code base. Though new, the code was already difficult to work with. Its design forced the developer to duplicate work. In my first meeting about the project, I was told we had to do lots of "fat fingering". I didn't even know what that meant. It turned out to mean typing almost the exact same thing over and over. I was horrified and ultimately wrote a code generation tool to automate the work. Though creating and maintaining it was extra work in itself, without it, doing many common tasks in this code easily took 3x longer than necessary.

After that project was "shelved", I was moved to the company's main product, which was older and had a much more "mature" code base. Actually, half was new-style (similar to what I had been working on) and half was old-style. The old-style code was even worse to work with. It was so bad that I was almost giddy whenever I could work on the new-style code. I'm sure you know what kind of code I'm talking about. Doing anything in this code easily took 3x even longer.

Combined, that's 9x slower. That seems too high. Is it even possible? How can a code base reduce productivity so much? Here are a few possibilities I thought of; I'm sure you can think of more:

  • Bad code leads to more code, and more code is slower to work with
  • Bad code is hard to understand
  • Bad code is dangerous to change
  • Bad code leads duplication of effort
  • Bad code leads to a slow change-compile-test cycle, leading to wasted time and loss of focus
  • Bad code from third party libraries can drive you crazy by crashing, malfunctioning randomly, or having little documentation
  • Bad code saps energy, interest, and morale

A bad code base makes any programmer less productive. Have you ever noticed that when you work from scratch with no code base to weigh you down, you can be much more productive? Imagine that as your baseline productivity. Now think of how long it takes you to accomplish something similar on a project that you're working on right now. How does it compare? I bet you're slower on the existing project.

But wait just a minute. Imagine if my list of the effects of bad code were reversed. What if, instead, it read:

  • Good code leads to less code, and less code is easier to work with
  • Good code is easy to understand
  • Good code is safe to change
  • Good code avoids duplication of effort
  • Good code leads to a quick change-compile-test cycle
  • Good code uses libraries which remove the need for "dirty work" and let you focus on the important problems
  • Good code is fun to work with!

A good code base makes any programmer more productive. Have you ever worked on a project that was so wonderful that you could crank out magnificent results almost effortlessly? Perhaps it has a great DSL embedded in it or has powerful infrastructure.

Even with conservative estimates, if bad code slows us down 5x and good code speeds us up just 2x faster, that's easily a 10x difference.

Maybe silver programmers don't exist. But is there "silver code"? What if there are programmers who are more adept at writing silver code? If they can make a code base that's just 2x easier to work with long-term, then that makes everyone that works on that code 2x more productive, possibly forever. If such programmers exist, then they must be extremely valuable, not so much because of their own productivity, but because of the effect they will have on the productivity of others in the future. Perhaps rather than "silver bullet" programmers that kill werewolves, these are just "garlic programmers" that ward of vampires.

Given that productivity can vary so much with quality of existing code, perhaps its worth looking for "garlic programmers" who will write code that will keep the rest us of productive long-term. I leave it as an exercise for the reader to figure out how to measure a programmer's garlic-ness :).

January 15, 2008

List Monad in Ruby and Python

Recently, I wrote about ways to add something like Haskell's do syntax to programming languages like python and ruby. The python trick used bidirectional generators and the ruby trick used callcc. I have since been notified that there is one serious problem with both of them: the bindee (the function given to bind) can only be called once. For many monads, this limitation is acceptable, but for some, it means you can't use that nice syntax.

Take the List monad, for example, in ruby:

class ListMonad < Monad
  attr_accessor :array

  def initialize(array)
    @array = array
  end

  def bind(bindee)
    ListMonad.new(concat(array.map { |val| maybeUnit(bindee.call(val)).array }))
  end

  def self.unit(val)
    self.new([val])
  end

  def to_s
    joined = array.join(', ')
    "ListMonad([#{joined}])"
  end
end

## I'm hoping this if faster than using fold (inject)
def concat(arrays)
  all = []
  for array in arrays
    all += array
  end 
  all
end

class Array
  def bind(bindee)
    ListMonad.new(self).bind(bindee)
  end

  def bindb(&block)
    ListMonad.new(self).bindb(&block)
  end
end
Ruby gives us the ability to extend Array to get a pretty sweet looking use of the monad:
list1 = with_monad ListMonad do
  x =xx    [1,2,3]
  y =xx [10,20,30]
  x + y
end

It looks great, but list1 should be ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]), be we get ListMonad([11]) instead.

Traditional binding works fine:

list2 = [1, 2, 3].bindb do |x|
  [10, 20, 30].bindb do |y|
    x + y
  end
end

list2 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). So, we know our monad is fine, but our with_monad doesn't work.

We have the same problem in python:

class ListMonad(Monad):
    def __init__(self, vals):
        self.vals = vals

    def bind(self, bindee):
        return self.__class__(concat((self.maybeUnit(bindee(val)) for val in self.vals)))

    @classmethod
    def unit(cls, val):
        return cls([val])

    def __repr__(self):
        return "ListMonad(%s)" % self.vals

    def __iter__(self):
        return iter(self.vals)

def concat(lists):
    return [val for lst in lists
                for val in lst]

@do(ListMonad)
def with_list_monad():
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

list1 = with_list_monad()

def with_list_monad_binding():
    return \
    ListMonad([  1, 2, 3])  >> (lambda x:
    ListMonad([10, 20, 30]) >> (lambda y:
    x + y))

list2 = with_list_monad_binding()
    

Again, it looks good, but list1 is ListMonad([11, None, None, None, None]) while list2 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). The result of list1 sure is bizarre.

Luckily, I have found a solution for ruby, and a bad hack that could be construed as a solution for python if you ignore some issues.

In Ruby, the trick is to monkey with the rbind continuation so that at the end of with_monad it returns control to the point where the continuation is called. In other words, we need to store a second continuation at the point right after the first continuation is called. Confused yet? Continuations will melt your brain, and this took a little while for met get right:

def with_monad_ext(monad_class, &block)
  finishers = []

  rbind_ext = lambda do |monad|
    begin
      checked_callcc do |outer_cont|
        monad.bindb do |val|
          callcc do |inner_cont|
            finishers.push(inner_cont)
            outer_cont.call(val)
          end
        end
      end
    rescue ContinuationUnused => unused
      raise MonadEscape.new(unused.result)
    end
  end

  val = begin
    monad_class.maybeUnit(block.call(rbind_ext))
  rescue MonadEscape => escape
    escape.monad
  end

  finisher = finishers.pop()
  if finisher
    finisher.call(val)
  else
    val
  end
end

list3 = with_monad_ext ListMonad do |rbind|
  x = rbind.call    [1,2,3]
  y = rbind.call [10,20,30]
  x + y
end

Success! list3 is correctly ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). The only real problem is that the normal rbind won't work. We have to make a special one and give it to the block as an argument. This wouldn't be that bad, except that Ruby has this silly limitation so we have to say rbind.call rather than just rbind, which makes it less fun to type. I named it with_monad_ext because I don't think it will be needed as often as with_monad, and with_monad is more convenient.

Now, back to python. The problem is harder. It's rooted in the fact that for a given iterator, itr.send() is not reentrant. But, if we could copy the iterator, that would give us a possible solution. I did a little googling and found that python isn't going to have copy.copy(itr) anytime soon because no one cares about them. Some people have made some progress, but it segfaults on my computer (64-bit Linux, in case you're wondering).

So, I came up with this terrible little hack which makes it possible to "copy" iterators:

class CopyableIterator:
    def __init__(self, generator, log = ()):
        self.generator = generator
        self.log       = list(log) #hmmm... if the logs were immutable, we wouldn't have to do this
        self.iterator  = None

    def getIterator(self):
        if self.iterator is None:
            self.iterator = self.generator()
            for value in self.log:
                self.iterator.send(value)
        return self.iterator
            
    def send(self, value):
        iterator = self.getIterator()
        self.log.append(value)
        return iterator.send(value)

    def next(self):
        return self.send(None)

    def copy(self):
        return self.__class__(self.generator, self.log)

That let's us define @do_ext:

@decorator_with_args
def do_ext(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(itr, val):
                try:
                    # here's the real magic
                    monad = Monad.maybeNew(itr.send(val))
                    return monad.bind(lambda val : send(itr.copy(), val))
                except StopIteration:
                    return Monad.unit(None)
                
            return send(CopyableIterator(lambda : func(*func_args, **func_kargs)), None)
        else:
            #not really a generator
            if itr is None:
                return Monad.unit(None)
            else:
                return itr

    return run_maybe_iterator()

@do_ext(ListMonad)
def with_list_monad_ext():
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

list3 = with_list_monad_ext()

And list3 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23]). Success again! There is a downside, though. First, all of the calculations are done for all of the combinations. This is especially bad if you do this:

@do_ext(ListMonad)
def with_list_monad_ext():
    print "foo"
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

Because now you'll print "foo" 9 times instead of 1.

So there you have it: you can do the List monad with do syntax in python and ruby, but you'll have to decide whether the trade-offs are worth it.

January 9, 2008

Monads in Ruby (with nice syntax!)

My last article was about how you can do monads in python with nice syntax. Now I'd like to present nice monad syntax in Ruby. I'm not explaining what monads are or how you can use them. For now, I'm expecting you to be familiar with monads. If you aren't, go read a nice article on them.

Imagine you have a Monad base class like this:

class Monad
  def bind(func)
    raise "not implemented"
  end

  def self.unit(val)
    raise "not implemented"
  end

  # bind to block
  def bindb(&func)
    bind(func)
  end
end

As an aside, Please excuse there being a "bind" and a "bindb". It's silly that Ruby differentiates between a block and Proc like that. I also think it's silly that I have to keep typing "lambda {|val| func(val)}" to turn a method into a Proc and "proc.call(val)" to call a Proc. In python, methods, functions, and lambdas are all the same thing, and it's a lot easier to code with. In this sense, python is way better. But Ruby has really slick syntax for passing in the block, and python's lambda restrictions are annoying. Why can't we have the best of both? I guess then I'd need Scala or Perl6. End aside.

Let's implement the Either monad, which I call it Failable:

class Failable < Monad
  def initialize(value, success)
    @value   = value
    @success = success
  end

  def bind(bindee)
    if @success
      bindee.call(@value)
    else
      self
    end
  end

  def self.unit(val)
    self.new(val, true)
  end

  def to_s
    if @success
      "Success(#{@value})"
    else
      "Failure(#{@value})"
    end
  end
end

def success(val)
  Failable.new(val, true)
end

def failure(val)
  Failable.new(val, false)
end

Now we can write some code that safely handles divide by zero without using exceptions (actually, exceptions essentiatlly are the Either monad, but never mind that for now):

def fdiv(a, b)
  if b == 0
    failure("cannot divide by zero")
  else
    success(a / b)
  end
end

def fdiv_with_binding(first_divisor)
  fdiv(2.0, first_divisor).bindb do |val1|
    fdiv(3.0, 1.0)        .bindb do |val2|
      fdiv(val1, val2)    .bindb do |val3|
        success(val3)
      end
    end
  end
end

puts fdiv_with_binding(1.0)
puts fdiv_with_binding(0.0)

Which prints:

Success(0.666666666666667)
Failure(cannot divide by zero)

But it's not very pretty. Luckily, ruby has callcc, which makes it very easy to define a function which I'll call "rbind" which can do this:

def fdiv_with_rbinding(first_divisor)
  with_monad Failable do
    val1 = rbind fdiv(2.0, first_divisor)
    val2 = rbind fdiv(3.0, 1.0)
    val3 = rbind fdiv(val1, val2)
    val3
  end
end

def with_monad(monad_class, & block)
  begin
    val = block.call()
    if val.class == monad_class
      val
    else
      monad_class.unit(val)
    end
  rescue MonadEscape => escape
    escape.monad
  end
end

def rbind(monad)
  begin
    checked_callcc {|cc| monad.bind(cc)}
  rescue ContinuationUnused => unused
    raise MonadEscape.new(unused.result)
  end
end

class MonadEscape < RuntimeError
  attr :monad

  def initialize(monad)
    @monad = monad
  end
end

def checked_callcc(&with_cc)
  callcc do |cont|
    val = with_cc.call(lambda {|val| cont.call(val)})
    raise ContinuationUnused.new(val) if cont
    val
  end
end

class ContinuationUnused < RuntimeError
  attr :result
  
  def initialize(result)
    @result = result
  end
end  

Ruby's block syntax makes it very nice to say "with_monad Monad do", which I like. But I don't really like seeing "= rbind". I'd really like it if we could override "<<" and read that as "=<<", but I think we're stuck with unary operators ("+", "-", "~", all of which look bad here) or words. At least we can choose our name, unlike in python where we have to use "yield". Does anyone have any idea for a better name?

Maybe "xx" would work:

def fdiv_with_rbinding(first_divisor)
  with_monad Failable do
    val1 =xx fdiv(2.0, first_divisor)
    val2 =xx fdiv(3.0, 1.0)
    val3 =xx fdiv(val1, val2)
    val3
  end
end

So there you have it. You can have nice monad syntax in Ruby using callcc. Unfortunately, I've read that not all implementations of Ruby have continuatoins, which means JRuby and IronRuby may be left out in the cold. Keep in mind that Ruby's "yield" syntax is NOT a true generator, which means that we can't use the same trick that we used in python. It's callcc or nothing.

Here's the complete code in case you want to cut and paste it:

############# Monad Base ##############

class Monad
  def bind(func)
    raise "not implemented"
  end
  
  def self.unit(val)
    raise "not implemented"
  end

  # bind to block
  def bindb(&func)
    bind(func)
  end
end

def with_monad(monad_class, &block)
  begin
    val = block.call()
    if val.class == monad_class
      val
    else
      monad_class.unit(val)
    end
  rescue MonadEscape => escape
    escape.monad
  end
end

# "reverse" bind, or bind to the return value, or bind to the continuation
def rbind(monad)
  begin
    mycallcc {|cc| monad.bind(cc)}
  rescue ContinuationUnused => unused
    raise MonadEscape.new(unused.result)
  end
end


class MonadEscape < RuntimeError
  attr :monad

  def initialize(monad)
    @monad = monad
  end
end

def mycallcc(&with_cc)
  used = false
  val  = callcc do |cc|
    fake_cc = lambda do |val| 
      used = true
      cc.call(val)
    end

    with_cc.call(fake_cc)
  end

  raise ContinuationUnused.new(val) unless used
  val
end 

class ContinuationUnused < RuntimeError
  attr :result
  
  def initialize(result)
    @result = result
  end
end  

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

class Failable < Monad
  def initialize(value, success)
    @value   = value
    @success = success
  end
      
  def bind(bindee)
    if @success
      bindee.call(@value)
    else
      self
    end
  end

  def self.unit(val)
      self.new(val, true)
  end

  def to_s
    if @success
        "Success(#{@value})"
    else
        "Failure(#{@value})"
    end
  end
end

def success(val)
  Failable.new(val, true)
end

def failure(val)
  Failable.new(val, false)
end

######## Failable Monad Example ##########

def fdiv(a, b)
  if b == 0
    failure("cannot divide by zero")
  else
    success(a / b)
  end
end

def with_failable_binding(first_divisor)
  fdiv(2.0, first_divisor).bindb { |val1|
    fdiv(3.0, 1.0)        .bindb { |val2|
      fdiv(val1, val2)    .bindb { |val3|
        success(val3)
      }
    }
  }
end

def xx(monad)
  rbind(monad)
end

def with_failable_rbinding(first_divisor)
  with_monad Failable do
    val1 =xx fdiv(2.0, first_divisor)
    val2 =xx fdiv(3.0, 1.0)
    val3 =xx fdiv(val1, val2)
    val3
  end
end

puts with_failable_binding(1.0)
puts with_failable_binding(0.0)
puts with_failable_rbinding(1.0)
puts with_failable_rbinding(0.0)

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()

Blog Archive

Google Analytics