Higher-Order Procedures Tutorial (long)

Discussion in 'Ruby' started by Nate Murray, Dec 28, 2006.

  1. Nate Murray

    Nate Murray Guest

    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?

    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 <> 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.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 Murray, Dec 28, 2006
    #1
    1. Advertising

  2. Nate Murray wrote:
    > 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?


    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 )
     
    William James, Dec 28, 2006
    #2
    1. Advertising

  3. Nate Murray

    Guest

    On Thu, 28 Dec 2006, Nate Murray wrote:

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


    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
    --
    if you find yourself slandering anybody, first imagine that your mouth is
    filled with excrement. it will break you of the habit quickly enough. - the
    dalai lama
     
    , Dec 28, 2006
    #3
  4. Nate Murray

    Guest

    On Thu, 28 Dec 2006, Nate Murray 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
    --
    if you find yourself slandering anybody, first imagine that your mouth is
    filled with excrement. it will break you of the habit quickly enough. - the
    dalai lama
     
    , Dec 28, 2006
    #4
  5. 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/27/06, <> wrote:
    > On Thu, 28 Dec 2006, Nate Murray 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
    > --
    > if you find yourself slandering anybody, first imagine that your mouth is
    > filled with excrement. it will break you of the habit quickly enough. - the
    > dalai lama
    >
    >



    --
    Giles Bowkett
    http://www.gilesgoatboy.org
    http://gilesbowkett.blogspot.com
    http://gilesgoatboy.blogspot.com
     
    Giles Bowkett, Dec 28, 2006
    #5
  6. On Dec 27, 2006, at 11:11 PM, Giles Bowkett 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 Gray II
     
    James Edward Gray II, Dec 28, 2006
    #6
  7. Nate Murray

    pat eyler Guest

    On 12/28/06, James Edward Gray II <> wrote:
    > On Dec 27, 2006, at 11:11 PM, Giles Bowkett 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...


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

    >
    > James Edward Gray II
    >
    >



    --
    thanks,
    -pate
    -------------------------
    http://on-ruby.blogspot.com
     
    pat eyler, Dec 28, 2006
    #7
  8. Nate Murray

    Sam Smoot Guest

    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.
     
    Sam Smoot, Dec 28, 2006
    #8
  9. On 12/28/06, Sam Smoot <> 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.

    --
    Giles Bowkett
    http://www.gilesgoatboy.org
    http://gilesbowkett.blogspot.com
    http://gilesgoatboy.blogspot.com
     
    Giles Bowkett, Dec 31, 2006
    #9
  10. Re: CSV ORM

    On 1/5/07, Jon Egil Strand <> wrote:
    >
    > 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, Jan 5, 2007
    #10
  11. Re: CSV ORM

    On 1/5/07, Gregory Brown <> wrote:
    > On 1/5/07, Gregory Brown <> 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
     
    Gregory Brown, Jan 5, 2007
    #11
  12. Re: CSV ORM

    On 1/5/07, Gregory Brown <> 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 Brown, Jan 5, 2007
    #12
  13. Re: CSV ORM

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

    > On 1/5/07, Gregory Brown <> 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"]


    Where does the Record class get used? Does the Table class use it
    internally?
     
    Mark Volkmann, Jan 5, 2007
    #13
  14. Re: CSV ORM

    On 1/5/07, Mark Volkmann <> 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.
     
    Gregory Brown, Jan 5, 2007
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jonathan Bartlett

    Higher-Order Programming in C

    Jonathan Bartlett, Mar 31, 2005, in forum: C Programming
    Replies:
    4
    Views:
    305
    Jonathan Bartlett
    Apr 4, 2005
  2. Mark Fink
    Replies:
    3
    Views:
    296
    Arnaud Delobelle
    Dec 22, 2010
  3. Nickolay Kolev

    Higher Order Functions

    Nickolay Kolev, Jul 31, 2005, in forum: Ruby
    Replies:
    5
    Views:
    151
    Nickolay Kolev
    Aug 8, 2005
  4. Victor \Zverok\ Shepelev

    Higher-order messaging in Ruby

    Victor \Zverok\ Shepelev, Oct 11, 2006, in forum: Ruby
    Replies:
    0
    Views:
    125
    Victor \Zverok\ Shepelev
    Oct 11, 2006
  5. Veli-Pekka Tätilä
    Replies:
    2
    Views:
    110
    Veli-Pekka Tätilä
    Apr 2, 2006
Loading...

Share This Page