Home Made Continuations with Ruby

More functional experiments from yours truly. Upon review, I've realized that this code is quite tricky.

Here's the rub: Basically, evens_only_star_cc is a function that processes a gnarly data structure of nested lists (I designate these types of functions with 'star') using a collector (aka a continuation -- hence the cc in the function name). It could just as easily have been called evens_only.

A continuation in this context means that instead of using the call stack the normal way, I'm opting to just nest lambdas. That means that the function needs to be called with a lambda as one of the arguments. You can think of this lambda as the innermost doll in those nifty russian matryoshka doll sets. Each time the function recurs, it wraps the previous doll (lambda) in a new one. When the function reaches its termination point, we can either hand back our 'nested doll lambda call stack' thing as is, or we can apply it to its arguments and undwind it. I'm doing the latter here.

What we're doing is recurring through a crazy ass data structure of integers and collecting only the evens, while at the same time finding the sum of the odd numbers and the product of the even numbers. For sure, there are easier ways to do the same thing, but it's nice to put Ruby to the test every now and again. It's a great language.

The Code

def evens_only_star_cc(l, col)
if l.empty?
  col.call [], 1, 0
elsif l.car.is_a? Fixnum
  if l.car.even?
    evens_only_star_cc l.cdr, ->(op, ep, os) {
      col.call op.cons(l.car),
               (ep * l.car),
               os
    }
  else
    evens_only_star_cc l.cdr, ->(op, ep, os) {
      col.call op,
               ep,
               (os + l.car)
    }
  end
else
  evens_only_star_cc l.car, ->(nop, nep, nos) {
    evens_only_star_cc l.cdr, ->(op, ep, os) {
      col.call op.cons(nop),
               (ep * nep),
               (os + nos)
    }
  }
end
end

Usage

evens_only_star_cc([1, [2, [3]], 4, [[[5]]], 6, [7, [8]], 9, 10],  ->(output, poe, soo) { 
{:output => output, :product_of_evens => poe, :sum_of_odds => soo}
})

Preliminaries

class Array
def car
  first
end

def cdr
  self[1..-1]
end

def cons(s)
  self.unshift s
end
end

class Fixnum
def even?
  (self % 2) == 0
end
end

Ruby: throw/catch vs callcc

More diversions. I earlier stated that this code should be readily understood by intermediate Rubyists. That is false, actually. The code is difficult. Not because it's using advanced Ruby, but because it's using Ruby in a very non standard way. rember_upto_last stands for "remove member upto last". 'a' stands for any atom (perhaps an integer or a symbol or a char). 'lat' stands for list-of-atoms (a simple array of atoms).

rember_upto_last

# if the atom is not in the list we simply return the list.
rember_upto_last 'a', %w(x y z)
=> %w(x y z)

# if the atom is in the list, we only return everything 
# after the atom.
rember_upto_last 'a', %w(x y z a b c)
=> %w(b c)

# if the atom exists in multiple places, then we only 
# return everything after the last instance of the atom.
rember_upto_last 'a', %w(x y z a b c a p q)
=> %w(p q)

version using throw/catch

# with try/catch
def rember_upto_last(a, lat)
result = catch(:jump!) do
  r = lambda do |l|
    if l.empty?
      []
    elsif l.first == a
      throw :jump!, r.call(l[1..-1])
    else
      cons l.first, r.call(l[1..-1])
    end
  end

  r.call(lat)
end
end

version using callcc

# with callcc
def rember_upto_last(a, lat)
result = callcc do |c|
  yComb do |f|
    lambda do |l|
      if l.empty?
        []
      elsif l.first == a
        c.call f.call(l[1..-1])
      else
        cons l.first, f.call(l[1..-1])
      end
    end
  end.call(lat)
end
end

helpers

def cons(a, b)
b.unshift a
end

def yComb
lambda { |f|
  f[f]
}.call(
  lambda { |f| yield lambda { |x| f[f][x] } }
)
end

Beware Herd Thinking in Design Patterns

I was reading Object Design a few months back and came upon an example illustrating Double Dispatch. The example was showing a simple way to model Rock, Paper, Scissors. Here is the code translated to Ruby from Java:

class Rock
 def beats?(obj)
   obj.loses_to_rock?
 end

 def loses_to_rock?; false; end
 def loses_to_paper?; true; end
 def loses_to_scissors?; false; end
end

