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.