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