# Higher-Order Ruby

A Rubyification of the Perl book about functional programming.

JAN
2006

### Recursion and Callbacks

I'm currently reading through Higher-Order Perl, by Mark Jason Dominus. (Yes, I read books about things other than Ruby.)

So far, I'm enjoying the title quite a bit. It certainly has me thinking and the Perl in it is very clean and easy to understand. That helps me translate the concepts to my language of interest.

I'll post some of my Ruby translations of the books example code here as I go along. Others familiar with the book might enjoy looking over them. Be warned, my comments might not make much sense to those who haven't read the book.

#### Recursion

The book starts with some very simple recursion examples trivially translated. Here's one for manually translating `Integer`s to binary `String`s (a long way to say `str.to_i.to_s(2)` in Ruby):

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

def binary(number)
return number.to_s if [0, 1].include?(number)

k, b = number.divmod(2)
binary(k) + b.to_s
end

unless !ARGV.empty? && ARGV.all? { |n| n =~ /\A\d+\Z/ }
abort "Usage:  #{File.basename(\$PROGRAM_NAME)} DECIMAL_NUMBERS"
end

puts ARGV.map { |num| binary(num.to_i) }.join(" ")
```

Here's another for calculating factorials:

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

def factorial(number)
return 1 if number == 0

factorial(number - 1) * number
end

unless !ARGV.empty? && ARGV.all? { |n| n =~ /\A\d+\Z/ }
abort "Usage:  #{File.basename(\$PROGRAM_NAME)} DECIMAL_NUMBERS"
end

puts ARGV.map { |num| factorial(num.to_i) }.join(" ")
```

MJD does talk about how recursion can always be unrolled into an iterative solution. That leads to what is probably a more natural Ruby solution for examples like these. Here's how I would probably code `factorial()`:

```def factorial(number)
(1..number).inject { |prod, n| prod * n }
end
```

Of course, that's just not what this chapter is about.

#### Callbacks

This section starts off by showing just how cool Ruby's blocks can be:

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

def hanoi(disk, start, finish, extra, &mover)
if disk == 1
mover[disk, start, finish]
else
hanoi(disk - 1, start, extra, finish, &mover)
mover[disk, start, finish]
hanoi(disk - 1, extra, finish, start, &mover)
end
end

disks = ARGV.empty? ? 64 : ARGV.first.to_i

positions = [nil] + ["A"] * disks
hanoi(disks, "A", "C", "B") do |disk, start, finish|
if disk < 1 || disk > positions.size - 1
raise "Bad disk number:  #{disk}.  Disks should be between 1 and #{disks}."
end

unless positions[disk] == start
raise "Tried to move ##{disk} from #{start}, " +
"but it is on peg #{positions[disk]}."
end

(1...disk).each do |smaller_disk|
if positions[smaller_disk] == start
raise "Cannot move #{disk} from #{start}, " +
"because #{smaller_disk} is on top of it."
elsif positions[smaller_disk] == finish
raise "Cannot move #{disk} to #{finish}, " +
end
end

puts "Move ##{disk} from #{start} to #{finish}."
positions[disk] = finish
end
```

Interestingly though, MJD quickly gets into passing around multiple anonymous functions, and Ruby has to do that just like Perl:

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

def dir_walk(top, file_proc, dir_proc)
total = File.size(top)

if File.directory?(top)
results = Array.new
Dir.foreach(top) do |file_name|
next if %w{. ..}.include?(file_name)
results += dir_walk(File.join(top, file_name), file_proc, dir_proc)
end
dir_proc.nil? ? Array.new : dir_proc[top, results]
else
file_proc.nil? ? Array.new : file_proc[top]
end
end

if __FILE__ == \$0
require "pp"

unless ARGV.size == 1 && File.exist? ARGV.first
abort "Usage:  #{File.basename(\$PROGRAM_NAME)} FILE_OR_DIRECTORY"
end

file = lambda { |f|        [File.basename(f), File.size(f)] }
dir  = lambda { |d, files| [File.basename(d), Hash[*files]] }

pp dir_walk(ARGV.first, file, dir)
end
```

