Keldysh Institute for Applied Mathematics   M.M.Gorbunov-Possadov

M.M.Gorbunov-Possadov

THE WAY TO GROW A PROGRAM

During the life cycle every large program undergoes revolutionary and evolutionary alterations. Revolutionary alterations transform the program radically, however the need for them arises infrequently. As a rule, the bulk of the programmer's activity is expended on evolutionary alterations. The evolution of the program takes place in rather small steps called transactions. At each step the code produced by the previous transaction almost does not vary, but the component realizing new functionality, i.e. a new use case, is added to it. The problem to coordinate the structures of the program and the transaction is as follows. The new component must join naturally into the existent collection of program modules. The evolutionary alteration must take place non-intrusively; it must threaten to program's ability to work.

1. Horizontal layers

As early as the Seventies A. L. Fuksman [1] called attention to how the structure of a the program component that is being added is usually divided into modules. The component being added usually relates to several extant structural formations, the so-called "horizontal layers" of the given program. In each horizontal layer some aspect of program realization is localized. If the component being added is sufficiently non-trivial, it will simultaneously influence several layers.

Now the concept of the horizontal layer is becoming popular in the West as well. Not infrequently [2, 3] the general structure of the program is represented in the form of the "square-cluster" scheme (Fig. 1).

Fig. 1. "Square-cluster" scheme of a program

Here, horizontal ovals represent horizontal layers, vertical dotted rectangles represent components. Usually, at the intersection of an oval and a rectangle the name of a module is written. There are no module names shown in Fig. 1; asterisks without names are being used to indicate those elements of the layer that are actually present in the program. The fact is that the component, of course, does not need to be present in all horizontal layers. If the program is complex, then the matrix similar to Fig. 1 may be rather sparse.

The role allotted to the subroutines is usually that of elementary building blocks, or rather, terminal leaves for growing tree of a program. Such a leaf can be either written anew or borrowed from the library. Neither choice is likely to present any difficulties. Though, if any other part of the program tree is to be reused, then somewhat more complicated constructs must be applied.

We cite two examples. Suppose someone is writing an article. Here, the new component being added to the article is a new section. The text of the new section is placed on the horizontal layer "Main text". However, that is not all. Probably, some new citations will be added to the bibliography, i.e. to the horizontal layer "References". New lines will appear in glossary, and so on.

In the second example someone is developing a text editor. A new component is the realization of a context-sensitive search operation. Of course, the bulk of the new source code will be placed on the horizontal layer "Realization of basic operations". But some additions will be needed as well to the horizontal layer "Menu of operations" and, probably, "Table of hot keys".

As it might appear at first sight on rectangular contours of Fig. 1, the horizontal and vertical directions are symmetric or, more properly, interchangeable. But on second thought this conclusion appears to be false. These two directions differ in the essential nature.

The horizontal layers are organically necessary, irremovable parts of the program. The program, being deprived of any of the horizontal layers, most likely can neither be debugged or run successfully. Indeed, the isolated bibliography without the main text of the article cannot even be called a subassembly of the article. The isolated table of hot keys cannot be executed; it says almost nothing about the program containing it. If the text editor has no menu of operations, then how can it be run, or even debugged?

On the contrary, components ("the vertical layers" using Fuksman’s terminology) only expand the functionality of the program, which, if only in some truncated form, may function without them. Thus the article with several sections yet missing may well be shown to a colleague: he probably will be able to understand the subject and to make useful comments. A text editor that does not yet have context-sensitive search can not only be debugged, but can even be run successfully.

Hence with a large program it is convenient to put off the realization of vertical layers. This characteristic of the vertical layer was first noted by Fuksman [1], and served as the starting point for his suggested strategy of stepwise program development. According to Fuksman, for the first step the developer realizes an extremely simplified version of the program (what is left over from removing all vertical layers). Then, during the next stages (transactions), more and more new vertical layers are realized and added to the program that is being developed this way. The noteworthy advantage of this strategy is that each intermediate version of the program (missing some vertical layers) can be debugged without creating stubs (dummies), as is necessary in the well-known stepwise program refinement strategies "top-down" and "bottom-up".

The authors of [2, 3] arrive at the same structure of the program-extending component by a somewhat different path. Here the component is considered in connection with reuse. It is noted that the established stereotype of representing a reusable program component as a relatively independent subroutine or a class unjustifiably underemphasizes mechanisms of interaction between the component and the program using it. Substantially more fruitful is a representation of a program as a totality of horizontal layers, in each of which the component that is being added has the right to leave its traces.

