Hence an index may carry the association and we can respond to the query:
"Who is the mother of Arnold?" by scanning the quot;mother of" column, picking
the Index 3 at the entry "Arnold" and returning "Mary" from the "3 position" of
NAME.

Such retrieval systems are obvious and are in general use. What, then, are
the faults? Part of the problem lies in the relative paucity of information-the
large number of blanks in the tables. Other problems occur at the time of
search, for the tables are not properly ordered. In fact, the "best order"
depends on what question is expected to be asked. For the question: "Who is the
mother of...?" the order 4,3,2,1 is preferred, whereas "Who is the father
of...?" prefers the order 2,1,3,4 or 1,2,3,4. Hence there is no order that is
optimal for all questions. Another major problem of tabular storage is its size
limitation. To be efficient, the table sizes must be pre-specified, and hence a
sudden request for extra space is potentially catastrophic.

The need for easy addition and deletion led to the list processor, and many
information systems stem from the ideas of IPL-V and SLIP. The former elucidated
and refined the method of pointers and lists, and the ideas of association lists
(Figure 2). The use of lists makes possible dynamically extended tables. A
second use of lists is with association explicitly defined for certain objects.
Thus the illustration of Figure 2b could be written:
$<Attribute$
A&gt; of &lt;object &#945;&gt; = &lt;value A&gt;
&lt;Son&gt; of
&lt;Arnold&gt; is &lt;James&gt; etc.
Here we see that the question "Who is
the mother of Arnold?" is difficult to answer, because it was not explicitly
stored on Arnold's association list. This question may be answered by searching
all association lists, until one is found which has the pair {Mother, Arnold}.

SLIP was the first embedding of a list-processing capability within a
higher-level language and was a formative ring structure. The idea of rings was
crystalized by Sutherland, and Roberts, and used with data systems designed
primarily for graphics and computer-aided design. Roberts has also developed a
language to refer to rings (Class Oriented Ring Associative Language: CORAL). In
such languages, the associations are built into the structure by allowing blocks
of information to be threaded by rings which carry the associations between the
blocks of data. This is illustrated by Figure 3. Dodd has implemented a similar
structure within PL/I. The duality of certain relationships, such as: "defined
by" and "defines" or "to the left of" and "to the right of," etc., led to the
need for a connector block, here illustrated by the three NUBS.

In essence, the NUB represents a two-way switch for transferring out of one
ring and into another. The subroutines or macros pass along the ring until they
arrive at a NUB. They "switch" it, and pass into the other ring, passing along
the second ring (and others as found) picking up information until they return
to the original NUB and re-enter the first ring. This allows answers to
questions such as "Who is the mother of Arnold?" as well as "Who is the son of
Mary?" One of the major disadvantages of these structures occurs on adding a
new, not previously anticipated, association. The operation either is
impossible, requiring a complete recompilation, or else clumsy, patching on
additional blocks (Figure 4) and requiring sophisticated garbage collectors. A
recent survey by Gray describes these and similar structures.

Probably the first conception of a true relational data structure was
Kochen's AMNIPS . He dealt with the problem of logical inference rather than
with data structures, but he recognized that conventional memories were
inadequate, and turned to the relational structure, which unfortunately was
never fully realized.

A considerable amount of work has been done on various "question-answering
machines." Among the better early machines were Lindsay's SAD SAM which can
digest English statements about family relationships and construct a family
tree, and the BASEBALL program of Green, et al. which answers English queries
about facts taken from a stylized baseball "yearbook." These investigations use
conventional data structures, and their real contributions were to the analysis
of the English language and logical inference by computer. Simmons provides the
most complete survey to date of this work.

Maron and Levien have designed one of the most extensive and complete systems
depending on a relational data file. They deal with binary relations as their
building blocks, i.e., each association has three components: one relation and
two operands. In addition, they allow the naming of the entire association
(triple) giving rise to a fourth component. Reference can be made using any of
the four components, and there are four copies of each association-one copy for
each word which can reference it.

Feldman has recently used the ideas of hash coding for association tables.
The associations are, of course, carried by a new table, referenced by a "double
hash" technique. Feldman's language, AL , is designed to be compiled rather than
interpreted. AL has been expanded to be three languages in one: a true
ALGOL-type algebraic language with full numerical computation facilities; an
associative processor; and a language which operates on sets as its basic
entities with a full complement of set operations. The language now allows for
certain kinds of restricted composition of associations. Specifically, if a
sentence is a triple &lt;A,0,V&gt;, then 0 or V may itself be another triple.
This allows for generating N-place relations out of the basic binary relations.
However, the language has, instead of dynamic inference, a DO loop which is
slightly more cumbersome, and far less economical of storage, than are strict
logical inference capabilities.

Naturally, the simplicity in using data systems depends on the retrieval
language. We have already suggested that the problem is partially a function of
explicit versus implicit storage. If the family relationships are taken in the
binary male lineage tree of four generations (Figure 5), we have: 16
great-grandfather-son; 24 grandfather-son; 28 father-son; 14 brother; 24
uncle-nephew; 48 cousins, etc. Obviously, a large number of relationships must
be explicitly stored for rapid access, compared with the cost of an implied
relationship search with small storage requirement.

The "relational" part of the TRAMP system is the means for retrieving implied
relationships, while the "associative" part deals with the explicit
relations.

III. TRAMP

TRAMP (Timeshared Relational Associative Memory Program) is two packages of
functions: the first-the data structure-may be used to enter, retrieve, and
generally manipulate an associative data structure; the second-the relational
memory-places an artificial structure on the "associative triples," viz., the
relational structure. The relational package allows logical inference to be
performed on the data within the associative structure. Specifically, rules may
be entered; these will be followed by TRAMP, effectively expanding a "minimal"
set of data to a workably large set; the number of associations that must be
explicitly stored is thereby drastically reduced. For example: by defining the
relation "HUSBAND OF" to be the converse of "WIFE OF," the user need only store
marital relations in one direction, while effectively having them available in
both directions. More detailed examples and the rules for using the relational
package appear later.

These machine-coded functional packages are presently embedded in the UMIST
interpreter on the IBM/360 model 67. Although this existing union has proved
most fruitful, the data structure is totally independent of the interpreter and
actually relies on it only for I/O. The relational package is also independent,
except that it relies on the type of recursion that the interpreter provides.
The relational package is totally

The Associative Data Structure

Feldman's initial work was a strong motivation in the design of this system,
and led us to adopt his notation, viz., the generic entity:
A (0) =
V
&lt;Attribute&gt; of &lt;Object&gt; equals &lt;Value&gt;
Thus the
Associative Triple is: lt;A,O,V&gt;. Each of the three components is a non-empty
set. To the data structure this is an ordered triple, but no interpretation or
meaning is attached to the ordering, and all three are treated equally, giving
none a priority.

By appropriately designating the three components as being constant or
variable, we can ask eight "questions" of the data structure. Again using
Feldman's notation, with a slight re-ordering, they are:

where [ A,O,V ] represent constants, and [ x,y,z ] are variables. Question F7
is not a question at all but a request for a dump of the associative memory, and
in TRAMP such a dump is given. Question FO simply asks: "Does A (O) = V?" and
the answer is a kind of truth value. In the case where A, O, and V are all
singletons, the truth value is a straightforward 1 or O denoting whether or not
the specified association can be verified by the data. The interpretation is
slightly ambiguous, however, when one or more of the three sets has cardinality
greater than one. To illustrate, assuming that the association
COLOR (CAR) =
RED; GREEN

has been stored, these five questions have the following truth values:


  
  
    
    
    
  
    
    
    
  
    
    
    
  
    
    
    
  
    
    
    

1.	COLOR (CAR) = BLUE	O
2.	COLOR (CAR) = RED; GREEN	1
3.	COLOR (CAR) = RED; BLUE	?
4.	COLOR (CAR) = RED	1
5.	COLOR (CAR) = RED;GREEN; BLUE	?

Questions 1 and 2 are clearly false and true
respectively, but questions 3 and 5 are each partially true and partially false;
question 4 is only half true. The interpretation which seemed most natural, and
the one adopted by TRAMP, gives the truth values as shown, namely:
if ALL
associations implied by the question are resident in memory, or derivable
therefrom, the value is "1"
if none, the value is "0"
if some, but not
all, the value returned is "?"

Questions F1-F6 simply ask the system to "fill in the blank(s)," i.e., to
replace the variable with the set that is the answer to the question. For
example, Question F1 asks for the set of all Vs that A (0) equals. Question F3
asks for the sets of all 0s and Vs that have a first component "A." Because of
the recursive nature of TRAC, questions F1-F6 may be nested in any way, to any
desired depth. One may ask: "How many fingers on a hand?"; "What figures are
pointed to by the arrows in Window Q?"; "How old are the fathers of the wives of
Mary's brothers?"; or any questions composed in any way compatible with the
stored data, nested to any level.

