Higher-Order Procedures Tutorial (long)

[Nate Murray]

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:

1) 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.methodcube).to_proc
cube.call(3)

part. Any suggestions on how to make this a little more transparent or
simplified?

2) 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 Murray
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 Murray <[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 <name>(a, b)
# return 0 if a > b
# <term>(a) + <name>(<next>(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.methodcube).to_proc
inc = self.methodinc ).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.methodidentity).to_proc
inc = self.methodinc ).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.methodpi_term).to_proc
nex = self.methodpi_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.

 

[William James]

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:

1) 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.methodcube).to_proc
cube.call(3)

part. Any suggestions on how to make this a little more transparent or
simplified?

def cube n
n * n * n
end

def inc(n)
n + 1
end

def sum(term, a, the_next, b)
return 0 if a > b
send(term,a) + sum(term, send(the_next,a), the_next, b)
end

p sum( :cube, 1, :inc, 3 )

 

[ara.t.howard]

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:

1) 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.methodcube).to_proc
cube.call(3)

part. Any suggestions on how to make this a little more transparent or
simplified?

method('cube')[ 3 ]

2) 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 Murray
http://www.natemurray.com

btw.

harp:~ > cat a.rb
def sum_integers(a, b)
return 0 if a > b
a + sum_integers((a + 1), b)
end

p sum_integers(10, 10)

harp:~ > ruby a.rb
10

and similar errors.

you could post this on http://sciruby.codeforpeople.com/ if you wanted.

regards.

-a

 

[ara.t.howard]

# == 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

def cube(n) n ** 3 end

-a

 

[Giles Bowkett]

Hey, I don't have time to look at this right away, BUT, you should
check out James Grey's blog, Google "Higher-Order Ruby." He did a
series on using higher-order programming in Ruby, based on
translations from Mark-Jason Dominus' "Higher-Order Perl," and it's
very good.

 

[James Edward Gray II]

Hey, I don't have time to look at this right away, BUT, you should
check out James Grey's blog, Google "Higher-Order Ruby." He did a
series on using higher-order programming in Ruby, based on
translations from Mark-Jason Dominus' "Higher-Order Perl," and it's
very good.

http://blog.grayproductions.net/articles/category/higher-order-ruby

I really am working on the last two as well and will get them out
eventually...

James Edward Gray II

 

[pat eyler]

http://blog.grayproductions.net/articles/category/higher-order-ruby

I really am working on the last two as well and will get them out
eventually...

I hope so, I'm anxious to read them. ;^)

 

[Sam Smoot]

The filter_evens() example is not very ruby-ish. (As I interpret it
anyways.) I might write it like this:

class Fixnum
def even?
self % 2 == 0
end
def odd?
not self.even?
end
end

Then instead of a filter_evens() method, I would just:

list.select { |n| n.even? }

Or even shorter:

list.select &:even?

....if you have 'facets/symbol/to_proc' or 'active_support' loaded.

 

[Giles Bowkett]

The filter_evens() example is not very ruby-ish. (As I interpret it
anyways.) I might write it like this:
...

Or even shorter:

list.select &:even?

...if you have 'facets/symbol/to_proc' or 'active_support' loaded.

You also did (a * a * a) for a to the 3rd power, when you could have
just done (a ** 3).

However, I took a look at the PDF, and I have to say, there are some
very good bits in this. It looks like a lot of your examples come
directly from the Ableson-Sussman videos? I really liked the
#filter_ths() example. There are probably more Rubyish ways to do
these things, but it's a very clear set of examples. I liked it a lot.

 

[Gregory Brown]

Greetings

Do we have an object relational mapper for csv files?

#data:
first_name;last_name;phone
peter;pan;12345

#ROW ACCESS
person.first_name => "peter"
person.last_name => "pan"



Even nicer if it header_row and separation_character can be specified?


I've considered csvparser-0.1.1 and FasterCSV, but as far as I can tell

- csvparser is a little thin on header_row/sep_char
- FasterCSV's synax
table[:first_name][1]
this kind'o does the job, but I would prefer the implementation of
the datasource to be a bit less visible in the rest of the app

Have you considered Ruport?

 

[Gregory Brown]

Should have included an example.

and the file I used! Sorry for the triple post.

seltzer:~ sandal$ cat foo.csv
first_name;last_name;phone
peter;pan;12345
joe;loop;56789

 

[Gregory Brown]

Have you considered Ruport?

Should have included an example.
=> ["peter pan", "joe loop"]

 

[Mark Volkmann]

Have you considered Ruport?

Should have included an example.
=> ["peter pan", "joe loop"]

Where does the Record class get used? Does the Table class use it
internally?

 

[Gregory Brown]

Where does the Record class get used? Does the Table class use it
internally?

yeah. I'm currently contemplating a better alternative. That's a bit
of a hack there.

Pending user feedback, I may implement something like what is
described in this mailing list post:
http://rubyurl.com/BuR

I never really set out to build an ORM style thing, but since our
Tables can be built from ActiveRecord objects via acts_as_reportable,
SQL (requires DBI), CSVs, or hand built, it's starting to shape up a
bit.

I'd be interested in feedback from folks about this, but please carry
it on over to the Ruport list so I can archive it there.