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