perm filename TUTOR.DOC[DOC,AIL]1 blob sn#048387 filedate 1973-06-28 generic text, type T, neo UTF8

                                LEAP TUTORIAL

                                 By Jim Low
                            LEAP TUTORIAL               June 12, 1973


SAIL contains an associative data system called LEAP. It is patterned
after the LEAP system implemented at LINCOLN LABORATORY by ROVNER and
FELDMAN. Features contained in our  LEAP but not in the  Lincoln LEAP
include a  data-type  called  list, and  "matching" procedures  to be
described below.

This document is intended to serve as a companion volume to  the SAIL
manual and hopefully will be easier to understand than the  manual as
here we can afford expound more on the various constructs and we also
have the space to include more examples.

Other documents  which may be  of interest to  the LEAP  user include
LEAP.WRU[LEP,JRL],  which  is a  general  guide to  the  leap runtime
environment; LEAP.TXT[LEP,JRL], which is a detailed guide to the LEAP
parts of the SAIL compiler and the SAIL runtime system; and of course
the SAIL manual.

                            LEAP TUTORIAL               June 12, 1973


The basic entities which LEAP manipulates are called "items". An item
is similar  in many  respects to a  LISP atom.   It optionally  has a
printname and a datum.  A datum is a scalar  or an array of  any SAIL
data-type other than types "item" and "itemvar". An itemvar is simply
a variable whose values are items.

As an example of an item we may consider the following declaration.

                          REAL ITEM RITEM;

This  declares an  item  named RITEM  whose  datum is  a  scalar real

In  addition  to  declarations  of  items  at  compile-time,  we  may
dynamically  create  new items  by  calling the  function  NEW.  This
function may  either have  no arguments, (in  which case  the created
item has no datum); or it may have a single argument which  is either
an  expression or  an array.  This argument  is copied  and  the copy
becomes the  value of the  datum of  the new item.  We may  of course
later change the value  of the datum or  an element of the  datum (if
the datum  is an  array) by using  standard algolic  assignments. The
data-type  of the  datum of  the  new item  is the  data-type  of the
argument to NEW.  Thus NEW(1) would create  a new integer  item whose
datum was initially given the value 1.

Items  may  be  assigned  to  itemvars  by  standard  SAIL assignment
statements and assignment expressions.

                           itmvr← itmexpr;

Items  themselves are  considered to  be constants  and thus  may not
appear  on  the  left  hand  side  of  an  assignment   statement  or

                            LEAP TUTORIAL               June 12, 1973


Associated  with  most  items  are datums  which  may  be  treated as
standard SAIL variables. To refer to the datum of an item we  use the
operator DATUM.

                               INTEGER ITEM II;
                               INTEGER I;
                           L1: DATUM(II)←5;
                           L2: I ← DATUM(II)+1;

At L1 the  datum of the item  II is given the  value "5". At  L2, the
value  of  the  datum  of II  is  used  in  an  arithmetic assignment
statement which would cause the variable I to receive the value 6.