One way or another, there are weighty reasons to design each transaction of program evolution in terms of adding of a new component, i.e. a new vertical layer. In general this component is composed of modules intended for several horizontal layers of the program. Probably, a mathematician would say here: "Each regular alteration of the program is decomposable into the basis of horizontal layers". This decomposition applies both to the program's own parts as well as to externally reusable components. In what follows, we will not be much interested in the genesis of program evolution materials, and the terms "vertical layer" and "component" will be used basically as synonyms.

2. Two-dimensional structure of a program

The realization of horizontal and vertical layers runs up against the following contradiction. Here the program structure, in essence, is two-dimensional, but the popular algorithmic languages assume one-dimensional representation of the source text. As a result, the developer is forced to decide between the two. If he designs the horizontal layers in form of continuous blocks of the source text, then the modules forming the vertical layer will be at some distance from each other. But if the vertical layers are designed in the form of continuous blocks, then the horizontal layer will be broken apart. The seriousness of the contradiction under consideration can be illustrated with the technological decisions taken in the articles mentioned above.

Fuksman [1] prefers representing the horizontal layers as continuous blocks. On this account the vertical layer becomes dispersed and then the special cumbersome construct "lumped description of distributed vertical layer" is required. Without this construct the vertical layer would dissolve irretrievably in the program text, and doing this would be shortsighted at the least. First, the vertical layer is an essential element of the program structure; it is extremely useful to see its outlines in subsequent analysis of the source text. Secondly, quite often it is required to cancel the installation of one of the vertical layers, and there is no easy way to do this without the lumped description.

On the contrary, in the articles [2, 3] the components turn out to be represented as continuous blocks, and, consequently, the horizontal layers are dispersed. The components are designed in the form of classes or objects containing elements of the horizontal layers. Serious effort is required here to organize the functioning of a horizontal layer as a single whole. The readability of the source text also has some disadvantages: it can be difficult to observe the current composition of a horizontal layer. Finally, the dispersion of a horizontal layer into several classes often results in a noticeable loss of efficiency of the code: the programmer is forced to transform tables into lists, etc.

The way out of the contradiction produced by two-dimensional program structure is rather obvious. Programming tools are needed to support two dimensions. The concepts of horizontal and vertical layer should be reflected in the programming environment. Then the developer will be able to use simple and reliable basic operations to install/uninstall the vertical layer on a daily basis. When studying the program text, it will be possible to see the horizontal as well as the vertical constructs. Nevertheless, the programming environment tools will generate a one-dimensional text of the program to be fed into the conventional compiler.

3. Module declaration

For the programming environment to be able to support two dimensions, it is necessary to form the transaction of the program evolution into a certain structure. First, the component being installed, i.e. the vertical layer, should be decomposed into modules intended for various horizontal layers. Secondly, an efficient method to install these modules in the receiving program should be proposed.

Let's begin with the decomposition of a component being installed. It is required, that the component defines in some way the set of declarations of the constituent modules intended to be installed in specified horizontal layers. The following construct of the module declaration may be proposed:

In the first line the name_of_horizontal_layer, for which the module being declared is intended, is given.

The braces bordering the second line mean that the enclosed element may be reproduced one or several times. Thus the way for the declaration of a compound module is introduced: the name and value of one of fields defines each instance of an element.

For what purpose could the module field be needed? Let us turn back again to our examples. In the module of an article section intended for the horizontal layer “Main text,” it is worthwhile to separate the fields "Heading" and "Text". Then it will be possible to uniformly format all headings and to mechanically construct the table of contents. It is worthwhile to separate out the field "Author" in the bibliographic references. Then it will be possible to italicize the authors’ last names in the bibliography. When defining a hot key of the text editor (which is defined by means of a certain structure, more precisely, a set of constants), it is worthwhile to separate the values of constants as the independent fields of a module instead of forming this definition as flat text in a declaration. Then a considerable gain in size and flexibility of code will be obtained.

The next element of the module declaration is #APPLY. The bordering square brackets mean that this element may be omitted. #APPLY is used in nested declarations only. By means of #APPLY the application is specified that remains in the source code of the containing module after preprocessing of the #INSTALL_IN construct. The application is an arbitrary text in the source language. Among this text the values of the fields of the module being declared may be placed. These values are specified as place-holders of the form: #name_of_horizontal_layer.name_of_field.

The nested declarations may be needed when the modules forming the component are closely related. Let's illustrate the interdependency of modules by the above example of an article section involving bibliographic references. Where should the declaration of a module of the bibliographic reference be placed? Best of all is to embed it directly in the main text of the section. Then, when the text fragment containing the reference is deleted, the software will correct the composition of the bibliography automatically. However, the text of a section is also represented as an independent module — more precisely, as the field "Text" of the module intended for the horizontal layer "Main text". Thus, here it is required to declare the module of the bibliographic reference inside the declaration of another module.