For those totally unfamiliar with TRAC language, for this section it is
necessary to know only the syntax of a function call. The sharp sign (#) signals
the start of a function call, with the call itself enclosed in an immediately
following pair of parentheses. The arguments are separated by commas, and the
first argument is the name of the function.
#(sub,ARG)
is therefore
analagous to the FORTRAN
CALL SUB(ARG)

Data Structure Storage

The name of the storage function is dr and the syntax of the call is:
#(dr,A,0,V) . Again, the three arguments to dr are each non-empty sets. Each
point in the cartesian product of the three sets is stored, i.e., each element
of each set is grouped with each pair of elements of the other two sets, and the
resulting triple is stored. Thus a single call on dr stores as many associations
as the product of the cardinalities of the three sets. The storage
declaration:
M(dr,AGE,JOHN;MARY,64)

would therefore store:
AGE (JOHN) = 64
AGE (MARY) = 64
The actual
storage is accomplished by pairing each A and 0 to point to a list of Vs ; each
A and V point to a list of Os , etc. These answer' lists are, strictly speaking,
un-ordered, except that they retain the order in which they were stored. That
is, asking the question:
"Whose age is 64?"
would yield the
answer:
JOHN; MARY not MARY; JOHN

It should be noted that this is a pure data structure, and it does not deal
with semantics; dr simply inserts associations into memory in a way that they
can be quickly retrieved. TRAMP is not a question-answering system that checks
for redundancies or inconsistencies of data.

Data Retrieval

The primary retrieval function has the name rl The syntax of the function
call is identical to that of dr except for variable specification. A variable in
TRAMP is denoted by enclosing a name, possibly null, within asterisks (*) .
Thus, #(rl,A,O,V) has no variables and asks whether A (O) = V ; #(rl,A,O,*X*)
asks: "What does A (O) equal?" If the variable is Named, i.e., there is a name
within the asterisks, then the function is Null Valued and the answer is stored
in TRAC language form storage labeled by the Name. #(rl,A,O,*ANS*) would store
the set of Vs which A (O) equals, under the label "ANS." If the variable is not
Named, #(rl,A,O,**) , then the answer is the Value of the function.
#(rl,A,*SETO*,**) is an example of a two-variable question with one Named and
one Unnamed variable. The result in this case would be that the set of Os is
placed in form storage under the label "SETO" while the set of Vs is returned as
the Value of the function.

The two-variable questions (F3, F5, F6) simply use the Name table of one of
the variables and index through that table, internally always asking the
one-variable questions. Since the data structure does not assign any priority to
the three components, questions F3, F5, and F6, although considerably slower
that the one-variable questions, are all equal among themselves. The process of
answering a two-variable question is less efficient because it must iterate on
the one-variable questions, the number of iterations being a linear function of
the size of memory.

The speed with which the one-variable questions are answered is not
significantly affected by the size of memory! The three-variable question,
#(rl,**,**,**), is, of course, the slowest of all and it is a full dump of the
associative memory. Alternatively, one can call: #(dump).

Going back to the earlier example of JOHN and MARY, the question:
#(rl,AGE,JOHN;MARY,**) should have as its value: 64;64. That is, redundancies
can be valid and should be reported. But there are certain times, particularly
in the two-variable questions, when redundancies become quite a nuisance (and
even threaten to overflow the interpreter). Therefore, the function rl will
always return an answer set with all redundancies deleted. A second entry point
is provided, with the name rlr, which is identical except that it does not check
for redundancies but returns the answer set as it finds it.

rl generates the union of the answer sets. That is, the question:
#(rl,AGE,JOHN;MARY,**) has two answer sets: the AGE of JOHN and the AGE of MARY.
rl simply forms the union of however many sets there might be. int is the
function (yet another entry point to the same routine) which generates the
intersection of the several answer sets. Thus, #(int,SOUTH;WEST,AUGUSTA,**)
generates the set of all things both south and west of Augusta. #(rl,SOUTH;WEST,
AUGUSTA,**), on the other hand, would generate the set of all things either
south or west of Augusta.

Data Structure-General Strategy

As stated in the introduction, hash-coding is the technique most basic to the
data structure design. A brief description of the use of hash-coding in TRAMP
follows. Section V gives a more technical and detailed description.

