UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Lotus - a Procedural Environment Fowler, James M. 1976

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1976_A6_7 F68.pdf [ 4.17MB ]
Metadata
JSON: 831-1.0051783.json
JSON-LD: 831-1.0051783-ld.json
RDF/XML (Pretty): 831-1.0051783-rdf.xml
RDF/JSON: 831-1.0051783-rdf.json
Turtle: 831-1.0051783-turtle.txt
N-Triples: 831-1.0051783-rdf-ntriples.txt
Original Record: 831-1.0051783-source.json
Full Text
831-1.0051783-fulltext.txt
Citation
831-1.0051783.ris

Full Text

LOTUS - A P r o c e d u r a l Environment i by James M. Fowler B.5c, # U n i v e r s i t y o f B r i t i s h C o lumbia, 1973 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF We a c c e p t t h i s t h e s i s as conforming t o the r e q u i r e d s t a n d a r d . The U n i v e r s i t y o f B r i t i s h C o l u m b i a August 1976 ( c ^ James M. Fowler, 1 9 7 6 MASTER OF SCIENCE i n the department of COMPUTER SCIENCE. In presenting th i s thes is in pa r t i a l fu l f i lment of the requirements for an advanced degree at the Univers i ty of B r i t i s h Columbia, I agree that the L ibrary sha l l make it f ree ly ava i lab le for reference and study. I further agree that permission for extensive copying of th is thesis for scho lar ly purposes may be granted by the Head of my Department or by his representat ives. It is understood that copying or pub l i cat ion of th is thes is for f inanc ia l gain sha l l not be allowed without my writ ten permission. Department of ( jQtylA U I & / Eft C P The Univers i ty of B r i t i s h Columbi 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 Date / / Oh ABSTRACT i i Much r e c e n t A r t i f i c i a l I n t e l l i g e n c e r e s e a r c h i n v o l v e s p r o c e d u r a l o r e x e c u t a b l e r e p r e s e n t a t i o n s o f k n o w l e d g e a s an a l t e r n a t i v e t o c o n v e n t i o n a l s t a t i c d a t a r e p r e s e n t a t i o n s , LOTUS i s a p u r e l y p r o c e d u r a l p r o g r a m m i n g e n v i r o n m e n t where v a r i a b l e s c a n assume o n l y e x e c u t a b l e v a l u e s , and may be i n t e r r o g a t e d o n l y t h r o u g h t h e i r e x e c u t i o n . The LOTUS l a n g u a g e i s d e f i n e d and p r o v e n t o be u n i v e r s a l . D e s i g n s t r a t e g i e s and i m p l e m e n t a t i o n t e c h n i g u e s a r e d e v e l o p e d w h i c h a l l o w a l g o r i t h m s t o be i m p l e m e n t e d as g l o b a l s e l f - m o d i f y i n g p r o c e d u r a l n e t w o r k s . Such e x e c u t a b l e n e t w o r k s may be v i e w e d a s s e l f - m o d i f y i n g i n t e r p r e t e r s w h i c h s i m p l y e x e c u t e t h e i r s y m b o l i c i n p u t s , A c o n t e x t - f r e e p a r s e r i s i m p l e m e n t e d i n w h i c h t h e s e n t e n c e t o be p a r s e d i s r e a l l y a LOTUS p r o g r a m w h i c h , when e x e c u t e d , p a r s e s i t s e l f . A t t e n t i o n i s drawn t o t h e i n i t i a l c o n c e p t u a l d i f f i c u l t i e s p r e s e n t e d by LOTUS. P o s s i b l e e x t e n s i o n s t o t h e l a n g u a g e w h i c h c o u l d make i t more e f f e c t i v e i n o t h e r A. I . d o m a i n s a r e d i s c u s s e d , and q u e s t i o n s o f s y n c h r o n i z a t i o n r e q u i r e m e n t s a n d p a r a l l e l i s m a r e i n v e s t i g a t e d . A LOTOS M a n u a l and t h e c o m p l e t e MTS-LISP i m p l e m e n t a t i o n o f LOTOS a r e i n c l u d e d as a p p e n d i c e s . LOTUS i i i CONTENTS 1. INTRODUCTION . . 1 2. THE LOTUS ENVIRONMENT . . . . . 3 2.1 A S i m p l e U n i v e r s a l C o n t r o l S t r u c t u r e . 4 2.2 The LOTUS Language . 9 2.3 A S i m p l e Example . . . . . . . . . . . . 1 2 2.4 A C o n t e x t S e n s i t i v e A c c e p t o r . . . . . 17 3. A CONTEXT-FREE PARSER . . . . . 25 3.1 The P a r s i n g A l g o r i t h m . . . . . . . . 25 3.2 The LOTUS P a r s e r 29 4. FURTHER OBSERVATIONS . . . . . . . . . . . 34 5. CONCLUSIONS . . . . . . . . . . . . . . . 4 2 BIBLIOGRAPHY . . . . . . . . . . . 44 APPENDICES I - A LOTUS MANUAL . . . . . . . . . . . . 46 I I - A LOTUS "GREEN CARD" . . . . . . . . . . 63 I I I - LOTUS (MIS-LISP VERSION) . . . . . . . 64 IV - A LOTUS CONTEXT-FREE PARSER 7 8 INDEX . . . . . . . . . . . . . . . . . . . . . 88 1. INTRODUCTION Page 1 LOTUS i s a programming l a n g u a g e which was d e s i g n e d and i m p l e m e n t e d t o p r o v i d e an o p p o r t u n i t y t o g a i n p r a c t i c a l e x p e r i e n c e i n a p u r e l y p r o c e d u r a l programming e n v i r o n m e n t . LOTUS i s i m p l e m e n t e d i n LISP and i s c o - r e c u r s i v e w i t h L I S P . V e r s i o n s i n b o t h MTS-IISP [ 2 0 ] f o r t h e IBM /370 and S t a n f o r d A I L I S P 1.6 [ 1 4 ] f o r t h e PDP-10 have been i m p l e m e n t e d . However, t h e l a n g u a g e i s now s u f f i c i e n t l y s t a b l e t h a t i t c o u l d and p r o b a b l y s h o u l d be i m p l e m e n t e d i n a more e f f i c i e n t f a s h i o n b e f o r e more s e r i o u s r e s e a r c h i s c o n t e m p l a t e d . The p r o c e d u r a l domain o f t h e LOTUS s y s t e m was d e f i n e d t o p r o v i d e c o n s t r a i n t s which would f o r c e a p r o c e d u r a l a p p r o a c h t o program d e s i g n , a s w e l l as e n a b l e a r e l a t i v e l y s t r a i g h t f o r w a r d i m p l e m e n t a t i o n o f LOTUS i t s e l f . The s i n g l e most s i g n i f i c a n t o f t h e s e c o n s t r a i n t s i s t h a t v a r i a b l e s c a n assume o n l y p r o c e d u r a l v a l u e s - t h a t i s , LOTUS "atoms" a r e bound t o e x e c u t a b l e f orms and c a n o n l y be i n t e r r o g a t e d t h r o u g h t h e i r e x e c u t i o n . T h i s c o n s t r a i n t e l i m i n a t e s t h e need f o r any l a n g u a g e p r i m i t i v e s which o p e r a t e on c o n v e n t i o n a l s y n t a c t i c d a t a s t r u c t u r e s s u c h a s L I S P ' s l i s t s . I t a l s o i n d i c a t e s t h e u s u a l p a r a d i g m f o r c o n d u c t i n g an i n t e r a c t i o n w i t h a LOTUS s y s t e m . A LOTUS s y s t e m s i m p l y e x e c u t e s whatever i n p u t s y m b o l s a r e e n c o u n t e r e d on t h e i n p u t c h a n n e l . The "meaning" o f each i n p u t symbol i s t h e r e f o r e d e pendent on t h e c u r r e n t e x e c u t a b l e LOTUS Page 2 l i IITBODCJCTION (cont'd) value of the symbol, and i s " s t o r e d " i n the LOTOS network by e s t a b l i s h i n g new executable values f o r other LOTUS v a r i a b l e s as the r e s u l t of e x e c u t i n g the input symbol. The LOTUS language p r i m i t i v e s are designed t o allow the c o n s t r u c t i o n of these new pr o c e d u r a l fragments. Other p r i m i t i v e s e x i s t to c o n s t r u c t forms which w i l l cause symbols to be p r i n t e d on the output channel, thereby completing the i n t e r a c t i o n with the user. S o l u t i o n s to s e v e r a l common programming problems have been implemented i n the LOTUS environment, and are d e s c r i b e d i n d e t a i l l a t e r . In p a r t i c u l a r , a c o n t e x t - f r e e p a r s e r has been w r i t t e n and was used i n a system which i d e n t i f i e s simple noun phrases l e t t e r e d on a gra p h i c s screen with a l i g h t pen [ 6 ] , C e r t a i n design s t a t e g i e s and methods of d e f i n i n g a l g o r i t h m s a p p r o p r i a t e to the LOTUS environment have emerged. They w i l l seem somewhat unconventional, but appear to be both e f f e c t i v e and e s s e n t i a l i n such a p r o c e d u r a l domain. LOTUS has been d e s c r i b e d as p r o v i d i n g a method f o r implementing a g e n e r a l purpose a l g o r i t h m i n which the p a r t i c u l a r problem at hand i s used by the al g o r i t h m t o generate a s i n g l e purpose procedure s u i t e d to the problem which i s then executed and d i s c a r d e d [ 1 5 1 . I t has a l s o been d e s c r i b e d as p r o c e d u r a l t i n k e r - t o y s [9]. 2. THE LOTUS ENVIRONMENT Page 3 The primary a c t i v i t y of most LOTUS programs i s the creation or modification of other LOTUS programs. The biggest obstacle l i m i t i n g t h i s a c t i v i t y i n conventional "procedural" languages such as MICRO-PLANNER [2, 19, 21], CONHIVEB [7, 11, 12, 18] or even LISP i t s e l f i s the complex relationship between the language syntax and the problem semantics. The d i f f i c u l t i e s involved in implementing code which can, for example, construct a s y n t a c t i c a l l y correct and semantically appropriate "THFIND" statement i n MICRO-PLANNER are considerable. Combined with the problems of how to organize such fragments for l a t e r use and how to e f f e c t semantically motivated changes to the syntactic representations ( i . e . debug the new procedures), such a c t i v i t i e s become very unpleasant to contemplate. LOTUS addresses this d i f f i c u l t y from two d i r e c t i o n s . F i r s t , the syntactic complexity of a LOTUS fragment i s minimized by assuming a global environment. The need f o r formal arguments commonly associated with procedural imperatives i s thereby eliminated. The fact that most LOTUS programs are single purpose code generated to handle the s p e c i f i c s i t u a t i o n at hand makes the generality provided by formal arguments quite unnecessary. LOTUS Page JHE LOTUS ENVIRONMENT (cont'd) S e c o n d l y , i n o r d e r t o f u r t h e r s i m p l i f y t he r e l a t i o n s h i p between s e m a n t i c i n t e n t and s y n t a c t i c s t r u c t u r e , LOTUS adopts a s i m p l e almost t r i v i a l c o n t r o l s t r u c t u r e . k Simrjle Universal Control Structure The LOTUS language has a single formation r u l e , the recursive i f - t h e n - e l s e statement. Bohm S Jacopini [ 1 ] have investigated properties of control structures using flow diagrams comprised of functional and predicative boxes - the common flowchart. The results of Bohm & Jacopini's work are summarized here so that they may be expanded to prove the univer s a l i t y of the LOTUS control structure. They f i r s t demonstrate that " I t i s not possible to decompose a l l flow diagrams into a f i n i t e number of given base diagrams" 1. However, they go on to introduce three base diagrams (see figure 1) and three new functional boxes (T, F and K) along with one new predicative box (w) which are defined as follows: T transforms the object x into the ordered pair (t,x) . F transforms the object x into the ordered pair (f,x). 1 Bohm & Jacopini [ 1 ] , page 367. ZJL III LOTUS ENVIRONMENT (cont'd) LOTUS Paqe 5 K transforms the ordered pair (t,x) or (f#x) into the object x. v i s v e r i f i e d or not according to the t / f value of the f i r s t element.of i t s ordered pair argument. Hhile K and w are defined only on an ordered pair, T and F are defined on either an ordered pair or an elementary object. The four new boxes combine to manipulate a s t a c k - l i k e structure, and leave the o r i g i n a l f u n c t i o n a l and predicative boxes undefined on a p a i r . ir A $ Figure 1 - Three Base Diagrams An inductive proof i s then given for the theorem: "I f a mapping x -> x* i s representable by any flow diagram consisting of functional and predicative boxes, i t i s also representable by a flow diagram decomposable int o rr, ^ and <3? containing the same boxes which occurred i n the i n i t i a l d i a g r a m s , plus the boxes T, F, K and The l a t t e r half of the paper i s devoted to proving that every Turing machine i s reducible to a program written as a flow diagram in an eguivalent set of base diagrams. 2 Bohm S Jacopini [ 1 ] , page 368. LCTUS I s . THE LOTUS ENVIRONMENT (cont'd) Paqe 6 We w i l l now show that the s i n g l e r e c u r s i v e oase diagram P shown i n f i g u r e 2 can be used i n p l a c e of tt, A and $ i n the above theorem. The f u n c t i o n a l boxes P i n the base diagram can be e i t h e r a d d i t i o n a l occurrences of the base diagram P i t s e l f or p r i m i t i v e o p e r a t i o n s (see f i g u r e 3) or symbolic l a b e l s . F i g u r e 2 - Base Diagram P For reasons which w i l l become apparent we w i l l a c t u a l l y prove: I f a mapping x -> x' i s r e p r e s e n t a b l e by a f l o w diagram decomposable i n t o 1T, A and £ c o n t a i n i n g f u n c t i o n a l and p r e d i c a t i v e boxes i n c l u d i n g T, K, F and then the mapping (v,x) -> ( v ^ x ' j i s r e p r e s e n t a b l e by a flow diagram decomposaule i n t o P c o n t a i n i n g the same boxes which o c c u r r e d i n the o r i g i n a l diagram. Since a l l the boxes except T, K, F and w a r e undefined on an ordered p a i r and P op e r a t e s o n l y on a p a i r , i t i s necessary t o d e f i n e a n o r m a l i z a t i o n of J a c o p i n i ' s p r i m i t i v e boxes so they a l s o operate on p a i r s . F i g u r e 3 shows t h i s n o r m a l i z a t i o n , where the box T/F i n d i c a t e s o p t i o n a l l y e i t h e r T or F. Two new p r i m i t i v e s *PASS and *FAIL are i n t r o d u c e d . These n o r m a l i z e d p r i m i t i v e s are admissable occurrences of P i n the base diagram of f i g u r e 2. LOTOS I s . THE LOTUS ENVIRONMENT (cont'd) Paqe 7 T/F •PASS •FAIL Figure 3 - Normalized Primitives The base diagram P i s made recursive by allowing each P an optional symbolic l a b e l and accepting symbolic references i n the formation rule. Such symbolic references are indicated by a c i r c l e d l a b e l , as i n figure 4. Our theorem i s now proven by showing that each and $ can be normalized to diagrams decomposaule demonstrated in figure U. of TT/ i n t o P, A as LOTUS Page THE LOTUS ENVIRONMENT (cont'd) Pigure 4 - Decomposition of Tf, A and $ into P The application of these normalized constructions for Tf, A and to the decomposition of Jacopini's type I and type II diagrams shows that the single stack structure i s s u f f i c i e n t to maintain the r e s u l t of his o r i g i n a l theorem, stated e a r l i e r . The two theorems therefore combine to prove that the single recursive formation rule P provides a universal control LOTUS 2j. THE LOTUS ENVIRONMMJ. (cont'd) Page 9 s t r u c t u r e . lk§. i O J U S Language The s i n g l e f o r m a t i o n r u l e P o f f i g u r e 2 and t h e d e f i n i t i o n o f p r i m i t i v e o p e r a t i o n s g i v e n i n f i g u r e 3 form t h e b a s i s f o r t h e LOTUS l a n g u a g e . The B-N-F s y n t a x f o r LOTUS programs I s a s f o l l o w s : PGM > (PGM PGM PGM) t h e ( i f - t h e n - e l s e ) t r i p l e > SYMBOL a LOTUS "atom" > PRIMITIVE a L I S P s - e x p r e s s i o n The LOTUS s y n t a x a l l o w s t h e c o n t r o l s t r u c t u r e o f a program t o become a p r o p e r t y o f t h e p h y s i c a l ( s y n t a c t i c ) s t r u c t u r e o f t h e program. T h i s r e p r e s e n t s a marked d e p a r t u r e from c o n v e n t i o n a l l a n g u a g e s s u c h as L I S P , where t h e c o n t r o l s t r u c t u r e i s a s e m a n t i c p r o p e r t y o f i t s p r i m i t i v e f u n c t i o n s (eg. COND, OR, e t c . ) a s w e l l a s any u s e r - d e f i n e d f u n c t i o n s . LOTUS p r o v i d e s a programming e n v i r o n m e n t i n which t h e l o g i c a l program s t r u c t u r e maps d i r e c t l y onto the p h y s i c a l s t r u c t u r e and v i c e - v e r s a . The i m p o r t a n c e o f t h i s p r o p e r t y c a n n o t be o v e r e m p h a s i z e d i n a domain where p r o c e d u r e s a r e r o u t i n e l y c o n s t r u c t i n g s y n t a c t i c representations of s e m a n t i c LOTUS Page 2 «_ THE LOTUS ENVIRONMENT (cont'd) intent ( i . e . other procedures). The LOTUS environment i s designed to support, a programmer in t h i s procedural domain. Since we w i l l now begin to look at actual examples of LOTUS programs, i t i s appropriate that the reader should turn to Appendix I "A LOTUS Manual", and read the sections which describe the LOTUS Prettyprinter and the LOTUS Compiler. Later, when we begin using the LOTUS primitives, i t w i l l be i n s t r u c t i v e to sketch " c e l l diagrams" of LOTUS programs to better understand the meaning of the prettyprint representations. In these diagrams each LOTUS t r i p l e i s sketched as a c e l l having three output pointers (TEST PASS FAIL), much l i k e a CONS c e l l i n LISP with i t s CAR and CBR pointers. Figure 5 gives c e l l diagrams for two programs beside t h e i r respective prettyprint displays. LOTUS I s . THE LOTUS ENVIRONMENT (cont'd) Page 11 x *<*rP X) > X I «-> A »<»TALK> *<»TERSE> »<»S£TOC X <*AND A B O ) > > > «-> B C c X *<*TALK) • UTERSE) • USETQC X (*NOT <*H0 A B » > > »<*PP X) > x : - > > > > > ••> A *FAIL *PASS -•> B C • '• • c -«> SAME AS PASS FORM <ABOVE) A Figure 5 - Two LOTUS Programs When the "leaves" of the programs are language p r i m i t i v e s which refer to other portions of the network, these references can be indicated graphically i n the diagram to i l l u s t r a t e what the primitive i s r e a l l y doing. It i s taese language primitives which provide the a b i l i t y f o r a LOTUS network to r e f l e c t the meaning of i t s inputs within i t s own executable structures. Before proceeding to the f i r s t examples of LOTUS systems, the reader should have a basic understanding of the LOTUS Language Primitives, which are described in Section 4 of Appendix I. LOTOS 2JL THE LOTOS ENYTSONMENT (cont'd) Page 2^3 A S i m p l e Example Our f i r s t introduction to a LOTUS network i s a simple system which " l i k e s " alternating A's and B's, and complains when the input seguence i s broken. It consists of two symmetric programs, each containing a *AND of three elements. The sample dialogue given below includes the compiler statement which establishes the network, followed by a series of inputs and responses. Whenever an input symbol i s repeated the network complains with "UNHAPPY". * ( * T A L K ) *(*COMP (A (*AND (*P0SHQ B (*POST B B) B *F&IL) * (*PUSHQ B (*POST A A) B *FAIL) * (*SETQ A (*PEINTC UNHAPPY)))) * (B (*AND (*PUSHQ A (*POST A A) A *FAIL) * (*PUSHQ A (*POST B B) A *FAIL) * (*SETQ B (*PRINTC UNHAPPY))))) *A *B *B > UNHAPPY *a *A > UNHAPPY *A > UNHAPPY Before the operation of t h i s simple network is analysed in d e t a i l , the algorithm i t represents i s described. I n i t i a l l y the network w i l l be "happy" with either an A or a B. If the i n i t i a l input i s an A, the program bound to A LOTUS Is. IHE LOTUS ENVIRONMENT (cont'd) Page 13 constructs new programs for both A and B. The new program bound to A simply pri n t s "UNHAPPY" and leaves the network unchanged. The new program for B restores the network, to i t s i n i t i a l state and does what would have been done i f the i n i t i a l input had been a B. A detailed study of t h i s network using c e l l diagrams w i l l i l l u s t r a t e the operation of several language primi t i v e s . In p a r t i c u l a r , the workings of *PUSHQ and the elusive *POST w i l l be exposed. C e l l diagrams f o r the i n i t i a l network are given in figure 6 with the corresponding p r e t t y p r i n t of the two programs. *OTALK> »!«Cbn|E(A OAN6 OPU'JIid B OPCST 11)11 *FAIL> « OPUiilUI ll OPUST A .1) » *FAIL> * <«EFTI) A OPRINTC UHHIll'PY)))) • (B OAHB OPUSIIU A UPOST A A) A »FAIL) t Or-USHO A OPOST B B) A *FAIL> » OSETQ A OPRINTC UNHAPPY))))) « O P P A) „ v > A | «•> O P U S H Q B t l B *FAIL> > .»> <«pllliMU B St B (FAIL) > O S E T Q A 11) > «FAIL >' $FAIL »<«PP B) > B : OPUSMO A t t A *FAIL> > .-> OPIISHQ A k t A *FAIL) > OSETa A I t ) > *FAIL > *FAIL O P U S H Q B ...) 3, (FAIL O P U S H Q A ...) •FAIL O P U S H O B ...> ( »FAIL (*PUSHQ A ...) I *FAIL V v OSETQ A .> USETQ B .> Figure 6 - The I n i t i a l Network If the i n i t i a l input symbol i s an A, the structure bound to A w i l l be executed. The f i r s t element encountered i n program A i s a c a l l to the *PUSHQ pr i m i t i v e , namely "(*PUStiQ a (*POST B B) B *FAIL)". The *FUSHQ function creates a new t r i p l e c e l l LOTUS I s . THE LOTUS ENVIRONMENT (cont'd) Page from the present LOTUS values of the l a s t three arguments and binds i t to the f i r s t argument which must, of course, be a symbol. Thus, the FAIL form of the.new c e l l i s the present value of the symbol *FAIL, and the PASS form xs the present value of the symbol B. The TEST form w i l l be the value of the form "(*POST B B) Now, *POST i s a primitive wnich returns a form which (when executed) w i l l bind the present value of i t s second argument to i t s f i r s t argument (necessarily a symbol). Therefore " (*POST B B)" returns a form to the *PUSHQ which w i l l restore program B to i t s present value. The *PUSHQ primitive then binds t h i s new c e l l to the symbol B. USETQ B => 0 Lo OPUSHO B . . . ) | *FAZL UPUSHQ A ...) I (FAIL % v tt. MPUSHQ B • ..>^, *FAXL <*PUSHO A ...) X. 'FAIL <»SET0 A .) V USETQ B .) Figure 7 - After the F i r s t *PUSHQ Figure 7 shows the network a f t e r the f i r s t *PUSHQ has executed, with tha deferred binding of B generated by the •POST indicated g r a p h i c a l l y . The next element in A i s another •PUSHQ which stores the current binding of A i t s e l f onto program B. The l a s t element i n program A i s •"(*SETQ A 2- THE LOTUS ENVIRONMENT (cont'd) LOTUS Paqe 15 (•PRINTC UNHAPPY))". *SETQ i s a primitive wnich binds the present value of i t s second argument to i t s f i r s t argument, which must be a symbol. Since the *PRINTC primitive returns a form which w i l l p r i n t i t s symbolic argument, program A w i l l now, when executed, simply print "UNHAPPY". Program A has now fin i s h e d executing, and the f i n a l state of the network i s as shown i n f i g u r e 8, which also includes a pr e t t y p r i n t of the network after t h i s f i r s t input has been executed. *«*rf> A) > A : (PRINT I t ) »(»PP ») > D : «»> USETQ A I I ) > .»>' USETQ B t t ) > >•> UPUSHQ A I t A *FAIL> > •-> UPtlSHU A t t A *FAIL) > OSKTQ A t t ) > *FAIL > *FAIL > (QUOTE NIL) > (QUOTE NIL) (PRINT 'UNHAPPY) 0 USETQ A^> (FAIL USETQ l ^ l I *FAIL OPUSHQ B ...) *FAIL OPUSHO A ...) | ' «FAIL V v O -P e l OPUSHQ B •••>!_ *FAIL UPUSHQ A (•SETQ A .) • USETQ B .) •FAIL Figure 8 - After the F i r s t Input At t h i s point, any further A's w i l l r e s u l t in the network responding with "UNHAPPY". The input of a B, howaver, w i l l cause f i r s t A and then B to be restored to th e i r i n i t i a l values, and then the o r i g i n a l body of program B to be executed. LOTOS Page 16 2. THE LOTOS ENVIRONMENT (cont'd) This example i s meant to point out a s i g n i f i c a n t c h a r a c t e r i s t i c of the t y p i c a l LOTOS network. An algorithm implemented in LOTUS does not even f a i n t l y resemble a conventional computer program. The LOTOS algorithm i s not captured in a concise seguence of procedural steps. Rather, i t i s spread out a l l over the LOTUS network waiting to be executed. To make the situ a t i o n even more d i f f i c u l t to grasp, the execution of any one element of the network often results i n major portions of the network being re-written. Conventional methods of analysing computer programs are simply i n e f f e c t u a l i n such a box of procedural snakes. However a l l i s not hopeless. It appears that soma LOTUS networks can be studied in terms of something that can be c a l l e d a "process". Let us accept a process as an abstraction of an algorithm which captures the present and future intent of the algorithm. Such processes can be i d e n t i f i e d as proceeding through the network, emitting new sub-processes as necessary. The various fragments which constitute a process can then oe analysed i n terms of the intent that each one represents. The notion of a process w i l l be developed i n more d e t a i l in" the next example. LOTUS Page THE LOTUS ENVIRONMENT (cont'd) A Con t e x t S e n s i t i v e A c c e p t o r The next example p r e s e n t s a more r e a l i s t i c view o f a t y p i c a l LOTUS envir o n m e n t , and w i l l i l l u s t r a t e some b a s i c i m p l e m e n t a t i o n t e c h n i g u e s as w e l l as p e r t i n e n t d e s i g n s t r a t e g y . The network i s a c o n t e x t s e n s i t i v e a c c e p t o r f o r a s t r i n g f o l l o w e d by i t s e l f o v e r the a l p h a b e t [ A , B ] . I n t h e network which f o l l o w s , two symbols o t h e r t h a n t h e elements o f the a l p h a b e t a re i n t e n d e d f o r use as top l e v e l i n p u t s . The symbol "START" e r a s e s the e f f e c t o f a l l p r e c e d i n g i n p u t s and "LOOK" s t a r t s the network l o o k i n g f o r a v a l i d s t r i n g a t t h e p o i n t where i t i s e n t e r e d . The o t h e r LOTUS programs s i m p l y s e r v e as s u b r o u t i n e s f o r t h e v a r i o u s programs t h a t g e t c o n s t r u c t e d . (*COMP (START (*AND RESET (•SETQ DUP •PASS) (•SETQ AHA (•PRINTC AHA!)))) (LOOK (*PUSHQ DUP (QUOTE GO) DUP •FAIL) ) (A (•AND RESET {•PUSHQ DUP (QUOTE ?A) DUP * FAIL) DUP) ) (B (•AND RESET (*PUSHQ DUP (QUOTE ?B) DUP *FAIL) DUP) ) (RESET =RES) (=RES {•AND (*SETQC RESET =RES) (•SETQ ?DUP (•PRINTC D U P L I C A T E ! i ! ) ) ) ) (GO (•AND {•PUSHQ ?DUP ?DUP (*POST ?DUP ?DUP) • F A I L ) ?DUP) ) LOTOS 2A THE LOTUS ENVIRONMENT ( c o n t ' d ) Page (?& ( * A N D ( * P U S H Q ? D U P (QUOTE a Ha) ? D U P * F A I L ) ( * P 0 S H Q ? D U P ( * P O S T ? D U P ?DUP) (QUOTE ? ? A ) * F A I L ) ) ) ( ? B ( * A N D ( * P U S H Q ? D U P (QUOTE AH A) ? D U P * F A I L ) ( * P U S H Q ? D U P ( * P 0 5 T ? D 0 P ? D U P ) (QUOTE ??B) * F A I L ) ) ) ( ? ? A {* AND ( * P U S H Q R E S E T ( * P O S T A a) R E S E T * F A I L ) ( * P U S H Q A A ?DOP * F A I L ) ) ) (??B ( * A N D ( * P 0 S H Q R E S E T ( * P O S T B B) R E S E T * F A I L ) ( * P U S H Q B B ? D U P * F A I L ) ) ) ) The s t r a t e g y e m p l o y e d i n t h i s n e t w o r k c a n b e s t be e x p o s e d by a c a r e f u l i n s p e c t i o n o f t h e p r o g r a m s "DUP" and "?DUP". The p r o g r a m DUP i s b u i l t up by t h e i n p u t s d u r i n g t h e s e s s i o n and r e p r e s e n t s t h e "memory" o f t h e i n p u t s t r e a m . When e x e c u t e d , DUP c o n s t r u c t s t h e p r o g r a m ?DUP, a - p r ocess whose i n t e n t i s t o l o o k f o r t h e a p p r o p r i a t e r e p e a t e d I n p u t s t r i n g and a n n o u n c e i t s p r e s e n c e . The p r o c e s s e s c o n s t r u c t e d on ?DUP a r e r e l e a s e d i n t o t h e n e t w o r k a f t e r e a c h I n p u t o f an A o r B, and p r o g r e s s t h r o u g h t h e n e t w o r k u n t i l t h e y d i e o f f o r s u c c e s s f u l l y t e r m i n a t e . Each s u c h p r o c e s s i n t h i s e x a m p l e p r i n t s "AHA!" when a d v a n c e d by t h e e x e c u t i o n o f an i n p u t s y m b o l i t was e x p e c t i n g , T h i s t e l l s t h e u s e r i f a n y t h i n g was " l i s t e n i n g " f o r e a c h i n p u t . The s u b r o u t i n e s a r e i n c l u d e d as s y m b o l s i n t h e p r o g r a m s b e i n g c o n s t r u c t e d t o make t h e p r e t t y p r i a t o u t p u t more r e a d a b l e . S i n c e t h e s e s u b r o u t i n e s a r e n o t s u b j e c t t o m o d i f i c a t i o n t h e y c a n be I n c o r p o r a t e d e i t h e r a s s y m b o l s o r a s LOTOS Paqe 2_;_ THE LOTUS ENIIEOSMENT (cont'd) their constituent code. Often, however, the "spare parts" are also being modified over time and the decision to use the value at the time of construction or at the time of execution must be considered. E a r l i e r in t h i s chapter (Section 2.3 A Simple Example) i t was pointed out that a LOTOS network does not even f a i n t l y resemble a conventional computer program. In f a c t , LOTOS i s not simply another programming language - LOTUS i s a new way of viewing an algorithm. If you l i k e , LOTOS i s a new way of thinking! The task of becoming comfortable in a t o t a l l y new domain d e f i n i t e l y requires a l o t of e f f o r t . Look at Appendix I I , "A LOTUS Green Card", and make sure i t adequately summarizes the information in Appendix I "A LOTUS Manual". Then, Green Card in hand, we w i l l take a closer look at t h i s example. The following sample dialogue with the system includes prettyprint displays of key portions of the network afte r several inputs have been executed. LOTUS 2JL THE LOTUS ENVIHONMENT (cont'd) Page 20 • {•TALK) *(•TERSE) •START •LOOK •A • B •A > AHA! • (•PP DUP) > DUP : ==> ?A > ==> 7B > ==> ?A > ==> GO > (QUOTE T) > (QUOTE NIL) > (QUOTE NIL) > (QUOTE NIL) > (QUOTE NIL) •(•PP A) > A : ==> ==> RESET > => (•PUSHQ DUP SS DUP •FAIL) > DUP > •FAIL > •FAIL > ==>. AHA > = > (•SETQ ?DUP SS) > ?"?B > (QUOTE NIL) > (QUOTE NIL) > (QUOTE NIL) •(•PP B) > B : ••-=> ~ > RESET > ==> {•PUSHQ DUP SS DUP •FAIL) > DUP > •FAIL > •FAIL > ==> AHA > (PRINT SS) > (QUOTE NIL) > (QUOTE NIL) •B > AHA! > DUPLICATE!!! Be g i n by c o n c e n t r a t i n g on DUP. Each o f A, B and LOOK push a "spare p a r t " onto DUP. For now, i g n o r e the f a c t t h a t A and B IQJOS Pag 2i THE LOTUS ENVIRONMENT (cont'd) also execute i t . The only other program that affects DUP i s START, which simply resets i t to *PASS. Program DUP then, i s the *AND of a l l the spare parts pushed onto i t since the l a s t START was executed. The prettyprint of DUP given in the dialogue confirms t h i s observation. Now, DUP i s executed from only two places i n the network, namely A and B, The f i r s t thing A and B do i s to execute RESET which, among other things, i n i t i a l i z e s the program ?DUP to announce "DUPLICATE!!!". Later we w i l l see that RESET does a l o t more, but at least ?DUP i s i n i t i a l i z e d before program DUP i s executed from A or B. Now consider what DOP does. Each of ?A and ?B impose an odd construction onto ?DUP. F i r s t , an AHA i s pushed onto ?DUP. Then ?DUP i s set to a form which w i l l (when executed) restore ?DUP to i t s present value and execute yet another spare part (a ??A or ??B) . This continues u n t i l a GO i s encountered on DUP. Each GO pushes a form onto ?DUP which causes ?DUP to restore i t s e l f after i t has executed and then simply executes i t . The restoration of ?DUP i s necessary because the GO need not be the la s t thing i n DUP (LOOK can be entered anywhere in the dialogue). Se have f i n a l l y reached the crux of the network! What does ?DUP do before i t resets i t s e l f ? Let us consider the s p e c i f i c case of the ?DUP LOTUS Page 22 2A THE LOTUS ENVIRONMENT (cont'd) constructed by the prettyprinted DUP i n the dialogue. A c e l l diagram for t h i s p a r t i c u l a r ?DUP i s given i n figur e 9. TBUP <*SETO TDUP -> ??A *FA I L AHA V 1FA IL (PRINT ' D U P L I C A T E ! ! ! ) Figure 9 - The Program ?DUP When the GO i s encountered and ?DUP i s executed, ?DUP w i l l f i r s t set i t s e l f back to the form constructed by the ?A and ?B. It w i l l then execute the spare part l e f t by the f i n a l ?A (namely ??A). This ??A pushes a form onto RESET which w i l l restore A and then pushes the new ?DUP onto A. rfhat has happened? A £rocess that w i l l look f o r consecutive inputs A B A (the repeat of the s t r i n g thus far) has been released into LOTUS Pag Zx. Ill LJ2JC2S ENVIRONMENT ( c o n t ' d ) t h e n e t w o r k . i t t h i s moment, t h e p r o c e s s c a n bs f o u n d on pr o g r a m A, w h i c h may be v e r i f i e d f r o m t h e p r e t t y p r i n t o f p r o g r a m A i n t h e d i a l o g u e . B u t t h e i n p u t o f e i t h e r a n A o r B w i l l e x e c u t e RESET, c a u s i n g t h e s y m b o l A t o be r e s t o r e d and t h e p r o c e s s t o be a n n i h i l a t e d . However, i f t h e i n p u t was an A, t h e p r o c e s s w i l l a l s o be e x e c u t e d , and w i l l d e p o s i t i t s e l f b a ck i n t h e n e t w o r k t o w a i t f o r t h e n e x t i n p u t ! Which b r i n g s us t o t h e e x p l a n a t i o n f o r t h e c o n f i g u r a t i o n o f p r o g r a m B i n c l u d e d i n t h e d i a l o g u e . The p r o c e s s r e l e a s e d by t h e f i r s t B i n t h e d i a l o g u e was l o o k i n g f o r c o n s e c u t i v e i n p u t s A B, and was t h u s d e p o s i t e d on p r o g r a m A. When t h e A was e n t e r e d , i t p r i n t e d "AHA!" and a d v a n c e d i t s e l f t o B where we see i t i n t h e d i a l o g u e , w a i t i n g t o a n n o u n c e t h e d u p l i c a t e s t r i n g . O n l y one m i n o r d e t a i l r e m a i n s ! A f t e r RESET h a s c l e a n e d a l l t h e dead p r o c e s s e s o u t o f t h e n e t w o r k i t r e - i n i t i a l i z e s i t s e l f i n p r e p a r a t i o n f o r t h e f o r t h c o m i n g a n n o u n c e m e n t s o f new p r o c e s s e s . A l t h o u g h t h e a b o v e d e t a i l e d d e s c r i p t i o n i s s p e c i f i c t o t h i s p a r t i c u l a r e x a m p l e , i t i l l u s t r a t e s t h e common LOTUS mechanism f o r h a n d l i n g c u r r e n t l y u n r e s o l v a b l e a l t e r n a t i v e s . T h i s n o t i o n o f p r o c e s s e s w i l l a p p e a r w i t h m i n o r v a r i a t i o n s i n most LOTUS n e t w o r k s , and i s w e l l w o r t h u n d e r s t a n d i n g a t t h e m i c r o - l e v e l . LOTUS Pag Is. TM LOIfiS ENZJSONMENT (cont'd) It should be realized that a l l processes are not necessarily se n s i t i v e to every symbol on the input channel. It i s even reasonable to define processes which operate deep in the network and are not d i r e c t l y sensitive to any input l e v e l symbols. There are those who i n s i s t that one can understand the forest without knowing anything- about a tree. In terms of that analogy, we have just finished a detailed study of some leaves and branches.' fit thi s l e v e l , LOTUS i s indeed l i k e "procedural tinker-toys". Shea we step back to view the tree, we see a dynamic network of programs capable of constructing and supporting executable fragments c a l l e d processes. These processes represent the conditional future intent of the network, and survive only while t h e i r conditions can s t i l l be rea l i z e d . Now i f we step back even further to look at the forest, the entire network can be viewed as a single self-modifying interpreter for a program received through i t s "ear", the *TA'LK function, whose purpose i s simply to present an i t e r a t i v e *DO of a l l past and future symbolic inputs to the network. Clearly then, the input symbols are not data to be processed - they are symbolic instructions i n an ongoing program which i s being executed. 3. A CONTEXT-FREE PARSER Page 3 i . l The P a r s i n g A l g o r i t h m The a l g o r i t h m used i n our p a r s e r i s d e r i v e d from Jay E a r l e y ' s d e s c r i p t i o n o f h i s g e n e r a l c o n t e x t - f r e e p a r s e r [ 3 ] . However, i t a l s o resembles t h e c o n v e n t i o n a l top-down d e p t h - f i r s t a l g o r i t h m d e s c r i b e d by F l o y d [ 5 ] and s h a r e s i t s d i f f i c u l t i e s w i t h l e f t r e c u r s i v e p r o d u c t i o n s ( i . e . X -> X A) . E a r l e y d e s c r i b e s h i s a l g o r i t h m i n terms of t h r e e o p e r a t i o n s ; a " p r e d i c t o r " , a " s c a n n e r " and a " c o m p l e t e r " which p r o c e s s s t a t e s e t s r e p r e s e n t i n g t h e p r e s e n t s t a t u s o f t h e p a r s e . I n t u i t i v e l y , the a l g o r i t h m can be viewed as mapping t h e elements of the i n p u t s t r i n g onto t h e p r o d u c t i o n s of the grammar and c o n s t r u c t i n g a n n o t a t e d s t r i n g s which i d e n t i f y t h o s e paths t h r o u g h the grammar which y i e l d s u c c e s s f u l p a r s e s . The t h r e e o p e r a t i o n s a r e d e s c r i b e d u s i n g a n o t a t i o n s i m i l a r t o t h a t i n t r o d u c e d by E a r l e y . The c u r r e n t p o s i t i o n i n the s t r i n g b e i n g p a r s e d i s marked by a " b a r " (3) which s t a r t s a t t h e b e g i n n i n g of t h e s t r i n g and i s moved through t h e s t r i n g a c c o r d i n g t o t h e p r e d i c t i n g , s c a n n i n g and c o m p l e t i n g o p e r a t i o n s . When t h e bar r e a c h e s the end of the s t r i n g , a s u c c e s s f u l parse has been d i s c o v e r e d . The o p e r a t i o n of the p a r s i n g a l g o r i t h m i s i l l u s t r a t e d w i t h the f o l l o w i n g example: Grammar: X -> a X -> b & CONTEXT-FREE PARSER ( c o n t ' d ) Page 26 S e n t e n c e : a a b The p a r s e b e g i n s by p l a c i n g t h e b a r a t t h e b e g i n n i n g o f t h e i n p u t s e n t e n c e (s) and e s t a b l i s h i n g t h e r o o t n ode o f t h e grammar ( i n t h i s c a s e X) a s t h e s i n g l e member o f t h e i n i t i a l s t a t e s e t (S) : s = 3) a a b S = a X The members of t h e s t a t e s e t a r e now p r o c e s s e d by t h e p r e d i c t o r , w h i c h i s d e f i n e d a s f o l l o w s : The p r e d i c t o r i s o n l y a p p l i c a b l e t o a member o f S when t h e s y m b o l t o t h e r i g h t o f t h e b a r i s a n o n - t e r m i n a l o f t h e grammar. When a p p l i e d , t h e p r e d i c t o r r e m o v e s t h e member f r o m S and a d d s new members f o r e a c h a l t e r n a t i v e o f t h e n o n - t e r m i n a l i n t h e grammar, The n o n - t e r m i n a l ( i n t h i s c a s e X) i s r e p l a c e d by t h e m a r k e r s :X f o l l o w e d by =X, and t h e b a r i s moved o v e r t h e :X. A new member i s now added t o S f o r e a c h a l t e r n a t i v e , w i t h t h e p r o d u c t i o n f o r t h e n o n - t e r m i n a l i n s e r t e d t o t h e r i g h t o f t h e b a r . The p r e d i c t o r i s t h e n a p p l i e d t o t h e s e new members o f t h e s t a t e s e t u n t i l a l l members have a t e r m i n a l t o t h e r i g h t o f t h e b a r . The s t r i n g r e m a i n s u n c h a n g e d . A p p l i e d t o t h e i n i t i a l member o f t h e s t a t e s e t i n o u r e x a m p l e , t h e p r e d i c t o r y i e l d s : s = S a a b S = :X 3 a X =X :X 3 b =x 1 LOTOS Is. A CONTEXT-FREE PARSER ( c o n t ' d ) Page The s c a n n i n g o p e r a t i o n i s now a p p l i e d t o e a c h member o f t h e s t a t e set.: The b a r i s moved o v e r t h e n e x t word i n t h e i n p u t s e n t e n c e s and e a c h member o f t h e s t a t e s e t i s p r o c e s s e d . I f t h e s y m b o l t o t h e r i g h t o f t h e b a r m a t c h e s t h a t j u s t s c a n n e d i n s, t h e b a r i s moved o v e r i t a s w e l l . I f t h e s y m b o l does n o t m a t c h , t h e member i s d e l e t e d f r o m t h e s t a t e s e t . I n o u r e x a m p l e t h e s c a n n e r y i e l d s : s = a a) a b S = :X a S X =X The c o m p l e t e r o p e r a t i o n i s now a p p l i e d t o e a c h member o f t h e s t a t e s e t : E a c h member o f t h e s t a t e s e t i s i n s p e c t e d f o r any m a r k e r s t o t h e r i g h t o f t h e b a r . I f a n y a r e e n c o u n t e r e d , t h e b a r i s moved o v e r them. I n o u r e x a m p l e t h e . c o m p l e t e r i s n o t a p p l i c a b l e and n o t h i n g i s c h a n g e d . The c y c l e o f p r e d i c t o r - s c a n n e r - c o m p l e t e r i s t h e n r e p e a t e d u n t i l e i t h e r t h e s t a t e s e t i s empty ( i n d i c a t i n g no p o s s i b l e p a r s e s ) o r t h e b a r i s a t t h e r i g h t m o s t end o f t h e i n p u t s e n t e n c e , i n w h i c h c a s e a l l r e m a i n i n g members o f S r e p r e s e n t s u c c e s s f u l p a r s e s . The e x a m p l e i s c o n t i n u e d : LOTUS 3a. A CONTEXT-FfiSE PASSER (cont'd) Page p r e d i c t o r : s = a a a b S = :X a :X 3 a X =X =X :X a :X a b =X =X scanner: s = a a a b S = :X a :x a a X =X =x c o m p l e t e r : no change p r e d i c t o r : s = a a a b S = :X a :X a :X 8 a X =X =X =X :X a :X a :X a b =X =X =X scanner: s = a a b a S = :X a :X a :X b 3 =X =X =X c o m p l e t e r : s = a a b 3 S = :X a :X a :X b =X =X =X 3 As e x p e c t e d , t h e sample i n p u t s e n t e n c e y i e l d s a s i n g l e p a r s e . The markers l e f t by the n o n - t e r m i n a l p r e d i c t o r s i n d i c a t e the b e g i n n i n g and end o f t h e s u c c e s s f u l a l t e r n a t i v e s f o r t h a t n o n - t e r m i n a l , and r e p r e s e n t t h e path t a k e n through t h e grammar. T h i s a l g o r i t h m d i f f e r s from E a r l e y ' s i n t h a t i t does not p r o v i d e f o r l o o k - a h e a d i n the s t r i n g b e i n g p a r s e d , and does not combine s i m i l a r s u b - p a r s e s (which would a l s o s o l v e t h e l e f t r e c u r s i o n problem). However, i t does r e t a i n 'the n o - b a c k t r a c k f e a t u r e which d i s t i n g u i s h e s i t from the c o n v e n t i o n a l top-down d e p t h - f i r s t a l g o r i t h m mentioned e a r l i e r . Page 3i A CONTEXT-FREE PARSER (cont'd) 3±2 The LOTUS Parser The implementation of t h i s parsing algorithm in LOTUS i s now described. The state set i s represented by that portion of the LOTUS network corresponding to the terminal symbols i n the grammar. The predictors (in the case of non-terminals) and the scanners (in the case of terminals) are LOTUS fragments named by their corresponding symbol preceded by a "?". The members of the state set are LOTUS processes which are constructed such that the predictor, scanner and completer operations are performed automatically by the input symbols themselves as they are executed. A situation i s thereby achieved wherein an input sentence i s r e a l l y a LOTUS program which, when executed, parses i t s e l f . Each member of the state set i s a LOTUS process consisting of two LOTUS programs. Everything to the l e f t of the bar marker i s carr i e d on *REDN, which w i l l contain a f u l l parse upon successful completion of the algorithm. Everything to the right of the bar i s contained i n *BETA, and represents what to do next at the current stage of the parse. *BETA i s i n i t i a l i z e d to execute *REDN, so the parse w i l l be executed whenever an acceptable string has been encountered. LOTOS Page 3 0 Ii. A CONTEXT-FSEE PAROUS ( c o n t ' d ) The same e x a m p l e t h a t was u s e d t o i l l u s t r a t e t h e a l g o r i t h m i s now u s e d t o i n t r o d u c e t h e i m p l e m e n t a t i o n o f t h e p a r s e r . The p r e d i c t o r f o r t h e o n l y n o n - t e r m i n a l , X, i s d e f i n e d a s f o l l o w s : (*SETQC ?X . (# AND *S AVR.E.DN . ' . {•PUSHQ *REDN *EEDN :X * F A I L ) (•PTJSHQ *BETA ' (*PUSHQ *REDN *REDN = X * F A I L ) •BETA • F A I L ) X *STAK) ) The LOTUS p r o g r a m X c a u s e s t h e a l t e r n a t e p r o d u c t i o n s f o r t h e n o n - t e r m i n a l X t o be p l a c e d on *BETA: (•SSTQC X (*AND •S AVBET.A {•PUSHQ *BETA (*PQST *BETA •BETA) ?X * F A I L ) (*PUSHQ *BETA (*P0ST •BETA *BETA) ?A • F A I L ) • BETA •STAK •SAVBETA (•PUSHQ *BETA ( * P 0 S T • BETA • BETA) ?B *.FAIL) • BETA •STAK)) The f r a g m e n t s *SAVBETA, •SAVREDN and •STAR a r e i n v o l v e d i n t e m p o r a r i l y s a v i n g and r e s t o r i n g •BETA and *REDN, and a r e shown l a t e r . I t s h o u l d be o b s e r v e d t h a t t h e p r e d i c t o r ?X p l a c e s t h e a p p r o p r i a t e c o m p l e t e r on *BETA, t o be e x e c u t e d a f t e r t h e p r o d u c t i o n h a s b e e n i d e n t i f i e d i n t h e i n p u t s e n t e n c e . The p r o g r a m s ?A and ?B a r e t h e s c a n n e r s f o r t h e t e r m i n a l s y m b o l s i n t h e grammar, a n d s i m p l y a s s e m b l e t h e LOTOS Page i i . A CONTEXT-FREE PARSER (cont'd) processes and deposit them on the appropriate symbols i n the network: (*SETQC ?A (•AND •SAVREDN (•PUSHQ • REDN • REDN : A •FAIL) (•POSHQ •REDN •REDN =A •FAIL) (•POSHQ •BETA (•POST •REDN •REDN) •BETA •FAIL) (•POSHQ •RESET (•POST A A) •RESET •FAIL) (•POSHQ A A •BETA •FAIL) •STAK) ) (•SETQC ?B (•AND •SAVREDN (•POSHQ •REDN •REDN :B •FAIL) (•PUSHQ •REDN •REDN =B •FAIL) (•PUSHQ •BETA (•POST •REDN •REDN) •BETA •FAIL) (•POSHQ •BESET (•POST B B) •RESET •FAIL) (•PUSHQ B B •BETA •FAIL) • STAK) ) These scanners i n e f f e c t move the bar over the terminal symbol in the surviving members of the state set and deposit each member on that symbol in the network. The bar i s then "moved over" the symbol i n the input sentence when the next input symbol i s executed and the appropriate processes are advanced. The remainder of the network i s now shown. The ":" and "=" markers are i n i t i a l i z e d to simply announce their presence when •REDN i s executed. (•SETQC •RESET ••RESET) (•SETQC ••RESET {•SETQC •RESET ••RESET)) (•SETQC •STAK •PASS) {•SETQC A •RESET) (•SETQC B •RESET) (•SETQC •SAVBETA (•POSHQ •STAK {•POST •BETA •BETA) (•POST •STAK •STAK) • FAIL) ) L O T O S i i A CONTEXT-FREE PARSER (cont'd) Page 32 (•SETQC *S AVREDN (•PUSHQ •STAK (*POST *KEDN •REDN) (*POST •STAK •STAK) •FAIL) ) (*SETQ :X (•PRINTC LOOKING-FOR-AN-X)) (•SETQ =X (•PRINTC FOOND-AN-X)) (•SETQ :A (•PRINTC LOOKING-FOR-AN-A)) (•SETQ =A (•PRINTC FOUND-AN-A) ) (•SETQ :B (•PRINTC LOOKING-FOR-A-B) ) (•SETQ =B (•PRINTC FOUND-A-B)) F i n a l l y , we need a new •TALK f u n c t i o n which w i l l i n i t i a l i z e *BETA and *REDN on e v e r y c y c l e : (DEFON •TALK () (PROG () LOOP (•SETQC •BETA • REDN) (*SETQ •REDN (•PRINTC PARSE:)) (•EVAL (READ) ) (GO LOOP) ) ) The f o l l o w i n g sample run shows t h i s network p a r s i n g f o r an X w i t h our sample sentence "a a b". •(*TALK) •?X • A •A *B > PARSE: > LOOKING-FOR- AN -X > LOOKING—F0 R-AN -A > FOUND-AN-A > LCOKING-FOR- AN -X > LOOKING-FOR- AN -A > FOUND-AN-A > LQOKING-FOR- AN -X > LOOKING—FOR- A- E > FOUND-A-B > FOUND-AN-X > FOUND-AN-X > FOUND-AN-X LOTOS i i 1 £2I2I12zfiIl I M i l i (cont'd) Page appendix IV contains a set of LISP primitives which w i l l generate a LOTOS parser similar to the one we have just seen from a description of a context-free grammar. The generated parser, however, constructs a program on *HEDN which prints a conventional indented tree to display the structure of the parse, A simple grammar for noun phrases i s used to generate a parser which i s then used to parse some sample phrases. The system mentioned i n the Introduction which uses a LOTOS parser to i d e n t i f y noun phrases lettered on a graphics screen [ 6 ] represents a working example of a reasonably large LOTOS system. In t h i s system, a sentence to be parsed consists of the sequence of unit vectors returned by the l i g h t pen or tablet routines of the graphics processor. The grammar i s organized in several l e v e l s with the unit vectors yieldi n g strokes, l e t t e r s , words, parts of speech and f i n a l l y the noun phrase, although a h e u r i s t i c i s used to f i l t e r spurious vectors generated by the graphics hardware, the grammar i s extremely ambiguous to allow for poorly formed strokes and multiple methods of forming l e t t e r s . i n spite of t h i s ambiguity, the system parses i n roughly real time on the time-shared IBM 370-168 at U.B.C. I J I K T H E E O B S E R V A T I O N S L O T U S Page The research reported here was undertaken to gain p r a c t i c a l experience i n a procedural programming domain. The expected result was a clearer understanding of the nature and c a p a b i l i t i e s of such a domain, This insight was expected to manifest i t s e l f i n the d e f i n i t i o n of appropriate design and implementation strategies. These strategies have developed from the necessity (or opportunity) to store procedural fragments rather than syntactic structures for l a t e r use. A reasonable method of deciding what to store i s to ask what you would eventually do with a syntactic structure i f you could save one, construct a procedure to do that,- and store i t where i t w i l l be encountered at the appropriate time. The i n c l i n a t i o n to employ conventional function c a l l s on syntactic arguments which contain embedded elements of control structure i s not desirable because i t forces the eventual execution of the procedure out of the LOTUS environment into a single-purpose user created domain. This renders the rest of the LOTUS network temporarily inaccessible while the procedure i s executed. If the procedural fragment i s synthesised using the LOTUS primitives i t can be integrated into the network, thereby maintaining the global environment. LOTUS Page 35 iU OBSERVATIONS (cont'd) It i s often the case that there are so many potential uses of a current fragment that one hesitates to construct them a l l . In t h i s s i t u a t i o n one simply saves what already exists along with the procedures that would have been used to construct the desired fragments. Later, when the s p e c i f i c use becomes apparent, only the e s s e n t i a l fragment i s constructed and executed. This strategy i s a s p e c i f i c instance of a much more general model for LOTUS programs - If you can't decide now, construct a program that w i l l decide l a t e r . In e f f e c t , our context-free parser i s "deciding now" when i t tours through i t s predictors and scanners leaving processes on the terminal symbols i n the network. This a c t i v i t y amounts to creating expectation in the network, and enables the network to respond quickly to each word on the input channel. The application of a "decide l a t e r " strategy to the parser creates a situation i n which the network accommodates an input word afte r i t has been encountered on the channel. This i s nothing more than the incorporation of T-level look-ahead i n the parsing algorithm. The price of "deciding l a t e r " i s that the network does not have an established expectation f o r the l i k e l y events, and i t i s obliged to react (i.e. decide later) after each event occurs. The o f f s e t t i n g advantage i s the obvious elimination of the unnecessary e f f o r t involved i n LOTUS Page iU fllTHER O B S E R V 1 I I 2 1 S (cont'd) creating expectation for those events that do not materialize. Perhaps the single LOTUS strategy which i s most d i f f i c u l t to adopt i s that of actually depositing a process i n the network, and simply continuing on. In languages such as MICRO-PLANNER the e f f e c t of the success or f a i l u r e of the current goal i s contained in the system's recursive stack, leaving no alternative to a top down exhaustive search at each step. However, a LOTUS process which represents what to do next i f a goal i s achieved can be deposited on the recognizer for the goal with absolute certainty that the eventual achievement of the goal w i l l cause the process to be resumed. If the LOTUS parser described i n Chapter 3 i s viewed i n th i s context, *BETA and *REDN take on somewhat altered roles: *BETA represents what to do next i n order to achieve the top l e v e l goal of a successful parse, and *REDN represents what to do when the top l e v e l goal i s f i n a l l y achieved (i.e. announce the parse). The examples used to i l l u s t r a t e the LOTUS language are perhaps preoccupied with transient processes designed to deal with input symbols from an input channel. This i s the case because the reguirements for handling the unpredictable nature of an input channel seemed most d i f f i c u l t to r e a l i z e . LOTOS Page ISSSHER OBSERVATIONS (cont'd) However, the need for more permanent storage of concepts and higher l e v e l procedures cannot be overlooked. When a concept (for our purposes, a l o g i c a l l y related sub-network) exists i n a LOTOS network, i t i s necessarily by virtue of the current bindings of certain LOTOS symbols. The i d e n t i f i c a t i o n of the concept amounts to i d e n t i f y i n g those symbols which constitute the concept. F i n a l l y , the storage of the concept i s accomplished by preserving the bindings of the constituent symbols for l a t e r use. An approach which seems to hold promise involves the use of foreground registers i n the network as work areas for the manipulation of concepts. Once the notion of such registers i s introduced, two new LOTOS primitives are reguired to operate through the re g i s t e r s on the bindings of the foregrounded symbols. The reguired primitives are *SET and *POSH which modify the binding of the symbol bound to the subject, d i f f e r i n g from *5ETQ and *PUSHQ in the same way that LISP's SET d i f f e r s from SETQ. The fragments constituting a concept may now be manipulated as well as executed through the foreground r e g i s t e r s . For example, the concept "ROVER" may be current i n the network because of the register bindings: LOTUS i i i 1112111 OBSERVATIONS (cont'd) Page NAME: ROVER SIZE: BIG COLOUR: BLACK GENERIC: DOG The i d e n t i f i c a t i o n of the concept may be constructed on a register such as STORE: (*AND (*SET NAME (*POST STORE STORE) ) ( * P 0 S H NAME (*POST NAME NAME) NAME *FAIL) (*PUSH NAME (*POST SIZE SIZE) NAME *FAIL) (*PUSH NAME (*POST COLOUR COLOUR) NAME *fAIL) (*PUSH NAME (*POST GENERIC GENERIC) NAME *FAIL)) When STORE i s executed, the regis t e r bindings pertinent to the current concept including the binding of STORE i t s e l f are compressed onto the name of the concept, i n t h i s case "ROVER". Later, when ROVER i s again invoked, these bindings are foregrounded to be executed or modified and restored. This strategy i s not intended as a paradigm for the manipulation of semantic concepts i n LOTUS, but as a general approach which seems to have some merit. In order to be implementable, It must acknowledge the fact that the bindings of the registers are not simply LOTUS symbols, but are r e a l l y more concepts which must be foregrounded in turn before they can be u t i l i z e d by the network, whether or not the r e g i s t e r s themselves are also concepts i s not immediately clear. In any case the approach does provide an at t r a c t i v e semantic context mechanism, i n that the binding of each register i s modified by LOTUS Page 39 i i I2STHEH OBSERVATIONS (cont'd) the bindings of the other registers. For instance, the meaning of "BIG" i n the above example i s cer t a i n l y constrained by the fact that the current concept i s a generic "DOG". I t also seems clear that the structure of such r e g i s t e r s at a l i n g u i s t i c interface could be modelled after the case structures proposed by Fillmore [4]. At a deeper l e v e l , a similar register set could possibly be used to implement the psychological modelling concept of short term memory. A l l the examples of LOTUS processes that we have examined in d e t a i l involve what could be c a l l e d independent processes, in that they are not affected by the progress of other processes in the network. At least two other types of dependent processes appear to e x i s t ; competing processes and cooperating processes. Competing processes are found i n theorem proving situations where a proof of any alternative at an "or" branch i n the proof tree makes i t unnecessary to pursue the other alternatives,and i n some graph traversing situations where the discovery of any path i s s u f f i c i e n t to abandon the search. Cooperating processes are characterized by the requirement for synchronization within groups of interacting processes such that one process executes independently u n t i l i t must wait for some other process to achieve a s p e c i f i c state before i t can proceed. An example of LOTUS OBSERVATIONS (cont'd) Page such a requirement i s the processing of "and" nodes by a theorem proving system. Co-routine structures are sometimes employed in languages where t h i s type of synchronization i s required. Both types of dependent processes w i l l need a more sophisticated communication mechanism than has been developed so far. Since each dependency appears to be associated with an i d e n t i f i a b l e sub-goal or state or event, i t seems appropriate to associate a LOTUS program with each such object which w i l l keep track of i t s current status. Any process which i s dependent on such an object need only execute the object to foreground i t s current status, and any process which affects the status of one of these objects would be constructed to establish appropriate status bindings on the object. Since the present set of primitives operate only on the bindings of LOTUS symbols, t h i s reguires each synchronization object to be e x p l i c i t l y named, plus a method of purging the symbol from the network after i t has served i t s purpose. It should be clear that independent processes such as those found i n our parser should r e a l l y be executing i n p a r a l l e l . They are stored and executed i n sequence only LOTOS Page I i IM ISER OBSERVATIONS (cont'd) because of the l i m i t s imposed by the host environment. It i s also the case that dependent processes could execute i n p a r a l l e l within the synchronization constraints already described. since the use of processes appears basic to the implementation of many algorithms in LOTUS, i t should be possible to take advantage of the potential parallelism i n a "LOTOS machine". I f the if-t h e n - e l s e c e l l s were stored i n an executable memory where each addressable word embodied the if-then-else l o g i c element, the execution of these c e l l s could be accomplished i n a distributed environment, at the memory cycle time. Because the execution path of a LOTUS program i s a binary tree, t h i s represents approximately half of the t o t a l number of inst r u c t i o n s executed by a l l LOTUS programs. The structure of thi s memory or of processors to perform the other necessary functions such as the manipulation of the contents of the executable memory, the resolution of LOTUS symbols, and the execution of *PASS and *FAI.L i s far beyond the scope of this thesis. 5. CONCLUSIONS Page 42 The LOTUS programming formalism has provided considerable insight into the c h a r a c t e r i s t i c s of a procedural domain. Although LOTUS i s d e f i n i t e l y not a high-level language i n the usual sense, i t i s possible to implement concise statements of algorithms which are normally Implemented exclusively in high-level languages. The design strategies that appear to be e f f e c t i v e i n the LOTUS environment are unconventional at f i r s t exposure, but one could hardly expect conventional strategies to be appropriate i n such a r e s t r i c t e d domain. The techniques f o r manipulating procedural fragments are egually uncomfortable for the same basic reasons. The unconventional nature of the domain at every l e v e l presents an i n i t i a l conceptual d i f f i c u l t y f o r many people. However, the experience with LOTUS has given no reason to suspect that such a domain has any inherent computational weakness. Quite to the contrary, some d i f f i c u l t problems have surprisingly straightforward Implementations. The results achieved through t h i s research have barely scratched the surface of the potential for such a language. There remains much room for improvement in the d e f i n i t i o n of primitives and innumerable strategies are waiting to be 5i CONCLUSIONS (cont'd) Page 43 discovered. I firmly believe that much can be learned about the basic nature of algorithms through further research i n procedural domains, LOTUS 1IBLJ06BAPHY Page [ 1 ] Bohm, C. £ J a c o p i n i , G, "Flow Diagrams, T u r i n g Machines and Languages With Only Two F o r m a t i o n R u l e s " , CACM. V o l 9, No 5, May 1966. [ 2 ] C h a r n i a k , B. Toward a Model o f Chila-reni-s Story. Comprehension. MIT A l Lab T e c h n i c a l Report 266, 1972. [ 3 ] E a r l e y , Jay. "An E f f i c i e n t C o n t e x t - F r e e P a r s i n g A l g o r i t h m " , CACM, V o l 13, No 2, Feb 1970. [ 4 ] F i l l m o r e , C h a r l e s . "The Case f o r CASE", i n U n i v e r s a l s i f l L i a a n i s t i c Theory. e d i t e d by Bach S HarmsT New York: H o l t , B i n e h a r t & Winston, 1968. [5] F l o y d , Robert W. "The Syntax o f Programming Languages -a Survey", IEEE. T r a n s . , EC13, No 4, Aug 1964. [ 6 ] F o w l e r , J . & McDonald, D. " C h a r a c t e r R e c o g n i t i o n i n a P r o c e d u r a l Environment", u n p u b l i s h e d r e p o r t , U n i v e r s i t y of B.C., Dept o f Computer S c i e n c e , A p r i l 1975. [ 7 ] G o l d s t e i n , I . P. U n d e r s t a n d i n g Simple P i c t u r e EEoasams. MIT A l Lab T e c h n i c a l Report 294, 1974. [ 8 ] G r e i f , I . & H e w i t t , C. " A c t o r Semantics o f PLANNER-73", MIT AI Lab Working Paper 81. [ 9 ] Havens, W i l l i a m . p e r s o n a l communication, U n i v e r s i t y o f B. C., 1974. [ 1 0 ] H e w i t t , c , B i s h o p , P. S S t e i g e r , R. "A U n i v e r s a l Modular A c t o r Formalism f o r A r t i f i c i a l I n t e l l i g e n c e " , I J C A I - 7 3 , S t a n f o r d , C a l i f . , Aug 1973. LOTOS BIBLIOGRAPHY (cont'd) P a g [11] McDer.mott, D. V. Assimilation of Maw Information by a IsL£ura.l l^I13S§.9.Sz]IIl^S£standing System. MIT Al Lab Technical Report 291, 1974. [12] McDermott, D. V. S Sussman, G. J . The CQNNIVER iL§f§£§.££§ Manual. MIT Al Lab Memo 259, 1973. [13] Minsky, M. A Framework for RQ£resentina Knowledge. MIT Al Lab Memo 306"7~Nov 1973~(rev7 June ?974)7 [14] Quam, Lynn H. & D i f f i e , W h i t f i e l d . Stanford LISP 1..6 Manual. Stanford AT Lab Operating Note 28.7, 1969. [15] Reiter, Ray. personal communication, University of B. C , 1974. [16] Rosenkrantz, Daniel J. "Programmed Grammars and Classes of Formal Languages", JACM., Vol 16, No 1, Jan 1969. [17] Smith, B. & Hewitt, C. "Towards a Programming Apprentice", AISB Summer Conference, University of Sussex, July 1974. [18] Sussman, G. J. A Computational Model of S k i l l Acquisition. MIT Al Lab Technical Report 297, 1973. [19] Sussman, G. J., Winograd, T. & Charniak, E. MICRO-PLANNER Reference Manual. MIT Al Lab Memo 203A, 1971. [20] Wilcox, B. & Hafner, C. LISP/MTS Users Guide. Ann Arbor, Mich., Mental Health Research I n s t i t u t e , 1973. [21] Winograd, T. P£0£S^2£®s as a Representation for Data i n §. Computer Program for Understand-ing, Nat ureal Lanc[ua5e7 ~MIT Al Lab Technical Report 84, 1971. APPENDIX I A LOTUS~Manual Page The complete LOTUS implementation (MTS-LISP version) i s given i n Appendix I I I . A one-page summary of t h i s manual i s included as Appendix I I , "A LOTUS Green Card". The description of the LOTUS language presented here i s organized in f i v e sections: 1. The LOTUS Interpreter 2. The LOTUS Prettyprinter 3. The LOTUS Compiler 4. LOTUS Language Primitives 5. LOTUS Debugging F a c i l i t i e s The B-N-F syntax for LOTUS programs i s as follows: PGM > (PGM PGM PGM) the (if-then-else) t r i p l e > SYMBOL a LOTUS "atom" > PRIMITIVE a LISP s-expression From th i s point on, the (if-then-else) t r i p l e w i l l also be referred to as a (TEST PASS FAIL) t r i p l e , and the in d i v i d u a l elements w i l l be i d e n t i f i e d as the TEST, PASS and FAIL forms respectively. APPENDIX I A LOTUS Manual Page Is. The LOIII3. intergreter This section describes enough LOTUS "internals' 1 to provide a LISP programmer with an overview of the code i n Appendix I I I . A LOTUS program i s associated with i t s LOTUS symbol through the property "LOTUS" on the corresponding LISP atom. A LOTUS t r i p l e (for example (A B C)) i s stored as an e x p l i c i t c a l l to the interpreter on the three elements' of the t r i p l e (i.e. (LOTUS A B . C)). The l a s t two elements of the t r i p l e are stored as a dotted pair to conserve the extra CONS c e l l . The function "LOTUS" i s the heart of the interpreter, the r e a l i z a t i o n of the if-then-else control structure: (DEFUN LOTUS FEXPR (T-P-F) (COND ( (*EVAL (CAS T-P-F) ) (*EVAL (CADE T-P-F) ) ) ((*EVAL (CDDR T-P-F))))) The function *EVAL simply transfers control through LOTUS symbols to their executable values. Any LISP s-expression presented to *EVAL i s simply EVAL'd. Anything other than a c a l l to "LOTUS" Is presumed to be a language primitive, whose success or f a i l u r e value i s determined by the non-NIL or NIL value returned: APPENDIX I A LOTUS~Manual Page {DEFUN *EV AL EXPR (PGM) (COND ( (ATOM PGM) (*EVAL (GET PGM (QUOTE LOTUS))}) ((EVAL PGM)))) An NEXPR e n t r y t o t h e i n t e r p r e t e r , *INT i s p r o v i d e d f o r use d i r e c t l y f r o m L I S P : (DEFUN *INT NEXPR (PGM) (COND ( (*EVAL PGM) (QUOTE PASS)) ((QUOTE F A I L ) ) ) ) However, t o p - l e v e l LOTUS i s n o r m a l l y r e a c h e d f r o m L I S P by i n v o k i n g a f u n c t i o n s u c h a s *TALK: (DEFUN *TALK EXPR {) (PROG {) LOOP ( * E V & L (READ)) (GO LOOP))) The r e m a i n d e r o f t h e LOTUS i n t e r p r e t e r i s c o n c e r n e d w i t h a n c i l l a r y m a t t e r s , s u c h a s r e c o v e r y f r o m u n d e f i n e d s y m b o l s a nd t h e #TRACE f a c i l i t y , w h i c h i s d e s c r i b e d l a t e r . APPENDIX I A LOTUS Manual Pag 2^ The LOTUS Prettyjarinter The LOTUS prettyprinter i s an attempt to capture and display the physical structure, and hence the l o g i c a l structure of a LOTUS program. A method of presenting the physical program structure i s es s e n t i a l , since the various language primitives approach l o g i c a l program composition by physically manipulating fragments. The prettyprinter i s invoked on a LOTUS symbol by (* P RE TT Y P RIN T SYMBOL) or simply (*PP SYMBOL). The output of the prettyprinter i s read v e r t i c a l l y , with horizontal indentation i n d i c a t i n g nesting of LOTUS t r i p l e s . For example, the LOTUS symbol PGM bound to the program (A (B C D) E) would print as: *,(*PP PGM) > PGM : ==> A > = = > B > C > D > E The prettyprinter output maps d i r e c t l y onto the LOTUS B-N-F syntax. Each occurrence of the (PGM PGM PGM) production i s marked by the appearance of the indicator which points to the f i r s t (TEST) element of the t r i p l e . The other I Page 50 A LOTUS Manual two elements of the t r i p l e appear d i r e c t l y below the f i r s t , i n the same v e r t i c a l column. LOTUS symbols and language primitives constitute the leaves of a LOTUS program, and are displayed where they are encountered. An option exists to compress the prettyprinter output where lengthy language primitives (LISP expressions) obscure the displayed structure. Entering (*TERSE) causes further output to be compressed u n t i l another (*TER5E) i s entered. The *TERSE option also compresses output from the *TRACE f a c i l i t y , one of the debugging tools described l a t e r . APPENDIX I A LOTUS Manual Page 3^ The LOTUS Compiler The compiler consists of the two LISP functions *C0MP and *SETQC, plus several compiler extensions which generate commonly used l o g i c a l structures. Both compiler functions accept the LOTUS B-N-F syntax, as follows: (*C0MP (SYMBOL PGM) (SYMBOL PGM) . . .) -returns the atom "READY". (*SETQC SYMBOL PGM) -returns the pgm generated. The p o s s i b i l i t y of confusion exists between the (PGM PGM PGM) production and the PRIMITIVE (LISP s-expression) production when the TEST form i s both a LOTUS symbol and the name of a LISP function. The compiler presumes the expression i s a LOTUS t r i p l e i f the f i r s t element i s a defined LOTUS symbol or i s not currently the name of a LISP function. I t i s assumed to be a LISP expression only i f the f i r s t element i s not presently a LOTUS symbol and i s the name of a LISP function. In any case, prefixing the form with M*LISP" or simply "*L" forces i t to be treated as a LISP expression. A LOTOS Manual Page The c o m p i l e r e x t e n s i o n s r e p r e s e n t a d d i t i o n a l p r o d u c t i o n s t o the B-N-F s y n t a x , a c c e p t a b l e o n l y t o the c o m p i l e r f u n c t i o n s : PGM -— > (*NOT PGM) > (*AND PGM PGM . . .) . — > (*QR PGM PGM . • •) - — > (*DG PGM PGM . • •) The s t r u c t u r e s generated by t h e e x t e n s i o n s make use o f The above programs s h o u l d be i n s p e c t e d t o v e r i f y t h a t succeed and f a i l r e s p e c t i v e l y , *(*C0MP (NOT (*N0T A)) * (AND (* A N D A B C ) ) * (OR (*0R A B C ) ) * (DO (*D0 A B C) ) ) READY *(*PP NOT) > NOT : = = > A > *FAIL > *PASS *(*PP AND) > AND : ==> A > = = > B > C > *FAIL > *FAIL *(*PP OR) > OR : ==> A > *PASS > == > B > *PASS > C APPENDIX I A LOTUS Manual Page 53 *(*PP DO) > DO : ==> A > ==> B > C > C > ==> SAME AS PASS FOBH (ABOVE) The above programs should be inspected to ve r i f y that they do indeed represent appropriate l o g i c a l structures. Particular attention should be given the "DO" construction, as i t i l l u s t r a t e s an inter e s t i n g characteristic of the prettyprinter. When i d e n t i c a l (not simply l o g i c a l l y eguivalent, but physically identical) PASS and FAIL forms are encountered, only the PASS form i s expanded. This i s done purely to physically shorten the prettyprinter display of a "DO" structure. APPJNDIX I A LOTOS Manual Page 54 i i i LOTOS Language P r i m i t i v e s The LOTUS language p r i m i t i v e s e n a b l e a LOTUS network t o op e r a t e on i t s e l f . LOTUS p r i m i t i v e s come i n two f l a v o u r s ; t h o s e which b i n d symbols t o programs, and those which r e t u r n programs. Most o f the p r i m i t i v e s e x t r a c t t h e c u r r e n t v a l u e s (LOTUS v a l u e of a SYMBOL o r v a l u e r e t u r n e d by a PRIMITIVE) o f t h e i r operands when c o n s t r u c t i n g new programs. Where t h i s i s the c a s e , t h e operand i s denoted by "FORM". Thus FORM r e p r e s e n t s a SYMBOL o r a PRIMITIVE e x p r e s s i o n i n the s y n t a x o f the language p r i m i t i v e , and i n d i c a t e s t h a t the c u r r e n t v a l u e of FORM i s used by th e p r i m i t i v e . The examples of each p r i m i t i v e use t h e programs A B and C which were e s t a b l i s h e d by: * (*CGHP (A PGHA) * (B PGMB) * (C PGMC) ) READY *(*PP A) > A : PGMA * (*PP B) > B : PGMB *(*PP C) > C : PGMC APPENDIX I A LOTUS Manual Page 55 Primitives which bind programs to symbols: (*SETQ SYMBOL FORM) -binds SYMBOL to FGBM. -returns new value of SYMBOL, -example: *{*SETQ X A) * (*PP X) > X : PGMA (*PUSHQ SYMBOL FORM FORM FORM) -binds SYMBOL to the t r i p l e (FORM FORM FORM), -returns new value of SYMBOL, -example: *(*PUSHQ X A B C) * (*PP X) > X : ==> PGMA > PGMB > PGMC (*SETQC SYMBOL PGM) -uses compiler syntax for PGM. -binds SYMBOL to the compiled PGM. -returns new value of SYMBOL, -example: * (*SETQC X A) * (*PP X) > X : A APPENDIX I A LOTOS Manual Page primitives which ret urn programs: (*CQNS FORM FORM FORM) -returns the t r i p l e (FORM FORM FORM). -example: *(*SETQ X (*CONS A B C) ) * (*PP X) > X : ==> PGMA > PGMB > PGMC (*POST SYMBOL FORM) -returns a pgm which w i l l bind the present value of FORM to SYMBOL, -example: *(*SETQ X (*POST Z A)) *X *(*PP Z) > Z : PGMA (*.PRINT FORM) -returns a pgm which w i l l print FORM (which normally yields a SYMBOL), -example: * (*SSTQ X (*PRINT A)) *X > PGMA (•PRINTC PGM) -uses compiler syntax for PGM. -returns a pgm which w i l l print PGM (normally a SYMBOL) . -example; *{*SETQ X (*PRINTC A)) *X > A These functions constitute the supported base of LOTOS language primitives, and provide s u f f i c i e n t power and . f l e x i b i l i t y to handle most si t u a t i o n s encountered so f a r . However, the LISP implementation of LOTOS allows new primitives to be established e a s i l y , as convenience dictates. A LOTUS Manual Page 5-. LOTUS D e b u s i n g F a c i l i t i e s The LOTUS debugging package c o n s i s t s o f an i n t e r a c t i v e program t r a c i n g f a c i l i t y , a LOTUS program e d i t o r and an e x e c u t i o n break h a n d l i n g routine-. The t r a c e f a c i l i t y i s i n v o k e d by e n t e r i n g (*TRACE SYMBOL SYMBOL . . .) and i s t u r n e d o f f by (•UNTHACE SYMBOL SYMBOL . . . ) . Each t i m e a t r a c e d symbol i s encountered by t h e i n t e r p r e t e r , d e t a i l s o f i t s e x e c u t i o n are p r e s e n t e d t o t h e u s e r . As each LOTUS t r i p l e i s e n t e r e d , i t i s d i s p l a y e d f o r i n s p e c t i o n . I f t h e *TERS£ o p t i o n i s i n e f f e c t (the recommended mode) the expansion of t r i p l e s i s t e r m i n a t e d a t the top l e v e l . When a l e a f (a SYMBOL o r a PRIMITIVE) i s f i n a l l y r e a c h e d , i t i s d i s p l a y e d and i t s PASS o r FAIL v a l u e i s p r i n t e d below i t . The t r a c e then c o n t i n u e s through the a p p r o p r i a t e PASS or FAIL form of the t r i p l e , and the r e s u l t i n g v a l u e o f the t r i p l e i s d i s p l a y e d i n i t s t u r n . T h i s goes on u n t i l t he e n t i r e program has been e x e c u t e d and an o v e r a l l PASS or FAIL v a l u e has been reached. APPENDIX I A LOTOS Manual Page 58 An example w i l l c l a r i f y m a t t e r s * (*TA1K) •{•COMP (X {•AND A B C D) ) * (A * (B * (C •PASS) •PASS) • (D •{•PP X) > X : ==> > > > > > > {•NOT B) ) •PASS) ) A == > B C D •FAIL •FAIL •FAIL •(•TRACE X) • (•TERSE) •X > ENTERING X : > (A ! &S ! •FAIL) > 1. T A > 1. T <==PASS > 1. P (B ! && ! •FAIL) > 2. T B > 2. T <==PASS > 2, P (C I D ! •FAIL) > 3. T C > 3. T <==FAIL > 3. F • F A I L > 3. F <=-=FAIL > 2. P <==FAIL > 1. P <==.FAIL > <== FAIL SETOHNED FROM T h i s t r a c e shows how program X (the •AND of programs A, B, c and D) f a i l s b e c a u s e program C f a i l s . E a c h l i n e i n t h e t r a c e b e g i n s w i t h a number which d e n o t e s t h e n e s t e d d e p t h o f t h e e l e m e n t d i s p l a y e d on t h a t l i n e , and a T, P or F i n d i c a t i n g t h a t i t i s a TEST, PASS o r FAIL f o r m r e s p e c t i v e l y . The form A LOTUS Manual Page i t s e l f i s indented according to i t s nested depth, as i s the value returned from each form. The *TERSE option causes nested t r i p l e s i n each form to print as "SS". If other traced symbols are encountered during a trace, t h e i r trace simply appears embedded at the appropriate spot : *<*TEACE C) *x > ENTERING X : > (A ! SS ! * FAIL) > 1. T A > 1. T <-=PASS > 1. P (B I SS ! *FAIL) > 2. T B > 2. T <—PASS > 2. P (C ! D ! *FAIL) > 3. T C > ENTERING C : > (B ! *'F AIL ! *PASS) > t. T B > 1. T <==PASS > 1. P *FAIL > 1. P <= = FAIL > <==FAIL RETURNED FROM > 3. T <= = FAIL > 3. F *FAIL > 3. F < = = FAIL > 2. P <==FAII > 1. P <==FAIL > <==FAIL RETURNED FROM APPENDIX I A LOTUS Manual Page The LOTUS program editor allows the user to modify existing programs i n t e r a c t i v e l y . The editor i s unleashed on a program by entering (*EDIT SYMBOL). Whenever the editor i s active, four special LOTUS programs are defined : * -the current active t r i p l e . *T - i t s TEST form. *P - i t s PASS form. *F - i t s FAIL form. The editor consists of commands which move the "*" pointer around i n the program being edited, plus commands which replace TEST, PASS and FAIL forms. 'These commands are : *T *p *F *TJP *TOP *UNDO •OUT *0K (*REPT FORM) (*R£PP FORM) (*REPF FORM) -move the pointer down the TEST arc. -move the pointer down the PASS arc. -move the pointer down the FAIL arc. -move the pointer up one l e v e l , -move the pointer to the top l e v e l , -restore the pgm to i t s status at the sta r t of the edit (and point to the top l e v e l ) , - e x i t without changing the program, -e x i t with changes applied. . -replace TEST form with FORM, -replace PASS form with FORM, -replace FAIL form with FORM. The "FORM" operand of the replace commands i s commonly a language primitive which returns a program, and may contain references to the editor pointers (*, *T, *P, *F) . The editor w i l l also accept any executable LISP expression as a command, including reguests to prettyprint portions of the program being edited. A LOTOS Manual Page Editor commands can be nested i n parentheses to achieve conditional execution. Each nested sequence of commands i s executed u n t i l a f a i l u r e i s encountered, which causes the rest of the seguance to be bypassed. The sequences themselves always succeed however, and cannot cause following sequences to be bypassed. The following example i l l u s t r a t e s the use of the editor to change program X (the •AND of programs A, B and C) into the •DO of A, B and C : •(•TALK) * (•CQMP (X (•AND A B C) ) ) *(•EDIT X) * (*PP •) > * : = •=> A > ==> B > C > •FAIL > •FAIL **P (•RE PF •P) •OP (•REPF *p. > .* : = = > A > ==> B > C > c > ==> SAME AS PASS ••OK APPENDIX I A LOTUS Manual Page I f you d i s c o v e r t h a t your changes were not what you r e a l l y wanted a f t e r you have l e f t t h e e d i t o r (as i s a l w a y s the c a s e ) , you can undo th e e f f e c t s o f a p r e v i o u s e d i t w i t h (*UNDO SYMBOL). For example : * (*PP X) > X : ==> A > ==> B > C > C > ==> SAME AS PASS FORM (ABOVE) * (*UNDO X) * (*PP X) > X : ==> A > ==> 3 > C > *FAI.L > *FAIL The e x e c u t i o n break r e c o v e r y r o u t i n e i s r e a l l y t h e LISP break package. The f u l l power of L I S P ' S BREAK f a c i l i t y a r e made a v a i l a b l e when an unbound LOTUS symbol i s e n c o u n t e r e d . A f t e r you have l o o k e d around and h o p e f u l l y r e p a i r e d t h e damage, you may r e e n t e r LOTUS where i t broke w i t h (*USE SYMBOL). The SYMBOL i s r e t u r n e d t o LOTOS t o be used i n p l a c e o f the p r e v i o u s l y u n d e f i n e d symbol which caused t h e break. APPENDIX I I A LOTUS "Green C a r d " Page 63 SYNTAX PGM --> (PGM PGM PGM) - t h e ( i f - t h e n - e l s e ) t r i p l e . — > SYMBOL -a LOTUS "atom". — > PRIMITIVE - a L I S P s - e x p r e s s i o n . COMPILER i (•COUP (SYMBOL PGM) (SYMBOL PGM) . . .) (•SETQC SYMBOL PGM) C o m p i l e r s y n t a x e x t e n s i o n s : PGM --> (•NOT PGM) — > {•AND PGM PGM . . .) — > (•OR PGM PGM . . . ) --> (*DO PGM PGM . . .) PRIMITIVES ^ FORM d e n o t e s e i t h e r a SYMBOL o r a PRIMITIVE e x p r e s s i o n and i n d i c a t e s t h a t t h e c u r r e n t LOTUS v a l u e o f t h e SYMBOL o r t h e v a l u e r e t u r n e d f r o m e x e c u t i n g t h e PRIMITIVE i s used. (•SETQ SYMBOL FORM) - b i n d s t h e FORM t o t h e SYMBOL. (•PUSHQ SYMBOL FORM FORM FORM) - b i n d s t h e t r i p l e (FORM FORM FORM) t o t h e SYMBOL. (•CONS FORM FORM FORM) - r e t u r n s t h e t r i p l e {FORM FORM FORM). {•POST SYMBOL FORM) - r e t u r n s a pgm which w i l l b i n d t h e FORM t o t h e SYMBOL. (•PRINT FORM) - r e t u r n s a pgm which w i l l p r i n t t h e FORM ( n o r m a l l y y i e l d i n g a SYMBOL). {•PRINTC PGM) - r e t u r n s a pgm which w i l l p r i n t t h e PGM ( n o r m a l l y a SYMBOL). O t h e r f u n c t i o n s commonly used as p r i m i t i v e s : (QUOTE ARG) - r e t u r n s I t s argument. (•SETQC SYMBOL PGM) -see~COMPILER (above) . FUNCTIONS 1 (•PP SYMBOL) {•TRACE SYMBOL SYMBOL . . .) (•UNTE ACS SYMBOL SYMBOL . . .) (•TERSE) (•EDIT SYMBOL) {•UNDO SYMBOL) (•TALK) (•EVAL FORM) - p r i n t s t h e pgm bound t o SYMBOL, - s t a r t s t r a c i n g e x e c u t i o n o f t h e SYMBOLS, - s t o p s t r a c i n g e x e c u t i o n of t h e SYMBOLS, - t u r n s " t e r s e " o p t i o n on / o f f . - a l l o w s e d i t on pgm bound t o SYMBOL, -undoes p r e v i o u s (•EDIT SYMBOL) . - t o p l e v e l LOTUS from L I S P , - e x p l i c i t c a l l t o LOTUS (eg. from L I S P ) . APPENDIX I I I LOTOS (MTS-LISP V e r s i o n ) Page ; * * * * * * * * * * * * THE LOTOS COMPILER * * * * * * * * * * * * * * * (POT • *PASS 1 LOTOS • »T) (POT »*FAIL * LOTOS " N I L ) (DEFUN *COMP FEXP.R (LIST) (MAPC »*C0MP1 LIST) 'READY) (DEFON *SETQC NEXPR (LEL LPGM) (AND (ATOM LBL) (POT LBL * LOTUS (*COMP3 LPGM)))) (DEFUN *C0MP1 (PGM) (COND ( (ATOM (CAR PGM)) (PUT (CAR PGM) 'LOTUS (*COHP3 (*COMP2 (CDR PGM})))) ( (PRINT '"*** ERROR - MISSING LABEL * * * " ) ) ) ) (DEFUN *COMP3 (TRIP) (PROG (TEMP) (COND ((ATOM TRIP) (RETURN TRIP)) { (MEMQ (CAR TRIP) ' (*LISP *L) ) (RETURN (CDR T R I P ) ) ) ( (AND (NULL (GET (CAR TRIP) 'LOTUS)) (GSTL (CAR TRIP) '(EXPR SUBR NSUBH FSU8E))) (COND ( (NOT (MEMQ (CAR TRIP) » (*AND * O E *NOT *DO))) (RETURN TRIP) ) { (RETURN (*COMP3 (EVAL TRIP) ) ) ) )) ( (NOT (EQ (LENGTH TRIP) 3) ) (PRINT " » * * * ERROR - SYNTAX ***") (RETURN N I L ) ) ) {RETURN (CONS ' LOTUS (CONS (*CCMP3 (CAR TRIP)) (CONS (SETQ TEMP (*COHP3 (CADfi T R I P ) ) ) (COND ({EQ (CADR TRIP) (CADDR TRIP)) TEMP) ({*COMP3 (CADDR T R I P ) ) ) ) ) ) ) ) ) ) APPENDIX I I I LOTUS (MTS-LISP V e r s i o n ) Page (DEFUN *C0MP2 (LPGM) (COND ( (NULL LPGM) NIL) ((•COMP21 (CAE LPGM) (*COHP2 (CDR L P G M ) ) ) ) ) ) (DEFUN *COMP21 (TRIP NEXT) (COND ( (ATOM TRIP) TRIP) ( (AND (NULL (INTERSECT TRIP ' (* *N *NEXT) ) ) NEXT) (PRINT «« * * * ERROR - SYNTAX ***") NIL) ( (MAPCAR '*COMP2 (*COHP23 (MAPCAR »*COHP22 T R I P ) ) ) } ) ) (DEFUN *COMP22 (ATOM) (COND {{NULL (MEMQ ATOM > (* *N *NEXT) ) ) ATOM) (NEXT) {(PRINT '»*** ERROR - SYNTAX ***") N I L ) ) ) (DEFUN *COMP23 (LIST) (PROG (TEMP) (COND { (NULL LIST) NIL) { {OR (ATOM (CAR LIST) ) (NULL (INTERSECT (CAR LIST) » {* *N *NEXT) ) ) ) (CONS (CONS (CAR LIST) NIL) (*COMP23 (CDR L I S T ) ) ) ) {(CONS (LIST (CAR LIST) (CAAR (SETQ TEMP (*CCMP23 (CDR L I S T ) ) ) ) ) (CDR TEMP) ) ) ) ) ) ARRMQIl I I I Page 66 LOTUS (MTS-LISP V e r s i o n ) . * * * * * * * * * * * * r j H E COMPILER EXTENSIONS *************** (DEFUN *XVAL (FORM) (COND { (OR (ATOM FORM) (NOT (MEMQ (CAR FORM) ' (*AND *OR *NOT *DO) ) ) ) FORM) {(EVAL FORM)))) (DEFUN *NOT NEXPR (FORM) (L I S T (*XVAL FORM) ' * F A I L •*PASS)) (DEFUN *AND FEXPR ( L I S T ) (COND ((NULL (CDR L I S T ) ) (*XVAL (CAR L I S T ) ) ) ( ( L I S T (*XVAL (CAR L I S T ) ) (APPLY * *AND (CDR L I S T ) ) ' * F A I L ) ) ) ) (DEFUN *OR FEXPR ( L I S T ) (COND { (NULL (CDR L I S T ) ) (*XVAL (CAR L I S T ) ) ) ( ( L I S T (*XVAL (CAR L I S T ) ) '*PASS (APPLY '*OR (CDR L I S T ) ) ) ) ) ) (DEFUN *DO FEXPR (LI S T ) (PROG (TEMP) (COND ( (NULL (CDR L I S T ) ) (*XVAL (CAR L I S T ) ) ) ( ( L I S T (*XVAL (CAR L I S T ) ) (SETQ TEMP (APPLY ' *DO (CDR L I S T ) ) ) TEMP) ) ) ) ) LOTOS (MTS-LISP V e r s i o n ) Page 67 • * * * * * * * * * * * * TEE LOTUS INTERPRETER *************** (DEFON LOTOS FEXPR (T-P-F) (COND (*TRACE (TRACE-LOTUS T-P-F)) { (*EVAL (CAR T-P-F) ) (*EVAL (C ADR T-P-F) ) ) { (*EVAL (CDDR T-P-F))))) (DEFUN *EVAL (PGM) (COND {(ATOM PGM) (*FETCH PGM)) { (EVAL PGM) ) ) ) (DEFUN *INT NEXPR (PGM) (COND { (*EVAL PGM) 'PASS) ( ' F A I L ) ) ) (DEFUN *FETCH (LABEL) (PROG (*TRACE PGM) {AND (GET LABEL 1*TRACE) (SETQ *TRACE 0 ) ) (COND ((SETQ PGM (GET LABEL * LOTUS) ) (AND *TRACE (PRIN1 ' ENTERING) (PRIN1 LABEL) (PRIN1 •:) (TERPR1) (TAB 3) (PHIN1 (*SHORT (*TR2 PGM))) ( T E R P R 1 ) ) (SETQ PGM (*EVAL PGM) ) (AND *TRACE (TAB 3) (PRIN1 (COND (PGM •"<==PASS") {'«<==FAI L") ) ) (PRIN1 '"RETURNED FROM") (PRIN1 LABEL) (TERPR1) ) PGM) (T (*FETCH (*BREAK L A B E L ) ) ) ) ) ) APPENDIX I I I LOTUS (MTS-LISP V e r s i o n ) Page 68 (DEFUN *BREAK (LABEL) (PRIN1 •«*** ERROR: *FETCH - NULL PGM =") ( P R I N 1 LABEL) (PRIN1 »***) (TERPRI) (BREAK) ) (DEFUN *USE NEXPR (FORM) (RETURN FORM 1 BREAK)) (DEFUN *TALK () (PROG () LOOP (*EVAL (READ) ) (GO LOOP) ) ) M £ I I D I X I I I LOTUS (MTS-LISP V e r s i o n ) Page 69 . ************ THE LOTOS P R I M I T I V E S *************** (DEFUN *GET NEXPR (LAB) (COND { ( L I S T P LAB) (EVAL LAB) ) ( (GET LAB ' LOTOS) ) (T (PRIN1 «»*** ERROR: *GET - NULL PGM =") (PRIN1 LAB) (PRIN1 '***) (TERPRI) (APPLY 1 '*GET ( B R E A K ) ) ) ) ) (DEFUN *5ETQ NEXPR (LAB FORM) (PUT LAB 'LOTUS (COND ( (ATOM FORM) (APPLY1 * *GET FORM)) ( (EVAL FORM) ) ) ) ) (DEFUN *CONS NEXPR (TEST PASS F A I L ) (CONS 'LOTOS (CONS (APPLY 1 '*GET TEST) (CONS (APPLY 1 •*GET PASS) (APPLY 1 •*GET F A I L ) ) ) ) ) (DEFUN *P0SHQ NEXPR (LAB TEST PASS F A I L ) {APPLY1 «*SETQ LAB (APPLY 1 '*CONS TEST PASS F A I L ) ) ) (DEFUN *SETL NEXPR" (L VALUE) (MAPC * (LAMBDA (R) (PUT R 'LOTUS (APPLY 1 '*GET V A L U E ) ) ) L) T) (DEFUN *POST NEXPR (REG VALUE) ( L I S T «*5ETQ REG ( L I S T 'QUOTE (APPLY1 «*GET V A L U E ) ) ) ) (DEFUN *PRINTC NEXPR (SYM) (LIST 'PRINT (LIST •QUOTE SYM))) (DEFUN *PRINT NEXPR (FORM) (APPLY 1 '*PRINTC (APPLY 1 1*GET FORM))) APPENDIX I I I LOTUS i M T S - L I S P Version) Page 70 . ************ THE TRACE PACKAGE *************** (SETQ *TRACE NIL) {DEFUN *TRACE FEXPR {LIST) (MAPC 1 (LAMBDA (X) (PUT X ' *TRACE) ) LIST) •DONE) (DEFUN *UNTRACS FEXPR (LIST) {MAPC ' (LAMBDA (X) {REM X ' *TRACE) ) LIS T ) 'DONE) (DEFUN TRACE-LOTUS (T-P-F) (PROG (*CC) (SETQ *TRACE (ADD1 *TRACE)) (COND ((*TRVAL (CAR T-P-F) «T) (*TRVAL (CADR T-P-F) »P)) ( (*TRVAL (CDDR T-P-F) • F) ) ) (SETQ *TRACE (SUB 1 *TRACE) ) (RETURN *CC) ) ) (DEFUN *TRVAL (FORM CHAR) (*TR CHAR FORM) (COND { (SETQ *CC (*EVAL FORM) ) (*TR CHAR »"<==PASS")) { (*TR CHAR '"<==FAIL"))) *CC) (DEFUN *TR (CHAR FORM) (PRIN1 *TRACE) (PRIN1 CHAR) (TAB {ADD 3 (TIMES 3 *TRACE))) (PRIN 1 (*SHORT (*TR2 FORM))) (TERPRI) ) (DEFUN *TR2 (PGM) (COND ( {ATOM PGM) PGM) ((NOT (EQ (CAS PGM) 'LOTUS)) PGM) ( ( L I S T (*TR2 (CADR PGM) ) ' ! (*TR2 (CADDR PGM) ) • ! ( * T R 2 (CDDDR PGM) ) ) ) ) ) APPENDIX I I I LOTUS 7«TS-LISP~Version) Page 71 {DEFUN TERPR1 () (TERPRI) T) (SETQ *TERSE NIL) (DEFUN *SHORT (LIST) (COND ({OR (ATOM L I S T ) (NULL *TERSE) ) LIS T ) • { (ATOM (CAR L I S T ) ) (CONS (CAR L I S T ) (*SHORT (CDR L I S T ) ) ) ) (T (CONS •&& (*SHORT (CDR L I S T ) ) ) ) ) ) (DEFUN *TERSE () (COND {(NULL *TERSE) (SETQ *TERSE T) ««*TERSE = ON") (T (SETQ *TERSE NIL) •"•TEBSE = O F F " ) ) ) LOTUS (MTS-LISP Version) Page 72 - ************ 2. H E PRETTYP'RINTES *************** (DEFUN *PRSTTYPRINT (PGM) (APPLY1 »*PP PGM) ) (DEFUN *PP NEXPR (PGM) (PROG (TABN FORM) (COND ( (ATOM PGM) (SETQ TABN (ADD 9 (PLEN P GM)))) { (PRINT '"PROGRAM NAME MUST BE AN ATOM")) (RETURN '" »)) (COND ( (SETQ FORM (GET PGM 'LOTUS) ) (PRIN1 PGM) (PRIN1 ':) (*PR1 TABN FORM)) ( ( P R I N 1 PGM) (PRIN1 ' " I S NOT A LOTUS PROGRAM") (TERPRI) ) ) in .1)) (DEFUN *PR1 (TABN FORM) (COND ( (ATOM FORM) (PRIN1 FORM) (TERPRI)) ( (NOT (EQ (CAR FORM) 'LOTUS) ) (PRIN 1 (*SHORT FORM) ) (TERPRI) ) (T (PRIN 1 >»-=> ") (AND (GREATERP TABN 60) (SETQ TABN 5)) (*PR1 (ADD 5 TABN) (CADR FORM) ) (TAB TABN) (*PR1 (ADD 5 TABN) (CADDR FORM)) (TAB TABN) (COND ((AND (NOLL (ATOM (CDDDR FORM))) (EQ (CADDR FORM) (CDDDR FORM))) (PRIN 1 '"==> SAME AS PASS FORM (ABOVE)") (TERPRI) ) (T (*PR1 (ADD 5 TABN) (CDDDR FORM))))))) £ £ £ M D I X I I I Page 73 LOTUS (MTS-LISP V e r s i o n ) ; ************ THE EDITOR *************** (SETQ *EDIT NIL) (DEFUN *T FEXPR (ARCS) (COND { (NULL *EDIT) NIL) ({NULL (EQ (CAADR (CAR *PGM) ) 'LOTUS}) (PRIN1 «"*T FAILED:") (*REJ (CONS ' *T ARGS))) (T (SETQ *PGM (CONS (CADAR *PGM) *PGM) ) (*ED-GO A R G S ) ) ) ) (DEFUN *P FEXPR (ARGS) (COND { (NULL *EDIT) NIL) ((NULL (EQ (CAADIR (CAR *PGM)) 'LOTUS)) (PRIN1 »«*P FAILED:") (*HEJ (CONS •*P ASGS))} (T (SETQ *PGM (CONS (CADDAR *PGM) *PGM) ) (*3D-G0 A R G S ) ) ) ) (DEFUN *F FEXPR (ARGS) (COND ({NULL * E D I T ) NIL) ((NULL (EQ (CAADDR (CDAR *PGM) ) 'LOTUS)) (PRIN1 «"*F FAILED:") (*REJ (CONS • *F ARGS))) (T (SETQ *PGM (CONS (CDDDAR *PGM) *PGM) ) (*ED-GQ AR G S ) ) } ) (DEFUN *ED-GO (ARGS) (AND (COND { (NULL *EDIT) NIL) { (NULL ARGS) ) { (NULL (ATOM (CAR ARGS))) (COND {(*ED-GO (CAR ARGS))(*ED-GO (CDR ARGS}}} (T (*REJ A R G S ) ) ) ) ( (EVAL ARGS) ) ) (*SETQ * (CAR *PGM) ) (*SETQ *T (CADAR *PGM) ) (*SETQ *P {CADDAR *PGM)) (*SETQ *F (CDDDAR *PGM)))) (DEFUN *R.EJ (ARGS) (PROG () (PRIN1 • "CANNOT DO") (PRIN1 ARGS) (TERPRI) (RETURN T ) ) ) MEMDIX III LOTUS (MTS-LISP Version) Page (DEFUN *UP FEXPR (ARGS) (COND ( (NULL *EDIT) NIL) ((NULL (CDR *PGM)) ( P R I N 1 *"*UP FAILED:") (*REJ ARGS) ) (T (SETQ *PGM (CDR *PGM) ) (*ED-GO ARGS)))) (DEFUN *TOP FEXPR (ARGS) (COND ((NULL *EDIT) NIL) (T (SETQ *PGM (LAST *PGM)) (*ED-GO ARGS)))) {DEFUN *ED.IT FEXPR ( LBL ) (PROG (*PGM) (COND ( (AND (NULL LBL ) *EDIT) (GO LOOP)) ( (NULL LBL ) ( P R I N 1 '"NO EDIT ACTIVE") (RETURN (TERPRI)))) (SETQ *EDIT (GET (CAR LBL ) 'LOTUS)) (AND (NULL (EQ (CAR *EDIT) 'LOTUS) ) (PRIN1 '"PROGRAM NOT A TRIPLE") (RETURN (TERPRI) ) ) (SETQ *PGM (LIST (*COPY *EDIT))) (*ED-GO "T) LOOP (*ED-GO (LIST (READ))) (GO LOOP) ) ) (DEFUN *UNDO FEXPR (ARGS) (COND ((NULL *EDIT) (MAPC '*POPl ARGS) * UNDONE) (T (SETQ *PGM (LIST (*COPY *EDIT))) (*ED-GO ARGS)))) (DEFUN *POP1 ( LBL ) (PROG (*PGM) (RETURN (COND ((NULL (SETQ *PGM (GET LBL »*EDIT))) ( P R I N 1 '"FAILED ON") (PRIN1 LBL ) (TERPRI)) (T (PUTPROP LBL (CAR *PGM) ' LOTUS) (PUTPROP LBL (CDR *PGM) , * S D I T ) ) ) ) ) ) (DEFUN *REPT FEXPR (ARGS) (COND ({NULL *EDIT) NIL) (T (RPLACA (CDAR *PGM)(APPLY1 ' *GET (CAR ARGS)))))) MOND IX I I I LOTUS (MTS-LISP Version) Page 7 5 (DEFUN *REPP FEXPR (ARGS) (COND { (NULL *EDIT) NIL) (T (RPLACA (CDDAR *PGM)(APPLY1 • *GET (CAR ARGS)))))) (DEFUN *REPF FEXPR (ARGS) (COND ( (NULL *EDIT) NIL) (T (RPLACD (CDDAR *PGM) (APPLY1 ' *GET (CAR ARGS)))))) (DEFUN *OUT FEXPR (ARGS) (COND { (NULL *EDIT) NIL) (T (SETQ *EDIT NIL) (RETURN 'UNCHANGED)))) (DEFUN *0K FEXPR (ARGS) (COND ( (NULL *EDIT) NIL) (T (PUTPROP (CAR LBL ) (CAR (LAST *PGM) ) • LOTUS) (PUTPROP (CAR LBL ) (CONS *EDIT (GET (CAR LBL ) 1*EDIT)) ' *EDIT) (SETQ *EDIT NIL) (RETURN 'CHANGED)))) APPENDIX III LOTUS (MTS-LISP Version) Page ; ************ BOTTOM-UP VARIABLE PROTECTION *************** {DEFUN *LOG FEXPR (LIST) (MAPC ' (LAMBDA (X) (COND ( (MEMQ X *LOG) ) (T (SETQ *LOG (CONS X *LOG)) (APPLY 1 '*PUSHQ '*EPILOGUE (LIST «*POST X X) '•EPILOGUE •*FAIL)))) LIST) T) (DEFUN *PROLOGUE {) (*C0MP3 (APPEND (LIST (LIST (LIST 'QUOTE (LIST 'SETQ •*LOG (LIST QUOTE *LOG))) (MAPCAR '*NEXT •' *NEXT) ) • (LAMBDA (X) (LIST (LIST >*POST X X) '*NEXT ' *NEXT) ) *LOG) ' (*PASS) ) ) ) (DEFUN *LEAVE NEXPR (LEL PROCESS) (SETQ PROCESS (APPLY 1 «*CONS PROCESS "*EPTLOGUE * * ^ EPILOGUE) (SETQ PROCESS (APPLY 1 »*CONS • (*PROLOGUE) • (EVAL 'PROCESS) '(EVAL 'PROCESS))) (APPLY1 '*PUSHQ LBL LBL « (EVAL * PROCESS) « (EVAL 'PROCESS)) PROCESS) (SETQ *.LOG • (*EPILOGUE) ) (SETQ *EPILOGOE (*CONS '(SETQ *LOG » {*EPILOGUE)) '(*SETQ *EPILOG0E (EVAL '^EPILOGUE)) •*FAIL) ) {•SETQ *EPILOGUE (EVAL »*EPILOGUE)) APPENDIX III LOTOS (MTS-LISP V e r s i o n ) Page 77 . ************ MISCELLANEOUS ************ (DEFUN * P S I Z E NEXPR (PGM) (COND ( (NULL (SETQ PGM (GET PGM 'LOTUS))) 0) ({•PSIZE1 P G M ) ) ) ) (DEFUN *S.IZE () (PROG (NUM) (SETQ NUM 0) (MAPC «*SIZE1 (DELQ »*ONDEF* (OBLIST) ) ) (RETURN NOM) ) ) (DEFON *PSIZE1 (PGM) (COND ( (EQ (CAR PGM) ' LOTUS) (ADD 1 (*PSIZE1 (CADR PGM) ) (•PSIZE1 (CADDR PGM)) (*PSIZE1 (CDD.DR P G M ) ) ) ) ( (EQ (CAR PGM) ' QUOTE) (*PSIZE1 (CADR PGM))) ( (EQ (CAR PGM) * *SETQ) (ADD1 (*PSIZE1 (CADDR P G M ) ) ) ) (1))) (DEFUN *SIZE1 (LAB) (SETQ NUM (ADD NUM (APPLY 1 ' * P S I Z E L A B ) ) ) ) APPENDIX I V A LOTOS CONTEXT-FREE PARSER Page 78 THE PARSER GENERATING P R I M I T I V E S : (DEFUN •TALK () (PROG () LOOP (•SETQC •BETA •REDN) {•SETQ •REDN {•PRINTC PARSE:)) (•EVAL (READ) ) (GO LOOP) ) ) (DEFUN TERM NEXPR (X) (APPLY1 '•SETQC X ' • RESET) (BLD= X) (BLD: X) (*SETQC TMP •STAK) (•PUSHQ TMP ( L I S T '•PUSHQ X X '•BETA * • F A I L ) TMP •F AIL) (•PUSHQ TMP ( L I S T '•PUSHQ '*RESET (LIS T ••POST X X) '•RESET '•F A I L ) TMP • F A I L ) (•PUSHQ TMP ' (•PUSHQ •BETA (•POST •REDN •REDN * BETA • F A I L ) ) TMP • F A I L ) (•PUSHQ TMP ( L I S T '•PUSHQ '•REDN '•REDN (MKATOM '= X) '•FA I L ) TMP • F A I L ) {•PUSHQ TMP ( L I S T *•PUSHQ '•REDN ••REDN (MKATOM •: X) •• F A I L ) TMP • F A I L ) (•PUSHQ TMP '•SAVREDN TMP • F A I L ) (APPLY 1 * •SETQ (MKATCM '? X) 'TMP)) A P P E N D I X i v A L O T U S C O N T E X T — P R E E P A R S E R (DE.'FUN NO.NT N E X P R (X) (APPLY 1 ' * S E T Q C X « * P A S S ) (BLD= X) (BLD: X) { • S E T Q C TMP * S T A K ) ( • P U S H Q TMP ( E V A L ' X ) TMP * F A I L ) ( • P U S H Q TMP ( L I S T » * P U S H Q • • B E T A ( L I S T ' Q U O T E ( L I S T «*PUSHQ • * R E D N • • R E D N (MKATOM ' • • F A I L ) ) • • B E T A ' • F A I L ) T M P • F A I L ) ( • P U S H Q TMP ( L I S T • • P U S H Q ' • R E D N ••REDN (MKATOM ' : X) • • F A I L ) TMP • F A I L ) ( • P U S H Q TMP • • S A V R E D N TMP * F A I L ) ( A P P L Y 1 ' * S E T Q (MKATOM » ? X) • TMP) ) ( D E F U N PBO.DN N E X P R ( L H S RHS) ( • S E T Q C TMP * S T A K ) ( • P U S H Q TMP ' * B E T A T M P * F A I L ) (MAPC ' ADD? RHS) ( • P U S H Q TMP • * S A V B E T A TMP *FAIL) ( A P P L Y 1 ' * P U S H Q L H S ' T M P L H S • • F A I L ) ) ( D E F U N A D D ? (X) ( • P U S H Q TMP ( L I S T » *.PUSHQ • * B E T A T M P • F A I L ) ) ' ( * P O S T * B E T A * B E T A ) (MKATOM • ? X) ' • F A I L ) IV A LOTUS~CONTEXT~FREE PARSER (DEFUN BLD= (X) (APPLY1 •*SETQC (MKATOM » = X) '•OUT)) (DEFUN BID: (X) (APPLY 1 '•PUSHQ (MKATOM ': X) • • • I N (LIST '•PRINTC X) ' • F A I L ) ) (•SETQC •RESET ••RESET) (•SETQC ••RESET (•SETQC •RESET ••RESET)) {•SETQC •STAK •PASS) (•SETQC •SAVBETA (•PUSHQ •STAK (•POST •BETA •BETA) (•POST •STAK •STAK) • F A I L ) ) (•SETQC •SAVREDN (•PUSHQ •STAK {•POST •REDN •REDN) {•POST •STAK •STAK) • F A I L ) ) (•SETQC •SP (PRIN 1 "' ") ) (•SETQC • I N {•AND (•PUSHQ •OUT (•POST • I N ^IN) (•POST •OUT •OUT) • F A I L ) (•PUSHQ •IN • I N •SP • F A I L ) ) ) (•SETQC •OUT •PASS) APPENDIX IV A LOTOS C O N T E X T - F R E E PASSER Page 81 IM HfiON PHRASE GRAMMAR AND DICTIONASYj. (NO NT NOUNPHRASE) (NONT NOONGROUP) (NONT ADJECTIVEPHRASE) (NO NT NOONCLASSIFIER) (NONT MAINNOUN) (NONT POSTNOMINA.L) {N 0 NT PREPOSIT ION PHRASE) (NONT CONJUNCTION) (NONT ADJECTIVE) (NONT ADVERB) (NONT NOUN) (NONT PREPOSITION) (NONT DETERMINER) (PRODN NOUNPHRASE (DETERMINES NOUNGROUP)) (PRODN NOUNPHRASE (NOUNGROUP CONJUNCTION NOUNGROUP) ) (PRODN NOUNPHRASE (NOUNGROUP)) (PRODN NOUNGROUP (ADJECT!VEPHRASE NOUNGROUP)) (PRODN NOUNGROUP (MAINNOON POSTNOMINAL)) (PRODN NOUNGROUP (MAINNOUN)) (PRODN ADJECTIVEPHRASE (ADVERB ABJECTIVEPHRASE) ) (PRODN A D J E C T I V E P H R A S E (ADJECTIVE)) (PRODN MAINNOUN (NOONCLASSIFIER MAINNOUN)) (PRODN MAINNOUN (NOUN)) (PRODN NOONCLASSIFIER (NOON) ) (PRODN POSTNOMINAL (PREPOSITICNPHRASE)) (PRODN PREPOSIT IONPHRASE (PREPOSITION NOUNPHRASE)) (TERM A) (TERM THE) (TERM BIG) (TERM RED) (TERM SMALL) (TERM BACK) (TERM DOG) (TERM HOUSE) (TERM YARD) (TERM IN) (TERM VERY) (PRODN DETERMINER (A)) (PRODN DETERMINER (THE)) (PRODN ADJECTIVE (B I G ) ) (PRODN ADJECTIVE (RED) ) (PRODN ADJECTIVE (BACK)) (PRODN ADJECTIVE (SMALL) ) APPENDIX I V A LOTOS CONTEXT-FREE PARSER Page 82 (PRODN NOUN (BACK)) (PRODN NOUN (DOG) ) (PRODN NOUN (HOUSE)) (PRODN NOUN (YARD) ) (PRODN PREPOSITION (IN) ) (PRODN ADVERB (VERY)) APPENDIX I V A LOTUS CONTEXT-FREE PARSER Page 83 1 SAMPLE ME 21 THE GENERATED PASSER.: ; PARSE FOR A NOUNPHRASE • (*TALK) * *?NOUN PHRASE • A • VERY *BIG •HOUSE > PARSE: > NOUNPHRASE > DETERMINER > A > NOUNGROUP > ADJECTIVEPHRASE > ADVERB > VERY > ADJECTIVEPHRASE > ADJECTIVE > BIG > NOUNGROUP > MAINNOUN > NOUN > HOUSE * ••RESET * •7N0UNPHRASE •A • BIG •RED •DOG > PARSE: > NOUNPHRASE > DETERMINER > A > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > BIG > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > RED > NOUNGROUP ; K I L L OFF ALL ACTIVE PROCESSES ;READY FOR THE NEXT PHRASE ;A PREMATURE SUCCESS APPENDIX I V A LOTUS CONTEXT-FREE PARSER Page 84 > MAINNOUN > NOUN > DOG * •HOUSE ;ANOTHER SUCCESS > PARSE: > NOUNPHRASE > DETERMINER > A > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > BIG > NOUNGROUP > ADJECTIVEPHRASE > 'ADJECTIVE > RED > NOUNGROUP > MAINNOUN > NOUNCLASSIFISR > NOUN > DOG > MAINNOUN > NOUN > HOUSE * • I N ;THE NEXT WORD • THE •VERY •SMALL •BACK ;ANOTHER PREMATURE PARSE > PARSE: > NOUNPHRASE > DETERMINER > A > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > BIG > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > RED > NOUNGROUP > MAINNOUN > NOUNCLASSIFISR > NOUN > DOG ' APPENDIX I V Page 85 A LOTUS CONTEXT-FREE PARSER > MAINNOUN > NOUN > HOUSE > POSTNOMIN AL > PRIPOSITIGNPHRASE > PREPOSITION > IN > NOUNPHRASE > DETERMINER > THE > NOUNGROUP > ADJECTIVEPHRASE > ADVERB > VERY > ADJECTIVEPHRASE > ADJECTIVE > SMALL > NOUNGROUP > MAINNOUN > NOUN > BACK * *YARD ;AN AMBIGUOUS SENTENCE > PARSE: > NOUNPHRASE > DETERMINER > A > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > BIG > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > RED > NOUNGROUP > MAINNOUN > NOUNCLASSIFIER > NOUN > DOG > MAINNOUN > NOUN > HOUSE > POSTNOMINAL > PREFOSITIONPHRASE > PREPOSITION > I N > NOUNPHRASE APPENDIX I V A LOTOS CONTEXT-FREE Page 86 PARSER > DETERMINER > THE > NOUNGEOUP > ADJECTIVEPHRASE > ADVERB > VERY > ADJECTIVEPHRASE > ADJECTIVE > SMALL > NOUNGROUP > MAINNOUN > NOUNCLASSIFISR > NOUN > BACK > MAINNOUN > NOUN > YARD > PARSE: > NOUNPHRASE > DETERMINE R > A > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > BIG > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > RED > NOUNGROUP > MAINNOUN > NOUNCLASSIFIER > NOUN > DOG > MAINNOUN > NOUN > HOUSE > POSTNOMINAL > PRIPOSITIONPHRASE >. PREPOSITION > IN > NOUNPHRASE > DETERMINER > THE > NOUNGROUP > ADJECTIVEPHRASE > ADVERB > VERY APJ?ENDIX I V Page 87 A LOTUS CONTEXT-FREE PARSER > ADJECTIVEPHRASE > ADJECTIVE > SMALL > NOUNGROUP > ADJECTIVEPHRASE > ADJECTIVE > BACK > NOUNGROUP > MAINNOUN > NOUN > YARD Page 8 8 INDEX * . . ' . . » . . . . 60 •AND . . . . . . . 52, 66 •COH.P . . . . . . . 51, 64 E x t e n s i o n s . . , 51 •CONS . 56, 69 • DO . 52, 66 I n t e r p r e t e r . . . . 47 •EDIT . . . . . . . 60, 74 •EVAL . . 48, 67 . . . 47, 67 •F . . . . . . . . . 60, 73 •FAIL . . . . . . . 6, 52 P r e t t y p r i n t e r . . . 49 •INT . . . . . . . 48, 67 P r i m i t i v e s . . . 54 •L . 51 •LISP . . . . . . . 51 . . . 9, 46 •NOT . . . . . . . 52, 66 •OK . 60, 75 •OR . 52, 66 •OUT . . 60, 75 •P . 60, 73 •PASS . 6, 5 2 •POST . . . . . . 14, 56, 69 •PP . . . . . . . . . 49, 72 *PR ETT Y PR I NT . , . 49, 72 •PRINT . . . . . . 56, 69 • PRINTC . . . . . . 15, 56, 69 •POSH . . 37 •PUSHQ . . . . . 13, 55, 69 •RSPF . . . . . . . 60, 75 •REPP . . . . . . . . 60, 75 •REPT . . . . . . . . 60, 74 •SET . . . . . . . . 37 •SETQ . . . 15, 55, 69 •SETQC . . . . . . 51, 55, 64 •T . . . . . . . . . . 60, 73 •TALK . . . . . . . . 24, 32, 48, 58 •TERSE . . . . . . 50, 57, 71 •TOP . . . . . . . . 60, 74 •TRACE . . 57, 70 •UNDO . . . . . . . . 60, 62, 74 •UNTRACE .. . . . . 57, 70 •UP . . . . . . . . . 60, 74 •USE . . . . . . . 62, 68 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051783/manifest

Comment

Related Items