17
JAN2006
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 Integers to binary Strings (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}, " +
"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 && 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…
Comments (17)
-
Jim Weirich January 24th, 2006 Reply LinkThe way MJD described OO, is certainly not how a lot of idiomatic Ruby comes out.
Could you elaborate on this? Sounds interesting.
-
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::Unitspots all methods beginning withtest_).It just strikes me that we use objects pretty differently from typical Object Oriented languages.
-
-
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.
-
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 asFile.read('report').map(&:gsub[/java/i,'C#']) -
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.
-
Simula predates Smalltalk. Smalltalk added a lot of innovation, but it's not fair to say it invented OO.
-
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.
-
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.
-
-
-
-
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.
RetrainJunkBackendEventProcessMailBackendEventThey are all subclasses of a
BackendEventmethod, which defines a baserunmethod.Each subclass defines its own
runmethod.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!
-
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?
-
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!
-
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.
-
-
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.
-
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.
-
-
Actually, your implementation of factorial:
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.
-
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
-
-
Thank you for this excellent series of articles. In order to better understand the examples and also compare Ruby with JavaScript I ported many of the examples to JavaScript here https://github.com/antivanov/Higher-Order-JavaScript
It turns out that JavaScript is also a pretty powerful and flexible language, although often Ruby provides more syntactic sugar and for more concise code. However, I was surprised that there were a few cases when the JavaScript code is actually shorter simpler: memoization and currying. This is mainly because JavaScript has only functions and no classes and modules.