Definition of the program notion

When solving complex problems in programming an important role plays definition of the program notion. Depending on the way program is concerned an approach to its construction, as well as its properties, vary. In the paper the program notion is studied and defined based on the theory of parallel programs synthesis on the basis of computational models. The proposed definition conforms to the theory, starting from the description of the problem in the subject domain terms and up to imperative program execution with dynamic properties provided. In programmers’ work it is not usual to employ a precise definition of the program notion. Usually some partial definition is used, which is applicable in particular circumstances. In practice there is no problem with that. Nevertheless, in solving problems of automatic construction of any kind of programs (sequential, parallel, distributed, real-time, numerical, etc.) in various computational model (in various models of informatics) and for different bases it becomes necessary to precisely define the program notion. This allows to precisely define objects and concepts of the theory and practice of informatics and use them in precise proofs/argumentation of various statements in different theories. That’s why we have chosen mathematical logic as the base theory within which all considerations in the papers are made. The theory of synthesis of parallel programs and systems on the basis of computational models was originally formulated in [1] and further studied in [2, 3]. Computational model (CM) is a bipartite directed finite graph, the parts of which form two sets of vertices, called sets of operations and variables. The arcs entering and exiting the operation determine the input and output variables of this operation, respectively. A computational model describes a certain subject domain, where the properties of objects in the subject domain are described by the set of variables (property values are represented by variable values), and the ability to calculate the values of some properties from others is represented by the set of operations (see Fig. 1). CM defines an axiomatic theory. The interpretation function I is defined on the vertices of the graph. Each variable x has the value I(x), and each operation a computes a function I(a). To make computations available each operation has a computational module assigned. An example of such module is a conventional serial subroutine capable of computing values of output variables of the operation, provided values of operation’s input variables are submitted as inputs to the subroutine. Let’s define two subsets on the set of variables of the computational model - V and W, and call them input and output variables of the problem. Values of all variables from V are considered given. In this case, we will say that the VW-problem is posed on a computational model. If in a computational model there is a subset of operations, the ordered application of which to known values of variables will allow obtaining values of new variables until all variables from W obtain values, then this set defines a set of functional terms, each of which calculates one of the variables in W and is calculated from the variables of set V. We will call this set of functional terms a VW-plan (or simply a plan). To solve any VW-problem, generally, zero or more VW-plans can be constructed. Obviously, for a given VW-problem, one can set the task of finding a VW-plan, and if successful, compute the values of all variables from W, given the values of the variables from V. The above allows us to give the following definition of the notion of a program. A program is a description of a process of computation of the values of the interpretation function for the variables included in the VW-plan, and only them. Execution of a plan demands definition of control, i.e. the order in which operations are to be executed. That order must not contradict information dependencies between operations. Also the resources have to be assigned: each variable must have a memory extent to store its value and each operation must have a processor time to execute its corresponding module. Generally both control definition and resources assignment should be done partially statically and the rest - dynamically. This allows to provide static and dynamic properties of the program. Derivation of a VW-plan to solve the formulated problem can also be derived dynamically. The proposed definition of the program notion has a number of advantages, considered in the paper. The advantages include the ability of algorithmic optimizations, the ability to optimize non-functional properties, etc. Also the process of programming in terms of computational models is described. Other program definitions are concerned in comparison.