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)

14 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
  12. Bạn đang cần tìm địa chỉ mua hàng Trung Quốc tốt nhất? Hãy đến với lamphongchina. Chúng tôi là nơi chuyên cung cấp các Dịch vụ vận chuyển hàng hóa từ trung quốc uy tín chất lượng, Dịch vụ đặt mua hàng từ Trung Quốc, vận chuyển hàng hóa từ quảng châu về việt nam... Khi bạn đến với chúng tôi, chúng tôi sẽ giải đáp các thắc mắc cho bạn. Khi bạn gặp rắc rối chúng tôi sẽ hổ trợ bạn giải quyết vấn đề. Đối với những cần nhập hàng Trung Quốc giá rẻ thì chúng tôi đã có Dịch vụ nhập hàng từ Trung Quốc về Việt Nam giá rẻ sẽ giúp bạn giải quyết. Hãy đến với chúng tôi để được phục vụ tốt nhất nhé.

    ReplyDelete
  13. تعتبر العاب تلبيس من اشهر الانواع في هذا المجال وهي بدورها تتضمن عدة اصناف جميلة ويعشقها الكتير وخاصة البنات منها العاب تلبيس ومكياج التي تمزج بين التلبيس وكذلك الميك اب في آن واحد هذا الامر الدي يزيد من جمالها وتجعل كل من يلعبها يستمتع بذلك زد على ذلك العاب تلبيس باربي التي تعرف شعبية كبيرة لانها شخصية مشهورة ويعرفها الصغير والكبير ولهم ذكريات جميلة معها لانها اشتهرت في عالم الكارتون والان اصبح الامر كذلك في مجال الالعاب وغير هذا هناك كذلك نوع آخر مميز ايضا وهو العاب تلبيس عرائس فالجميع يحلم ان يقوم بتلبيسهما لانها تذكرهم بهذه المناسبة الجميلة الا وهي الزواج التي تعتبر اهم مرحلة في حياة الانسان وهناك انواع مغايرة لها جمهور كبير في كل انحاء العالم وهي العاب قص الشعر ليس هي فقط بل توجد ايضا العاب طبخ التي يمكن للجميع لعبها سواء كانوا اولادا او بناتا وهي الاكتر طلبا في النت ويحبها الجميع ومعها ايضا العاب باربي التي تكلمنا عليها بكل انواعها تتنوع العاب فلاش وذلك على حسب كل شخص ورغبته فهناك عدة انواع منها وهناك من هي خاصة بالبنات واخرى للاولاد وتعتبر العاب تلبيس من اكتر الالعاب انتشارا في الويب وهي محبوبة عند الجميع ولديها جمهور واسع كما انها سهلة اللعب والجميع يمكنه لعبها بسهولة تامة بدون صعوبات تذكر كما ان هناك انواع اخرى متل العاب طبخ والعاب اكشن ومكياج و سيارات الى غير ذلك فلك صنف جمهوره ومحبيه ولكن تبقى العاب بنات الاكتر انتشارا وشعبيتنا في عالم العاب الفلاش كما انها تحتوي على شخصيات معروفة وغنية عن التعريف متل باربي و سندريلا وشخصيات اخرى تركت بصمتها في هذا المجال لهذا اصبح يعتمد عليها كتيرا في صنف العاب تلبيس بنات الدي تحبه البنات بكترة خاصة في العالم العربي مما يجعل المواقع الخاصة بهذا النوع تزداد يوما بعد الاخر فذلك ليس عبثا ففي الحقيقة نوع العاب التلبيس من اجمل اصناف العاب فلاش بصفة عامة و العاب بنات بصفة خاصة

    ReplyDelete

Blog Archive

Google Analytics