perm filename TUTOR.PUB[DOC,AIL] blob
sn#071738 filedate 1973-11-10 generic text, type T, neo UTF8
00100
00200 .BEGIN VERBATIM
00300 .GROUP SKIP 20
00400 LEAP TUTORIAL
00500
00600
00700 By Jim Low
00800 .END
00900 .EVERY HEADING(,LEAP TUTORIAL,{DATE})
01000 .EVERY FOOTING(,{PAGE},)
01100 .PREFACE 0
01200
01300 .MACRO BEGSEC(CNT) ⊂ BEGIN
01400 .SKIP 1
01500 .VARIABLE TCNT
01600 .TCNT←CNT
01700 .NARROW CNT ⊃
01800
01900 .MACRO ENDSEC ⊂
02000 .WIDEN TCNT
02100 .INDENT1←INDENT2←0
02200 .END⊃
02300
02400 .MACRO SAMESEC ⊂
02500 .SKIP 1
02600 .IF LINES < 10 THEN NEXT PAGE
02700 .INDENT1←0⊃
02800
02900 .MACRO EXAMPLE ⊂SKIP 1
03000 .ONCE CENTER⊃
03100
03200 .NEXT PAGE
03300 I. INTRODUCTION
03400 .SKIP 3
03500 SAIL contains an associative data system called LEAP. It is
03600 patterned after the LEAP system implemented at LINCOLN LABORATORY
03700 by ROVNER and FELDMAN. Features contained in our LEAP but not in
03800 the Lincoln LEAP include a data-type called list, and "matching"
03900 procedures to be described below.
04000 .SKIP 1
04100 This document is intended to serve as a companion volume to the
04200 SAIL manual and hopefully will be easier to understand than the
04300 manual as here we can afford expound more on the various
04400 constructs and we also have the space to include more examples.
04500 .SKIP 1
04600 Other documents which may be of interest to the LEAP user include
04700 LEAP.WRU[DOC,AIL], which is a general guide to the leap runtime
04800 environment; LEAP.TXT[DOC,AIL], which is a detailed guide to the
04900 LEAP parts of the SAIL compiler and the SAIL runtime system; and
05000 of course the SAIL manual.
05100 .NEXT PAGE
00100 II. ITEMS
00200 .SKIP 3
00300 The basic entities which LEAP manipulates are called
00400 "items". An item is similar in many respects to a LISP atom.
00500 It optionally has a printname and a datum. A datum is a scalar
00600 or an array of any SAIL data-type other than types "item" and
00700 "itemvar". An itemvar is simply a variable whose values are
00800 items.
00900 .SKIP 1
01000 As an example of an item we may consider the following
01100 declaration.
01200
01300 .EXAMPLE
01400 REAL ITEM RITEM;
01500 .SKIP 1
01600 This declares an item named RITEM whose datum is a
01700 scalar real variable.
01800 .SKIP 1
01900 In addition to declarations of items at compile-time, we
02000 may dynamically create new items by calling the function NEW.
02100 This function may either have no arguments, (in which case the created
02200 item has no datum); or it may have a single argument which is either
02300 an expression or an array. This argument is copied and the copy
02400 becomes the value of the datum of the new item. We may of course later
02500 change the value of the datum or an element of the datum (if the
02600 datum is an array) by using standard algolic assignments. The data-type
02700 of the datum of the new item is the data-type of the argument to NEW. Thus
02800 NEW(1) would create a new integer item whose datum was initially
02900 given the value 1.
03000 .SKIP 1
03100 Items may be assigned to itemvars by standard SAIL assignment
03200 statements and assignment expressions.
03300 .EXAMPLE
03400 itmvr← itmexpr;
03500 .SKIP 1
03600 Items themselves are considered to be constants and thus may not appear
03700 on the left hand side of an assignment statement or expression.
03800
03900 .NEXT PAGE
00100 III. DATUMS
00200 .SKIP 3
00300 Associated with most items are datums which may be treated
00400 as standard SAIL variables. To refer to the datum of an item we use
00500 the operator DATUM.
00600 .SKIP 1
00700 .GROUP
00800 .BEGIN
00900 .NARROW 15
01000 .VERBATIM
01100 Example:
01200
01300 INTEGER ITEM II;
01400 INTEGER I;
01500 L1: DATUM(II)←5;
01600 L2: I ← DATUM(II)+1;
01700 .FILL ADJUST
01800 .WIDEN 15
01900 .END
02000 .APART
02100 .SKIP 1
02200 At L1 the datum of the item II is given the value "5". At L2, the
02300 value of the datum of II is used in an arithmetic assignment statement
02400 which would cause the variable I to receive the value 6.
02500 .SKIP 1
02600 Datum takes as its argument a typed item expression: Typed
02700 item expressions include:
02800 .BEGSEC(6)
02900 .INDENT2← 3
03000 1. Typed items and itemvars (declared with their type followed by
03100 ITEM or ITEMVAR) as in:
03200 .INDENT1←3
03300 .BEGSEC(4)
03400 .CRBREAK
03500 INTEGER ITEM JJ;
03600 INTEGER ARRAY ITEM X[1:5];
03700 INTEGER ITEMVAR ARRAY Y[1:5];
03800 INTEGER ARRAY ITEMVAR ARRAY Z[1:5];
03900 INTEGER ARRAY ITEMVAR Q;
04000 .CRSPACE
04100 .ENDSEC
04200 .SKIP 1
04300 Note the distinctions between the later four declarations.
04400 X is declared to be a single item whose datum is an integer
04500 array containing five elements. Y is declared to be an array
04600 of five itemvars, each of which is claimed to contain
04700 an item whose datum is a scalar integer. Z is declared to be
04800 an array of five itemvars whose values are claimed to be
04900 items with datums which are integer arrays. Q is an itemvar which
05000 supposedly contains an item whose datum in an integer array.
05100 As is shown above, we do not specify the dimensions of the
05200 the array which is the datum of an array itemvar. Thus for
05300 example, each element of Z could contain items whose datums
05400 were arrays of different dimensions. With declared array items
05500 we must declare the dimension , otherwise the
05600 compiler would not know how much space to allocate for the array.
05700 We place the dimensions of the array following the item name.
05800 This is somewhat confusing as it appear that we have an
05900 array of items rather than a single item whose datum is an array.
06000 SAIL has solved this problem in a very arbitrary way by outlawing
06100 declarations of arrays of items. One can get the effect of arrays
06200 of items by declaring itemvar arrays and then assigning "NEW"
06300 items to the individual elements.
06400
06500 .SAMESEC
06600 2. Typed itemvar function calls:
06700 .INDENT1←3
06800 .EXAMPLE
06900 STRING ITEMVAR PROCEDURE SNEW(STRING X);
07000 .EXAMPLE
07100 RETURN(NEW(X));
07200 .SKIP 1
07300 Thus we may talk of DATUM(SNEW("anystring"))
07400 .SAMESEC
07500 3. Assignment expressions whose left hand side is a typed itemvar.
07600 .INDENT2←0
07700 .ENDSEC
07800 .SKIP 3
07900 The type of the datum variable is the type of its item expression.
08000 Thus, the datum of an integer item expression is treated as an integer variable,
08100 the datum of a real array item expression is treated as a real array and so forth.
08200 .SKIP 1
08300 NOTE: no check is actually made that the item is of the claimed type. Thus
08400 , for example, disastrous things may happen if one uses DATUM on a string itemvar
08500 in which an integer item has been stored. The user should be careful
08600 about storing typed items into different type itemvars. When in doubt about
08700 the actual type an item expression he should use the function TYPEIT to
08800 verify that the item is of the required type. TYPEIT is a predeclared integer
08900 function.
09000 .EXAMPLE
09100 INTEGER PROCEDURE TYPEIT(ITEMVAR X);
09200 .SKIP 1
09300 .GROUP
09400 The values returned by TYPEIT are:
09500 .SKIP 1
09600 .BEGIN VERBATIM
09700 0 - deleted or never allocated 1 - item has no datum.
09800 2 - bracketed triple(no datum) 3 - string item
09900 4 - real item 5 - integer item
10000 6 - set item 7 - list item
10100 8 - procedure item 9 - process item
10200 10 - event-type item 11 - context item
10300 12 - refitm item 16 - string array item
10400 17 - real array item 18 - integer array item
10500 19 - set array item 20 - list array item
10600 24 - context array item 25 - invalid type(error in LEAP)
10700
10800 .END
10900 Those codes not mentioned (13-15,21-23) are also invalid and should be
11000 considered erroneous.
11100 .APART
11200 .NEXT PAGE
11300
00100 IV. SETS
00200 .SKIP 3
00300 A set is an unordered collection of unique items. All set
00400 variables are initialized to PHI, the empty set consisting of no items.
00500 Set variables receive values by assignment or by placing individual
00600 items in them by PUT statements.
00700 .SKIP 2
00800 SET EXPRESSIONS:
00900 .BEGSEC(5)
01000 .INDENT2←3
01100 1. Explicit Set - A sequence of item expressions which make up
01200 .INDENT1←3
01300 the set surrounded by set brackets.
01400
01500 E. G.
01600
01700 a) {item1,item2,item3}
01800
01900 b) {item2,item1,item3}
02000
02100 c) {item2,item2,item2,item3}
02200 .SKIP 1
02300 Note: Since sets are unordered and a given item may appear at most
02400 once within a set, set expressions a,b,and c above all represent the
02500 same set.
02600 .SAMESEC
02700 2. PHI - the empty set.
02800 .INDENT1←3
02900 The set consisting of no elements at all is the empty set which may
03000 be written as either
03100
03200 {} or PHI
03300 .SAMESEC
03400 3. Set Union - written SET1 ∪ SET2.
03500 .INDENT1←3
03600
03700 The resultant set contains all items which are elements of either SET1
03800 or SET2 or both.
03900
04000 E.G.
04100
04200 {item1,item2} ∪ {item2,item3} = {item1,item2,item3}
04300
04400 .SAMESEC
04500 4. Set Intersection - written SET1 ∩ SET2
04600 .INDENT1←3
04700
04800 The resultant set contains all items which are elements of both SET1 and SET2.
04900
05000 E. G.
05100
05200 {item1,item2,item3} ∩ {item1,item2,item4} = {item1,item2}
05300 .SAMESEC
05400 5. Set Subtraction - written SET1 - SET2
05500 .INDENT1←3
05600
05700 The resultant set contains all items which are elements of SET1 but not
05800 elements of SET2.
05900
06000 E. G.
06100
06200 {item1,item2,item3} - {item2,item4,item5} = {item1,item3}
06300 .ENDSEC
06400 .SKIP 2
06500 .IF LINES < 10 THEN NEXT PAGE
00100 PUT and REMOVE
00200 .SKIP 2
00300 .BEGSEC(5)
00400 .INDENT2←3
00500 1. To place a single item into a set variable we may use the PUT statement:
00600 .INDENT1←3
00700 .EXAMPLE
00800 PUT itemexpr IN setvar;
00900 .SKIP 1
01000 This has the identical effect as:
01100 .EXAMPLE
01200 setvar ← setvar ∪ {itemexpr};
01300 .SKIP 1
01400 However, as the assignment causes the set to be copied, and the PUT doesn,'t
01500 the PUT statement will take less time and space to execute.
01600 .SAMESEC
01700 2. To remove a single item from a set variable we may use the REMOVE statement
01800 .INDENT1←3
01900 .EXAMPLE
02000 REMOVE itemexpr FROM setvar;
02100 .SKIP 1
02200 This has the same effect as:
02300 .EXAMPLE
02400 setvar ← setvar - {itemexpr};
02500 .SKIP 1
02600 Again, as the REMOVE statement avoids copying the set, it is more efficient
02700 than the equivalent assignment statement.
02800 .ENDSEC
02900 .SKIP 3
03000 .NEXT PAGE
03100 SET BOOLEANS
03200 .SKIP 2
03300 .BEGSEC(5)
03400 .INDENT2←3
03500 1. Set membership
03600 .INDENT1←3
03700 .EXAMPLE
03800 itemexpr ε setexpr
03900 .SKIP 1
04000 TRUE only if the item is an element of the set.
04100 .SAMESEC
04200 2. Set equality
04300 .INDENT1←3
04400 .EXAMPLE
04500 setexpr1 = setexpr2
04600 .SKIP 1
04700 TRUE only if each item in setexpr1 is in setexpr2 and vice versa.
04800 .SAMESEC
04900 3. Set inequality
05000 .INDENT1←3
05100 .EXAMPLE
05200 setexpr1 ≠ setexpr2
05300 .SKIP 1
05400 TRUE if setexpr1 or setexpr2 contains an item not found in the other.
05500
05600 Equivalent to
05700 .EXAMPLE
05800 ¬(setexpr1=setexpr2)
05900 .SAMESEC
06000 4. Proper containment
06100 .INDENT1←3
06200 .EXAMPLE
06300 setexpr1 < setexpr2 or setexpr2 > setexpr1
06400 .SKIP 1
06500 TRUE if every item in setexpr1 is also in setexpr2, but setexpr1 ≠ setexpr2
06600 Equivalent to:
06700 ((setexpr1 ∩ setexpr2) = setexpr1) ∧ (setexpr1 ≠ setexpr2)
06800 .SAMESEC
06900 5. Containment
07000 .INDENT1←3
07100 .EXAMPLE
07200 setexpr1 ≤ setexpr2 or setexpr2 ≥ setexpr1
07300 .SKIP 1
07400 TRUE if every item in setexpr1 in also in setexpr2.
07500 .BREAK
07600 Equivalent to
07700 .EXAMPLE
07800 (setexpr1 = setexpr2) ∨ (setexpr1 < setexpr2)
07900 .ENDSEC
08000 .NEXT PAGE
00100 COP, LOP and LENGTH
00200 .SKIP 2
00300 .BEGSEC(5)
00400 .INDENT2←3
00500
00600 1. COP (setexpr) - returns an item which is an element of the set. As sets
00700 .INDENT1←3
00800 are unordered you do not know which element of the set will be returned
00900 It is useful most often when we know the set has but a single element
01000 in which case it will return that item.
01100 .SAMESEC
01200
01300 2. LOP (setvar) - same as COP except argument must be a set variable and
01400 .INDENT1←3
01500 the item returned is also removed from that set.
01600 It is logically equivalent to the following procedure:
01700 .BEGIN VERBATIM
01800
01900 ITEMVAR PROCEDURE LOP(REFERENCE SET Y);
02000 BEGIN ITEMVAR Q;
02100 Q ← COP(Y);
02200 REMOVE Q FROM Y;
02300 RETURN(Q)
02400 END;
02500
02600 .END
02700 LOP is often valuable if we wish some operation to be performed on each
02800 item of a set. Consider the example below where we wish the datums
02900 of all integer items contained in a set SETI to be incremented by one.
03000 Assume that we have declared IITMVR to be an integer itemvar and TSET
03100 to be a set variable which we will use as temporaries.
03200 .BEGIN VERBATIM
03300
03400 TSET ← SETI; "Copy set of interest into temporary"
03500 WHILE (TSET ≠ PHI) DO "loop while TSET has elements"
03600 BEGIN IITMVR ← LOP(TSET); "remove an element from TSET"
03700 IF TYPEIT(IITMVR) = 5 THEN "check if really integer"
03800 DATUM(IITMVR) ← DATUM(IITMVR) + 1;
03900 END;
04000
04100 .END
04200 NOTE: LOP is compiled into code other than a straightforward procedure
04300 call and thus like many other functionals cannot appear as a statement
04400 but only as part of an expression. Thus if we just wanted to remove
04500 an arbitrary set element and throw if away we would have to say:
04600 .EXAMPLE
04700 DMY ← LOP(SETVAR);
04800 .SKIP 1
04900 where DMY is an itemvar whose contents we do not care about, rather than the simpler:
05000 .EXAMPLE
05100 LOP(SETVAR);
05200 .SAMESEC
05300 3. LENGTH(setexpr) - returns the number of items within a set.
05400 .INDENT1←3
05500 Logically equivalent to following procedure:
05600 .BEGIN VERBATIM
05700
05800 INTEGER PROCEDURE LENGTH(SET Y);
05900 BEGIN "LENGTH"
06000 INTEGER COUNT; ITEMVAR DUMMY;
06100 COUNT ← 0;
06200 WHILE (Y ≠ PHI) DO
06300 BEGIN
06400 DUMMY ← LOP(Y);"remove an element from the set"
06500 COUNT ← COUNT +1; "step count of elements"
06600 END;
06700 RETURN(COUNT);
06800 END "LENGTH";
06900
07000 .END
07100
07200 The actual implementation of LENGTH is much more efficient than the above
07300 procedure (usually taking only two machine instructions). The most efficient
07400 way of determining if a
07500 given set is empty is to see if the LENGTH of that set is zero. This
07600 is much faster that comparing the set and PHI for equality.
07700 .ENDSEC
07800 .NEXT PAGE
07900
00100 V. LISTS
00200 .SKIP 2
00300 A list is an ordered sequence of items (not necessarily distinct).
00400 List variables are initialized to NIL the empty list containing
00500 no items. List variables receive values by assignment or by
00600 placing individual items in them by PUT statements.
00700 .SKIP 2
00800 LIST Expressions
00900 .SKIP 1
01000 .BEGSEC(5)
01100 .INDENT2←3
01200 1. Explicit List - written as the sequence of items (separated by commas)
01300 .INDENT1←3
01400 all surrounded by list brackets "{{ }}".
01500 .SKIP 1
01600 a. {{ item1, item2, item3}}
01700
01800 b. {{ item2, item1, item3}}
01900
02000 c. {{ item2, item2, item1, item 3}}
02100 .SKIP 1
02200 Note that since the order and number of times each item appears is
02300 important with lists, the expressions a, b, and c above all
02400 represent different list expressions.
02500 .SKIP 1
02600 NOTE: we may represent NIL, the empty list, by {{ }}
02700
02800 .SAMESEC
02900 2. Concatenation - written list1 & list2.
03000 .INDENT1←3
03100 This forms a new list containing all the items in list1 followed by
03200 all the items in list2.
03300
03400 E. G.
03500
03600 .BEGIN CENTER
03700 .SKIP 1
03800 {{item1, item2, item3,}} & {{item3, item4, item5 }}
03900 =
04000 {{item1, item2, item3, item3, item4, item5}}
04100 .SKIP 2
04200 {{item1, item2}} & {{item 4, item4, item5}}
04300 =
04400 {{item1, item2, item4, item4, item5}}
04500 .END
04600 .SAMESEC
04700 3. Sublists - There are two forms of sublist expressions
04800 .INDENT1← 3
04900 .INDENT2←6
05000 .SKIP 1
05100 a. listexpr [i1 TO i2] - the first integer expression (i1) stands for
05200 the position of the first element to be taken and the second (i2)
05300 stands for the position of the last element to be taken.
05400 .INDENT1←6
05500
05600 E. G.
05700 .SKIP 1
05800 .ONCE COMPACT
05900 {{itema,itemb,itemc,itemd}}[2 TO 3]={{itemb,itemc}}
06000 .SKIP 1
06100 .ONCE COMPACT
06200 {{itema,itemb,itemc,itemd}}[3 TO 3]={{itemc}}
06300 .SKIP 1
06400 .INDENT1←3
06500 b. listexpr [i1 FOR i2] - the first integer expression (i1) stands for
06600 the position of the first element to be taken and the second (i2)
06700 stands for the number of elements to be taken.
06800 .INDENT1←6
06900 E. G.
07000 .SKIP 1
07100 .ONCE COMPACT
07200 {{itema,itemb,itemc,itemd}}[2 FOR 3]={{itemb,itemc,itemd}}
07300 .SKIP 1
07400 .ONCE COMPACT
07500 {{itema,itemb,itemc,itemd}}[3 FOR 1]={{itemc}}
07600 .SKIP 1
07700 .ONCE COMPACT
07800 {{itema,itemb,itemc,itemd}}[3 FOR 0]={{ }}= NIL
07900 .ENDSEC
08000 .SKIP 2
08100 LIST Selectors
08200 .SKIP 1
08300 It is often useful to think of a list as an untyped itemvar array with
08400 a single dimension with lower bound 1 and upper bound variable.
08500 .BEGSEC(5)
08600 .INDENT2←3
08700 1. Expression selector
08800 .INDENT1←3
08900 .SKIP 1
09000 listexpr [i1] - returns the item which is the i1 element of the
09100 list. If i1 is less than 0 or greater than the number of elements
09200 of the list an error is signaled.
09300
09400 E. G.
09500 .EXAMPLE
09600 {{itema, itemb, itemc}} [1] = itema
09700 .EXAMPLE
09800 {{itemb, itemc, itemd}} [2] = itemc
09900 .SKIP 1
10000 Note the difference between listexpr[i1] and listexpr[i1 FOR 1].
10100 The former returns an item and the later returns a list containing
10200 a single item.
10300 .SAMESEC
10400 2. Replacement selector
10500 .INDENT1←3
10600 .EXAMPLE
10700 listvar[i1] ← itemexpr;
10800 .SKIP 1
10900 This removes the i1 element of the list and replaces it with the itemexpr
11000 i1 must be between 1 and the number of elements in the list + 1.
11100
11200 E. G.
11300 .BEGIN VERBATIM
11400
11500 LIST1 ← {{ITEM1}};
11600 LIST1[1] ← ITEM2; "NOW LIST1 = {{ITEM2}}"
11700 LIST1[2] ← ITEM3; "NOW LIST1 = {{ITEM2,ITEM3}}"
11800 LIST1[1] ← LIST1[2]; "NOW LIST1 = {{ITEM3,ITEM3}}"
11900 .END
12000 .ENDSEC
12100 .NEXT PAGE
00010 LIST BOOLEANS
00020 .SKIP 4
00030 itm ε listexpr - TRUE if the itm is an element of the listexpr
00040 .SKIP 4
00050 listexpr1 = listexpr2 - TRUE if the lists contain
00060 the same items in the same order.
00100 LIST FUNCTIONS
00200
00210 LENGTH(listexpr) - this returns the current length of the list.
00220 .SKIP 1
00300
00400 COP(listexpr) - this is identical in semantics
00500 with the expression "listexpr[1]"
00600 .SKIP 1
00700 LOP(listvar) - this returns the first item in the list
00800 variable and as a side effect removes the first element
00900 from the list variable. It is logically equivalent to the
01000 following procedure.
01100
01200 ITEMVAR PROCEDURE LOP(REFERENCE LIST ARG);
01300 BEGIN "LOP"
01400 ITEMVAR RESULT;
01500 RESULT ← ARG[1];
01600 ARG ← ARG[2 TO LENGTH(ARG)];
01700 RETURN(RESULT);
01800 END "LOP";
01900
02000 .SKIP 1
02100 LISTX(listexpr,itemexpr,intexpr) - this integer function
02200 returns 0 if the "itemexpr" does not appear in the
02300 "listexpr" at least "intexpr" different times.
02310 Otherwise it returns the index of the "intexpr" occurence
02320 of the "itemexpr" within the "listexpr".
02400 Thus,
02500 .EXAMPLE
02600 LISTX({{FOO,BAZ,GARP,BAZ,BAZ}},BAZ,2) is 4.
02610 .EXAMPLE
02620 LISTX({{FOO,BAZ,GARP,BAZ,BAZ}},GARP,2) IS 0.
02630 .NEXT PAGE
02640 LIST PUT AND REMOVE STATEMENTS
02650
02660 When we insert items into a list we need to specify in some way
02670 the position within the list where the item is to be placed.
02680 We do this by specifying either an index position, or
02690 item BEFORE or AFTER which the item is to be inserted.
02700 .SKIP 2
02710
02720 PUT itm1 IN listvar AFTER n - will insert "itm1" after the "nth"
02730 element of the "listvar". Thus to insert an item
02740 into the list after every element in the list we would
02750 execute:
02760 .EXAMPLE
02770 PUT itm1 IN listvar AFTER LENGTH(listvar);
02780 .skip 1
02790 To insert the item at the head of the list we would use the index
02800 0:
02810 .EXAMPLE
02820 PUT itm1 IN listvar AFTER 0;
02830 .skip 1
02840
02850 If the index is less than 0 or greater than the length of the
02860 list variable then an error message is generated.
02870
02880 .skip 3
02890
02990 PUT itm IN listvar BEFORE n - this is identical in semantics
03090 with:
03190 .EXAMPLE
03290 PUT itm IN listvar AFTER N-1;
03390 .SKIP 3
03490 PUT itm1 IN listvar AFTER itm2;-- this statement searches
03590 for the first occurrence of itm2 within the listvar
03690 and inserts itm1 into the list following itm2. If
03790 itm2 is not an element of the list then itm1 is inserted
03890 at the end of the list. It is equivalent to :
03990 .EXAMPLE
04000 PUT itm1 IN listvar AFTER (IF LISTX(listvar,itm2,1)
04100 ≠ 0 THEN LISTX(listvar,itm2,1) ELSE LENGTH(listvar);
04200 .skip 4
04300 PUT itm1 IN listvar BEFORE itm2 - this statement
04400 searches the listvar for the first occurence of itm2 and
04500 then inserts itm1 ahead of itm2 in the list.
04600 It is logically equivalent to:
04700 .EXAMPLE
04800 PUT itm1 IN listvar BEFORE (IF LISTX(listvar,itm2,1)≠ 0
04900 THEN LISTX(listvar,itm2,1) ELSE 1;
05000
05100 .SKIP 5
05200 REMOVE intexpr FROM listvar -- This removes the "intexpr" element
05300 from the listvar. It is equivalent to:
05400 .EXAMPLE
05500 listvar ← listvar[0 to intexpr-1] &
05550 listvar[intexpr+1 to LENGTH(listvar)];
05600 .skip 5
05700 REMOVE itm FROM listvar - This removes the first
05800 occurrence of "itm" from the list variable. It is equivalent
05900 to:
06000 .EXAMPLE
06100 IF itm ε listvar THEN REMOVE LISTX(listvar,itm,1) FROM listvar;
06200 .SKIP 5
06300 REMOVE ALL itm FROM listvar - This removes all instances of
06400 "itm" from tthe listvar.
06500 It is equivalent to:
06600 .EXAMPLE
06700 WHILE itm ε listvar DO REMOVE itm FROM listvar;
06800 .next page
00100 VI. ASSOCIATIONS
00200 .SKIP 3
00300 The associative power of LEAP comes from the use of associations,
00400 also called triples or associative triples. A triple is a 3-tuple of items.
00500 We write a triple as:
00600 .EXAMPLE
00700 A⊗O≡V
00800 .SKIP 1
00900 where A, O, and V are items or item expressions. We call the first component
01000 of the triple (A above) the "attribute"; the second component (O above), the
01100 "object"; and the third component (V above), the "value". Triples are kept
01200 in the "associative store". Triples are inserted into the associative store
01300 by MAKE statements and removed from the associative store by ERASE statements.
01400 .SKIP 3
01500 MAKE
01600 .SKIP 2
01700 A MAKE statement is of the form:
01800 .EXAMPLE
01900 MAKE itmexpr1⊗itmexpr2 ≡itemexpr3;
02000 .SKIP 1
02100 If the triple already exists in the associative store, the statement
02200 does nothing, otherwise the triple is inserted into the store.
02300 .SKIP 4
02400 ERASE
02500 .SKIP 2
02600 To remove a triple from the associative store we execute an ERASE
02700 statement:
02800 .EXAMPLE
02900 ERASE itmexpr1⊗itmexpr2≡ itemexpr3;
03000 .SKIP 1
03100 If the triple is not in the associative store, the statement does nothing,
03200 otherwise the triple is removed from the associative store. We often wish
03300 to erase all the triples which have specific items as 1 or 2 of their components
03400 but we don't care about the remaining components. To do this we may
03500 use the token ANY to stand for the unspecified components.
03600 .SKIP 1
03700 E. G. to erase all associations with item2 as their object we could use:
03800 .EXAMPLE
03900 ERASE ANY⊗item2≡ANY;
04000 .SKIP 1
04100 to erase all associations with item1 as their attribute and item2 as
04200 their object we would use:
04300 .EXAMPLE
04400 ERASE item1⊗item2 ≡ ANY;
04500 .SKIP 1
04600 ANY may be used in 0, 1, 2, or all 3 positions in the triple. Thus,
04700 .EXAMPLE
04800 ERASE ANY⊗ANY≡ANY;
04900 .SKIP 1
05000 would get rid of all associations in the UNIVERSE.
05100 .NEXT PAGE
00100 ASSOCIATIVE BOOLEANS
00200 .SKIP 2
00300 We may determine if a given triple exists by using the
00400 boolean expression:
00500 .EXAMPLE
00600 itmexp1 ⊗ itmexp2 ≡ itmexp3
00700 .SKIP 1
00800 which will evaluate to TRUE if the triple containing the items
00900 exists in the associative store. As with ERASE 1 or 2 of the components
01000 may be ANY. Thus,
01100 .EXAMPLE
01200 ANY ⊗ ANY ≡ item1
01300 .SKIP 1
01400 will yield the value TRUE if any triple in the associative store contains
01500 item1 as its value component.
01600 .SKIP 4
01700 BINDING ASSOCIATIVE BOOLEANS
01800 .SKIP 2
01900 Another form of the associative boolean takes one or more itemvars
02000 (prefaced by the operator BIND) in place of corresponding item expressions.
02100 The boolean value of this
02200 expression is the same as that of the associative boolean formed
02300 by replacing the "BIND ITEMVAR" terms with ANY. thus the
02400 expression:
02500 .example
02600 FATHER ⊗ JOHN ≡ BIND itv
02700 .skip 1
02800 would have the same truth value as the boolean expression:
02900 .example
03000 FATHER ⊗ JOHN ≡ ANY
03100 .skip 1
03200 The binding boolean though, has an additional side effect if
03300 the value returned is TRUE. In that case it assigns to the itemvar
03400 (prefaced by BIND) the value of an item which makes the
03500 associative boolean TRUE. For example above, the interpreter would
03600 search to see if there was any triple in the associative store,
03700 which had both FATHER as its attribute component and JOHN as its object
03800 component. If it found one, the interpreter would then assign the item in
03900 the value component to the itemvar "itv".
04000 .skip 1
04100
04200 Note that if there is more than one triple which satisfies the associative
04300 boolean, which one is selected is undefined. If there is no triple which
04400 satisfies the boolean then the boolean returns FALSE and the value of the
04500 BIND itemvar remains unchanged. Thus if we had a group of associations:
04600 with attributes, the items CAR and CDR (representing a LISP like structure)
04700 we could find the last cell in the CDR direction of the LISP-list pointed
04800 to by first, using the very simple program:
04900 .BEGIN VERBATIM
05000
05100 LAST ← FIRST ;
05200 WHILE (CDR ⊗ LAST ≡ BIND LAST ) DO;
05300
05400 .end
05500 .SKIP 1
05600 Note that each time the associative boolean is executed, the current value
05700 of the itemvar LAST is used as the object component, and if successful
05800 the value of LAST is changed to become the next element in the CDR direction.
05900 .NEXT page
00100 DERIVED SETS
00200 .SKIP 2
00300 In order to use the associative nature of triples we must have
00400 ways of finding triples which have certain specified components. One way
00500 we have discussed above is the use of binding associative booleans.
00600 Another
00700 is to use derived sets. The third, FOREACH statements, will be discussed
00800 later.
00900 .SKIP 1
01000 There are three forms of derived sets now implemented: the (')
01100 derived set, the (⊗) derived set, and the (≡) derived set.
01200 .EXAMPLE
01300 itmexp1 ' itmexp2
01400 .SKIP 1
01500 produces the set of all items X, such that
01600 .EXAMPLE
01700 itmexp1 ⊗ X ≡ itmexp2
01800 .SKIP 1
01900 is a triple currently in the associative store.
02000 .EXAMPLE
02100 itmexp1 ⊗ itmexp2
02200 .SKIP 1
02300 produces the set of all items Y such that,
02400 .EXAMPLE
02500 itmexp1 ⊗ itmexp2 ≡ Y
02600 .SKIP 1
02700 is a triple in the associative store.
02800 .EXAMPLE
02900 itmexp1 ≡ itmexp2
03000 .SKIP 1
03100 produces the set of all items Y such that.
03200 .EXAMPLE
03300 Y ⊗ itmexp1 ≡ itmexp2
03400 .SKIP 1
03500 is a triple in the associative store
03600 .SKIP 1
03700 One or both of the item expressions may be the token ANY. Again this
03800 means that we do not care about the value of that component. Thus,
03900 .EXAMPLE
04000 itmexp1 ⊗ ANY
04100 .SKIP 1
04200 will search the associative store for all associations which have itmexp1 as
04300 their attribute component, and will return the set of value components of
04400 such associations.
04500 .NEXT PAGE
04600
00100 EXAMPLE -DERIVED SETS
00200 .SKIP 2
00300 Let us represent a family tree using associations. We will have
00400 the declared item PARENT and the sets MALE and FEMALE, as well as
00500 items representing members of the family: JOE, TIM, TED, JOYCE, JANET,
00600 ALICE, and HARRIET.
00700 .SKIP 1
00800 The familial relationships are represented by a the following tree.
00900 .BEGIN VERBATIM
01000
01100 TOM ALICE JOE JAN
01200 | | | |
01300 --------------- ------------
01400 | |
01500 ------------- |
01600 | | |
01700 JOYCE TED TIM
01800 | |
01900 -------------------------------------
02000 |
02100 HARRIET
02200
02300 .END
02400
02500 Thus, the parents of HARRIET are JOYCE and TIM; the parents of JOYCE and TED
02600 are TOM and ALICE and so forth.
02700 .SKIP 1
02800 We can represent this tree by making the following associations:
02900 .SKIP 1
03000 .BEGIN VERBATIM
03100 MAKE PARENT ⊗ HARRIET ≡ JOYCE;
03200 MAKE PARENT ⊗ HARRIET ≡ TIM;
03300
03400 MAKE PARENT ⊗ JOYCE ≡ TOM;
03500 MAKE PARENT ⊗ JOYCE ≡ ALICE;
03600
03700 MAKE PARENT ⊗ TED ≡ ALICE;
03800 MAKE PARENT ⊗ TED ≡ TOM;
03900
04000 MAKE PARENT ⊗ TIM ≡ JOE;
04100 MAKE PARENT ⊗ TIM ≡ JAN;
04200
04300 .END
04400 To keep track of the sexes of the various people we have the two
04500 sets MALE and FEMALE.
04600 .SKIP 1
04700 .BEGIN VERBATIM
04800 MALE ← {TIM,TED,TOM,JOE};
04900 FEMALE ← {JAN,JOYCE,ALICE};
05000 .END
05100 .SKIP 1
05200 NOTE: The above is merely one possible way we might represent the family tree.
05300 For example instead of the MALE and FEMALE sets, we might have associations
05400 of the form: SEX ⊗ person ≡ MALE, where MALE is now an item. One of the
05500 interesting difficulties in using LEAP is deciding how to represent a given
05600 system of data as LEAP will often allow many different ways of representing
05700 the same information. Some of the tradeoffs between the different representations
05800 will be discussed later.
05900 .SKIP 2
06000 Now to use the structure we have built. Let us say that we wished to find the
06100 parents of Harriet. We may easily do this by use of a derived set.
06200 .SKIP 1
06300 .BEGIN VERBATIM
06400 HARRIET_PARENTS ← PARENTS ⊗ HARRIET;
06500 .END
06600 .SKIP 1
06700 where HARRIET_PARENTS has been declared to be a set variable.
06800 .SKIP 1
06900 To find Harriet's brothers is a little more complicated.
07000 .BEGIN VERBATIM
07100 "find one parent"
07200 PARENT_ITMVR ← COP(PARENTS ⊗ HARRIET);
07300 Comment the above could be replaced by
07350 the binding associative boolean.
07500 IF ¬(PARENTS⊗HARRIET≡BIND PARENT_ITMVR) THEN
07600 PRINT("HARRIET IS AN ANDROID")
07700 ;
07800 "set of brothers,sisters"
07900 SIBLING_SET ← PARENT ' PARENT_ITMVR;
08000
08100 "brother is a male sibling"
08200 BROTHER_SET ← SIBLING_SET ∩ MALES;
08300 .END
08400 .SKIP 1
08500 The above example illustrates the use of associations as binary relations between
08600 items, in this case the relation "parent of". Often we wish to associate
08700 several different pieces of data with an item. To do this we may declare items
08800 which will be used to name the data and then allocate items which will contain
08900 the corresponding data for each item. For example we may wish to record such
09000 various attributes of a person such as weight, height, nickname. To do this
09100 we will have items WEIGHT, HEIGHT, and NICKNAME which will be used to name the
09200 attributes. We will allocate items whose datums are the corresponding values.
09300 E.G.
09400 .BEGIN VERBATIM
09500
09600 MAKE WEIGHT ⊗ JOE ≡ NEW(165);
09700 MAKE HEIGHT ⊗ JOE ≡ NEW (70);
09800 MAKE NICKNAME ⊗ JOE ≡ NEW("JOEY");
09900
10000 .END
10100 Then to find the value of an attribute such as weight we would use the
10200 expression:
10300 .BEGIN VERBATIM
10400 DATUM(INT_ITMVR ← COP(WEIGHT⊗JOE))
10500 .END
10600
10700 Remember that the assignment of the item to the integer itmvr is required
10800 so that the compiler can tell what the data type of the datum is.
10900 Again we could use a binding associative boolean instead of a COP of
11000 a derived set. The binding boolean generates more efficient code, but has
11100 the disadvantage of returning a boolean value rather than an item value
11200 as does COP. However since COP will stop your program if you apply it
11300 to an empty set, it is well worth the syntactic bother to use the associative
11400 boolean.
00100 .SKIP 1
00200
00300 FOREACH STATEMENTS
00400
00500 By using these operations and set variables we
00600 have sufficient power to do any search on the associative data
00700 base. However one soon realizes that they are very
00800 inconvenient to use in all but the most simple cases. Therefore
00900 another technique is provided called FOREACH statements.
01000 .SKIP 1
01100 A FOREACH statement is similar to a FOR statement
01200 in that it causes the iteration of a given SAIL statement to be
01300 performed with a control variable receiving various values
01400 for each iteration. These values are obtained by searching the
01500 associative data base or enumerating the members of a set of items.
01600 .SKIP 1
01700 The most simple FOREACH statement has a single "local" itemvar
01800 and a single "associative context". A local itemvar serves the
01900 same purpose as the loop variable in a FOR statement. With each
02000 iteration it will receive an item value and a SAIL statement will
02100 be executed. A simple example of a FOR statement is:
02200 .EXAMPLE
02300 FOREACH X | BROTHER⊗BOY1≡ X DO
02400 .ONCE CENTER
02500 <stmt>
02600 .SKIP 1
02700 This statement is equivalent to the following:
02800 .SKIP 1
02900 .BEGIN VERBATIM
03000
03100 listx← BROTHER⊗BOY;
03200 FOR j ← 1 step 1 until LENGTH(LISTX) DO
03300 BEGIN X←listx[j];
03400 <stmt>
03500 END;
03600
03700 .END
03800
00100 .SKIP 1
00200
00300 ANY and BINDIT
00400
00500 There are two special "items" which may not be arguments to a make statement
00600 (and thus may not be components of any association in the associative data
00700 base). These are ANY and BINDIT. These items may appear anywhere else
00800 an item might be legal, such as within sets, itemvars and lists.
00900
01000 We have mentioned ANY earlier. It essentially represents "don't care" when
01100 we are doing pattern matching on the associative store. Thus
01200
01300 FOREACH x | x ⊗ANY ≡ B DO
01400
01500 is to be iterated once for every distinct X which appears in associations with
01600 B as the value component.
01700
01800 BINDIT is used to conditionally control ? searches. It also has importance
01900 in MATCHING PROCEDURES which will be discussed later.
02000
02100 There are special forms of the BINDING BOOLEANS and FOREACH statements,
02200 are affected when an itemvar to be bound contains BINDIT.
02300
02400 The BINDING BOOLEAN B ⊗ C ≡ ? x is identical in effect with the expression
02500 .example
02600 (IF x = BINDIT THEN (B⊗C≡ BIND x) ELSE (B⊗C≡x))
02700 .skip 1
02800 That is the value of x is used if not equal to BINDIT and the itemvar x
02900 is to be bound if the value of x is equal to BINDIT.
03000
03100 .example
03200 FOREACH ?x,y | A⊗x≡ y DO <stmt>
03300 .example
03400 is similarly equivalent to
03500
03600 .begin verbatim
03700 IF X=BINDIT THEN
03800 FOREACH x,y | A⊗x=y DO <stmt>
03900 else FOREACH y | A⊗x≡y DO <stmt>
04000 .end
04100 Note that the FOREACH in the else part of the statement does not have "x"
04200 in its binding list and thus x is considered to have a value. The reverse is
04300 true in the THEN part of the statement.
04400