We call an association net an oriented multigraph with some objects (abstract or concrete) ascribed to its vertices and arcs. As a rule, the objects ascribed to arcs are words, representing binary relationships, and in this case the arc is interpreted as a statement that the respective relationship holds between the objects, ascribed to the ends of the arc.

A well-known type of such nets are diagrams used in books to illustrate relationships between some concepts or objects (pic.1). Such nets are also used by psychologists to represent the structure of human knowledge [2].

Computer programming, too, has an old tradition of utilizing association nets and similar structures (program flow-charts, property lists in LISP); among less obvious cases we can note the language of RX-codes [8] for information retrieval systems and the job control language of the OS/360 operating system. Here is an example for the latter case:
//IEFPROC.IEFRDER DD UNIT=280,VOL=SER=SYSIN,
// LABEL=(1,NL,,IN),DSN=SYSIN,DISP=OLD,
// DCB=(RECFM=F,BLKSIZE=80,BUFNO=2)

This DD-statement essentially describes the net shown in pic.2. The fact that OS/360 itself fails to use such a structure, handling instead of it character strings or rigidly formatted "control blocks", results in the first case in considerable complication of operating system programs, and in the second case becomes an obstacle to future developments.

In 1970's a number of AI systems were developed with "semantic nets" used to represent relationships between the notions in the problem area of the system [12].

The author recognized the need in programming systems based on the concept of association net out of his own experience with special purpose languages for various kinds of problems and, in particular, from studying the process of transforming a verbal formulation of a task to a computer program (or to some other kind of signal to control a technical device); it was found among other things that it is better to treat the words used in the task formulation as names of arcs in an association net rather than trying to represent the words by means of complicated mathematical structures ([13]; a similar use of names is found in the UTOPIST language [11]). In [7] an attempt was made to use nets for parsing and understanding natural language texts along the lines of M.Minsky [3]. Some complications of the concept of a net, introduced in [7] for parallel development of mutually incompatible processes, had to be given up later. Now this research continues on the basis of the version described here. Finally we note papers by A.M.Stepanov [9] and [10], presenting some ideas very close to this paper.

The aim of this research was to study the power of programming in terms of association nets by developing and upgrading an experimental programming system based on the concept of net. In the course of the development the author tried to avoid unnecessary extensions of the set of system primitives; new facilities were only added when it was difficult to do without them in some particular application, and when added the simplest possible form was preferred.

The approach of this paper differs from other work on association nets in the following respects:

procedures are included in the net and systematically used;

no attempts are made to complicate the definition of net by introducing special types of vertices and arcs (for disjunction, conditions, quantifiers, modalities, etc.) in order to represent in the net some logically complicated statements (this function is shifted over to procedural facilities whose role is considered in [14]);

graph vertices are used, as a rule, not to represent abstract notions or object classes but rather to stand for concrete objects in the current situation that usually even do not have any unique names to identify them beyond this situation;

the representation of information in terms of nets is regarded as a basis for a system of modular programming in which preliminary requirements imposed on a module for interaction with other modules are minimized;

an attempt is made to interpret nets and operations in terms of logics.

Here logic does not necessarily mean common mathematical logics. The forms of thinking reflected by this system seem to be more elementary than rigorous mathematical thinking reflected by mathematical logics. The author acknowledges a substantial help from N.N.Nepeivoda in understanding the logical impact of the techniques proposed here. But, in contrast to his paper [5], suggesting an interpretation of logical constructions in terms of computer programming, this paper follows a reverse tack, starting from the needs of programming towards logical interpretation. It would be also interesting to study relationships between this system and the PROLOG programming language which is based immediately upon predicate logic.

In every particular application the repertoire of abstract notions (or, more precisely, their names) that can appear in the net is always restricted to the problem area, but there is always a possibility of extending the area, and, correspondingly, the set of names used. For this reason this system never requires to specify in advance the whole set of names to be used; moreover, it follows from requirements of modularity and extensibility that inclusion of new names should have no effect on previously written procedures that know nothing about those new names. In particular, the system should not have any ways for a procedure to obtain the complete list of names present in the net, not even the complete list of names ascribed to the arcs emanating from a given vertex. However it is a good idea for the implementation to benefit from the fact that the repertoire of names is restricted (or, at least, is seldom extended) and thus to replace full symbolic representations of the names by specially assigned short internal codes.

This programming system is being developed since late in 1979. It has been used as a basis for a few experimental projects, involving automatic construction of programs from a description of the structure of objects with which the programs are to work. The largest of those projects is described in [4], it is a system for automatic generation of parts of a compiler for an ALGOL-like language responsible for evaluation of attributes of program constructs, starting from the description of the attributes.

This system has been used also for some experiments in computer understanding of natural language texts in a small problem area. This kind of application is harder than those previously named due to the fact that natural language text used as input, in contrast to specially defined descriptions, has no explicit structure but linear sequence of words. Revealing the internal structure of this kind of text is a peculiar task that has required introduction of additional facilities (procedure queue); similar facilities will be probably needed in other applications for recognition of situations that are not specified explicitly.

Communications about this system were presented in 1980 at a National conference on methods of mathematical logics in AI problems and systematic programming and in 1982 at a meeting of the working group for implementation of programming languages attached to the Coordinating Committee for computing of the U.S.S.R. Academy of Sciences.

The system is described here as it is actually implemented; all suggestions for improvements are clearly so designated.

The author is indebted to the first users of the system, R.I.Muravina and T.N.Nevleva, for their assistance in learning how to use the system.