Harvard Street

The street names surrounding Tufts University are "Harvard Street", "Yale Dr", and "Princeton Blvd".

I've never visited Yale, but the other schools do not have similarly named streets in their vicinity. They do not feel the need to. And even if they did, Tufts would certainly not be one of the street names.

I highly doubt that Medical or Law professionals describe their profession in relation to software.

They do not feel the need to.

Functional Patterns in Ruby: Monads

Haskell has a concept called a "Monad" which allows programmers to model IO, state, etc, in a purely functional manner. However, the concept is also useful in non-pure languages such as Lisp, Scheme, Smalltalk, Ruby, Java, and others.

The concept of a Monad is very simple, but sounds daunting at first. The idea is that you have an object that acts as a container (or context), and a way to sequence expressions.


In Ruby, Java, and many other languages, it's common to see code like the following:

if foo != nil && foo.bar != nil
  foo.bar.baz
end

The idea is that you want to chain a bunch of methods together (this is the sequencing of expressions), but any of these methods could result in a nil object, which would cause an exception to be thrown. To avoid that situation, a collection of boolean expressions are chained together to decide if the last expression should be evaluated (this is the context). Since this is a common pattern, it can be useful to extract it.


Assume I have the following two classes:

class Foo
  attr_accessor :bar
  def initialize(bar)
    @bar = bar
  end
end

class Bar
  attr_accessor :baz
  def initialize(baz)
    @baz = baz
  end
end

.... and an instance of each of them.....

bar = Bar.new(5)
foo = Foo.new(bar)

.... then the following will evaluate to 5

foo.bar.baz => 5

.... However, if foo is nil.....

bar = Bar.new(5)
foo = nil

.... I will get an exception......