Suppose, for example, the reference to E.Dijkstra "A Discipline of Programming" should be included in the text of a section. In the final text of publication the reference should take the form "[Dij76]". In this case the following lines will be entered into the section text

Thus on installing the section in the repository of the article a new module composed of the "Name", "Author", and "Text" fields will be added to the horizontal layer "References". The #APPLY will provide the presence of the desired reference "[Dij76]" in the final publishable text of the section.

4. Homogeneity of modules

The construct offered above makes it possible to declare a component being installed in the program as a composition of several modules intended for various horizontal layers. Now we have to decide how to determine in which the locations in the program text to install the new modules. To define the locations turns out to be rather easy, thanks to an enormously important feature of the horizontal layer: the modules comprising horizontal layer are homogeneous.

Here by homogeneity of modules is meant not only unity of their purposes (semantics and pragmatics), but also their perfect syntactic uniformity. The modules consist of fields. Homogeneity means that the composition of the fields will be one and the same for all the modules in a horizontal layer, and the values of fields of the same name are in turn homogeneous.

To illustrate homogeneity of modules we return to the above examples of horizontal layers. In the first example a component (new section) is being added to the article being prepared. The horizontal layer "Main text" is being generated from the uniformly designed modules (sections); the horizontal layer "References" is being generated from the uniformly designed bibliographic references, etc. Each module of layer "Main text" includes the field "Heading", and all of these fields are designed uniformly.

In the second example a new operation is being added to the text editor being developed. The horizontal layer "Realization of basic operations" consists of homogeneous procedures. The horizontal layer "Menu of operations" is an array of homogeneous structures (constants). The "Table of hot keys" is an array of homogeneous structures too, but, of course, the structures "Menu of operations" and "Table of hot keys" are of different types.

Each transaction expanding the program has a well-defined structure: it can be represented as a series of extensions of the horizontal layers that are present. A transaction can have no effect on some horizontal layers, or can add one module or several modules to some other horizontal layers. For one operation of the text editor no hot keys are bound, for another operation one hot key is bound, for a third operation several hot keys are bound, for example, Ctrl+F and F11. Each horizontal layer establishes the format of its own modules; in other words, all the modules being installed in the layer are homogeneous elements of the same format. Fig. 2, as well as Fig. 1, shows the program structure based on horizontal layers. But here the homogeneity of modules belonging to the same layer and the variety of formats of modules belonging to various layers is illustrated.

Fig. 2.  Homogeneous modules of horizontal layers.
The modules installed in the program by the latest transaction are shaded

5. Representation of a horizontal layer

So a horizontal layer has absorbed all the homogeneous modules directed to it from the components installed in the program. Then this set of homogeneous modules should somehow turn into a programming language text in order to be suitable for compilation. In what follows, we shall consider the representation of the horizontal layer in the program text.

It turns out that the horizontal layer can take form of any homogeneous language construct. There are a lot of homogeneous constructs in popular programming languages. For example, constants in a constant array are homogeneous, branches in a case operator are homogeneous, etc. Even the most frequently used construct such as a group of actions being parallel or sequentially executed is composed of homogeneous operators.

In the source text a horizontal layer is written in the form of a compilation time loop statement [4]. The loop repeats as many times as there are modules installed in the layer by components included to the program. At the same time a loop variable runs sequentially through all the modules being installed in the layer. The loop statement is allocated in the immediate text of the program and takes the following form:

#HORIZON and #END_OF_HORIZON outline a loop body. By means of the name_of_layer a horizontal layer is specified and at the same time serves as the loop variable that runs sequentially through all the modules of the layer. The loop_body is an arbitrary text in the programming language. This text will be reproduced repeatedly at compilation time. The fields of the current module of the horizontal layer are placed in the text. Each field takes the form of an place-holder:

#name_of_layer.name_of_field

As stated above, the number of loop repetitions is governed by the number of homogeneous modules in the horizontal layer. Each repetition results in the addition of a new copy of the loop body to the program text being generated. In so doing, the text values of specified fields of the current module are substituted for the place-holder.

It is assumed that more than one of the #HORIZON constructs specifying the same horizontal layer can be placed in the source text. For example, in the article the horizontal layer "Main text" will be used at least twice: to form the publishable main text of the article and to form a table of contents. The table of contents will be constructed from the "Heading" fields only.

Let's return to the above example of bibliographic references representation. For concreteness, we assume that a paper is being prepared for Internet publication and consequently is being written in HTML. (We consciously choose a non-algorithmic language such as HTML for illustration. Today the overwhelming majority of programmers are familiar with HTML. The enthusiasts of C, Pascal, and other popular programming languages can find a score of more programmer-oriented examples in [4].) All references declared in the text of article can be brought together in the single bibliography by means of the following construct

All the references will be arranged one after another, and each of them will be represented as the five lines in HTML. The reference to E.Dijkstra "A Discipline of Programming" (mentioned above) is represented as follows

