[QUIZ] Port a Library (#64)

9 views
Skip to first unread message

Ruby Quiz

unread,
Jan 27, 2006, 8:52:11 AM1/27/06
to
The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Twice this week, I've gone looking for the Ruby equivalent to a simple Perl
module and had trouble finding what I was after. Both times I've peeked inside
the source and been surprised at how trivial the operations are. "I could port
that in no time," I thought. This quiz is my thinly disguised attempt to pass
my homework on to others. :)

Seriously, this quiz is *not* intended to be a lot of work. Don't underestimate
the power of a simple library. (See the "Rethinking Memoization" thread where
we are trying to improve a very helpful library that is literally 10 lines of
code, in one of the forms presented.)

Given all that, this is a build-it-yourself Ruby Quiz. Most of us are familiar
with another language. Go into their libraries and find something you like,
that is also simple, and port the library to Ruby. (You might want to search
the RAA and RubyForge first, just to make sure someone hasn't done similar work
already.) If a library is over 200 lines, forget it. This one is for the
little guys!

If you'll allow a brief aside here, it can be interesting to consider what the
word "port" means. Obviously, the goal of this is to build a library that does
the same things for Ruby. Don't think that means you should copy every method,
verbatim though. If you don't think a method is needed, leave it out. See a
better way to do something, use your way. Most important though, remember to
Rubyize the interface. It's fine to port your favorite Java library, but Ruby
programmers don't want to call methodsNamedLikeThis(). Watch for chances to use
blocks and jump on them *when they lead to a better experience*. Just remember
the adage, "If it ain't broke, don't fix it."

A few more details: Please tell us what your library does and show an example
of simple usage in your submission email. Be kind to your quiz summarizer. ;)
Also, please credit the original library and author who worked so hard to give
you something cool to play with!

Now, if you have no idea what to port, here are two suggestions. (Please feel
free to post other suggestions to Ruby Talk. These are *not* spoilers!)

File::ReadBackwards

This is a Perl module (by Uri Guttman) for reading a file in reverse,
line-by-line. This can often be helpful for things like log files, where the
interesting information is usually at the end.

Don't worry about the Perl interface on this one, copy Ruby's File instead.
Heck, all I really want is a foreach() iterator. Anything else is extra.

This module is so well commented, you should be able to understand how it works,
even if you aren't familiar with Perl. Here's a link straight to the source:

http://search.cpan.org/src/URI/File-ReadBackwards-1.04/ReadBackwards.pm

WWW::RobotRules

This is another Perl module (by Gisle Aas) and it is actually over the 200 line
limit. Trust me though, it doesn't need to be. :)

The idea here is that many web sites provide a /robots.txt file, telling spider
programs which pages they should not visit. This module gives you a way to
parse these rules and make queries about what you are allowed to visit. You can
learn all about the interface and even the file format of /robots.txt at:

http://search.cpan.org/~gaas/libwww-perl-5.805/lib/WWW/RobotRules.pm


Ross Bamford

unread,
Jan 29, 2006, 10:13:54 AM1/29/06
to
(By my calculations it's gone 48 hours now? Hope so, anyway...)

I did "Ruby Murray" - a port of Johan Lodin's Sub::Curry from Perl. It's
not so useful in Ruby I guess but it's fun and pretty flexible. Below is
the uncommented version, but since I can't sleep when I have
undocumented code I did Rdoc it and make the commented version available
at http://roscopeco.co.uk/code/ruby-quiz-entries/64/ .

There's also a translation of the Sub::Curry cookbook I used to drive
development a bit. The original Sub::Curry can be found at
http://search.cpan.org/~lodin/Sub-Curry-0.8/lib/Sub/Curry.pm and the
cookbook is at
http://search.cpan.org/~lodin/Sub-Curry-0.8/lib/Sub/Curry/Cookbook.pod .

Ruby Murray is about a hundred lines for the main Curry class, another
forty or so for convenience methods and the like, and about 70 lines of
tests. It could be smaller but I like (reasonably) readable code and the
TDD makes it more verbose I guess...

Here's a couple of quick examples. See the cookbook and tests (either
below or in the Rdoc linked above if formatting is broken) for more.

Just curry a method:

c = "string".method(:slice).curry(Curry::HOLE,2)
c.call(0)
# => "st"
c.call(2)
# => "ri"

Swallow arguments:

curry = lambda { |*args| args }.curry(1,Curry::ANTISPICE,3)
curry.call(2,5)
# => [1,3,5]

Do some mad curry to curry stuff:

curry = [10,20,30].method(:inject).curry(Curry::HOLE)
curry.call(0) { |s,i| s + i }
# => 60

mult_sum = lambda do |sum, i, mult|
sum + (i * mult)
end.curry(Curry::BLACKHOLE, Curry::HOLE)

double_sum = mult_sum.new(Curry::BLACKHOLE, Curry::WHITEHOLE, 2)
triple_sum = mult_sum.new(Curry::BLACKHOLE, Curry::WHITEHOLE, 3)

curry.call(0, &double_sum)
# => 120

curry.call(0, &triple_sum)
# => 180

Obviously it's completely different from the Perl original under the
hood but I tried to make it familiar enough while making good use of
Ruby.

There's a few other ideas I'd like to have tried but I didn't want to
get too far into it ;). One advantage this version has over Perl's is
that it's easy to make custom Spice argument types (HOLE, BLACKHOLE,
etc) so maybe there's some scope for hacking around in there...

=====[CURRY.RB]=====
require 'singleton'

class Curry
WHITEHOLE = Object.new
ANTIHOLE = Object.new
def WHITEHOLE.inspect #:nodoc:
"<WHITEHOLE>"
end
def ANTIHOLE.inspect #:nodoc:
"<ANTIHOLE>"
end

class SpiceArg
def initialize(name)
@name = name
end
def spice_arg(args_remain)
raise NoMethodError, "Abstract method"
end
def inspect
"<#{@name}>"
end
end

class HoleArg < SpiceArg #:nodoc: all
include Singleton
def initialize; super("HOLE"); end
def spice_arg(args_remain)
a = args_remain.shift
if a == ANTIHOLE
[]
else
[a]
end
end
end

class BlackHoleArg < SpiceArg #:nodoc: all
include Singleton
def initialize; super("BLACKHOLE"); end
def spice_arg(args_remain)
if idx = args_remain.index(WHITEHOLE)
args_remain.slice!(0..idx)[0..-2]
else
args_remain.slice!(0..args_remain.length)
end
end
end

class AntiSpiceArg < SpiceArg #:nodoc: all
include Singleton
def initialize; super("ANTISPICE"); end
def spice_arg(args_remain)
args_remain.shift
[]
end
end

HOLE = HoleArg.instance
BLACKHOLE = BlackHoleArg.instance
ANTISPICE = AntiSpiceArg.instance

attr_reader :spice
attr_reader :uncurried

def initialize(*spice, &block)
block = block || (spice.shift if spice.first.respond_to?(:call))
raise ArgumentError, "No block supplied" unless block
@spice, @uncurried = spice, block
end

def call(*args, &blk)
@uncurried.call(*call_spice(args), &blk)
end

# This would be an alias, but it's documented along with call and
# I couldn't :nodoc: an alias - how do we do that ?
def [](*args) # :nodoc:
call(*args)
end

def new(*spice)
Curry.new(*merge_spice(spice), &@uncurried)
end

def to_proc
@extern_proc ||= method(:call).to_proc
end

private

def merge_spice(spice)
largs = spice.dup

res = @spice.inject([]) do |res, sparg|
if sparg.is_a?(SpiceArg) && !largs.empty?
res + sparg.spice_arg(largs)
else
res << sparg
end
end

res + largs
end

def call_spice(args)
sp = merge_spice(args)
sp.map do |a|
if a.is_a? SpiceArg
nil
else
a
end
end
end
end

# Undocumented alias for Perl familiarity
module Sub #:nodoc: all
Curry = ::Curry
end

module Curriable
def curry(*spice)
Curry.new(self, *spice)
end
end

unless defined? NO_CORE_CURRY
NO_CORE_CURRY = (ENV['NO_CORE_CURRY'] || $SAFE > 3)
end

unless NO_CORE_CURRY
class Proc
include Curriable
end

class Method
include Curriable
end
end

if $0 == __FILE__ || (TEST_CURRY if defined? TEST_CURRY)
require 'test/unit'

class TestCurry < Test::Unit::TestCase
def test_fixed_args
curry = Curry.new(1,2,3) { |a,b,c| [a,b,c] }
assert_equal [1,2,3], curry.call
end

def test_fixed_array_args
curry = Curry.new([1],[2,3]) { |*args| args }
assert_equal [[1],[2,3]], curry.call
end

def test_hole
curry = Curry.new(1,Curry::HOLE,3) { |a,b,c| [a,b,c] }
assert_equal [1,nil,3], curry.call
assert_equal [1,2,3], curry.call(2)

curry = Curry.new(1,Curry::HOLE,3,Curry::HOLE) { |*args| args }
assert_equal [1,2,3,4], curry.call(2,4)
assert_equal [1,2,3,4,5,6], curry.call(2,4,5,6)
assert_equal [1,[2,'two'],3,[4,0],[[14]]],
curry.call([2,'two'],[4,0],[[14]])

end

def test_antihole
curry = Curry.new(1,Curry::HOLE,3) { |*args| args }
assert_equal [1,3], curry.call(Curry::ANTIHOLE)

curry = Curry.new(1,Curry::HOLE,3,Curry::HOLE,4) { |*args| args }
assert_equal [1,2,3,4,5], curry.call(2,Curry::ANTIHOLE,5)
end

def test_antispice
curry = Curry.new(1,Curry::ANTISPICE,3,Curry::HOLE,4) { |*args|
args }
assert_equal [1,3,4,5], curry.call(2,Curry::ANTIHOLE,5)
end

def test_black_hole
curry = Curry.new(1,Curry::BLACKHOLE) { |*args| args }
assert_equal [1,2,3], curry.call(2,3)

curry = Curry.new(1,Curry::BLACKHOLE,3,4) { |*args| args }
assert_equal [1,2,10,3,4], curry.call(2,10)
end

def test_white_hole
curry = Curry.new(1,Curry::BLACKHOLE,3,Curry::HOLE,5) { |*args|
args }
assert_equal [1,2,3,7,5,8,9], curry.call(2,Curry::WHITEHOLE,7,8,9)
assert_equal [1,10,20,3,nil,5], curry.call(10,20,Curry::WHITEHOLE)
assert_equal [1,10,20,25,3,4,5],
curry.call(10,20,25,Curry::WHITEHOLE,4)

curry =
Curry.new(1,Curry::BLACKHOLE,6,Curry::HOLE,3,4,Curry::BLACKHOLE,5) { |
*args| args }
assert_equal [1,10,20,25,6,40,3,4,50,60,5],
curry.call(10,20,25,Curry::WHITEHOLE,40,50,60)
end

def test_curry_from_curry
curry =
Curry.new(1,Curry::BLACKHOLE,6,Curry::HOLE,3,4,Curry::BLACKHOLE,5) { |
*args| args }
curry = curry.new(Curry::HOLE,Curry::WHITEHOLE,8,9,10)
assert_equal [1,Curry::HOLE,6,8,3,4,9,10,5], curry.spice

curry = curry.new(Curry::HOLE, 4, Curry::BLACKHOLE)
assert_equal [1,Curry::HOLE,6,8,3,4,9,10,5,4,Curry::BLACKHOLE],
curry.spice

curry = curry.new(Curry::ANTIHOLE)
assert_equal [1,6,8,3,4,9,10,5,4,Curry::BLACKHOLE], curry.spice

curry = curry.new(3,Curry::BLACKHOLE,Curry::WHITEHOLE,0)
assert_equal [1,6,8,3,4,9,10,5,4,3,Curry::BLACKHOLE,0],
curry.spice
assert_equal [1,6,8,3,4,9,10,5,4,3,2,1,0], curry.call(2,1)
end

def test_cant_block_to_curried_block
a = Curry.new(1,2) { |*args| args }

assert_equal [1,2,3], a.call(3) { |b| }
end

def test_curry_proc
a = [1,2,3,4,5]
c = Curry.new(*a) { |*args| args * 2 }
assert_equal [1,2,3,4,5,1,2,3,4,5], c.call

if NO_CORE_CURRY
warn "Skipping Proc extension test"
else
c = lambda { |*args| args * 2 }.curry(*a)
assert_equal [1,2,3,4,5,1,2,3,4,5], c.call
end
end

def test_curry_method
a = [1,2,3,4,5]
injsum = Curry.new(a.method(:inject),0)
assert_equal 15, injsum.call { |s,i| s + i }

if NO_CORE_CURRY
warn "Skipping Method extension test"
else
injsum = a.method(:inject).curry(0)
assert_equal 15, injsum.call { |s,i| s + i }
end
end

def test_curry_to_proc
curry = Curry.new(Curry::HOLE, Curry::HOLE, 'thou') { |ary,i,msg|
ary << "#{i} #{msg}" }
assert_equal ["1 thou", "2 thou", "3 thou"],
[1,2,3].inject([],&curry)
end

def test_alt_bits
curry = Curry.new(Curry::BLACKHOLE, 'too', 'true') { |one, two,
*rest| [one, two, rest] }
assert_equal [1,2,['too','true']], curry[1,2]
end

def test_perlish
s = "str"
s = Sub::Curry.new(s.method(:+), "ing")
assert_equal "string", s.call
end
end

if ARGV.member?('--doc') || !File.exist?('doc')
ARGV.reject! { |a| a == '--doc' }
system("rdoc #{__FILE__} #{'currybook.rdoc' if
File.exists?('currybook.rdoc')} --main Curry")
end
end

__END__

--
Ross Bamford - ro...@roscopeco.REMOVE.co.uk

Daniel Berger

unread,
Jan 29, 2006, 10:49:33 AM1/29/06
to
Ruby Quiz wrote:

<snip>

>
> Now, if you have no idea what to port, here are two suggestions. (Please feel
> free to post other suggestions to Ruby Talk. These are *not* spoilers!)
>
> File::ReadBackwards

See ruby-talk:13185 and the following discussion. I was such a noob
then.

Regards,

Dan

James Edward Gray II

unread,
Jan 29, 2006, 11:23:56 AM1/29/06
to
On Jan 27, 2006, at 7:52 AM, Ruby Quiz wrote:

> Seriously, this quiz is *not* intended to be a lot of work.

I just know people aren't going to believe me on this, so here's my
attempt to put my code where my mouth is. This is my port of
File::ReadBackwards. Translating the heart of the algorithm took me
well under an hour, though I did spend a bit more time adding
interface methods and documentation.

James Edward Gray II

#!/usr/local/bin/ruby -w

# elif.rb
#
# Created by James Edward Gray II on 2006-01-28.
# Copyright 2006 Gray Productions. All rights reserved.

#
# A File-like object for reading lines from a disk file in reverse
order. See
# Elif::new and Elif#gets for details. All other methods are just
interface
# conveniences.
#
# Based on Perl's File::ReadBackwards module, by Uri Guttman.
#
class Elif
# The size of the reads we will use to add to the line buffer.
MAX_READ_SIZE = 1 << 10 # 1024

