Higher-Order Procedures Tutorial (long)

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.method(:cube).to_proc
cube.call(3)

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

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

Nate M. wrote:

stuff in Ruby.

cube = self.method(:cube).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 )

On Thu, 28 Dec 2006, Nate M. wrote:

stuff in Ruby.

cube = self.method(:cube).to_proc
cube.call(3)

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

method(‘cube’)[ 3 ]

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

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

On Thu, 28 Dec 2006, Nate M. wrote:

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

On Dec 27, 2006, at 11:11 PM, Giles B. wrote:

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 G. II

On 12/28/06, James Edward G. II [email protected] wrote:

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. ;^)

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.

On 12/28/06, Sam S. [email protected] wrote:

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.

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.

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

Thank’s for your time

JE

On 1/5/07, Jon Egil S. [email protected] wrote:

person.first_name => "peter"
  • 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?

On Jan 5, 2007, at 12:36 PM, Jon Egil S. wrote:

person.first_name => "peter"
person.last_name => "pan"

First idea:

#!/usr/bin/env ruby -w

require “rubygems”
require “faster_csv”

require “ostruct”

load

people = FCSV( DATA, :col_sep => “;”,
:headers => true,
:header_converters => :symbol ) do |csv|
csv.inject(Array.new) { |all, person| all + [OpenStruct.new
(person.to_hash)] }
end

example usage

puts people.map { |person| person.first_name }

END
First Name;Last Name;Phone
Peter;Pan;111-1111
Wendy;Darling;222-2222

Second idea, if you are in control of the CSV data:

#!/usr/bin/env ruby -w

require “rubygems”
require “faster_csv”

require “pp”

Person = Struct.new(:first_name, :last_name, :phone)

people = [ %w[Peter Pan 111-1111],
%w[Wendy Darling 222-2222] ].inject(Array.new) do |all,
attrs|
all + [Person.new(*attrs)]
end

dump

csv = FCSV.dump(people)
puts csv
puts

load

reloaded = FCSV.load(csv)
pp reloaded
puts

use

puts reloaded.map { |person| person.first_name }

Hope one of those helps.

James Edward G. II

On 1/5/07, Gregory B. [email protected] wrote:

Have you considered Ruport?

Should have included an example.

table = Table(“foo.csv”,:csv_options => { :col_sep => “;” })
class Ruport::Data::Record
def name
“#{first_name} #{last_name}”
end
end
=> nil

table.map { |r| r.name }
=> [“peter pan”, “joe loop”]

Gregory and James

Thank you so much for your precise and speedy replies, I am thankful
both
for your suggestions and for your effort in building these libraries.

With FasterCSV I espescially like the ability to set

:headers => “my;custom;header”

and with ruport it seems very covenient to add some simple logic within
the Ruport::Data::Record class.

James - your code example is very neat, but since I’m blessed with a
simple mind I traded space for readability:


FROM

people = FCSV(data, :col_sep => “;”,
:headers => true,
:header_converters => :symbol ) do |csv|
csv.inject(Array.new) { |all, person| all +
[OpenStruct.new(person.to_hash)] }
end

example usage

puts people.map { |person| person.first_name }


TO

people = Array.new
FCSV(data, :col_sep => “;”,
:headers => true,
:header_converters => :symbol ) do |csv|
csv.each do |csvrow|
people.push OpenStruct.new(csvrow.to_hash)
end
end

people.each do |person|
puts person.first_name
end

Not meaning to bash your suggestion, just sharing my initial reaction.
Any
comments or caveats?

Anyway, both your suggestions surpass my needs though, so from here on
in
it’s a breeze. Thank you.

JE

On Jan 5, 2007, at 2:31 PM, Gregory B. wrote:

"#{first_name} #{last_name}"

end
end
=> nil

table.map { |r| r.name }
=> [“peter pan”, “joe loop”]

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

On 1/5/07, Jon Egil S. [email protected] wrote:

Gregory and James

Thank you so much for your precise and speedy replies, I am thankful both
for your suggestions and for your effort in building these libraries.

With FasterCSV I espescially like the ability to set

    :headers => "my;custom;header"

anything in :csv_options gets passed along to FasterCSV in the code I
suggested, so you might be able to see if that’ll be helpful somehow.

On Jan 5, 2007, at 3:23 PM, Jon Egil S. wrote:

end

people.each do |person|
puts person.first_name
end

Not meaning to bash your suggestion, just sharing my initial
reaction. Any comments or caveats?

Your code looks just fine to me. Glad it helps!

James Edward G. II

On 1/5/07, Mark V. [email protected] wrote:

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.

On 1/5/07, Gregory B. [email protected] wrote:

On 1/5/07, Gregory B. [email protected] wrote:

Have you considered Ruport?

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs