@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Computer Science, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Fine, Gary"@en ; dcterms:issued "2010-03-02T22:36:11Z"@en, "1979"@en ; vivo:relatedDegree "Master of Science - MSc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description "Recent developments in interactive Computer-Aided -Instruction and in Artificial Intelligence have enabled teaching machines and programs to deal reasonably effectively with the subject matter to be taught. Presented herein is a proposal and design for an intelligent LISP teaching machine. It is expected that such a system would be used in conjunction with other conventional methods to teach students, with some prior programming knowledge, the LISP programming language and \"correct\" programming style. With the belief that procedural knowledge is best learned by 'doing', this CAI system will integrate instruction in concepts, LISP syntax and semantics; instruction in the design of LISP functions and code; and analysis of students' solutions and consequent error correction. The goal of this LISP tutor is simply to act like a human tutor - cognizant of what the student is doing all the time, and able to provide advice and give direction where necessary."@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/21357?expand=metadata"@en ; skos:note "DESIGN OF AN INTELLIGENT LISP CAI TUTOR GARY FINE B.Sc.(Hons.), The U n i v e r s i t y of Cape Town, 1977 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept t h i s t h e s i s as conforming t o the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA October 1979 Gary F i n e , 1979 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r a n a d v a n c e d d e g r e e a t t h e 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 , I a g r e e t h a t t h e L i b r a r y s h a l l m a k e i t f r e e l y a v a i l a b l e f o r r e f e r e n c e a n d s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e H e a d o f my D e p a r t m e n t o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . D e p a r t m e n t o f C o m p u t e r S c i e n c e 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 2075 Wesbrook Place Vancouver, Canada V6T 1WS Date n r r n h p r - 3 1 Q 7 Q i i ABSTRACT R e c e n t d e v e l o p m e n t s i n i n t e r a c t i v e C o m p u t e r - A i d e d -I n s t r u c t i o n and i n A r t i f i c i a l I n t e l l i g e n c e have e n a b l e d t e a c h i n g m a c h i n e s and p r o g r a m s t o d e a l r e a s o n a b l y e f f e c t i v e l y w i t h t h e s u b j e c t m a t t e r t o be t a u g h t . P r e s e n t e d h e r e i n i s a p r o p o s a l and d e s i g n f o r an i n t e l l i g e n t L I S P t e a c h i n g m a c h i n e . I t i s e x p e c t e d t h a t s u c h a s y s t e m w o u l d be u s e d i n c o n j u n c t i o n w i t h o t h e r c o n v e n t i o n a l m e t h o d s t o t e a c h s t u d e n t s , w i t h some p r i o r p r o g r a m m i n g k n o w l e d g e , t h e L I S P p r o g r a m m i n g l a n g u a g e and \" c o r r e c t \" p r o g r a m m i n g s t y l e . W i t h t h e b e l i e f t h a t p r o c e d u r a l k n o w l e d g e i s b e s t l e a r n e d by ' d o i n g ' , t h i s C A I s y s t e m w i l l i n t e g r a t e i n s t r u c t i o n i n c o n c e p t s , L I S P s y n t a x and s e m a n t i c s ; i n s t r u c t i o n i n t h e d e s i g n o f .LISP f u n c t i o n s and c o d e ; and a n a l y s i s o f s t u d e n t s ' s o l u t i o n s and c o n s e q u e n t e r r o r c o r r e c t i o n . The g o a l o f t h i s L I S P t u t o r i s s i m p l y t o a c t l i k e a human t u t o r - c o g n i z a n t of what t h e s t u d e n t i s d o i n g a l l t h e t i m e , and a b l e t o p r o v i d e a d v i c e and g i v e d i r e c t i o n w h e r e n e c e s s a r y . i i i TABLE OF CONTENTS PAGE ABSTRACT i i LIST OF FIGURES i v CHAPTER I I n t r o d u c t i o n 1 I I H i s t o r i c a l Survey of CAI 5 I I I The Semantic Network & I n s t r u c t i o n of T i m e - I n v a r i a n t Concepts 18 IV M o d e l l i n g LISP f u n c t i o n s IV.1 I n t r o d u c t i o n IV.2 R e p r e s e n t i n g Segments v i a base e n t r i e s IV.3 S p e c i f i c a t i o n s IV.4 P l a n s IV.5 C o n c l u s i o n V A n a l y s i s , D i a g n o s i s & C o r r e c t i o n of Programs 73 V. 1 T r a p p i n g LISP e r r o r messages 74 V.2 D i a g n o s t i c Models 77 V. 3 A n n o t a t i n g the model w i t h CAVEATS 86 V.4 Co n c l u s i on 93 VI The T u t o r i n g P r o c e s s 94 V I . 1 Te a c h i n g s t r a t e g y 95 V I . 2 Te a c h i n g mechanisms 100 VI.3 The t u t o r i n g a l g o r i t h m 104 V I . 4 C o n c l u s i o n 111 V I I C o n c l u s i o n 112 BIBLIOGRAPHY 27 27 d a t a -34 40 48 70 APPENDIX LIST OF FIGURES PAGE FIGURE 1 The network's r o l e i n the teaching process 26 2 Dataflow r e p r e s e n t a t i o n between sub-segments of the f u n c t i o n REPLACE 32 3 C o n t r o l flow r e p r e s e n t a t i o n for the f u n c t i o n REPLACE 3 3 1 CHAPTER I INTRODUCTION P r e s e n t e d h e r e i n i s a p r o p o s a l and d e s i g n f o r an i n t e l l i g e n t L I S P t e a c h i n g m a c h i n e . The d e s i g n o f t h e m a c h i n e , t h o u g h n o t c o m p l e t e l y o r i e n t e d t o w a r d s i m p l e m e n t a t i o n , t a k e s i n t o a c c o u n t t h e s t u d e n t p o p u l a t i o n w h i c h c o u l d be e x p e c t e d t o make u s e o f s u c h a t u t o r . I t i s e x p e c t e d t h a t s u c h a CAI s y s t e m w o u l d be u s e d i n c o n j u n c t i o n w i t h a s e t o f L I S P n o t e s s u c h as t h o s e w r i t t e n f o r C o m p u t e r S c i e n c e 312 by R . R e i t e r and A . M a c k w o r t h , t o t e a c h s t u d e n t s , w i t h some p r i o r p r o g r a m m i n g k n o w l e d g e , t h e L I S P p r o g r a m m i n g l a n g u a g e and \" c o r r e c t \" p r o g r a m m i n g s t y l e . D e v e l o p m e n t s i n i n t e r a c t i v e CAI and i n a r t i f i c i a l i n t e l l i g e n c e have e n a b l e d t e a c h i n g p r o g r a m s t o d e a l r e a s o n a b l y e f f e c t i v e l y w i t h t h e s u b j e c t m a t t e r t o be t a u g h t . P r e s e n t a t i o n o f c o u r s e m a t e r i a l i s o b v i o u s l y f u n d a m e n t a l t o any t e a c h i n g s y s t e m . T h i s p a p e r does n o t p l a c e t o o much e m p h a s i s on t h i s a s p e c t o f t h e t e a c h i n g m a c h i n e , s i n c e p r e v i o u s w o r k s u c h as SCHOLAR ( C a r b o n e l l , C o l l i n s e t a l , 2 1970, 1975) c o v e r s c o u r s e p r e s e n t a t i o n q u i t e a d e q u a t e l y . T h i s L I S P m a c h i n e w i l l s t i l l have t o c o m m u n i c a t e w i t h s t u d e n t s and d i s c u s s c o n c e p t s and i d e a s r e l a t e d t o t h e b a s i c s y n t a x and s e m a n t i c s o f L I S P . I t i s e n v i s a g e d t h a t i n s t r u c t i o n a l t e x t w i l l be p r e s e n t e d , and q u e s t i o n s on t h e m a t e r i a l c o v e r e d w i l l be a s k e d ( a n d a n s w e r e d ) by e m p l o y i n g a s e m a n t i c n e t w o r k i n t e r r e l a t i n g a f a c t u a l d a t a b a s e o f s t a t i c L I S P i n f o r m a t i o n , s i m i l a r t o , and c o m p l e m e n t i n g t h e L I S P n o t e s m e n t i o n e d a b o v e . A b r i e f d e s c r i p t i o n o f t h e s e m a n t i c n e t w o r k and i t s u s e f u l n e s s i n t h e d i s c u s s i o n o f c o u r s e m a t e r i a l i s p r e s e n t e d i n C h a p t e r I I I . The m a j o r g o a l o f t h e t u t o r w i l l be t o p r o v i d e i n s t r u c t i o n i n L I S P f u n c t i o n d e s i g n t e c h n i q u e s and t o p e r f o r m t h e c o n s e q u e n t e r r o r d e t e c t i o n and c o r r e c t i o n . W i t h t h e b e l i e f t h a t p r o c e d u r a l k n o w l e d g e i s b e s t l e a r n e d by \" d o i n g \" , t h i s CAI s y s t e m w i l l i n t e g r a t e c o n c e p t t e a c h i n g w i t h a c t u a l p r a c t i c e , i . e . t h e s t u d e n t w i l l be a s k e d t o d e s i g n s i m p l e L I S P f u n c t i o n s , t r y i n g o u t t h e c o n c e p t s w h i c h have j u s t b een l e a r n e d , u n d e r t h e s u p e r v i s i o n o f an \" i n t e l l i g e n t \" t e a c h e r . T h i s t u t o r i n g p r o c e s s i s d e c r i b e d i n C h a p t e r V I . The t e a c h e r w i l l a i d t h e s t u d e n t by r e f e r e n c i n g a m o d e l o f t h e f u n c t i o n w h i c h i s t o be d e s i g n e d . C h a p t e r VI a l s o p r e s e n t s t h e 3 a l g o r i t h m s w h i c h r e f e r t o and i n v o k e t h e s e f u n c t i o n m o d e l s , and g i v e s a g e n e r a l i d e a o f t h e e n v i r o n m e n t i n w h i c h s u c h a t u t o r w i l l f u n c t i o n . A c o m p l e t e L I S P f u n c t i o n m o d e l i n g s y s t e m i s d e s c r i b e d i n C h a p t e r IV. T h i s w i l l d e s c r i b e i n d e t a i l how a p a r t i c u l a r L I S P f u n c t i o n i s v i e w e d by t h e s y s t e m , m o d e l l e d i n t e r n a l l y , and p h y s i c a l l y s t o r e d . F u n d a m e n t a l t o t h e L I S P t e a c h i n g m a c h i n e w i l l be t h e a b i l i t y t o a n a l y s e s t u d e n t - p r o d u c e d f u n c t i o n s and t o p r o v i d e e r r o r c o r r e c t i o n and a d v i c e w h e r e n e c e s s a r y . E r r o r d e t e c t i o n and c o r r e c t i o n i s p e r f o r m e d a t a l l l e v e l s i n t h e l e s s o n , i . e . b e f o r e f u n c t i o n d e s i g n , d u r i n g d e s i g n , and upon c o m p l e t i o n o f t h e d e s i g n , i n o r d e r t o d e t e r m i n e w h e t h e r t h e s t u d e n t ' s f u n c t i o n a c t u a l l y \" w o r k s \" o r n o t . I t i s n o t s u f f i c i e n t t o o n l y come up w i t h a \" y e s \" o r \"no\" v e r d i c t , h e n c e t h e a n a l y z e r needs some \" u n d e r s t a n d i n g \" o f t h e L I S P f u n c t i o n i t i s t e s t i n g , i n o r d e r t o p i n p o i n t and d e s c r i b e e r r o r s . C h a p t e r V d i s c u s s e s b o t h t h e d a t a s t r u c t u r e s w h i c h a r e r e q u i r e d t o e n a b l e e r r o r d e t e c t i o n , and t h e p r o c e d u r e s w h i c h w i l l be \" r e a d y t o f i r e \" upon d e t e c t i o n o f any e r r o r s i n t h e s t u d e n t ' s c o d e . O b v i o u s l y t h e s e t h r e e a r e a s , v i z . 4 1) i n s t r u c t i o n in concepts, LISP syntax and semantics; 2) i n s t r u c t i o n in the design of LISP f u n c t i o n s ; and 3 ) a n a l y s i s of student's s o l u t i o n and consequent e r r o r c o r r e c t i o n w i l l not e x i s t i n the t e a c h ing machine as completely separate e n t i t i e s . Nor w i l l they be regarded as three phases to be executed s e q u e n t i a l l y . However, for ease of understanding and design, they w i l l now be d i s c u s s e d and considered s e p a r a t e l y . 5 CHAPTER I I HISTORICAL SURVEY OF CAI T e a c h i n g m a c h i n e s and a u t o m a t e d i n s t r u c t i o n a r e n o t as r e c e n t an i n n o v a t i o n as t h e y a p p e a r t o be. I n t h e f o u r t e e n t h c e n t u r y , f o r e x a m p l e , E n g l i s h grammar s c h o o l s , o w i n g t o t h e l a c k o f p r i n t e d m a t e r i a l , w e r e f o r c e d t o a p p l y an o r a l m e t h o d o f t e a c h i n g w h i c h was b a s e d on t h e p r i n c i p l e s o f programmed i n s t r u c t i o n , n a m e l y r e p e t i t i o n and r e m e d i a l b r a n c h i n g . G r e e n ( 1 9 6 2 ) d e s c r i b e s a q u i n t a i n , a m e d i a e v a l t e a c h i n g m a c h i n e u s e d f o r t h e t e a c h i n g and t r a i n i n g o f k n i g h t s . T h r e e s i g n i f i c a n t e a r l y t e a c h i n g s y s t e m s w e r e d e s i g n e d by P r e s s e y , S k i n n e r and C r o w d e r . S i d n e y L. P r e s s e y o r i g i n a l l y d e s i g n e d h i s t e a c h i n g m a c h i n e i n 1926 as an a u t o m a t i c t e s t i n g d e v i c e , b u t he s o o n r e a l i z e d t h a t m a c h i n e s c o u l d n o t o n l y t e s t and s c o r e , b u t a l s o had i m p o r t a n t i n s t r u c t i o n a l c a p a b i l i t i e s . I n t h e 1950's B . F . S k i n n e r d e s i g n e d t e a c h i n g m a c h i n e s i n s p i r e d by e x p e r i m e n t s on a n i m a l s . T h e s e m a c h i n e s f o l l o w e d t h e b a s i c S k i n n e r P a r a d i g m - a l i n e a r s e q u e n c e o f ' f r a m e s ' e a c h c o n s i s t i n g o f a few w o r d s ( s t i m u l u s ) , a b l a n k f o r t h e f i l l i n g i n o f t h e s t u d e n t ' s answer ( r e s p o n s e ) , and a c o r r e c t answer w h i c h a p p e a r e d t o t h e s t u d e n t a f t e r he had made an a t t e m p t ( r e i n f o r c e m e n t ) . Hence s u c h a S k i n n e r i a n l i n e a r p r o g r a m i s f i x e d i n s e q u e n c e , t h e same m a t e r i a l b e i n g p r e s e n t e d t o a l l s t u d e n t s i n t h e same o r d e r . I n t h e e a r l y 1960's Norman C r o w d e r d e v e l o p e d a p r e - p r o g r a m m e d d e v i c e w h i c h p l a c e d some e m p h a s i s on d i a g n o s i s . M a t e r i a l i s p r e s e n t e d t o s t u d e n t s i n s m a l l l o g i c a l s t e p s e a c h o f w h i c h i s a c c o m p a n i e d by a t e s t . The t e s t q u e s t i o n s a r e m u l t i p l e c h o i c e q u e s t i o n s and t h e r e i s a s e p a r a t e s e t o f c o r r e c t i o n a l m a t e r i a l s f o r e a c h w r o n g answer t h a t i s i n c l u d e d i n t h e m u l t i p l e c h o i c e a l t e r n a t i v e . T h e s e a l t e r n a t i v e s a r e u s e f u l i n d i a g n o s i n g t h e s t u d e n t ' s d i f f i c u l t i e s and a r e a l s o u s e f u l i n p r o v i d i n g f u r t h e r e x p l a n a t i o n o f t h e p r o b l e m . I t was t h e s e e a r l y d e v e l o p m e n t s i n i n s t r u c t i o n a l s y s t e m s , a i d e d by t h e e v o l v e m e n t o f t i m e - s h a r i n g and t h e s u b s t i t u t i o n o f a c o m p u t e r f o r t h e programmed t e x t s o f t h e e a r l y 1 9 6 0 ' s , w h i c h made c o m p u t e r - a i d e d i n s t r u c t i o n a r e a l i t y . The c u r r e n t s t a t e o f CAI i s s t i l l b a s i c a l l y one o f p r o l o n g e d i n f a n c y . A l t h o u g h i t has been u t i l i z e d e x p e r i m e n t a l l y a t many l e v e l s o f e d u c a t i o n , t o d a y i t i s n o t r e a l l y w i d e s p r e a d . CAI d e v e l o p m e n t s have been s o m e t i m e s u n i m a g i n a t i v e and e v e n o p p r e s s i v e , w i t h a l a r g e p e r c e n t a g e o f CAI a p p l i c a t i o n s h a v i n g been t u t o r i a l d r i 1 1 - a n d - t e s t s e q u e n c e s , i n w h i c h t h e s t u d e n t i s d o m i n a t e d d u r i n g i n s t r u c t i o n . T o d a y , h o w e v e r , t h e d e s i g n o f A l - b a s e d t u t o r i n g p r o g r a m s o f f e r s q u a l i t i e s h e r e t o f o r e l a c k i n g i n CAI - s e n s i t i v e and i n t e l l i g e n t i n t e r a c t i o n and p e d a g o g i c a l s t r a t e g i e s . S i m i l a r l y , CAI o f f e r s A I a c h a l l e n g i n g a r e a f o r t e s t i n g t h e e f f e c t i v e n e s s o f s o p h i s t i c a t e d i n f o r m a t i o n p r o c e s s i n g t e c h n i q u e s and c o m p u t a t i o n a l t h e o r i e s . 0 The f i r s t i n t r o d u c t i o n o f c o m p u t e r s i n t o i n s t r u c t i o n a l s y s t e m s was t y p i c a l l y l i t t l e more t h a n an a u t o m a t i c programmed t e x t b o o k . T h i s f r a m e - b a s e d CAI u s e d t h e c o m p u t e r as a page t u r n e r f o r a d e c i s i o n t r e e o f m u l t i p l e c h o i c e q u e s t i o n s , w h e r e i n t h e p a t h t a k e n was d e t e r m i n e d by t h e s t u d e n t ' s a n s w e r . S i m p l e b r a n c h i n g t e c h n i q u e s w e r e i n c l u d e d i n o r d e r t o be more s e n s i t i v e t o t h e s t u d e n t ' s a c t u a l a b i l i t y . S y s t e m s s u c h as PLATO ( B i t z e r e t a l , 1967) and T I C C I T ( B u n d e r s o n , 1974) w e r e u l t i m a t e l y l i m i t e d by t h e i r i n a d e q u a t e u n d e r s t a n d i n g o f t h e c o u r s e work b e i n g t a u g h t , and by t h e i r i n a b i l i t y t o m o d e l t h e t e a c h i n g and l e a r n i n g p r o c e s s . They had no i n i t i a t i v e o r d e c i s i o n power o f t h e i r own, n o r any k n o w l e d g e a v a i l a b l e o t h e r t h a n a t f i x e d p o i n t s i n t h e s e q u e n c e . C o n s e q u e n t l y t h e r e was a s h i f t t o a new p a r a d i g m whose g o a l was t o embed g e n u i n e d omain e x p e r t i s e i n t h e CAI p r o g r a m . The i n c l u s i o n o f A l - b a s e d e x p e r t i s e h e l p e d s u r m o u n t t h e r e s t r i c t i v e n a t u r e o f o l d e r s y s t e m s by s u p p l y i n g a \" r e a c t i v e \" l e a r n i n g e n v i r o n m e n t a b l e t o a n a l y z e a w i d e r r a n g e o f s t u d e n t r e s p o n s e s . T hey have a d v a n t a g e s o v e r t h e e a r l i e r s y s t e m s i n t h a t t h e y a r e more i n t e r e s t i n g t o u s e ; t h e y a l l o w s t u d e n t s ' d e c i s i o n s t o a f f e c t t h e d i r e c t i o n o f t h e s e s s i o n ; and t h e y a r e a b l e t o t e a c h new s k i l l s i n s t e a d o f s i m p l y p r o v i d i n g p r a c t i c e i n a l r e a d y l e a r n e d o n e s . N e c e s s a r i l y t h e s e t u t o r s a r e d o main s p e c i f i c as i s e v i d e n t when one c o n s i d e r s t h e t h r e e most n o t a b l e e f f o r t s , e a c h c o n c e r n e d w i t h a d i f f e r e n t k i n d o f e x p e r t i s e ; v i z . , t h e L o g i c and S e t T h e o r y t u t o r s o f Suppes e t a l ( 1 9 7 2 ) ; t h e G e o g r a p h y t u t o r , SCHOLAR, o f C a r b o n e l l and C o l l i n s ( 1 9 7 0 , 1 9 7 5 ) ; and t h e E l e c t r o n i c s t r o u b l e s h o o t i n g t u t o r , SOPHIE, o f Brown e t a l ( 1 9 7 5 ) . 9 S u p p e s ' w o r k i n CAI a t t h e IMSSS a t S t a n f o r d has s l o w l y f o l l o w e d t h e c h a n g e s i n t h e f i e l d . The g o a l o f t h e L o g i c t u t o r has a l w a y s been t o d e v e l o p a s y s t e m a b l e t o c h e c k t h e v a l i d i t y o f a s t u d e n t ' s p r o o f . W i t h A I t e c h n i q u e s , e s p e c i a l l y t h e u s e o f a s e m a n t i c n e t w o r k f o r s t o r i n g i n f o r m a t i o n , t h e IMSSS has d e v e l o p e d more p o w e r f u l p r o o f c h e c k e r s . A t t h e same t i m e , t h e IMSSS has been i n v o l v e d i n an i n s t r u c t i o n a l p r o g r a m f o r B A S I C ( B I P ) w h i c h i n c o r p o r a t e s a m o d e l o f t h e s t u d e n t , and a s e m a n t i c n e t w o r k f o r r e p r e s e n t i n g k n o w l e d g e a b o u t t h e w o r l d . The c o n c e p t o f a s e m a n t i c n e t w o r k was d e v e l o p e d by Q u i l l i a n ( C o l l i n s and Q u i 1 1 i a n , 1972) and was f i r s t e m p l o y e d as an A I t e c h n i q u e f o r r e p r e s e n t i n g d o m a i n k n o w l e d g e i n a CAI s y s t e m by C a r b o n e l l ' s SCHOLAR s y s t e m . A n e t w o r k s t o r e s c o n c e p t s u n d e r d i f f e r e n t e n t r i e s a c c o r d i n g t o a w e l l d e f i n e d f o r m a t , so t h a t e a c h c o n c e p t c a n be d e s c r i b e d by o t h e r c o n c e p t s e l s e w h e r e i n t h e n e t w o r k . SCHOLAR and a l l i t s l a t e r d e r i v a t i v e s ( c f . C o l l i n s and G r i g n e t t i , 1975) employ s u c h a n e t w o r k i n t h e d e s i g n o f an i n s t r u c t i o n a l s y s t e m t o t e a c h t h e g e o g r a p h y o f S o u t h A m e r i c a . SCHOLAR ' S n e t w o r k f a c i l i t a t e d i n t e r a c t i v e c a p a b i l i t i e s ; i n d i v i d u a l i z a t i o n o f i n s t r u c t i o n ; and e v e n t h e t u t o r i n g o f some p r o c e d u r a l s k i l l s . N o n e t h e l e s s a n e t w o r k 10 i s o n l y b e s t a t m a n i p u l a t i n g s t a t i c i n f o r m a t i o n w h i c h i s i n s u f f i c i e n t f o r c e r t a i n i n s t r u c t i o n . P r o g r a m s s u c h as SOPHIE or WUMPUS ( G o l d s t e i n , 1976, 1978) embed t h e r e a s o n i n g s k i l l s t o be t a u g h t i n t h e s t r u c t u r e o f t h e p r o g r a m i t s e l f . By i n t e r a c t i n g w i t h t h e c o m p u t e r , s t u d e n t s l e a r n t o m i m i c and so a c q u i r e t h e s e s k i l l s . SOPHIE, a s o p h i s t i c a t e d i n s t r u c t i o n a l e n v i r o n m e n t f o r t u t o r i n g e l e c t r o n i c t r o u b l e s h o o t i n g , i s v e r y much an e x p e r t - b a s e d s y s t e m . I t compares a s t u d e n t ' s t r o u b l e s h o o t i n g l o g i c f o r an e l e c t r o n i c c i r c u i t w i t h t h a t o f i t s e x p e r t and o f f e r s a d v i c e w h e r e v e r p o s s i b l e . U n f o r t u n a t e l y t h i s embedded k n o w l e d g e i s a b l a c k box t o t h e s t u d e n t s i n c e SOPHIE has no a c c e s s t o a m o d e l o f human o r i e n t e d t r o u b l e s h o o t i n g s k i l l s , n o r does i t have any r e p r e s e n t a t i o n f o r t h e a c q u i s i t i o n o f t h e s e s k i l l s . P o s s i b l y t h e g r e a t e s t w e a k n e s s o f t h e s e k n o w l e d g e - b a s e d t u t o r s i s t h e i r e l e m e n t a r y t u t o r i n g t h e o r y and s t r a t e g y . They c o n s i d e r e x p e r t i s e t o be a s e t o f f a c t s o r r u l e s , w h e r e a s we c o n s i d e r i t t o be an e v o l u t i o n a r y p r o c e s s , and h e n c e p r e f e r t o m o d e l t h e k n o w l e d g e and a c q u i s i t i o n o f t h e k n o w l e d g e as one. T h i s i n c l u s i o n o f e x p e r t i s e r e g a r d i n g l e a r n i n g b e h a v i o u r and t u t o r i n g s t r a t e g i e s c h a r a c t e r i z e s t h e A I C A I t u t o r s ( i . e . a r t i f i c i a l l y i n t e l l i g e n t c o m p u t e r - a i d e d 11 i n s t r u c t i o n ) . The m a i n f u n c t i o n o f i n t e l l i g e n t t u t o r s i s t o a s s i s t s t u d e n t s , t o a c t as c o n s u l t a n t s , and most i m p o r t a n t t o c o a c h s t u d e n t s , h e l p i n g them surmount c u r r e n t d i f f i c u l t i e s t o r e a c h a new p l a t e a u o f a b i l i t y . The BUGGY s y s t e m o f Brown and B u r t o n ( 1 9 7 7 ) c o n s t r u c t s a m o d e l o f s t u d e n t s ' a r i t h m e t i c s k i l l s as d e v i a t i o n s f r o m t h e c o r r e c t m e t h o d s . T h e r e i s n o t , h o w e v e r , much e f f o r t made i n f e e d i n g b a c k t h e d e v i a t i o n s t o t h e s t u d e n t i n o r d e r t o h e l p c o r r e c t h i s / h e r a r i t h m e t i c p r o c e s s . R a t h e r , t h e s e d e v i a t i o n s a r e f i l e d away f o r l a t e r a n a l y s i s , o n l y a f f e c t i n g s t u d e n t s by t h e manner i n w h i c h t h e y a f f e c t r e v i s i o n s o f t h e t e a c h i n g m a t e r i a l . M ore r e l a t e d t o o u r p a r t i c u l a r L I S P t u t o r a r e t h e B I P I I p r o j e c t o f W e s t c o u r t e t a l ( 1 9 7 7 ) , P S I o f G r e e n and B a r s t o w ( 1 9 7 7 ) and MALT o f K o f f m a n and B l o u n t ( 1 9 7 5 ) . T h e s e t h r e e s y s t e m s a l l f a l l w i t h i n t h e IC A I g e n e r a t i o n and a r e d e s i g n e d s p e c i f i c a l l y f o r t e a c h i n g p r o g r a m m i n g l a n g u a g e s o r g e n e r a t i n g p r o g r a m s . The B I P I I s y s t e m a t t e m p t s t o t e a c h B A S I C p r o g r a m m i n g by e m p l o y i n g a u t h o r - s u p p l i e d e x e r c i s e s as p r a c t i c e s e s s i o n s f o r t h e p a r t i c u l a r s k i l l s b e i n g t a u g h t . Thus t h e r e i s an u n f o r t u n a t e d i s t i n c t i o n b e t w e e n s k i l l and p r a c t i c e , c a u s e d by t h e a b s e n c e o f a m o d e l l i n k i n g t h e o r e t i c a l s k i l l s t o p r a c t i c a l 12 i m p l e m e n t a t i o n s . N or i s t h e r e any a t t e m p t made t o d e s c r i b e d e v i a t i o n s f r o m t h e s k i l l , o r t o d e s c r i b e t h e p r o c e s s o f l e a r n i n g a s k i l l i t s e l f . MALT, a t u t o r f o r m a c h i n e l a n g u a g e p r o g r a m m i n g , does i n c l u d e some e x p e r t i s e f o r d e t e r m i n i n g t h e d e g r e e o f c o r r e c t n e s s o f a s t u d e n t ' s e f f o r t . U s i n g a l i n e - b y - l i n e a p p r o a c h , t h e r e i s a l s o some e f f o r t made t o h e l p t h e s t u d e n t i n h i s / h e r p r o d u c t i o n o f a m a c h i n e l a n g u a g e p r o g r a m . T h i s l i n e - b y - l i n e a p p r o a c h i s o f t e n s u c c e s s f u l , b u t i n t h e l o n g r u n i t does n o t t e a c h a g l o b a l p r o g r a m m i n g s t r a t e g y , n o r does i t f a c i l i t a t e g e n e r a l i z a t i o n o f one p a r t i c u l a r s k i l l i n t o a s t a n d a r d t e c h n i q u e . MALT's s y l l a b u s o f s k i l l s a r e r e l a t e d o n l y by t h e p r o b a b i l i t y o f b e i n g i n c l u d e d i n a p a r t i c u l a r g e n e r a t e d p r o b l e m and n o t by any e v o l u t i o n a r y l i n k s . Hence i t does n o t p r o v i d e t h e f r a m e w o r k f o r t e a c h i n g a c o m p l e t e p r o g r a m m i n g l a n g u a g e f r o m t h e b a s i c s u p w a r d s , b u t i t does p r o v i d e a c o m p e t e n t e x e r c i s e r f o r p r a c t i c i n g p r e v i o u s l y l e a r n e d p r o g r a m m i n g s k i l l s . The P S I p r o g r a m s y n t h e s i s s y s t e m i s a p r o g r a m t h a t a c q u i r e s h i g h - l e v e l E n g l i s h s e n t e n c e s d e s c r i b i n g p r o g r a m s , and p r o d u c e s p a r t i a l i m p l e m e n t a t i o n s o f t h e s e p r o g r a m s i n L I S P o r S A I L . An a c q u i s i t i o n p h a s e p a r s e s E n g l i s h s e n t e n c e s , i n t e r p r e t s them i n t o f r a g m e n t s a n d , u s i n g a g e n e r a l m o d e l o f 13 c o r r e c t c o m p l e t e p r o g r a m m i n g , a m o d e l b u i l d e r b u i l d s a s p e c i f i c m o d e l f o r t h e p r o g r a m f r o m t h e s e f r a g m e n t s . The s y n t h e s i s p h a s e t h e n u s e s h e u r i s t i c s t o s u c c e s s f u l l y r e f i n e / c r e a t e a p r o g r a m w h i c h s a t i s f i e s t h e p r o g r a m m o d e l . PS I i s m o d e r a t e l y s u c c e s s f u l a t p r o d u c i n g s i m p l e p r o g r a m s o f a p a r t i c u l a r c l a s s ( e . g . e x c h a n g e s o r t s ) , b u t l i k e R i c h and S c h r o b e ' s L I S P p r o g r a m m i n g a p p r e n t i c e ( 1 9 7 6 ) , i t i s n o t g e a r e d t o w a r d s C A I . They w e r e d e s i g n e d as a i d s f o r e x p e r i e n c e d p r o g r ammers and w o u l d f a i l m i s e r a b l y i f t h e y w e r e u s e d t o t e a c h s t u d e n t s who know v e r y l i t t l e a b o u t L I S P p r o g r a m m i n g . Thus we have s e e n two t r e n d s i n t h e a r e a o f t e a c h i n g p r o g r a m m i n g . T h e r e a r e s y s t e m s s u c h as MALT and B I P w h i c h have some d i a g n o s i s a b i l i t y and s t r a t e g y t e a c h i n g , b u t do no t i n c o r p o r a t e t h e s e i n t o one g e n e r a l m o d e l . T h e s e s y s t e m s somehow s e p a r a t e t h e p r o c e s s o f l e a r n i n g a l a n g u a g e , i t s t e c h n i q u e s and s u b t l e t i e s , f r o m t h e p r o c e s s o f p r o g r a m m i n g i n t h a t l a n g u a g e . On t h e o t h e r h a n d , t h e r e a r e s y s t e m s s u c h as PSI and R i c h and S c h r o b e ' s p r o g r a m m i n g a p p r e n t i c e w h i c h a r e v e r y , c a p a b l e o f h e l p i n g a s t u d e n t p r o d u c e a p r o g r a m . They do empl o y some m o d e l b u t do n o t a t t e m p t t o p e r f o r m d i a g n o s i s , n o r do t h e y e n u n c i a t e a n d / o r c l a r i f y t h e s k i l l s 14 and s t r a t e g i e s w h i c h a r e u s e d i n t h e p r o g r a m m i n g p r o c e s s . I t w o u l d t h e r e f o r e seem t h a t any s y s t e m w h i c h u t i l i z e s a d a t a - b a s e o f s k i l l s , t e c h n i q u e s , p r o g r a m m o d e l s and d i a g n o s t i c i n f o r m a t i o n , t o h e l p a s t u d e n t c r e a t e a p r o g r a m t o p e r f o r m a c e r t a i n t a s k , w o u l d be a much more s u c c e s s f u l c o a c h and t u t o r . Such a s y s t e m w o u l d n o t d i v o r c e t h e a c t o f p r o g r a m m i n g f r o m t h e p r o c e s s o f l e a r n i n g t h e s k i l l s , l a n g u a g e and t e c h n i q u e s n e c e s s a r y f o r p r o g r a m m i n g . A p a r t f r o m t h e f i e l d s o f A l and CAI t h e r e a r e o t h e r a r e a s i n c o m p u t e r s c i e n c e , p s y c h o l o g y , and p e d a g o g y w h i c h have made s u b s t a n t i a l c o n t r i b u t i o n s t o A I C A I . New c o n c e p t s o f c o g n i t i v e p s y c h o l o g y , s u c h as p r o d u c t i o n s y s t e m s and s e m a n t i c n e t s , have been u s e d t o m o d e l memory and s i m p l e human i n f o r m a t i o n p r o c e s s i n g ( c f N e w e l l and Simon's Human P r o b l e m S o l v i n g , 1 9 7 2 ) . T h e s e a r e i n v a l u a b l e i n i n t e l l i g e n t CAI f o r r e p r e s e n t i n g k n o w l e d g e and l e a r n i n g m o d e l s o f s t u d e n t s . G o l d s t e i n ( 1 9 7 4 , 1976) began t h e i m p o r t a n t work o f c l a s s i f y i n g p l a n t y p e s , and i n t r o d u c e d t h e i d e a o f \" d e b u g g i n g a l m o s t - r i g h t p l a n s \" . G o l d s t e i n and M i l l e r ' s SPADE ( 1 9 7 6 ) and PAZATN ( 1 9 7 6 ) have i n v e s t i g a t e d p r o b l e m s o l v i n g , p l a n n i n g and d e b u g g i n g i n h i g h l y c o n s t r a i n e d d o m a i n s s u c h as t h e d r a w i n g o f s t i c k f i g u r e s on a TV s c r e e n . They c o m p i l e d 15 t some i m p o r t a n t s t r a t e g i e s i n t o an augmented t r a n s i t i o n n e t w o r k PAZATN and a grammar SPADE w h i c h c a n be u s e d t o g e n e r a t e and r e c o g n i z e s i m p l e s t i c k p i c t u r e s . P r o g r e s s has a l s o been made on t h e p r o b l e m s o f p r o g r a m m i n g . R i c h and S c h r o b e ( 1 9 7 6 ) have d e s i g n e d a L I S P p r o g r a m m i n g a p p r e n t i c e w h i c h w o u l d a i d an e x p e r t programmer i n d e s i g n i n g , i m p l e m e n t i n g , d e b u g g i n g and m a i n t a i n i n g a l a r g e p r o g r a m . T h e i r i d e a s c o n t r i b u t e d t o my d e s i g n o f s t r u c t u r e s f o r r e p r e s e n t i n g p l a n s o f d a t a f l o w , c o n t r o l f l o w , g o a l and s u b g o a l r e l a t i o n s h i p s w i t h i n a L I S P p r o g r a m . G r e e n and B a r s t o w ( 1 9 7 6 , 1 9 7 7 ) , as m e n t i o n e d e a r l i e r , h ave c o m p i l e d a s e t o f r u l e s a b o u t L I S P p r o g r a m m i n g w h i c h h a v e • been i n c o r p o r a t e d i n t o t h e i r P S I a u t o m a t i c p r o g r a m m i n g p r o j e c t . R u t h ' s p r o g r a m a n a l y z e r ( 1 9 7 6 ) r e p r e s e n t s a c l a s s o f e x p e c t e d p r o g r a m s ( e . g . f o r b u b b l e s o r t i n g ) as a f o r m a l grammar. R u t h t h e n u s e s t h e grammar t o u n d e r s t a n d and a n a l y z e a v a r i e t y o f p r o g r a m s . T h e r e i s n o t , h o w e v e r , any e x p l i c i t i n f o r m a t i o n as t o what t h e p r o g r a m a c h i e v e s , n o r i s t h e r e any d i v i s i o n o f t h e end g o a l i n t o s i m p l e r s u b - g o a l s . W i t h no c o n c e p t s o f p r e - r e q u i s i t e s u b - g o a l s , o r n e c e s s a r y c o n d i t i o n s upon e n t r y t o d i f f e r e n t p a r t s o f t h e p r o g r a m , R u t h ' s a n a l y z e r w o u l d be an u n s u c c e s s f u l p e d a g o g i c a l t o o l . B o t h R u t h ' s a n a l y z e r and t h e P S I s y s t e m w e r e d e v e l o p e d f o r s y n t h e s i z i n g p r o g r a m s , and a l t h o u g h t h e y a r e i n f o r m a t i v e and u s e f u l as s u c h , t h e i r p r i n c i p l e s o f d e s i g n do n o t l e n d v e r y e a s i l y t o p r o g r a m a n a l y s i s and e x p l a n a t i o n . A u t o m a t i c p r o g r a m m i n g i m m e d i a t e l y b r i n g s t o m i n d t h e p r o b l e m o f p r o g r a m v e r i f i c a t i o n . W e l l known w o r k i n C o m p u t e r S c i e n c e , e s p e c i a l l y by F l o y d and Manna, show t h a t l o g i c c a n be u s e d t o a n a l y z e p r o g r a m s . I n f a c t , s i n c e t h e c o r r e c t n e s s and e q u i v a l e n c e p r o b l e m s c a n o f t e n be f o r m u l a t e d and v i e w e d as a t e r m i n a t i o n p r o b l e m (Manna 1969, C h ang and L e e 1 9 7 3 ) , i t i s p o s s i b l e t o show t h a t p r o g r a m v e r i f i c a t i o n i s n o t d e c i d a b l e . A t t e m p t s a t ( p a r t i a l ) v e r i f i c a t i o n h ave been made t h o u g h , and t h e y have d i s p l a y e d some s u c c e s s i n d e a l i n g w i t h l i m i t e d d o m a i n p r o g r a m s . Our d i f f e r e n c e s w i t h t h i s m a t h e m a t i c a l - c o m p u t e r s c i e n c e a p p r o a c h t o v e r i f i c a t i o n and a n a l y s i s i s t h a t i t s t a r t s w i t h l a n g u a g e p r i m i t i v e s and m a t h e m a t i c a l l y r e l a t e s t h e i r b e h a v i o u r t o t h a t o f t h e e l a b o r a t e p r o g r a m . T h i s i s t h e o r e t i c a l l y v e r y s o u n d , b u t 9 y i e l d s a r e l a t i o n s h i p so c o m p l e x t h a t i t c a n h a r d l y be u s e d as an e x p l a n a t o r y t o o l o r l e s s o n g u i d e f o r s t u d e n t s who a r e j u s t l e a r n i n g t h e l a n g u a g e . A l e s s c o m p l e t e , b u t more u s e f u l , v e r i f i c a t i o n a p p r o a c h i s a h i e r a r c h i c a l d e s r i p t i o n 17 o f t h e p r o g r a m , w i t h p l a n s and s p e c i f i c a t i o n s a t e a c h l e v e l c o m p l e m e n t e d by d i a g n o s i s , d e b u g g i n g and s u g g e s t i o n s , w h i c h w i l l h o p e f u l l y h e l p t h e s t u d e n t p r o d u c e a c o r r e c t p r o g r a m . Thus t h e b a s i c i d e a b e h i n d o u r L I S P t u t o r i s as f o l l o w s : -t o t e a c h p r o g r a m m i n g , an i n t e l l i g e n t t u t o r must g u i d e a s t u d e n t t h r o u g h t h e a n a l y s i s o f a p r o b l e m t o t h e p r o d u c t i o n o f t h e p r o g r a m by r e f e r e n c i n g a m o d e l o f t h a t p r o b l e m and i t s s o l u t i o n ; by e n u n c i a t i n g t h e s k i l l s and t e c h n i q u e s as t h e y a r e r e q u i r e d and added t o t h e r e p e r t o i r e ; by a l l o w i n g some f o r m o f i n t e r a c t i o n and s u b s e q u e n t r e f e r e n c e s t o o t h e r m a t e r i a l ; and by p e r f o r m i n g d i a g n o s i s a t a l l l e v e l s t h r o u g h o u t t h e l e s s o n . The g o a l i s s i m p l y t o a c t l i k e a human t u t o r - c o g n i z a n t o f what t h e s t u d e n t i s d o i n g a l l t h e t i m e , and a b l e t o p r o v i d e a d v i c e and g i v e d i r e c t i o n w h e r e n e c e s s a r y . CHAPTER I I I THE SEMANTIC NETWORK AND INSTRUCTION OF TIME-INVARIANT CONCEPTS I t i s p r o p o s e d t h a t a s e m a n t i c n e t w o r k be u s e d t o s t o r e and en c o d e t i m e - i n v a r i a n t c o n c e p t s , w h i c h a r e t o be t a u g h t and r e f e r r e d t o by t h e c o m p l e t e L I S P t e a c h i n g m a c h i n e . I t must be e m p h a s i z e d t h a t t h i s a s p e c t o f t h e t e a c h i n g m a c h i n e w i l l n o t be s t r e s s e d o u t s i d e t h i s c h a p t e r . C e r t a i n l y , t h e r e w i l l be no a t t e m p t made t o im p l e m e n t s u c h a n e t w o r k , n o r w i l l t h e a c t u a l d e s i g n , o f a s e m a n t i c n e t w o r k be d i s c u s s e d . Any work i n t h i s a r e a w o u l d m e r e l y be a d u p l i c a t i o n o f t h e e f f o r t o f p e o p l e l i k e C o l l i n s and G r i g n e t t i ( 1 9 7 5 ) ; B a r r , B e a r and A t k i n s o n ( 1 9 7 4 ) ; and C a r b o n e l l ( 1 9 7 0 ) . S i n c e s u c h a n e t w o r k , h o w e v e r , w o u l d be o f m a j o r s i g n i f i c a n c e i n t h e d e s i g n o f a c o m p l e t e L I S P t e a c h i n g m a c h i n e , some d i s c u s s i o n o f i t s s t r u c t u r e , p u r p o s e and d e s i g n , i s n e c e s s a r y t o p l a c e t h e p r o p o s e d s y s t e m i n p r o p e r p e r s p e c t i v e . I t i s e n v i s a g e d t h a t i n a c o m p l e t e s y s t e m t h e s e m a n t i c n e t w o r k w o u l d be a t t h e c o r e o f t h e l e a r n i n g p r o c e s s . I t w o u l d i l l u s t r a t e t h e i n t e r r e l a t i o n s h i p s b e t w e e n c o n c e p t s ; s t o r e i n f o r m a t i o n a b o u t t h e s y n t a x and s e m a n t i c s o f L I S P c o d e ; s t o r e a s t u d e n t l e a r n i n g m o d e l t o p r e s e n t e a c h s t u d e n t w i t h an i n d i v i d u a l i z e d l e s s o n ; d e t e r m i n e t h e f l o w o f a l e s s o n , l i n k i n g s k i l l s t o p r o b l e m s , s u b - p r o b l e m s , and s o l u t i o n s ; and f i n a l l y , t h e n e t w o r k w o u l d make r e f e r e n c e t o t h e t e x t s and a v a i l a b l e m a n u a l s . I n a s e m a n t i c n e t w o r k , i n f o r m a t i o n a b o u t c o n c e p t s i s s t o r e d u n d e r d i f f e r e n t e n t r i e s a c c o r d i n g t o a w e l l d e f i n e d f o r m a t so t h a t e a c h u n i t i n t h e n e t may r e f e r t o o t h e r u n i t s w h i c h a r e r e l a t e d t o t h a t u n i t i n a m e a n i n g f u l manner. C o n c e p t s a r e t h e b a s i c c o m p o n e n t s o f t h e n e t w o r k and may be t h o u g h t of as p i e c e s o f i n f o r m a t i o n t o w h i c h we u s u a l l y a s s i g n a name. S i n c e c o n c e p t s a r e d e f i n e d i n t e r m s o f any a n d / o r e v e r y o t h e r c o n c e p t , t h e r e e x i s t s no p r i m i t i v e o r u n d e f i n e d t e r m . Thus t h e r e i s k n o w l e d g e a b o u t e v e r y c o n c e p t w h i c h t h e L I S P t e a c h e r m i g h t u s e . I n f o r m a t i o n a b o u t a c o n c e p t i s s t o r e d i n a l i s t o f p r o p e r t i e s , w h i c h c a n e i t h e r i n c l u d e t h e names o f o t h e r c o n c e p t s o r p o i n t t o o t h e r c o n c e p t s . I n o t h e r w o r d s , e a c h p r o p e r t y c o n s i s t s of two p a r t s : - i t s name ( a t t r i b u t e ) and i t s v a l u e . These v a l u e s can e i t h e r be p o i n t e r s to some ot h e r concept m o d i f i e d by o t h e r p r o p e r t i e s , or the v a l u e s can be a set of p r o p e r t i e s ( a t t r i b u t e - v a l u e p a i r s ) themse1yes. For example, the concept \"SUN\" has a l i s t of p r o p e r t i e s one of which would be the a t t r i b u t e COLOUR w i t h v a l u e YELLOW. However, as mentioned above, p r o p e r t i e s can be more complex. Thus f o r the concept \"CANARY\", the v a l u e of the a t t r i b u t e COLOUR may have embedded o t h e r p r o p e r t i e s t o i n d i c a t e the f a c t t h a t the y e l l o w c o l o u r i s o n l y on the s u r f a c e (as opposed to gr a s s b e i n g green t h r o u g h o u t ) . E.g. (CONCEPT CANARY (PROP-LI ST 0 (COLOUR (YELLOW (DEPTH SURFACE) (SIZE (SMALL (SIMILAR ROBIN) )) Thus one of the p r o p e r t i e s of a CANARY i s t h a t i t s SIZE has v a l u e SMALL and t h a t t h i s p r o p e r t y i n c l u d e s the f u r t h e r p r o p e r t y t h a t a CANARY i s SIMILAR to a ROBIN i n SIZE. (SHADE LIGHT) )) )) 21 There i s however, no 1-1 correspondence between concepts and words or names. . Concepts need not have names, but can s i m p l y be a c o l l e c t i o n of p r o p e r t i e s . Moreover, a word w i t h two meanings, can have two concepts a s s o c i a t e d w i t h i t ; two words may be synonymous w i t h the same co n c e p t , e.g. buy and purchase; and two words may r e f e r t o the same a c t i v i t y , e . g . buy and s e l l . There a l s o e x i s t s p e c i a l p r o p e r t y a t t r i b u t e s which p e r m i t i n f e r e n c e s over the network. These are the s u p e r s e t or s u p e r o r d i n a t e r e l a t i o n s such t h a t a l l p r o p e r t i e s of a s u p e r s e t ( p e o p l e ) a l s o h o l d f o r i n s t a n c e s of t h a t s u p e r s e t ( J o h n ) . Two s u p e r s e t r e l a t i o n s used i n the Geography t u t o r system, SCHOLAR, are SUPERCONCEPT (ARGENTINA - COUNTRY) and SUPERPART (ARGENTINA - SOUTH AMERICA). S i n c e t h e r e o f t e n e x i s t s more than one s u p e r s e t f o r a con c e p t , (DOG - ANIMAL - MAMMAL - LIVE ORGANISM), s u p e r s e t s form c h a i n s a l o n g which i n f e r e n c e s can be made. Q u i l l i a n and C o l l i n s (1972) make r e f e r e n c e t o o t h e r s p e c i a l p r o p e r t y a t t r i b u t e s w hich would a l l o w the same set of i n f e r e n c e s as a s u p e r s e t would, but w i t h l e s s c e r t a i n t y , e.g. SIMILARITY, PROXIMITY, CAUSALITY, e t c . These types of r e l a t i o n s or a t t r i b u t e s form the b a s i s f o r o r g a n i s i n g semantics and g r o u p i n g c o n c e p t s , s i n c e they not o n l y f u n c t i o n as i n f o r m a t i o n b a s k e t s , but a l s o f o r c a r r y i n g i n f e r e n c e s . 2 2 Part of the data base for h o l d i n g i n f o r m a t i o n about LISP might look l i k e t h i s : (CONCEPT CONS (PROP-LIST (SUPERCONCEPT SYSTEM-FUNCTION) (OPERAND (S-EXP S-EXP) ) (RETURN (CONSCELL (CAR-PART (EVALD (S-EXP (POSITION 1) ))) (CDR-PART (EVALD (S-EXP (POSITION 2) ))) ) ) ) i . e . the f u n c t i o n CONS takes two S-expressions and returns a c o n s - c e l l whose CAR is the value of the f i r s t S-expression and whose CDR i s the value of the second S-expression. (CONCEPT CAR (PROP-LIST (SUPERCONCEPT SYSTEM-FUNCTION) (OPERAND (S-EXP (NOT ATOM)) ) (RETURN (ELEMENT (POSITION 1) (FROM LIST) ) (CAR-PART (FROM DOT-PAIR)) )) (PROP-LI ST (SUPERCONCEPT POINTER) (SUPERPART CONSCELL (POSITION 1)) ) ) ) T h i s i l l u s t r a t e s that CAR i s a f u n c t i o n which returns e i t h e r the f i r s t element of a l i s t , or the c a r - p o i n t e r of a dotted p a i r . It i s a l s o a p o i n t e r to the f i r s t , part of a c o n s - c e l 1 . It is p o s s i b l e to imagine how in f o r m a t i o n s t o r e d i n the 2 4 a b o v e n e t w o r k s t r u c t u r e c a n be u s e d by d i f f e r e n t p r o c e d u r e s ( W e x l e r , 1970; G r i g n e t t i & W a r n o c k , 1973) t o f o r m u l a t e q u e s t i o n s , e v a l u a t e s t u d e n t a n s w e r s , answer q u e s t i o n s , and g e n e r a l l y a c h i e v e a d e g r e e o f f r e e d o m f o r E n g l i s h e x p r e s s i o n . The s e m a n t i c n e t w o r k c a n be s e a r c h e d t o f i n d i n f o r m a t i o n , o r c o m p u t a t i o n s and i n f e r e n c e s c a n be a p p l i e d t o r e t r i e v e i n f o r m a t i o n n o t s t o r e d d i r e c t l y on t h e n e t w o r k . I t i s e n v i s a g e d t h a t t h e s e m a n t i c n e t w o r k c a n be u s e d f o r more t h a n t h e s t o r a g e o f b a s i c L I S P c o n c e p t s , o p e r a t i o n s and c o d e . The n e t w o r k c o u l d i n f a c t be t h e d r i v e r o f t h e w h o l e s t u d e n t - t u t o r d i a l o g u e , i n t e r r e l a t i n g m a n u a l r e f e r e n c e s , b a s i c L I S P c o n c e p t s , s k i l l s , h i n t s , t a s k s , p r o b l e m s and e r r o r s . F i r s t o f a l l , t h e n e t w o r k c a n be u s e d f o r d r i l l i n L I S P s y n t a x and s e m a n t i c s , w i t h r e f e r e n c e t o t h e m a n u a l and b a s i c e x a m p l e s s i m i l a r t o t h o s e i n t h e n o t e s by R e i t e r and M a c k w o r t h . T h e r e a f t e r t h e n e t w o r k c o u l d p r o v i d e t h e s t u d e n t w i t h i n f o r m a t i o n a b o u t a p r o b l e m t o be s o l v e d . T h i s p r o b l e m , p r e v i o u s l y d e s i g n e d by t h e t e a c h e r , c o u l d \"be d i s c u s s e d \" by t h e t e a c h i n g m a c h i n e w i t h r e f e r e n c e t o t h e s k i l l s r e q u i r e d . T h e s e s k i l l s and h i n t s c o u l d be l i n k e d t o g e t h e r i n t h e n e t w o r k a l o n g some p a t h f r o m t h e p r o b l e m t o be s o l v e d . T h e r e a f t e r , t h e t e a c h i n g m a c h i n e w o u l d p r o v i d e t h e s t u d e n t w i t h i n s t r u c t i o n i n t h e d e s i g n o f a L I S P f u n c t i o n t o s o l v e t h e p r o b l e m ; a n a l y s e t h e s t u d e n t ' s s o l u t i o n ; d e t e c t and c o r r e c t e r r o r s ; and f i n a l l y r e t u r n t o t h e n e t w o r k f o r f u r t h e r i n s t r u c t i o n i n p o s s i b l y more s o p h i s t i c a t e d c o n c e p t s and s k i l l s . A s c h e m a t i c i l l u s t r a t i o n o f t h e n e t w o r k ' s p r o p o s e d r o l e i n t h e t e a c h i n g p r o c e s s i s p r o v i d e d b e l o w . 26 LiflA The n e t w o r k ' s r o l e i n t h e t e a c h i n g p r o c e s s i V i ! Presentation o f course m a t e r i a l ( I n s t r u c t i o n a l Program) 7S~ Notes on LISP syntax and seman-t i c s . Examples i l l u s t -r a t i n g the notes. I n s t r u c t i o n i n the d e s i g n o f LISP f u n c t i o n s t o s o l v e a problem r e l a t e d t o the course m a t e r i a l . X * i i ! A n a l y s i s of student's s o l u t i o n . E r r o r d i a g n o s i s , c o r r e c t i o n & m o d i f i c a t i o n advice. >- o References t o v a r i o u s t e x t s & manuals Problems a s s o c i a t e d with course m a t e r i a l I n t e r n a l models of f u n c t i o n s students are t o design. Expected r e s u l t s o f e v a l u a t i o n of the f u n c t i o n s . N E T W O R K Information / data flow C o n t r o l flow 27 CHAPTER IV MODELLING L I S P FUNCTIONS IV. 1 I n t r o d u c t i o n The u l t i m a t e g o a l o f t h i s L I S P t u t o r i s t o p r o v i d e a s y s t e m o f d e s i g n and d e b u g g i n g a i d s , t o h e l p a c o m p u t e r s c i e n c e s t u d e n t p r o d u c e a c o r r e c t p r o g r a m w h i c h s o l v e s a s p e c i f i c , g i v e n p r o b l e m . The l i m i t a t i o n o f t h e t a s k t o one p a r t i c u l a r p r o g r a m a t one p a r t i c u l a r t i m e a l l o w s t h e i n c o r p o r a t i o n ' o f s p e c i f i c k n o w l e d g e t o a i d t h e t u t o r . To s t o r e t h i s k n o w l e d g e , s p e c i f i c t o a, p r o g r a m , t h e s y s t e m must p r o v i d e s t r u c t u r e s e n a b l i n g t h e d e s i r e d p r o g r a m t o be a c c u r a t e l y m o d e l l e d . T h e s e s t r u c t u r e s w h i c h m o d e l L I S P p r o g r a m s and p r o v i d e a f r a m e w o r k f o r t e a c h i n g a r e now d e s c r i b e d b e l o w . They r e f l e c t t h e work done by R i c h and S c h r o b e ( 1 9 7 4 , 1 9 7 8 ) , on a L I S P p r o g r a m m e r ' s a p p r e n t i c e , G r e e n and B a r s t o w ( 1 9 7 6 , 1 9 7 7 ) , on a s e m i - a u t o m a t i c p r o g r a m m i n g s y s t e m , and G o l d s t e i n ( 1 9 7 4 , 1 9 7 7 ) , on u n d e r s t a n d i n g p i c t u r e p r o g r a m s and a n n o t a t e d p r o d u c t i o n s y s t e m s . 28 U n d e r l y i n g t h e d e s i g n o f t h e L I S P f u n c t i o n m o d e l l i n g s t r u c t u r e s i s t h e a s s u m p t i o n t h a t i t i s b o t h p o s s i b l e and d e s i r a b l e t o i n s t r u c t s t u d e n t s i n a p r o c e d u r a l , \"how t o do i t \" t y p e o f k n o w l e d g e d o m a i n , by s u b d i v i d i n g p r o g r a m s ( p r o b l e m s ) i n t o l o g i c a l s u b t a s k s . E a c h o f t h e s e s u b - p r o b l e m s c a n be \" t a u g h t \" by t h e s y s t e m and s o l v e d by t h e s t u d e n t , w i t h o u t t o o much r e f e r e n c e t o t h e g l o b a l p r o b l e m . A t a p r o g r a m m i n g l e v e l , t h i s a s s u m p t i o n i m p l i e s t h a t s t u d e n t s a r e e n c o u r a g e d t o p e r f o r m a b r e a k d o w n o f p l a n s i n t o s m a l l e r g o a l s , and t o p r o d u c e p r o g r a m s by c o n s t r u c t i n g and a m a l g a m a t i n g s m a l l e r p i e c e s o f c o d e . A t a d e s i g n l e v e l t h i s i m p l i e s t h a t a f u n c t i o n m o d e l w i l l s i m p l y c o n s i s t o f s u c c e s s i v e l y s i m p l e r m i n i - m o d e l s w h i c h , t o g e t h e r , f o r m t h e h i g h e r l e v e l m o d e l . I t must be e m p h a s i z e d t h a t t h i s a s s u m p t i o n does not n e c e s s a r i l y a c c e p t t h a t t h e w h o l e i s e q u a l t o t h e sum o f t h e p a r t s . I n f a c t , e v e n t h o u g h code w i l l be p r o d u c e d i n a p i e c e - m e a l f a s h i o n , i t i s e n v i s a g e d t h a t t h e r e w i l l be g l o b a l t u t o r i n g and e r r o r d i a g n o s i s w h i c h w i l l e x a m i n e t h e p r o b l e m as a w h o l e . As d e s c r i b e d e a r l i e r a p r o g r a m i s v i e w e d as c o n t r i v e d m e c h a n i s m c o n s t r u c t e d f r o m p a r t s a \" d e l i b e r a t e l y whose b e h a v i o r s 29 a r e c o m b i n e d t o p r o d u c e t h e b e h a v i o r o f t h e w h o l e \" . ( R i c h , S c h r o b e e t a l , 1 9 7 8 ) . P r o g r a m m e r s u n d e r s t a n d and c o n s t r u c t t h e i r p r o g r a m s i n t e r m s o f t h e e f f e c t s o f u n i t s o f b e h a v i o u r , w h i c h a r e l i n k e d t o g e t h e r as some h i e r a r c h i c a l n e t w o r k . A t one l e v e l t h e s e u n i t s o f b e h a v i o u r r e p r e s e n t i d e a s o r p l a n n i n g i n f o r m a t i o n , and a t a l o w e r l e v e l t h e y r e p r e s e n t p i e c e s o f L I S P c o d e . We r e f e r t o t h e s e u n i t s as SEGMENTS. C o n s e q u e n t l y , o u r m o d e l o f a L I S P p r o g r a m i s a h i e r a r c h i c a l n e t w o r k o f s e g m e n t s , s u c h t h a t t h e m o d e l i n c l u d e s b o t h p l a n n i n g i n f o r m a t i o n , w h i c h r e f l e c t s a p r o g r a m m e r ' s way o f t h i n k i n g , and t h e a c t u a l p i e c e s o f L I S P c o d e w h i c h o u g h t t o be p r o d u c e d by a c o m p e t e n t p r o g r a m m e r . E a c h segment c a n be c h a r a c t e r i z e d by S P E C I F I C A T I O N S and PLANS. S p e c i f i c a t i o n s s t a t e f o r m a l l y t h e c o n d i t i o n s and r e l a t i o n s h i p s b e t w e e n i n p u t o b j e c t s , w h i c h h o l d p r i o r t o e x e c u t i o n o f t h e s e g m e n t , and o u t p u t o b j e c t s w h i c h a r e t h e i m m e d i a t e c o n s e q u e n c e o f t h e e x e c u t i o n o f t h e segment. Thus a s e g m e n t ' s s p e c i f i c a t i o n s o r SPECS c o r r e s p o n d t o G o l d s t e i n ' s c o n c e p t o f p e r f o r m a n c e a n n o t a t i o n ( 1 9 7 4 ) , w h i c h d ocuments t h e e f f e c t o f r u n n i n g t h e p r o g r a m o r p i e c e o f c o d e . P l a n s s t a t e f o r m a l l y t h e h i g h e r l e v e l t h i n k i n g i n v o l v e d i n d e s i g n i n g a p r o g r a m t o a c h i e v e a c e r t a i n 30 f u n c t i o n . They are d i v i d e d i n t o d a t a f l o w and c o n t r o l f l o w . To d e s i g n a program, a programmer puts t o g e t h e r a number of segments i n a h i e r a r c h i c a l f a s h i o n by a r r a n g i n g d a t a and c o n t r o l f l o w to s a t i s f y h i g h e r l e v e l s p e c i f i c a t i o n s . Data f l o w s p e c i f i e s how o b j e c t s pass between segments e.g. f u n c t i o n arguments, f r e e v a r i a b l e s , and s i d e e f f e c t s on da t a s t r u c t u r e s . C o n t r o l f l o w d e s c r i b e s the orde r of e x e c u t i o n of segments and i s u s u a l l y a c h i e v e d by PROGs, CONDs, RETURNS, GOs, and f u n c t i o n c a l l s . Thus by e x p l i c a t i n g the behaviour of a segment (seg-A) i n terms of the c o n t r o l and d a t a f l o w of more p r i m i t i v e sub-segments (seg-B, seg-C, seg-D,...), or i t s e l f (seg-A) i n the case of r e c u r s i o n , PLANS are e f f e c t i v e l y c o n s t r u c t e d f o r t h a t segment ( s e g - A ) . T h i s f l o w of data and c o n t r o l w i t h i n the segment (seg-A) p r o v i d e s a s u r f a c e p l a n d e s c r i b i n g how LISP code s h o u l d be put t o g e t h e r to r e a l i s e t h a t segment ( s e g - A ) . At the same time t h i s d e s c r i p t i o n of data and c o n t r o l f l o w d i s p l a y s the purpose or i n t e n t of sub-segments (seg-B, seg-C, seg-D,...), and thus r e p r e s e n t s deep p l a n s f o r these sub-segments. C o n s i d e r the f o l l o w i n g f u n c t i o n , which r e p l a c e s o c c u r r e n c e s of atom , ATI, at the top l e v e l i n a l i s t , L, w i t h atom, A T 2 . 31 (DEFUN REPLACE (ATI AT2 L) (COND ((NULL L) NIL) ((EQ (CAR L) ATI) (CONS AT2 (REPLACE ATI AT2 (CDR L ) ) ) ) (T (CONS (CAR L) (REPLACE ATI AT2 (CDR L ) ) ) ) )) F i g u r e s 2 and 3 below then show the segments wh-ich w.i 11 be used as b u i l d i n g blocks i n the c o n s t r u c t i o n of the f u n c t i o n REPLACE, as w e l l as the data and c o n t r o l flow between these sub-segments. These sub-segments have been given unique i d e n t i f i e r s in the diagrams, to d i s t i n q u i s h t h e i r d i f f e r e n t o c c u r r e n c e s . 32 FIG. 2 Dataflow R e p r e s e n t a t i o n between Sub-segments of the F u n c t i o n REPLACE L t t v t ; i \" v NULLTEST-13 TRUE 25 ATI t j v CAR-19 t v t V t CAR-10 CDR-12 26 19 / / / / EQTEST-14 / v REPLACE-16 23 CONS-18 22 v 24 AT 2 v i CDR-11 20 v REPLACE-15 21 v CONS-17 v v 3 3 FIG. 3 C o n t r o l Flow R e p r e s e n t a t i o n for the F u n c t i o n REPLACE REPLACE NULLTEST-13 TRUE FALSE CAR-10 CDR-12 t v t CAR-19 v t EQTEST-14 TRUE FALSE v t REPLACE-16 ! t V ! CONS-18 RETURNS CDR-11 v t ; REPLACE-15 T t V J I CONS-17 t I t t RETURNS v V 34 'V.2 Representing segments v i a data-base e n t r i e s A s s o c i a t e d with every occurrence of a segment, except p r i m i t i v e LISP f u n c t i o n segments such as CAR, CDR, APPEND, is an entry i n a data-base which has the f o l l o w i n g form: (LAMBDA-EXP) segment-id SEGMENT (FUNC-CALL ) name (OPEN-CODE ) code-entry code-entry .... Since a data-base i s made for each occurrence of a segment in the LISP program, a unique i d e n t i f i e r i s necessary to d i s t i n q u i s h each p a r t i c u l a r segment occurrence. These ocurrences of segments in LISP may be lambda expressions (named or unnamed f u n c t i o n d e f i n i t i o n s ) or pieces of open code (PROGs, loops, S - e x p r e s s i o n s ) . Each segment has one main data-base entry corresponding to i t s d e f i n i t i o n , which we r e f e r to as i t s MAJOR SEGMENT ENTRY. T h i s major entry can be considered the r e f e r e n c e to the deep p l a n , as i t s t o r e s 35 s p e c i f i c a t i o n a n d p l a n n i n g i n f o r m a t i o n o n i t s a s s o c i a t e d p r o p e r t y - l i s t . T h i s m a j o r e n t r y h a s i t s o w n s e g m e n t n a m e a s i t s s e g m e n t i d e n t i f i e r , a n d h a s a s i t s c o d e - e n t r i e s t h o s e a l t e r n a t i v e p i e c e s o f c o d e w h i c h m a y r e a l i z e t h a t s e g m e n t . T h u s f o r t h e a b o v e e x a m p l e , t h e r e w o u l d b e a m a j o r s e g m e n t d a t a - b a s e e n t r y o f t h e f o l l o w i n g f o r m : R E P L A C E S E G M E N T L A M B D A - E X P R E P L A C E ( D E F U N R E P L A C E ( A T I A T 2 L ) ( C O N D ( C D R L ) ) ) ) ) ) T h e S P E C S a n d P L A N S f o r t h e s e g m e n t R E P L A C E w o u l d b e a v a i l a b l e o n t h e p r o p e r t y l i s t o f t h e s e g m e n t ' s n a m e i . e . o n t h e p r o p e r t y l i s t o f R E P L A C E u n d e r t h e a t t r i b u t e s S P E C S a n d P L A N S . T h u s t h e s u r f a c e s t r u c t u r e a n d p u r p o s e o f e a c h s e g m e n t r e f e r e n c e d i n t h e p r o g r a m , c a n b e r e f e r e n c e d v i a t h e m a j o r d a t a - b a s e e n t r y f o r t h a t s e g m e n t . A s m e n t i o n e d e a r l i e r , e v e r y s e g m e n t h a s o n l y o n e m a j o r d a t a - b a s e e n t r y , b u t e v e r y s i n g l e r e f e r e n c e t o t h a t s e g m e n t i n t h e L I S P p r o g r a m a l s o h a s a M I N O R D A T A - B A S E E N T R Y 36 a s s o c i a t e d w i t h i t . These minor segment e n t r i e s have s p e c i a l segment i d e n t i f i e r s g e n e r a t e d f o r them by the system. They r e f e r t o t h e i r major segment e n t r y , and thus the SPECS and PLANS f o r the segment as a whole, v i a ' the \"name f i e l d \" which i s c o n s t a n t f o r a l l e n t r i e s (major or min o r ) of a segment. The c o d e - e n t r y f o r a minor-segment i s s i m p l y the LISP S - e x p r e s s i o n which r e f e r e n c e s the segment. C o n s e q u e n t l y , s i n c e the f u n c t i o n REPLACE i s r e c u r s i v e and r e f e r s to i t s e l f , t h e r e would be a second e n t r y f o r the segment - a minor e n t r y - i n the data-base: REPLACE-15 SEGMENT FUNC-CALL REPLACE (REPLACE ATI AT2 (CDR L ) ) T h i s minor segment, or code segment e n t r y , has a unique segment i d e n t i f i e r , yet i t s t i l l has acc e s s t o SPECS and PLANS v i a the name f i e l d w h ich r e f e r e n c e s i t s major segment e n t r y . (Note t h a t both REPLACE-15 and REPLACE-16 would be r e f e r e n c e d as sub-segments of REPLACE i n the g e n e r a l PLAN f o r segment REPLACE.) T h e r e c o u l d a l s o b e a m a j o r s e g m e n t e n t r y f o r t h e s e g m e n t N U L L T E S T w h i c h i s a p i e c e o f O P E N - C O D E w i t h n o n a m e . I t i s m o s t l i k e l y , h o w e v e r , t h a t a n O P E N - C O D E s e g m e n t w o u l d s i m p l y h a v e a s e p a r a t e m a j o r e n t r y e a c h t i m e i t o c c u r r e d , u n l e s s t h i s O P E N - C O D E w e r e s u c h t h a t i t a p p e a r s r e g u l a r l y i n L I S P p r o g r a m s . I n s u c h c a s e s i t w o u l d b e d e s i r a b l e t o h a v e a l l f r e q u e n t l y u s e d o p e n - c o d e s e g m e n t s p r e - d e f i n e d b y t h e s y s t e m s o t h a t a l e s s o n i n v o l v i n g t h e s e s e g m e n t s c o u l d s i m p l y r e f e r t o t h e m a s e x i s t i n g s e g m e n t s . S i n c e m a j o r O P E N - C O D E s e g m e n t s h a v e n o n a m e f i e l d t h e y w o u l d h a v e t o r e f e r e n c e t h e i r S P E C S a n d P L A N S v i a t h e s e g m e n t i d e n t i f i e r . S u c h a M A J O R S E G M E N T O P E N - C O D E D A T A - B A S E E N T R Y w o u l d l o o k l i k e t h e f o l l o w i n g p i e c e o f c o d e : N U L L T E S T S E G M E N T O P E N - C O D E N I L ( N U L L A N Y L I S T ) C o n s e q u e n t l y , e v e r y r e f e r e n c e t o t h i s o p e n - c o d e s e g m e n t i n t h e L I S P c o d e w o u l d h a v e a m i n o r s e g m e n t d a t a - b a s e e n t r y c a p a b l e o f r e f e r e n c i n g t h e a b o v e m a j o r e n t r y , v i a a s p e c i a l l y c r e a t e d n a m e f i e l d : 38 NULLTEST-13 SEGMENT OPEN-CODE NULLTEST (NULL L) I t i s worth r e p e a t i n g at t h i s p o i n t , t h a t segments must form a h i e r a r c h y , i . e . t h e r e are segments w i t h i n segments and sub-segments may be shared between l a r g e r segments. Such a shared sub-segment would s t i l l have one major e n t r y i n the dat a - b a s e , and each time t h a t i t would appear as a sub-segment to some oth e r segment, i t would have a minor segment e n t r y i n the data-base. Thus, i f segments seg-A and seg-B both r e f e r e n c e d sub-segment seg-C as p a r t of t h e i r PLANS, e i t h e r i n da t a or c o n t r o l f l o w , t h e r e would be major segment e n t r i e s i n the data-base f o r a l l of seg-A, seg-B, and seg-C; t h e r e would be minor segment e n t r i e s s e g - C and s e g - C ' which c o u l d r e f e r e n c e the SPECS and PLANS of segment seg-C v i a the major data-base e n t r y f o r seg-C; and s e g - C and s e g - C ' would be r e f e r e n c e d i n t u r n by the PLANS of segments seg-A and seg-B r e s p e c t i v e l y . D e s c r i p t i o n s of segments c o u l d be s u c c e s s i v e l y r e f i n e d t o any degree, u n t i l i n d i v i d u a l segments become the LISP p r i m i t i v e s , such as CAR,CDR..., which have no SPECS and PLANS, but are r e f e r e n c e d by the studen t v i a the network d e s c r i b e d i n Chapter I I I . 40 I V . 3 S p e c i f i c a t i o n s A s m e n t i o n e d e a r l i e r , a s e g m e n t ' s b e h a v i o u r c a n b e s p e c i f i e d b y i t s i n p u t o b j e c t s , i t s o u t p u t o b j e c t s , a n d t h e c o n d i t i o n s t h a t o u g h t t o h o l d t r u e o n t h e s e o b j e c t s . T h i s t r a d i t i o n a l n o t i o n o f i n p u t - o u t p u t s p e c i f i c a t i o n s , w h i c h i s u s e d t o d e s c r i b e a s e g m e n t , i s e n c a p t u r e d i n a d a t a s t r u c t u r e c a l l e d S P E C S . T h i s s t r u c t u r e e x i s t s a s a n a t t r i b u t e c a l l e d S P E C S o n t h e p r o p e r t y l i s t o f a s e g m e n t ' s n a m e , a n d c a n b e r e f e r e n c e d v i a t h e m a j o r d a t a - b a s e e n t r y f o r t h a t s e g m e n t . A t t h i s s t a g e , w e w i s h t o e m p h a s i z e t h a t t h e r e i s o n l y o n e s e t o f S P E C S f o r a l l t h e i n s t a n c e s o f a s e g m e n t . E v e n t h o u g h e a c h i n s t a n c e o f a s e g m e n t h a s a u n i q u e s e g m e n t i d e n t i f i e r a n d a u n i q u e e n t r y o n t h e d a t a - b a s e , e a c h e n t r y h a s t h e s a m e i n t r i n s i c b e h a v i o u r . C o n s e q u e n t l y i t i s o n l y n e c e s s a r y t o s t o r e t h e S P E C S f o r a s e g m e n t o n t h e p r o p e r t y l i s t o f t h e n a m e . T h i s p r o p e r t y l i s t c a n b e r e f e r e n c e d b y a l l o c c u r r e n c e s o f t h e s e g m e n t , m i n o r a n d m a j o r , v i a t h e n a m e o f t h e a c t u a l s e g m e n t i . e . i t s d e f i n i t i o n , w h i c h i s a v a i l a b l e i n t h e n a m e f i e l d s o f t h e s e g m e n t s ' d a t a - b a s e e n t r i e s . 41 S P E C S h a v e f o u r p a r t s : a l i s t o f i n p u t o b j e c t s ( I N P U T S ) , a l i s t o f p r e - c o n d i t i o n s w h i c h a r e e x p e c t e d t o h o l d o v e r t h e i n p u t o b j e c t s ( P R E C O N D S ) , a l i s t o f o u t p u t o b j e c t s ( O U T P U T S ) , a n d a l i s t o f p o s t - c o n d i t i o n s w h i c h a r e g u a r a n t e e d t o b e t r u e o n o u t p u t ( P O S T C O N D S ) . T h e s e i n p u t a n d o u t p u t c o n d i t i o n s a r e s i m p l y w r i t t e n a s L I S P , f o r m s . I n p u t o b j e c t s a r e a n y d a t a o b j e c t s e . g . a r r a y s , l i s t s , n u m b e r s t h a t d i r e c t l y a f f e c t t h e a c t i o n o f a s e g m e n t . A t t h e L I S P c o d e l e v e l t h e s e e n t e r a s e g m e n t a s l a m b d a a r g u m e n t s o r f r e e v a r i a b l e s . T h e P R E C O N D S e x p l i c a t e t\\\\e c o n d i t i o n s w h i c h m u s t h o l d o n , o r b e t w e e n i n p u t o b j e c t s p r i o r t o e x e c u t i o n o f t h e s e g m e n t . I f t h e y a r e n o t s a t i s f i e d t h e s e g m e n t m a y n o t b e e n t e r e d , a n d i t i s t h u s i m p o r t a n t n e i t h e r t o m a k e t h e s e c o n d i t i o n s e x c e e d i n g l y s t r i n g e n t ( r e s t r i c t i n g a s e g m e n t ' s r a n g e o f a c t i o n s ) , n o r t o m a k e t h e m t o o w e a k ( a l l o w i n g s e g m e n t s t o b e e x e c u t e d o n a l m o s t r a n d o m d a t a ) . O u t p u t o b j e c t s i n c l u d e a l l n e w l y c r e a t e d s t r u c t u r e s a n d e x i s t i n g s t r u c t u r e s w h i c h a r e c h a n g e d b y t h e e x e c u t i o n o f a 42 segment. L I S P o u t p u t o b j e c t s a r e v a l u e s r e t u r n e d by S - e x p r e s s i o n s , v a l u e s o f f r e e - v a r i a b l e s , o r n e w l y c r e a t e d l i s t s ( R P L A C e d , NCONCed)\". POSTCONDS a r e n o t o n l y c o n d i t i o n s on and b e t w e e n o u t p u t o b j e c t s , b u t may a l s o r e f l e c t t h e r e l a t i o n s h i p s b e t w e e n i n p u t and o u t p u t o b j e c t s , w h i c h w i l l h o l d f o l l o w i n g t h e e x e c u t i o n o f t h e segment. T h u s , i n e f f e c t , t h e y c h e c k t h e \" c o r r e c t n e s s \" o f t h e e x e c u t i o n o f a segme n t , a l b e i t i n a v e r y l i m i t e d f a s h i o n . Now, many p r o g r a m s , and henc e s e g m e n t s , a r e p o w e r f u l enough t o h a n d l e more t h a n one t a s k . T h i s i s u s u a l l y a c h i e v e d by means o f c o n d i t i o n a l b r a n c h i n g . We r e f l e c t t h i s b r a n c h i n g i n t h e SPECS by i n t r o d u c i n g CASES w h i c h d e s c r i b e m u t u a l l y e x c l u s i v e a c t i o n s p e r f o r m e d by a segment. F o r e x a m p l e , t h e REPLACE f u n c t i o n , w h i c h i n p u t s a l i s t \"and two a t o m s , c a n be v i e w e d as p e r f o r m i n g two f u n c t i o n s , v i z . : 1) r e p l a c i n g a l l o c c u r r e n c e s o f one atom by a n o t h e r i n t h e 1 i s t , o r , 2) r e t u r n i n g t h e l i s t i t s e l f i f i t i s a n u l l l i s t . C o n s e q u e n t l y , t h e SPECS o f t h e REPLACE f u n c t i o n w i l l r e f l e c t t h a t t h e i n p u t i s a l w a y s a l i s t and a p a i r o f a t o m s , b u t , d e p e n d i n g on t h e l i s t i t s e l f , i . e . t h e PRECONDS a s s o c i a t e d w i t h t h e l i s t , t h e OUTPUTS o f t h e segment and t h e POSTCONDS, 43 can be of one of two c a s e s . That p a r t of a segment's s p e c i f i c a t i o n s which i s a p p l i c a b l e i n a l l cases appears f i r s t , and the r e s t of the SPECS i s d i v i d e d i n t o d i f f e r e n t case phrases c a l l e d CASE-1, CASE-2, e t c . For a complete segment to be s a t i s f i e d , ALL i t s non-CASE-embedded and ONE case phrase must be s a t i s f i e d . Thus the g e n e r a l format f o r w r i t i n g the SPECS of a segment i s as shown below: SPECS: segment-name (FREE-VAR ) (INPUTS o b j e c t - i d ( o r ) ) (LAMBDA-ARG ) (INPUTS...) (PRECONDS LISP S-exprs i n v o l v i n g o b j e c t - i d ' s ) (PRECONDS...) 44 (NEW-LIST ) (OUTPUTS o b j e c t - i d (FREE-VAR ) ) (RETURN-VAL ) (OUTPUTS...) (POSTCONDS LISP S-exprs i n v o l v i n g o b j e c t - i d ' s ) (POSTCONDS...) (CASE-1 (INPUTS...) (PRECONDS...) (OUTPUTS...) (POSTCONDS...) ) (CASE-2 (PRECONDS . . . ) (OUTPUTS...) (POSTCONDS...) ) 45 T h e s e SPECS a r e s t o r e d on t h e p r o p e r t y l i s t o f t h e segment name o r m a j o r segment e n t r y i d e n t i f i e r , u n d e r t h e a t t r i b u t e SPECS. Thus f o r t h e segment REPLACE, w i t h m a j o r segment e n t r y and m i n o r segment e n t r i e s i n t h e d a t a - b a s e , we w o u l d have on i t s p r o p e r t y l i s t , u n d e r t h e a t t r i b u t e SPECS, t h e f o l l o w i n g p i e c e o f c o d e : (INPUTS ATI LAMBDA-ARG) (INPUTS AT 2 LAMBDA-ARG) (INPUTS L LAMBDA-ARG) (PRECONDS (AND (ATOM A T I ) (ATOM AT2) ) ) (CASE-1 (PRECONDS (NULL L ) ) (OUTPUTS L-2 5 RETURN-VAL) (POSTCONDS (NULL L-2 5) ) ) (CASE-2 (PRECONDS (AND (NOT (ATOM L ) ) L) ) (OUTPUTS L-24 RETURN-VAL) 46 (POSTCONDS (AND (NOT (MEM ATI L-24)) (EQ (LEN L) (LEN L - 2 4 ) ) ) ) ) ) Thus i t i s p o s s i b l e to s p e c i f y t h a t the segment REPLACE always expects two atoms and a t h i r d element, which may be a non-empty l i s t or n i l , as i n p u t . I t y i e l d s as output e i t h e r the n u l l t h i r d element or a new l i s t of equal l e n g t h t o the n o n - n u l l t h i r d element and d e v o i d of any o c u r r e n c e s of the f i r s t atom. S i n c e the POSTCONDS of a segment o f t e n e s t a b l i s h the r e q u i r e d PRECONDS of another segment, we can c o n s i d e r t h e r e b e i n g a t e l e o l o g i c a l r e l a t i o n s h i p between segments, d e s c r i b i n g \"why\" each segment i s used. T h i s network which can t i e t o g e t h e r sub-segments i n a p r e r e q u i s i t e , g o a l - s u b g o a l r e l a t i o n s h i p p r e s e n t s a deep l e v e l u n d e r s t a n d i n g of how a program works. I t a l s o p r o v i d e s i n f o r m a t i o n as to what s t r u c t u r e s the programmer s h o u l d have i n mind when p l a n n i n g h i s program. T h i s knowledge needed by a programmer i n p l a n n i n g h i s program, i s augmented by more i n f o r m a t i o n w hich i s s t o r e d on the segment's p r o p e r t y l i s t under the a t t r i b u t e PLANS. P l a n n i n g i n f o r m a t i o n , such as 47 l i s t s of sub-segments, and l i s t s of d a t a f l o w between them, not o n l y h e l p s the programmer produce the LISP code f o r t h a t segment, but a l s o h e l p s him g a i n i n s i g h t i n t o the t e l e o l o g i c a l r e l a t i o n s h i p s between segments. 48 IV.4 P l a n s J u s t as an engin e e r might c o n s t r u c t a c i r c u i t from e l e c t r o n i c components, so a programmer can d e s i g n a program u t i l i s i n g segments. These segments are a r r a n g e d i n some p u r p o s e f u l manner, by o r g a n i s i n g d a t a f l o w and c o n t r o l f l o w to s a t i s f y the g i v e n s p e c i f i c a t i o n s . Thus t h i s a r r a n g i n g of segments i s n o t h i n g more than a p l a n t o implement the p r e v i o u s l y d e c i d e d upon s p e c i f i c a t i o n s . PLANS model the way LISP code s h o u l d be c o n s t r u c t e d i n ord e r to r e a l i s e the SPECS and a c h i e v e the I/O r e l a t i o n s h i p of a segment. I t i s t h i s p l a n n i n g i n f o r m a t i o n which w i l l be h e a v i l y r e l i e d upon d u r i n g the i n s t r u c t i o n p r o c e s s . The system w i l l use the PLANS\"\" to h e l p the stude n t d e s i g n the f u n c t i o n o r , a l t e r n a t i v e l y , i t c o u l d t e a c h by l i m i t i n g h i s / h e r d e s i g n to the model i t p r e s e n t s . J u s t l i k e SPECS, p l a n n i n g i n f o r m a t i o n f o r a segment i s s t o r e d on the p r o p e r t y l i s t of the segment's name under the a t t r i b u t e PLANS. The PLANS s t r u c t u r e f o r a segment has t h r e e major s e c t i o n s , v i z . : 1) a l i s t of sub-segments r e f e r e n c e d by t h a t segment, 49 2 ) 1 i s t s i 1 l u s t r a t i n g t h e f l o w o f d a t a b e t w e e n t h e s e s u b - s e g m e n t s , a n d , 3 ) l i s t s i l l u s t r a t i n g t h e f l o w o f c o n t r o l b e t w e e n ( h e n c e t h e t e l e o l o g y o f ) t h e s u b - s e g m e n t s . 50 Sub-segment L i s t Each instance of a segment type which i s re f e r e n c e d by the segment under c o n s t r u c t i o n , i s l i s t e d i n the segment's PLANS in the sub-segment l i s t . The s t r u c t u r e of such a l i s t i s simply the f o l l o w i n g : PLANS: segment-name (SUB-SEGS ( segment-id segment-id ...)) Thus for the segment REPLACE, under the a t t r i b u t e PLANS on REPLACE's pro p e r t y l i s t , there may be the f o l l o w i n g sub-segment l i s t : (SUB-SEGS (CAR-10 CDR-11 CDR-12 NULLTEST-13 EQTEST-14 REPLACE-15 REPLACE-16 CONS-17 CONS-18 CONS-19 ) ) As sub-segments are referenced by a segment duri n g PLANS 0 construction and more s p e c i f i c a l l y during sub-segment l i s t construction, entries are added to the data-base for those sub-segments. Assuming that segments have already been defined for EQTEST and NULLTEST i.e. they already have major segment entries; then there are three types of sub-segments which may be referenced by a segment's SUB-SEGS l i s t . 1) Sub-segments such as NULLTEST-13 and EQTEST-14 w i l l have minor segment entries constructed for them on the data-base as they are referenced by segment REPLACE. Since OPEN-CODE segments have already been defined for them, and major segment entries exist, sub-segments NULLTEST-13 and EQTEST-14 can be considered to have been constructed in a bottom-up approach, i.e. they are used as sub-segments in REPLACE's PLANS and'referenced by REPLACE after they have already been constructed and defined. Thus, apart from being added to the SUB-SEGS l i s t , they have minor entries made on the data-base corresponding to their reference in REPLACE. 2) Sub-segments REPLACE-15 and REPLACE-16 w i l l also have minor segment entries constructed on the data-base as they 52 are r e f e r e n c e d r e c u r s i v e l y by segment REPLACE. Even though REPLACE has as yet not been c o m p l e t e l y d e f i n e d and t h e r e i s no segment d e f i n i t i o n or major e n t r y f o r REPLACE on the dat a - b a s e , t h e r e i s no problem i n r e f e r e n c i n g i t , r e c u r s i v e l y or o t h e r w i s e , as sub-segment REPLACE-15 f o r example. In t h i s manner i t i s p o s s i b l e to c o n s t r u c t a program i n top-down s t y l e by s i m p l y c o n s t r u c t i n g minor segment e n t r i e s f o r those sub-segments which need to be r e f e r e n c e d , but are not yet d e f i n e d . E v e n t u a l l y , when the d e f i n i t i o n of REPLACE i s completed, i t w i l l o n l y be n e c e s s a r y to ensure t h a t a l l i t s p r e v i o u s l y c o n s t r u c t e d minor segment e n t r i e s , w h i c h were r e f e r e n c e d elsewhere as sub-segments, p r o p e r l y l i n k up to i t s SPECS and PLANS v i a the segment name REPLACE. The minor segment e n t r i e s f o r REPLACE-15 and REPLACE-16 c o n s t r u c t e d d u r i n g the d e f i n i t i o n of REPLACE w i l l be of the f o l l o w i n g f o rm: REPLACE-15 SEGMENT FUNC-CALL REPLACE REPLACE-16 SEGMENT FUNC-CALL REPLACE 53 3) CAR-10, CDR-11, CDR-12, CONS-17, CONS-18, CAR-19 a l s o e x i s t as sub-segments i n the SUB-SEGS l i s t of REPLACE. As mentioned p r e v i o u s l y , these LISP f u n c t i o n s a re c o n s i d e r e d p r i m i t i v e and do not have any segment d e f i n i t i o n s or e n t r i e s i n the da t a - b a s e . They do not appear i n the sub-segment l i s t , and are g i v e n segment i d e n t i f i e r s so t h a t they can be i n c l u d e d i n the d e s c r i p t i o n of d a t a and c o n t r o l f l o w w i t h i n the segment REPLACE. 54 Data Flow In our model of LISP programs there are three l e v e l s of data flow:- data flow in and out of a s i n g l e code segment, e.g. i n and out of REPLACE; data flow between sub-segments and t h e i r e n c l o s i n g main segment one l e v e l up i n the h i e r a r c h y , e.g. between NULLTEST-13 and REPLACE; and data flow between code segments at the same l e v e l i n the h i e r a r c h y , e.g. between CAR-10 and EQTEST-14. 1) Data flow in and out of a s i n g l e code segment i s modelled by the SPECS of a segment and does not have anything to do with the flow of data w i t h i n that segment. The INPUTS and OUTPUTS statements of the SPECS d e s c r i b e the data o b j e c t s and a l l o w the student and t u t o r to view the segment as a black box, without having to understand any s t r u c t u r e s or data and c o n t r o l flow. 2) At the next l e v e l of data flow, sub-segments w i t h i n a segment have to r e c e i v e data from, and transmit i t to, the o u t s i d e world a c c o r d i n g to the SPECS of the e n c l o s i n g 5 5 segment. T h i s type of data f l o w between a segment and i t s sub-segments can be i n p u t - i n p u t or o u t p u t - o u t p u t i n n a t u r e . The in p u t to the segment as a whole (as s p e c i f i e d i n the SPECS) must a l s o be the in p u t to at l e a s t one of the sub-segments which comprise t h a t e n c l o s i n g , main segment. S i m i l a r l y , the output of the e n c l o s i n g segment must be the r e s u l t of some output a c t i o n of one of i t s e n c l o s e d sub-segments. For example, the atom ATI which i s i n p u t to the EQTEST-14 sub-segment i n the PLANS f o r REPLACE i s the same atom which i s an input d a t a o b j e c t of the segment REPLACE. i . e . ATI i s not in p u t to sub-segment EQTEST-14 from some o t h e r sub-segment, but from the o u t s i d e w o r l d . L i k e w i s e , the output of the CONS-17 sub-segment becomes the output of REPLACE as a whole. The g e n e r a l s y n t a x of the DATAFLOW statement i n the PLANS f o r a segment i s the f o l l o w i n g : (DATAFLOW (segment-id (INPUT ) o b j e c t - i d ) (OUTPUT ) (segment-id (INPUT ) o b j e c t - i d ) ) 56 (OUTPUT ) Thus at t h i s l e v e l of the data flow between a sub-segment and the non-REPLACE o u t s i d e world, the PLANS f o r REPLACE could i n c l u d e the f o l l o w i n g DATAFLOW statements: PLANS: REPLACE (SUB-SEGS...) (DATAFLOW (REPLACE INPUT ATI) (EQTEST-14 INPUT ATI)) (DATAFLOW (REPLACE INPUT ATI) (REPLACE-15 INPUT AT1)) (DATAFLOW (CONS-17 OUTPUT L-24) (REPLACE OUTPUT L-24)) (DATAFLOW (CONS-18 OUTPUT L-24) (REPLACE OUTPUT L-24)) L e t us now examine a p a r t i c u l a r d a t a f l o w l i n k between a main segment and i t s sub-segment. (DATAFLOW (CONS-18 OUTPUT L-24)-(REPLACE OUTPUT L-24)) T h i s i s an o u t p u t - o u t p u t d a t a f l o w type between a sub-segment and i t s e n c l o s i n g segment. CONS-18 i s t h a t i n s t a n c e of the CONS segment r e f e r e n c e d as a sub-segment i n the p l a n of segment REPLACE. The output of t h i s i n s t a n c e of CONS y i e l d s a d a t a o b j e c t , which i s r e f e r r e d to i n F i g . 2 as L-24. L-24 i s i n t u r n the output of segment REPLACE as a whole. S i n c e i t i s an output of segment REPLACE, t h i s d a t a o b j e c t , L-24, w i l l have to s a t i s f y the POSTCONDS as s p e c i f i e d i n the SPECS of REPLACE. These SPECS c l a r i f y the manner i n which the t r a n s f e r of d a t a i s e f f e c t e d between segments and t h e i r e n c l o s e d sub-segments i n an i n p u t - i n p u t or o u t p u t - o u t p u t type of t r a n s f e r . S i n c e L-24 i s output from REPLACE as a RETURN-VALUE of an S - e x p r e s s i o n , 58 ( a c c o r d i n g to the POSTCONDS of REPLACE's SPECS), i t must have been t r a n s f e r r e d from CONS-17 or CONS-18 as the r e t u r n v a l u e of some S - e x p r e s s i o n . S i m i l a r l y , j u s t as ATI i s in p u t to REPLACE as a lambda argument, so i t i s e f f e c t i v e l y i n p u t to EQTEST-14, REPLACE-15, et a l , as a lambda argument. S i n c e a l l movement of data at t h i s l e v e l i s between the segment under d i s c u s s i o n i . e . REPLACE, and i t s sub-segments, the d i r e c t i o n of d a t a f l o w i s always f i x e d . Thus a l l these d a t a f l o w l i n k s are u n i - d i r e c t i o n a l i . e . i n p u t - i n p u t or o u t p u t - o u t p u t . The mechanisms f o r a c h i e v i n g t h i s d a t a f l o w are determined by the SPECS of the h i g h e r l e v e l segment and are not s p e c i f i e d on the DATAFLOW l i n k . When t r a n s f e r i s between sub-segments on the same l e v e l of the h i e r a r c h y , then the mechanisms of data f l o w and the d i r e c t i o n changes somewhat. 3) The lowest l e v e l of d a t a f l o w i s between sub-segments at the same l e v e l of d e s c r i p t i o n i n a segment's PLANS. \" The type of d a t a f l o w at t h i s l e v e l of the p l a n i s an output - i„nput da t a f l o w . The output of one sub-segment i s matched to the in p u t of another to model the movement of 59 d a t a w i t h i n the e n c l o s i n g segment. J u s t as the mechanism f o r data f l o w i n t o and out of a s i n g l e segment i s r e c o r d e d as e x t r a a n n o t a t i o n on the c o r r e s p o n d i n g INPUTS and OUTPUTS statements i n the SPECS of the segment, so the mechanism of dat a f l o w between sub-segments on the same l e v e l i s r e c o r d e d on the c o r r e s p o n d i n g DATAFLOW statement i n the PLANS of which they are sub-segments. On o u t p u t - i n p u t d a t a f l o w l i n k s , i . e . f l o w between sub-segments, data can e f f e c t i v e l y be t r a n s f e r r e d by two mechanisms, v i z . : s a m e - f r e e - v a r i a b l e , and n e s t i n g of S - e x p r e s s i o n s . Thus the complete s y n t a x of the DATAFLOW statement i s : (DATAFLOW (s egment-i d (segment - i d R e l e v a n t f o r o u t p u t -i n p u t d a t a f l o w o n l y (INPUT ) o b j e c t - i d ) (OUTPUT ) (INPUT ) o b j e c t - i d ) (OUTPUT ) (SAME-FREE-VAR) (NESTED-SEXP ) ) 1 60 Note t h a t the mechanism of d a t a f l o w needs o n l y to be s p e c i f i e d f o r d a t a f l o w i n g between sub-segments i n a p l a n and not f o r d a t a f l o w to or from the h i g h e r l e v e l segment. When the same f r e e v a r i a b l e i s r e f e r r e d to by both segments i n an o u t p u t - i n p u t DATAFLOW stat e m e n t , the two sub-segments communicate d i r e c t l y . C o n s i d e r the f o l l o w i n g p i e c e of code: (FN (SETQ L (CAR L ) ) ) In t h i s code, the l i s t L g e t s t r a n s f e r r e d from the CAR segment to the FN segment. T h i s i s a c h i e v e d by the f a c t t h a t the output of the CAR and the input to the FN are r e f e r e n c e d by the same f r e e v a r i a b l e , L. Hence the DATAFLOW statement f o r t h i s o u t p u t - i n p u t t r a n s f e r would be anno t a t e d w i t h an e x t r a p h r a s e , SAME-FREE-VAR. N e s t i n g of S - e x p r e s s i o r i s i s another common method to move d a t a between segments at the same l e v e l . T h i s n e s t i n g i s such t h a t the d a t a o b j e c t i s output as the r e t u r n v a l u e of the n e s t e d segment, and in p u t as the argument to the n e s t i n g or o u t e r segment. For example, the code (REPLACE ATI AT2 (CDR D ) has sub-segments REPLACE-16, and CDR-12, w i t h CDR-12 n e s t e d w i t h i n REPLACE-16. Data f l o w s from the r e s u l t of a p p l y i n g CDR to L and i s bound as an argument to the REPLACE segment. Hence t h i s DATAFLOW statement would i n c l u d e the p h r a s e , NESTED-SEXP, as a n n o t a t i o n . 61 In the PLAN f o r REPLACE there are s e v e r a l output-input data flow statements i . e . flow between sub-segments on the same l e v e l . Each of these would be annotated, i l l u s t r a t i n g the mechanism used to b r i n g about t h i s t r a n s f e r . Hence the PLANS fo r REPLACE would i n c l u d e the f o l l o w i n g DATAFLOW statements f o r output-input t r a n s f e r s : PLANS: REPLACE (DATAFLOW (CAR-10 OUTPUT L-19) (EQTEST-14 INPUT L-19) NESTED-SEXP) (DATAFLOW (CDR-11 OUTPUT L-20) (REPLACE-15 INPUT L-20) NESTED-SEXP) (DATAFLOW (..OUTPUT ..) (..OUTPUT ..) ) 62 he complete data f l o w i n the PLANS f o r a segment o n l y r e p r e s e n t s one p o s s i b l e r e a l i s a t i o n of the segment's SPECS by LISP code. I t i s q u i t e p o s s i b l e , i n almost every i n s t a n c e , t o take the SPECS of a segment and c o n s t r u c t many PLANS w i t h v a r y i n g DATAFLOWS which w i l l r e a l i s e those SPECS. T h i s r e p r e s e n t s a problem i n t r y i n g t o un d e r s t a n d the f l o w of d a t a w i t h i n a program. I t a l s o p r e s e n t s program v e r i f i c a t i o n problems. For t e a c h i n g p u r p o s e s , however, i t i s s a t i s f a c t o r y t o have the one model which can be used to e x p l a i n and i l l u s t r a t e the f l o w of d a t a . S i n c e c o a c h i n g and not program v e r i f i c a t i o n i s the g o a l of t h i s t u t o r , one model of a f u n c t i o n i s s u f f i c i e n t to coach a stude n t i n w r i t i n g a LISP program. 63 C o n t r o l Flow Segment PLANS are da t a s t r u c t u r e s which i l l u s t r a t e the manner i n which LISP programs are c o n s t r u c t e d to a c h i e v e the SPECS of the segment. These PLANS have i n f o r m a t i o n about the f l o w of da t a w i t h i n segments (DATAFLOW STRUCTURE);the r e f e r e n c e s made by segments to t h e i r e n c l o s e d sub-segments (SUB-SEGS LIST);and the order of these r e f e r e n c e s , i . e . the sequence of e x e c u t i o n of sub-segments. T h i s sequence of sub-segment e x e c u t i o n i s determined by the f l o w of c o n t r o l w i t h i n a segment, and i s m o d e l l e d by a CONTROLFLOW da t a s t r u c t u r e i n the segment's PLANS. C o n t r o l f l o w can occur i n LISP v i a f u n c t i o n i n v o c a t i o n and r e t u r n , by forms i n lambda b o d i e s , and by COND and PROG e x p r e s s i o n s . In t h i s paper we do not t r e a t PROGs e x p l i c i t l y . S i n c e a l l c o n t r o l f l o w s between segments and sub-segments, i t would be l o g i c a l t o t r e a t a complete PROG and GO loop as a s i n g l e segment which may s i m p l y r e t u r n c o n t r o l to i t s e l f , (as opposed to r e g u l a r segments which may o n l y be r e c u r s i v e , or may r e t u r n c o n t r o l to some . o t h e r segment at a h i g h e r l e v e l ) . C o n d i t i o n a l b r a n c h i n g w i t h i n a segment,i.e. 64 a l t e r n a t i v e d i r e c t i o n s o f c o n t r o l f l o w u s u a l l y a c h i e v e d by CONDs, i s h a n d l e d by DIRECTION s t a t e m e n t s w i t h i n t h e CONTROLFLOW d a t a s t r u c t u r e . T h e s e DIRECTION s t a t e m e n t s a r e s i m i l a r t o t h e CASE s t a t e m e n t s u s e d i n t h e d e s c r i p t i o n o f a seg m e n t ' s SPECS. CONTROLFLOW b e t w e e n s u b - s e g m e n t s i s r e p r e s e n t e d by a s e r i e s o f INVOKES and NEXT r e l a t i o n s h i p s . When c o n t r o l l e a v e s a segment as a r e t u r n t o a h i g h e r l e v e l c a l l i n g s e g m e n t , o r as an i t e r a t i o n i n a PROG l o o p , t h i s i s i n d i c a t e d by t h e RETURN s t a t e m e n t on t h e CONTROLFLOW d a t a s t r u c t u r e . T h e s e RETURN s t a t e m e n t s , w h i c h n o t e t h e r e t u r n v a l u e s o f s e g m e n t s , may o b v i o u s l y a p p e a r s e v e r a l t i m e s i n t h e d e s c r i p t i o n o f t h e CONTROLFLOW f o r a segment. Thus we have t h e f o l l o w i n g s t a t e m e n t s i n t h e CONTROLFLOW d a t a s t r u c t u r e : DIRECTION i n d i c a t e s a p o s s i b l e c h a n g e o f d i r e c t i o n i n t h e f l o w ; INVOKES i n d i c a t e s t h e f i r s t segment i n a p a t h o f c o n t r o l f l o w ; NEXT i n d i c a t e s t h e a c t u a l p a t h o f c o n t r o l f l o w ; and RETURN i n d i c a t e s t h e end p o i n t i n a p a t h o f c o n t r o l f l o w . The s y n t a x o f t h e CONTROLFLOW s t a t e m e n t w i t h i n a s e g m e n t ' s PLANS c a n be g e n e r a l l y d e s c r i b e d as f o l l o w s : PLANS: s e g - i d (SUB-SEGS...) (DATAFLOW...) (CONTROLFLOW (INVOKES s e g - i d ) (NEXT s e g - i d s e g - i d ...) (RETURNS s e g - i d ) (DIRECTION-1 t r u t h - v a l u e (INVOKES ...) (NEXT ...) (DIRECTION-2 ...) . . n e s t e d d i r e c t i o n s (DIRECTION-3 t r u t h - v a l u e (RETURNS s e g - i d ) ) ..end o f d i r e c t i o n 3 (RETURNS ...) ) ..end o f d i r e c t i o n l (DIRECTION-4 t r u t h - v a l u e 6 6 ) A DIRECTION statement i n d i c a t e s p o s s i b l e c o n t r o l . f l o w at a p a r t i c u l a r p o i n t i n the segment's PLANS. These statements u s u a l l y c o r r e s p o n d to a COND statement i n the LISP code, but are used t o i l l u s t r a t e any b r a n c h i n g c h a r a c t e r i s t i c s of a PLAN. N o r m a l l y , a s i n g l e COND statement i n the LISP program has as many DIRECTION statements a s s o c i a t e d w i t h i t i n the PLANS, as i t has COND-expressions i n the LISP code. B r a n c h i n g i s always dependent on a l o g i c a l c o n d i t i o n , and i t i s thus obvious t h a t the sub-segment which i m m e d i a t e l y precedes a DIRECTION statement ( u s u a l l y a NEXT) i n the CONTROLFLOW ought to i n c o r p o r a t e some t e s t . I t i s the outcome of t h i s t e s t which determines whether c o n t r o l f l o w s h o u l d f o l l o w the DIRECTION statement or not. A s s o c i a t e d w i t h each DIRECTION statement i s a c o n s t a n t t r u t h - v a l u e . T h i s t r u t h - v a l u e must match the v a l u e of the p r e c e d i n g (NEXT) sub-segment f o r c o n t r o l to f o l l o w t h a t path i n d i c a t e d by the DIRECTION statement. In o t h e r words, a d i r e c t i o n - k w i l l be p o s s i b l e i f and o n l y i f the v a l u e r e t u r n e d by the p r e c e d i n g sub-segment i s e q u i v a l e n t t o the t r u t h - v a l u e on the DIRECTION-k statement. J u s t as n e s t i n g of CONDs i s 67 p o s s i b l e i n L I S P , so n e s t i n g o f DIRECTION s t a t e m e n t s i n t h e CONTROLFLOW o f a se g m e n t ' s PLANS i s p o s s i b l e . E v e r y p a t h a l o n g w h i c h c o n t r o l f l o w s i n a se g m e n t ' s PLANS, must be i n i t i a t e d by an i n v o c a t i o n o f some s u b - s e g m e n t . The f i r s t s u b - segment i n t h e CONTROLFLOW i s t h u s a l w a y s i n v o k e d by t h e m a i n segment w h i c h e n c l o s e s t h e c o n t r o l f l o w s e q u e n c e . E v e r y DIRECTION s t a t e m e n t a l s o r e p r e s e n t s a new s e q u e n c e o f c o n t r o l f l o w and i s a l s o c o n s e q u e n t l y f o l l o w e d by an INVOKE s t a t e m e n t . I n o t h e r w o r d s , b o t h t h e f i r s t s u b - s egment e x e c u t e d i n a se g m e n t ' s PLANS, and t h e f i r s t s u b -segment f o l l o w i n g a DIRECTION s t a t e m e n t , i n d i c a t e t h e b e g i n n i n g o f a c o n t r o l f l o w s e q u e n c e . H e nce any INVOKE s t a t e m e n t s i m p l y i n d i c a t e s t h e i n i t i a t i o n o f a new p a t h o r d i r e c t i o n o f c o n t r o l f l o w i n t h e L I S P c o d e . C o n t r o l f l o w i s d i r e c t e d a l o n g t h i s p a t h by t h e NEXT s t a t e m e n t . T h e s e NEXT s t a t e m e n t s r e p r e s e n t t h e c o n n e c t i v e t i s s u e o f a L I S P p r o g r a m w h i c h s e q u e n c e s t h e e x e c u t i o n o f L I S P f o r m s . C o n n e c t i v e t i s s u e c a n be e x p l i c i t i n t h e f o r m o f PROGNs, o r i t c a n be i m p l i e d by n e s t i n g S - e x p r e s s i o n s a n d / o r s u b - s e g m e n t s . C o n s i s t e n t w i t h t h e f a c t t h a t a 6 8 DIRECTION statement i s preceded by some c o n d i t i o n , the l a s t sub-segment i n the path of c o n t r o l f l o w , i . e . the sequence of NEXTs, must e i t h e r be one which i n c o r p o r a t e s some t e s t and thus y i e l d s a t r u t h - v a l u e to be f e d to the s u c c e e d i n g DIRECTION s t a t e m e n t , or i t must be f o l l o w e d by one of the RETURNS to the h i g h e r l e v e l segment. The RETURN statement i l l u s t r a t e s the p o i n t i n the segment's PLANS where c o n t r o l can be r e l i n q u i s h e d to the h i g h e r l e v e l segment. The segment-id of a RETURN statement i s u s u a l l y a r e f e r e n c e to t h a t sub-segment whose v a l u e i s the r e t u r n - v a l u e of the main segment as a whole. T h i s v a l u e i s e i t h e r r e t u r n e d to some h i g h e r - l e v e l segment i n the LISP program, or i t i s r e t u r n e d as the v a l u e of the e n t i r e program when the segment under c o n s i d e r a t i o n i s at the top l e v e l . A RETURN statement can a l s o be used to p e r f o r m a jump i n the program. Such a RETURN w i l l c o r r e s p o n d to the GO statement of a PROG l o o p , and the segment-id w i l l e f f e c t i v e l y be a r e f e r e n c e to t h a t sub-segment which i m m e d i a t e l y f o l l o w s the PROG l a b e l . The CONTROLFLOW of the PLANS f o r segment REPLACE c o u l d be 69 the f o l l o w i n g : PLANS: REPLACE (CONTROLFLOW (INVOKES NULLTEST-13) (DIRECTION-1 TRUE (RETURNS NIL)) (DIRECTION-2 NIL (INVOKES CAR-10) (NEXT EQTEST-14) (DIRECTION-4 NIL (INVOKES CAR-19) (NEXT CDR-12 REPLACE-16 CONS-18) (RETURNS REPLACE)) ..end of d i r e c t i o n 4 ) ..end of d i r e c t i o n 2 ) 70 IV.5 C o n c l u s i o n We have now c o n s i d e r e d the f u n c t i o n m o d e l l i n g s t r u c t u r e s w h i c h w i l l be r e f e r e n c e d by the t e a c h i n g p r o c e s s i n h e l p i n g a student d e s i g n a program to s o l v e a problem. These s t r u c t u r e s are a v a i l a b l e to the t u t o r as the v a l u e s of the a t t r i b u t e s SPECS and PLANS on the p r o p e r t y l i s t of the p a r t i c u l a r segment name which models the f u n c t i o n . The t u t o r w i l l a l s o have access to the i n f o r m a t i o n i n the data-base which w i l l r e c o r d a l l r e f e r e n c e s to both the d e f i n i t i o n and i n s t a n c e s of any segment. There are two more s t r u c t u r e s which w i l l a l s o be a v a i l a b l e to the t e a c h i n g machine. A s s o c i a t e d w i t h each segment w i l l a l s o be a d i a g n o s t i c and c o r r e c t i o n s t r u c t u r e , and a d e s c r i p t i v e s t r u c t u r e . The d i a g n o s t i c s t r u c t u r e , which e x p l i c a t e s p o s s i b l e e r r o r s f o r each s e g m e n t ' w i l l be d e a l t w i t h i n the next c h a p t e r . T h i s c h a p t e r w i l l d i s c u s s a l l the l e v e l s of d i a g n o s i s and e r r o r c o r r e c t i o n which a r e p a r t of the l e a r n i n g p r o c e s s . 71 The d e s c r i p t i v e s t r u c t u r e w i l l s i m p l y be a p i e c e of E n g l i s h language p r o s e . T h i s w i l l be s t o r e d under the a t t r i b u t e DESCRIPTION on the p r o p e r t y l i s t of the segment. I t w i l l j u s t p r o v i d e a b r i e f o v e r v i e w of the purpose and a c t i o n s of t h a t p a r t i c u l a r segment. I t w i l l have u t i l i t y both i n the t e a c h i n g p r o c e s s and as a source of m i s c e l l a n e o u s documentation. Thus f o r segment REPLACE, under the a t t r i b u t e DESCRIPTION, c o u l d be s t o r e d the f o l l o w i n g : ( \" F u n c t i o n REPLACE takes as i n p u t two atoms and a l i s t . I t s earches the l i s t f o r a l l t o p - l e v e l o c c u r r e n c e s of the f i r s t atom and r e p l a c e s them w i t h the second atom. T h i s new l i s t i s r e t u r n e d as the v a l u e of REPLACE. I f the f i r s t atom does not appear at the top l e v e l i n the l i s t , or i f the l i s t i s the n u l l l i s t , then the o r i g i n a l l i s t i s r e t u r n e d unchanged as the v a l u e of REPLACE.\") T h i s DESCRIPTION w i l l be used by the t u t o r i n g p r o c e s s to d e s c r i b e the problem to the student and to h e l p him/her make some sense of the a c t i o n s of each segment. 72 We will now consider the structures and process involved in helping a student produce a correct LISP function, i.e. the error detection and correction routines. 73 CHAPTER V ANALYSIS,DIAGNOSIS, AND CORRECTION OF PROGRAMS Chapter F i v e d e a l s e x c l u s i v e l y w i t h the d i a g n o s i s of st u d e n t - p r o d u c e d programs, d e t e c t i o n of e r r o r s , and the a n a l y s i s and c o r r e c t i o n of these e r r o r s . A l t h o u g h t h i s a n a l y s i s aspect appears as a s e p a r a t e c h a p t e r , the reader must be aware t h a t i t i s not i n any way s e p a r a t e d from the t e a c h i n g p r o c e s s . What f o l l o w s i s a d e s c r i p t i o n of the d i a g n o s t i c s t r u c t u r e s , and a n a l y s i s and c o r r e c t i o n r o u t i n e s , and an i m p l i c i t o v e r v i e w of what t h i s subsystem e x p e c t s t o a c c o m p l i s h . 74 V . l T r a p p i n g LISP e r r o r messages D i a g n o s i s and a n a l y s i s w i l l be performed at t h r e e l e v e l s . At the top l e v e l the e r r o r messages r e t u r n e d by the LISP i n t e r p r e t e r when e x e c u t i n g code, w i l l s i m p l y be t r a p p e d by the system, a n n o t a t e d w i t h e x t r a i n f o r m a t i o n and r e f e r e n c e s to t e x t , and passed on to the stude n t w i t h d i r e c t p o i n t e r s to h i s / h e r own LISP program. S i l l y s y n t a c t i c c a r e l e s s bugs, such as \" m i s s i n g p a r e n t h e s e s \" , w i l l a l s o be p i c k e d up from the LISP i n t e r p r e t e r ' s e r r o r r o u t i n e s and d i r e c t e d back t o the s t u d e n t . Each time a complete p i e c e of LISP i s produced, ( w i t h b a l a n c e d p a r e n t h e s e s ) , i t w i l l be EVALd, and any e r r o r messages w i l l be used to index e x p l a n a t i o n t a b l e s . These t a b l e s w i l l have access to more d e t a i l e d i n f o r m a t i o n f o r a l l the important LISP e r r o r messages. For example, a s t a c k o v e r f l o w LISP e r r o r message i s u s u a l l y a r e s u l t of improper r e c u r s i o n t e r m i n a t i o n . The LISP e r r o r e x p l a n a t i o n t a b l e f o r t h i s e r r o r c o u l d e x p l a i n t h i s to the s t u d e n t , and g i v e him/her some i n d i c a t i o n as to which segment of code s h o u l d d e a l w i t h c o r r e c t i n g the e r r o r . (Sub-segment NULLTEST i n the case of, f u n c t i o n REPLACE). T h i s form of e r r o r c o r r e c t i o n i s not i n t e n d e d to-be a n y t h i n g more than the p r o g r a m m e d - i n s t r u c t i o n type response found i n e a r l y CAI systems. These t a b l e s of LISP e r r o r messages, programmed to y i e l d a more complete, n a t u r a l - l a n g u a g e type d i s c u s s i o n of the e r r o r and i t s accompanying e x p l a n a t i o n s , w i l l s i m p l y be a channel of communication between the LISP i n t e r p r e t e r and the s t u d e n t . The communications of t h i s p a r t of the sub-system w i l l not r e l a t e i n any way 'to the p a r t i c u l a r f u n c t i o n b e i n g d e s i g n e d , but w i l l emphasize g e n e r a l concepts of LISP programming, common causes o f , and remedies f o r the p a r t i c u l a r e r r o r . The advantage of m a i n t a i n i n g these t a b l e s i n d e p e n d e n t l y of the f u n c t i o n b e i n g d e s i g n e d , i s t h a t the a s s o c i a t e d d i s c u s s i o n of g e n e r a l e r r o r s can be w r i t t e n by an e x p e r i e n c e d LISP programmer. Such an e x p e r t would emphasize g l o b a l s t r a t e g y and g e n e r a l LISP t e c h n i q u e r a t h e r than the n i t t y - g r i t t y of implementing a s p e c i f i c f u n c t i o n . O b v i o u s l y , however, t h i s type of e r r o r c o r r e c t i o n i s i n s u f f i c i e n t i f the stude n t i s to produce a c o r r e c t , w o r k i n g program. E r r o r - f r e e e x e c u t i o n of a program i s no guarantee t h a t the problem has been a d e q u a t e l y s o l v e d by the program. Program a n a l y s i s and v e r i f i c a t i o n are not c o m p l e t e l y developed or complete, yet we b e l i e v e t h a t the f o l l o w i n g two a n a l y s i s e f f o r t s , w hich r e l a t e more d i r e c t l y to the s p e c i f i c f u n c t i o n b e i n g d e s i g n e d , w i l l y i e l d a more complete e r r o r d e t e c t i o n and c o r r e c t i o n p r o c e s s 77 V.2 D i a g n o s t i c models The f i r s t r e a l a n a l y s i s schema, which i s d e s c r i b e d below, i s a p p l i e d to the complete student f u n c t i o n , and not to each segment as i t i s c o n s t r u c t e d . I t emphasizes performance of the f u n c t i o n , r a t h e r than i m p l e m e n t a t i o n or methodology. T h i s a n a l y s i s system i n v o l v e s the e x e c u t i o n of the s t u d e n t ' s program on s p e c i a l l y chosen t e s t d a t a , comparing i t s output w i t h t h a t of a model s o l u t i o n . At t h i s l e v e l of e r r o r d e t e c t i o n and c o r r e c t i o n we e n v i s a g e a DIAGNOSTIC MODEL for, each f u n c t i o n t o be t a u g h t . In d e s c r i b i n g the BUGGY system, Brown and B u r t o n use the term d i a g n o s t i c model, meaning \"a r e p r e s e n t a t i o n of s t u d e n t ' s p r o c e d u r a l knowledge or s k i l l , t h a t d e p i c t s h i s i n t e r n a l i z a t i o n of a s k i l l as a v a r i a n t of a c o r r e c t v e r s i o n of th a t s k i l l \" (Brown & Bur ton,1977,p.5). In o r d e r t o c a p t u r e s t u d e n t s ' f a u l t y b e h a v i o u r or m i s c o n c e p t i o n s , the t e a c h i n g system must be a b l e t o model i n c o r r e c t , as w e l l as c o r r e c t , procedures f o r a s k i l l . J u s t as BUGGY uses s p e c i a l l y chosen problems as t e s t cases to f l u s h out e r r o r s , so we w i l l s t o r e t e s t problems on the model of the f u n c t i o n b e i n g d e s i g n e d . These t e s t problems, 78 w i t h t h e i r a c c o m p a n y i n g s o l u t i o n s and d e b u g g i n g i n f o r m a t i o n , w i l l be s t o r e d on t h e p r o p e r t y l i s t o f t h e t o p - l e v e l s e g m e n t ' s name ( i . e . t h e f u n c t i o n name) u n d e r t h e a t t r i b u t e DIAGNOSTICS. T h e s e d i a g n o s t i c p r o b l e m s w i l l have t o be c h o s e n i n an i n t e l l i g e n t m a n n e r , s i n c e d i a g n o s i n g m i s c o n c e p t i o n s , e ven i n much s i m p l e r d o m ains s u c h as a r i t h m e t i c , i s o f t e n v e r y s u b t l e . A t a p r a c t i c a l l e v e l , s t u d e n t s ' p r o g r a m s w i l l be e x e c u t e d w i t h d a t a s p e c i a l l y c h o s e n t o h i g h l i g h t e r r o r s i n t h e c o d e . A s s o c i a t e d w i t h e a c h t e a c h i n g f u n c t i o n w i l l be a d a t a - b a s e , e a c h e l e m e n t o f w h i c h . w i l l i n c l u d e a s e t o f d i f f e r e n t b i n d i n g v a l u e s t o be a p p l i e d t o ,the s t u d e n t ' s c o d e , and s e v e r a l s e t s o f o u t p u t v a l u e s w h i c h c o u l d p o s s i b l y be p r o d u c e d by a c o r r e c t / i n c o r r e c t p r o g r a m a c t i n g on t h o s e b i n d i n g v a l u e s . B o t h t h e i n p u t s e t and t h e a s s o c i a t e d s e t o f o u t p u t s e t s c o u l d i n c l u d e s h a r e d o r g l o b a l v a r i a b l e s , and w o u l d be a b l e t o r e f e r e n c e t h e v a l u e r e t u r n e d by some f u n c t i o n v i a a s p e c i a l l y c r e a t e d s y m b o l , *F. Hence t h i s d a t a - b a s e w o u l d e f f e c t i v e l y p r o v i d e a p i c t u r e o r m o d e l o f t h e c o n s e q u e n c e s o f s t u d e n t s ' m i s c o n c e p t i o n s . G i v e n a f u n c t i o n F, assume t h e r e i s a d i a g n o s t i c d a t a - b a s e D. T h e n , one p a r t i c u l a r e l e m e n t o f D, D i s a y , i n c l u d e s a s e t o f 79 b i n d i n g v a l u e s f o r a l l r e l e v a n t i n p u t a t o ms. T h i s b i n d i n g s e t , I i , e x i s t s as an A - l i s t w i t h i n t h e d i a g n o s t i c m o d e l . A s s o c i a t e d w i t h t h i s I i , t h e p a r t i c u l a r e l e m e n t D i w o u l d a l s o i n c l u d e s e v e r a l s e t s o f p o s s i b l e ( e r r o n e o u s ) o u t p u t s , O i l . . . O i n . E a c h s e t O i j c o u l d p r o v i d e a d i r e c t l i n k t o e r r o r m e s s a g e s , c o r r e c t i o n p r o m p t s , and code r e f e r e n c e s w h i c h c o u l d be u s e d t o c o r r e c t t h e e r r o r e x e m p l i f i e d by t h a t p a r t i c u l a r O i j . The DIAGNOSTIC s t r u c t u r e f o r any p a r t i c u l a r L I S P f u n c t i o n w o u l d be s t o r e d on t h e m o d e l , u n d e r t h e a t t r i b u t e DIAGNOSTICS, as a m u l t i p l e c o n d i t i o n a l s t a t e m e n t : DIAGNOSTICS f o r f u n c t i o n F (TEST f u n c t i o n \" (WITH-INPUT I I ... . L i s p . , f o r m t o b i n d v a r i a b l e s ((TEST-OUTPUT O i l ) ( c o n s e q u e n t a c t i o n / c o m m e n t s ) ) ((TEST-OUTPUT 0 1 2 ) ( c o n s e q u e n t a c t i o n / c o m m e n t s ) ) ( (TEST-OUTPUT 0 1 j ) )) ..end i n p u t 1 80 (WITH-INPUT 12 ((TEST-OUTPUT 021) (consequent action/comments)) ((TEST-OUTPUT 02 2) (consequent action/comments)) ' ((TEST-OUTPUT 02k) )) ..end input2 (WITH-INPUT I i ((TEST-OUTPUT O i l ) (consequent action/comments)) ((TEST-OUTPUT Oin) )) ..end i n p u t i ) end d i a g n o s t i c s where I i are LISP forms which b i n d a l l r e l e v a n t v a r i a b l e s and O i j are c o n d i t i o n a l e x p r e s s i o n s on the r e s u l t s of the a c t i o n s of the f u n c t i o n . I f ( i n p u t to the f u n c t i o n i s a c c o r d i n g t o I i ) AND 81 ( o u t p u t f r o m t h e f u n c t i o n s a t i s f i e s t h e c o n d i t i o n s o f o u t p u t s e t O i n ) THEN DO ( a l l t h e s e e r r o r c o r r e c t i o n r o u t i n e s , i n t e r a c t i o n s , s u b - 1 e s s o n s e t c . ) . E a c h i n p u t I i w o u l d m e r e l y be an A - l i s t s p e c i f y i n g one p o s s i b l e i n i t i a l c o n d i t i o n o f a l l r e l e v a n t v a r i a b l e s , l i s t s , and atoms u s e d by t h e f u n c t i o n . e.g. '( ( A T I . A ) (AT2.B) ( L . ' ( A C B X A A ) ) ) . The s t u d e n t f u n c t i o n w o u l d be a p p l i e d t o t h e s e i n p u t c o n d i t i o n s , y i e l d i n g a r e t u r n v a l u e r e f e r e n c e d i n t h e m o d e l by *F, and a new s e t o f o u t p u t ( s h a r e d o r l o c a l ) v a l u e s . The d i f f e r e n t p o s s i b l e r e s u l t s o f t h e f u n c t i o n ' s a c t i o n on I i w i l l be m o d e l l e d by t h e s e t O i on t h e d i a g n o s t i c m o d e l . E a c h member o f O i w o u l d be a L I S P c o n d i t i o n a l e x p r e s s i o n a c t i n g on t h e v a l u e s r e t u r n e d by t h e s t u d e n t ' s f u n c t i o n . F o r e x a m p l e , t o c h e c k f o r some m i s u n d e r s t a n d i n g , t h e t e a c h e r m i g h t w i s h t o e n s u r e t h a t t h e s t u d e n t does n o t s i m p l y REPLACE t h e one p a r a m e t e r p a s s e d t o t h e f u n c t i o n , w i t h t h e o t h e r . Thus t h e t e a c h e r w o u l d s u p p l y some o u t p u t t e s t w h i c h w o u l d t r a n s l a t e i n t o t h e c l a u s e (OR (EQ A T I AT2) (NULL *F) ) w i t h i n t h e m u l t i p l e c o n d i t i o n a l c l a u s e o f some O i j . T h i s c l a u s e w o u l d be EVALd u s i n g t h e o u t p u t s f r o m t h e s t u d e n t ' s f u n c t i o n as b i n d i n g v a l u e s f o r A T I and AT2. R e m e d i a l t e a c h i n g m i g h t f o l l o w , d e p e n d i n g on 82 the r e s u l t of the e v a l u a t i o n . Thus the p o s s i b l e output c o n d i t i o n a l s can be as s i m p l e as a l i s t , or as complex as any LISP program. By u s i n g the e v a l u a t i o n of c o n d i t i o n a l c l a u s e s as checks f o r any m a t c h i n g output we e f f e c t i v e l y a l l o w an e x t r e m e l y wide range of d i a g n o s i s : - from \" c o r r e c t answer m a t c h i n g \" to v e r y s u b t l e e r r o r d e t e c t i o n . A s s o c i a t e d w i t h each output c o n d i t i o n ( i . e . w i t h each of O i j from in p u t I i ) > i s d e t a i l e d i n f o r m a t i o n such as:-encouragement f o r c o r r e c t r e s u l t s ; r e f e r e n c e s to t e x t ; r e f e r e n c e s to the segments i n the model which may be c a u s i n g any e r r o r ; c o r r e c t i o n h i n t s and a d v i c e ; e x p l a n a t i o n s ; and g e n e r a l i n t e r a c t i o n s . A l l t h i s a d v i c e woUld p r o b a b l y be a s i m p l e LISP program which c a l l s p rocedures to p e r f o r m the a p p r o p r i a t e r e m e d i a t i o n e t c . I t would gr a n t a t e a c h e r the c a p a b i l i t y of p e r f o r m i n g any LISP p r o c e s s i n g t o p e r f o r m a n a l y s i s , i n t e r r u p t s , data c o l l e c t i o n and stude n t e v a l u a t i o n . One member of the DIAGNOSTICS f o r f u n c t i o n REPLACE c o u l d thus be: 83 (TEST REPLACE (WITH-INPUT '( ( A T I . A ) (AT2.B) ( L . ' ( A B C ) ) ) (TEST-OUTPUT '(AND (EQ *REPLACE ' ( B B C ) ) (EQ A T I B ) ) o u t p u t O i l . . ( ( P R I N T 'NO NEED TO SUBSTITUTE IN THE ACTUAL PARAMETERS, BUT ONLY I N THE L I S T \" ) (LOOK-FOR-XTRA 'SETQ) ) ) (TEST-OUTPUT '(EQ *REPLACE '(B B C ) ) o u t p u t 0 1 2 . . ( ( P R I N T 'LOOKS GOOD AT F I R S T GLANCE\") ) ) )) O b v i o u s l y f o r segment REPLACE t h e r e w o u l d need t o be s e v e r a l more e l e m e n t s l i k e t h e above i n t h e DIAGNOSTIC m o d e l . The a d v a n t a g e s o f t h i s d e s i g n f o r a d i a g n o s t i c m o d e l ( a s a L I S P p r o g r a m t o be EVALd) a r e o b v i o u s , s i n c e i t a l l o w s a l m o s t an u n l i m i t e d r a n g e o f t e s t i n g , and a n a l y s i s , n o t t o m e n t i o n t h e e a s e o f i m p l e m e n t a t i o n . The L I S P C A I s y s t e m w o u l d o n l y p r o v i d e a f r a m e w o r k f o r t h i s 8 4 d i a g n o s t i c model, and procedures to m a i n t a i n and execute i t . I t would be up to i n d i v i d u a l t e a c h e r s to d e c i d e upon the s p e c i f i c t e s t s and expected r e s u l t s , the l e v e l of i n t e r a c t i o n , s i z e and scope, r e m e d i a l v a l u e , and to prime i t a c c o r d i n g l y . T h i s d i a g n o s t i c model i s not c o n s i d e r e d to be a complete debugging system. In f a c t i t i s o n l y a s i m p l i f i e d form of program v e r i f i c a t i o n , which i s s t i l l an undeveloped a r e a of a r t i f i c i a l i n t e l l i g e n c e and computer s c i e n c e . I t i s c e r t a i n l y not easy to determine s t u d e n t s ' e r r o r s t h a t i n v o l v e an i n t e r a c t i o n of m i s c o n c e p t i o n s or bugs. Moreover, not a l l the sample problems can p o s s i b l y m a n i f e s t a l l of the symptoms, so i t i s n e i t h e r p o s s i b l e to guarantee c o r r e c t code, nor i s i t p o s s i b l e to c a t c h a l l e r r o r s . I f a s t u d e n t ' s a l g o r i t h m d i f f e r s from the one employed by the system, a r e a s o n a b l e amount of d i f f i c u l t y can be e x p e c t e d . However, w i t h o u t a module f o r deducing a model of the f u n c t i o n from the code i t s e l f , and w i t h o u t a means of massaging d i f f e r e n t models i n t o one u n i v e r s a l model f o r a p a r t i c u l a r f u n c t i o n , an e x t r e m e l y f l e x i b l e d i a g n o s t i c model such as the above, or the BUGGY system of Brown & B u r t o n , p r o v i d e s the most p r o m i s i n g p a r t i a l s o l u t i o n t o the e r r o r 8 5 d e t e c t i o n and c o r r e c t i o n problem. By a n n o t a t i n g the a c t u a l model of the segment w i t h warnings and demons at those p a r t i c u l a r p o i n t s i n the program which are e xpected to g i v e d i f f i c u l t i e s , the LISPCAI system can f u r t h e r m o r e watch f o r and be c o g n i z a n t of d i f f i c u l t and/or s p e c i a l s i t u a t i o n s . T h i s i s the purpose of the t h i r d e r r o r d e t e c t i o n and c o r r e c t i o n system which employs a set of CAVEATS or warnings as a n n o t a t i o n s on the model of each s p e c i a l segment. Note t h a t these CAVEATS e x i s t as e x t e n s i o n s to the model of each important segment i n the f u n c t i o n , whereas the DIAGNOSTIC model a p p l i e s t o the complete s t u d e n t - p r o d u c e d LISP f u n c t i o n as a whole. Thus the DIAGNOSTIC model measures peformance, as opposed to the CAVEATS w h i c h , as we s h a l l see, are more concerned w i t h methodology and s t r a t e g y p l a n n i n g . 86 V.3 A n n o t a t i n g the Model w i t h CAVEATS A c t u a l e x e c u t i o n of LISP f u n c t i o n s , v i a a DIAGNOSTIC model, cannot i d e n t i f y or l o c a t e e r r o r s which may be the r e s u l t of i n c o m p l e t e programming. Nor i s the e r r o r d e t e c t i o n c a p a b i l i t y of vthe g l o b a l d i a g n o s t i c model a l l encompassing. S i n c e e r r o r s are not i s o l a t e d or independent from each o t h e r , the c o n t e x t i n which they occur i s most s i g n i f i c a n t . T h i s c o n t e x t s e n s i t i v i t y of e r r o r s r e q u i r e s some way of l i n k i n g e r r o r c h e c k i n g to s p e c i f i c p i e c e s of LISP code, i n o r d e r to d e a l w i t h e r r o r s which occur l o c a l l y i n the program. We do not c l a i m to be a b l e to s o l v e t h i s problem, but as a p a r t i a l s o l u t i o n we i n t r o d u c e a t h i r d l e v e l of debugging and a d v i c e , which e x i s t s as a n n o t a t i o n on the segments c o m p r i s i n g the d e s i r e d f u n c t i o n . Each segment w i l l not o n l y have SPECS and PLANS, but w i l l a l s o have a d i a g n o s t i c s t r u c t u r e c a l l e d CAVEATS. T h i s w i l l a l l o w a l i m i t e d a n a l y s i s of each segment of the program as i t i s typed i n by the s t u d e n t . J u s t l i k e the MALT system of Koffman & B l o u n t (1975), t h i s makes sense, because each p i e c e of LISP code c o r r e s p o n d s to one of the segments, w i t h 87 a s et of SPECS and PLANS, i n t o which the g r e a t e r t a s k has been d i v i d e d . A CAVEAT w i l l be e i t h e r a t t a c h e d t o some segment as a fo r m a l d e s c r i p t i o n of the expected common stud e n t e r r o r s which are l i k e l y to o c c u r , or as a w a r n i n g t o be i s s u e d t o the studen t w h i l e c o d i n g t h a t p a r t i c u l a r segment. J u s t as G o l d s t e i n & Grimson (1977) found the need t o augment p r o d u c t i o n systems w i t h e x t r a a n n o t a t i o n , so we f i n d t h a t SPECS and PLANS ( i . e . the f u n c t i o n d e s c r i p t i o n ) , need to be an n o t a t e d w i t h debugging commentary. In t h e i r s k i l l model which c o n t r o l l e d a f M g h t s i m u l a t o r , G o l d s t e i n & Grimson found some p r e l i m i n a r y e v i d e n c e t h a t \" a n n o t a t i o n s . . . . c o u l d model c e r t a i n bugs and c e r t a i n l e a r n i n g b e h a v i o r s c h a r a c t e r i s t i c of s t u d e n t s \" , ( G o l d s t e i n & Grimson, Feb. 1977). G o l d s t e i n ' s a n n o t a t o r i n model d r i v e n debugging of s i m p l e p i c t u r e programs \" a l e r t s the debugger to o d d i t i e s i n program s t r u c t u r e which may be the u n d e r l y i n g cause of some semantic v i o l a t i o n \" , ( G o l d s t e i n , Sept. 1974). CAVEATS w i l l m o s t l y be a l i s t of warnings and/or comments to both the t u t o r and the s t u d e n t s . When the t u t o r c o n s i d e r s the code t h a t a studen t produces, i t s a t t e n t i o n w i l l be drawn to s p e c i a l i s s u e s w h i c h may be c r i t i c a l , but are l i k e l y t o be i g n o r e d . CAVEATS might a l s o p r o v i d e e x p l i c i t 88 i n f o r m a t i o n , a b o u t t h e t y p e o f code n e e d e d t o a c h i e v e a g o a l , i n t h e f o r m o f m e s s a g e s t o t h e s t u d e n t s . E s p e c i a l l y i n t h e c a s e when a s t u d e n t s t a r t s t o d i v e r g e f r o m t h e m o d e l , t h e s e CAVEATS c a n i n f o r m h i m / h e r o f h i s d i v e r g e n c e and c a n a l s o a c t as a r e m i n d e r t o t h e s y s t e m t h a t t h e s t u d e n t i s no l o n g e r f o l l o w i n g t h e i n t e r n a l m o d e l . T h i s i s e s p e c i a l l y u s e f u l i f some p r o g r a m o d d i t y i s q u i t e common and b o t h h a r m l e s s a n d / o r i n t e n d e d by t h e pr o g r a m m e r . Thus i t i s c l e a r t h a t t h e r o l e o f CAVEATS i s n e i t h e r p u r e l y f o r d e b u g g i n g , n o r i s i t t h a t o f t e a c h i n g a i d . They e x i s t s s i m p l y as comments on t h e s t r u c t u r e f o r e a c h segment, and s u p p l y t h e i n f o r m a t i o n , w h i c h i s s t o r e d on t h e i r s t r u c t u r e , w h e n e v e r t h e y a r e t r i g g e r e d . I t i s e n v i s a g e d t h a t e a c h CAVEAT w i l l c o n s i s t o f two p a r t s , v i z . : a p a t t e r n and an a c t i o n . I n a s t a n d a r d p a t t e r n d i r e c t e d mode, i f i t i s o b s e r v e d t h a t t h e s t u d e n t ' s c o d e s a t i s f i e s t h e p a t t e r n p a r t o f any CAVEAT, t h e n t h e a c t i o n p a r t w i l l be e x e c u t e d . I n t h i s mode, a n n o t a t i o n s a r e u s e d f o r d e b u g g i n g i n v a l i d code w h i c h may have t r i g g e r e d t h e CAVEAT. F o r e x a m p l e , i f i t i s n o t i c e d t h a t t h e s t u d e n t ' s l a s t COND c l a u s e i n t h e REPLACE f u n c t i o n i s : (T (CONS A T I (REPLACE A TI AT2 (CDR L ) ) ) ) i n s t e a d o f 89 (T (CONS (CAR L) (REPLACE ATI AT2 (CDR L ) ) ) ) then the a p p r o p r i a t e CAVEAT, which watches f o r t h i s common e r r o r , c o u l d t r i g g e r the a p p r o p r i a t e e r r o r message. Hence the CAVEAT a c t s as debugger. In t h i s same p a t t e r n d i r e c t e d mode, a n n o t a t i o n s can be used to i n f o r m the LISPCAI system of some v a l i d d i v e r g e n c e i n the s t u d e n t ' s program. For example, were the studen t t o negate the EQTEST statement i n REPLACE, then the t u t o r must be informed t h a t DIRECTION - 3 and DIRECTION - 4 i n the PLANS f o r REPLACE ought to be r e v e r s e d . i . e . (COND ((EQ A B ) C) (T D) ) i s e q u i v a l e n t t o : (COND ((NOT (EQ A B )) D) (T C) ). In t h i s form the CAVEAT would act as a knowledgeable t u t o r , w h i c h , when i t n o t i c e s v a l i d d i v e r g e n c e , makes the a p p r o p r i a t e adjustments to the model. T h i s m o d i f i c a t i o n of the model when t r i g g e r e d by a CAVEAT, i s o b v i o u s l y not q u i t e so s i m p l e t o implement. I t would r e q u i r e t h a t the LISPCAI system i n c o r p o r a t e s u t i l i t i e s a b l e t o p e r f o r m s i m p l e m a n i p u l a t i o n s to the s t r u c t u r e s a s s o c i a t e d w i t h a segment, i . e . to a l t e r the DATA and CONTROL FLOW s t r u c t u r e s . Even so, i t i s p o s s i b l e t o en v i s a g e the f o l l o w i n g CAVEAT i n the EQTEST segment of the model f o r f u n c t i o n REPLACE. 90 CAVEATS (PATTERN @NOT@) (ACTION (PRINT 'YOUR TEST IS THE REVERSE OF THE MODEL, S T I L L ACCEPTABLE\") (NEGATE-TRUTHVALUES DIRECTION-3 D I R E C T I O N - 4 ) ) T h i s c o u l d m o d i f y t h e PLANS fo,r REPLACE t o accommodate t h e s t u d e n t as f o l l o w s : PLANS (CONTROLFLOW ... (NEXT EQTEST-14 (DIRECTION-3 N I L (DIRECTION-4 TRUE Thus t h e EQTEST i s now e f f e c t i v e l y a NOT EQTEST. 91 The p a t t e r n p a r t s o f CAVEATS c o u l d a l s o be s i m p l e t r u t h v a l u e s , w h i c h when TRUE f i r e t h e a c t i o n p a r t s , s o t h a t comments c o u l d be made a c c o r d i n g t o t h e p a r t i c u l a r needs o f a s i t u a t i o n . The s t r u c t u r e f o r segment REPLACE i t s e l f c o u l d be a n n o t a t e d w i t h t h e f o l l o w i n g CAVEAT: CAVEATS (PATTERN TRUE) (ACTION ( P R I N T 'TEST FOR AN EMPTY L I S T BEFORE ANYTHING E L S E \" ) ) T h i s m i g h t be u s e f u l i f i t s t u d e ' n t s , ( p e r h a p s - u n f a m i 1 i a r NULLTEST s h o u l d p r e c e d e a l l t h e w e r e n e c e s s a r y t o i n f o r m w i t h r e c u r s i o n ) , why t h e o t h e r s e g m e n t s . E f f e c t i v e l y CAVEATS a r e t h u s s e r v i c e d i n two w a y s . W i t h t r u t h v a l u e s as p a t t e r n s , t h e i r a c t i o n s c a n be f o r c e d upon e n t r y t o a se g m e n t . W i t h l o g i c a l e x p r e s s i o n s as p a t t e r n s , t h e y c a n r e s i d e as demons w a i t i n g t o be t r i g g e r e d by some s p e c i f i c s i t u a t i o n . CAVEATS a r e n o t i n t e n d e d t o t e s t t h e 9 2 correctness of the program, but are only to be used for making the student and the tutor more cognizant of the problem and the changing environment. 93 V.4 C o n c l u s i o n These d i a g n o s i s r o u t i n e s w i l l p r i m a r i l y be used to h e l p the student produce a v a l i d program which s o l v e s a g i v e n problem. The i s s u e of how procedures are un d e r s t o o d and/or l e a r n e d by a p e r s o n , have not been i n v e s t i g a t e d . Nor do we make a f o r m a l attempt at program v e r i f i c a t i o n . Even so, a fo r m a l program v e r i f i c a t i o n system which d e a l s w i t h programs i n a n o n - n a t u r a l way would not be most s u i t a b l e f o r studen t e d u c a t i o n . I t i s hoped though, t h a t by b e i n g l e d to the p r o d u c t i o n of p a r t i c u l a r c o r r e c t programs, the studen t w i l l l e a r n the d e s i r e d programming t e c h n i q u e s , and w i l l become aware of the source of many e r r o r s . T h i s knowledge s h o u l d be s u f f i c i e n t t o enable him/her to produce programs of a more g e n e r a l n a t u r e . CHAPTER VI THE TUTORING PROCESS In t h i s s e c t i o n we w i s h to g i v e the reader some id e a of the form t h a t a l e s s o n might t a k e , under the s u p e r v i s i o n of t h i s L I SP CAI t e a c h i n g system. I t i s expected t h a t a stude n t w i l l be s e a t e d at a t e r m i n a l and would take the LISP l e s s o n by i n t e r a c t i n g w i t h the LISP t e a c h i n g machine. The complete d e t a i l s of t h i s i n t e r a c t i o n are as yet un d e c i d e d , but the e x p e r i e n c e of o t h e r s , such as John S e e l y Brown, at B o l t , B e r a n e k , and Newman, I r a G o l d s t e i n at MIT, P a t r i c k Suppes at the I n s t i t u t e f o r M a t h e m a t i c a l S t u d i e s i n S o c i a l S c i e n c e (IMSSS) at S t a n f o r d , and Green & Barstow at S t a n f o r d , seems to i n d i c a t e t h a t .a l e s s o n such as the one d e s c r i b e d below s h o u l d be q u i t e f e a s i b l e at the im p l e m e n t a t i o n l e v e l . 9 5 VI 1 T e a c h i n g S t r a t e g y T e a c h i n g L I S P p r o g r a m m i n g i n v o l v e s t h r e e m a j o r m o d u l e s , c o r r e s p o n d i n g t o F i g u r e 1 i n C h a p t e r I . T h e s e a r e : 1) The t e a c h i n g o f s t a t i c i n f o r m a t i o n and c o n c e p t s , 2 ) T u t o r i n g and a i d i n g i n t h e d e s i g n and c o n s t r u c t i o n o f p r o g r a m s , and 3) The s u b s e q u e n t a n a l y s i s o f t h e s e p r o g r a m s and r e m e d i a l t e a c h i n g . We c o n s i d e r t h e f i r s t m o d u l e as t h e most t r i v i a l , s i n c e s t a t i c k n o w l e d g e has been t r a d i t i o n a l l y t a u g h t by s i m p l y r e f e r e n c i n g p i e c e s o f t e x t . We have p r o p o s e d t h a t a s e m a n t i c n e t w o r k be u s e d t o a l l o w d i s c u s s i o n and c o m m u n i c a t i o n b e t w e e n s t u d e n t and \" t e a c h e r \" . The t h i r d m o d u l e c o u l d e a s i l y be b r u s h e d a s i d e by e m p l o y i n g a d i a g n o s t i c s y s t e m w h i c h o n l y p r o v i d e s t h e s t u d e n t w i t h a \" y e s / n o \" a n s w e r . S u c h a s y s t e m i s o b v i o u s l y u n a c c e p t a b l e when i t come t o t e a c h i n g p r o g r a m m i n g . I n t h i s s e c t i o n , h o w e v e r , when we d i s c u s s t h e t u t o r i n g p r o c e s s , we w i l l r e g a r d t h e d i a g n o s t i c m o d u l e as a b l a c k box w h i c h s i m p l y r e t u r n s \" y e s \" i f c o r r e c t o r a s u i t a b l e e r r o r m e s s a g e o t h e r w i s e . T h i s d i a g n o s t i c 96 module was d i s c u s s e d s e p a r a t e l y i n Chapter V. Thus, t h i s s e c t i o n w i l l d e s c r i b e how a s t u d e n t i s a i d e d i n f o r m u l a t i n g a p l a n of a t t a c k , how he/she i s l e d to an u n d e r s t a n d i n g of the problem, i t s g o a l s and r e q u i r e m e n t s , and how the s t u d e n t i s d i r e c t e d a l o n g the path from t h i s p l a n to the c o n s t r u c t i o n of a LISP program. Te a c h i n g t h i s p r o c e s s of program c o n s t r u c t i o n \"can p r o b a b l y best be a c c o m p l i s h e d by f o c u s s i n g on the domain of knowledge the student i s to s p e c i a l i z e i n \" , (Brown, C o l l i n s , & H a r r i s , June 1977, p. 4 2 ) . By l i m i t i n g the t a s k to be a c c o m p l i s h e d , t o one s p e c i f i c program, knowledge s p e c i f i c to t h a t program can be i n c o r p o r a t e d to a i d the t u t o r . I t i s to t h i s end t h a t our model of LISP f u n c t i o n s i s so complete. T h i s model i s p o w e r f u l enough to enable a s t u d e n t to have a 1-1 r e l a t i o n s h i p w i t h an \" e x p e r t \" who can h e l p him or her c r e a t e i d e a s , experiment w i t h these ideas i n LISP code, and debug these ideas and code. The s t u d e n t w i l l go about u n d e r s t a n d i n g the program by s e e i n g the p r o c e s s e v o l v e i n the \" e x p e r t ' s head\". T h i s \" e x p e r t \" which i s n o t h i n g more than the t u t o r i n g module of our system, would use the f u n c t i o n model as r e f e r e n c e . I t thus would not have to see the program as a b l a c k box w i t h i n p u t s and o u t p u t s . In 97 f a c t , the \" e x p e r t \" c o u l d a l s o m o n i t o r and improve the s t u d e n t ' s programming s t y l e by d i r e c t i n g him or her to f o l l o w t h a t s t y l e l a i d out i n the model of the LISP f u n c t i o n . I d e a l l y , we would l i k e t h i s \" e x p e r t \" to be a r t i c u l a t e enough to d e s c r i b e e x p l i c i t l y b a s i c LISP knowledge, p l a n n i n g knowledge, and s t r a t e g i e s n e c e s s a r y f o r w r i t i n g a s t y l i s t i c a l l y s a t i s f a c t o r y program. As i t i s , our model does not a l l o w such h i g h e r l e v e l knowledge such as p l a n s and s t r a t e g i e s , to be s t o r e d e x p l i c i t l y . N o n e t h e l e s s , a c e r t a i n amount of a r t i c u l a t i o n c o u l d be b u i l t i n t o the t u t o r i n g module a l l o w i n g the \" e x p e r t \" to e x t r a c t t h a t p l a n n i n g i n f o r m a t i o n which i s i m p l i c i t i n the model ( a l b e i t lower l e v e l p l a n s ) , and to communicate i t to the s t u d e n t so t h a t he/she c o u l d produce a good program. A major assumption of t h i s LISP t u t o r i s t h a t i t i s not always s u f f i c i e n t to a l l o w s t u d e n t s to w r i t e a complete program i n d e p e n d e n t l y and o n l y examine the r e s u l t a n t e f f o r t as a whole. We contend, t h a t s e p a r a t i n g debugging from p l a n n i n g and programming w i l l l e a d to a l a c k of i n s i g h t i n t o the s t r u c t u r e of the problem. Moreover, such an approach would e n t a i l t h a t the sudent's p l a n need be near p e r f e c t the f i r s t t i m e . R a t h e r , we see program w r i t i n g as a p r o c e s s 98 i n v o l v i n g p a r a l l e l p l a n n i n g and d e b u g g i n g , w h e r e b y i n c o m p l e t e schemas a r e c o r r e c t e d and d e v e l o p e d u n t i l t h e e n t i r e g o a l i s met. T h u s , o u r t e a c h i n g s t r a t e g y i s t o h e l p t h e s t u d e n t a n a l y z e and debug e a c h s u b - s e c t i o n o f c o d e as i t i s w r i t t e n , e n s u r i n g t h a t e a c h s u b - p l a n i s p r o p e r l y r e a l i s e d by a s a t i s f a c t o r y p i e c e o f L I S P c o d e . T h i s i m p l i e s t h a t o u r s y s t e m must c o n s i d e r code i n t e r m s o f g o a l s and s u b - g o a l s . Once a g a i n , i t must be e m p h a s i z e d t h a t we a c c e p t t h a t t h e w h o l e i s more t h a n t h e sum o f i t s p a r t s and we c o n s e q u e n t l y i n t e n d t o a n a l y z e and debug t h e w h o l e , c o m p l e t e d p r o g r a m by means o f a d i a g n o s t i c m o d e l w h i c h w i l l t e s t t h e code by e x e c u t i n g i t on s p e c i a l t e s t d a t a . I n l i n e w i t h t h e s e a s s u m p t i o n s , i t i s e n v i s a g e d t h a t a s t u d e n t w i l l be g u i d e d t h r o u g h t h e f o l l o w i n g p a t h i n d e s i g n i n g a p r o g r a m t o s o l v e a p a r t i c u l a r p r o b l e m . A m o d e l o f t h e d e s i r e d L I S P f u n c t i o n ( s ) w i l l a l r e a d y have been s t o r e d i n t h e s y s t e m i n s u c h a way t h a t t h e f u n c t i o n ( s ) w i l l be d i v i d e d i n t o m e a n i n g f u l i n p u t / o u t p u t s e g m e n t s . A s s o c i a t e d w i t h e a c h segment w i l l be p l a n n i n g i n f o r m a t i o n , I/O i n f o r m a t i o n , d i a g n o s t i c i n f o r m a t i o n , and a c t u a l L I S P c ode w h i c h w o u l d r e a l i s e t h a t segment. The t u t o r w i l l t h e n be a b l e t o h e l p t h e s t u d e n t d e s i g n t h e L I S P p r o g r a m by 99 r e c u r s i v e l y b u i l d i n g up l a r g e r and l a r g e r segments, composed of p r i m i t i v e LISP f u n c t i o n s and o t h e r sub-segments c o r r e s p o n d i n g to s e c t i o n s of expected LISP code. Each time a p i e c e of code i s w r i t t e n by the s t u d e n t , d i a g n o s t i c r o u t i n e s w i l l be c a l l e d t o check the s t u d e n t ' s code a g a i n s t the s t o r e d model of the f u n c t i o n , t o t r i g g e r any s t o r e d w a r n i n g s , and i n some c a s e s , to compare i t a g a i n s t expected LISP code f o r t h a t segment. T h i s w i l l g i v e some i n d i c a t i o n as to whether the stude n t i s p r o c e e d i n g i n an a c c e p t a b l e manner or n o t . O b v i o u s l y t h i s i s no g u a r a n t e e , but such guarantees are not even p r e d i c t e d f o r the f i e l d of program v e r i f i c a t i o n . At t h i s stage i t w i l l be p o s s i b l e t o i n t e r r u p t programming to proceed w i t h r e m e d i a l t e a c h i n g v i a the model and/or by r e f e r e n c i n g the LISP n o t e s . \\ 100 VI.2 T e a c h i n g Mechanisms The t u t o r i n g p r o c e s s r e s t s on the system's a b i l i t y t o i n c o r p o r a t e the f o l l o w i n g mechansisms, v i z . : a mechanism f o r d e t e r m i n i n g the l e v e l of i n t e r a c t i o n , a n a t u r a l language i n t e r f a c e , and a mechanism to a l l o w the stude n t t o randomly i n t e r r u p t the r e g u l a r f l o w of the l e s s o n . One of the major g o a l s of CAI i s i n d i v i d u a l i z a t i o n of i n s t r u c t i o n , i . e . the act of t a i l o r i n g the l e s s o n to s u i t the needs of the p a r t i c u l a r s t u d e n t . O p t i m a l l y we would l i k e t o gather h i s t o r i c a l d a t a on each stud e n t so t h a t a stude n t l e a r n i n g model c o u l d be c o n s t r u c t e d f o r each p a r t i c u l a r s t u d e n t . T h i s s t u d e n t model c o u l d then be a p p l i e d t o the l e a r n i n g p r o c e s s to p r e s e n t an i n d i v i d u a l i z e d sequence of problems, t o c o n t r o l both the frequ e n c y and type of a s s i s t a n c e g i v e n d u r i n g programming, and to i d e n t i f y a s t u d e n t ' s problem a r e a s . For example, some s t u d e n t s may be s o p h i s t i c a t e d enough so t h a t , g i v e n the SPECS f o r a segment, they would be a b l e to produce the LISP code. On the o t h e r hand, some s t u d e n t s may need to have both the d a t a and c o n t r o l f l o w of a segment's PLANS e x p l i c a t e d and d i s c u s s e d b e f o r e they would be a b l e to w r i t e the c o r r e s p o n d i n g LISP code. S i n c e we do not have such a stude n t m o d e l l i n g c a p a b i l i t y , our t e a c h i n g a l g o r i t h m assumes a \" f r e e \" or \"s t u d e n t c h o i c e \" mode of o p e r a t i o n , where the stud e n t i s g i v e n enough i n f o r m a t i o n to d e c i d e f o r h i m s e l f what l e v e l of e x p l a n a t i o n and t u t o r i n g he needs. For example, h a v i n g d e s c r i b e d a segment's SPECS, the system c o u l d pose the f o l l o w i n g q u e s t i o n : \"Do you f e e l c a p a b l e of w r i t i n g the program on your own? O t h e r w i s e I can go i n t o more d e t a i l . \" Such a query would demand t h a t the stud e n t e s t a b l i s h e s the l e v e l of t u t o r i n g f o r h i m s e l f . The second p r e r e q u i s i t e f o r s u c c e s s f u l t e a c h i n g would be some form of n a t u r a l language i n t e r f a c e between the stud e n t and the system. The stud e n t and t u t o r would have to i n t e r a c t i n s e v e r a l ways. F i r s t l y , t h e r e w i l l be a c e r t a i n amount of d i s c u s s i o n on LISP s y n t a x and s e m a n t i c s . S i n c e t h i s i n f o r m a t i o n would be s t o r e d on a semantic network, the l i k e s of which have been used p r e v i o u s l y i n n a t u r a l language systems, e.g. SCHOLAR, such a d i s c u s s i o n i n n a t u r a l language i s q u i t e c o n c e i v a b l e . When i t comes to program w r i t i n g and e r r o r c o r r e c t i o n however, the system w i l l o n l y be a b l e to r e f e r e n c e t h a t knowledge which i s a t t a c h e d to the program m o d e l l i n g s t r u c t u r e and the d i a g n o s t i c model f o r t h a t f u n c t i o n . The language used i n t e a c h i n g programming c o u l d 102 be q u i t e r i g i d , r e f l e c t i n g the model d i r e c t l y , and s t i l l be a s u c c e s s f u l channel of communication. E.g. \"We w i l l now c o n s t r u c t a program f o r segment \". \"These are the s p e c i f i c a t i o n s f o r segment . I t has as inp u t w i t h the f o l l o w i n g p r e - c o n d i t i o n s \". E r r o r messages c o u l d be t r a n s m i t t e d t o the student d i r e c t l y from the d i a g n o s t i c model i n much the same way as the LISP i n t e r p r e t e r does. The d i a g n o s t i c model w i l l do more than the LI S P e r r o r r o u t i n e s , i n t h a t i t w i l l l i n k t hese messages to the LISP code, and r e f e r e n c e both the f u n c t i o n model and/or the LISP manual when s u g g e s t i n g changes. E.g. \"You have not t e r m i n a t e d the r e c u r s i o n . T h i s i s a c c o m p l i s h e d by segment NULLTEST.\" A d m i t t e d l y , the system would not be a b l e to accept n a t u r a l language input from the s t u d e n t , but t h i s problem i s of g r e a t e r c o m p l e x i t y than the LISP t e a c h i n g system i t s e l f , and i s not c o n s i d e r e d i n t h i s paper. The t h i r d f e a t u r e which would f a c i l i t a t e l e a r n i n g , and i s r e l a t i v e l y easy to implement, i s a stude n t i n t e r r u p t mechanism. At any stage of the l e s s o n a stud e n t may w i s h to r e c a l l i n f o r m a t i o n about the problem i n g e n e r a l , about a s p e c i f i c segment, or about LISP programming. T h i s i n f o r m a t i o n i s made a v a i l a b l e to the stude n t on demand by s i m p l y p o l l i n g a l l input to determine i f i t i s of an i n t e r r u p t i n g n a t u r e . The student may i n t e r r u p t to ask f o r s t a t i c i n f o r m a t i o n s t o r e d on the network; to be reminded of a segment's SPECS; to demand d i v i s i o n of the problem i n t o sub-problems and sub-segments; and to req u e s t a model s o l u t i o n . These above i n t e r r u p t s are of two forms. Requests f o r i n f o r m a t i o n c o u l d s i m p l y employ a s t a c k s t r u c t u r e which a l l o w s the main t a s k to be d e f e r r e d u n t i l the stude n t i s ready. I n t e r r u p t s which demand a change i n the f l o w of a l e s s o n can be handled by jumps to d i f f e r e n t p o s i t i o n s i n the t e a c h i n g a l g o r i t h m , or by p e r f o r m i n g a r e c u r s i o n of the a l g o r i t h m at a lower l e v e l . 104 V I . 3 The T u t o r i n g A l g o r i t h m In r e c e n t y e a r s , the s t r u c t u r e d programming movement has made computer s c i e n t i s t s more concerned w i t h the a c t u a l c r e a t i o n of programs. LISP programming i s i n h e r e n t l y m o d u l a r i l y d e s i g n e d so t h a t the arrangements of segments i s h i g h l y s t r u c t u r e d . C o n s e q u e n t l y , the t u t o r i n g a l g o r i t h m i s a p p l i e d i n a b r e a d t h - f i r s t manner. Top l e v e l segments are d i s c u s s e d and t a u g h t , assuming t h a t r e f e r e n c e s to lower l e v e l sub-segments w i l l be s a t i s f i e d by the c r e a t i o n of these lower l e v e l sub-segments at a l a t e r s tage i n the l e s s o n . T h i s modular approach makes f o r e a s i e r i n s t r u c t i o n , h e l p s reduce the number of c a r e l e s s and s y n t a c t i c bugs, and h e l p s the a n a l y s i s r o u t i n e s l o c a t e and c o r r e c t r a t i o n a l bugs more e a s i l y . G i v e n the problem to be s o l v e d , the f u n c t i o n model i s used to g u i d e a top-down p l a n n i n g p r o c e s s which begins by s p e c i f y i n g the h i g h e s t l e v e l segment. T h i s main segment i s taught by f o l l o w i n g a path through the d a t a and c o n t r o l f l o w of i t s model. Code i s c o n s t r u c t e d by the s t u d e n t f o r t h i s top l e v e l segment i n a l i n e a r f a s h i o n , under the d i r e c t i o n 105 of the model. Each time a sub-segment i s r e f e r e n c e d i n t h i s d i s c u s s i o n , the s t u d e n t w i l l s i m p l y i n c l u d e a r e f e r e n c e to t h a t sub-segment i n h i s / h e r LISP code. On c o m p l e t i o n of program w r i t i n g f o r the top l e v e l , code w i l l be w r i t t e n f o r each sub-segment at the next l e v e l by r e c u r s i n g the system and f o l l o w i n g the same l i n e of a t t a c k . The s e c t i o n s of code f o r a l l sub-segments at a l l l e v e l s w i l l then e i t h e r be r e c u r s i v e l y s u b s t i t u t e d f o r t h e i r r e f e r e n c e s i n the h i g h e r l e v e l segments, or they w i l l be s t o r e d as s e p a r a t e LISP f u n c t i o n s to be r e f e r e n c e d by the code of the h i g h e r l e v e l segments. As each segment i s w r i t t e n , debugging r o u t i n e s w i l l be c a l l e d to a n a l y z e the LISP code u n t i l f i n a l l y , the whole program can be t e s t e d a g a i n s t a d i a g n o s t i c model f o r t h a t program or f u n c t i o n . The t u t o r i n g a l g o r i t h m takes the f o l l o w i n g form: 1) D e s c r i b e the problem and of the p r e v i o u s l e s s o n s , semantic network which are program. r e l a t e i t both to the t e x t and to c o ncepts i n the r e l e v a n t to the r e q u i r e d 106 2) Set a l e v e l - i n d i c a t o r t h i s w i l l i n d i c a t e which c u r r e n t l y b e i n g d i s c u s s e d . to z e r o . At any one time l e v e l of the program i s 3) Supply the s t u d e n t w i t h an E n g l i s h language d e s c r i p t i o n of the c u r r e n t segment at l e v e l n. T h i s d e s c r i p t i o n i s s t o r e d on the segment's p r o p e r t y l i s t under the a t t r i b u t e DESCRIPTION. 4) H e l p the student determine the SPECS f o r t h i s segment at l e v e l n. \"What w i l l be the i n p u t s ? \" ... \"How do they e n t e r the segment?\" ... \"We w i l l name these i n p u t s ATI, AT2 r e s p e c t i v e l y . \" 5) D e s c r i b e those sub-segments at l e v e l n+1 which t h i s segment w i l l r e f e r e n c e . These are a v a i l a b l e from the SUB-SEGS e n t r y i n the segment's PLANS. (Note t h a t p r i m i t i v e segments are not i n c l u d e d i n t h i s l i s t of r e l e v a n t sub-segments.) 6) I f the s t u d e n t f e e l s t h a t he or she i s unable to produce the r e q u i r e d program w i t h o u t some t u t o r a i d , ( g i v e n the SPECS, and assuming t h a t a l l sub-segments at l e v e l n+1 a l r e a d y e x i s t ) , then more e x p l a n a t o r y 107 i n f o r m a t i o n abo.ut the f o l l o w i n g i s n e c e s s a r y : a) Mechanisms by which i n p u t s e n t e r and outputs\" l e a v e the segment. ( F r e e - v a r i a b l e s , bound arguments, e t c . ) b) Input and output d e t a i l s of the n o n - p r i m i t i v e sub-segments at l e v e l n+1. A c t u a l LISP code from t h e i r minor segment e n t r i e s on the d a t a base, t o i l l u s t r a t e the manner i n which they a re r e f e r e n c e d by the segment at l e v e l n. c) The manner i n which d a t a f l o w s through the segment, i . e . between the n o n - p r i m i t i v e and p r i m i t i v e sub-segments. A v a i l a b l e from the DATAFLOW statements of the segment at l e v e l n. d) P o s i t i o n i n the code where sub-segments a re a c t u a l l y r e f e r e n c e d . A v a i l a b l e from the CONTROLFLOW of the segment's PLANS. e) The a c t u a l expected LISP code f o r the segment at l e v e l n. T h i s i s a v a i l a b l e from the c o d e - e n t r y on the segment's major data-base e n t r y . (Used f o r 108 prompt ing.) 7) At t h i s p o i n t a c t u a l LISP code s h o u l d now e x i s t to r e a l i s e the segment at l e v e l n. T h i s w i l l have e i t h e r been produced i n d e p e n d e n t l y by the s t u d e n t , or w i t h a i d and prompting from the t u t o r at s t e p 6. T h i s code i s passed to the a n a l y s i s and d i a g n o s i s r o u t i n e s ' t o check f o r common e r r o r s , v a l i d code, and SPECS s a t i s f a c t i o n . 8) I f the code i s e r r o n e o u s , and a) the e r r o r can be determined and i d e n t i f i e d by the a n a l y s i s r o u t i n e s , then s i m p l y i n f o r m t h e \" student of the e r r o r , h e l p him make the n e c e s s a r y c o r r e c t i o n s by r e f e r e n c i n g a p o s i t i o n i n h i s code, and r e t u r n to the a n a l y s i s r o u t i n e s at s t e p 7. b) the e r r o r cannot be i d e n t i f i e d by the a n a l y s i s r o u t i n e s , then o b v i o u s l y the program does not pe r f o r m w e l l enough compared to any expected model. Such a program w i l l need to be r e d e s i g n e d f o r the t u t o r t o be of any use. Hence a r e t u r n t o the \" d e t a i l e d e x p l a n a t i o n \" r o u t i n e s at s t e p 6 w i l l be n e c e s s a r y . 109 9) At t h i s p o i n t the code appears to be c o r r e c t . a) I f t h e r e a re any segments at the same l e v e l ( l e v e l n) to be d i s c u s s e d , s i m p l y i t e r a t e the a l g o r i t h m . In oth e r words, a p p l y the a l g o r i t h m b r e a d t h - w i s e to the next sub-segment which ~ forms p a r t of the p l a n f o r a segment at l e v e l n-1. (Step 3) Note t h a t at l e v e l 0 t h e r e can o n l y be a s i n g l e segment. b) I f t h e r e a re no more segments to be coded at the same l e v e l , but n o n - p r i m i t i v e sub-segments at l e v e l n+1 are s t i l l t o be coded, then increment the l e v e l - i n d i c a t o r and r e c u r s e the a l g o r i t h m t o t u t o r programming at a lower l e v e l i n the p l a n . c) O t h e r w i s e , r e c u r s i v e l y s u b s t i t u t e the code of lower l e v e l sub-segments back i n t o the h i g h e r l e v e l segments to y i e l d a complete program. 10) Peform g l o b a l e r r o r d i a g n o s i s t o check f o r l i n k a g e s between segments and p o s s i b l y make a second pass through e r r o r c o r r e c t i o n r o u t i n e s f o r minor 110 a d j u s t m e n t s . ( S t e p 8) 11) D i s c u s s b r i e f l y p o s s i b l e a l t e r n a t e L I S P p r o g r a m s t o s o l v e t h e p r o b l e m . T h e s e a r e s t o r e d as a l t e r n a t e c o d e - e n t r i e s on t h e m a j o r s e g m e n t ' s d a t a - b a s e e n t r y . I t must be r e a l i s e d t h a t t h e a c t u a l l e s s o n i n p r o g r a m m i n g may be somewhat more d i s j o i n t t h a n t h e a l g o r i t h m . S t u d e n t s w i l l p r o b a b l y i n t e r r u p t t h e t u t o r on s e v e r a l o c c a s i o n s , t o g e t e x t r a i n f o r m a t i o n , t o r e v i s e t o p i c s c o v e r e d by t h e t e x t , o r t o r e f e r e n c e any r e l e v a n t c o n c e p t s w h i c h may be s t o r e d on t h e s e m a n t i c n e t w o r k . I l l V I . 4 C o n e l u s i o n M o r e g e n e r a l l y , t h e t e a c h i n g a l g o r i t h m s and m o d e l s a r e g e a r e d t o w a r d s p r o v i d i n g i n d i v i d u a l i z e d i n s t r u c t i o n f o r a v a r y i n g s t u d e n t p o p u l a t i o n . J e r m a n d e f i n e s i n d i v i d u a l i z e d i n s t r u c t i o n i n an e d u c a t i o n a l c o n t e x t as m e a n i n g , \" ( i ) t h a t e a c h s t u d e n t s h o u l d be p e r m i t t e d t o p r o c e e d as r a p i d l y as h i s own a b i l i t y w i l l p e r m i t a n d , ( i i ) i n s t r u c t i o n a l v a r i a b l e s s u c h as ... t h e l e v e l o f d i f f i c u l t y o f e x e r c i s e s , be a d a p t e d t o t h e a c h i e v e m e n t l e v e l o f e a c h i n d i v i d u a l , as much as p o s s i b l e , w h e r e v e r p o s s i b l e . \" ( J e r m a n , May 1972, p. 395) . The t u t o r i n g p r o c e s s d e s c r i b e d a b o v e , n o t o n l y p r o v i d e s t h e o p p r t u n i t y f o r t e a c h i n g p r o c e d u r a l k n o w l e d g e , b u t a l s o a t t e m p t s t o accommodate t h e i n d i v i d u a l d i f f e r e n e c e s i n t h e s t u d e n t p o p u l a t i o n . CHAPTER V I I CONCLUSION Our i n t e r e s t i n CAI, as mentioned i n Chapter I I , i s s i m p l y to c r e a t e a t u t o r c a p a b l e of p r o v i d i n g s t u d e n t s w i t h m e a n i n g f u l l e s s o n s , i n such a way as to enhance the g e n e r a l l e v e l of knowledge. S p e c i f i c a l l y , w i t h r e g a r d t o t e a c h i n g programming languages, we b e l i e v e t h a t i t i s not enough to s i m p l y s u p p l y t e x t b o o k type knowledge. Thus the d e s i g n of our LISPCAI system was based upon the concept of \" l e a r n i n g by d o i n g \" , r a t h e r than \" l e a r n i n g by s e e i n g or h e a r i n g \" . T h i s LISPCAI t u t o r has emphasized c e r t a i n a s p e c t s of l e a r n i n g programming which are e s s e n t i a l , but o f t e n taken f o r g r a n t e d , or even i g n o r e d . F i r s t l y , by b a s i n g the l e s s o n s on a model of a LISP f u n c t i o n , t h i s t u t o r can c e r t a i n l y encourage or even demand good programming s t y l e . T h i s model of the f u n c t i o n enables the system to be c o g n i z a n t , not o n l y of the LISP language, but a l s o of the a r t of programming. Hence the LISP t u t o r can s u c c e s s f u l l y mer«ge the p r o c e s s of l e a r n i n g LISP w i t h the p r o c e s s of 113 p r o g r a m m i n g i n L I S P . I n t h e f i e l d o f CAI t h i s i s an i m p o r t a n t f a c t o r , s i n c e e a r l i e r s y s t e m s c l e a r l y made' t h e m i s t a k e o f s e p a r a t i n g s t a t i c k n o w l e d g e , d y n a m i c k n o w l e d g e , and t u t o r i n g . F r o m a c o m p u t e r s c i e n c e p o i n t o f v i e w , t h e L I S P t u t o r a l l o w s d i a l o g u e a t t h e p r o b l e m s o l v i n g l e v e l and n o t o n l y a t t h e l e v e l o f p r o g r a m s y n t a x . T h e r e i s s t i l l o p p o r t u n i t y f o r i n c r e a s i n g t h e body o f g e n e r a l p r o g r a m m i n g k n o w l e d g e a v a i l a b l e t o s t u d e n t s . K n o w l e d g e a b o u t s e t s , l i s t s , t e c h n i q u e s , and d a t a s t r u c t u r e s , \" i s n o t i n c l u d e d i n some g e n e r a l l i b r a r y , b u t c o u l d be added t o t h e s e m a n t i c n e t w o r k o r i n c o r p o r a t e d i n t o m o d e l s o f t h o s e f u n c t i o n s w h i c h r e l y upon t h e s e c o m p u t e r s c i e n c e c o n c e p t s . T h e r e a r e o t h e r a r e a s c l o s e l y r e l a t e d t o CAI w h i c h c o u l d e x t e n d t h i s s y s t e m and e n h a n c e i t s u t i l i t y . F u t u r e work c o u l d c o n c e n t r a t e on a more f o r m a l p r o g r a m v e r i f i c a t i o n m o d u l e , s u c h t h a t v a r i a n t s o f a p a r t i c u l a r p r o g r a m c o u l d be more a c c u r a t e l y d i a g n o s e d . I t w o u l d a l s o be most u s e f u l t o i n c o r p o r a t e p r o g r a m g e n e r a t i o n c o n c e p t s , t o e n a b l e t h e s y s t e m t o g e n e r a t e a f u n c t i o n m o d e l f r o m a g i v e n p r o g r a m ( i . e . t h e r e v e r s e d i r e c t i o n ) . S u c h a m o d u l e w o u l d a l s o have t o be c a p a b l e o f m a s s a g i n g e q u i v a l e n t p r o g r a m s t o f i t t h e g l o b a l m o d e l , so t h a t a w h o l e c l a s s o f p r o g r a m s c o u l d be 114 d i a g n o s e d and taught u s i n g a s i n g l e model. As i s , the f u n c t i o n m o d e l l i n g s t r u c t u r e s cannot work i n advanced a p p l i c a t i o n s where EVAL i s b e i n g c a l l e d e x p l i c i t l y on d y n a m i c a l l y c o n s t r u c t e d code. A f u n c t i o n model g e n e r a t o r would be a b l e to p a r t i a l l y s o l v e t h i s problem by d y n a m i c a l l y c o n s t r u c t i n g the s t r u c t u r e s as the code i s d y n a m i c a l l y g e n e r a t e d . W i t h a model g e n e r a t o r , i t would be p o s s i b l e to reduce the i n i t i a l e f f o r t r e q u i r e d by a t e a c h e r i n s e t t i n g up the models f o r the f u n c t i o n s to be t a u g h t . No doubt, i m p l e m e n t a t i o n of the system and a p p l i c a t i o n to the s c h o o l environment, would demand s u b s t a n t i a l e f f o r t i n the areas of n a t u r a l language communication, environment p r e p a r a t i o n , and stud e n t p r o f i l e m o d e l l i n g . T h i s l a t t e r c o u l d be m a i n t a i n e d by the d i a g n o s t i c r o u t i n e s which c o u l d be improved to r e c o r d s t u d e n t s ' a c t i v i t i e s , ( f a i l u r e s , e r r o r s , problems, i n n o v a t i o n s ) , on a data-base. However, as mentioned i n Chapter I , t h i s system i s proposed as a t h e o r e t i c a l model and as such, i t i s complete and s u c c e s s f u l . I mplementation of t h i s system, and a l l CAI systems i n g e n e r a l , has to take i n t o account the broader consequences of computers i n e d u c a t i o n . T e c h n i c a l problems c e r t a i n l y abound, and many of the n e c e s s a r y developments are not 115 t r i v i a l . A l l o c a t i o n of r e s o u r c e s a l s o p l a c e s some c o n s t r a i n t s on the i m p l e m e n t a t i o n of such s o p h i s t i c a t e d CAI systems; and once i n s t a l l e d , t h e r e c e r t a i n l y must be a commitment to even more s o p h i s t i c a t e d s o f t w a r e and equipment, w i t h c o r r e s p o n d i n g l y steep p r i c e s . From a moral p o i n t of view, o t h e r s o b e r i n g problems emerge as u n r e s o l v e d i s s u e s . I t i s easy to imagine an O r w e l l i a n s o c i e t y w i t h people c o n t r o l l e d by machines; where complete e d u c a t i o n a l m o n i t o r i n g and the a s s o c i a t e d banks of p r i v a t e i n f o r m a t i o n c o u l d be used t o u n j u s t l y r e f i n e s t u d e n t c l a s s i f i c a t i o n schemas; where the e f f i c i e n c y of e d u c a t i n g v i a computer systems v i o l a t e s h u m a n i s t i c concerns and s e n s i t i v i t y . On the o t h e r hand, computers are unique, i n t h a t they can s e r v e as c o g n i t i v e t o o l s . CAI systems can be a c t i v e s e r v a n t s , a s s i s t a n t s , and coaches, q u a l i t a t i v e l y d i f f e r e n t from books and t e l e v i s i o n . As Mowshowitz (1976, p.103), o b s e r v e s : \" E d u c a t i o n f o r the masses i n a p l u r a l i s t i c s o c i e t y c a l l s f o r an e x t r a o r d i n a r y b a l a n c i n g a c t . Homogeneity and d i v e r s i t y are a n t a g o n i s t i c p r i n c i p l e s under c o n d i t i o n s of h i g h s t u d e n t - t e a c h e r r a t i o s and s c a r c e r e s o u r c e s . S e n s i t i v i t y to i n d i v i d u a l d i f f e r e n c e s i s a l u x u r y 116 i n t h e t r a d i t i o n a l ... c l a s s r o o m . I f t h e r e i s t o be any t e c h n o l o g i c a l r e v o l u t i o n i n e d u c a t i o n , i t i s most l i k e l y t o come f r o m c o m p u t e r a p p l i c a t i o n s i n t h e l e a r n i n g e n v i r o n m e n t w h i c h a l l o w f o r i n d i v i d u a l i z e d p r o g r a m s . . . . . . . C o m p u t e r - a s s i s t e d i n s t r u c t i o n h o l d s o u t t h e p r o m i s e o f f u n d a m e n t a l c h a n g e s i n t h e p r o c e s s o f e d u c a t i o n . \" 117 BIBLIOGRAPHY B a r r , A., Beard, M. , & A t k i n s o n , R.C. A r a t i o n a l e and d e s c r i p t i o n of the B a s i c I n s t r u c t i o n a l Program. T.R. No. 228, IMSSS, S t a n f o r d U n i v e r s i t y , A p r i l 1974. B a r r , A., B e a r d , M., & A t k i n s o n , R.C. The computer as a t u t o r i a l l a b o r a t o r y : The S t a n f o r d BIP P r o j e c t . T.R. No. 260, IMSSS, S t a n f o r d Uni v e r s i t y , 1975. Barstow, D. A knowledge-based system f o r a u t o m a t i c program c o n s t r u c t i o n . IJCAI 5, M.I.T., 1977, pp.382-388. B i t z e r , D.L., H i c k s , B.L., Johnson, R.L., & Lyman, E.R. The PLATO system: C u r r e n t r e s e a r c h and developments. IEEE T r a n s a c t i o n s on Human f a c t o r s i n E l e c t r o n i c s . V o l . HFE-8, 1967. B o l t , R i c h a r d H. Computer A s s i s t e d S o c r a t i c I n s t r u c t i o n . I n : W i l l i a m D. O r r , ( E d . ) , C o n v e r s a t i o n a l Computers, W i l e y & sons, New Y o r k , 1968. Bork, A.M. E f f e c t i v e computer use i n P h y s i c s e d u c a t i o n . American J o u r n a l of P h y s i c s , V o l . 43, No. 1, January 1975. Bork, A.M. The Computer i n T e a c h i n g - 10 w i d e l y b e l i e v e d myths. ACM SIGCUE B u l l e t i n , V o l . 7, No. 4, October 1973. Boyer, R., & Moore, S. P r o v i n g theorems about LISP programs. JACM, V o l . 2 2 , No. 4, January 1975. Brown, J.S., C o l l i n s , A., & H a r r i s , G. A l and L e a r n i n g S t r a t e g i e s . BBN Report No. 3634, ICAI Report No. 6, 1973. Brown, J.S., & B u r t o n , R.R. D i a g n o s t i c models f o r p r o c e d u r a l bugs i n b a s i c M a t h e m a t i c a l s k i l l s . BBN Report No. 3669, ICAI Report No. 8, 1977. Brown, J.S., & G o l d s t e i n , I . Computers i n a l e a r n i n g s o c i e t y - Testimony f o r the house S c i e n c e and Technology sub-committee on domestic and i n t e r n a t i o n a l P l a n n i n g , A n a l y s i s and C o o p e r a t i o n . October 13, 1977. Brown, J.S., B u r t o n , R.R., & B e l l , A. 118 SOPHIE: A step toward c r e a t i n g a r e a c t i v e l e a r n i n g environment. I n t e r n a t i o n a l Journal of Man-Machine S t u d i e s , V o l . 7, 1975, pp. 675-696. Bunderson, V i c t o r C. Design s t r a t e g y for lea r n e r c o n t r o l l e d courseware. In: EDUCOM, Computing and the D e c i s i o n makers. Spring Conference, 1974. Burton, R.R., & Brown, J.S. A t u t o r i n g and student m o d e l l i n g paradigm for gaming environments. In: Computer Science and Education, SIGCSE B u l l e t i n , V o l . 8, No. 1, February 1976, pp. 236-246. Carbonel1, J.R. AI i n CAI: An i n t e l l i g e n t approach to CAI. IEEE Trans, on Man-Machine Systems, MMS-11, 1970, p.190. C a r r , B. WUSOR I I : A CAI program with student m o d e l l i n g c a p a b i l i t i e s . MIT AI Memo 417, May 1977. Chang, Chin-Lang., & Lee, R i c h a r d , Char-Tung. Symbolic L o g i c and mechanical theorem p r o v i n g . Academic Press, 1973. Clema, J.K., Didday, R.L., & W e s s l e r , M. P r e l i m i n a r y thoughts about a u n i v e r s a l t e a c h i n g machine. AFIPS Conference, 40, 1972. C o l l i n s , A.M., & Q u i l l i a n , M.R. How to make a language user. In: O r g a n i z a t i o n of Memory, E. T u l v i n g , & W. Donaldson, (Eds.), Academic Press, 1972. C o l l i n s , A.M., & G r i g n e t t i , M.C. I n t e l l i g e n t CAI. BBN Report No. 3181, October 1975. C o l l i n s , A., Warnock, E., A i e l l o , N., & M i l l e r , M. Reasoning from incomplete knowledge. In: D.Bobrow & A.Col 1 i n s , ( E d s . ) , R e p r e s e n t a t i o n and understanding s t u d i e s i n C o g n i t i v e Science. Academic Press, New York, 1975. Coulson, John, E.(Ed.) Programmed l e a r n i n g and computer based i n s t r u c t i o n . Wiley, New York, 1962. Crowder, N. Automatic t u t o r i n g by means of i n t r i n s i c programming. In: E . G a l a n t e r , ( E d . ) , Automatic teaching - the s t a t e of the a r t . Wiley H i l l , 1959. Dionne, Mark, S., & Mackworth, Alan K. ANTICS:A System for Animating LISP Programs. Computer Graphics and Image P r o c e s s i n g , V o l . 7, No. 1, February 119 1978. E l l i s , A l l a n , B. The use and misuse of computers i n education. McGraw-Hill Book Company, 1974. F r i e n d , J . Programs students w r i t e . S t a n f o r d Memo AD-A05093/8, J u l y 1975. Gagne, R.M. The c o n d i t i o n s of l e a r n i n g . H o l t , Rinehart & Winston, New York, 1970. G o l d s t e i n , I.P. Understanding simple p i c t u r e programs. AI-TR-294, M.I.T., September 1974. G o l d s t e i n , I.P., & Grimson, E. Annotated p r o d u c t i o n systems: a model f o r s k i l l a c q u i s i t i o n . MIT A l Memo 407, February 1977. G o l d s t e i n , I r a P., & M i l l e r , Mark L. S t r u c t u r e d p l a n n i n g and debugging. A l i n g u i s t i c theory of desig n . MIT A l Lab., A l Memo 387, December 1976. G o l d s t e i n , I r a P. The computer as coach. An a t h l e t i c paradigm f o r i n t e l l e c t u a l education. MIT A l Lab., Memo No. 389, December 1976. G o l d s t e i n , I r a P., & M i l l e r , Mark L. Al based l e a r n i n g environments:- D i r e c t i o n s for long term r e s e a r c h . MIT A l Lab., Memo No. 384, December 1976. G o l d s t e i n , I r a P. The g e n e t i c epistemology of r u l e systems. MIT A l Lab., Memo No. 449, January 1978. Green, C., & Barstow, D. A h y p o t h e t i c a l d i a l o g u e e x h i b i t i n g a knowledge base for a program understanding system. S t a n f o r d A l Lab., Memo AIM-258, January 1975. Green, G.C. The design of the PSI program s y n t h e s i s system. Proc. of the 2nd I n t e r n a t i o n a l Conference on Software e n g i n e e r i n g , San F r a n c i s c o , October 1976, pp. 4-18. Green, G.C, & Barstow, D.R. Some r u l e s for the automatic s y n t h e s i s of programs. IJCAI 4, T b i l i s i , USSR, September 1975, pp.232-239. Green, C. A summary of the PSI program s y n t h e s i s system. IJCAI 120 5, M.I.T., 1977, pp. 380-381. G r i g n e t t i , M.C, &Warnock, E.H. M i x e d - i n i t i a t i v e i n f o r m a t i o n system f o r computer a i d e d t r a i n i n g and d e c i s i o n making. BBN Report No. ESD-TR-73-290, September 1973. G r i g n e t t i , M.C, Hausman, C , & G o u l d , L. An i n t e l l i g e n t o n - l i n e a s s i s t a n t and tutor--NLS-SCHOLAR. I n : P r o c . of the N a t i o n a l Computer C o n f e r e n c e , San D i e g o , 1975, pp. 775-781. H i c k s , B.L., & Hunka, S. The t e a c h e r and the computer. W.B. Saunders Co., 1972 . Holtzman, W.H. ( E d . ) . Computer A s s i s t e d I n s t r u c t i o n , T e s t i n g and Guidance. Harper and Row, New Y o r k , 1970. I h r i e , D.W-A n a l y s i s of s y n t h e t i c s t u d e n t s as a model of human b e h a v i o r . MIT A l Lab., Memo No. 477, May 1978. Jerman, Max. The use of computers to ' i n d i v i d u a l i z e i n s t r u c t i o n . M athematics Teacher, V o l . 65, May 1972. K e a r s l e y , G.P. Some f a c t s about CAI t r e n d s 1970 - 1976. J . E d u c a t i o n a l Data P r o c e s s i n g , 13, 3, 1976. Koffman, E.B., & B l o u n t , S.E. A l and . a u t o m a t i c programming i n CAI. A r t i f i c i a l I n t e l l i g e n c e 6, 3, F a l l 1975, pp.215-234. Koffman, E.B. G e n e r a t i v e CAI: An a p p l i c a t i o n of A l to CAI. 1st USA-JAPAN Computer C o n f e r e n c e P r o c e e d i n g s , AFIPS, N.J., USA, 1972, pp. 28-35. Lecarme & Lewis (Eds.) Computers i n E d u c a t i o n . I F I P S , 1975. Manna Z. The c o r r e c t n e s s of programs. J . Computer Systems S c i e n c e . V o l . 3, No. 2, 1969, pp.119-127. Manna Z. P r o p e r t i e s of programs and the f i r s t o r d e r p r e d i c a t e c a l c u l u s . JACM, V o l . 16, No. 2, 1969, pp. 244-255. M a r g o l i n , Joseph B., & M i r s c h , M a r i a n R. (Eds.) Computers i n the c l a s s r o o m . M a c M i l l a n & Company, London, 1970. M a r t i n , James & Norman, A d r i a n R.D. 121 The c o m p u t e r i z e d s o c i e t y . Penguin Books, 1973. M i l l e r , M.L., & G o l d s t e i n , I.P. PAZATN: A l i n g u i s t i c approach to a u t o m a t i c a n a l y s i s of eleme n t a r y programming p r o t o c o l s . MIT AI Lab., Memo 388, December 1976. M i l l e r , M.L., & G o l d s t e i n , I.P. SPADE: A grammar based e d i t o r f o r p l a n n i n g and debugging programs. MIT AI Lab., Memo 385, December 1976. Mowshowitz, Abbe. The conquest of w i l l : I n f o r m a t i o n p r o c e s s i n g i n human a f f a i r s . Addison-Wesley, 1976. N e w e l l , A. & Simon, H. Human Problem S o l v i n g . Englewood C l i f f s , N.J: P r e n t i c e H a l l , 1972. P a p e r t , Seymour A. Teac h i n g c h i l d r e n to be ma t h e m a t i c i a n s v e r s u s t e a c h i n g about mathematics. MIT AI Lab., Memo 249, 1971. P e e l e , Howard A., & Riseman, Edward. Four f a c e s of HAL: A framework f o r u s i n g AI t e c h n i q u e s i n C o m p u t e r - A s s i s t e d I n s t r u c t i o n . IEEE T r a n s . on System, Man and C y b e r n e t i c s , May 1975. P e r r y , J.M., & K o f f m a n , E.B. Problem g e n e r a t i o n and s o l u t i o n . P r o c e e d i n g s of 1973 I n t e r n a t i o n a l C o n f e r e n c e on C y b e r n e t i c s and S o c i e t y . IEEE Systems, Man and C y b e r n e t i c s . P i a g e t , Jean. The s c i e n c e of e d u c a t i o n and the p s y c h o l o g y of the c h i l d . New Y o r k , V i k i n g P r e s s , 1972. P r e s s e y , S.L. A s i m p l e apparatus which g i v e s t e s t s and s c o r e s - and te a c h e s . School and S o c i e t y , 23, March 1926. P r e s s e y , S.L. Some p e r s p e c t i v e s and major problems r e g a r d i n g t e a c h i n g machines. I n : Lumsdaine & G l a s e r ( E d s . ) , T e a c h i n g machines and programmed l e a r n i n g , 1961. R i c h , C., & Schrobe, H.E. I n i t i a l r e p o r t on a LIS P programmer's a p p r e n t i c e . MIT AI Lab., TR-354, December 1976. R i c h , C , Schrobe, H.E., Waters, R.C., Sussman, G.J., H e w i t t , C.E. Programming viewed as an e n g i n e e r i n g a c t i v i t y . MIT AI Lab., Memo 459, January 1978. Rut h , G. 122 I n t e l l i g e n t program a n a l y s i s . A r t i f i c i a l I n t e l l i g e n c e , 7, S p r i n g 1976, pp. 65-85. S c o t t , A . C , C l a n c e y , W.J., D a v i s , R. , & S h o r t c l i f f e , E.H. E x p l a n a t i o n c a p a b i l i t i e s of p r o d u c t i o n - b a s e d c o n s u l t a t i o n systems. American J o u r n a l of C o m p u t a t i o n a l L i n g u i s t i c s , 62, 1977. S e l f , J.A. Student models i n CAI. I n t e r n a t i o n a l J . of Man-Machine s t u d i e s , 6, 1974. S e l f , J.A. Concept t e a c h i n g . A r t i f i c i a l I n t e l l i g e n c e ( N e t h e r l a n d s ) , 9 ( 2 ) , October 1977, pp. 197-221. S k i n n e r , B.F. . The s c i e n c e of t e a c h i n g and the a r t of l e a r n i n g . H a r v a r d Ed. Review, 1954. S k i n n e r , B.F. T e a c h i n g Machines. S c i e n c e , V o l . 128, 1958. and S c i e n t i f i c A merican, V o l . 205, 1961. S t e v e n s , A.L., & C o l l i n s , A. The Goal s t r u c t u r e of a S o c r a t i c t u t o r . BBN Report No. 3518, March 1977. S t o c k d a l e , M. Towards the d e s i g n of an i n t e l l i g e n t L I S P t u t o r . Computer S c i e n c e Department, UBC, 1977. Suppes, P., Smith, R., & Beard, M. U n i v e r s i t y l e v e l CAI at S t a n f o r d . I n s t r u c t i o n a l S c i e n c e , 6, 1977. Suppes, P., & G o l d b e r g , A. A computer a s s i s t e d i n s t r u c t i o n a l program f o r e x e r c i s e s on f i n d i n g Axioms. E d u c a t i o n a l s t u d i e s i n M a t h e m a t i c s , 4, 1972, pp. 429-499. West, T. D i a g n o s i n g p u p i l e r r o r s : L o o k i n g f o r p a t t e r n s . The A r i t h m e t i c T e a cher, Novemer 1971. W e s t c o u r t , K., B e a r d , M., & G o u l d , L. Knowledge based a d a p t i v e c u r r i c u l u m s equencing f o r CAI: A p p l i c a t i o n s of a network r e p r e s e n t a t i o n . P r o c . of 1977 Annual C o n f e r e n c e , ACM, October 1977, pp.234-240. W e x l e r , J.D. I n f o r m a t i o n networks i n g e n e r a t i v e CAI. IEEE T r a n s , on Man-Machine Systems, MMS-11, 1970. APPENDIX INTERNAL MODEL OF FUNCTION REPLACE T h i s appendix i l l u s t r a t e s the i n t e r n a l model f o r the f u n c t i o n REPLACE. P i e c e s of t h i s model have appeared throughout t h i s paper, but i t i s p r e s e n t e d h e r e , i n the appendix, i n i t s complete form. I t must be emphasized t h a t t h i s i s a r e p r e s e n t a t i o n of how the LISPCAI system w i l l s t o r e and r e f e r e n c e the model f o r f u n c t i o n REPLACE. The t e a c h e r ' s own model w i l l be f a r l e s s complex, but o b v i o u s l y e q u i v a l e n t . I t i s assumed t h a t t h e r e w i l l e x i s t some f r o n t - e n d p r o c e s s o r to c r e a t e such an i n t e r n a l model from a t e a c h e r ' s d e s c r i p t i o n . By prompting the t e a c h e r f o r a l l the r e l e v a n t i n f o r m a t i o n , and by u s i n g the g e n e r a l t e m p l a t e f o r i n t e r n a l models, ( d e s c r i b e d throughout t h i s p a p e r ) , the LISPCAI system s h o u l d be a b l e to y i e l d the f o l l o w i n g model o f o r f u n c t i o n REPLACE. ( N o t e : r e f e r to f i g u r e s 2 & 3 o i n c h a p t e r IV) 124 y Data-base E n t r i e s REPLACE SEGMENT LAMBDA-EXP REPLACE (DEFUN REPLACE (ATI AT2 L) (COND (CDR L ) ) ) ) ) ) REPLACE-15 SEGMENT FUNC-CALL REPLACE (REPLACE ATI AT2 (CDR L ) ) REPLACE-16 'SEGMENT FUNC-CALL REPLACE (REPLACE ATI AT2 (CDR L ) ) NULLTEST-13 SEGMENT OPEN-CODE NULLTEST (NULL L) EQTEST-14 SEGMENT OPEN-CODE EQTEST (EQ (CAR L) ATI) Except f o r the f i r s t , the above are a l l minor data-base e n t r i e s . NULLTEST and EQTEST have t h e i r major data-base e n t r i e s d e f i n e d elsewhere i n the model, or p r e - d e f i n e d by t h e s y s t e m . 125 S p e c i f i c a t i o n s SPECS : REPLACE (INPUTS ATI LAMBDA-ARG) (INPUTS AT2 LAMBDA-ARG) (INPUTS L LAMBDA-ARG) (PRECONDS (AND (ATOM ATI) (ATOM AT2) )) (CASE-1 (PRECONDS (NULL L ) ) (OUTPUTS L-2 5 RETURN-VAL) (POSTCONDS (NULL L-25) )) (CASE-2 (PRECONDS (AND (LISTP L) L) ) (OUTPUTS L-24 RETURN-VAL) (POSTCONDS (AND (NOT (MEMQ ATI L-24)) (EQ (LENGTH L) (LENGTH L - 2 4 ) ) ) ) ) 126 P l a n s PLANS : REPLACE Sub-segment l i s t (SUB-SEGS (CAR-10 CDR-11 CDR-12 NULLTEST-13 EQTEST-14 REPLACE-15 REPLACE-16 CONS-17 CONS-18 CONS-19 ) ) 127 Data F l o w PLANS : REPLACE CDATAFLOW (REPLACE INPUT ATI) (EQTEST-14 INPUT A T I ) ) (DATAFLOW (REPLACE INPUT ATI) (REPLACE-15 INPUT A T I ) ) (DATAFLOW (REPLACE INPUT ATI) (REPLACE-16 INPUT A T I ) ) (DATAFLOW (REPLACE INPUT AT2) (REPLACE-15 INPUT AT2)) (DATAFLOW (REPLACE INPUT AT2) (REPLACE-16 INPUT AT2)) (DATAFLOW (REPLACE INPUT AT2) (CONS-17 INPUT AT2)) (DATAFLOW (REPLACE INPUT L) (CAR-19 INPUT L ) ) (DATAFLOW (REPLACE INPUT L) (CAR-10 INPUT L ) ) (DATAFLOW (REPLACE INPUT L) (CDR-12 INPUT L ) ) (DATAFLOW (REPLACE INPUT L) (CDR-11 INPUT L ) ) 128 (DATAFLOW (REPLACE INPUT L) (NULLTEST-13 INPUT L ) ) (DATAFLOW (NULLTEST-13 OUTPUT L-25) (REPLACE OUTPUT L-25)) (DATAFLOW (CONS-17 OUTPUT L-24) (REPLACE OUTPUT L-24)) (DATAFLOW (CONS-18 OUTPUT L-24) (REPLACE OUTPUT L-24)) (DATAFLOW (CAR-10 OUTPUT L-19) (EQTEST-14 INPUT L-19) NESTED-SEXP) (DATAFLOW (CAR-19 OUTPUT L-2 6) (CONS-18 INPUT L-26) NESTED-SEXP) (DATAFLOW (CDR-11 OUTPUT L-2 0) (REPLACE-15 INPUT L-2 0) NESTED-SEXP) (DATAFLOW (CDR-12 OUTPUT L-2 2) (REPLACE-16 INPUT L-2 2) NESTED-SEXP) (DATAFLOW (REPLACE-15 OUTPUT L-21) (CONS-17 INPUT L-21) NESTED-SEXP) (DATAFLOW (REPLACE-16 OUTPUT L-23) (CONS-18 INPUT L-23) NESTED-SEXP) 130 C o n t r o l Flow PLANS : REPLACE (CONTROLFLOW (INVOKES NULLTEST-13) (DIRECTION-1 TRUE (RETURNS N I L ) ) (DIRECTION-2 NIL (INVOKES CAR-10) (NEXT EQTEST-14) (DIRECTION-3 TRUE (INVOKES CDR-11) (NEXT REPLACE-15 CONS-17) (RETURNS REPLACE)) (DIRECTION-4 NIL (INVOKES CAR-19) (NEXT CDR-12 REPLACE-16 CONS-18) (RETURNS REPLACE)) ..end d i r e c t i o n 4 ) ..end d i r e c t i on2 ) ..end c o n t r o l f l o w t 131 A n a l y s i s and c o r r e c t i o n s t r u c t u r e s DIAGNOSTICS : REPLACE (TEST REPLACE (WITH-INPUT '( (ATI.A) (AT2.B) ( L . ' ( A B C ) ) ) (TEST-OUTPUT '(AND (EQ *REPLACE ' ( B B C ) ) (EQ ATI B)) output O I L . ((PRINT 'NO NEED TO SUBSTITUTE IN THE ACTUAL PARAMETERS, BUT ONLY IN THE LIST\") (LOOK-FOR-XTRA 'SETQ) )) (TEST-OUTPUT '(EQ *REPLACE ' ( B B C ) ) output 012.. ((PRINT 'LOOKS GOOD AT FIRST GLANCE\") )) ) .. end i nput 11 (WITH-INPUT '( ( L . N I L ) ) (TEST-OUTPUT '(NOT (NULL L ) ) ((PRINT \"SHOULD NOT SUBSTITUTE INTO A NULL LIST) (EXPLAIN-SEG 'NULLTEST) )) ) .. end i nput 12 ) 132 Note t h a t o n l y the t o p - l e v e l segment ( i . e . REPLACE i t s e l f ) would have a DIAGNOSTIC model. L o w e r - l e v e l segments o n l y have CAVEATS. (The t o p - l e v e l segment has CAVEATS t o o ) . 133 CAVEATS : REPLACE f i r s t caveat ( (PATTERN @NOT@) (ACTION (PRINT \"YOUR TEST IS THE REVERSE OF THE MODEL, STILL ACCEPTABLE) (NEGATE-TRUTHVALUES DIRECTION-3 DIRECTION-4)) ) second caveat ( (PATTERN TRUE) (ACTION (PRINT \" TEST FOR AN EMPTY LIST BEFORE ANYTHING ELSE)) ) A l l the sub-segments w i t h d e f i n i t i o n s and e n t r i e s on the da t a - b a s e , e.g. NULLTEST and EQTEST, would a l s o have CAVEATS a s s o c i a t e d w i t h t h e i r model. We have o n l y p r o v i d e d the d e t a i l s of REPLACE's i n t e r n a l model. S i n c e REPLACE i s a t o p - l e v e l segment, i . e . a f u n c t i o n name, i t s model i s somewhat more complex than t h a t of an i n t e r n a l segment such as NULLTEST. The degree of c o m p l e x i t y of a model w i l l be determined by both i t s importance i n the g e n e r a l d e s i g n of the program, and by the e x t e n t of the 134 t e a c h e r - s u p p l i e d d i a g n o s i s i n f o r m a t i o n . "@en ; edm:hasType "Thesis/Dissertation"@en ; edm:isShownAt "10.14288/1.0051792"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Computer Science"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Design of an intelligent lisp cai tutor"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/21357"@en .