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
I. INTRODUCTION
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.
1
LEAP TUTORIAL June 12, 1973
II. ITEMS
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
variable.
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
expression.
2
LEAP TUTORIAL June 12, 1973
III. DATUMS
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.
Example:
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];
INTEGER ARRAY ITEMVAR ARRAY Z[1:5];
INTEGER ARRAY ITEMVAR Q;
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
3
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:
STRING ITEMVAR PROCEDURE SNEW(STRING X);
RETURN(NEW(X));
Thus we may talk of DATUM(SNEW("anystring"))
3. Assignment expressions whose left hand side is a typed
itemvar.
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.
INTEGER PROCEDURE TYPEIT(ITEMVAR X);
4
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.
5
LEAP TUTORIAL June 12, 1973
IV. SETS
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.
SET EXPRESSIONS:
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.
E.G.
{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}
6
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}
PUT and REMOVE
1. To place a single item into a set variable we may use the PUT
statement:
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.
7
LEAP TUTORIAL June 12, 1973
2. Set equality
setexpr1 = setexpr2
TRUE only if each item in setexpr1 is in setexpr2 and vice
versa.
3. Set inequality
setexpr1 ≠ setexpr2
TRUE if setexpr1 or setexpr2 contains an item not found in
the other.
Equivalent to
¬(setexpr1=setexpr2)
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)
8
LEAP TUTORIAL June 12, 1973
COP, LOP and LENGTH
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:
ITEMVAR PROCEDURE LOP(REFERENCE SET Y);
BEGIN ITEMVAR Q;
Q ← COP(Y);
REMOVE Q FROM Y;
RETURN(Q)
END;
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;
END;
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:
LOP(SETVAR);
9
LEAP TUTORIAL June 12, 1973
3. LENGTH(setexpr) - returns the number of items within a set.
Logically equivalent to following procedure:
INTEGER PROCEDURE LENGTH(SET Y);
BEGIN "LENGTH"
INTEGER COUNT; ITEMVAR DUMMY;
COUNT ← 0;
WHILE (Y ≠ PHI) DO
BEGIN
DUMMY ← LOP(Y);"remove an element from the set"
COUNT ← COUNT +1; "step count of elements"
END;
RETURN(COUNT);
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.
10
LEAP TUTORIAL June 12, 1973
V. LISTS
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}}
11
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}}"
12