#!/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 <nate@natemurray.com> 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# Mathmatical procedures are, in effect, abstractions that describe compound operations on# numbers independent of the particular numbers. For example, when wedefcube(a) a * a * aend# 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:defsum_integers(a, b)return0ifa > b a + sum_integers((a +1), b)endsum_integers(1,10)#=> 55# == Slide# The second computes the sum of the cubes of the integers in the given range:defsum_cubes(a, b)return0ifa > b cube(a) + sum_cubes((a +1), b)endsum_cubes(1,3)#=> 36# The third computes the sum of a sequence of terms in the series which# converges to pi/8 (very slowly)defpi_sum(a, b)return0ifa > b (1.0/ ((a +2) * a)) + (pi_sum((a +4), b))endpi_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:defsum(term, a, the_next, b)return0ifa > 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:definc(n) n +1enddefsum_cubes(a, b) cube =self.method(:cube).to_proc inc =self.method(:inc).to_proc sum(cube, a, inc, b)endsum_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:defidentity(x) xenddefsum_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 waydefpi_term(x) (1.0/ (x * (x+2)))enddefpi_next(x) (x +4)enddefpi_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:defpi_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.defeven?(i) i %2==0end# at the end, functions that return functionsdeffilter_evens(list) new_list = [] list.eachdo|element| new_list << elementifeven?(element)endnew_listendlist = [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.defmake_filter(predicate)lambdado|list| new_list = [] list.eachdo|element| new_list << elementifpredicate.call(element)endnew_listendendfilter_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(lambdado|i| i.ordinal =~/th$/?true:falseend) 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.