Functional Programming
ISL research group discussion
6 January 2011
Genre: Programming languages and tools
Speaker: Prabhas Chongstitvatana
Today I would like to discuss Functional Programming paradigm.
The discussion is based on 1977 ACM Turing Award lecture, John Backus,
"Can Programming Be Liberated from the von Neumann Style? A Functional
Style and Its Algebra of Programs", Communication of the ACM, vol.21,
no.8, August 1978, pp.613-641.
<ACM paper>
I will begin with an example of a program written in FP language.
FP is the very original functional language proposed by Backus back in
1977.
<excerpt from the paper>
Def Innerproduct
= (Insert +) . (ApplyToAll
*) . Transpose
Now apply the function
Innerproduct:
<<1,2,3>, <6,5,4>>
=> 28
Please note that there is no "variable" in this language. When I saw it
the first time, I was not believe that it is possible to write computer
programs without variables.
An FP system comprises the following:
1) a set O of objects;
2) a set F of functions f that map objects into objects;
3) an operation, application;
4) a set F of functional forms; these are used to combine existing
functions, or objects, to form new functions in F;
5) a set D of definitions that define some functions in F and assign a
name to each.
Builtin functions
Selector
Tail
Identity
Atom
Equals
Null
Reverse
Distribute from left, from right
Length
Add, subtract, multiply, divide
Transpose
And, or, not
Append left; append right
Right selectors; Right tail
Rotate left; rotate right
Functional form
Composition
(f.g):x = f:(g:x)
Construction
[f1,...fn]:x =
<f1:x,...,fn:x>
Condition
(p ->f;g):x = (p:x) = T
-> f:x;
(p:x) = F -> g:x; bottom
Constant
Insert
ApplyToAll
Binary to unary
Some more example
Def last = null.tail -> 1;
last.tail
last:<1,2> =
(null.tail -> 1;
last.tail):<1,2>
last.tail:<1,2>
since
null.tail:<1,2> =
null:<2>
F
last:(tail:<1,2>)
last:<2>
(null.tail -> 1;
last.tail):<2>
1:<2>
since
null.tail:<2> =
null:0
T
=> 2
Here is a more complicate program, a matrix multiplication program.
Def MM = (ApplyToAll ApplyToAll
Innerproduct).
(ApplyToAll distribute-left) .
distribute-right .
[1, transpose . 2]
We can make Laws of the algebra of programs
For example
[f,g].h =
[f.g, g.h]
We can prove it.
Proposition: For all functions f, g, and h and all objects x,
([f,g].h):x = [f.g, g.h]:x.
Proof:
([f,g].h):x =
[f.g]:(h:x) by
composition
=
<f:(h:x), g:(h:x)> by construction
=
<(f.h):x, (g.h):x> by composition
=
[f.h, g.h]:x by construction
QED
Next I will show some example of writing programs in fuctional
style. I will use LISP-like syntax. (I took these examples from
Samuel Kamin, Programming Languages: An interpreter-based
approach, Addison-Wesley, 1990.)
First I will define a function "mapcar" (similar to ApplyToAll in FP).
It takes a function as an argument.
> (set mapcar (lambda (f l)
(if (null? l)
'()
(cons (f (car l)) (mapcar f (cdr l))))))
> (mapcar number? '(3 a b (5
6)))
(T () () ())
Now I can define a function "add1*" that use "mapcar" to apply a
function to all arguments.
> (set add1* (lambda (l)
(mapcar add 1)))
> (add1* '(3 4 5))
(4 5 6)
Another example where we make use of the fact that applyting a function
can return a function. We show how "curry" turn one-argument function
into two-argument function. It can do that because firstly it
applies the function to the first argument and return a new function
that then applies to the second argument.
> (set curry (lambda (f)
(lambda (x) (lambda (y) (f x y)))))
> (((curry +) 3) 4)
7
> (set mapc (curry mapcar))
> (set add1* (mapc add 1))
> (add1* '(3 4 5))
(4 5 6)
> (set add1** (mapc add1*))
> (add1** '((23) (45)))
((34) (56))
Now I will show you one famous example of building natural number from
pure function. It is called "Church numeral":
(lambda (f) (lambda (x) (f (f …
(f x) … ))))
there are n times of f. this anonymous function represents the number n.
We define "number" as follow:
> (set ZERO (lambda (f)
(lambda (x) x)))
> (set ONE (lambda (f) (lambda
(x) (f x))))
> (set TWO (lambda (f) (lambda
(x) (f (f x)))))
Now define some function to "see" the number:
> (set print-int (lambda (n)
((n +1) 0)))
> (print-int TWO)
2
Can you see how it is done? The magic is that "n" is really a
function!
The number n is represented by
(lambda (f) (f^n), ((n +1 0) =
(+1^n 0) =
(+1 (+1 … (+1 0) … ))
← n
times →
Now we try to define some operation on Church number. The first one is
"add". We start with a simple case, just add one. define plusOne
> (set +ONE (lambda (n)
(lambda (g) (compose g (n g)))))
in general
> (set PLUS (lambda (m n)
(lambda (g) (compose (m g) (n g)))))
since (m g) = g^m and (n g) = g^n, their composition is g^(m+n)
Now, try to use "PLUS", here it is:
> (set THREE (PLUS ONE TWO))
> (print-int THREE)
3
We can do the same for "multiplication"
> (set MULT (lambda (m n)
(compose m n)))
((compose m n) g) = (n (m g)) =
(g^m)^n = g^(mn)
> (set SIX (MULT THREE TWO))
> (print-int SIX)
6
The end of presentation