Programming

The process of designing programs (cf. Program), a plan of action.

The discipline studying methods and means for designing programs. As a discipline programming can be divided, with a large part of arbitrariness, into theoretical programming, studying mathematical abstractions of programs and ways of constructing them, system programming, occupying itself with the development of software for computers, i.e. of program complexes for large-scale or protracted use, and applied programming, attending to concrete applications of computers in all their variants.

Designing programs is a creative activity, since the attempt to arrive at a goal, even a clearly outlined one, by certain means requires, in general, the development or involvement of new knowledge. In certain particular situations it is possible to find more systematic or formal programming procedures. E.g. if the programming task has already been formulated as an algorithm, programming reduces to a translation from the language in which the algorithm is written, or algorithmic language, into a language that can immediately be accepted by the computer. For certain mathematical models the translation problem has been solved exhaustively. E.g. if a problem is formulated as an existence theorem,

$$ \forall x \exists !y P ( x, y), $$

where $ P ( x, y) $ is a formula in the restricted predicate calculus, then from the proof of the theorem in constructive logic one can effectively extract a recursive description of the functions $ \phi ( x) $ for which $ \forall x P ( x, \phi ( x)) $( the Kleene–Nelson theorem). The attempt to translate the description of the algorithm into a program and to derive the program from the conditions of the problem and additional information in a systematic way forms the subject matter of automatic programming and its particular case, the translation of programs.

The methodics of programming devotes special attention to the ways of describing the initial specification of a problem that needs to be programmed, since a skillful use of the information contained in the specification makes it possible to give a more reliable character to programming. An important aspect of programming is the care for a clear program structure, facilitating the verification of correctness of the program, and most important is the extraction and isolation of those fragments of a program whose further elaboration into details requires that new knowledge be invoked.

A conception of the way of transition from the specification of a problem to a program is given by the following example of programming, viz. the problem of raising $ x $ to a natural power $ n $.

The initial knowledge: $ x ^ {1} = x $, $ x ^ {n + m } = x ^ {n} \cdot x ^ {m} $, $ x ^ {nm} = ( x ^ {n} ) ^ {m} $. Discovering that these relations allow one to reduce the solution of the problem of $ x ^ {n} $ to simpler ones (i.e. with lesser $ n $), one attempts to specify the initial knowledge in the simple form (a creative step):

$$ x ^ {0} = 1,\ \ x ^ {n + 1 } = x ^ {n} \cdot x,\ \ x ^ {2n} = ( x ^ {n} ) ^ {2} . $$

Analysis of the content shows that the third relation is more effective than the second, but is not always applicable. The second relation is re-written, keeping in mind the case complementary to the third relation (a creative step):

$$ x ^ {0} = 1,\ \ x ^ {2n + 1 } = x ^ {2n} \cdot x,\ \ x ^ {2n} = ( x ^ {n} ) ^ {2} . $$

By using the invertibility of the functions $ n \mapsto 2n $ and $ n \mapsto n + 1 $ as well as the logical incompatibility of the relations, one obtains a recursive relation by the method of sorting out cases (a formal step):

$$ x ^ {n} = \ \textrm{ if } \ \left \{ \begin{array}{ll} n = 0, & \textrm{ then } 1; \\ n \textrm{ even } , & \textrm{ then } ( x ^ {n/2} ) ^ {2} ; \\ n \textrm{ odd } , & \textrm{ then } x \cdot x ^ {n - 1 } . \\ \end{array} \right .$$

It remains to re-write this rule in some algorithmic language, e.g. Algol-60 (a formal step):

$ {\mathbf{real} procedure } power ( x, n); {\mathbf{real} } x, {\mathbf{integer} } n $;

$ power : = \mathbf{i f } n = 0 {\mathbf{then} } 1 {\mathbf{else} } $

$ \mathbf{i f } even ( n) {\mathbf{then} } power ( x, n/2) \uparrow 2 {\mathbf{else} } x \times power ( x, n - 1) $.

The determination of a procedure to check the parity $ even ( n) $ is a separate, more particular, programming problem.

An important component of programming is to check the correctness of a program. One way to ensure correctness is to specify the procedure of programming in a form that resembles the proof of a theorem, i.e. when each formation step of the program can be associated with a reasoning by means of which the consistency of this step can be confirmed with the initial knowledge on the program and the additional information used in the step. The formal deductive system that arises in this way is also studied in theoretical programming. An additional means for checking correctness of an already compiled program is systematic execution, i.e. systematic testing on a computer and comparing the effects generated by the program with the expected effects. Although in practice systematic execution is the most important means of checking a program, theoretically it cannot be exhaustive, since the establishment of correctness of a program by a finite system of tests can be realized for very narrow classes of problems only (cf. Automata, theory of).

References

[1]	E.Z. Lyubimskii, V.V. Martinyuk, N.P. Trifonov, "Programming" , Moscow (1980) (In Russian)
[2]	E.W. Dykstra, "A discipline of programming" , Prentice-Hall (1976)
[3]	B. Meyer, C. Baudoin, "Méthodes de programmation" , 1–2 , Eyrolles (1978)

References

[a1]	D. Gries, "The science of programming" , Springer (1981)