Datum  takes as  its  argument a  typed item  expression:  Typed item
expressions include:

      1. Typed items and itemvars (declared with their  type followed
         by ITEM as in:

             INTEGER ITEM JJ;
             INTEGER ARRAY ITEM X[1:5];
             INTEGER ITEMVAR ARRAY Y[1:5];

         Note the distinctions  between the later  four declarations.
         X is declared to be a single item whose datum is  an integer
         array containing five elements. Y is declared to be an array
         of five  itemvars, each  of which is  claimed to  contain an
         item whose datum is a scalar integer. Z is declared to be an
         array of five itemvars whose values are claimed to  be items
         with datums which are integer arrays. Q is an  itemvar which
         supposedly contains an item whose datum in an integer array.
         As is shown above, we  do not specify the dimensions  of the
         the array which is the  datum of an array itemvar.  Thus for
         example, each element of Z could contain items  whose datums
         were arrays of different dimensions. However for array items
         we must declare the dimension because otherwise the compiler
         would not know how much space to allocate for the array.  We
         place the dimensions of  the array following the  item name.
         This  is somewhat  confusing as  it appear  that we  have an

                            LEAP TUTORIAL               June 12, 1973

         array of items rather than  a single item whose datum  is an
         array.  SAIL has solved this problem in a very arbitrary way
         by outlawing  declarations of arrays  of items. One  can get
         the effect  of arrays of  items by declaring  itemvar arrays
         and then assigning "NEW" items to the individual elements.

      2. Typed itemvar function calls:



         Thus we may talk of DATUM(SNEW("anystring"))

      3.  Assignment  expressions whose  left  hand side  is  a typed

The type of  the datum variable is  the type of its  item expression.
Thus,  the datum  of  an integer  item  expression is  treated  as an
integer  variable,  the datum  of  a real  array  item  expression is
treated as a real array and so forth.

NOTE: no check is actually made that the item is of the claimed type.
Thus, for example disastrous things may happen if one uses DATUM on a
string itemvar in  which an integer  item has been  stored. Therefore
the user should be  careful about storing typed items  into different
type itemvars. When in doubt about the actual type an item expression
he should use the function TYPEIT  to verify that the item is  of the
required type. TYPEIT is a predeclared integer function.


                            LEAP TUTORIAL               June 12, 1973

The values returned by TYPEIT are:

 0 - deleted or never allocated     1 - item has no datum.
 2 - bracketed triple(no datum)     3 - string item
 4 - real item                      5 - integer item
 6 - set item                       7 - list item
 8 - procedure item                 9 - process item
10 - event-type item               11 - context item
12 - refitm item                   16 - string array item
17 - real array item               18 - integer array item
19 - set array item                20 - list array item
24 - context array item            25 - invalid type(error inside LEA

Those codes not mentioned  (13-15,21-23) are also invalid  and should
be considered erroneous.

                            LEAP TUTORIAL               June 12, 1973


A set is an unordered  collection of unique items. All  set variables
are initialized to  PHI, the empty set  consisting of no  items.  Set
variables receive values by assignment or by placing individual items
in them by PUT statements.


     1. Explicit Set -  A sequence of item expressions which  make up
        the set surrounded by set brackets.
        E. G.
        a)  {item1,item2,item3}
        b)  {item2,item1,item3}
        c)  {item2,item2,item2,item3}

        Note: Since sets are unordered and a given item may appear at
        most once within a  set, set expressions a,b,and c  above all
        represent the same set.

     2. PHI -  the empty set.  The  set consisting of no  elements at
        all is the empty set which may be written as either
        {} or PHI

     3. Set Union - written SET1 ∪ SET2.
        The resultant  set contains all  items which are  elements of
        either SET1 or SET2 or both.
        {item1,item2} ∪ {item2,item3} = {item1,item2,item3}

     4. Set Intersection - written SET1 ∩ SET2
        The resultant  set contains all  items which are  elements of
        both SET1 and SET2.
        E. G.
        {item1,item2,item3} ∩ {item1,item2,item4} = {item1,item2}

                            LEAP TUTORIAL               June 12, 1973

     5. Set Subtraction - written SET1 - SET2
        The resultant  set contains all  items which are  elements of
        SET1 but not elements of SET2.
        E. G.
        {item1,item2,item3} - {item2,item4,item5} = {item1,item3}


     1. To place a single item into a set variable we may use the PUT

                       PUT itemexpr IN setvar;

        This has the identical effect as:

                    setvar ← setvar ∪ {itemexpr};

        However, as the assignment  causes the set to be  copied, and
        the PUT  doesn't the  PUT statement will  take less  time and
        space to execute.

     2. To remove a  single item from a  set variable we may  use the
        REMOVE statement

                    REMOVE itemexpr FROM setvar;

        This has the same effect as:

                    setvar ← setvar - {itemexpr};

        Again, as the REMOVE statement avoids copying the set,  it is
        more efficient than the equivalent assignment statement.

SET Booleans

     1. Set membership

                         itemexpr ε setexpr

        TRUE only if the item is an element of the set.

                            LEAP TUTORIAL               June 12, 1973

     2. Set equality

                         setexpr1 = setexpr2

        TRUE only if  each item in setexpr1  is in setexpr2  and vice

     3. Set inequality

                         setexpr1 ≠ setexpr2

        TRUE if setexpr1  or setexpr2 contains  an item not  found in
        the other.
        Equivalent to


     4. Proper containment

           setexpr1 < setexpr2    or   setexpr2 < setexpr1

        TRUE  if every  item  in setexpr1  is also  in  setexpr2, but
        setexpr1 ≠ setexpr2  Equivalent to: ((setexpr1 ∩  setexpr2) =
        setexpr1) ∧ (setexpr1 ≠ setexpr2)

     5. Containment

            setexpr1 ≤ setexpr2    or setexpr2 ≥ setexpr1

        TRUE if every item in setexpr1 in also in setexpr2.
        Equivalent to

            (setexpr1 = setexpr2) ∨ (setexpr1 < setexpr2)

                            LEAP TUTORIAL               June 12, 1973


     1. COP (setexpr)  - returns an item  which is an element  of the
        set. As sets are unordered  you do not know which  element of
        the set will be returned It is useful most often when we know
        the set has but a single element in which case it will return
        that item.

     2. LOP  (setvar) -  same as COP  except argument  must be  a set
        variable and the item returned is also removed from that set.
        It is logically equivalent to the  following procedure:
             BEGIN ITEMVAR Q;
                     Q ← COP(Y);
                     REMOVE Q FROM Y;
        LOP  is  often  valuable  if we  wish  some  operation  to be
        performed on each item  of a set. Consider the  example below
        where we wish the datums of all integer items contained  in a
        set  SETI to  be  incremented by  one.  Assume  that  we have
        declared IITMVR to be an integer itemvar and TSET to be a set
        variable which we will use as temporaries.
             TSET ← SETI; "Copy set of interest into temporary"
             WHILE (TSET ≠ PHI) DO "loop while TSET has elements"
             BEGIN IITMVR ← LOP(TSET); "remove an element from TSET"
                IF TYPEIT(IITMVR) = 5 THEN "check if really integer"
                      DATUM(IITMVR) ← DATUM(IITMVR) + 1;
        NOTE: LOP is compiled into code other than  a straightforward
        procedure call  and thus like  many other  functionals cannot
        appear as a statement but only as part of an expression. Thus
        if  we just  wanted to  remove an  arbitrary set  element and
        throw if away we would have to say:

                         DMY ← LOP(SETVAR);

        where DMY is an itemvar whose contents we do not  care about,
        rather than the simpler:


                            LEAP TUTORIAL               June 12, 1973

     3. LENGTH(setexpr) - returns  the number of items within  a set.
        Logically equivalent to following procedure:
             BEGIN "LENGTH"
                COUNT ← 0;
                WHILE (Y ≠ PHI) DO
                      DUMMY ← LOP(Y);"remove an element from the set"
                      COUNT ← COUNT +1; "step count of elements"
             END "LENGTH";
        The actual  implementation of LENGTH  is much  more efficient
        than  the above  procedure (usually  taking only  two machine
        instructions).  The most  efficient way  of determining  if a
        given set is  empty is to  see if the  LENGTH of that  set is
        zero. This is actually much faster that comparing the set and
        PHI for equality.

                            LEAP TUTORIAL               June 12, 1973