The above makes me want for a multi-block syntax.

It's probably worth noting here that the above is basically an attempt at direct translation. I am aware of the standard `Find` library and I do think we should be using that, for this kind of traversal.

#### Variable Scope

Twice in this chapter, MJD has to pause the discussion to school the reader on the dangers of using improperly scoped variables, which can easily wreck recursion. What I found interesting in reading these was that coding the correct Perl was always adding a step, but it Ruby you have to add a step to get it wrong. What Rubyists naturally want to type turns out to be the correct thing to do, at least in these cases. I think this is a good sign that Ruby got variable scope right.

#### Functional vs. OO Programming

We always talk about how Ruby is very Object Oriented, but after reading this side discussion about the two approaches, I wonder how true that really is. The way MJD described OO, is certainly not how a lot of idiomatic Ruby comes out. And I found myself seeing a few of the described Functional Programming elements in my favorite language. Perhaps Ruby is a hybrid Functional OO Programming Language? Food for thought…

The way MJD described OO, is certainly not how a lot of idiomatic Ruby comes out.

Could you elaborate on this? Sounds interesting.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

MJD is mainly discussing how callbacks can make code so much more powerful. I'm paraphrasing here, but first he describes the functional style of handling callbacks which basically comes out to: Have your workhorse routine accept functions as arguments and call them as needed. Then he describes how you do the same thing in Object Oriented languages (paraphrasing again): Build a class where the main work method calls virtual methods so user code can subclass and provide the missing methods.

While you certainly can write Ruby code this way, I sure don't see much of it. I think we tend to hang this kind of functionality on Ruby's blocks, which is a lot closer to passing a function argument I would say. Even when we do have people subclass and provide methods, there is often some magic involved (like how `Test::Unit` spots all methods beginning with `test_`).

It just strikes me that we use objects pretty differently from typical Object Oriented languages.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

Any language with first class functions can be used as a functional programming language.

Any language that meets the above condition and also satisfies the condition that every expression returns a value is a functional programming language.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

I've found `Symbol#to_proc` (newly in Rails) quite convenient. I made my own:

```class Symbol
def to_proc *args
lambda {|*a|
a.first.send self, *(args+a[1..-1])
}
end
alias [] to_proc
end
```

so factorial is `(1..n).inject(&:*)`, and report rewriting is as simple as `File.read('report').map(&:gsub[/java/i,'C#'])`

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

I'm new to Ruby but I've very much gotten the impression that Ruby is, as you say, a hybrid functional/OO language. It's part of the reason I'm interested in it in the first place. (Rails is the other big reason.)

One of the things about Ruby which first caught my attention was a Lisper blog saying "Ruby is an acceptable Lisp," which was basically the Lisp community's equivalent of a compliment, and as I understand it the design was inspired partly by Lisp, as well as by Perl, Python, and Smalltalk. In fact if I recall correctly Matz wrote a popular package in emacs Lisp before he wrote Ruby. (I think it was an e-mail client.)

Python is obsessively OO, obviously Smalltalk invented OO, and Perl can be very Lispy at times. So you've got a strong OO heritage and a strong functional heritage. As I said, I'm new to Ruby, but it really does appear that some hybrid elements are definitely in there.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

Simula predates Smalltalk. Smalltalk added a lot of innovation, but it's not fair to say it invented OO.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

It's a popular mis-conception that Smalltalk took OO from Simula. Alan Kay cites Simula as one of his influences on the early design of Smalltalk, but it was the original Simula (now known as Simula I), and not Simula-67 which adapted Tony Hoare's record class idea, but wasn't itself object-oriented.

Kay defined the term object-oriented as a computation model based on objects responding to messages. Classes were introduced several iterations into the evolution of Smalltalk, and as a way to share behavior, rather than a way to compose abstract data types.

Peter Wegner did a diservice when he took it upon himself to re-define object-oriented as "objects+classes+inheritance" thereby stealing Kay's term and giving it to the Abstract Data Type/Strong Typing clan.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

Rick: interesting comment. It doesn't match the other references I've seen, which state that the first implementation of Smalltalk was done in a couple days in 71, as an attempt at duplicating Simula message passing in a one page implementation.

