As described by Wikipedia, a computer program is a collection of instructions that can be executed by a computer to perform a specific task.
To understand this, let's consider a task of adding any two natural numbers, let's call them \(a\) and \(b\). And if it is known that the computer can compute something similar but simpler tasks, like adding \(1\) to a number \(n\), subtracting \(1\) from a number \(n\), etc. Then, we can simplify our task into a bunch of simpler tasks, like \(a\) times back to back addition of \(1\), starting from \(b\). Thus, this simplified expression of our task is nothing but a computer program. And the set of words/phrases/sentences with a grammar, enabling such simplification is termed as a programming language.
But if we go back to our high school mathematics then we would simply write like following, \[1 + (1 + (1 + \cdots (1 + b \: )) \cdots )\] which will evaluate to the sum of \(a\) and \(b\). This recursion can be emulated in computers if the (underneath) programming language supports functions (and their compositions) - the very same function that is taught in high school mathematics. Functions that usually take arguments but always evaluate to a value. Functions, of which we can form a chain such that the return value of one is an argument of others. \[x \mapsto y\] Being read as "x maps to y", Lambda Calculus denotes it as below. \[\lambda x \: . y\] Therefore, if we treat "performing our task" as a function evaluation (which should not be surprising as functions are the very abstraction of day to day tasks we perform) and, if the programming language has a predefined function which when evaluated performs our simpler tasks, then we can create our "collection of instructions" by \(f\), composing it \(a\) number of times, where \(f\) denotes the function which adds \(1\) to its argument, \(g\) denotes the function which subtracts \(1\) from its argument and, \(F\) denotes the function which when evaluated performs our given task. \[F\: (a,b\: ) \equiv f(f(\cdots (f(b\: )) \cdots ))\] But our computer program is not complete yet because we have not expressed the number of compositions \(f\) has to go. Formally, it can be written like this, \[ F\: (a,b\: ) = \begin{cases}\: b & \text{if} \quad a=0 \\ F\: (g(a),f(b\: )) & \text{otherwise} \end{cases} \] This completes our computer program if the programming language supports function declarations using pattern matching or at least built-in if-then-else function. And just to enlighten this point, let's look at an implementation in Lisp and see for ourselves if it works. Here in Lisp, built-in functions \(f\) and \(g\) are called \(1+\) and \(1-\), respectively.
If our program is a function, then it should evaluate to a value given an argument. That is to say, we should be able to know the value of \(F(3,2)\), for example. Please follow this and "execute" to convince yourself. Thus, we can modify our definition to suit our functional style.
"A computer program is a composition of functions that can be evaluated by a computer to perform a specific task."
But many languages don't support such ways (like "pattern matching", "inductive/recursive constructs", etc) to define functions. Nor many of them have if-then-else defined as a function. In such situations, programs like this would not become what is called, "pure functions". But in the next section, we will see how to use Church encoding to build programs like this into "pure functions".