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/200...ional_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[i] * b[i]

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.velocityreviews.com/forums/(E-Mail Removed)
http://www.jessemerriman.com/