SELF-PROGRAMMING TECHNIQUES IN
GENERAL PURPOSE DIGITAL COMPUTERS

B.L. Ryle

Marc Shiowitz and Associates, Inc.

INTRODUCTION

Two equally valid approaches exist to the problem of simulating the mental activities of humans. One consists of mechanizing neuron-equivalents and otherwise attempting to duplicate what is known and/or hypothesized about the human nervous system and mind. The other is concerned with duplicating the results of mental activity, without regard for the methods by which the results are obtained. The former is currently useful as a research tool, primarily in the effort to gain a better understanding of "thought" and "mind." The latter approach has been rather extensively applied, since it is implicit in the present-day use of digital computers. This "black box" approach will be reviewed in this paper. In particular, this paper will discuss the application of self-programming techniques to the programming of general purpose digital computers.

PROGRAMMING

Consider for a moment what is involved in "programming" a human. Suppose it is desired that a series of computations are to be executed over several sets of data. An inexperienced desk calculator operator, with no knowledge of mathematics, must be given a set of instructions which translate the functions into terms he can understand. These tell him which keys to punch and when, what to do with intermediate results, etc. On the other hand, an experienced operator with a doctorate in applied math need only be given the data and a statement of the objectives. Assuming that the two operators have equal intelligence, the difference between them lies in the experienced operator being able to use previously stored information to determine his own "program" of what to do and when.

A human, in executing a "program, may use previously defined algorithms, devise his own algorithms, use tables of tabulated functions, resort to a slide rule, make a calculated guess, or use any of a large number of other techniques to attain the objectives of the program.

A computer has access to much more limited numbers of techniques in the execution of a program. In its simplest terms, a general purpose digital computer has, at the beginning of a problem, a certain binary function stored in the computer, with each binary storage position containing either a 0 or 1. At the end of the problem, the computer contains a second binary function, usually different from

the first. Thus, the computer itself is the method of forming correspondence between one such binary function and another. If there are no binary storage positions in the computer system (including any auxiliary storage), then there are 2 possible machine functions. The problem of programming a computer consists of:

a.

b.

c.

Isolating two sets of functions (f1 and f2) in the "problem space."

Defining a problem operator, P, which transforms
f1 into f2 (i.e., Pfl
(i.e., Pf1 = f2).

1

2

Translating or mapping problem functions f1 and
f2, and problem operator P, into computer functions
and 92, and computer operator M. This trans-
formation is called computer programming.

91

The problem of programming a computer is complicated by a number of factors:

1.

2.

Although
2N
may be a large number of functions,
this number is still small when compared to all
possible functions. Thus, in general, the trans-
lation of the set of "input" functions, f1, into
the set of machine functions, g1 is usually not
1:1. For example, consider the mapping of rational
and irrational numbers into computer number of
finite length: all numbers within a certain inter-
val are made to correspond to a single number with-
in the computer. This is the source of the round-
off problem.

A problem similar to that of 1 above relates to
the mapping of 92 into f2. This problem is com-
plicated by the fact that, in general, the mapping
of 92 into f2 is not the inverse operation of
mapping f1 into 91. This is due to the inherent
restriction that the computer operator, M, must
be a finite operator, whereas the problem operator,
P, generally operates on an infinite number of

elements.

1

3. The elements, M., of the computer operator, M, are

usually stored within the computer as functions
of the same type as the input and output function
sets, 91 and 92, and are able to operate on each
other. In the extreme, each element M

i

is a

function of all the preceding elements, M.,

(j < i) and of the input functions 91.

GENERAL PROGRAMMING SYSTEM

The development of a computer program can be reduced to the classic problem which faces any designer: the formal description of a process or procedure. The steps involved are:

1.

2.

3.

4.

5.

Statement of the problem: determination of a definitive descriptive statement of the problem in some formal language

Choosing the set of basic computer elements:
determination of the particular set of elements
which will be ordered and duplicated to form
the elemental computer operations, M. These
may be instructions, subroutines, statements, etc.
Translation: decomposition of the problem oper-
ator, P, into elements, P
, Pi'
and the choice of an
appropriate computer element from 2, above, to
serve as M1 such that M i Pi

=

Optimization of the program:

determination of

an appropriate measure of effectiveness (execution time, programming time, storage space, etc.), and organizing the program to that measure

Testing:

determination of the behavior of the final program, under an appropriate set of input parameters.

SELF-PROGRAMMING

The participation of the computer in any of the steps of the general programming system means that the computer is assisting in the programming of itself. The degree of participation determines the degree to which a computer can be said to be "self-programming.

The limitation to the extent a computer system can

become self-programming is determined in part by the design of the system. The truly self-programming computer system would perform in the following sequence:

1.

2.

3.

4.

5.

6.

7.

Input the problem operator, P, in some previously
decided upon language.

Translate P into computer language, and decompose
P into elements P Pi according to some algorithm.
Determine a "best" form for the corresponding M
into the M1.

Translate the P
Pi

i°

Translate the set of input problem functions,
f1 into the corresponding computer functions 91.

1

Execute the sequence of machine operations, M
and derive the computer output function set

92°

i'

Translate the computer function set 92 into the problem output function set f2.

DEVELOPMENT OF SELF-PROGRAMMING SYSTEMS

Almost with the introduction of stored-program digital computers, users and manufacturers started developing programming systems to reduce the time required (and the number of errors) to perform this translation. An obvious direction in which to proceed was to use the computer to take over some of the tasks being performed by humans to assist in the programming of themselves. The efforts expended to date have resulted in three somewhat overlapping classes of program designs to assist in this task; assemblers, compilers and interpreters.

In keeping with the view of the programming job as one essentially of translating the problem to machine language, the three classes of programs may be defined as follows:

a.

Source program language is computer-oriented and is usually a word-for-word substitution for the computer's instruction language, mnemonic codes are generally used, addressing is normally in decimal, and is normally relative to one or more abstract addresses.

Type of translation is usually a one-to-one
substitution. However, some assemblers admit,
as single pseudo-instructions in the source
program, subroutines or sets of instructions
in the machine language. These pseudo-
instructions are normally fixed for a partic-
ular assembler, (i.e., it is not usually
possible to define pseudo instructions within
the context of the source program). This type
of translation is equivalent to using a
dictionary which contains each word to be
translated.

Useful features:

1) permits portions of a program to be coded independently

2)

3)

4)

permits the use of all of the particular
computer's idiosyncracies

eliminates the problem of memory allocation, provided the memory capacity is not exceeded

the translated computer program, ready for use, is the end-product

5) the coder's functions are minimized and
can frequently be assumed by the programmer.

Interpreters:

a.

b.

Source program language very closely resembles that of the compiler. However, the form of the program usually resembles that of the assembler, i.e., a step-by-step sequence of symbolic instructions.

Type of translation is similar to that of the assembler in that each source program instruction is treated as a request for a sub-routine internal to the interpreter. However, the interpreter differs from the assembler and the compiler in that the translation occurs concurrently with the execution of the object program, rather than preceding it.