As a result of processing by a browser, on the screen it will take the form

[Dij76]  Dijkstra E.  A Discipline ...

Of course, for practical use the representation offered here of a horizontal layer should be carefully polished and somewhat improved. For example, it makes sense to allow an option for arrangement of the above bibliographic references in increasing order by names or in order of the first appearance in the main text. Improvements for the above module declaration construct are also needed. However these improvements will introduce nothing that is essentially new: both the concept and the realization of the offered scheme of program evolution stay compact and effective enough.

6. Non-intrusive program evolution

We have become convinced that the realization of horizontal layers is not only possible, but also is rather easy. Let's sum up the possibilities given to the programmer by this technique.

First of all, the two-dimensional constructs make it possible to reflect clearly the most substantive and deep content of the program text. Vertical layers (components) describe a variety of the external manifestations of the program. Horizontal layers cement together the program elements, providing for the unity of the internal algorithmic decisions and the user interface.

Fresh opportunities are being opened up for the development of reusable components. Now an interaction of a large component with the receiving program does not look like a bulky chaotic totality of diverse interface agreements. The interaction takes the readable and technologically convenient structure of unified module interfaces being installed in various horizontal layers.

One further, less obvious, but rather significant advantage of horizontal layers is the non-intrusive evolution of a program. Here the installation of a new vertical layer (component) is performed without editing the previously written source. Indeed, any program evolution transaction is decomposed into a series of installations of new homogeneous modules into the available horizontal layers. And each such installation passes non-intrusively: the module is merely put in the program repository and is supplied with an attribute of belonging to a certain horizontal layer. Now it is not necessary to edit the source text of the receiving program. Moreover, it is not necessary to do anything at all. On program linkage all modules with this attribute will be associatively extracted from the repository and placed into the newly formed horizontal layer.

It is no less important that not only an installation of the component is performed in the style "Plug and play", but also its uninstallation is performed in the style "Unplug and play". After all a component in the program repository is always accessible not only as a union of constituent modules, but also as an unified whole. Therefore uninstalling the component is reduced here to deleting it as one object in the program repository and leaves the remaining source code unaltered. Under different evolutionary transaction structures the uninstall will usually entail great difficulties. It is sufficient to recall the well-known problems that arise when uninstalling an application in MS Windows.

Finally, when the two-dimensional programming wins general acceptance, it would mean the triumph of an extremely productive idea. Each hot spot or, more properly, each point of growth of a program can be represented as a horizontal layer, i.e. extensible set of homogeneous modules.

7. Prospects

Now it should seem that the time has come to present the manufacturers of the above programming environment or to at least announce the target date for the appearance of tools for two-dimensional programming support. Unfortunately, we must disappoint the interested reader. In spite of the growing number of publications dealing with these problems, it seems that these tools will not soon appear in widely-used programming.

Though the realization of two-dimensionality is rather straightforward, it nevertheless affects a great many delicate aspects, i.e. horizontal layers, of the programming environment. It will suffice to mention source code debugging. In each point of the program execution the programmer should now have the possibility to see three representational axes of the source text: vertical, horizontal, and target, i.e. the usual input to the compiler. On this account realizing two-dimension support in the form of plug-in will not be successful without affecting the source code of the programming environment.

A vicious circle has been created. Without participation of the manufacturer the non-intrusive addition of two-dimension support fails, in as much as the code of current programming environments is not sufficiently open to extensions. But the code openness is insufficient because at one time its developers did not have at hand this same two-dimension support. As a result the code of the programming environment became in essence non-two-dimensional, i.e. the extensible horizontal layers remained unmanifested. Probably, it will be possible to break this vicious circle only when the programming environment manufacturers have considered two-dimensional constructs to be worthy of attention and have themselves incorporated support of such constructs in their programming products.

References

1. A.L. Fuksman, Technological Aspects of Program Design, Statistika, Moscow, 1979 (in Russian).
   
2. M. VanHilst M., D.Notkin, "Using C++ Templates to Implement Role-based Designs," JSSST international symposium in object technologies for advanced software, Springer-Verlag, 1996, pp. 22-37.
   
3. Y. Smaragdakis, D. Batory, "Implementing Reusable Object-oriented Components," 5th International Conference on Software Reuse, Victoria, Canada, June 1998, ftp://ftp.cs.utexas.edu/pub/predator/icsrtemp.pdf.
   
4. M.M. Gorbunov-Possadov, Extensible Programs, Polyptych, Moscow, 1999, http://www.keldysh.ru/gorbunov/ (in Russian).

The work was supported by the Russian Foundation for Basic Research, grant 99-01-00984

Author's personal web page: http://keldysh.ru/persons/english/gorbunov.html