BIG LEAP

                       Jon Shopiro
              Department of Computer Science
               The University of Rochester

     Several changes have been made to the LEAP subsystem of SAIL.
The user of the modified system will enjoy the following
enhancements:

     1. The maximum number of items has been increased from about
        4090 to about 100000.

     2. The two slowest searches, A xor X eqv Y and X xor O eqv Y
        have been improved very substantially.

     3. The set insertion PUT NEW(X) in SETY is improved.

     4. A compiler option exists for inserting runtime checks
        so that an error message is given at runtime
        if DATUM is used with an improper argument (either
        an unallocated item, or an item of the wrong datum
        type). This takes the form of a new REQUIRE statement:

               REQUIRE VERIFY!DATUMS;

        All datum constructs seen after the above will have
        two extra instructions generated which will check the
        TYPEIT code to verify that the argument to DATUM is
        of the appropriate datum-type.

     The casual user need not concern himself with the details of these
changes. Existing programs should continue to run with little or no
space penalty. New programs may REQUIRE up to 100000 items and the
searches above need no longer be eschewed. As always the user is 
warned against using knowledge about the internal
structures of LEAP in his programs.

     For hackers and the curious, a brief discussion of
the changes follows.

     First off, items are now 18 bits long so that the limitation
on the number of items is now the size of the address space of
the PDP-10. As before a minimum of two words are required per
item. Since an association no longer fits in a single word
a new internal form for triples was designed, retaining all the
linkages of the old system, but requiring two words for each 
association plus two words for every distinct attribute-object pair
in the associative store. The new data structure requires the same
amount as the old one , plus two words for each attribute-object 
pair that appears in exactly one triple. Bracketed triples are no
longer in the main data structure but are in a separate list all
their own. A planned future improvement is to store bracketed 
triples in their own hash table.

     Second, the hashing scheme for the associative store was changed.
For a thorough discussion see Rashid [1]. The effect
of this change is that for a A xor X eqv Y or an
X xor O eqv Y search only 32 locations in the hash table
have to be examined. This is a very substantial improvement over the
old method for most cases.

     Finally, new items are now allocated in descending order.
Since sets are stored as ordered lists, a new item inserted in a set will
now go at the head of the list, instead of the end. However, programs
that (foolishly) used knowledge of the order of allocation of items
will no longer work.