# Works just line File::foreach, save that the lines come in
reverse order.
def self.foreach( name, sep_string = $/ )
open(name) do |file|
while line = file.gets(sep_string)
yield line
end
end
end

# Works just line File::open.
def self.open( *args )
file = new(*args)
if block_given?
begin
yield file
ensure
file.close
end
else
file
end
end

#
# Works just line File::readlines, save that line Array will be in
# reverse order.
#
def self.readlines( name, sep_string = $/ )
open(name) { |file| file.readlines(sep_string) }
end

#
# The first half of the Elif algorithm (to read file lines in
reverse order).
# This creates a new Elif object, shifts the read pointer to the
end of the
# file, and prepares a buffer to hold read lines until they can be
returned.
# This method also sets the <tt>@read_size</tt> to the remainer of
File#size
# and +MAX_READ_SIZE+ for the first read.
#
# Technically +args+ are delegated straight to File#new, but you
must open the
# File object for reading for it to work with this algorithm.
#
def initialize( *args )
# Delegate to File::new and move to the end of the file.
@file = File.new(*args)
@file.seek(0, IO::SEEK_END)

# Record where we are.
@current_pos = @file.pos

# Get the size of the next of the first read, the dangling bit
of the file.
@read_size = @file.pos % MAX_READ_SIZE
@read_size = MAX_READ_SIZE if @read_size.zero?

# A buffer to hold lines read, but not yet returned.
@line_buffer = Array.new
end

#
# The second half on the Elif algorthim (see Elif::new). This
method returns
# the next line of the File, working from the end to the beginning
in reverse
# line order.
#
# It works by moving the file pointer backwords +MAX_READ_SIZE+ at
a time,
# storing seen lines in <tt>@line_buffer</tt>. Once the buffer
contains at
# least two lines (ensuring we have seen on full line) or the file
pointer
# reaches the head of the File, the last line from the buffer is
returned.
# When the buffer is exhausted, this will throw +nil+ (from the
empty Array).
#
def gets( sep_string = $/ )
#
# If we have more than one line in the buffer or we have reached
the
# beginning of the file, send the last line in the buffer to the
caller.
# (This may be +nil+, if the buffer has been exhausted.)
#
return @line_buffer.pop if @line_buffer.size > 2 or
@current_pos.zero?

#
# If we made it this far, we need to read more data to try and
find the
# beginning of a line or the beginning of the file. Move the
file pointer
# back a step, to give us new bytes to read.
#
@current_pos -= @read_size
@file.seek(@current_pos, IO::SEEK_SET)

#
# Read more bytes and prepend them to the first (likely partial)
line in the
# buffer.
#
@line_buffer[0] = "#{@file.read(@read_size)}#{@line_buffer[0]}"
@read_size = MAX_READ_SIZE # Set a size for the next read.

#
# Divide the first line of the buffer based on +sep_string+ and
#flatten!
# those new lines into the buffer.
#
@line_buffer[0] = @line_buffer[0].scan(/.*?#{Regexp.escape
(sep_string)}|.+/)
@line_buffer.flatten!

# We have move data now, so try again to read a line...
gets(sep_string)
end

# Works just line File#each, save that the lines come in reverse
order.
def each( sep_string = $/ )
while line = gets(sep_string)
yield line
end
end
alias_method :each_line, :each # Works just like File#each_line.
include Enumerable # Support all the standard iterators.

# Works just line File#readline, save that the lines come in
reverse order.
def readline( sep_string = $/ )
gets(sep_string) || raise(EOFError, "end of file reached")
end

#
# Works just line File#readlines, save that line Array will be in
# reverse order.
#
def readlines( sep_string = $/ )
lines = Array.new
while line = gets(sep_string)
lines << line
end
lines
end

# Works just line File#close.
def close
@file.close
end
end

Matthew Moss

unread,
Jan 30, 2006, 11:36:07 AM1/30/06
to
There aren't any particular libraries I've used anytime recently...
all my work is in-house code. But I took a quick glance over CPAN for
something relatively small and simple... the latter because I stopped
coding in Perl years ago and don't remember all the syntax very well,
especially the stuff that has been added for objects.

In any case, I found a simple library called Trampoline by Steven
Lembark which allows you to create an object but delay actual
construction... which is useful to have something with expensive
construction cost ready to go but not actually constructed until used.

Below I provide a really basic implementation that is probably not
rock-solid and could probably be done better ... I'm still such a
n00b, especially when it comes to metaclasses (or eigenclasses, or
whatever they want to be called this week). It also doesn't do
everything the Perl lib did, just what I found useful and could
understand.

Anyway, here's the code (trampoline.rb), with a couple of use examples
at the bottom.

module Trampoline
# Instance methods
class Bounce
def initialize(cons, klass, *args)
@klass, @cons, @args = klass, cons, args
end

def method_missing(method, *args)
@obj = @klass.send(@cons, *@args) unless @obj
@obj.send(method, *args)
end
end

# Class methods
class << Bounce
alias_method :old_new, :new

def new(*args)
old_new(:new, *args)
end

def method_missing(method, *args)
old_new(method, *args)
end
end
end

And now, example use. Obviously, this class is not in need of delayed
construction; just using it as an example.

require 'trampoline'
class Logger
def initialize(prefix)
puts 'Constructing Logger...'
@prefix = prefix
end

def Logger.make(prefix)
Logger.new(prefix)
end

def log(msg)
puts "#{@prefix}: #{msg}"
end
end

puts "start"
errors = Trampoline::Bounce.new(Logger, 'ERROR')
puts "made bouncer, about to log message"
errors.log('Hello, world!')
puts "about to log second message"
errors.log('Goodbye, world!')
puts "message logged"

# This is really the same, but eventually calls Logger.make to construct.
puts "start"
warns = Trampoline::Bounce.make(Logger, 'WARNING')
puts "made bouncer, about to log message"
warns.log('Hello, world!')
puts "about to log second message"
warns.log('Goodbye, world!')
puts "message logged"


Output from the example code:

start
made bouncer, about to log message
Constructing Logger...
ERROR: Hello, world!
about to log second message
ERROR: Goodbye, world!
message logged
start
made bouncer, about to log message
Constructing Logger...
WARNING: Hello, world!
about to log second message
WARNING: Goodbye, world!
message logged


amrangaye

unread,
Jan 30, 2006, 11:52:40 AM1/30/06
to
Hello.

