Search

The family of subroutines described in this report was designed to create, search and maintain tables which are to contain entries of different lengths, and yet be amenable to search by partition, or “binary” search. It is designed explicitly for fixed-word-length binary machines; the tables in question are the argument-function type, with the two parts physically separated—i.e., no one machine word contains both, or parts of both. The family consists at present of seven subroutines, of which four are primitive and three second-generation. (By “primitive” is meant a self-sufficient routine; a second-generation routine is one which calls on one or more primitives.) These routines are at present coded for the IBM 709; with a few trivial changes they are ready also for the 704. The primitives are: (1) STT (Start Table), (2) TLU (Table Look-Up), (3) ITC (Increase Table Capacity), and (4) AOD (Append Ordered Data). The second-generation routines are: (1) INT (Insert in Table), (2) INX (Insert and Expand), and (3) ANX (Append and Expand). It is intended that this family be written, with modifications as necessary, for several stored-program computers. The calling-sequences for any one of the routines will, as far as possible, be identical on the several machines.

The XPOP programming system is a straightforward and practical means of implementing on a computer a great variety of languages---in other words, of writing a variety of compilers. The class of languages it can handle is not easy to characterize by syntactic form, since the system permits syntax specification to be varied freely from statement to statement in a program being scanned; the permitted class includes the best-known programming languages, as well as something closely approaching natural language. We believe that this distinguishes the XPOP processor from the syntax-directed compilers, although it shares with them the fundamental idea that the process of programming-language translation can be usefully generalized by a compiler to which source-language syntax is specified as a parameter.