The data structure uses three Name tables and three Association tables, one
each for each of the three components of the association. When the declaration:
#(dr,WIFE,JOHN,MARY) is made, each name that appears must be stored somewhere in
memory. The full name must be present so that it can be retrieved, and so that,
when it is referenced, a collision can be identified and resolved. The first
hash, H₁, then is applied to the "A" component, "WIFE," to generate a
displacement from the A Name Table. The designated table entry is then
inspected. If the entry is zero, then there is no collision and WIFE has never
appeared before as an "A" component. Accordingly, the table entry is now made to
point to the Header for the name WIFE, see Figure 6. If the table entry is not
zero, the Header to which it points is inspected to see if it is the Header for
WIFE. If so, the A name has been processed and we move on to the 0 component,
otherwise there is a collision. For a collision, instead of a single Header,
there is an alphabetical list of Headers.

Thus, Name Table collisions are not really special cases: if there is no
collision, then there is a list consisting of a single Header, otherwise the
list contains two or more Headers in alphabetical order.

If the above process did not find the name, before it is actually placed in
storage, a further check is made on the other Name Tables, thus avoiding
redundant storage. Any name will appear at most once in memory, with up to three
Headers pointing to it.

The same procedure is applied to "JOHN" and "MARY," the O and V of this
example, on their respective Name Tables. As a result of the Name Table
processing, a unique pointer is associated with each of A, O , and V , namely
the pointer in the Header which points to the location of the actual name. It is
this unique pointer that will be used for the second hash, H₂. "WIFE"
must now be placed on the A Association Table. To do this, the O and V pointers
are hashed together to generate a displacement from the Association Table. To be
able to identify collisions, both pointers that were used to generate the hash
are stored in the table entry designated by the hash. Collisions are again
resolved by ordered lists. The Association Table entry has three pointers: the
first two are the pointers used to generate the displacement; the third points
to the Answer List, i.e., the list of A's (in this case) with which O and V have
been associated. Thus, "WIFE" is appended to the Answer List by placing the
unique pointer to it at the end of the list. Note that H₁ is a
function of the actual name, while H₂ is only a function of where the
name is stored and is independent of the name itself. Figure 7 shows the
Association Tables, both for the collision case [ 7b ] , and for the normal case
[ 7a ] .

IV. LOGICAL INFERENCE PACKAGE

The associative memory accomplishes a kind of content addressability by using
two quick hashes to address data, and the access time is essentially independent
of the size of storage. But for most, if not all, applications, many
associations will be implied by a single associative sentence. This poses two
real problems:

1. The user must make sure that all associations that apply are actually
  inserted into the structure. This is extremely tedious and prone to error and
  omissions.
2. Explicit storage results in gross inefficiency.

To alleviate this, TRAMP provides the facility to define, in a characteristic
way, what other associations may be derived from a given association. This
permits all of the information that might be contained in a single association
or sequence of associations to be utilized instead of having to enter the same
information redundantly in each of the several ways that it might be referenced.
The name of the function which makes the definition is ddr. The syntax of the
function call is: #(ddr,(R = EXP)) , where R is the relation ("A"component) to
be defined, and "EXP" is a logical expression which is the definition.

Before presenting examples of the use of ddr, two relational operators must
be defined:
The first is converse, denoted in TRAMP by ".CON." Converse
simply inverts the order of the two relational arguments:
R(x,y)
&amp;leftrightarrow; .CON. R(y,x)
Thus "CHILD OF" is the converse of
"PARENT OF"; "WIFE OF" is the converse of "HUSBAND OF"; "SPOUSE" is its own
converse; any symmetric relation is its own converse. (The relational notation
used by TRAMP is derived from the format "R,x,y" by enclosing the relational
arguments in parentheses. This is a slight distortion of the associative
notation: A(0) = V , but the order is preserved: R(x,y) means that it(x) = y. )

Relative Product: The relative product or composition of two relations is
commonly denoted by R₁/R₂, and this is the notation used
by TRAMP.
$\forall x\; \forall y\; \&exists;z\; [\; (R$₁/R₂) (x,y)
&amp;leftrightarrow; R₁(x,z) &#923; R₂(z,y) ]
Less
rigorously, but more specifically,
#(ddr,(R₃ =
R₁/R₂))
would tell TRAMP that R₃(x,y) if a
"z"can be found such that R_l(x,z) and R₂(z,y).
Besides
these two relational operators, three logical operators are available: .A.
(conjunction); .V. (disjunction); .N. (negation). Finally, there are six
equality operators: .EQ.; .NE.; .GE.; .LE.; .GT.; .LT. , with obvious meanings.