As I recall even the early version of Simula had message passing between coroutines which strongly resembles a concurrent OO language.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

James - we've written a portion of Ruby code that works this way in Mailroom. (SproutIt.com's first app)

We have a series of backend events, i.e.
`RetrainJunkBackendEvent`
`ProcessMailBackendEvent`

They are all subclasses of a `BackendEvent` method, which defines a base `run` method.

Each subclass defines its own `run` method.

The `BackendEvent`s get serialized and de-marshalled at their intended server. (each has a context, defining which server it should get run on)

But.. this is all old hat to you =)

Ruby is pretty powerful stuff, eh!

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

The idea of passsing blocks as arguments in an OO context isn't new. Smalltalk is OO (obviously) and passes blocks too. This is what makes the Smalltalk collection classes so neat.

Ruby has picked up on this idea aswell.

Back to functional versus OO. I'm not sure if the original OO researchers at Xerox-Parc saw subclassing as the best/only way to get varied behaviour in an OO program. IMO we have just started to think of OO in this limited way because most of us have come to OO through C++ (which doesn't have blocks). Message sends with blocks is as OO in my view as any other type of message send.

BTW. isn't it the lack of side effects and the fact that you can deduce the correctness of a function as a result the key difference between functional and imperative programming?

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

BTW. In my haste to add my 2 cents, I forgot to say what agreat series of articles these are. I'm sorely tempted to go out and by the book and learn Perl just to follow along.

Great Stuff!

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

Paul is right about side effects. The lack of side effects is essential in a "true" functional programming language. Functional languages like SML have imperative features, but these are always considered to be "not functional" (dysfunctional??) and their usage is generally discouraged.

The fact that you can deduce the correctness is a consequence of the functional paradigm, and not a requirement.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

MJD does talk about how recursion can always be unrolled into an iterative solution.

Well, he shouldn't. Because it's not true. For example, there is no iterative version of the following.

```def ack(m, n)
return n + 1 if m == 0
return ack(m - 1, 1) if m > 0 && n == 0
return ack(m - 1, ack(m, n - 1)) if m > 0 && n > 0
fail
end
```

It may look innocuous, but this is an extemely nasty function.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

Morton, I mean this in the nicest possible way, but you're dead wrong. ;)

Recursion is just using the call stack to manage your parameters. You can always hand-roll your own call stack. Here's the iterative rewrite of your Ackermann function:

```def ack_iter(m, n)
call_stack = [[m, n]]

loop do
current = call_stack.pop

if current.first.zero?
result = current.last + 1
if !call_stack.empty? && call_stack[-1][-1] == "X"
call_stack[-1][-1] = result
else
return result
end
elsif current.first > 0 && current.last.zero?
call_stack << [current.first - 1, 1]
elsif current.all? { |n| n > 0 }
call_stack << [current.first - 1, "X"] <<
[current.first, current.last - 1]
else
fail
end
end
end
```

I won't pretend that's pretty, but it's certainly doable. It's also faster and less likely to overrun the call stack in Ruby.

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

```def factorial(number)
(1..number).inject { |prod, n| prod * n }
end
```

is recursive and not iterative. At least inject/reduce/fold is recursive in all functional programming languages – I'm not sure if Ruby's C-implementation is recursive, but it should probably be regarded as such.

http://en.wikipedia.org/wiki/Fold_(higher-order_function)

1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.

It's iterative:

``````\$ cat fac.rb
def factorial(number)
(1..number).inject { |prod, n| prod * n }
end

def factorial_recursive(number, n = 1)
n >= number ? number : n * factorial_recursive(number, n + 1)
end

p factorial(2_000) && true
factorial_recursive(2_000)
\$ ruby fac.rb
true
fac.rb:6:in `factorial_recursive': stack level too deep (SystemStackError)
from fac.rb:6:in `factorial_recursive'
from fac.rb:10
``````
1. ##### Reply (using GitHub Flavored Markdown)

Comments on this blog are moderated. Spam is removed, formatting is fixed, and there's a zero tolerance policy on intolerance.