Backus, Functional Programming, and Ruby

Discussion in 'Ruby' started by Jesse Merriman, Mar 25, 2007.

  1. Recently, John Backus, the father of Fortran, died. In 1977 he won the Turi=
    ng=20
    Award, and gave a lecture promoting functional programming. The lecture can=
    =20
    be accessed here:

    =C2=A0 http://www.stanford.edu/class/cs242/readings/backus.pdf

    and an interesting blog post about it is here:

    =C2=A0=20
    http://scienceblogs.com/goodmath/2007/03/backuss_idea_of_functional_pro_1.p=
    hp

    In section 5 of the lecture an example is given comparing calculation of th=
    e=20
    inner product of two vectors in an imperative style versus a functional=20
    style. I thought it'd be fun to try to write it (functionally) in Ruby, and=
    I=20
    think it came out rather nifty, so I thought I'd post it here. The basic id=
    ea=20
    is to define an inner_product function as the compose of 3 other functions =
    (a=20
    sum insert, multiply mapping, and transpose), instead of doing it iterative=
    ly=20
    like this:

    def inner_product(a, b)
    sum =3D 0
    (0...a.length).each do |i|
    sum +=3D a * b
    end
    sum
    end

    Below is my more functional solution. Most of it is defining functions for=
    =20
    doing composes and such, and then almost at the end inner_product is define=
    d=20
    as Backus would've liked.

    =2D--------------------------------------------------------------------
    # Ruby implementation of John Backus' functional inner product example, from
    # section 5.2 of his 1977 Turing Award Lecture, available here:
    # http://www.stanford.edu/class/cs242/readings/backus.pdf

    # Returns the transpose of a pair of vectors as a vector of pairs.
    transpose =3D lambda do |pair_of_vec|
    =C2=A0 pair_of_vec.first.zip(pair_of_vec.last)
    end

    # Returns a Proc that takes a vector of pairs and returns a vector of whate=
    ver
    # f returns.
    apply_to_all =3D lambda do |f|
    =C2=A0 lambda do |vec_of_pair|
    =C2=A0 =C2=A0 vec_of_pair.map { |pair| f.call(pair.first, pair.last) }
    =C2=A0 end
    end

    # Returns a Proc that takes a vector and returns a value of whatever f
    # returns.
    insert =3D lambda do |f|
    =C2=A0 lambda do |vec|
    =C2=A0 =C2=A0 # The reverse is taken so that, for example, when vec is [1,2=
    ,3,4], the
    =C2=A0 =C2=A0 # result is: =C2=A01 <op> (2 <op> (3 <op> 4))
    =C2=A0 =C2=A0 # instead of: ((1 <op> 2) <op> 3) <op> 4
    =C2=A0 =C2=A0 # (Though its just a convention, and in many cases doesn't ma=
    tter)
    =C2=A0 =C2=A0 vec.reverse.inject { |memo, e| f.call(memo, e) }
    =C2=A0 end
    end

    # Returns the composition of f and g as a Proc.
    compose =3D lambda do |f,g|
    =C2=A0 lambda { |*args| f.call(g.call(*args)) }
    end

    # Returns the composition of all given functions as a Proc.
    compose_all =3D lambda do |*funcs|
    =C2=A0 funcs.reverse.inject { |memo, f| compose.call(f, memo) }
    end

    # Convenience Procs.
    add =C2=A0=3D lambda { |x,y| x+y }
    mult =3D lambda { |x,y| x*y }

    # Returns a value: the inner product of a pair of vectors.
    inner_product =3D compose_all.call(
    =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 insert.call(=
    add), apply_to_all.call(mult), transpose)

    # Test case from the lecture. Should print out 28.
    puts inner_product.call([[1,2,3], [6,5,4]])
    =2D--------------------------------------------------------------------

    =2D-=20
    Jesse Merriman

    http://www.jessemerriman.com/
     
    Jesse Merriman, Mar 25, 2007
    #1
    1. Advertising

  2. Jesse Merriman wrote:
    ...
    > # Test case from the lecture. Should print out 28.
    > puts inner_product.call([[1,2,3], [6,5,4]])
    > ---------------------------------------------------------------------


    Ruby has its own way of doing things, not that there is anything wrong
    with defining new ways:

    [[1,2,3], [6,5,4]].transpose.map{|x,y|x*y}.inject{|s,x|s+x}
    => 28

    --
    vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
     
    Joel VanderWerf, Mar 25, 2007
    #2
    1. Advertising

  3. On Sunday 25 March 2007 18:03, Joel VanderWerf wrote:
    > Ruby has its own way of doing things, not that there is anything wrong
    > with defining new ways:
    >
    > [[1,2,3], [6,5,4]].transpose.map{|x,y|x*y}.inject{|s,x|s+x}
    > => 28


    Yep, I was just seeing how close I could make Ruby code look like Backus'
    code; the goal was to define inner_product as a compose of the three other
    functions without any named variables.

    --
    Jesse Merriman

    http://www.jessemerriman.com/
     
    Jesse Merriman, Mar 25, 2007
    #3
  4. Jesse Merriman wrote:
    > On Sunday 25 March 2007 18:03, Joel VanderWerf wrote:
    >
    >>Ruby has its own way of doing things, not that there is anything wrong
    >>with defining new ways:
    >>
    >>[[1,2,3], [6,5,4]].transpose.map{|x,y|x*y}.inject{|s,x|s+x}
    >>=> 28

    >
    > Yep, I was just seeing how close I could make Ruby code look like Backus'
    > code; the goal was to define inner_product as a compose of the three other
    > functions without any named variables.


    module Enumerable
    def inner_product
    transpose.map(&:*).inject(&:+)
    end
    end

    :p

    (Not to slight Backus. Functional programming and BNF are both totally
    cool.)
     
    Devin Mullins, Mar 25, 2007
    #4
  5. On Sunday 25 March 2007 18:47, Devin Mullins wrote:
    > module Enumerable
    > def inner_product
    > transpose.map(&:*).inject(&:+)
    > end
    > end


    That looks good, but is it right?

    irb(main):001:0> module Enumerable
    irb(main):002:1> def inner_product
    irb(main):003:2> transpose.map(&:*).inject(&:+)
    irb(main):004:2> end
    irb(main):005:1> end
    => nil
    irb(main):006:0> [[0,1,2], [6,5,4]].inner_product
    TypeError: wrong argument type Symbol (expected Proc)
    from (irb):3:in `inner_product'
    from (irb):6

    $ ruby --version
    ruby 1.8.5 (2006-12-04 patchlevel 2) [i686-linux]

    --
    Jesse Merriman

    http://www.jessemerriman.com/
     
    Jesse Merriman, Mar 26, 2007
    #5
  6. Jesse Merriman wrote:
    > Recently, John Backus, the father of Fortran, died. In 1977 he won the Turing
    > Award, and gave a lecture promoting functional programming. The lecture can
    > be accessed here:
    >
    > http://www.stanford.edu/class/cs242/readings/backus.pdf
    >
    > and an interesting blog post about it is here:
    >
    >
    > http://scienceblogs.com/goodmath/2007/03/backuss_idea_of_functional_pro_1.php
    >

    Well ... let me throw a bit of historical perspective into the mix:

    1. I read the article when it was published. At the time, I was working
    as a mainly assembly language programmer in real-time operating systems.
    I was quite familiar with functional programming styles, Lisp (1.5), the
    lambda calculus and combinatory logic, and I was studying the formal
    semantics of programming languages. The article resonated with me for
    those reasons. However, I found it difficult to read in context with the
    other computer science I was studying.

    2. A few years later, functional languages, so-called single-assignment
    languages and dataflow programming paradigms started to make an
    appearance during the renaissance of high-performance scientific
    computing that occurred during the Reagan years. Despite their
    advantages, these, like the Backus paper, withered on the academic vine.

    3. Maybe the time is *finally* ripe for the functional programming
    paradigm to establish a firm commercial and business presence, given at
    least a few useful applications written in Haskell, Erlang and OCaml.
    After all, FORTRAN I came out in 1957 and LISP I only three years or so
    later. I date the start of Lisp from McCarthy's 1960 paper, but I'm not
    sure when the first actual LISP interpreter was put into operation.
    Maybe ... but it's been about 50 years and the Von
    Neumann/FORTRAN/imperative paradigm has continued to dominate the
    computing world. The Church/McCarthy/LISP/Functional paradigm has held
    its own -- once there were Lisp machines, after all -- but it is a
    distinct second place runner.


    --
    M. Edward (Ed) Borasky, FBG, AB, PTA, PGS, MS, MNLP, NST, ACMC(P)
    http://borasky-research.blogspot.com/

    If God had meant for carrots to be eaten cooked, He would have given rabbits fire.
     
    M. Edward (Ed) Borasky, Mar 26, 2007
    #6
  7. Jesse Merriman

    Chris Carter Guest

    On 3/25/07, Jesse Merriman <> wrote:
    > On Sunday 25 March 2007 18:47, Devin Mullins wrote:
    > > module Enumerable
    > > def inner_product
    > > transpose.map(&:*).inject(&:+)
    > > end
    > > end

    >
    > That looks good, but is it right?
    >
    > irb(main):001:0> module Enumerable
    > irb(main):002:1> def inner_product
    > irb(main):003:2> transpose.map(&:*).inject(&:+)
    > irb(main):004:2> end
    > irb(main):005:1> end
    > => nil
    > irb(main):006:0> [[0,1,2], [6,5,4]].inner_product
    > TypeError: wrong argument type Symbol (expected Proc)
    > from (irb):3:in `inner_product'
    > from (irb):6
    >
    > $ ruby --version
    > ruby 1.8.5 (2006-12-04 patchlevel 2) [i686-linux]
    >
    > --
    > Jesse Merriman
    >
    > http://www.jessemerriman.com/
    >
    >


    He is assuming you have the famed "Symbol#to_proc" method, you can
    find it with a quick google.

    --
    Chris Carter
    concentrationstudios.com
    brynmawrcs.com
     
    Chris Carter, Mar 26, 2007
    #7
  8. On Sunday 25 March 2007 19:30, Chris Carter wrote:
    > He is assuming you have the famed "Symbol#to_proc" method, you can
    > find it with a quick google.


    Ah, very nice. Very nice.

    --
    Jesse Merriman

    http://www.jessemerriman.com/
     
    Jesse Merriman, Mar 26, 2007
    #8
  9. > > He is assuming you have the famed "Symbol#to_proc" method, you can
    > > find it with a quick google.

    >
    > Ah, very nice. Very nice.


    I think this technique is massively underutilized. Imagine what it
    would be like if overriding to_proc was a standard technique for all
    kinds of objects. Things could get really weird.

    (In a good way.)

    --
    Giles Bowkett
    http://www.gilesgoatboy.org
    http://gilesbowkett.blogspot.com
    http://giles.tumblr.com/
     
    Giles Bowkett, Mar 26, 2007
    #9
  10. Jesse Merriman

    SonOfLilit Guest

    oooh, shiny!

    On 3/26/07, Giles Bowkett <> wrote:
    > > > He is assuming you have the famed "Symbol#to_proc" method, you can
    > > > find it with a quick google.

    > >
    > > Ah, very nice. Very nice.

    >
    > I think this technique is massively underutilized. Imagine what it
    > would be like if overriding to_proc was a standard technique for all
    > kinds of objects. Things could get really weird.
    >
    > (In a good way.)
    >
    > --
    > Giles Bowkett
    > http://www.gilesgoatboy.org
    > http://gilesbowkett.blogspot.com
    > http://giles.tumblr.com/
    >
    >
     
    SonOfLilit, Mar 26, 2007
    #10
  11. Yep -- I've always been a fan of OSOP. (Oooh Shiny Oriented Programming.)

    --
    Giles Bowkett
    http://www.gilesgoatboy.org
    http://gilesbowkett.blogspot.com
    http://giles.tumblr.com/

    On 3/26/07, SonOfLilit <> wrote:
    > oooh, shiny!
    >
    > On 3/26/07, Giles Bowkett <> wrote:
    > > > > He is assuming you have the famed "Symbol#to_proc" method, you can
    > > > > find it with a quick google.
    > > >
    > > > Ah, very nice. Very nice.

    > >
    > > I think this technique is massively underutilized. Imagine what it
    > > would be like if overriding to_proc was a standard technique for all
    > > kinds of objects. Things could get really weird.
    > >
    > > (In a good way.)
    > >
    > > --
    > > Giles Bowkett
    > > http://www.gilesgoatboy.org
    > > http://gilesbowkett.blogspot.com
    > > http://giles.tumblr.com/
    > >
    > >

    >
    >
     
    Giles Bowkett, Mar 26, 2007
    #11
    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. Casey Hawthorne
    Replies:
    4
    Views:
    1,026
    Jarek Zgoda
    Aug 4, 2006
  2. Kenneth Brody

    Sorta-OT: John Backus obit

    Kenneth Brody, Mar 21, 2007, in forum: C Programming
    Replies:
    5
    Views:
    298
    Nick Keighley
    Mar 22, 2007
  3. Replies:
    23
    Views:
    544
    Robert Klemme
    Mar 13, 2013
  4. Replies:
    7
    Views:
    306
    Arved Sandstrom
    Mar 15, 2013
  5. Replies:
    1
    Views:
    304
    Arne Vajhøj
    Mar 15, 2013
Loading...

Share This Page