Examples of TRAMP relational definitions are:

  

#(ddr,(BIGGER = BIGGER / BIGGER))
  

Bigger is transitive
  

#(ddr,(BIGGER(A,B) = BIGGER(A,Q) .A. BIGGER(Q,B)))
  

exact same definition using expanded format-specifying dummy arguments.
  

#(ddr, (SIB = BRO .V. SIS .V. .CON.SIB))
  

a sibling is a brother or a sister and it is symmetric.
  

#(ddr,(HUSBAND = .CON.WIFE))
  

Husband is the converse of Wife.
  

#(ddr, (BIGGER = LARGER)
  

Bigger and Larger are synonomous.
  

#(ddr,(BRO(CAIN,ABEL) = SIB(CAIN,ABEL).A. SEX(ABEL,"MALE")))
  

a brother is a male sibling. Note that constants are denoted by enclosing
  them within double quotes.
  

#(ddr,(MALE(X) = SEX(X,"MALE")))
  

defined the unary relation MALE
  

#(ddr,(BRO(X,Y) = FATHER(X,Z) .A. FATHER(Y,Z) .A. MALE(Y) .A. X.NE.Y))
  

a brother is a male offspring of the same father, other than oneself.
  

#(ddr, (STEPMOTHER = FATHER / SPOUSE .A. .N.MOTHER))
  

a stepmother is the spouse of the father who is not the mother.
  

#(ddr, (NEPHEW = SIBLING / SON))
  

a nephew is the composition of sibling and son.
  

#(ddr, (UNCLE = .CON.(SIBLING/SON)))
  

in a male world, uncle is the converse of nephew and may be defined as the
  converse of the definition of nephew.
  

#(ddr,(UNCLE = .CON.NEPHEW))
  

or simply as the converse of nephew.

More complex examples will arise, and TRAMP is prepared to handle definitions
of the above form to a level of complexity virtually unlimited. One major
constraint is placed on the definitions: relations must be defined so that at
least one set is generated. This generated set can then be intersected with or
joined with another set, or otherwise manipulated. The intent of this constraint
is that there be at least one reference set. The "whole space" may never be used
as a reference set.

  

#(ddr,(R₃ = .N.R₁ .V. R₂))
  

is illegal since it specifies a global complement (of R₁),
  i.e., it references the "whole space."
  

#(ddr,(R₃ = .N.R₁.A. R₂))
  

is legal because it specifies a relative rather than a global complement,
  i.e., R₁ places a constraint on R₂ not on the whole
  space.

In effect, TRAMP employs a triple storage technique to be able to reference
an association in three different ways. Thus, the association A (O) = V is
stored on each of the A , O , and V Association Tables. This makes the answers
to questions F1, F2, and F4 equally accessible and optimizes retrieval time.

For purposes of illustration, let us follow the interpretation
of:
#(dr,HUSBAND,EVE,ADAM)
First the Name Tables are processed. "HUSBAND"
is hashed to produce a displacement from the "A" Name Table. The actual hashing
scheme for H₁ is to form a full word (4 bytes) by concatenating the
first, last, and middle two characters of the name, in that order. A single
character may play only one of those roles, i.e., a name consisting of one
character has no last or middle characters. Any missing components are filled
with hexadecimal zeroes. Thus HUSBAND yields "HDBA"; EVE yields "EEVo" and ADAM
yields "AMDA." The full word so generated is then transformed, with the
transformation being little more than squaring and masking.

A list is generated in GS to hold the EBCDIC representation of the name: 6
characters (bytes) per double word and a 2-byte pointer to the next unit in the
list. All units in GS are double words (64 bits). Each name list is terminated
with a stop meta character. All lists in TRAMP are terminated with a stop
pointer, though the stop pointer is superfluous in the name lists because of the
stop meta. In the case of HUSBAND, two double word units will be needed: the
first will hold the 6 characters H-U-S-B-A-N, and a two-byte pointer to the next
unit which will hold the character "D," the stop meta charcter, and the stop
pointer, with four bytes left over. Since HUSBAND is used here as an
"attribute," we are concerned with the A Name Table. We look at the entry in
this table designated by the hash. If this entry is empty, i.e., zero, there is
no collision, and HUSBAND has not been used previously as an attribute. If not
empty, we look at the list of Headers pointed to by the entry. This list is
alphabetical, so we need look only until we find HUSBAND or its proper
alphabetical position on the list. Proceeding down this list of Headers, we
compare the list generated above with the sublists pointed to by the headers. If
a match is found, simply return this temporary list to GS and increment the USE
count for HUSBAND in its header. If it is not found, insert it ... after
checking the 0 and V tables for its occurrence. Previously HUSBAND may have been
used as, say, an "object": #(dr,SEX,HUSBAND,MALE). In this case the HUSBAND name
list would already be resident in GS. We therefore return the copy of it
generated above, and insert a pointer to the first list on the A table header
list. Thus a name never appears in core more than once, though many pointers may
point to it, including up to four headers if a name appears on all four Name
Tables.

The above process is done for each HUSBAND, EVE, and ADAM. The final pointer
to the one name sublist of each is saved to generate the Association Table
hash-H₂. Let us follow the processing of the O Association Table.
HUSBAND and ADAM (A and V) are hashed together (multiplied and masked) to
produce a displacement in the Association Table. The actual hash is performed on
the two unique pointers found during Name Table processing. The designated
Association Table entry is examined. If zero, there is no collision, and HUSBAND
and ADAM have never appeared together with another value. The unique pointer to
HUSBAND is placed in the first 2 bytes of the 6-byte entry. The pointer to ADAM
is inserted in the middle 2 bytes. A double word unit is picked off GS to be the
start of the "Answer List," and the pointer to this Answer List is placed in the
last 2 bytes of the table entry. The Answer List elements consist of three
2-byte pointers to name sublists, the answers, and a 2-byte pointer to the next
list element. Accordingly, the pointer to EVE is inserted in the Answer List.

If the table entry was not zero, compare the first 4 bytes of it with the two
pointers that would go there. If a match is made, then just add EVE to the end
of the already started Answer List (polygamy is fine here), starting a new unit
if necessary. This is a simple unordered list, with new elements always being
added to the right-hand end. If the first four bytes of the table entry do not
match the pointers, is there a collision flag in the entry? If not, a collision
list is begun. This is an ordered list, with the ordering being the numerical
value of the full word obtained by concatenation of the A and V pointers (the
first 4 bytes of the table entry). Each element of the list is a double word as
always. The first 6 bytes of this double word are identical to the 6-byte table
entry. The last 2 bytes point to the next element on the list. When a collision
occurs, the first 4 bytes of the table entry are so flagged and the last two
bytes point to the list which resolves it.

The entries of all the tables, as well as all list pointers within GS , point
to double word units in GS . All pointers are 2 bytes long (16 bits), but are
capable of addressing 128 pages of GS. (1 page = 4096 bytes; 128 pages =
2¹⁹ bytes.) For some applications this size is more than adequate,
and for others (e.g., artificial intelligence) not nearly enough. With its
present scheme (addressing 2¹⁹ bytes with only 16 bits) TRAMP has an
upper limit of 128 pages, which is a usable size for the majority of cases,
including many AI applications. There is obviously a trade-off here since the
more core that a pointer can address, the less percentage (though not
proportionately less) of that core is available! There is a second trade-off
because the size of the units which must be addressed determines the number of
bits needed to address them-the larger the unit, the fewer bits required, but
generally, the less efficiently it is used. We arbitrarily decided that the
half-word pointers that TRAMP uses to address double words are, in a sense,
optimal. Should more experience prove us wrong, or if some special application
should require much greater capacity, the structure could be augmented, e.g., to
incorporate full 32-bit addresses, with little more trouble than alteration of
an assembly parameter. At this time it is not anticipated that explicit use will
be made of any peripheral storage devices, other than the transparent swapping
performed by the timesharing supervisor.

The sizes of the various Name and Association tables are another assembly
parameter. Currently the 7 tables occupy 4 pages of core. This figure was
arrived at arbitrarily and will remain in force pending feedback which indicates
that it is inappropriate.

TRAMP is initially loaded into core with all of its tables, a one-page PSECT
and 8 pages of GS . Thereafter, when more space is needed (GS is the only unit
that will require more space, since overflow from the tables is placed in GS),
TRAMP requests it of the system in blocks of 8 pages until the maximum of 128 is
reached, or the system is unable to comply with the request.

TRAMP is continually generating temporary lists which are immediately
returned to GS when no longer needed. As well, when an association is destroyed,
or a relational definition erased (KR and KDR , Appendix B), as much storage as
is being released is at that time returned to GS. Thus, unused units are never
left lying about core: a unit is returned, not discarded, eliminating formal
garbage collections by ensuring that garbage is never created.