This is my first rubyquiz, and I am still learning Ruby. I decided to
go with something simple but fun. So I did a search on the CPAN (I've
used Perl before) for the Acme modules, and chose Acme::Bleach
(http://search.cpan.org/~dconway/Acme-Bleach-1.12/lib/Acme/Bleach.pm)
to implement. I couldn't find a Ruby version on either RAA or
rubyforge.

Acme::Bleach is a module by Damian Conway, and it literally bleaches
your program, whilst still leaving it in a runnable state. It's a
really cool little module, and I stuck as close to the original as
possible - even using nearly the same method names. Here it is in its
entirety. Any suggestions, criticisms, etc. are highly welcome.


#Ruby port of Acme::Bleach - by Amran Gaye
#You can use this by doing an "include 'Bleach' " at the top of your
program

$tie="\t"*8

def whiten(laundry)
#Change laundry to binary 1s and 0s...
#then change those to tab and space characters. Finally add newlines
after every 9th character
result = laundry.unpack('b*').to_s.tr('01',"
\t").gsub(/(.{9})/,"\\1\n")
return $tie + result #Add a tie to the washed shirt, and
return it
end

def brighten(laundry)
#Does the opposite of whiten
laundry.sub!(/\t{8}/,'') #Remove tie
laundry.tr!("\n",'') #Remove newlines
laundry.tr(" \t",'01').to_a.pack('b*') #Change spaces and tabs to 0s
and 1s, then repack them as binary
end


def dirty?(laundry) #Laundry is dirty only if it contains
non-space characters
laundry =~ /\S/
end

def proper?(laundry) #shirt is proper if it contains a
tie
laundry =~ /^#$tie/
end


shirt = IO.readlines($0).to_s #Read in current program
shirt.sub!("require 'Bleach'",'') #Remove require line

if(not dirty?(shirt) and proper?(shirt))
eval brighten(shirt)
else
file = File.new($0,"w")
file.puts("require 'Bleach'")
file.puts(whiten(shirt))
file.close
end

amrangaye

unread,
Jan 30, 2006, 4:21:01 PM1/30/06
to
Soon after I posted this, I saw Rubyquiz #34 (Whiteout) and - much to
my chagrin - it was the same problem! :( Seems I arrived too late to
the party. Still, I hope someone found it interesting.

James Edward Gray II

unread,
Jan 31, 2006, 9:40:21 AM1/31/06
to
On Jan 29, 2006, at 10:23 AM, James Edward Gray II wrote:

> This is my port of File::ReadBackwards.

I just noticed that everyone provided sample usage (just as I asked
them too), but me! Egad. Here's Elif at work:

$ cat sample_data.txt
This is line one.
This is line two.
This is line three.
..
$ ruby -r elif -e 'puts Elif.readlines(ARGV.first)' sample_data.txt
..
This is line three.
This is line two.
This is line one.
$ ruby -r elif -e 'Elif.foreach(ARGV.first) { |line| puts line if
line =~ /t[a-z]+.$/ }' sample_data.txt
This is line three.
This is line two.

James Edward Gray II


James Edward Gray II

unread,
Jan 31, 2006, 12:18:27 PM1/31/06
to
On Jan 29, 2006, at 10:23 AM, James Edward Gray II wrote:

> This is my port of File::ReadBackwards.

I haven't had time to document it yet, but here is the other port of
WWW::RobotRules. You use it something like this:

#!/usr/local/bin/ruby -w

require "robot_rules"
require "open-uri"

rules = RobotRules.new("RubyQuizBrowser 1.0")
robots_url = "http://pragmaticprogrammer.com/robots.txt"

open(robots_url) do |url|
data = url.read

puts "/robots.txt:"
puts data
puts

rules.parse(robots_url, data)
end

puts "URL tests:"
%w{ http://pragmaticprogrammer.com/images/dave.jpg
http://pragmaticprogrammer.com/imagination }.each do |test|
puts "rules.allowed?( #{test.inspect} )"
puts rules.allowed?(test)
end

__END__

Which prints:

/robots.txt:
User-agent: *
Disallow: images

URL tests:
rules.allowed?( "http://pragmaticprogrammer.com/images/dave.jpg" )
false
rules.allowed?( "http://pragmaticprogrammer.com/imagination" )
true

James Edward Gray II

#!/usr/local/bin/ruby -w

# robot_rules.rb
#
# Created by James Edward Gray II on 2006-01-31.


# Copyright 2006 Gray Productions. All rights reserved.

require "uri"

# Based on Perl's WWW::RobotRules module, by Gisle Aas.
class RobotRules
def initialize( user_agent )
@user_agent = user_agent.scan(/\S+/).first.sub(%r{/.*},
"").downcase
@rules = Hash.new { |rules, rule| rules[rule] = Array.new }
end

def parse( text_uri, robots_data )
uri = URI.parse(text_uri)
location = "#{uri.host}:#{uri.port}"
@rules.delete(location)

rules = robots_data.split(/[\015\012]+/).
map { |rule| rule.sub(/\s*#.*$/, "") }
anon_rules = Array.new
my_rules = Array.new
current = anon_rules
rules.each do |rule|
case rule
when /^\s*User-Agent\s*:\s*(.+?)\s*$/i
break unless my_rules.empty?

current = if $1 == "*"
anon_rules
elsif $1.downcase.index(@user_agent)
my_rules
else
nil
end
when /^\s*Disallow\s*:\s*(.*?)\s*$/i
next if current.nil?

if $1.empty?
current << nil
else
disallow = URI.parse($1)

next unless disallow.scheme.nil? or disallow.scheme ==
uri.scheme
next unless disallow.port.nil? or disallow.port == uri.port
next unless disallow.host.nil? or
disallow.host.downcase == uri.host.downcase

disallow = disallow.path
disallow = "/" if disallow.empty?
disallow = "/#{disallow}" unless disallow[0] == ?/

current << disallow
end
end
end

@rules[location] = if my_rules.empty?
anon_rules.compact
else
my_rules.compact
end
end

def allowed?( text_uri )
uri = URI.parse(text_uri)
location = "#{uri.host}:#{uri.port}"
path = uri.path

return true unless %w{http https}.include?(uri.scheme)

not @rules[location].any? { |rule| path.index(rule) == 0 }
end
end

Adam Shelly

unread,
Jan 31, 2006, 5:55:11 PM1/31/06
to
I went browsing in CPAN to find something interesting, and came up
with Algorithm::Merge.
I don't use the perl version, but 3 way merging is something I do
often since we allow concurrent access with our source control at
work.

Merge.rb is a fairly straight port of the perl version. I did change
a callback to a block, and added some symbols in place of numeric
constants. I need to add better documentation, but I wanted to get
this in before it was too late for the summary.

Usage:
original= "Ok,\n this is a test sentence\n which will be edited."
edited ="Ok,\n this is a sample phrase\n which has been edited."
change="Hello World,\n this is a test phrase\n which I edited."

puts "\nSplit by lines\n--------------------"
$;="\n"
Merge::diff3(original.split, edited.split, change.split).each{|l| puts
l.inspect}
puts Merge::merge(original.split, edited.split, change.split)
puts "\nSplit by words\n--------------------"
$;=" "
Merge::diff3(original.split, edited.split, change.split).each{|l| puts
l.inspect}
puts Merge::merge(original.split, edited.split,
change.split){|conflicts|
["<<"]+conflicts[1]+["|"]+conflicts[2]+[">>"]}.join(' ')

yields:
Split by lines
--------------------
["r", "Ok,", "Ok,", "Hello World,"]
["c", " this is a test sentence", " this is a sample phrase", " this
is a test phrase"]
["c", " which will be edited.", " which has been edited.", " which I edited"]
Hello World,
<!-- ------ START CONFLICT ------ -->
this is a sample phrase
which has been edited.
<!-- ---------------------------- -->
this is a test phrase
which I edited.
<!-- ------ END CONFLICT ------ -->}

Split by words
--------------------
["r", "Ok,", "Ok,", "Hello"]
["r", nil, nil, "World,"]
["u", "this", "this", "this"]
["u", "is", "is", "is"]
["u", "a", "a", "a"]
["l", "test", "sample", "test"]
["o", "sentence", "phrase", "phrase"]
["u", "which", "which", "which"]
["c", "will", "has", "I"]
["c", "be", "been", nil]
["u", "edited.", "edited.", "edited."]
Hello World, this is a sample phrase which << has been | I >> edited.


Bugs:
- Merge::diff3(original,edited, change) - does a character-based diff,
but returns inconsistent results (lines like [u, e, s, e]). I think
this is because the callback_map has some no-ops where it should have
valid callbacks, but it could be due to a porting error. I am still
struggling to completely grok the use of the callback_map, with hopes
of simplifying/clarifying it.

Question:
Can I add to or replace the Perl license with the ruby one?

Source:
---- Merge.rb -----
module Merge

# Module Merge
# Three-way merge and diff
#
# based on perl's Algorithm::Merge
# by James G. Smith, <jsm...@cpan.org>
# Copyright (C) 2003 Texas A&M University. All Rights Reserved.
# This module is free software; you may redistribute it and/or
# modify it under the same terms as Perl itself.
# ported to Ruby
# by Adam Shelly <adam....@gmail.com>


require 'diff/lcs'


# Given references to three lists of items, diff3 performs a
# three-way difference.
# This function returns an array of operations describing how the
# left and right lists differ from the original list. In scalar
# context, this function returns a reference to such an array.
#
# Given the following three lists,
# original: a b c e f h i k
# left: a b d e f g i j k
# right: a b c d e h i j k
#
# merge: a b d e g i j k
#
# we have the following result from diff3:
#
# [ 'u', 'a', 'a', 'a' ],
# [ 'u', 'b', 'b', 'b' ],
# [ 'l', 'c', undef, 'c' ],
# [ 'o', undef, 'd', 'd' ],
# [ 'u', 'e', 'e', 'e' ],
# [ 'r', 'f', 'f', undef ],
# [ 'o', 'h', 'g', 'h' ],
# [ 'u', 'i', 'i', 'i' ],
# [ 'o', undef, 'j', 'j' ],
# [ 'u', 'k', 'k', 'k' ]
#
# The first element in each row is the array with the difference:
# c - conflict (no two are the same)
# l - left is different
# o - original is different
# r - right is different
# u - unchanged
# The next three elements are the lists from the original, left,
# and right arrays respectively that the row refers to (in the synopsis,
#

def Merge::diff3( pivot, doc_a, doc_b)
ret = []

no_change = proc do |args|
ret << ['u', pivot[args[0]], doc_a[args[1]], doc_b[args[2]] ]
end

conflict = proc do |args|
p= pivot[args[0]] if args[0]
a= doc_a[args[1]] if args[1]
b= doc_b[args[2]] if args[2]
ret << ['c', p, a, b]
end

diff_a = proc do |args|
case args.size
when 1
ret << ['o',pivot[args[0]], nil, nil]
when 2
ret << ['o',nil, doc_a[args[0]], doc_b[args[1]]]
when 3
ret << ['o', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
end
end

diff_b = proc do |args|
case args.size
when 1
ret << ['l', nil, doc_a[args[0]], nil]
when 2
ret << ['l', pivot[args[0]], nil, doc_b[args[1]]]
when 3
ret << ['l', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
end
end

diff_c = proc do |args|
case args.size
when 1
ret << ['r', nil, nil, doc_b[args[0]]]
when 2
ret << ['r', pivot[args[0]], doc_a[args[1]], nil]
when 3
ret << ['r', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
end
end

traverse_sequences3(pivot, doc_a, doc_b,
{:NO_CHANGE=>no_change, :CONFLICT=>conflict,
:A_DIFF=> diff_a, :B_DIFF=>diff_b, :C_DIFF=>diff_c}
)
return ret
end


#callbacks for Diff::LCS
class LCS_Traverse_Callbacks
def initialize diffs
@diffs = diffs
end
def [] l,r
@diffs[@left=l]=[]
@diffs[@right=r]=[]
self
end
def match *args
end
def discard_a event
@diffs[@left]<<event.old_position
end
def discard_b event
@diffs[@right]<<event.new_position
end
end


# constants for traverse_sequences
D=nil
AB_A=32
AB_B=16
AC_A=8
AC_C=4
BC_B=2
BC_C=1
CB_B=5 #not used in calculations
CB_C=3 #not used in calculations
@base_doc = {AB_A=>:A,AB_B=>:B,AC_A=>:A,AC_C=>:C,BC_B=>:B,BC_C=>:C}


def Merge::traverse_sequences3(adoc, bdoc, cdoc, callbacks = {})
target_len = [bdoc.size,cdoc.size].min
bc_different_len = (bdoc.size != cdoc.size)
diffs = Hash.new([])


# callbacks#match:: Called when +a+ and +b+ are pointing
# to common elements in +:A+ and +:B+.
# callbacks#discard_a:: Called when +a+ is pointing to an
# element not in +:B+.
# callbacks#discard_b:: Called when +b+ is pointing to an
# element not in +:A+.
# The methods for <tt>callbacks#match</tt>,
<tt>callbacks#discard_a</tt>,
# and <tt>callbacks#discard_b</tt> are invoked with an event comprising
# the action ("=", "+", or "-", respectively), the indicies +ii+ and
# +jj+, and the elements <tt>:A[ii]</tt> and <tt>:B[jj]</tt>. Return
# values are discarded by #traverse_sequences.

ts_callbacks = LCS_Traverse_Callbacks.new(diffs)

Diff::LCS::traverse_sequences(adoc, bdoc, ts_callbacks[AB_A, AB_B])
Diff::LCS::traverse_sequences(adoc, cdoc, ts_callbacks[AC_A,AC_C])

if (bc_different_len)
Diff::LCS::traverse_sequences(cdoc, bdoc, ts_callbacks[CB_C,CB_B])
Diff::LCS::traverse_sequences(bdoc, cdoc, ts_callbacks[BC_B,BC_C])

if diffs[CB_B] != diffs[BC_B] || diffs[CB_C] != diffs[BC_C]
puts "Diff::diff is not symmetric for second and third
sequences - results might not be correct";

#trim to equal lengths and try again
b_len, c_len = bdoc.size, cdoc.size
bdoc_save = bdoc.slice!(target_len..-1)
cdoc_save = cdoc.slice!(target_len..-1)
Diff::LCS::traverse_sequences(bdoc, cdoc, ts_callbacks[BC_B,BC_C])

#mark the trimmed part as different and then restore
diffs[BC_B] += (target_len..b_len).to_a if target_len < b_len
diffs[BC_C] += (target_len..c_len).to_a if target_len < c_len
bdoc.concat bdoc_save
cdoc.concat cdoc_save
end

else # not bc_different_len
Diff::LCS::traverse_sequences(bdoc, cdoc, ts_callbacks[BC_B,BC_C])
end
pos = {:A=>0,:B=>0,:C=>0}
sizes ={:A=>adoc.size, :B=>bdoc.size, :C=>cdoc.size}
matches=[]
noop = proc {}

# Callback_Map is indexed by the sum of AB_A, AB_B, ..., as
indicated by @matches
# this isn't the most efficient, but it's a bit easier to maintain and
# read than if it were broken up into separate arrays
# half the entries are not noop - it would seem then that no
# entries should be noop. I need patterns to figure out what the
# other entries are.

callback_Map = [
[ callbacks[:NO_CHANGE], :A, :B, :C ], # 0 - no matches
[ noop, ], # 1 -
BC_C
[ callbacks[:B_DIFF], :B ], #*2 - BC_B
[ noop, ], # 3 -
BC_B BC_C
[ noop, ], # 4 - AC_C
[ callbacks[:C_DIFF], :C ], # 5 -
AC_C BC_C
[ noop, ], # 6 - AC_C BC_B
[ noop, ], # 7 -
AC_C BC_B BC_C
[ callbacks[:A_DIFF], :A ], # 8 - AC_A
[ noop, ], # 9 - AC_A
BC_C
[ callbacks[:C_DIFF], :A, :B ], # 10 - AC_A BC_B
[ callbacks[:C_DIFF], :A, :B, ], # 11 - AC_A
BC_B BC_C
[ noop, ], # 12 - AC_A AC_C
[ noop, ], # 13 - AC_A
AC_C BC_C
[ callbacks[:C_DIFF], :A, :B, ], # 14 - AC_A AC_C BC_B
[ callbacks[:C_DIFF], :A, :B, :C ], # 15 - AC_A
AC_C BC_B BC_C
[ noop, ], # 16 - AB_B
[ noop, ], # 17 - AB_B
BC_C
[ callbacks[:B_DIFF], :B ], # 18 - AB_B BC_B
[ noop, ], # 19 - AB_B
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 20 - AB_B AC_C
[ noop, ], # 21 - AB_B
AC_C BC_C
[ noop, ], # 22 - AB_B AC_C BC_B
[ callbacks[:CONFLICT], :A, :B, :C ], # 23 - AB_B
AC_C BC_B BC_C
[ callbacks[:B_DIFF], :B ], # 24 - AB_B AC_A
[ noop, ], # 25 - AB_B AC_A
BC_C
[ callbacks[:C_DIFF], :B, :C ], # 26 - AB_B AC_A BC_B
[ noop, ], # 27 - AB_B AC_A
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 28 - AB_B AC_A AC_C
[ noop, ], # 29 - AB_B AC_A
AC_C BC_C
[ noop, ], # 30 - AB_B AC_A AC_C BC_B
[ callbacks[:B_DIFF], :B ], # 31 - AB_B AC_A
AC_C BC_B BC_C
[ callbacks[:NO_CHANGE], :A, :B, :C ], # 32 - AB_A
[ callbacks[:B_DIFF], :A, :C ], # 33 - AB_A
BC_C
[ noop, ], # 34 - AB_A BC_B
[ callbacks[:B_DIFF], :A, :C ], # 35 - AB_A
BC_B BC_C
[ noop, ], # 36 - AB_A AC_C
[ noop, ], # 37 - AB_A
AC_C BC_C
[ noop, ], # 38 - AB_A AC_C BC_B
[ noop, ], # 39 - AB_A
AC_C BC_B BC_C
[ callbacks[:A_DIFF], :A, ], # 40 - AB_A AC_A
[ noop, ], # 41 - AB_A AC_A
BC_C
[ callbacks[:A_DIFF], :A ], # 42 - AB_A AC_A BC_B
[ noop, ], # 43 - AB_A AC_A
BC_B BC_C
[ noop, ], # 44 - AB_A AC_A AC_C
[ callbacks[:C_DIFF], :A, D, :C ], # 45 - AB_A AC_A
AC_C BC_C ##ADS: I think this should be :CONFLICT??
[ noop, ], # 46 - AB_A AC_A AC_C BC_B
[ noop, ], # 47 - AB_A AC_A
AC_C BC_B BC_C
[ noop, ], # 48 - AB_A AB_B
[ callbacks[:B_DIFF], :A, :C ], # 49 - AB_A AB_B
BC_C
[ noop, ], # 50 - AB_A AB_B BC_B
[ callbacks[:B_DIFF], :A, :B, :C ], # 51 - AB_A AB_B
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 52 - AB_A AB_B AC_C
[ noop, ], # 53 - AB_A AB_B
AC_C BC_C
[ noop, ], # 54 - AB_A AB_B AC_C BC_B
[ callbacks[:C_DIFF], :C ], # 55 - AB_A AB_B
AC_C BC_B BC_C
[ callbacks[:B_DIFF], :A, :C ], # 56 - AB_A AB_B AC_A
[ noop, ], # 57 - AB_A AB_B AC_A
BC_C
[ callbacks[:CONFLICT], :A, :B, D ], # 58 - AB_A AB_B AC_A
BC_B ##ADS: I changed this one to :CONFLICT
[ noop, ], # 59 - AB_A AB_B AC_A
BC_B BC_C
[ callbacks[:A_DIFF], :A, :B, :C ], # 60 - AB_A AB_B AC_A AC_C
[ callbacks[:CONFLICT], :A, D, :C ], # 61 - AB_A AB_B AC_A
AC_C BC_C
[ callbacks[:CONFLICT], :A, :B, D ], # 62 - AB_A AB_B AC_A AC_C BC_B
[ callbacks[:CONFLICT], :A, :B, :C ], # 63 - AB_A AB_B AC_A
AC_C BC_B BC_C
]

#while there is something to work with
while diffs.values.find{|e|e.size>0} && [:A,:B,:C].find{|n|pos[n]<sizes[n]}


#find all the differences at the current position of each doc
matchset=[:A,:B,:C].inject([]) do |ms,i|
ms+diffs.find_all {|k,v|@base_doc[k]==i && v[0]==pos[i]}
end
callback_num=matchset.uniq.inject(0){|cb,val| (cb|val[0])}
callback = callback_Map[callback_num]
args = callback[1..-1]
callback[0].call(args.map{|ar| ar&&pos[ar]})


args.each do |n|
pos[n]+=1 if n
case n
when :A
diffs[AB_A].shift while diffs[AB_A][0] && ( diffs[AB_A][0]
< pos[n] )
diffs[AC_A].shift while diffs[AC_A][0] && ( diffs[AC_A][0]
< pos[n] )
when :B
diffs[AB_B].shift while diffs[AB_B][0] && ( diffs[AB_B][0]
< pos[n] )
diffs[BC_B].shift while diffs[BC_B][0] && ( diffs[BC_B][0]
< pos[n] )
when :C
diffs[AC_C].shift while diffs[AC_C][0] && ( diffs[AC_C][0]
< pos[n] )
diffs[BC_C].shift while diffs[BC_C][0] && ( diffs[BC_C][0]
< pos[n] )
end
end #args.each
#raise "args empty" if args.empty? ##ADS: args.empty? is true
if the callback was a no-op. I don't think that should happen.
break if args.empty?
end

#this part takes care of the leftovers
bits={:A=>4,:B=>2,:C=>1}
while [:A,:B,:C].find{|n|pos[n]<sizes[n]}
match = 0
args=[]
[:A,:B,:C].each do |i|
if pos[i]<sizes[i]
match|=bits[i]
args << pos[i]
pos[i]+=1
end
end
switch = [0,5,24,17,34,8,10,0][match] #ADS: I totally don't
understand how these callbacks were chosen
callback_Map[switch][0].call(*args) if callback_Map[switch][0]
end
end

# Given references to three lists of items, merge performs a three-way
# merge. The merge function uses the diff3 function to do most of
# the work.
#
# The optional block parameter is called for conflicts. It should
# accept an array of 3 arrays
# The first array holds a list of elements from the original list.
# The second array has a list of elements from the left list.
# The last array holds a list of elements from the right list.
# The block should return a list of elements to place in the merged
# list in place of the conflict.
#
# The default conflict handler returns:
# ["<!-- ------ START CONFLICT ------ -->",
# args[1],
# "<!-- ---------------------------- -->",
# args[2],
# "<!-- ------ END CONFLICT ------ -->}"]

def Merge::merge(pivot,doc_a, doc_b)

conflict_callback = proc do |args|
["<!-- ------ START CONFLICT ------ -->",
args[1],
"<!-- ---------------------------- -->",
args[2],
"<!-- ------ END CONFLICT ------ -->}"]
end

diff = diff3(pivot, doc_a, doc_b);

ret = []
conflict = [[],[],[]]

diff.each do |diffline|
i = 0
if diffline[0] == 'c' # conflict
conflict[0] << diffline[1] if diffline[1];
conflict[1] << diffline[2] if diffline[2];
conflict[2] << diffline[3] if diffline[3];
else
unless (conflict[0].empty? && conflict[1].empty? && conflict[2].empty?)
ret << (block_given? ? yield(conflict) :
conflict_callback.call(conflict))
conflict = [[],[],[]]
end
case diffline[0]
when 'u' # unchanged
ret << diffline[2] || diffline[3];
when 'o','l' # added by both or left
ret << diffline[2] if diffline[2]
when 'r' #added by right
ret << diffline[3] if diffline[3]
end
end
end
unless (conflict[0].empty? && conflict[1].empty? && conflict[2].empty?)
ret << (block_given? ? yield(conflict) :
conflict_callback.call(conflict))
end

ret
end

end


Ruby Quiz

unread,
Feb 2, 2006, 8:37:43 AM2/2/06
to
The great element of porting a library is that you get examine another
programmer's ideas. If you're lucky, that may teach you a new trick or two.
I'll use my experience as an example.

Using Buffers

When I decided to port File::ReadBackwards, the first question I asked myself
was, how do you read a file backwards? I decided that you would need to put the
read head at the end of the file, then work it backwards bit by bit. You can't
return a line until you have the whole thing, so I knew I would need to buffer
the reads. I guessed I would be sure I had a line when I had seen two line
endings (whatever is between them is a line) or run into the beginning of the
file (no more data). That actually turns out to be the rough process, but,
luckily for me, Uri Guttman is smarter than me and reading Uri's code taught me
a couple of tricks.

Here's a simplified version of my port, showing only the interesting methods:

# Based on Perl's File::ReadBackwards module, by Uri Guttman.

class Elif


MAX_READ_SIZE = 1 << 10 # 1024

def initialize( *args )


@file = File.new(*args)
@file.seek(0, IO::SEEK_END)

@current_pos = @file.pos



@read_size = @file.pos % MAX_READ_SIZE
@read_size = MAX_READ_SIZE if @read_size.zero?

@line_buffer = Array.new
end



def gets( sep_string = $/ )

return @line_buffer.pop if @line_buffer.size > 2 or @current_pos.zero?

@current_pos -= @read_size
@file.seek(@current_pos, IO::SEEK_SET)

@line_buffer[0] = "#{@file.read(@read_size)}#{@line_buffer[0]}"
@read_size = MAX_READ_SIZE # Set a size for the next read.

@line_buffer[0] =
@line_buffer[0].scan(/.*?#{Regexp.escape(sep_string)}|.+/)
@line_buffer.flatten!

gets(sep_string)
end
end

You can see the first trick Uri taught me in initialize(). Working the pointer
backwards can be messy. You have to keep track of where you are, shift the read
pointer back, read some, but always make sure you have that many bytes left.
There's an easier way.

If you pick some number of bytes you are going to read, you can consider the
file to be in chunks that size. For example, if we are going to read ten bytes
at a time and have a twenty-four byte file, we can deal with it in chunks of
ten, ten, and four. The only odd chunk size is at the end, where we start, so
we can deal with that immediately and then all future reads can be whatever
chunk size we selected.

That's what initialize() is doing: Open the file, jump to the end, and set that
initial read size to handle the dangling partial chunk.

Now we can tackle gets() and I'll tell you about the other lesson Uri taught me.
First, the function of gets() is pretty basic: If we know we have a line or
that we are out of lines, return it or nil. Otherwise, read some more data,
trying to make one of those two exit conditions true, and recurse. The only
hard part is deciding when we have a line.

I was dreaming up a complicated solution to this, when reading Uri's code showed
me the light. You can store the data in the buffer exactly like it is in the
file (or whatever we've read of it so far). We will break it at lines though,
because that's what we're interested in reading. At any given time, it's very
likely the buffer holds a partial line (because we haven't seen the rest).
However, if we have at least two lines buffered, we can return one immediately.
One of them is likely a partial sure, but the last one, the one the user wants,
must be full now. This is easy to code, as you can see above.

In gets(), I prepend each read to the first (likely partial) line. Then I use
scan() to find all the lines in there, creating an Array, then flatten!() to
fold those lines back into the buffer, discarding the extra Array.

Thanks for the lessons Uri!

You really pick these insights up from reading the code of others, which is why
I think reading code is important. This is one of the big perks of running the
Ruby Quiz. I get to read a lot of code and the submissions are always teaching
me things. This week was no different, so now let me tell you what I learned
from others.

Lazy Evaluation

This next library came at just the right time for me. I'm reading Higher-Order
Perl, by Mark Jason Dominus, and trying to apply the ideas I am learning there
to my Ruby usage. One of the big concepts in the book is "lazy" code, which is
just a fancy way of saying, I want to run this... later.

There are a lot of advantages to something like this. If an operation is
expensive in computational terms, we can assure that it doesn't happen until it
is needed. The advantage to that is that it may not be needed at all, which
keeps us from wasting time.

Another less-used example is that we can delay evaluation until we have more
information. The standard PStore library is a great example here. You pass it
the path to the cache file in initialize(), but it waits until transaction() to
actually open the file. The reason is that you can start a "read-only"
transaction, or a normal transaction that allows reading and writing. By
waiting to open the file, PStore knows the right mode to use, the right level of
file locking to apply, etc.

The tricky part to lazy evaluation, for me at least, is just getting your head
around it. When you decide you're ready though, here is an excellent first
step:

module Trampoline
# Instance methods
class Bounce
def initialize(cons, klass, *args)
@klass, @cons, @args = klass, cons, args
end

def method_missing(method, *args)
@obj = @klass.send(@cons, *@args) unless @obj
@obj.send(method, *args)
end
end

# Class methods
class << Bounce
alias_method :old_new, :new

def new(*args)
old_new(:new, *args)
end

def method_missing(method, *args)
old_new(method, *args)
end
end
end

That's Matthew Moss's port of the Perl Trampoline module, by Steven Lembark.
Let's break down what this does.

First, the instance methods. It seems that initialize() doesn't do anything
except store some information. We will find out what for in method_missing().

Remember that method_missing() will be called for any message we haven't
defined. In this case, that's pretty much everything. (More on that in a
minute...) When called, method_missing() makes sure @obj is defined. If it's
not, it is created by calling the proper cons(tructor) with the args
initialize() tucked away. Then the message is just forwarded to @obj. That
means the object is built just before the first method call, then reused to
handle all future method calls.

The only problem with the above strategy is that Bounce includes some default
Ruby methods inherited from Object. This means that something like a to_s()
call isn't forwarded. You can fix this by adding something like the following
to Bounce:

instance_methods.each { |m| undef_method m unless m =~ /^__/ }

Now let's look at the class methods. You can see that new() is moved and
redefined, to change its interface for calling code. Now we see another
method_missing(), this time for the class itself. It works just like the
redefined new(), forwarding the message to the constructor. Remember, not all
objects are constructed with new(). Singleton objects often use instance(), for
example. This method allows for that. Whatever is called will later be used to
build the object.

That's a great introduction to lazy evaluation. When that sinks in a bit and
you're ready for more, see the excellent lazy.rb library by MenTaLguY:

http://moonbase.rydia.net/software/lazy.rb/

Currying

Another interesting technique discussed in Higher-Order Perl was also
represented in the solutions to this quiz. Ross Bamford ported Perl's
Sub::Curry module by Johan Lodin. Currying is basically the process of using
functions to manufacture other functions, as seen in these simple examples:

require "curry"

scale = lambda { |size, object| object * size }

puts "3 scaleded to a size of 10 is #{scale[10, 3]}." # 30
puts

# curry some functions
double = scale.curry(2)
triple = scale.curry(3)
halve = scale.curry(0.5)

puts "4 doubled is #{double[4]}." # 8
puts "1 tripled is #{triple[1]}." # 3
puts "Half of 10 is #{halve[10]}." # 5.0

The great side of this library is that it can handle much more complicated
argument setups than this. For example, what if the arguments to scale had been
reversed? No problem:

scale = lambda { |object, size| object * size }

puts "3 scaleded to a size of 10 is #{scale[10, 3]}." # 30
puts

# we can leave "holes" in the argument list
double = scale.curry(Curry::HOLE, 2)
triple = scale.curry(Curry::HOLE, 3)
halve = scale.curry(Curry::HOLE, 0.5)

puts "4 doubled is #{double[4]}." # 8
puts "1 tripled is #{triple[1]}." # 3
puts "Half of 10 is #{halve[10]}." # 5.0

That works exactly the same, but if you're not impressed yet we can get even
fancier. The library already supports a bunch of "spices", like HOLE above, but
you can also add your own:

# Lazy Evaluation meets Currying...
class LazySpice < Curry::SpiceArg
def initialize( &promise )
super("LAZYSPICE")

@promise = promise
end

def spice_arg( args ) # called to provide the missing argument
[@promise.call]
end
end

logger = lambda do |time, message|
puts "[#{time.strftime('%I:%M:%S %p %m/%d/%y')}] #{message}"
end

log_now = logger.curry(LazySpice.new { Time.now })

log_now["First Message."] # => [12:47:53 PM 02/01/06] First Message.
sleep 3
log_now["Second Message."] # => [12:47:56 PM 02/01/06] Second Message.

Notice how the LazySpice isn't evaluated until the time of the call. That lazy
execution makes sure our message is stamped with the time it was actually
logged.

I'm not going to show the library here, since I've gone on long enough, but I
hope you will agree that it's worth a look.

Wrap Up

Please take some time to look into the other solutions I didn't cover here. All
of them were interesting ideas and I hope their authors will consider packaging
them up for all to use.

Myself, and others, were worried that this would not be a popular quiz. It far
exceeded my expectations though and I owe a big thank you to all who made that
happen! You are all so clever it makes even me look good.

We'll go back to a more traditional Ruby Quiz problem tomorrow, I promise. This
time we will borrow a problem from the Code Katas...


Ross Bamford

unread,
Feb 2, 2006, 10:03:40 AM2/2/06
to
On Thu, 2006-02-02 at 22:37 +0900, Ruby Quiz wrote:
> The library already supports a bunch of "spices", like HOLE above, but
> you can also add your own:
>
> # Lazy Evaluation meets Currying...
> class LazySpice < Curry::SpiceArg
> def initialize( &promise )
> super("LAZYSPICE")
>
> @promise = promise
> end
>
> def spice_arg( args ) # called to provide the missing argument
> [@promise.call]
> end
> end
>
> logger = lambda do |time, message|
> puts "[#{time.strftime('%I:%M:%S %p %m/%d/%y')}] #{message}"
> end
>
> log_now = logger.curry(LazySpice.new { Time.now })
>
> log_now["First Message."] # => [12:47:53 PM 02/01/06] First Message.
> sleep 3
> log_now["Second Message."] # => [12:47:56 PM 02/01/06] Second Message.
>
> Notice how the LazySpice isn't evaluated until the time of the call. That lazy
> execution makes sure our message is stamped with the time it was actually
> logged.

This is very cool, thanks for the great write-up. However, there is a
small bug (in curry.rb, not this code) that can cause problems with
this, e.g:

a = [1,3,5]
b = [2,4,6]

l = lambda do |ary,aa,ba|
ary + [aa,ba]
end.curry(Curry::HOLE,Curry::HOLE,TestSpice.new { b.shift })

l.call
# => [1,nil,3,nil,5,nil] (expected: 1,2,3,4,5,6)

This only shows up when special spices are at the end of the argument
list, and happens because there are no args_remain left by the time
they're seen, and I took a short-cut in the implementation. The attached
patch (against the documented version from
http://roscopeco.co.uk/code/ruby-quiz-entries/64/curry.rb) fixes things.
There maybe a slight impact on performance, though (if that matters).

I'm considering maybe packaging Ruby Murray up as a gem and releasing it
on RubyForge. I'll add James' LazySpice, and would like any suggestions
others may have (esp if anyone has something we could legitimately call
"SportySpice" ;D)

Thanks again for the quiz. Cool entries everyone :)

0.1.0-0.1.2.patch

Ross Bamford

unread,
Feb 2, 2006, 10:06:24 AM2/2/06
to
On Fri, 2006-02-03 at 00:03 +0900, Ross Bamford wrote:

> l = lambda do |ary,aa,ba|
> ary + [aa,ba]
> end.curry(Curry::HOLE,Curry::HOLE,TestSpice.new { b.shift })

(Oops, TestSpice is a simplified LazySpice I used in the tests.
Substitute LazySpice there.)

Phil Tomson

unread,
Feb 2, 2006, 7:39:51 PM2/2/06
to
In article <20060202133728.KIME61...@localhost.localdomain>,

Ruby Quiz <ja...@grayproductions.net> wrote:
>
> Wrap Up
>
>Please take some time to look into the other solutions I didn't cover here. All
>of them were interesting ideas and I hope their authors will consider packaging
>them up for all to use.
>
>Myself, and others, were worried that this would not be a popular quiz. It far
>exceeded my expectations though and I owe a big thank you to all who made that
>happen! You are all so clever it makes even me look good.
>

It would be cool to have a monthly Port-a-library exercise that might run in
parallel to the Ruby Quizes. Lots of libraries are too large to port in a
weekend. it might also be interesting to have a 'hit-list' of libraries to port
each month based on input from ruby-talk and other sources.

Phil

James Edward Gray II

unread,
Feb 2, 2006, 8:15:37 PM2/2/06
to
On Feb 2, 2006, at 7:03 PM, Phil Tomson wrote:

> In article
> <20060202133728.KIME61...@localhost.localdomain>,
> Ruby Quiz <ja...@grayproductions.net> wrote:
>>
>> Wrap Up
>>
>> Please take some time to look into the other solutions I didn't
>> cover here. All
>> of them were interesting ideas and I hope their authors will
>> consider packaging
>> them up for all to use.
>>
>> Myself, and others, were worried that this would not be a popular
>> quiz. It far
>> exceeded my expectations though and I owe a big thank you to all
>> who made that
>> happen! You are all so clever it makes even me look good.
>>
>
> It would be cool to have a monthly Port-a-library exercise that
> might run in
> parallel to the Ruby Quizes. Lots of libraries are too large to
> port in a
> weekend.

Interesting thought. If you could divide up the bigger libraries,
maybe the whole group could help do one at a time.

> it might also be interesting to have a 'hit-list' of libraries to port
> each month based on input from ruby-talk and other sources.

Ooo, I really like that idea.

Sounds like a project you just have to start, to me. :)

James Edward Gray II

Martin DeMello

unread,
Feb 3, 2006, 5:45:56 AM2/3/06
to
Ruby Quiz <ja...@grayproductions.net> wrote:
> The great element of porting a library is that you get examine another
> programmer's ideas. If you're lucky, that may teach you a new trick or two.
> I'll use my experience as an example.

I also love the way that code seems to vanish when you port it to ruby :)

martin

Berger, Daniel

unread,
Feb 3, 2006, 11:00:01 AM2/3/06
to
> -----Original Message-----
> From: James Edward Gray II [mailto:ja...@grayproductions.net]
> Sent: Thursday, February 02, 2006 6:16 PM
> To: ruby-talk ML
> Subject: Re: [SUMMARY] Port a Library (#64)

<snip>

> > It would be cool to have a monthly Port-a-library exercise that
> > might run in
> > parallel to the Ruby Quizes. Lots of libraries are too large to
> > port in a
> > weekend.
>
> Interesting thought. If you could divide up the bigger libraries,
> maybe the whole group could help do one at a time.
>
> > it might also be interesting to have a 'hit-list' of
> libraries to port
> > each month based on input from ruby-talk and other sources.
>
> Ooo, I really like that idea.
>
> Sounds like a project you just have to start, to me. :)
>
> James Edward Gray II

See http://rubygarden.org/ruby?LibraryModules

Regards,

Dan


Reply all
Reply to author
Forward
0 new messages