class Paper
 def beats?(obj)
   obj.loses_to_paper?
 end

 def loses_to_rock?; false; end
 def loses_to_paper?; false; end
 def loses_to_scissors?; true; end
end

class Scissors
 def beats?(obj)
   obj.loses_to_scissors?
 end

 def loses_to_rock?; true; end
 def loses_to_paper?; false; end
 def loses_to_scissors?; false; end
end

Programmers with some experience with metaprogramming may instinctively feel uneasy with this code. I mean, it looks like a pattern. And we know that if we wished to extend the game, then we're obligated to add another boxy class with all of those silly `loses_to...` methods.

Here's a much better way:

# this makes me happy :)
class Piece
  class << self
   def beats(*args)
     class_eval do
       define_method(:beats) do
         args.map { |s| Object.const_get(s.to_s.capitalize) }
       end
     end
   end
 end

 def beats?(opp)
   beats.include? opp.class
 end
end

class Rock < Piece
 beats :scissors
end

class Scissors < Piece
 beats :paper
end

class Paper < Piece
 beats :rock
end

In this way, it is trivial to extend the game:

class JamesWhiteman < Piece
 beats :paper, :scissors, :rock
end

# ok, let me instantiate myself...
james_whiteman = JamesWhiteman.new

# and time to start kicking some ass :)
james_whiteman.beats? Rock.new
=> TRUE

james_whiteman.beats? Paper.new
=> TRUE

james_whiteman.beats? Scissors.new
=> TRUE

Meta Programming 101: A Compression Macro

Here is another small (and hopefully instructive) example I came up with to help you grok meta programming. Any subclass of Bar will have a `compress` class method (aka ruby-style macro).

require 'zlib'