foo.bar.baz ->
NoMethodError: undefined method `baz' for nil:NilClass
    from (irb):7
    from :0

Haskell models this concept with the "MaybeMonad". If you have a nil value, there is no reason to continue evaluating the remaining computation.

Using a MaybeMonad in Ruby, you could wrap a value in the Monad, call your chain of messages without needing explicit nil checks, and the unwrap the value at the end of the chain.

foo.liftIntoMaybeMonad.bar.baz.value -> 5
nil.liftIntoMaybeMonad.bar.baz.value -> nil

Here is a pseudo "MaybeMonad" in Ruby:

class Object
  def liftIntoMaybeMonad
    MaybeMonad.new(self)
  end
end



class MaybeMonad
  attr_accessor :value
  def initialize(v)
    @value = v
  end

  def monadicBind(proc)
    if @value != nil
      proc.call.liftIntoMaybeMonad
    else
      self
    end
  end

  def method_missing(method_name, *args)
    monadicBind(Proc.new {@value.send(method_name, *args)})
  end
end

The MaybeMonad is a container for some other value. The "monadicBind" method takes in a procedure, and if the value that the MaybeMonad is wrapping is non-null, it calls the procedure on the value, and lifts the result into a new instance of the MaybeMonad. If the value that the MaybeMonad is wrapping is null, "monadicBind" just returns itself because there is no value. At the end of the computation, we need to unwrap the wrapped value.


This explanation is far from rigorous, complete, or correct, but I hope that somebody may have found this explanation useful.

International Lisp Conference 2009 in Boston

I will be using vacation time to attend the International Lisp Conference in Boston next month. I'm highly looking forward to hearing the man himself, Gerald Sussman, speak. Additionally, I'm curious to see what people have to say about "The Great Macro Debate". I have my opinions on the subject; however, mine are probably pretty puerile when compared to others. As such, I look forward to learning a lot!

Simon Peyton-Jones' XMonad session

While watching his session on XMonad, the main question I have is, "where is the other half of the door?"

DRY

I've never liked the term DRY (Don't Repeat Yourself). I prefer STAFTS (Separate the Abstract from the Specific), mainly because it's catchier.

Functional Collection Patterns in Ruby, Part 3: ScanL and ScanR

This is a continuation of my posts on functional collection patterns in Ruby.

When using a language with high order functions, one can abstract out many common patterns on collections. So far I've described Map, Filter, Reduce (also known as foldl, foldr, or inject), Zip, and Flatmap.

ScanL

When using a pattern such as Reduce, sometimes you want all of the intermediate results of the folding, instead of just the final result. In Haskell, these functions are referred to as "scanl" and "scanr". The r or l on the end specify which way the folding occurs.

For example, the following shows its use:

irb(main):239:0> [1,2,3,4].scanl(0) {|acc, e| acc + e}
=> [1, 3, 6, 10]

To illustrate scanl, I will use the bowling example from "Agile Software Development" by Bob Martin.

Assume that I've already implemented all of the logic except for scoring. The frame are represented using an array, and each frame can have up to three values, reflecting the score that should be added for the frame.

irb(main)> game = BowlingGame.new
irb(main)> [4,3,3,7,4,6,10,9,1,10,10,10,7,3,10,10,10].map {|t| game.throw t}
irb(main)> game
=> #<BowlingGame:0xb7c85c78 
       @first_throw=true, 
       @frames=
       [[4, 3, nil], [3, 7, 4], [4, 6, 10], 
        [10, 9, 1], [9, 1, 10], [10, 10, 10],
        [10, 10, 7], [10, 7, 3], [7, 3, 10],
        [10, 10, 10]], 
       @maximum_frames=10, 
       @continuations=[#<Proc:0xb7c6a7fc@(irb):54>, #<Proc:0xb7c6a7c0@(irb):52>]>

 

What I want to do is call "to_a" on the game, and get back a multidimensional array that looks like what I would see in a real bowling alley. This can be achieved using scanl and zip.

  def score
    @frames.scanl(0) {|acc, frame|
      acc + frame.score
    }
  end
 

The way scanl works is that it takes an initial value and a block. It acts like inject, folding from the left, but instead of returning one scalar value, it returns an array of all of the intermediate scalar values.

irb(main)> game.score
=>   [7, 21, 41, 61, 81, 111, 138, 158, 178, 208]
 

Now that I have the scores, I can zip them up with each frame's corresponding throws

  def to_a
    (@frames[0..8].map {|x| x.throws} + [@frames[9]]).zip(score)
  end

Now, "game.to_a" evaluates to something which could be displayed on a real bowling alley monitor.
[[[4, 3], 7],
[[3, 7], 21],
[[4, 6], 41],
[[10], 61],
[[9, 1], 81],
[[10], 111],
[[10], 138],
[[10], 158],
[[7, 3], 178],
[[10, 10, 10], 208]]


Complete Source Code

module Enumerable
  def scanr(initial_value, &block)
    as_array = self.to_a
    if as_array.empty?
      [initial_value]
    else
      result = as_array[1..-1].scanr(initial_value,&block)
      [block.call(as_array[0],result[0])] + result
    end
  end

  def scanl(initial_value, &block)
    as_array = self.to_a
    if as_array.empty?
      []
    else
      head = block.call(initial_value, as_array[0])
      [head] + as_array[1..-1].scanl(head,&block)
    end
  end
  
end


class Array
  def strike?
    10 == self[0]
  end

  def spare?
    !strike? and 10 == self[0] + if self[1] then self[1] else 0 end
  end

  def throws
    return [self[0]] if strike?
    self[0..1]
  end

  def score
    reject {|x| x.nil?}.inject {|acc,x| acc + x}
  end

end




class BowlingGame
  def initialize
    @frames = []
    @first_throw = true
    @continuations = []
    @maximum_frames = 10
  end
  
  def current_frame
    @frames[-1]
  end 
  
  def throw(pins)
    add_pins_to_current_frame(pins)
    add_pins_to_previous_frames(pins)
    remember_to_add_future_pins_to_this_frame
    update_first_throw
    self 
  end

  def add_pins_to_current_frame(pins)
    if @first_throw and @frames.size < @maximum_frames
      @frames << [pins,nil,nil]
    elsif @frames.size <= @maximum_frames
      @frames[-1][1] = pins
    end
  end
  
  def add_pins_to_previous_frames(pins)
    @continuations = @continuations.map {|cont| cont.call(pins)}.select {|x| x.class == Proc}
  end
  
  def remember_to_add_future_pins_to_this_frame
    cf = current_frame
    if cf.strike?
      @continuations << Proc.new {|pins| 
        cf[1] = pins 
        Proc.new {|pins| cf[2] = pins}
      }
    elsif cf.spare?
      @continuations << Proc.new {|pins| cf[2] = pins}
    end
  end
  
  def update_first_throw
    @first_throw = !current_frame[1].nil? || current_frame.strike?
  end

  def score
    @frames.scanl(0) {|acc, frame|
      acc + frame.score
    }
  end

  def to_a
    (@frames[0..8].map {|x| x.throws} + [@frames[9]]).zip(score)
  end
end

Floating point

I subscribe to a few programming language mailing lists, and I'm surprised how frequently people believe they've found an issue with the language implementation when operations on floating points aren't exact.