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