J
Jesse Merriman
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/2007/03/backuss_idea_of_functional_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 * b
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
(e-mail address removed)
http://www.jessemerriman.com/
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/2007/03/backuss_idea_of_functional_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 * b
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
(e-mail address removed)
http://www.jessemerriman.com/