class Bar
  class << self
    def compress(*args)
      args.each do |id|
        module_eval <<-"end;"
          alias_method :__#{id.to_i}__, :#{id.to_s}
          private :__#{id.to_i}__
          def #{id.to_s}(*args, &block)
            Zlib::Deflate.deflate(__#{id.to_i}__(*args, &block), Zlib::BEST_COMPRESSION )
          end
        end;
      end
      nil # let's not return anything
    end
  end
end


class Foo < Bar
  
  def output
    ('a'..'z').to_a.join * 500
  end
  compress :output
    
end

Quicksort in PHP

Tonight I decided to write a Quicksort in PHP. Thank you Zend for create_function because Ruby has made me hopelessly closure dependent. Once I figured out that array_filter could take a lambda instead of a string I knew that it was on.

<?php
function qsort($l) {
  if (is_array($l) && empty($l)) { return array(); }
  list($car, $cdr) = array(array_shift($l), $l);
  return array_merge(
     qsort(array_filter($cdr, create_function('$e', "return \$e <= $car;"))), 
     array($car), 
     qsort(array_filter($cdr, create_function('$e', "return \$e > $car;")))
  );
}
?>

And I was pleased to see that I could, more or less, emulate Ruby's select/find iterator:

// Ruby
cdr.select { |x| x <= car }

/* in PHP */
<?php array_filter($cdr, create_function('$e', "return \$e <= $car;")); ?>

"But is it fast, Jim", you ask with baited breath. No. It could hardly be slower. PEAR has a nice little benchmarking package that will bring this point home (each sorting an array of 1000 random integers):

My Dumb Quicksort
time: 0.3607

PHP's built in sort
time: 0.0015

It isn't as nearly ugly as you'd expect it to be -- and still much easier to read than it would have been without the use of create_function. I'm always finding that I can do more with PHP than I thought I could.

Creating Random Usernames and Passwords with Ruby

NUMBER_OF_USERNAME_PASSWORDS = 10_000
LENGTH = 8

passwords = Hash[ 
  *Array.new(NUMBER_OF_USERNAME_PASSWORDS) do
    proc { |n| Array.new(n) { (97..122).to_a[ rand(26) ].chr }.join }[LENGTH]
  end
]

In this case, the variable passwords will be a hash of { :usernames => :passwords }.

PHP: A Language Full of Ceremony

Porting some of the previous post into PHP:

<?php
class SillyReverse {
 
 private $string;
 

 function __construct($s) {
  $this->string = $s;
 }
 

 function reverse() {
  return $this->reverse_helper($this->string);
 }
 

 private function reverse_helper($string) {
  if ($this->is_midpoint($string)) {
    return $string;
  } else {
    return $this->last_char($string) . 
           $this->reverse_helper($this->middle($string)) . 
           $this->first_char($string); 
  }
 }
 

 private function is_midpoint($string) {
  return strlen($string) == 0 || strlen($string) == 1;
 }
 

 private function last_char($string) {
  return $string[strlen($string)-1];
 }
 

 private function first_char($string) {
  return substr($string, 0, 1);
 }
 

 private function middle($string) {
  return substr($string, 1, -1);
 }
}


$sr = new SillyReverse('hello, world');
print $sr->reverse() . "\n";

?>

Reversing Strings in Ruby: Two Different Kinds

Admittedly, reversing a string in Ruby is as easy as string.reverse. But for the sake of code katas (and preparing for Ruby job interviews) it's sometimes worth the effort to roll your own. Here are two different ways that I came up with.

A smarter way (while not using C)

class String
  
  # reversing in place
  def reverse_i!
    (0...midpoint).each do |i| 
      self[i], self[-(i+1)] = self[-(i+1)], self[i] 
    end 
    
    self
  end
  
  private 
  
  def midpoint
    self.size / 2
  end
  
end

A very pretty way (but would get you fired!)

def reverse(s)
  if s.midpoint?
    s
  else
    s.last + reverse(s.middle) + s.first
  end
end

### helpers ###
def midpoint?
  self.size == 0 or
    self.size == 1
end

def first; self[0].chr end

def middle; self[1...-1] end

def last; self[-1].chr end

More Hitchens

"The essence of the independent mind lies not in what it thinks, but in how it thinks."

-- Christopher Hitchens

A Y-Combinator for Josh Susser

A couple of days ago Josh Susser posted a very attractive recursive lambda in his blog.

A couple of people in the comments said that a recursive lambda is a prime opportunity to use the Y-combinator.

In Scheme? Sure. In a Rails application? I don't think so.

While I think that functional programing represents a more powerful programming paradigm than what's typically used in Ruby, I think it's a mistake to parade Ruby around like it's Lisp (or Haskell, or ML, etc). It can 'do' Lisp (sans macros) but it's so much better at being itself.

Anyhoo, I whipped this thing up just to see what it would look like. I started writing in Ruby 1.9, but for some reason, when you coerce a lambda into a block (i.e function(& my_lambda)) it turns hash iterations (i.e |key,value|) into arrays ( |array| ). So I did it in 1.8 -- for which lambda syntax sucks. So I'm going to use &lambda instead of lambda 'cuz it just looks good.

class ApplicationController < ActionController::Base
  before_filter { |controller| controller.params.each(&λ { |le|
      λ {|f|
        f[f]
      }.call( λ {|f| le.call( λ { f[f] }) })
    }.call(λ {|m|
            λ {|k,v|
              case v
                when String then v.remove_accents!
                when Hash   then v.each(&m.call)
              end
             }
        }))
   }
end

Well...it is completely anonymous now. Are we having fun yet? Obviously, there are more readable ways to use Y but none of them result in anything nicer than what Josh wrote. This is basically a long way of saying avoid overly complicated code. You can never justify masturbatory programming because you're using strict FP -- especially in Ruby and even more so in Rails.

Smalltalk Best Practice Patterns

"Coding is where your fuzzy comfortable ideas awaken in the harsh dawn of reality."

-- Kent Beck

Testing #new in Ruby with RSpec and Mocha

Here's a trick I came up with:

class Foo
  def initialize
    my_nifty_init_method
  end
end

describe Foo, "#new" do
  it "should call my_nifty_init_method" do
    f = Foo.allocate
    f.expects(:my_nifty_init_method).returns(true)
    f.send(:initialize)
  end
end

Class#allocate creates an object without calling initialize. Pretty cool stuff.

Programming Erlang

Just got the PDF to Programing Erlang a few weeks ago. Erlang is a functional language, and, from what I can tell, is even more terse than Scheme. The book has a very nice and very compact Quicksort in the second chapter. Here's my version in Ruby:

def qsort(l) 
   return [] if l.empty?
   car, *cdr = l
   qsort(cdr.select { |x| x <= car }) +
     [car] +
     qsort(cdr.select { |x| x > car })
end

Not nearly as nice as the one in the book, but still pretty small. I borrowed 'car' and 'cdr' from the Little Schemer...I suppose 'first' and 'rest' would have been more readable. The Erlang book users 'Pivot' and 'L'. All in all, a very good book so far.