I've learned. I'll share.

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)

11 comments:

  1. I think what I have the biggest problem is... what to do with this?

    ReplyDelete
  2. I plan to write another article (or maybe a few) explaining what you can do with monads, and thus this syntax. Explaining how this works was big enough for one article (actually, two, there was one for python as well).

    ReplyDelete
  3. I don't have a haskell background so I've no idea what monads might be useful for, but here's how to get around your bind/bindb thing.

    def bind( proc = nil, &block )
    actual_bind( proc || block )
    end

    ReplyDelete
  4. Peter: combinator parsing!

    ReplyDelete
  5. afaik there is a difference between blocks and functions. the difference has to do with scope. sry i have no link available.

    ReplyDelete
  6. Maybe the Superator gem would enable you to use <- as an operator instead of =xx?

    ReplyDelete
  7. Methods may override operators: .., |, ^, &, <=>, ==, ===, =~, >, >=, <, <=, +, -, *, /, %, **, <<, >>, ~, +@, -@, [], []= (2 args)

    ReplyDelete
  8. It wouldn't have to be Scala or Perl6: see The Lord of the Lambdas to find out the alternative.

    ReplyDelete
  9. Hi Peter!
    This is another great bit of code (after your "Pysec" parser) - very nice!

    You very kindly agreed that Pysec could be used as public domain when I asked about it (in comments at bottom of that page - I'm the Andy there), so may I also include this Ruby parser in the public-domain collection of code that I'm putting together? (You will be credited and praised, that goes without saying...) Very many thanks for your time - bye for now!
    - Andy
    ( Oh, and btw, is it possible for you to email your email address to me? That is so I can email you to ask/thank you in future, instead of doing so via comments... Mine is - andy dot elvey at paradise dot net dot nz ) Thanks!
    - Andy

    ReplyDelete
  10. Hi Peter,

    There is now a ruby gem, Rumonade, that implements these ideas:
    https://github.com/ms-ati/rumonade

    If you give it a try, please let me know what you think of it in terms of correctness and (more importantly) usability.

    In terms of implementation, in Rumonade the Monad mix-in requires that the host class implement self.unit and #bind, and it adds the rest. Array is adapted for it, and it adds an Option and Either class so far.

    ReplyDelete
  11. There is also the monadic gem https://github.com/pzol/monadic which implements the monads with inheritance.

    ReplyDelete

Blog Archive

Google Analytics