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.
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)
Therefore we can conclude that if
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
f(a)=a then the input
a is called the fixpoint of
f. We can automate the process of composition as follows:
f(a) = athen return the fixpoint
f(a) is not athen 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)
fix correctly computes a fix point of
f starting with input
(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.
Translate the code (methodology) to your favorite programming language.