### 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

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

or$x<1$ then$c==1$ $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.

`f (generic function with 1 method)`

`xxxxxxxxxx`

`# input is a 3-tuple (r, x, c)`

`# output is a 3-tuple (r', x', c')`

`# f: Z x Z x {0,1} -> Z x Z x {0,1}`

``

`function f((r, x, c)) `

` if ( x >= 1) return (r*x, x-1, c) end`

` if ( x < 1) || (c == 1) return (r, x, 1) end`

`end`

``

`# Note that there are no variables local to the function`

Function

Therefore we can conclude that if

4

3

0

`xxxxxxxxxx`

`(f)((1,4,0))`

12

2

0

`xxxxxxxxxx`

`(f ∘ f)((1,4,0))`

24

1

0

`xxxxxxxxxx`

`(f ∘ f ∘ f)((1,4,0))`

24

0

0

`xxxxxxxxxx`

`(f ∘ f ∘ f ∘ f)((1,4,0))`

24

0

1

`xxxxxxxxxx`

`(f ∘ f ∘ f ∘ f ∘ f)((1,4,0))`

24

0

1

`xxxxxxxxxx`

`(f ∘ f ∘ f ∘ f ∘ f ∘ f)((1,4,0))`

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 (generic function with 1 method)`

`xxxxxxxxxx`

`# compose f with itself until the output does not change`

``

`function fix(f, in) # f is a function, in is the input to f`

` if f(in) == in return in end # output is the same as input`

` return fix(f, f(in)) # (f ∘ f)(x)= f(f(x))`

`end`

``

`# your first interpreter, that computes fixpoints`

`fix`

correctly computes a fix point of `f`

starting with input `(1,7,0)`

as `(7!, 0, 1)`

.

5040

0

1

`xxxxxxxxxx`

`fix(f,(1,7,0))`

Note

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.

`xxxxxxxxxx`

`plot([fix(f,(1,x,0))[1] for x=1:N], seriestype=:bar)`

**Exercise:**

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