Essence of Programming

Essence of programming is composition

This micropost is for students taking the first course in Programming and Discrete Structures for Computer Science. It attempts to answer the following question typically raised in the introductory class on discrete structures:

Why do we need to know function composition?

The answer is the title of the post. Let me explain using our old friend, the factorial. We will compute the factorial using only compositons of f as defined next. Function f takes a 3-tuple as input and produces a 3-tuple as output according to the following definition.

• If $x\ge 1$ then $f((r,x,c))=(r\times x,x-1,c)$

• If $x<1$ or $c==1$ then $f((r,x,c))=(r,x,1)$

An implementation of this function f is below in julia. Note that f does not need any variables that are local to the function. A side effect of this definition is that f does not have any side-effect on the state of the variables in the program.

Function $f$ on input (1,4,0) produces (1 $\times$ 4,3,0) as the output as the second entry $x$ in the 3-tuple is $>1$. Notice composition of $f$ with itself is the function $(f\circ f)$ which on input (1,4,0) returns (12, 2, 0). When $x=0$, the last element of the tuple $c$ is $1$ in the output. From then on, no matter how many more times we compose $f$, the output will not change.

Therefore we can conclude that if $f^n=\underset{n\text{ times }}{\underbrace{f\circ f\circ \dots \circ f}}$, then $f^n((1,x,0))$ returns $(x!,0,1)$ for all $n\ge x$. So, using only composition of functions we have computed the factorial of $x$.

The programming language being used allows for function composition to be expressed using the ∘ operator. However, the compositions were done manually, so the next natural question is whether we can automate the process of function composition.

If for an input a, f(a)=a then the input a is called the fixpoint of f. We can automate the process of composition as follows:

• If f(a) = a then return the fixpoint a

• if f(a) is not a then return the fixpoint of function (f ∘ f)(a) where (f ∘ f)(a) = f(f(a)).

The definition below computes the fix point. Such a scheme might not work always, what if the function does not have a fixpoint, or the start point is not the right guess. For our purpose it will work though.

fix correctly computes a fix point of f starting with input (1,7,0) as (7!, 0, 1).

No variables are needed in the input tuple or the output tuple. The function does not have any side-effect on the state of the world, literally. The first argument to the function fix below is a function and the second argument is a 3-tuple.

You have also written your first interpreter to compute solutions to an equation involving functions. you might want to think of other problems that can be solved in a similar fashion.

This paragraph is intended for readers with the knowledge of category: the first two elements r,x of the 3-tuple are a product type Z x Z and the last element c is a sum type 0 | 1. So, the type of the input is Z x Z x ( B | B) in an appropriate distributive category.

Finally, let us compute the facorial for first few integers using the composition. We collect the results of fix(f, (1, x, 0)) in a list and plot them using a library function as a bar chart below. The value of N can be selected using the slider below.

Exercise:

Translate the code (methodology) to your favorite programming language.