When a programmer writes a program to solve a problem, the programmer and the program are solving entirely different problems. The program is going through a series of steps that result in a solution to a problem of interest. The programmer is devising a series of steps that, when followed, result in a solution. The programmer is operating at one remove from the problem. The program solves the problem; the programmer solves a meta-problem, that is, a problem about the problem. The programmer does not need to be able to solve the problem. However, the programmer must devise a process which, when followed, results in a solution.
Just as a playscript is a static representation (the script) of a set of dynamic behavior (the play), a program is a static representation of an instance of program execution. But while the sequence of events in a play is more or less fixed, the sequence of events in a program execution is adaptive. Most programs contain tests of conditions, and modify their behavior depending on the results of these tests. It would be as if the script for a play were to contain instructions such as “if the third person in the front row is a critic, insert this scene here.” Such adaptation to particular conditions is unheard of in the world of plays, but is common in programs. While a troupe is not expected to adapt to unexpectedly playing before an audience understanding French instead of English, a program is expected to adapt to unexpectedly finding impossible, even meaningless, data — such as a length being specified as negative. The adaptation may be to halt with an error message, but the program has to do something.
As an example of programming as process design, consider the problem of determining the factorial of a number. The factorial of a number is defined as:
n! = n × n-1 × n-2 × ... × 1
Were a human to compute the factorial of 5, the human would likely arrange the problem as follows:
5! = 5 × 4 × 3 × 2 × 1
= 20 × 6
= 120
A computer, on the other hand, would go through a process like the following:
The steps the computer goes through are the results of what is called an algorithm. An algorithm is a process which, when followed, yields the result of interest. Describing, and to an extent discovering, the algorithm is the problem facing the programmer. The steps above result from the following algorithm:
(We will analyze why this algorithm works later.)
There are many ways of representing an algorithm. The above represents the algorithm as a series of numbered imperative statements in English. The following represents the same algorithm as a flowchart:
The following represents the same algorithm in the JavaScript language:
function Factorial (x) { var f = 1; for (var i = 1; i <= x; i ++) { f = f * i; } return f; }
The following represents the same algorithm in Visual Basic for Applications:
Private Function Factorial(ByVal n As Long) As Double Dim lIndex As Long Dim dProduct As Double dProduct = 1 For lIndex = 1 To n dProduct = dProduct * lIndex Next lIndex Factorial = dProduct End Function
The following represents the same algorithm in the Casio FX-7400G and CFX-9850G programming language:
1→B For 1→A To X AB→B Next B
There are other algorithms that yield the same result. For example,
n! = n × n-1 ×
n-2 × ... × 1, or
n! = n × (n-1 ×
n-2 × ... × 1), or
n! = n × (n-1)!
This recursive definition defines the factorial function in terms of itself. The corresponding recursive algorithm can be expressed in Visual Basic for Applications as:
Private Function Factorial(ByVal n As Long) As Double If n <= 1 Then Factorial = 1 Else Factorial = n * Factorial(n - 1) End If End Function
As we have seen, a program is an expression of an algorithm in terms of the context in which the computation is to take place. The craft of programming is that of defining a computational process and a minimal context such that the process, when followed in the context, provides answers to problems.
[ Previous page | Top of page | Next page ]
Copyright © 2001 Brian Hetrick
Page last updated 30 December 2001.
Tutorial
Fundamentals
Process Design
Modularization
Data Structures I
Recursion
Program Attributes
Building Blocks II
Algorithm Analysis
Structuring
Data Structures II
Abstract Types
Objects
Problem Analysis
Reference Card