Hey Guys,
I’ve been going through the video lectures "Structure and
Interpretation of Computer Programs by Hal Abelson and Gerald Jay
Sussman. " (
http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/ ).
The section on Higher-Order Procedures was a huge eye-opener for me and
I wanted to condense down what I learned in Lisp to guys who program in
Ruby. Now I know that for most of the experienced on this list this
will be old-news, but I hope to provide a valuable tutorial of Abelson
and Sussman’s material to some guys who are just learning about this
stuff in Ruby.
Posted below is the straight text and code examples of what I have so
far. ( I’ve also posted the pdf of slides here:
http://tech.natemurray.com/2006/12/higher-order-procedures-in-ruby.html
if you’re interested. ) Now, I am not just trying to drive up traffic
to my site. My purpose in posting this here is two-fold:
- To submit it for peer review. I’d like to know if you guys have any
suggestions or improvements on the code examples and/or copy. For
example a part that seems particularly ugly to me is the
cube = self.method(:cube).to_proc
cube.call(3)
part. Any suggestions on how to make this a little more transparent or
simplified?
- To provide a valuable introductory tutorial to the power of
higher-order procedures and how to implement them in Ruby.
The text below can be copied and pasted into a file. It should run with
no problems.
DISCLAIMER: As mentioned above and below the copy is taken mainly from
"Structure and Interpretation of Computer Programs by Hal Abelson and
Gerald Jay Sussman. " (
http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/ ). A
few paraphrases and examples were added and the code was converted to
Ruby.
enjoy,
Nate M.
http://www.natemurray.com
#!/usr/bin/ruby
== Higher-Order Procedures (in Ruby)
based on Structure and Interpretation of Computer Programs (1985 MIT
Press)
by Hal Abelson and Gerald Jay Sussman.
* http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/
Nathan M. [email protected] v1.0 12/13/06
http://www.natemurray.com
== Legal
The copy in this presentation is taken directly from Structure and
Interpretation of Computer Programs by Hal Abelson and Gerald Jay
Sussman
(MIT Press, 1984; ISBN 0-262-01077-1). Specifically section 1.3
Formulating
Abstractions with Higher-Order Procedures. There are a few
paraphrases and
additional examples added.
The main difference is that the code has been converted from Lisp to
Ruby.
The full text of this book and accompanying video lectures can be
found at:
http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/
http://mitpress.mit.edu/sicp/
The video lectures are copyright by Hal Abelson and Gerald Jay
Sussman. The
video lectures, and in turn this document, are licensed under a
Creative
Commons License.
http://creativecommons.org/licenses/by-sa/2.0/
== Slide
Mathematical procedures are, in effect, abstractions that describe
compound operations on
numbers independent of the particular numbers. For example, when we
def cube(a)
a * a * a
end
define cube we are not talking about the cube of a particular number,
but rather about a
method for obtaining the cube of any number.
== Slide
Of course we could get along
without ever defining this procedure, by always writing expressions
such as
(3 * 3 * 3)
(x * x * x)
(y * y * y)
and never mentioning cube explicitly. This would place us at a
serious
disadvantage, forcing us to work always at the level of the
particular
operations that happen to be primitives in the language
(multiplication, in
this case) rather than in terms of higher-level operations. Our
programs
would be able to compute cubes, but our language would lack the
ability to
express the concept of cubing. One of the things we should demand
from a
powerful programming language is the ability to build abstractions by
assigning names to common patterns and then to work in terms of the
abstractions directly. Procedures provide this ability.
== Slide
Yet even in numerical processing we will be severely limited in our
ability
to create abstractions if we are restricted to procedures whose
parameters
must be numbers.
Often the same programming pattern will be used with a number of
different
procedures. To express such patterns as concepts, we will need to
construct
procedures that can accept procedures as arguments or return
procedures as
values.
Procedures that manipulate procedures are called higher-order
procedures.
This presentation shows how higher-order procedures can serve as
powerful
abstraction mechanisms, vastly increasing the expressive power of our
language.
== Slide
Consider the following three procedures.
== Slide
The first computes the sum of the integers from a through b:
def sum_integers(a, b)
return 0 if a > b
a + sum_integers((a + 1), b)
end
sum_integers(1, 10) #=> 55
== Slide
The second computes the sum of the cubes of the integers in the given
range:
def sum_cubes(a, b)
return 0 if a > b
cube(a) + sum_cubes((a + 1), b)
end
sum_cubes(1, 3) #=> 36
The third computes the sum of a sequence of terms in the series which
converges to pi/8 (very slowly)
def pi_sum(a, b)
return 0 if a > b
(1.0 / ((a + 2) * a)) + (pi_sum((a + 4), b))
end
pi_sum(1, 1000) * 8 #=> 3.13959265558978
== Slide
These three procedures clearly share a common underlying pattern.
They are for the most part identical, differing only in the
* name of the procedure
* the function of a used to compute the term to be added, and
* the function that provides the next value of a.
We could generate each of the procedures by filling in slots in the
same template:
== Slide
def (a, b)
return 0 if a > b
(a) + ((a), b)
end
== Slide
The presence of such a common pattern is strong evidence that there
is a
useful abstraction waiting to be brought to the surface.
Mathematicians long ago identified the abstraction of summation of a
series
and invented ``sigma notation,’’ for example to express this concept.
The power of sigma notation is that it allows mathematicians to deal
with the
concept of summation itself rather than only with particular sums
For example, you can formulate general results about sums that are
independent of the particular series being summed.
Similarly, as program designers, we would like our language to be
powerful
enough so that we can write a procedure that expresses the concept of
summation itself rather than only procedures that compute particular
sums.
== Slide
We can do so readily in our procedural language by taking the common
template
shown above and transforming the ``slots’’ into formal parameters:
def sum(term, a, the_next, b)
return 0 if a > b
term.call(a) + sum(term, the_next.call(a), the_next, b)
end
== Slide
Now to define sum cubes all we have to do is:
def inc(n)
n + 1
end
def sum_cubes(a, b)
cube = self.method(:cube).to_proc
inc = self.method(:inc ).to_proc
sum(cube, a, inc, b)
end
sum_cubes(1, 3) #=> 36
== Slide
With the aid of an identity procedure to compute the term, we can
define
sum-integers in terms of sum:
def identity(x)
x
end
def sum_integers(a, b)
id = self.method(:identity).to_proc
inc = self.method(:inc ).to_proc
sum(id, a, inc, b)
end
#Then we can add up the integers from 1 to 10:
sum_integers(1, 10) #=> 55
== Slide
We can also define pi-sum in the same way
def pi_term(x)
(1.0 / (x * (x+2)))
end
def pi_next(x)
(x + 4)
end
def pi_sum(a, b)
term = self.method(:pi_term).to_proc
nex = self.method(:pi_next).to_proc
sum(term, a, nex, b)
end
Using these procedures, we can compute an approximation to pi:
pi_sum(1, 1000) * 8 #=> 3.13959265558978
In using #sum it seems terribly awkward to have to define trivial
procedures
such as pi_term and pi_next just so we can use them as arguments to
our
higher-order procedure.
Rather than define pi-next and pi-term, it would be more convenient
to have a way to directly specify
* ``the procedure that returns its input incremented by 4’’ and
* ``the procedure that returns the reciprocal of its input times its
input plus 2.’’
We can do this by introducing the special form lambda, which creates
procedures. Using lambda we can describe what we want as
lambda{ |x| (1.0 / (x * (x+2))) }
lambda{ |x| (x + 4) }
== Slide
Then our pi_sum procedure can be expressed without defining any
auxiliary procedures as in:
def pi_sum(a, b)
sum( lambda{ |x| (1.0 / (x * (x+2))) },
a,
lambda{ |x| (x + 4) },
b )
end
== Slide
The above examples demonstrate how the ability to pass procedures as
arguments significantly enhances the expressive power of our
programming
language.
We can achieve even more expressive power by creating procedures
whose
returned values are themselves procedures.
Lets say we want to filter out the even numbers in a list.
This procedure takes a list and returns a new list containing the
even numbers.
def even?(i)
i % 2 == 0
end
at the end, functions that return functions
def filter_evens(list)
new_list = []
list.each do |element|
new_list << element if even?(element)
end
new_list
end
list = [1,2,3,4,5,6,7,8,9,10]
filter_evens(list) #=> [2, 4, 6, 8, 10]
Well, later on we may want to filter by odd numbers, or by prime
numbers.
What we need is a way to express the concept of filtration.
== Slide
(predicate : Logic something that is affirmed or denied concerning an
argument of a proposition.)
Notice that #make_filter returns not just a value, but a procedure.
This
procedure can then be used on other data.
def make_filter(predicate)
lambda do |list|
new_list = []
list.each do |element|
new_list << element if predicate.call(element)
end
new_list
end
end
filter_odds = make_filter( lambda{|i| i % 2 != 0} )
filter_odds.call(list) #=> [1, 3, 5, 7, 9]
== Slide
The power of this is that our filter is not limited to numeric
evaluations.
Lets say we want to filter by numbers where the ordinal ends in th
such as 10th.
require ‘facet/integer/ordinal’
10.ordinal #=> “10th”
filter_ths = make_filter(
lambda do |i|
i.ordinal =~ /th$/ ? true : false
end
)
filter_ths.call(list) #=> [4, 5, 6, 7, 8, 9, 10]
You do this all the time with #map
== Slide
As programmers, we should be alert to opportunities to identify the
underlying abstractions in our programs and to build upon them and
generalize
them to create more powerful abstractions.
This is not to say that one should always write programs in the most
abstract
way possible; expert programmers know how to choose the level of
abstraction
appropriate to their task. But it is important to be able to think in
terms
of these abstractions, so that we can be ready to apply them in new
contexts.
The significance of higher-order procedures is that they enable us to
represent these abstractions explicitly as elements in our
programming
language, so that they can be handled just like other computational
elements.