Recursion and Callbacks

Posted over 2 years ago in Higher-Order Ruby.

Note: This is the first article in my Higher-Order Ruby series.

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 Integers to binary Strings:

#!/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 not ARGV.empty? and ARGV.all? { |n| n =~ /\A\d+\Z/ }
  puts "Usage:  #{File.basename($PROGRAM_NAME)} DECIMAL_NUMBERS"
  exit
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 not ARGV.empty? and ARGV.all? { |n| n =~ /\A\d+\Z/ }
  puts "Usage:  #{File.basename($PROGRAM_NAME)} DECIMAL_NUMBERS"
  exit
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 or 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}, " +
            "because #{smaller_disk} is already there."
    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 and File.exist? ARGV.first
    puts "Usage:  #{File.basename($PROGRAM_NAME)} FILE_OR_DIRECTORY"
    exit
  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...

Go to Next Article

Jim Weirich added 7 days later:

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

Could you elaborate on this? Sounds interesting.

James Edward Gray II added 7 days later:

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.

Danno added 26 days later:

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.

lee added 2 months later:

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#'])

giles bowkett added 3 months later:

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.

Shanti Braford added 3 months later:

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 BackendEvents 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!

Paul added 7 months later:

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?

Paul. added 7 months later:

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!

Jason Watkins added 7 months later:

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

Morton Goldberg added 8 months later:

"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.

James Edward Gray II added 8 months later:

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 not call_stack.empty? and 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.

Rick DeNatale added 9 months later:

A comment on Jason Watkins' comment.

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.

There's a little bit more about this on my blog

Jason Watkins added 11 months later:

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.

HellFeuer added about 1 year later:

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.

Add Your Thoughts

You can use Markdown in the body of your comment to format text and make links.

Note that I reserve the right to edit any content you post here. I typically exercise this right to fix formatting issues. All posts must be approved so spam will never been seen on these pages.

Author:
URL or Email (optional):
Body: