         
                                                          <Page No.   1>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||             TRAMP84 - A REVISION AND UPDATE of             ||
        ||                                                            ||
        ||                           TRAMP                            ||
        ||                                                            ||
        ||                    A RELATIONAL MEMORY                     ||
        ||                                                            ||
        ||                          WITH AN                           ||
        ||                                                            ||
        ||                      ASSOCIATIVE BASE                      ||
        ||                                                            ||
        ||                                                            ||
        ||                William Ash and Edgar Sibley                ||
        ||           The University of Michigan - May 1968            ||
        ||           prepared under ARPA Contract DA-49-083           ||
        ||                                                            ||
        ||                                                            ||
        ||               TRAMP84 Revision and Update by               ||
        ||                     Claude A. R. Kagan                     ||
        ||                       1980 and 1984                        ||
        ||                                                            ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
                                    ABSTRACT                            
        
        This report describes the theory and implementation of an
        experimental language called TRAMP, which is a software
        simulation of a content addressable memory. The system consists
        of an associative data structure embedded in an interpretive
        language, allowing great flexibility and strong recursive power.
        
        
        The system has further been extended with a logical inference
        capability by superimposing a relational structure over the
        associative memory. The resulting language has proved to be
        extremely powerful in various application domains; it can be
        termed a language for developing question answering, expert, and
        interactive communication systems.
        
        
        This updated and revised description of TRAMP was done to bring
        the concepts in line with current technology and to incorporate
        its structure in the structure of the SAM76 language which is
        available on a variety of micro computers. The combination of
        TRAMP and SAM76 appears to offer a powerful tool in the design
        and implementation of AI and Expert System applications.
        
                 
                                                          <Page No.   2>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||                          FOREWORD                          ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The bulk of this paper was written by William Ash and Edgar
        Sibley at the University of Michigan in 1968. In many respects
        it was ahead of its time. In the middle 1970's Claude Kagan
        received a copy from the authors and at various times considered
        implementing TRAMP as part of the SAM76 language. For various
        reasons this was not done - primarily due to lack of time,
        little interest by others and marginal memory availability in
        eight bit micro computer systems.
        
        
        Between 1981 and 1984 it was believed that the combination of
        TRAMP and the SAM76 language would be a superlative combination
        for studies in Expert Systems and Artificial Intelligence. To
        this end TRAMP was carefully reexamined and the original text
        was revised to better reflect current conditions. In addition a
        number of changes were made in the definitions of the primitives
        of the TRAMP system. These changes were to maintain a maximum
        level of consistency (cleanliness of syntax and semantics) to
        equal that currently embodied in the SAM76 language.
        
        
                                Claude A. R. Kagan, November 1984
        
                 
        I - Introduction                                  <Page No.   3>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||                  I - TRAMP - Introduction                  ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The need for a content addressable computer memory has become
        increasingly clear. Larger and larger programs are being written
        which require a structured data base to operate with any
        efficiency. Many of these could well benefit by replacing
        tedious searches with a fast, efficient, "content addressable"
        access of the data store. A good example is the "key-word"
        library search. If we ask for a list of the books written by J.
        von Neumann, we do not expect the system to look at each title
        in its store and save only those written by von Neumann. And, if
        there happens to be a catalog prepared, designed to answer this
        particular question, we do not want to have to do a binary
        search to find the correct section of the catalog - we want to
        retrieve the answer directly.
        
        
        There are many other problems which might find content
        addressability advantageous. Examples abound in Artificial
        Intelligence, where prohibitively large tree searches are
        encountered; question answering machines; logical inference
        systems; graphic systems; and most conversational systems, which
        require immediate, direct access to a large data store to
        interact effectively.
        
        
        To date, most investigations into content addressable memories
        have been concerned with hardware; such memories have not yet
        proved to be economically feasible. Even if they had, it is not
        clear that the obvious gain in speed would compensate for the
        loss in generality and flexibility. For the moment it can be
        said that software simulations are a stopgap measure. They are.
        But it is not certain that they will be completely replaced by
        hardware in even the relatively distant future.
        
        
        Another function of an artificial language is to permit the user
        to phrase his problem in a natural manner. For many problems
        information is most naturally described as "relational triples";
        e.g., in a graphic system, one might want to say; <picture in>
        <window A> is <line B>; or <connectedto> <line B> is <line C>.
        The associative processor approach to content addressability
        allows this.
        
        
        Before proceeding, we shall explain some potentially ambiguous
        terms.
        
        
        The essential feature of an associative processor is that it
        has, in the conventional sense, no explicit addresses. Reference
        to storage is made by specifying all or any part of an
        associative cell, and all cells which match this field(s) are
        referenced.
                 
        I - Introduction                                  <Page No.   4>
        ----------------------------------------------------------------
        
        
        
        The conventional computer store may be thought of as a special
        (degenerate) case of an associative memory, in that the
        association is between the physical address and its contents.
        However, reference can be made only by specifying the address -
        one cannot ask directly for all cells which are zero! The true
        associative memory is accessed by specifying any of the N
        participants in the association.
        
        
        Associative memories are often referred to as relational data
        structures. This is because an association between N + 1
        "objects" is most easily thought of, talked about, and
        manipulated by calling it an N-place relation.
        
        
        The following example demonstrates why an associative processor
        can effectively be employed as an application of content
        addressability. Suppose we wish to know the phone number of
        Clark Kent. It is simple to look it up in the local phone book.
        It is, however, quite a different matter to find out whose
        number is 764-6148 (using the same directory). An associative
        processor would find both tasks equal.
        
        
        In this example, the "association" is between a subscriber's
        name and his phone number. In translating this to a two-place
        relation, "phone number of" could be the relation, and using the
        <R,x,y> format we would say <Phone number of> <Clark Kent> is
        <KR9-8765>.
        
        
        This is a type of associativity wherein we may now directly
        reference this triple by any of its content addressable
        components or combination thereof. If we use only the first
        component, phone number, in a search, what will be referenced is
        the entire book. If we specify two components; phone number and
        764-6148, then we are referencing directly all associations
        containing these two components, viz., the associations
        containing the name(s) of the person(s) having the phone number
        764-6148.
        
        
        We are, of course, working with a conventional computer memory.
        The general strategy used to effect the simulation of an
        associative processor and an approximation to content
        addressability was that of hash - coding. For those unfamiliar
        with the term, hash-coding is simply a technique whereby an
        arithmetic transformation is applied to an external name to
        generate an internal address.
        
        
        Hash-coding by itself provides a restricted but significant
        approximation to content addressability, but hashing alone does
        no provide any kind of associativity, and there is always the
        problem of the "collision", i.e., when two distinct names hash
        to the same internal address. Hashing partitions the space of
        names into equivalence classes. Hopefully, each class has only
        one element, but two or more names may be equivalent under this
        partition.
                 
        I - Introduction                                  <Page No.   5>
        ----------------------------------------------------------------
        
        
        
        By providing an interpretive language with an associative data
        structure it is possible to achieve great flexibility. To this
        end, it is appropriate to use an existing interpreter and give
        it a new data structure, rather than starting at the bottom by
        designing a special purpose interpreter.
        
                 
        II - Background                                   <Page No.   6>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||                  II - TRAMP - Background                   ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        An associative processor is one possible tool for information
        storage and retrieval, and its history should be discussed
        relative to such systems. Unfortunately, adequate comparisons of
        different types of data systems are difficult to make because
        they are predicated on different rules.
        
        
        Thus the prime method of storage may vary from cards or paper
        tape, through magnetic devices to computer memory; more advances
        are still being made involving laser disc technology. At the
        same time the storage may be either random or ordered according
        to some schema.
        
        
        Finally, the retrieval of the information may be gross, such as
        the use of a mechanical sort based on some algorithm, or simple
        because the data were stored for such answers or because there
        is a well developed language to address the stored data.
        
        
        Thus we have three possible criteria for comparison of systems:
        the type of storage, the way of entering data into that storage,
        add the language for addressing that storage. The spectrum of
        potential systems is therefore large and varied. We will
        consider only those which use main computer memory as the
        storage device (including virtual or paged memory).
        
        
        One inherent bias of computer design affects the storage of
        data: the use of sequential storage, where the data are placed
        in numbered or ordered cells. Because this organization system
        allows the automatic "indexing" of information by means of some
        automatically varied register, the preferred method of storage
        is tabular.
        
        
        Fortunately, tables are excellent ways of storing information,
        for the parallel entries are ways of expressing associations
        between objects as illustrated in the table below.
        
        
        ITEM    NAME      FATHER OF       BROTHER OF     MOTHER OF
        
          1     JOHN      EDITH|ARNOLD    SAM|JOAN
          2     ARNOLD    JAMES           EDITH
          3     MARY                                     ARNOLD
          4     EDITH                                    MELISSA
        
        
        Hence an index may carry the association and we can respond to
        the query: "Who is the mother of Arnold?" by scanning the
        "mother of" column, picking the index 3 at the entry "Arnold"
        and returning "Mary" from the "3 position" of NAME.
        
                 
        II - Background                                   <Page No.   7>
        ----------------------------------------------------------------
        
        
        
        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 [16] add SLIP [21]. The former elucidated and refined the
        method of pointers and lists, and the ideas of association lists
        (Figure II-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 in
        Figure II-2b could be written:
        
        
                <Attribute A> of <object a> = <Value A>
        
                <Son> of <Arnold> is <James>     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 crystallized by Sutherland
        [20], and Roberts [17], and used with data systems designed
        primarily for graphics and computer aided design.
        
        
        Roberts also developed a language to refer to rings (Class
        Oriented Ring Associative Language - CORAL) In such languages,
        the associations are built into sthe 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 II-3. Dodd [1] has implemented a similar structure within
        PL/1.
        
        
        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. It should be noted that there is no need for NUBS if we         
        II - Background                                   <Page No.   8>
        ----------------------------------------------------------------
        
        
        are willing to store all inverse and similar relationships
        explicitly, with separate rings for each.
        
        
        In essence, the NUB represents a two-way switch for transferring
        out of one ring and into another. The subroutines or aacros 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 II-4) and requiring
        sophisticated garbage collectors. A survey by Gray [5] describes
        these and similar structures.
        
        
        Probably the first conception of a true relational data
        structure was Kochen's AMNIPS [7,8]. 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 at that time.
        
        
        A considerable amount of work has been done on various "question
        - answering machines". Among the better early machines were
        Lindsay's SAD SAM [11] which can digest English statements about
        family relationships and construct a family tree, and the
        BASEBALL program of Green, et al. [6] 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.
        
        
        Maron and Levien [9,10,12] designed a system which depended 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 used the ideas of hash-coding for association tables
        [3,4]. 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.         
        II - Background                                   <Page No.   9>
        ----------------------------------------------------------------
        
        
        
        
        The language now allows for certain kinds of restricted
        composition of associations. Specifically, if a sentence is a
        triple <A,O,V>, then O 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 more cumbersome, and less
        economical of storage, than a strict logical inference
        capability.
        
        
        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 II-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.
        
        
        
        
                 
        II - Background                                   <Page No.  10>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||              Figure II-2 - Association Lists               ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        II - Background                                   <Page No.  11>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||            Figure II-3 - Associations by Rings             ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        II - Background                                   <Page No.  12>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||      Figure II-4 - Addition of Association with Rings      ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        II - Background                                   <Page No.  13>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||  Figure II-5 - Binary 4 Generation Male Generational Tree  ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        III - General Description                         <Page No.  14>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||             III - TRAMP - General Description              ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        TRAMP (originally Timeshared Relational Associative Memory
        Processor) is two packages of functions:
        
                1.      Data Structure
                2.      Relational Memory
        
        
        The first may be used to enter, retrieve, and generally
        manipulate an associative data structure.
        
        
        The second 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 have at one time been
        embedded in the UMIST interpreter at the University of Michigan
        on an IBM/360 model 67. They may also be embedded in a variety
        of other interpreters since 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 and other facilities that the
        interpreter provides. The relational package is totally
        dependent on the associative data structure.
        
         __________________                                             
        ||                ||  Feldman's   initial   work  was  a  strong
        ||The Associative ||  motivation  in  the design of this system,
        || Data Structure ||  and  led  the original authors of TRAMP to
        ||                ||
         __________________   adopt  his  notation,  viz.,  the  generic
                              entity:                                   
        
        
        
                        A (O)  =  V
        
           <Attribute>  of  <Object>  equals <Value>
        
                 
        III - General Description                         <Page No.  15>
        ----------------------------------------------------------------
        
        
        
        Thus the "Associative Triple" is: <A,O,V>. 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. This is in contrast to the relational package which
        places an artificial structure on the triple, calling the first
        component a "relation" and the second and third its arguments.
        
        
        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
        reordering, they are:
        
        
                        F0              A  (O) = V
                        F1              A  (O) = x
                        F2              A  (x) = V
                        F3              A  (x) = y
                        F4              x  (O) = V
                        F5              x  (O) = y
                        F6              x  (y) = V
                        F7              x  (y) = z
        
        
        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 F0 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 in fact returned 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 data 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              false
                2.      COLOR (CAR) = RED|GREEN         true
                3.      COLOR (CAR) = RED|BLUE          ?
                4.      COLOR (CAR) = RED               true
                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:
        
        
        true    - If all associations implied by the question are
        resident in memory, or derivable therefrom, the value returned
        is the "true argument.
                 
        III - General Description                         <Page No.  16>
        ----------------------------------------------------------------
        
        
        false   - If none then the value is the false argument
        
        ?       - If some, but not all, the value is the ? argument
        
        
        Questions F1 to F6 simply ask the system to "fill in the
        blank(s)", that is to say 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(O) equals. Question F3 asks for the
        sets of all Os and Vs that have a first component "A".  Because
        of the recursive nature of the host interpreter, questions F1 to
        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, to any level.
        
        
        For those totally unfamiliar with typical interpreters suitable
        as a host to TRAMP, it is necessary to know only the syntax of a
        function call. For the purpose of this paper the syntax of the
        SAM76 language shall be used. The (%) percent sign signals the
        start of a function call and the (/) the end of the call.
        
        
        Alternatively one could use the syntax of the AT&T Bell Labs M6
        language where the (#) sign signals the start of the function
        call and the (:) the end of the call.
        
        
        The arguments are separated by commas and the first argument is
        the name of the function.
        
        
                        %sub,ARG/
                        #sub,ARG:
        
        are therefore analogous to the FORTRAN
        
                        CALL    SUB(ARG)
        
         __________________                                             
        ||                ||  The name of the storage function is "dr" -
        || Data Structure ||  define relationship, and the syntax of the
        ||    Storage     ||  call  is:  %dr,A,O,V/.  Again,  the  three
        ||                ||
         __________________   arguments to "dr" are each non-empty sets.
                              Each point in the cartesian product of the
        three  sets  is stored, ie., 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.   
        
                 
        III - General Description                         <Page No.  17>
        ----------------------------------------------------------------
        
        
        
        The storage declaration:
        
                        %dr,AGE,JOHN|MARY,64/
        
        would therefore store:
        
                        AGE (JOHN) = 64
                        AGE (MARY) = 64
        
        
        The actual storage is accomplished by pairing each A and O to
        point to a list of V's; each A and V point to a list of O's,
        etc. These "answer" lists are, strictly speaking, unordered,
        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" merely 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.
        
         __________________                                             
        ||                ||  The  primary  retrieval  function  has the
        ||      Data      ||  mnemonic   "far"   -   Fetch   Associative
        ||   Retrieval    ||  Relations. The syntax of the function call
        ||                ||
         __________________   is  identical  to  that of "dr" except for
                              variable   specifications   and   optional
        "true,  false  or  ?"  values. A variable in TRAMP is denoted by
        enclosing  a  name,  possibly  null, within asterisks (*). Thus,
        %far,A,O,V,t,f,?/  has no variables and asks whether A(O) equals
        V;  %far,A,O,*X*/  asks: what does A(O) equal?". If the variable
        is  "named",  i.e.,  there  is a name within asterisks, then the
        function  is  null  valued  and the answer is stored in the host
        interpreter text area labeled by the Name. %far,A,O,*ANS*/ would
        store  the set of Vs which A(O) equals under the label "ANS". If
        the  variable  is  not  named  (that  is  to say a null string),
        %far,A,O,**/,  then  the  value  of  the function is the answer. 
        
        
        A two variable question is illustrated by %far,A,*SETO*,**/. In
        this case there is one Named and one Unnamed variable. The
        result in this case would be that the set of Os is placed in
        text area 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         
        III - General Description                         <Page No.  18>
        ----------------------------------------------------------------
        
        
        components, questions F3, F5 and F6, although considerably
        slower than 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
        the data structure. The three variable question, %far,**,**,**/
        is of course the slowest of all and it is a full dump of the
        associative memory. Alternatively, one can call: %daa/ - Dump
        All Associations.
        
        
        Going back to the earlier example of JOHN and MARY, the question
        %far,AGE,JOHN|MARY,**/ should have as its value 64|64k. That is,
        redundancies can be valid and should be reported. But there are
        certain times, particularly in two variable questions, when
        redundancies become quite a nuisance (and may even threaten to
        overflow the host interpreter). Therefore the function "far"
        will always return an answer set with all redundancies deleted.
        A second entry point is provided with the name "frr" - Fetch
        Redundant Relationships, which is identical except that it does
        not check for redundancies but returns the answer set as it
        finds it.
        
        
        The function "far" generates the union of the answer sets. That
        is, the question: %far,AGE,JOHN|MARY,**/ has two answer sets:
        the AGE of JOHN and the AGE of MARY. "far" simply forms the
        "union" of however many sets there might be. "fir" - Fetch
        Intersecting Relationships is the function which generates the
        "intersection" of the several answer sets. Thus
        %fir,SOUTH|WEST,AUGUSTA,**/ generates the set of all things both
        south and west of Augusta. %far,SOUTH|WEST,AUGUSTA,**/, on the
        other hand, would generate the set of all things either south or
        west of Augusta.
        
        
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||        Early Implementation Details in Attachment 1        ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        IV - Logical Inference                            <Page No.  19>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||               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 (Note IV-1). 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 "dlr" - Define Logical Relationship. The syntax of
        the function call is: %dlr(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 "dlr", 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 (Note
        IV-2):
        
        
                R(x,y)   <->   .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
        symetric relation is its own converse.
        
        
        The second is "RELATIVE PRODUCT". The relative product or
        "composition" of two relations is commonly denoted by
        
                R1 .RP. R2, and this is the notation used by TRAMP.
        
        
                \/ x \/ y -| z [(R1/R2)(x,y) <-> R1(x,z) /\ R2(z,y)]
        
                 
        IV - Logical Inference                            <Page No.  20>
        ----------------------------------------------------------------
        
        
        
        Less rigorously, but more specifically,
        
                %dlr,(R3 = R1 .RP. R2)/
        
        would tell TRAMP that R3(x,y) if a "z" can be found such that
        R1(x,y) and R2(z,y).
        
        
        Besides these two relational operators, three logical operators
        are available:
        
        
                .A.     "conjunction" {AND}
                .V.     "disjunction" {OR}
                .N.     "negation" {NOT}
        
        
        Finally there are six equality operators: .EQ.; .NE.; .GE.;
        .LE.; .GT.; and .LT. with obvious meanings.
        
        
        Examples of TRAMP relational definitions are:
        
        
           %dlr,(BIGGGER = BIGGER.RP.BIGGER)/ Bigger is transitive
        
           %dlr,!BIGGER(A,B) = BIGGER(A,Q) .A. BIGGER (Q,B)//
        
        is exact same definition using expanded format specifying dummy
        arguments.
        
        
           %dlr,(SIB = BRO .V. SIS .V. .CON.SIB)/
        
        a sibling is a brother or a sister and it is symetric.
        
        
           %dlr,(HUSBAND = .CON. WIFE)/ Husband as converse of Wife.
        
        
           %dlr,(BIGGER = LARGER)/  Bigger and Larger are synonymous.
        
        
           %dlr,!BRO(CAIN,ABEL) = SIB(CAIN,ABEL,"MALE")//
        
        A brother is a male sibling. Note that constants are denoted by
        enclosing them within double quotes.
        
        
           %dlr,!MALE(X) = SEX(X,"MALE")// defined unary relation MALE.
        
        
           %dlr,!BRO(X,Y)=DAD(X,Z).A.DAD(Y,Z) .A.MALE"(Y).A.X.NE.Y//
        
        a brother is a male offspring of the same dad, other than
        oneself.
        
        
           %dlr,!STEPMOTHER = FATHER.RP.SPOUSE .A. .N. MOTHER//
        
        a stepmother is spouse of the father who is not the mother.
        
        
           %dlr,!NEPHEW = SIBLING .RP. SON//
        
        a nephew is the composition of sibling and son.
        
                 
        IV - Logical Inference                            <Page No.  21>
        ----------------------------------------------------------------
        
        
        
           %dlr,!UNCLE = .CON. (SIBLING/SON)//
        
        in male world, uncle is the converse of nephew and may be
        defined as the converse of the definition of nephew.
        
        
           %dlr,!UNCLE = .CON. NEPHEW// simply as 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.
        
        
           %dlr,(R3 = .N.R1 .V. R2)/  is illegal since it specifies a
                                      global complement (of R1), i.e.,
                                      it references the "whole space"
        
        
           %dlr,(R3 = .N.R1 .A. R2)/  is legal because it specifies
                                      a relative rather than a global
                                      complement, i.e., R1 places a
                                      constraint on R2 not on the
                                      "whole space".
        
        
         __________________                                             
        ||                ||  The  purpose of the inference mechanism is
        || Implementation ||  to  allow  the  user  to define under what
        ||  of Inference  ||  conditions  an  implied association may be
        ||                ||
         __________________   derived  from  data  explicitly in memory.
                              This  is  accomplished by generating where
        necessary  (where  defined) a more complex retrieval call from a
        simple  one.  Specifically, if the following definition had been
        entered:   
        
        
           %dlr,(STEPMOTHER = FATHER .RP. SPOUSE .A. .N. MOM)/
        
        
        then the following simple retrieval call:
        
           %far,STEPMOTHER,JOHN,**/
        
        which asks for the stepmother of John, would be expanded by the
        system to be the following:
        
        
         %frc,%far,SPOUSE,%far,FATHER,JOHN,**/,**/,%far,MOM,JOHN,**//
         %far,STEPMOTHER,JOHN,**/
        
        
        The exact call generated would be slightly different, but that
        is a technicality, irrelevant at this point. The final retrieval
        call in the sequence generated asks if the desired association
        was entered explicitly. It is always assumed that a relation
        that has been given a definition may also appear explicitly.
        
                 
        IV - Logical Inference                            <Page No.  22>
        ----------------------------------------------------------------
        
        
        
        The rest of the expanded call will find the answer if it is
        present implicitly. This expanded call is then returned to the
        host interpreter which in turn makes the actual calls to the
        data structure.
        
        
        The importance of this is that relations need be expanded only
        one level at a time, with the host interpreter recursion
        automatically taking care of the possibility that any relation
        is defined in terms of more complex relations, etc. (this is the
        major difference between the call as it actually would be
        generated, and as it appears above. The above, taken literally,
        would specify an infinite recursion!).
        
        
        Thus the inference compiler generates TRAMP procedures, they
        operate only within the TRAMP system, not at a lower, machine
        level. The definition, entered by %dlr,.../, specifies what
        information the procedure is to derive and what rules may be
        used to derive it; the compiler accordingly constructs such a
        procedure; and the interpreter (TRAMP inference interpreter -
        rather than the host interpreter) expands the procedure at
        retrieval time, filling in information specific to the call.
        
        
        At retrieval time, a retrieval "preprocessor" looks to see if
        the "relation" ("A" component) has been given a definition. If
        not, the preprocessor exits and retrieval proceeds as described
        earlier. If the name is found to have been defined, then the
        "interpreter" is called in to interpret the program generated by
        the compiler at the time it was defined. This program tells the
        interpreter what TRAMP function calls are to be made, and what
        the function arguments are to be.
        
        
        It should be noted that the compiler actually puts out two
        programs: one which, given x of R(x,y), builds a chain to
        generate y; the other builds the appropriate chain in the
        opposite direction, from y to x. Thus question F1: %far,A,O,**/
        generates a different sequence of function calls than F2:
        %far,A,**,V/.
        
        
        It may not be immediately obvious why this is necessary, but in
        general, the two programs will be quite different. This is
        always the case for composition. Still, the compiler would only
        have to output one program, and the interpreter could decide how
        to interpret it. Since the compiler will usually be called only
        once or twice for each relation, or certainly fewer times than
        the interpreter, it is most efficient to let the compiler do as
        much of the work as possible.
        
        
        The compiler is prepared to handle definitions which are
        circular in the sense that a relation is defined in terms of
        itself. That is, symmetric and transitive relations are
        perfectly acceptable. However, the sequence:
        
                 
        IV - Logical Inference                            <Page No.  23>
        ----------------------------------------------------------------
        
        
        
           %dlr,(PPP = QQQ .V. ...)/%dlr,(QQQ = PPP .V. ...)
        
        is invalid because of its circularity. Were the compiler to
        attempt to generate code for this sequence, the code would
        specify an infinite recursion. This situation is checked for and
        flagged if detected.
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        NOTES:
        
        IV-1    As the size of storage increases, there are more
        collisions, but they are quickly resolved, and do not cause
        significant delay. Even in extreme pathological cases, they
        involve relatively minor list searches.
        
        
        IV-2    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(O) = V, but the order is preserved: R(x,y) means
        that R(x) = y.
        
                 
        V - Internal organization                         <Page No.  24>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||              V - TRAMP INTERNAL ORGANIZATION               ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||         For time being see attachments for details         ||
        ||                                                            ||
        ||      of original - 1968 - TRAMP internal organization      ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        VI - Primitive Functions                          <Page No.  25>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||               VI - TRAMP Primitive Functions               ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
                            List of TRAMP functions                     
        
        
        
        1968    1984
        ver.1   ver.2   Function name
        
        
        dr      dr      Define Relationship
        kr      er      Erase Relationship
        rl      far     Fetch Associative Relationship
        rlr     frr     Fetch Redundant Relationship
        int     fir     Fetch Intersecting Relationship
        
        
        rcom    frc     Fetch Relative Complement
        symd    fsd     Fetch Symetric Difference
        int2    fis     Fetch Intersecting Set
        dump    daa     Dump All Associations
        dump2   dar     Dump All Relationships
        erm     erm     Erase Relational Memory
        use     qne     Query Number of Explicit associations
        
        
        ct      qsc     Query Set Cardinality
        table   lat     List Attribute Table
                lot     List Object Table
                lvt     List Value Table
                ldt     List Defined relationship Table
        prime           not used
        tramp           not used
        save    srf     Save Relational File
        copy    brf     Bring Relational File
        
        
        page    qra     Query Relational Area
        ddr     dlr     Define Logical Relationships
        kdr     elr     Erase Logical Relationships
        show    vlr     View Logical Relationship
        edit    clr     Correct Logical Relationship
        ddef            not used
        
                 
        VI - Primitive Functions                          <Page No.  26>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||            %dr,A,O,V/      Define Relationship             ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        This null valued function performs the associative storage task
        by inserting the data into the structure.
        
        
        The three arguments A, O, and V, are each non-empty sets. The
        set element delimiter is the vertical bar (|) because of the
        important role played by the comma in the host interpreter
        language. The triple is ordered and interpreted as meaning: A(O)
        = V.
        
        
        Each element of each set is grouped with each pair of elements
        of the other two sets, and the resulting triple is stored, i.e.,
        each point in the cartesian product is stored. The three sets
        are ordered only inasmuch as the order in which they appear in
        the storage declaration is retained.
        
        
        The "DR" function simply inserts the data into the structure in
        a way in which it can be efficiently retrieved. No check is made
        for inconsistency of data or for redundancies.
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %dr,COLOR,CAR,RED|GREEN/
        	o  %dr,AGE,MABLE|EUNICE,39/
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        
        The first of the above two examples would store:
        
                COLOR (CAR) = RED
                COLOR (CAR) = GREEN
        
        
        The second of the examples would store:
        
                AGE (MABLE) = 39
                AGE (EUNICE) = 39
        
                 
        VI - Primitive Functions                          <Page No.  27>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||            %er,A,O,V/       Erase Relationship             ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of this null valued function is to undo what
        function "dr" did. That is to say this function erases an
        association from memory.
        
        
        The syntax of this function is exactly the same and the effect
        exactly the opposite of function "dr".
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %er,COLOR,CAR,RED/
        	o  %er,AGE,%far,AGE,**,*X*,%X//
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        
        The first example above removes the association:
        
                COLOR (CAR) = RED
        
        
        The second example deletes all associations containing "AGE" as
        the "A" component. (See definition of "far" - Fetch Association
        Redundant).
        
                 
        VI - Primitive Functions                          <Page No.  28>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||    %far,A,O,V,t,f,?/    Fetch Associative Relationship     ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        This is the associative retrieval function. "Questions" are
        asked of the data structure by executing "far" and specifying
        which, if any among "A", "O", and "V" are variables.
        
        
        Variables are denoted by enclosing a name, possibly null, within
        asterisks (*). To ask the question: "What color is the car?",
        one would write: %far,COLOR,CAR,**/ or %far,COLOR,CAR,*NAME*/.
        The "answer set" in this example is the set of all third
        components of associations having "COLOR" as the first
        component, and "CAR" as the second.
        
        
        In the first instance above, the variable is not named (nothing
        between the asterisks). In this case, the answer set is the
        value of the function.
        
        
        In the second instance the variable is named, which results in
        the function being null valued, and the answer set being stored
        in the host interpreter text area labelled by the name within
        the asterisks. Thus the following two statements are exactly
        equivalent:
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %dt,ANS,%far,COLOR,CAR,**/
        	o  %far,COLOR,CAR,*ANS*/
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        
        If there are no variables, e.g., %far,COLOR,CAR,RED,t,f,?/, then
        the question being asked is "Does A(O) = V?", or in this case
        "Is the car colored red?". The value of this function is then
        either that argument denoted as "t" if true or "f", if farlse.
        
        
        If one or more of the three sets has cardinality greater than
        one, then the value is that argument denoted by "?".
        
        
        If there is one variable, then the "blank" is filled in. The one
        variable may be in any of the three positions of the triple. The
        variable may be either named or unnamed, with the respective
        consequences described above.
        
        
        If there are two variables, then two answer sets are generated.
        One of the variables is picked as the index variable, and values
        are one-by-one substituted for it, internally iterating on the
        one-variable question.
        
        
        The one constant may again be in any of the three positions of
        the triple.  If both variables are named, the function is null
        valued, and the two answer sets are stored and labelled by their         
        VI - Primitive Functions                          <Page No.  29>
        ----------------------------------------------------------------
        
        
        respective names. If one is named and the other unnamed, then
        the set corresponding to the named variable is stored and the
        other answer set is the value of the function. It is
        syntactically valid for both variables to be unnamed, but this
        should not be done since the value of the function would be the
        concatenation, not union, of the answer sets.
        
        
        The two variable questions generate two answer sets, not a set
        of ordered pairs! If this is desired the user will have to write
        a short procedure witten in the host interpreter language to
        pick out the proper subset of the cartesian product of the two
        answer sets.
        
        
        This form of the two variable questions, generating two answer
        sets, is used to find ALL "objects" associated with some other
        "objects", without regard for the third component of the triple.
        For example, to find all those who have sons, one could say:
        
                %far,son,**,*X*/
        
        with the set of all sons now being stored in the text named "X".
        In general this generated set, here the set "X", will not be
        further used and is not wanted.  If an asterisk is used as the
        name of the variable, then this is construed to mean that the
        corresponding answer set is not to be generated, thus:
        
        %far,son,**,*sons*/     would return the set of all those who
        have sons, and store the set of all sons in the text named
        "sons".
        
        
        %far,son,**,*sons*/%et,sons/    would likewise return the set of
        all those who have sons, but would discard the set of sons.
        
        
        If there are three variables it is interpreted as being a
        request for a dump of the associative memory. If any of the
        three variables are named, the names are ignored, Alternatively
        one can simply execute the %daa,x,.../ function.
        
                 
        VI - Primitive Functions                          <Page No.  30>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||    %frr,A,O,V,t,f,?/     Fetch Redundant Relationships     ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of this function is to retrieve answers that may
        contain redundancies.
        
        
        This function is identical to "far" except that any redundancies
        are reported. "far" returns non redundant answer sets, while
        "frr" does not check for redundancies and is therefore
        significantly faster.
        
        
                %frr,AGE,EUNICE|GLADYS,**/
        
        If they are both 31, then the value will be 31|31.
        
                 
        VI - Primitive Functions                          <Page No.  31>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||   %fir,A,O,V,t,f,?/     Fetch Intersecting Relationships   ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        This function generates intersections of answer sets.
        
        
        This has the same syntax as the one variable form of "far".
        Whereas "far" generates the union of the answer sets, "fir"
        generates the intersection.
        
        
                %far,SOUTH|WEST,TOLEDO,**/
        
        generates the set of all things either south or west of Toledo.
        
        
                %fir,SOUTH|WEST,TOLEDO,**/
        
        generates the set of all things both south and west of Toledo.
        
        
        If both constant sets are singletons, "fir" and "far" will yield
        identical answer sets. The variable may again be in any of the
        three positions and be be either named or unnamed. This function
        must have "exactly one" variable.
        
                 
        VI - Primitive Functions                          <Page No.  32>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||       %frc,set1,set2/     Fetch Relative Complement        ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of this function is to compute the relative
        complement of two TRAMP sets. The value of this function is the
        logical subtraction of the third argument denoted by "set2" from
        the second denoted by "set1".
        
        
           %frc,%far,AGE,**,40/,%far,SPOUSE,**,*X*/,SPINSTER/
        
        This would store in the text labelled "SPINSTER" all those who
        are 40 years old and not married. Note that it was necessary to
        direct part of the answer sets into a temporary text "X", which
        may then be erased at leisure.
        
                 
        VI - Primitive Functions                          <Page No.  33>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||       %fsd,set1,set2/     Fetch Symetric Difference        ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        This function computes the symetric difference of two sets. The
        value of "fsd" is defined as the set of all things that are in
        either of the two sets, but not in both (exclusive OR). The
        syntax of "fsd" is identitcal to that of "frc".
        
        
                %fsd,%far,BRO,**,*X*/,%far,SIS,**,*X*//
        
        This would return as its value the set of all those who have
        siblings, but siblings of only one sex.
        
                 
        VI - Primitive Functions                          <Page No.  34>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||        %fis,SET1,SET2/     Fetch Intersecting Sets         ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of this function is to intersect two TRAMP sets. The
        value of this function is the straight intersection of the sets
        denoted SET1 and SET2. Any redundancies that might exist because
        the sets are generated by "frr" are deleted.
        
        %fis,%fir,NORTH|EAST,CHICAGO,**/,%fir,SOUTH|WEST,MAINE,**//
        
        shows how the two nested "fir" return as arguments to "fis" sets
        such that the value of the full expression is the set of all
        things that are both north|east of CHICAGO and south|west of
        MAINE.
        
                 
        VI - Primitive Functions                          <Page No.  35>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||            %daa,.../     Dump All Associations             ||
        ||           %dar,.../     Dump All Relationships/            ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of these functions is to obtain a "dump" of
        everything that is explicitly stored in the data structure.
        
        
        All associations explicitly stored are output using the A(O)=V
        format. A and O are singletons, and V is the set of all "values"
        associated with the A/O pair.  Any redundancies in the "V" set
        are output. Implied associations are not listed in the "daa"
        dump.
        
        
        The "dar" dump outputs all current relational definitions
        [entered by the "ddr" function].
        
                 
        VI - Primitive Functions                          <Page No.  36>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||             %erm/     Erase Relational Memory              ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        This null valued function completely erases the relational
        memory.
        
                 
        VI - Primitive Functions                          <Page No.  37>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||    %qne,NAME/    Query Number of Explicit associations     ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of this function is to determine the number of
        explicit associations that the "NAME" is used in.
        
        
        The value of the function is the total number of associations
        that the name in the second argument is used in. Any implied
        associations are not included in the count.
        
        
                %qea,COLOR/
        
        tells how many objects have the attribute COLOR.
        
                 
        VI - Primitive Functions                          <Page No.  38>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||            %qsc,SET/     Query Set Cardinality             ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of "qsc" is to determine the cardinality of ta TRAMP
        set. The value of this function is the number of terms in a set.
        It distinguishes between a missing argument, a null set and a
        singleton (set with no bars).
        
                 
        VI - Primitive Functions                          <Page No.  39>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||             %lat,s0/     List Attribute Table              ||
        ||               %lot,s0/     List Object Table               ||
        ||               %lvt,s0/     List Value Table                ||
        ||          %ldt,s0/     List Defined Relation Table          ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of this family of functions is to obtain the
        contents of the various Name tables.
        
        
        The value returned by these various functions is a list of the
        names of the particular desired table, each name preceded by the
        string denoted by "s0".
        
                 
        VI - Primitive Functions                          <Page No.  40>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||             %srf,.../     Save Relational File             ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        To be defined when structure is designed.
        
        
        
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||            %brf,.../     Bring Relational File             ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        To be defined when structure is designed.
        
                 
        VI - Primitive Functions                          <Page No.  41>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||              %qra/     Query Relational Area               ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The value of this function is a measure of the size of the space
        occupied by the defined associations and relationships.
        
                 
        VI - Primitive Functions                          <Page No.  42>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||     %dlr,(REL = EXP)/     Define Logical Relationship      ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The purpose of the "dlr" function is to define a relation in
        terms of other relations, thereby creating implicit associations
        in the data structure.
        
        
        In the expression, "REL" is the relationship being defined, and
        "EXP" is an expression which is the definition. The equal sign
        is the delimiter and must be present. Although not required it
        is advisable to always enfold the relationship being defined in
        a pair of matched parentheses.
        
        
        EXP is composed of one or more relations joined by, logical
        connectives, relational operators or equality operators:
        
        
                .A.     Conjunction {AND}
                .V.     Disjunction {OR}
                .XV.    Exclusive Or {XOR}
                .NV.    {NOR}
                .N.     Negation {NOT}
        
                .RP.    Relative Product or composition
                .CON.   Converse
        
                .EQ.    Equal
                .NE.    Not Equal
                .GE.    Greater or Equal
                .LE.    Less than or Equal
                .GT.    Greater Than
                .LT.    Less Than
        
        
        The "R(x,y)" format is the relational format adopted by TRAMP
        and is interpreted to mean that a R(x) = y.
        
        
        "Converse" simply inverts the order of the two relational
        arguments R(x,y) <-> .CON.R(y,x). Thus "child of" is the
        converse of "parent of", any symetric relation is its own
        converse.
        
        
        Composition is defined:
        
                \/ x \/ y -| z [(R1/R2)(x,y) <-> R1(x,z) /\ R2(z,y)]
        
        
        Specifically, the declaration: %dlr,(R=S .RP. T)/ would tell
        TRAMP that R(x,y) if for some z: S(x,z) and T(z,y).
        
        
        Function "dlr" is the only TRAMP function that allows spurious
        white space, blanks, tabs, and new line codes. Before compiling
        the definition all spurious white spaces are removed.
                 
        VI - Primitive Functions                          <Page No.  43>
        ----------------------------------------------------------------
        
        
        
        Definitions may be either abbreviated:
        
                %dlr,(R1 = R2 .V. R3)/  or in an expanded form
                %dlr,(R1(X,Y) = R2(X,Y) .V. R3(X,Y))/
        
        There is a restriction that any one definition be consistent.
        
        
        The two relational operators, composition and converse may be
        used only in abbreviated definitions where ther are no explicit
        relational arguments. On the other hand, the equality operators
        may only be used with relational arguments as their operands. A
        constant which is to be used as a relational argument is denoted
        by enclosing the name of the argument between double quotes (").
        
        
        The precedence ordering of the various operators is as follows:
        
        
                .RP.    Relative Product or composition
                .CON.   Converse
                .EQ.    and all other equality operators
                .N.     Negation
                .A.     Conjunction
                .V.     Disjunction
        
        
        The above precedence ordering may be altered in the usual way
        using parentheses appropriately.
        
        
        One major constraint is placed on the argument to "dlr":
        relation must be defined so that at least one set is generated.
        The intent of this constraint is that there be at least one
        reference set. The "whole space" may never be the reference set!
        
        
           %dlr,(R = .N. S)/    is illegal, since it specifies a
                                global component, i.e., it references
                                the whole space.
        
        
           %dlr,(R = .N. S .A. T)/  is legal, since it first generates
                                    a reference set via T, and then
                                    places a constraint on that
                                    reference set, not on the whole
                                    space.
        
        
        Besides the choice of using the "expanded" vs. "abbreviated"
        notation for defining a relation, the user has the option of
        specifying whether or not the implication is one way, or
        specifies an if and only if condition.
        
        
                HUSBAND = .CON. WIFE
        
        is an "iff" condition whereby it is implicit that:
        
                WIFE = .CON. HUSBAND
        
        the equal sign will be used to denote this kind of equivalence
        which can be interpreted as meaning "iff".         
        VI - Primitive Functions                          <Page No.  44>
        ----------------------------------------------------------------
        
        
        
        
        On the other hand:
        
                PARENT := FATHER or MOTHER
        
        is one-way implication, giving information about the relation
        "parent" while giving none about the relations "father" or
        "mother". To denote this the "assignment symbol" (:=) is used.
        
        
        In general, if the assignment symbol is used then no attempt
        will be made to extract information about the relations on the
        right side of the equation. If the equality symbol is used, such
        an attempt will be made. This attempt will not, of course,
        always be successful:
        
        
                PARENT = FATHER .V. MOTHER
        
        gives us no information about "father" or "mother" even though
        the equality sign is used.
        
        
        If a relation is defined, and later a new definition is given
        for that same relation, TRAMP simply OR's the two definitions
        together. If there is a syntactic error in the second defintion,
        a diagnostic is printed and the earlier definition is retained.
        
        
        EXAMPLES:
        
        
                %dlr,(BIGGER = BIGGER .RP. BIGGER)/
                        Bigger is Transitive
        
        
                %dlr,(BIGGER(A,B)=BIGGER(A,C) .A. BIGGER(C,B))/
                        same definition using expanded format.
        
        
                %dlr,(SIB=BRO .V. SIS .CON. SIB)/
                        a sibling is defined to be a brother
                        or sister and it is symetric.
        
        
                %dlr,HUSBAND = .CON. WIFE/
                        Husband is the converse of wife.
        
        
                %dlr,(BRO(CAIN,ABEL)=
                        SIB(CAIN,ABEL) .A. SEX(ABEL,"MALE"))/
                        A brother is a male sibling. Constants
                        are enclosed in double quotes. Extra
                        line feeds and tabs are ignored.
        
        
                %dlr,BIGGER = LARGER/
                        bigger and larger are synonymous.
        
        
                %dlr,(MALE(X) = SEX(X,"MALE"))/
                        unary relations may be defined
        
                 
        VI - Primitive Functions                          <Page No.  45>
        ----------------------------------------------------------------
        
        
        
                %dlr,(BROTHER(X,Y)=
                FATHER(X,Z).A.(FATHER(Y,Z).A.MALE(Y).A.X.NE.Y)/         
        
                        A brother can be defined as the male
                        offspring of the same father other
                        than oneself.
        
        
                %dlr,(PARENT = FATHER .V. MOTHER)/
                %dlr,(NEPHEW = SIBLING/SON)/
                        a nephew is composition of sibling and son.
        
        
                %dlr,(UNCLE=.CON.(SIBLING .RP. SON))/
                        In a male world, uncle is the converse of
                        nephew and may be defined as the converse
                        of nephew.
        
        
                %dlr,(UNCLE = .CON. NEPHEW)/
                        or simply as converse of nephew.
        
        
                %dlr,(STEPMOTHER=FATHER .RP. SPOUSE .A. .N. MOTHER)/
                        a stepmother is spouse of the father
                        who is not the mother.
        
                 
        VI - Primitive Functions                          <Page No.  46>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||   %elr,REL1,REL2,...RELn/     Erase Logical Relationship   ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        Function is used to erase defined relationships. It may have an
        arbitrary number of arguments which denote the names of the
        relationships to be erased.
        
                 
        VI - Primitive Functions                          <Page No.  47>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||        %vlr,RELATION,s0/     View Logical Relation         ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        This function will output the definition of the relation
        specified by the second argument exactly as it was entered by
        the user, except that spurious blanks will have been removed.
        (possibly without blank removal).
        
        
        If more than one definition has been given for the relation,
        they will be concatenated, separated by the string denoted by
        "s0" in the expression.
        
                 
        VI - Primitive Functions                          <Page No.  48>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||        %clr,REL,S1,S2/     Correct Logical Relation        ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        This function is used to edit or correct defined relations. In
        the relation whose name is denoted by "REL", patterns denoted by
        the string "S1" are replaced by the string denoted by "S2".
        
        
        This is a null valued function. If invoked actively: %clr,.../,
        then all occurrences of the pattern are replaced. If invoked
        neutrally: &clr,.../, then only the first occurrence is
        replaced.
        
        
        EXAMPLES:
        
        
                %clr,SIB,(.V.),(.A.)/
        
                        Change all occurrences of OR to AND in
                        the definition of SIB.
        
        
                &clr,SIB,(.V.),(.A.)/
        
                        Change the first occurrence of
                        OR to AND in definition of SIB.
        
        
                %clr,REL,(.A. R4)/
        
                        Remove all occurrences of ".A. R4"
                        from the definition of REL.
        
                 
        VII - Examples of use                             <Page No.  49>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||                       VII - Examples                       ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The first set of examples show the "F0" questions of section
        III. First we define the COLOR of CAR to be RED or GREEN. Then
        the various Boolean questions are asked, the value being
        returned after the activating symbol which in this case is set
        to be an equal (=) sign.
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %dr,COLOR,CAR,RED|GREEN/=
        	o  %far,COLOR,CAR,BLUE,t,f,?/=f
        	o  %far,COLOR,CAR,RED|GREEN,t,f,?/=t
        	o  %far,COLOR,CAR,GREEN|RED,t,f,?/=t
        	o  %far,COLOR,CAR,RED|BLUE,t,f,?/=?
        	o  %far,COLOR,CAR,RED,t,f,?/=1
        	o  %far,COLOR,CAR,RED|BLUE|GREEN/=?
        	o  %far,COLOR,CAR,YELLOW|BLUE,t,f,?/=f
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        
        Let us now consider the following table which describes a
        collection of family relationships:
        
        
        ITEM    NAME      FATHER OF       BROTHER OF     MOTHER OF
        
          1     JOHN      EDITH|ARNOLD    SAM|JOAN
          2     ARNOLD    JAMES           EDITH
          3     MARY                                     ARNOLD
          4     EDITH                                    MELISSA
        
                 
        VII - Examples of use                             <Page No.  50>
        ----------------------------------------------------------------
        
        
        
        The next examples refer to previous family table:
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %dr,FATHER,ARNOLD,JOHN/=
        	o  %dr,FATHER,JAMES,ARNOLD/=
        	o  %dr,BROTHER,SAM|JOAN,JOHN/=
        	o  %dr,BROTHER,EDITH,ARNOLD/=
        	o  %dr,MOTHER,ARNOLD,MARY/=
        	o  %dr,MOTHER,MELISSA,EDITH/=
        	o  %dr,AGE,JOHN|MARY,64/=
        	o  %dr,AGE,ARNOLD,39/=
        	o  %dr,AGE,EDITH,33/=
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        
         Two relatively complicated questions are then asked. The first
        may be stated as: "Who are the people who have brothers whose
        age is 64?". To illustrate this in depth, we first ask "Who is
        aged 64?", then "Who are the people who can call this 64 year
        old 'brother'?"
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %far,BROTHER,**,%far,AGE,**,64//=SAM|JOAN
        	o  %far,AGE,**,64/=JOHN|MARY
        	o  %far,BROTHER,**,JOHN/=SAM|JOAN
        	o  %far,BROTHER,**,MARY/=
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        
        Obviously, for one of these people (Mary), there is no answer,
        for no one calls her "brother".
        
        
        The second question asks: "What is the age of the father of the
        brother of Melissa's mother?" Store the answer (this age) in the
        text labelled "NUM". Now Melissa's mother is Edith, Edith's
        brother is Arnold, Arnold's father is John, who is 64 years old.
        Hence a call for the text "NUM" outputs "64".
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %far,AGE,%far,FATHER,%far,BROTHER,%far,MOTHER,`
        	o  MELISSA,**/,**/,**/,*NUM*/=
        	o  %ft,NUM/=64
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
                 
        VII - Examples of use                             <Page No.  51>
        ----------------------------------------------------------------
        
        
        
        The next example shows the first use of "dlr" - Define Logical
        Relationship. We first add to the previous definitions the
        sisterhood of Joan and Alice. The first definition of Sibling
        now allows the retrieval of one of Alice's siblings, though
        Sibling has never appeared explicitly in an association. The
        second definition entered completes the job, and the system is
        now able to return all of Alice's siblings.
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %dr,SISTER,JOAN,ALICE/=
        	o  %dlr,(SIB=BROTHER .V. SISTER .V. .CON. SIB)/=
        	o  %far,SIB,ALICE,**/=JOAN
        	o  %dlr,(SIB(X,Y)=SIB(X,Z) .A. SIB(Y,Z) .A. X.NE.Y)/=
        	o  %far,SIB,ALICE,**/=JOAN|JOHN|SAM
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
         ______________________________________________________________ 
        ||                                                            ||
        ||           Rudimentary Question Answering System            ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        As a more complicated example of the use of this system, a
        rudimentary "question answering system", with thesaurus is
        shown. It should be noted that this illustration is not intended
        to constitute a good system - in fact, it represents a total of
        less than one hour's coding and debugging time.
        
        
        The task of this system is to parse input commands, and from
        them, generate statements. In this regard this system is grossly
        imcomplete, i.e., it uses a most unsophisticated parsing scheme.
        The generated calls are realistic, nonetheless. The complete
        program, used as the question answering system (QAS), may be
        found among the attachments to this paper.
        
        
        To enable the reader to easily follow the dialogue, each
        statement issued by the QAS is initiated by the word: "ANSWER".
        Everything else was typed at the console by the user. QAS has
        been given a thesaurus to relax the format of statements.
        
        
        This thesaurus, as well as all data, is held in the associative
        structure. To make a thesaurus entry, the user types the command
        "SYNONYM" followed by the two synonymous names. A datum is
        entered by the command "INPUT". The questions are self
        explanatory.
        
                 
        VII - Examples of use                             <Page No.  52>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||          Output of Question Answering interaction          ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        
        
        input author of huckfinn was marktwain
        synonym marktwain is samclemens
        what did samclemens write
                ANSWER: ?
        synonym write = author
        what did samclemens write ?
                ANSWER: huckfinn
        did twain write huckfinn ?
                ANSWER: NO
        synonym marktwain and twain
        did twain write huckfinn ?
                ANSWER: YES
        input author of tomsawyer is twain
        input author of thestranger was samclemens
        howmany books did marktwain write ?
                ANSWER: 3
        what did twain write ?
                ANSWER: huckfinn|tomsawyer|thestranger
        input model of ATTPC is 6300
        synonym ATTPC is PC
        which model of PC do we have ?
                ANSWER: 6300
        
                 
        VII - Examples of use                             <Page No.  53>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||            Merging relational structured files             ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The following procedure shows one way that two relational data
        files can be merged. This is necessary because the structures
        must be merged, not merely concatenated (as in the case of the
        host interpreter). Assume that DATA1 and DATA2 are two
        relational files that are to be merged:
        
        	o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        	o  %dt,PARSE,!%dt,X,&is//%ii,&fc,X, ,!%pt,X, /`
        	o  %dr,&fe,X/,&fe,X/,%nul,fe,X/&fe,X//%PARSE//,`
        	o  !%rr,!%PARSE1///////=
        	o  %brf,DATA1/%dof,SCRATCH/%soc,fil/%dar/=
        	o  %brf,DATA2/%dof/%dif,SCRATCH/%sic,fil/%PARSE/=
        	o
        	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        
        By way of superficial explanation: The procedure "PARSE" is
        first defined. This procedure simply reads in "dumped"
        information from the file SCRATCH which will contain the file
        DATA1 in dumped format. It then parses those lines to extract
        the three arguments to "dr". The procedure loops on itself until
        the end of the first part of the file is reached, signalled by
        not having a blank in the first position.
        
        
        The line just read in is partitioned on blanks. The first
        element will be the "A" component; the second element will be
        the "O" component (stripped of the parentheses by using "fe"
        actively); the next segment will be the equal sign and is
        discarded via the "nul" - null function; the last element is the
        "V" component.
        
        
        An analogous procedure could be written and called by PARSE1 to
        read in the rest of the dump which would contain the relational
        definitions, and make those definitions via generated calls on
        "dlr".
        
        
        At completion of PARSE1, it is necessary to restore the I/O
        sytem back to the console by executing %sic,CON/%soc,CON/.
        
                 
        References                                        <Page No.  54>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||                     VIII - REFERENCES                      ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        1.      Dodd, G.G., "APL - A language for Associative Data
        Handling in PL/1," Proc. AFIPS FJCC, November 1966, pp. 677-684.
        
        
        2.      Eastwood, D. E., and M.D. McIlroy, "Macro Compiler
        Modification of SAP," Computer Laboratory Memo, Bell Telephone
        Laboratories, Murray Hill, N.J., September 1959.
        
        
        3.      Feldman, J.A., "Aspects of Associative Processing,"
        Lincoln Laboratories, Lexington, MA, April 1965.
        
        
        4.      Feldman, J.A., and P.D. Rovner, "An Associative
        Processing System for Conventional Digital Computers," Lincoln
        Laboratories, Lexington, MA, April 1967.
        
        
        5.      Gray, J.C., "Compound Data Structure for Computer Aided
        Design: A Survey," ACM National Conference, August 1967, pp.
        355-365.
        
        
        6.      Green, B.F., A.K. Wolf, C. Chomsky, K. Laughery,
        "BASEBALL: An Automatic Question Answer," Computers and Thought,
        ed. E.A. Feigenbaum and J. Feldman, McGraw-Hill, New York, 1963,
        pp. 207-216.
        
        
        7.      Kochen, M., "Adaptive Mechanisms in Digital 'Concept'
        Processing," Discrete Adaptive Processes - Symposium and Panel
        Discussion, AIEE, New York, 1962, pp. 50-58.
        
        
        8.      Kochen, M., "Some Problems in Information Science with
        Emphasis on Adaptation to Use Through Man-Machine Interaction,"
        Vol. 1 & 2, IBM, Thomas J. Watson Research Center, Yorktown
        Heights, N.Y., April 1964.
        
        
        9.      Levien, R.E. and M.E. Maron, "Relational Data File: A
        Tool for Mechanized Inference Execution and Data Retrieval", The
        RAND Corp., RM-4793-PR, December 1965.
        
        
        10.     Levien, R.E. and M.E. Maron, "A Computer System for
        Inference Execution and Data Retrieval," The RAND Corp.,
        RM-5085-PR, September 1966.
        
        
        11.     Lindsay, R.K., "Inferential Memory as the Basis of
        Machines Which Understand Natural Language," Computers and
        Thought, ed. E.A. Feigenbaum and J. Feldman, McGraw-Hill, New
        York, 1963, pp. 217-233.
        
        
        12.     Maron, M.E., "Relational Data File I: Design
        Philosophy," The RAND Corp., P-3408, July 1966.
                 
        References                                        <Page No.  55>
        ----------------------------------------------------------------
        
        
        
        13.     McIlroy, M.D., "Using SAP Macro Instructions to
        Manipulate Symbolic Expression", Computer Laboratory Memo, Bell
        Telephone Laboratories, Murray Hill, N.J., 1960.
        
        
        14.     Hall, Andrew D., "The M6 Macroprocessor," Computer
        Science Report No. 2, Bell Telephone Laboratories, Murray Hill,
        N.J., 1971.
        
        
        15.     Kagan, Claude A. R., "The SAM76 Language," IEEE Computer
        Society Repository, No. R76-301, August 1976.
        
        
        16.     Newell, A. (ed.) "Information Processing Language - V
        Manual," The RAND Corp., Prentice Hall, Englewood Cliffs, N.J.,
        1961.
        
        
        17.     Roberts, L.G., "Graphical Communications and control
        Languages," Second Congress on Information System Sciences,
        Spartan Books, Baltimore Md., 1964.
        
        
        18.     Simmons, R.F., "Answering English Questions by Computer,
        A Survey," Comm. ACM, Vol. 8, No. 1, January 1965, pp. 53-70.
        
        
        19.     Strachey, C., "A General Purpose Macrogenerator,"
        Computer Journal, Vol. 8, No. 3, Oct. 1965.
        
        
        20.     Sutherland, I.E., "Sketchpad, A Man Machine Graphical
        Communication System," Proc. AFIPS 1963 SJCC, Spartan Books,
        Baltimore, MD., pp. 329-346.
        
        
        21.     Weizenbaum, J., "Symetric List Processor," Comm. ACM,
        Vol. 6, No. 9, September 1963, pp. 524-544.
        
                 
        Attachments                                       <Page No.  56>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||                        ATTACHMENTS                         ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        Att. 1          III - General Description cont'd
        
        
        Att. 2          V - 1968 Implementation Details
        
        
        Att. 3          Host Interpreter Description
        
        
        Att. 4          Question-Answer script
        
        
        Att. 5          ARPA Cover Sheet
        
                 
        Attachment - III General Description - Cont'd     <Page No.  57>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||             III - General Description - Cont'd             ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        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, H1, 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 III-1.
        
        
        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 "O" 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,
        H2. "WIFE" must now be placed on the "A Association Table".
                 
        Attachment - III General Description - Cont'd     <Page No.  58>
        ----------------------------------------------------------------
        
        
        
        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 H1 is a
        function of the actual name, while H2 is only a function of
        where the name is stored and is independent of the name itself.
        Figure III-2 shows the Association Tables, both for the
        collision case [2b], and for the normal case [2a].
        
                 
        Attachment - III General Description - Cont'd     <Page No.  59>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||            Figure III-1 - Name Table Structure             ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        Attachment - III General Description - Cont'd     <Page No.  60>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||             Figure III-2 - ASSOCIATION TABLES              ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        Attachment - Section V (1968)                     <Page No.  61>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||           V - Tramp Internal Organization - 1968           ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The following describes the 1968 implementation of the internal
        organization of TRAMP.
        
        
        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.
        
        
        TRAMP uses eight principal blocks of memory. Though it is
        designed to run under a timesharing supervisor which continually
        swaps TRAMP in and out of memory, TRAMP itself makes no explicit
        use of secondary storage devices; that is such use by the system
        is transparent to the user.
        
        
        The blocks of virtual memory are: four name tables [A, O, V, and
        a Name Table for Defined Relations]; three Association Tables;
        and a General Storage List [GS] (commonly called "Available
        Space" in many list processors). [GS] provides all the working
        space for TRAMP and is by far the largest of the eight. In
        addition to storing all of the information indexed by the seven
        tables, GS resolves any overflow (via collisions) from the
        tables.
        
        
        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 H1 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 "EEV0" 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).
                 
        Attachment - Section V (1968)                     <Page No.  62>
        ----------------------------------------------------------------
        
        
        
        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 character, 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 alphabetic
        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 O 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 memory more than once, though many
        pointers may point to it, including up to four headers if a name
        appears on all 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 H2. 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 Associated 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 th  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.
        
                 
        Attachment - Section V (1968)                     <Page No.  63>
        ----------------------------------------------------------------
        
        
        
        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 to 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**19 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**19 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 memory that a
        pointer can address, the less percentage (though not
        proportionately less) of that memory 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.  It was arbitrarily
        decided that the half word pointers that TRAMP uses to address
        double words are, in a sense, optimal.
        
        
        Should more experience show that this was 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 (1968) it is not anticipated
        that explicit use will be made of any peripheral storage device,         
        Attachment - Section V (1968)                     <Page No.  64>
        ----------------------------------------------------------------
        
        
        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
        memory (IBM/360-67). This figure was arrived at arbitrarily and
        will remain in force pending feedback which indicates that it is
        inappropriate.
        
        
        TRAMP is initially loaded into memory 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
        (ER and EIA - See section VI), as much storage as is being
        released is at that time returned to GS. Thus unused units are
        never left lying about memory: a unit is returned, not
        discarded, eliiminating formal garbage collections by ensuring
        that garbage is never created.
        
                 
        Attachment - Section V (1968)                     <Page No.  65>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||          Figure V-1 - Defined Relation Name Table          ||
        ||                                                            ||
         ______________________________________________________________ 
                 
        Attachment - M6 & SAM76 languages                 <Page No.  66>
        ----------------------------------------------------------------
        
        
         ______________________________________________________________ 
        ||                                                            ||
        ||        Brief Description of M6 and SAM76 languages         ||
        ||                                                            ||
         ______________________________________________________________ 
        
        
        
        The following is a partial and incomplete description of the M6
        and SAM76 languages and is intended only to familiarize the
        reader with the structure of these languages and enable him to
        follow the TRAMP definitions and examples.
        
        
        The M6 language is described in [14] and the basic SAM76
        language is described in [15]. Much of the motivation for the
        development of these languages came from the work of Eastwood
        and Mc Ilroy [2,13] at Bell Laboratories. A system similar to
        these languages was developed independently in Great Britain and
        was described by Strachey [19].
        
         __________________                                             
        ||                ||  There   are   two   kinds   of  functions:
        ||    Mode of     ||  "primitive"  or  "built-in" functions that
        ||   operation    ||  support   the   system   environment.  The
        ||                ||
         __________________   primitives  are  the  basis for the second
                              type   of   function   called  "texts"  or
        "procedures"   in   the   system   storage.   
        
        
        These texts are character strings written like macro definitions
        and expanded, interpretively when invoked or fetched. When
        writing a function expression, one specifies whether its value
        (replacing the invocation) is to be processed again as part of
        the input string (active fetch), or whether processing is to
        continue starting with the portion of the string to the right of
        the value returned (neutral fetch).
        
        
        A single processing cycle is completed when the scanning and
        evaluating process reaches the right-hand end of the string.
        
        
        Sequencing and evaluation are inherently recursive: expressions
        are evaluated from left to right, but may be nested to any depth
        in the arguments of the other expressions. Each function is
        evaluated when, and only when, all of its arguments have been
        completely processed.
        
        
        Thus the string being processed is divided logically into two
        parts: the active string, consisting of input text (possibly
        preceded by inserted functional values) which is yet to be
        scanned, and evaluated arguments of function fetches which are
        not completely ready for evaluation.
        
        
        This mode of operation, based on the completely interpretive
        execution of function fetches, eliminates the distinction
        between program and data.
        
                 
        Attachment - M6 & SAM76 languages                 <Page No.  67>
        ----------------------------------------------------------------
        
        
                                                     __________________ 
        Each  function  fetch  has  the  form of a  ||                ||
        specially   delimited  argument  list,  in  ||     Syntax     ||
        which  the  name of the function is always  ||                ||
                                                     __________________ 
        the  first argument. Fetches may be "open"                      
        (a   variable   number   of   arguments)   or   "closed".   
        
        
        A function fetch may be protected from evaluation by the use of
        literal delimiters. Another delimiter signals the right-hand end
        of the input string.
        
        
        These considerations lead to a syntax in which there are a
        number of special symbols, also known as warning characters. The
        occurrences of these symbols are deleted from the string during
        syntax scanning and their presence indicate the beginning or end
        of a substring.
        
        
        The symbols used and their purpose are:
        
        
                %       Beginning of active expression
                &       Beginning of neutral expression
                #       Beginning of M6 expression
                ,       Argument separator
                /       End of SAM76 expression
                :       End of active M6 expression
                ;       End of neutral M6 expression
                !       Beginning of protected string
                /       End of protected string
                (       Beginning of protected string
                )       End of protected string
                <       Beginning of protected string
                >       End of protected string
                =       End of input string (Changeable)
        
        
        Whenever a protected or literal string is encountered, the
        language processor removes the beginning and end symbol pair,
        but only the outer set is removed if more than one matching pair
        occurs. Thus a string initially protected from evaluation may be
        evaluated if scanned a second time, and, in general, evaluation
        can be controlled to occur the n-th time the string is scanned.
        
        
        INPUT STRING and OUTPUT STRING
        
        The value of an "input string" function %is/ is an input string
        accepted from the current input device.
        
        
        The "output string" function %os,X/ causes the output of the
        second argument, here symbolized by X, on the current output
        device, and has a null value.
        
        
        When the system is first given control, and at the end of every
        processing cycle the "restart expression"
        
                &os,%is//         
        Attachment - M6 & SAM76 languages                 <Page No.  68>
        ----------------------------------------------------------------
        
        
        
        is automatically loaded as an input string. This procedure first
        causes an input from the input device, with the input string
        becoming the second argument of the "output string" expression.
        Thus the string, if any, remaining when the input string has
        been completely processed, is finally output before the restart
        expression is again loaded. For example, if the input string is:
        
        
                %os,ABC/=
        
        then after the "input string" has been evaluated, the processor
        is scanning the string
        
                &os,%os,ABC//
        
        and the inner fetch produces the output ABC. The outer
        expression does nothing since the inner "output string" has a
        null value.
        
        
        DEFINE, FETCH and PARTITION TEXTS
        
        Any character string can be given a name and placed in storage,
        from whence it can be fetched by using its name. The null valued
        "define text" function
        
                %dt,A,B/
        
        places the text B in storage with the name A. A is called a text
        with value B. Usually only one text can be defined with a given
        name at any one time: use of the same name replaces a former
        definition. The value is retrieved with the "fetch text"
        function
        
                %ft,A/
        
        
        A text name, like a value, is any character string. The only
        restriction on length is that ot the total string capacity of
        the processor.
        
        
        The occurrence of texts in storage is deleted with the "erase
        text" function
        
                %et,N1,N2,.../
        
        
        This null valued function removes the names N1, N2, ... as texts
        and discards their values.
        
        
        Once defined, a text can be "parametrized" or "partitioned",
        using the "partition text" function:
        
                %pt,A,X1,X2, ... /
        
                 
        Attachment - M6 & SAM76 languages                 <Page No.  69>
        ----------------------------------------------------------------
        
        
        
        This null valued function scans the text "A", searching for an
        occurrence of the string X1 as a substring. If a match is found,
        that part is excluded from further matching, creating a "formal
        variable" also known as a "partition". The rest of the text is
        also compared with X1 to create, if possible, more partitions,
        all of which are assigned the ordinal value [1], identifying the
        argument matched.
        
        
        The (separate) substrings of the text not already taken for
        partitions are next scanned with respect to the string X2, and
        any occurrences of the latter substring in "A" create partitions
        of ordinal value [2], etc.
        
        
        Thus the "define text" and "partition text" functions together
        create a "macro" in which the partitions locate the "formal
        parameters". The "macro" is expanded by supplying the "actual
        parameters" in the use of a "fetch text" function:
        
                %ft,A,Y1,Y2, ... /
        
        
        The value of the "fetch text" is generated by returning the text
        "A" with all the partitions of ordinal values 1,2, ... repalced
        by Y1, Y2, ... respectively. If extra arguments are given in a
        "ft", they are ignored. If some are missing, null strings are
        used as their values.
        
        
        THE IF IDENTICAL FUNCTION
        
        A decision function is provided for character strings:
        
                %ii,A,B,T,F,b1,t1,b2,t2,.../
        
        
        If the string A is identical to the string B, then the value of
        thhis function is the fourth argument, T, otherwise the value is
        the fifth argument F, unless it is identical to b1, then t1,
        etc.
        
        
        Since the strings T and F may be any procedure, this primitive
        is the one normally used for branching.
