Backus, Functional Programming, and Ruby

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

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

def inner_product(a, b)
sum = 0
(0…a.length).each do |i|
sum += a[i] * b[i]
end
sum
end

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


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 = lambda do |pair_of_vec|
 pair_of_vec.first.zip(pair_of_vec.last)
end

Returns a Proc that takes a vector of pairs and returns a vector of

whatever

f returns.

apply_to_all = lambda do |f|
 lambda do |vec_of_pair|
  vec_of_pair.map { |pair| f.call(pair.first, pair.last) }
 end
end

Returns a Proc that takes a vector and returns a value of whatever f

returns.

insert = lambda do |f|
 lambda do |vec|
  # The reverse is taken so that, for example, when vec is [1,2,3,4],
the
  # result is:  1 (2 (3 4))
  # instead of: ((1 2) 3) 4
  # (Though its just a convention, and in many cases doesn’t matter)
  vec.reverse.inject { |memo, e| f.call(memo, e) }
 end
end

Returns the composition of f and g as a Proc.

compose = lambda do |f,g|
 lambda { |*args| f.call(g.call(*args)) }
end

Returns the composition of all given functions as a Proc.

compose_all = lambda do |*funcs|
 funcs.reverse.inject { |memo, f| compose.call(f, memo) }
end

Convenience Procs.

add  = lambda { |x,y| x+y }
mult = lambda { |x,y| x*y }

Returns a value: the inner product of a pair of vectors.

inner_product = compose_all.call(
         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]])

Jesse M. 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

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 M. wrote:

functions without any named variables.
module Enumerable
def inner_product
transpose.map(&:*).inject(&:+)
end
end

:stuck_out_tongue:

(Not to slight Backus. Functional programming and BNF are both totally
cool.)

Jesse M. wrote:

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§
http://borasky-research.blogspot.com/

If God had meant for carrots to be eaten cooked, He would have given
rabbits fire.

On 3/25/07, Jesse M. [email protected] wrote:

irb(main):002:1> def inner_product
ruby 1.8.5 (2006-12-04 patchlevel 2) [i686-linux]


Jesse M.
[email protected]
http://www.jessemerriman.com/

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

On Sunday 25 March 2007 19:30, Chris C. 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.

On Sunday 25 March 2007 18:47, Devin M. 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]

oooh, shiny!

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

Devin M. [email protected] writes:

Backus’ code; the goal was to define inner_product as a compose of
(Not to slight Backus. Functional programming and BNF are both totally
cool.)

That’s the most morphologically equivalent to Lisp Ruby ever!

(defun inner_product (matrix)
(reduce '+ (mapcar '* (transpose matrix))))

I’m rusty, but still…

Steve

Yep – I’ve always been a fan of OSOP. (Oooh Shiny Oriented
Programming.)


Giles B.
http://www.gilesgoatboy.org


http://giles.tumblr.com/