From: Jesse Merriman <jesse.d.merriman@...>
Date: 2007-03-25T13:49:31+09:00
Subject: 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 <op> (2 <op> (3 <op> 4))
    # instead of: ((1 <op> 2) <op> 3) <op> 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 Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/