A list is  an ordered sequence  of items (not  necessarily distinct).
List variables are  initialized to NIL  the empty list  containing no
items.  List variables  receive values  by assignment  or  by placing
individual items in them by PUT statements.

LIST Expressions

     1. Explicit List -  written as the sequence of  items (separated
        by commas) all surrounded  by list brackets "{{ }}".   SKIP 1
        a. {{ item1, item2, item3}}
        b. {{ item2, item1, item3 }}
        c. {{ item2, item2, item1, item 3 }}

        Note  that since  the  order and  number of  times  each item
        appears is  important for each  lists, the expressions  a, b,
        and c above all represent different list expressions.

        NOTE: we may represent NIL, the empty list, by {{ }}

     2. Concatenation - written  list1 & list2 This forms a  new list
        containing all the items  in list1 followed by all  the items
        in list2.
        E. G.

         {{item1, item2, item3,}} & {{item3, item4, item5 }}
            {{item1, item2, item3, item3, item4, item5}}

             {{item1, item2}} & {{item 4, item4, item5}}
                {{item1, item2, item4, item4, item5}}

     3. Sublists - There are two forms of sublist expressions

        a. listexpr [i1  TO i2] -  the first integer  expression (i1)
           stands for the position  of the first element to  be taken
           and the second  (i2) stands for  the position of  the last
           element to be taken.
           E. G.

           {{itema,itemb,itemc,itemd}}[2 TO 3]={{itemb,itemc}}

                            LEAP TUTORIAL               June 12, 1973

           {{itema,itemb,itemc,itemd}}[3 TO 3]={{itemc}}

        b. listexpr [i1 FOR  i2] - the first integer  expression (i1)
           stands for the position  of the first element to  be taken
           and the second (i2)  stands for the number of  elements to
           be taken.  E. G.

           {{itema,itemb,itemc,itemd}}[2 FOR 3]={{itemb,itemc,itemd}}

           {{itema,itemb,itemc,itemd}}[3 FOR 1]={{itemc}}

           {{itema,itemb,itemc,itemd}}[3 FOR 0]={{ }}= NIL

LIST Selectors

It is often  useful to think  of a list  as an untyped  itemvar array
with a single dimension with lower bound 1 and upper bound variable.

     1. Expression selector

        listexpr [i1] - returns the  item which is the i1  element of
        the list. If i1 is less than 0 or greater than the  number of
        elements of the list an error is signaled.
        E. G.

                 {{itema, itemb, itemc}} [1] = itema

                 {{itemb, itemc, itemd}} [2] = itemc

        Note the difference between  listexpr[i1] and listexpr[i1 FOR
        1].  The former returns an item and the later returns  a list
        containing a single item.

     2. Replacement selector

                       listvar[i1] ← itemexpr;

        This removes the i1 element of the list and replaces  it with
        the itemexpr i1 must be between 1 and the number  of elements
        in the list + 1.
        E. G.
        LIST1 ← {{ITEM1}};
        LIST1[1] ← ITEM2; "NOW LIST1 = {{ITEM2}}"
        LIST1[2] ← ITEM3; "NOW LIST1 = {{ITEM2,ITEM3}}"
        LIST1[1] ← LIST1[2]; "NOW LIST1 = {{ITEM3,ITEM3}}"