Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Explorations of programming learning behaviour of novices through computer-aided learning Looi, Chee-Kit 1984

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

Item Metadata

Download

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

Full Text

EXPLORATIONS OF PROGRAMMING LEARNING BEHAVIOUR pF NOVICES THROUGH COMPUTER-AIDED LEARNING by CHEE-KIT/^LOOI BSc, Nanyang U n i v e r s i t y , S i n g a p o r e , 1980 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 S c i e n c e We a c c e p t t h i s t h e s i s as c o n f o r m i n g t o the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA March 1984 © C h e e - k i t L o o i , 1984 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 the requirements f o r an advanced degree a t the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make 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 and study. I f u r t h e r agree 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 copying o f t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the head o f my department o r by h i s o r her r e p r e s e n t a t i v e s . I t i s understood t h a t copying or p u b l i c a t i o n of 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 not be allowed without my w r i t t e n p e r m i s s i o n . Department o f C o m p u t e r ScfefUe The U n i v e r s i t y o f B r i t i s h Columbia 1956 Main Ma l l Vancouver, Canada V6T 1Y3 Date Apniq,l<W i i A b s t r a c t The goal of Computer-Aided I n s t r u c t i o n (CAI) r e s e a r c h i s to b u i l d i n s t r u c t i o n a l programs that i n c o r p o r a t e w e l l - p r e p a r e d course m a t e r i a l i n l e s s o n s that attempt to i n d i v i d u a l i z e l e a r n i n g . The r o l e of A r t i f i c i a l I n t e l l i g e n c e (Al) i s to f a c i l i t a t e a new kind of l e a r n i n g environment that s t r e s s e s a l e a r n e r - b a s e d paradigm i n s t e a d of the teacher-based paradigm of t r a d i t i o n a l CAI. Research in I n t e l l i g e n t Computer-Aided Learning (ICAL) i s focused on p r o v i d i n g i n s t r u c t i o n that i s s e n s i t i v e to the student's s t r e n g t h s , weaknesses, and p r e f e r r e d s t y l e of l e a r n i n g . In t h i s t h e s i s , r e s e a r c h m i l e s t o n e s i n ICAL are d i s c u s s e d . An I n t e r a c t i v e Computer-aided T e s t i n g program that seeks to diagnose novices' misconceptions of the assignment statement in P a s c a l i s d e s c r i b e d . T h i s program was a l s o used to explore the u t i l i t y of p r o v i d i n g e x p l i c i t models as an a i d to l e a r n i n g programming. T a b l e of C o n t e n t s Chapter 1. I n t r o d u c t i o n 1 Chapter 2. A Survey of I n t e l l i g e n t Computer-Aided L e a r n i n g Systems 2.1 H i s t o r i c a l P e r s p e c t i v e 3 2.2 Towards ICAL 5 2.3 M i l e s t o n e s i n ICAL Research 9 2.3.1 I n t e r a c t i n g w i t h the Student i n a M i x e d - i n i t i a t i v e D i a l o g u e 10 2.3.2 T u t o r i n g by the S o c r a t i c method 12 2.3.3 E v a l u a t i n g Student H y p o t h e s i s f o r C o n s i s t e n c y w i t h Measurements taken 15 2.3.4 Enumerating Bugs i n C a u s a l Reasoning 17 2.3.5 I n t e r p r e t i n g Student Behaviour i n terms of E x p e r t Knowledge 19 2.3.6 C o d i f y i n g D i s c o u r s e P r o c e d u r e s f o r Teaching 23 2.3.7 C o n s t r u c t i n g I n c o r r e c t P l a n s or Pr o c e d u r e s 26 2.3.8 R e l a t i n g I n c o r r e c t P r o c e d u r e s t o a G e n e r a t i v e Theory 30 2.3.9 S e l f - I m p r o v i n g T e a c h i n g Systems 32 2.3.10 B u i l d i n g L e a r n i n g Environments 34 2.4 F u t u r e p r o s p e c t s • 37 2.5 The E v a l u a t i o n I s s u e 39 2.6 Summary 43 Chapter 3. Computer-Aided T e s t i n g , E v a l u a t i o n and A d v i c e (CATEA) 3.1 An Experiment i n W r i t i n g CAL System 44 3.2 N o v i c e s ' M i s c o n c e p t i o n s of the P a s c a l Assignment statement 3.2.1 Bayman and Mayer's work 45 3.2.2 The P a s c a l Assignment statement 47 Chapter 4. Design and Implementation of CATEA 4.1 O v e r a l l S t r u c t u r e 51 4.2 The P a s c a l Compiler 55 4.3 The D i a g n o s t i c Model 56 4.4 Implementation 60 Chapter 5. An E m p i r i c a l Study of CATEA 5.1 D e s c r i p t i o n of Study 61 5.2 R e s u l t s of Study 62 5.3 Q u e s t i o n n a i r e Survey 68 i v Chapter 6. C o n c l u s i o n 69 R e f e r e n c e s 72 Appendix A 7 7 Appendix B 7 8 Appendix C 80 V L i s t of T a b l e s 1. Performance of the f i r s t two groups of 39 s t u d e n t s 63 2. Breakdown of s t u d e n t s i n f i r s t two groups who program i n c o r r e c t l y 63 3. Performance of the t h i r d group of 9 s t u d e n t s 66 4. Student e v a l u a t i o n 68 v i L i s t of F i g u r e s 1. A Paradigm f o r T u t o r i n g 7 2. Components of an ICAL system 9 3. Three Problems t e s t e d by CATEA 52 4. S t r u c t u r e of CATEA 53 5. D i a g n o s t i c l o o p of CATEA 54 v i i Acknowledgement I would l i k e t o thank Dr. R i c h a r d Rosenberg f o r h i s i n v a l u a b l e guidance and p e r s p e c t i v e i n s u p e r v i s i n g my r e s e a r c h . Most of the m a t e r i a l i n Chapter 2 i s based on a paper w r i t t e n f o r CPSC 522 and I would l i k e t o thank Dr. A l a n Mackworth f o r h i s most h e l p f u l c r i t i c i s m s of t h a t paper and f o r r e a d i n g t h i s t h e s i s . 1 Chapter 1. I n t r o d u c t i o n The g o a l of Computer-Aided I n s t r u c t i o n (CAI) r e s e a r c h i s t o b u i l d i n s t r u c t i o n a l programs t h a t i n c o r p o r a t e w e l l - p r e p a r e d c o u r s e m a t e r i a l i n l e s s o n s t h a t attempt t o i n d i v i d u a l i z e l e a r n i n g . E a r l y programs were e i t h e r e l e c t r o n i c ' p a g e - t u r n e r s ' , which p r i n t e d p r e p a r e d t e x t , or d r i 1 1 - a n d - p r a c t i c e m o n i t o r s , which p r i n t e d problems and responded t o the s t u d e n t ' s s o l u t i o n s u s i n g p r e s t o r e d answers and r e m e d i a l comments. The 1970's saw the e v o l u t i o n of a new g e n e r a t i o n of CAI programs t h a t r e p r e s e n t e d c o u r s e m a t e r i a l i n d e p e n d e n t l y of t e a c h i n g p r o c e d u r e s , so t h a t problems and r e m e d i a l comments c o u l d be g e n e r a t e d d i f f e r e n t l y f o r each s t u d e n t . R esearch i n these I n t e l l i g e n t Computer-Aided L e a r n i n g (ICAL) programs i s f o c u s e d on p r o v i d i n g i n s t r u c t i o n t h a t i s s e n s i X t \ y e t o the s t u d e n t ' s s t r e n g t h s , weaknesses, and p r e f e r r e d s t y l e o f \ l e a r n i n g . The r o l e of A r t i f i c i a l I n t e l l i g e n c e ( A l ) i n ICAL i s t o \ make p o s s i b l e a new k i n d of l e a r n i n g environment t h a t s t r e s s e s a l e a r n e r - b a s e d paradigm i n s t e a d of the t e a c h e r - b a s e d paradigm of t r a d i t i o n a l CAI . An ICAL system g e n e r a l l y i n c o r p o r a t e s t h r e e models : a domain model, a t e a c h i n g model and a s t u d e n t model. Much r e s e a r c h work has been done on the s t u d e n t model which makes hypotheses about a s t u d e n t ' s m i s c o n c e p t i o n s and s u b o p t i m a l s t r a t e g i e s so t h a t the t e a c h i n g model can p o i n t them o u t , i n d i c a t e why they are wrong, and suggest c o r r e c t i o n s . In t h i s t h e s i s , we w i s h t o s p e c i f y a s m a l l domain of i n t e r e s t and w r i t e a CAL program t h a t seeks t o diagnose 2 m i s c o n c e p t i o n s i n a s t u d e n t ' s u n d e r s t a n d i n g of t h a t domain by a t t e m p t i n g some l i m i t e d use of AI t e c h n i q u e s . We c h o o s e as t h e knowledge domain t h e c o n c e p t of t h e a s s i g n m e n t s t a t e m e n t i n t h e P a s c a l programming l a n g u a g e . We b e g i n i n C h a p t e r 2 w i t h a b r o a d s u r v e y of t h e r e s e a r c h m i l e s t o n e s i n ICAL w h i c h w i l l p r o v i d e a b r o a d framework f o r t h e r e s t o f t h e t h e s i s . In C h a p t e r 3 , we d i s c u s s t h e m o t i v a t i o n s f o r w r i t i n g our i n s t r u c t i o n a l p r o g r a m w h i c h we c a l l C o m p u t e r - A i d e d T e s t i n g , E v a l u a t i o n and A d v i c e (CATEA). C e n t r a l t o t h e d i a g n o s i s m o d e l, we enumerate t h e p o s s i b l e m i s c o n c e p t i o n s n o v i c e s may have w i t h t h e a s s i g n m e n t s t a t e m e n t . In C h a p t e r 4 , we d i s c u s s t h e d e s i g n and i m p l e m e n t a t i o n o f CATEA. In C h a p t e r 5 , we d e s c r i b e t h e r e s u l t s o f an e m p i r i c a l s t u d y of CATEA c o n d u c t e d on s t u d e n t s o f an i n t r o d u c t o r y P a s c a l c o u r s e . In C h a p t e r 6 , we summarise what we have l e a r n e d from t h e whole e x p e r i m e n t o f d e v e l o p i n g CATEA. 3 Chapter 2. A Survey of ICAL Systems 2.1 H i s t o r i c a l P e r s p e c t i v e In the 1960s the d i g i t a l computer was e n v i s a g e d t o p l a y a key r o l e i n e d u c a t i o n t h rough the development and w i d e s p r e a d use of programs t h a t would ' t e a c h ' t o p i c s drawn from a wide v a r i e t y of d i s c i p l i n e s . R e i n f o r c e d by e a r l i e r work on programmed l e a r n i n g (by P r e s s e y , S k i n n e r , and Crowder amongst o t h e r s ) , the view t h a t c h i l d r e n ' l e a r n by b e i n g t o l d ' was much more p r e v a l e n t a t t h a t time than i t i s today. Subsequent i m p l e m e n t a t i o n of c o m p u t a t i o n a l t e a c h i n g programs, i n the p e r s u a s i v e a d v e r t i s i n g j a r g o n of e d u c a t i o n , c l a i m e d t o i n d i v i d u a l i z e t e a c h i n g , and so f a c i l i t a t e l e a r n i n g . A p r o f u s i o n of acronyms r e s u l t e d i n r e l a t i o n t o the use of computers i n e d u c a t i o n - CAI, CAL, CBE, r CBL, CMI, C F I , CML (where C=Computer, A=Aided or A s s i s t e d , B=Based, M=Managed, I = I n s t r u c t i o n , L = L e a r n i n g , E=Education and F = F u r t h e r e d ) . D u r i n g the mid-60's, a number of g e n e r a t i v e CAI systems (Suppes, 1971; Woods & H a r t l e y , 1971; Uhr, 1969) were d e v i s e d t o p r o v i d e d r i l l and p r a c t i c e i n a r i t h m e t i c and i n v o c a b u l a r y r e c a l l , and t o s e l e c t problems a t a l e v e l of d i f f i c u l t y dependent upon and a d j u s t e d t o the s t u d e n t ' s o v e r a l l p erformance. These systems use an a l g o r i t h m t o g e n e r a t e t e a c h i n g m a t e r i a l as opposed t o those programs where each p i e c e of t e a c h i n g m a t e r i a l i s p r e - s t o r e d . These systems a r e a l s o c a l l e d a d a p t i v e and t h e i r s o p h i s t i c a t i o n l a y i n the t a s k -s e l e c t i o n a l g o r i t h m s . In these systems, models of the s t u d e n t s a r e based more on p a r a m e t r i c summaries of b e h a v i o u r than 4 e x p l i c i t r e p r e s e n t a t i o n s of t h e i r knowledge. By the end of the decade, a group of A l r e s e a r c h workers g r a d u a l l y emerged who shared a v e r y d i f f e r e n t b e l i e f about the l e a r n i n g and t h i n k i n g p r o c e s s e s . The u n d e r l y i n g assumption i n t h e i r work i s t h a t complex c o g n i t i v e a c t i v i t i e s l i k e s e e i n g , l e a r n i n g , t h i n k i n g and u s i n g language a r e knowledge-based. One of t h e i r c h i e f c o n cerns i s how best t o r e p r e s e n t them i n the computer. The r e l e v a n c e t o e d u c a t i o n i s the b e l i e f t h a t a l e a r n e r , w o r k i n g i n a p a r t i c u l a r domain, has t o b u i l d the domain s p e c i f i c knowledge i n t o an a c t i v e mental d a t a b a s e , a c t i v e i n the sense t h a t the knowledge r e p r e s e n t a t i o n can be a s s e s s e d and used as the b a s i s f o r new l e a r n i n g . T h i s p r o c e s s of c o n s t r u c t i n g such a mental r e p r e s e n t a t i o n i m p l i e s c r e a t i v e mental b e h a v i o u r on the p a r t of the l e a r n e r . In t h i s c o n t e x t of ' l e a r n i n g by d o i n g ' , the r o l e of the t e a c h e r i s t o s t r u c t u r e a domain i n such a way t h a t i t f a c i l i t a t e s the m o d e l - b u i l d i n g a c t i v i t y . U n d e r l y i n g t h i s s h i f t t o a new paradigm i n CAI i s the b e l i e f t h a t t r u l y i n d i v i d u a l i z e d t e a c h i n g systems c o u l d not be b u i l t u n t i l deep c o n c e p t u a l problems , about such m a t t e r s as knowledge r e p r e s e n t a t i o n , s t u d e n t m o d e l l i n g and language u n d e r s t a n d i n g , were b e t t e r u n d e r s t o o d . The domain of CAL i s i n t e r p r e t e d b r o a d l y ( Z i n n , 1978) t o i n c l u d e l e a r n i n g about computers, w i t h computers, t h r o u g h computers, and computer-managed l e a r n i n g . In t h i s t h e s i s , the terms I n t e l l i g e n t Computer-aided L e a r n i n g ( I C A L ) , ICAI and I n t e l l i g e n t T u t o r i n g Systems (ITS) w i l l be t aken t o be synonymous, and t o i n c l u d e : ( 1 ) l e a r n i n g through the computer (coaches, l a b o r a t o r y 5 i n s t r u c t o r s , c o n s u l t a n t s ) (a) d r i l l and p r a c t i c e (b) t u t o r i a l (c) d i a g n o s t i c t e s t i n g ; (2) l e a r n i n g w i t h the computer ( p r o b l e m - s o l v i n g m o n i t o r s ) (a) s i m u l a t i o n and gaming (b) p r o b l e m - s o l v i n g (c) c r e a t i v e a c t i v i t i e s . 2.2 Towards I n t e l l i g e n t Computer-aided L e a r n i n g An ICAL system s h o u l d i n some sense model an i n t e l l i g e n t t e a c h e r , but we have o n l y e l e m e n t a r y n o t i o n s why some human t e a c h e r s a re good a t t e a c h i n g w h i l e o t h e r s a r e n o t . As an a l t e r n a t i v e s t r a t e g y , we w i l l s e l e c t the most o b v i o u s d e f i c i e n c i e s of the t r a d i t i o n a l CAL approach, and l o o k a t AI work which p r o v i d e s some i n s i g h t i n t o the u n d e r l y i n g d i f f i c u l t i e s . The 4 main l i m i t a t i o n s a r e : (1) i n a b i l i t y t o know or u n d e r s t a n d the s u b j e c t b e i n g t a u g h t , i n the sense t h a t the system cannot a c c e p t u n a n t i c i p a t e d answers or answer q u e s t i o n s ; (2) i n a b i l i t y t o conduct d i a l o g u e s w i t h the s t u d e n t i n n a t u r a l language; (3) i n a b i l i t y t o un d e r s t a n d the n a t u r e of the s t u d e n t ' s m i s t a k e s or m i s c o n c e p t i o n s ; (4) i n a b i l i t y t o p r o f i t from e x p e r i e n c e w i t h s t u d e n t s or t o experiment w i t h the t e a c h i n g s t r a t e g y (O'Shea, 1979). In c o n t r a s t , t o t u t o r w e l l , The [ICAL] system must have i t s own problem-6 s o l v i n g e x p e r t i s e , i t s own d i a g n o s t i c or s t u d e n t m o d e l l i n g c a p a b i l i t i e s and i t s own e x p l a n a t o r y c a b a b i l i t i e s . In o r d e r t o o r c h e s t r a t e these r e a s o n i n g c a p a b i l i t i e s , i t must a l s o have e x p l i c i t c o n t r o l or t u t o r i a l s t r a t e g i e s s p e c i f y i n g when t o i n t e r r u p t a s t u d e n t ' s p r o b l e m - s o l v i n g a c t i v i t y , what to say and how best t o say i t ; a l l i n o r d e r t o p r o v i d e the s t u d e n t w i t h i n s t r u c t i o n a l l y e f f e c t i v e a d v i c e (Brown & Sleeman, p. 2, 1981). ICAL programs use A l f o r m a l i s m s t o s e p a r a t e out what they i n t e n d t o t e a c h from t h e i r t e a c h i n g s t r a t e g y . T h i s approach has s e v e r a l v i r t u e s : i t becomes p o s s i b l e t o keep r e c o r d s of what the s t u d e n t know, the t e a c h i n g s t r a t e g y can be g e n e r a l i z e d and a p p l i e d t o m u l t i p l e problems i n m u l t i p l e problem-domains, and a model of s t u d e n t knowledge can be i n f e r r e d from s t u d e n t responses and used as a b a s i s f o r t u t o r i n g ( C l a n c e y & Buchanan, 1982) . As a g e n e r a l paradigm f o r the f i e l d , a t u t o r i n g system ( F i g u r e 1) s h o u l d i n c o r p o r a t e the f o l l o w i n g 3 models : (1) a domain model c o n t a i n i n g the knowledge or e x p e r t i s e we want t o t e a c h (what i s b e i n g t a u g h t ? ) (2) a t e a c h i n g model c o n t a i n i n g the t u t o r i n g t h e o r y and s t r a t e g y t o improve the s t u d e n t ' s performance (how s h a l l we t e a c h ? ) (3) a s t u d e n t model c o n t a i n i n g the knowledge t h a t the system e x p e c t s the s t u d e n t t o have a c q u i r e d (how much does the s t u d e n t know?). W i t h i n the t u t o r i n g system, a t e a c h i n g model a c c e s s e s the s t u d e n t model t o f i n d . o u t what the s t u d e n t knows and the domain model f o r what remains t o be l e a r n e d . The system then d e c i d e s what t a s k t o p r e s e n t t o the s t u d e n t . Once a t a s k i s g e n e r a t e d , the s t u d e n t draws upon h i s c u r r e n t knowledge t o do the t a s k , and 7 p r e s e n t s t h i s d e c i s i o n t o the t u t o r i n g system. From the s t u d e n t response, the system updates i t s s t u d e n t model and i n i t i a t e s a new d e c i s i o n c y c l e . T u t o r i n g System Domain Model / T e a c h i n g Model \ Student Model Student $ Knowledge D e c i s i o n s F i g u r e 1. A Paradigm f o r T u t o r i n g ( O s i n , 1980) Not a l l of the t h r e e models a r e f u l l y d e v e l o p e d i n every ICAL system. Because of the s i z e and c o m p l e x i t y of ICAL systems, most r e s e a r c h e r s t e n d t o c o n c e n t r a t e t h e i r e f f o r t s on the development of a s i n g l e p a r t of what would c o n t r i b u t e t o a f u l l y u s a b l e system ( B a r r & Feigenbaum, 1982). The g r e a t e s t weakness of c u r r e n t ICAL systems i s p o s s i b l y t h e i r e l e m e n t a r y t e a c h i n g models. C l a n c e y & Buchanan (1982, p. 4) note t h a t Almost i n v a r i a b l y , most r e s e a r c h e r s have backed o f f from i n i t i a l l y f o c u s i n g on the [second] q u e s t i o n - "How s h a l l we t e a c h ? " - t o r e c o n s i d e r the [ l a s t ] q u e s t i o n , b u i l d i n g a model of the s t u d e n t ' s knowledge. T h i s f o l l o w s from the assumption t h a t the s t u d e n t e r r o r s are not random, but r e f l e c t m i s c o n c e p t i o n s about the p r o c e d u r e t o be f o l l o w e d or 8 f a c t s i n the problem domain, and the best t e a c h i n g s t r a t e g y i s to d i r e c t l y a d d r e s s the s t u d e n t ' s mi sconeept i o n s . To a s s i s t r e s e a r c h i n b u i l d i n g models of m i s c o n c e p t i o n s , we need a sounder u n d e r s t a n d i n g of the n a t u r e of knowledge and e x p e r t i s e . Comparison s t u d i e s of e x p e r t s and n o v i c e s a r e r e v e a l i n g how the e x p e r t s t r u c t u r e s a problem; the v e r y c o n c e p t s he uses f o r t h i n k i n g about a problem, d i s t i n g u i s h h i s r e a s o n i n g from the s t u d e n t ' s o f t e n f o r m a l bottom-up approach. These s t u d i e s suggest t h a t we might convey t o the s t u d e n t the k i n d s of q u i c k a s s o c i a t i o n s , p a t t e r n s and r e a s o n i n g s t r a t e g i e s t h a t e x p e r t s b u i l d up t e d i o u s l y over l o n g exposure t o many k i n d s of problems - the k i n d of knowledge t h a t tends not t o be w r i t t e n down i n b a s i c t e x t b o o k s ( C l a n c e y & Buchanan, 1982). F o l l o w i n g t h i s premise t h a t we can be b e t t e r t e a c h e r s by b e t t e r u n d e r s t a n d i n g e x p e r t i s e , e x p e r t systems r e s e a r c h becomes of keen i n t e r e s t i n e d u c a t i o n . These knowledge-based programs c o n t a i n w i t h i n them a l a r g e amount of f a c t s and i n f e r e n c e r u l e s f o r s o l v i n g problems i n r e s t r i c t e d domains of m e d i c i n e , s c i e n c e and e n g i n e e r i n g . They have s p e c i a l i n t e r e s t t o C o g n i t i v e S c i e n c e r e s e a r c h as s i m u l a t i o n models t h a t can be used as a " l a b o r a t o r y workbench" f o r e x p e r i m e n t i n g w i t h knowledge s t r u c t u r e s and c o n t r o l s t r a t e g i e s . Another n a t u r a l a p p l i c a t i o n f o r e x p e r t systems i n e d u c a t i o n i s t o use them as the knowledge f o u n d a t i o n f o r an ICAL system ( F i g u r e 2 ) . The t e a c h i n g knowledge i s an e s s e n t i a l component as an e x p e r t system i n a p a r t i c u l a r domain i s not n e c e s s a r i l y an e x p e r t t e a c h e r of the m a t e r i a l ( B a r r & Feigenbaum, 1982). 9 I n t e l l i g e n t CAL System E x p e r t System Domain Knowledge Base I n t e r p r e t e r T e a c h i n g Knowledge F i g u r e 2 Components of an ICAL system ( C l a n c e y , 1981) 2.3 M i l e s t o n e s i n ICAL Research The well-known m i l e s t o n e s i n ICAL r e s e a r c h i n c l u d e 1 : (1) i n t e r a c t i n g w i t h the s t u d e n t i n a m i x e d - i n i t i a t i v e d i a l o g u e ( C a r b o n e l l , 1970) (2) t u t o r i n g by the S o c r a t i c method ( C o l l i n s , 1976) (3) e v a l u a t i n g h y p o t h e s i s f o r c o n s i s t e n c y w i t h measurements taken (Brown et a l , 1975) (4) enumerating bugs i n c a u s a l r e a s o n i n g ( S t e v e n s , 1978) (5) i n t e r p r e t i n g s t u d e n t b e h a v i o u r i n terms of e x p e r t knowledge ( B u r t o n , 1979; C a r r & G o l d s t e i n , 1977; C l a n c e y , 1979a) (6) c o d i f y i n g d i s c o u r s e p r o c e d u r e s f o r t e a c h i n g ( C l a n c e y , 1979b) (7) c o n s t r u c t i n g i n c o r r e c t p l a n s >or p r o c e d u r e s (Genesereth 1981; Brown, 1975) (8) r e l a t i n g i n c o r r e c t p r o c e d u r e s t o a g e n e r a t i v e t h e o r y (Brown, 1980) 1The l i s t of m i l e s t o n e s from 1 t o 8 was taken from C l a n c e y & Buchanan, 1982. In a t t e m p t i n g a comprehensive s u r v e y , I have added 9 and 10. 1 0 (9) b u i l d i n g s e l f - i m p r o v i n g t e a c h i n g systems (O'Shea, 1979) (10) b u i l d i n g l e a r n i n g environments ( F e u r z e i g & P a p e r t , 1969). M i l e s t o n e s 1,2,3,6,9 and 10 a d d r e s s the t e a c h i n g model, w h i l e 4,5,7 and 8 make c o n t r i b u t i o n s t o s t u d e n t m o d e l l i n g . We s h a l l now p r o c e e d t o d e l v e i n t o each m i l e s t o n e and d e s c r i b e i t s c o n t r i b u t i o n s t o ICAL r e s e a r c h as w e l l as some of i t s l i m i t a t i o n s . One broad theme emerges from t h e s e m i l e s t o n e s : the i n c o r p o r a t i o n of c o g n i t i v e models of l e a r n i n g or/and t e a c h i n g . T h i s means t h a t i n the near f u t u r e a l l CAL courseware w i l l be c o g n i t i v e l y - b a s e d , c a p a b l e of d i a g n o s i s and r e m e d i a t i o n a t the c o g n i t i v e l e v e l . 2.3.1 I n t e r a c t i n g w i t h the Student i n a M i x e d - I n i t i a t i v e  D i a l o g u e The CAI e f f o r t s of the 1960's can be c l a s s i f i e d i n t o 3 broad c a t e g o r i e s (Bryan, 1969). In the f i r s t , a d - l i b CAI, the s t u d e n t i s g i v e n a c c e s s t o the computer ( i n c l u d i n g one or more languages and perhaps a l i b r a r y of r o u t i n e s ) , but he i s i n f u l l c o n t r o l and h i s i n p u t i s not c o n t r o l l e d by the computer. A t y p i c a l example i s Seymour P a p e r t ' s LOGO L a b o r a t o r y ( P a p e r t , 1980; A b e l s o n & d i S e s s a , 1981). The second c a t e g o r y i s games and s i m u l a t i o n where the s t u d e n t has some i n i t i a t i v e but i s c o n s t r a i n e d by the r u l e s of the game or the l o g i c of the s i m u l a t i o n . In the f i r s t two c a t e g o r i e s , l e a r n i n g t a k e s p l a c e as an e x p e c t e d s i d e e f f e c t . The t h i r d c a t e g o r y makes an e x p l i c i t attempt t o i n s t i g a t e and c o n t r o l l e a r n i n g . D r i l l - a n d - p r a c t i c e and, i n g e n e r a l , c l a s s i c e f f o r t s t o use the computer as a t u t o r 11 a r e i n c l u d e d h e r e . These e f f o r t s i n v o l v e the c o n s t r u c t i o n of frames of q u e s t i o n s w i t h a n t i c i p a t e d c o r r e c t and wrong answers and perhaps keywords t o be e x t r a c t e d from the s t u d e n t ' s answer. As t h e i r sequencing i s d e t e r m i n i s t i c , C a r b o n e l l (1969) c a l l e d them 'ad-hoc f r a m e - o r i e n t e d ' CAI systems and obser v e d t h a t [In t hese s y s t e m s ] , the s t u d e n t has l i m i t e d or no i n i t i a t i v e ; he cannot use n a t u r a l language i n h i s re s p o n s e s , and systems u s u a l l y l o o k f a i r l y r i g i d t o him... From a systems v i e w p o i n t , the system c o n t r o l s the s t u d e n t but i s i n t u r n t i g h t l y ad-hoc programmed by the t e a c h e r ; the system has no r e a l i n i t i a t i v e or d e c i s i o n power of i t s own; and, of c o u r s e , i t has no r e a l 'knowledge'. C a r b o n e l l (1970) had these l i m i t a t i o n s i n mind when he' wrote a d i a l o g u e program, c a l l e d SCHOLAR (the e a r l i e s t of ICAI s y s t e m s ) , t o t e a c h f a c t s about the geography of South America. I t i s a " n o n - d e t e r m i n i s t i c " CAI program where d e c i s i o n s a re p r o b a b i l i s t i c among d y n a m i c a l l y d e t e r m i n e d a l t e r n a t i v e s , w i t h w e i g h t s t h a t a r e d y n a m i c a l l y a s s o c i a t e d . I n s t e a d of s t o r i n g g e o g r a p h i c i n f o r m a t i o n i n the form of p r e w r i t t e n frames , the program was o r g a n i z e d around an a s s o c i a t i v e database (semantic network) of s i m p l e g e o g r a p h i c f a c t s about i n d u s t r i e s , p o p u l a t i o n s and c a p i t a l s . I t . was d e s i g n e d t o m a n i p u l a t e i t s database to g e n e r a t e f a c t u a l q u e s t i o n s , t o check u n a n t i c i p a t e d answers t o these q u e s t i o n s , and a l s o t o answer the s t u d e n t ' s q u e s t i o n s . S i n c e c o n t r o l of the way i n which the c o n v e r s a t i o n c o u l d d e v e l o p i s shared between s t u d e n t and system, C a r b o n e l l c o i n e d the term ' m i x e d - i n i t i a t i v e ' t o d e s c r i b e t h i s k i n d of i n t e r a c t i o n . The semantic network i s a c o l l e c t i o n of named nodes, c a l l e d c o n c e p t s , w i t h p a i r s of these nodes l i n k e d by r e l a t i o n s . In the da t a b a s e , a f a c t i s r e p r e s e n t e d as a p a t t e r n of l i n k e d c o n c e p t s , 1 2 the p a t t e r n r e s e m b l i n g a t r e e or network. A q u e s t i o n , i n e f f e c t , i s an i n c o m p l e t e p a t t e r n , and the t a s k of the program's r e t r i e v a l p r o c e d u r e s i s t o s e a r c h i n the database f o r a p a t t e r n which matches the q u e s t i o n p a t t e r n , and t o s u p p l y i n i t s answer any a d d i t i o n a l r e l e v a n t i n f o r m a t i o n about the t o p i c which i s s t o r e d i n the d a t a b a s e . T h i s method works r e a s o n a b l y w e l l p r o v i d e d t h a t the i n f o r m a t i o n r e q u i r e d i s e x p l i c i t l y r e p r e s e n t e d i n the d a t a b a s e . However, a g r e a t d e a l of i n f o r m a t i o n i s encoded i m p l i c i t l y , and t h i s can o n l y be r e t r i e v e d by a d d i n g ad hoc i n f e r e n c e r u l e s t o the d a t a b a s e , and by a p p l y i n g t h e s e r u l e s d u r i n g r e t r i e v a l . For example, the database might c o n t a i n the r u l e 'To f i n d the p r o d u c t s of a p l a c e f i n d the p r o d u c t s of the i n d u s t r y a t a p l a c e . ' An o b v i o u s d i f f i c u l t y i s t h a t as the amount of knowledge i n the network i n c r e a s e s , ~ t h e r e w i l l be a r a p i d l y expanding number of f a l s e p a t h s a s s o c i a t e d w i t h nodes l i k e i n d u s t r y or p l a c e , c r e a t i n g a s i g n i f i c a n t s e a r c h problem. 2.3.2 T u t o r i n g by the S o c r a t i c method T h i s m i l e s t o n e c o n s i d e r s c o n v e r s a t i o n s between a t u t o r and a s t u d e n t as an i m p o r t a n t method of t e a c h i n g . C o l l i n s (1976) proposes t h a t the best way t o t e a c h knowledge and the s k i l l s n e c e s s a r y f o r a p p l y i n g t h a t knowledge t o new problems or s i t u a t i o n s , i s t h r o u g h the S o c r a t i c method of t e a c h i n g . The s t u d e n t of a S o c r a t i c d i a l o g u e i s f o r c e d to reason f o r h i m s e l f , d e r i v e g e n e r a l p r i n c i p l e s from s p e c i f i c c a s e s and a p p l y the g e n e r a l p r i n c i p l e s t h a t he have l e a r n e d t o new c a s e s . More s p e c i f i c a l l y , he l e a r n s 3 k i n d s of knowledge : 13 (1) s p e c i f i c i n f o r m a t i o n about a v a r i e t y of c a s e s ; (2) the c a u s a l dependencies or p r i n c i p l e s t h a t u n d e r l i e t h e s e c a s e s ; (3) r e a s o n i n g s k i l l s l i k e f o r m i n g h y p o t h e s e s , t e s t i n g h y p o t h e s e s , d i s t i n g u i s h i n g between n e c e s s a r y and s u f f i c i e n t c o n d i t i o n s , and a s k i n g the r i g h t q u e s t i o n s when t h e r e i s not enough i n f o r m a t i o n t o make a p r e d i c t i o n . C o l l i n s s p e c i f i e s and f o r m u l a t e s the S o c r a t i c method as a se t of s t r a t e g i e s or r u l e s . An ICAL system can i n c o r p o r a t e as many of t h e s e s t r a t e g i e s as p o s s i b l e i n t u t o r i n g c a s u a l knowledge and r e a s o n i n g . The S o c r a t i c method has not been p r e v i o u s l y c o n s i d e r e d f e a s i b l e f o r e d u c a t i o n g e n e r a l l y because i t i s a one-to-one t e a c h i n g s t r a t e g y . D e v e l o p i n g t e c h n o l o g i e s l i k e d i s t r i b u t e d i n s t r u c t i o n a l systems make i t p o s s i b l e t o t e a c h many more s t u d e n t s w i t h such a t u t o r i n g s t r a t e g y . C o l l i n s examines a v a r i e t y of S o c r a t i c d i a l o g u e s e m p i r i c a l l y t o uncover those f e a t u r e s t h a t c h a r a c t e r i z e the t u t o r ' s b e h a v i o u r . He f o r m a l i z e s the t u t o r i n g s t r a t e g y as p r o d u c t i o n r u l e s of the form " I f i n s i t u a t i o n X, do Y." The r u l e s a r e t h i s w r i t t e n , i n " a p r o c e d u r a l f o r m a l i s m t h a t i s independent of the p a r t i c u l a r c o n t e x t . 23 r u l e s a r e d e r i v e d , the f i r s t two r u l e s of which a r e l i s t e d below w i t h an example i n t u t o r i n g c a u s a l f a c t o r s a f f e c t i n g r i c e growing : Rule 1 : Ask about a known c a s e . I f TT) i t i s the s t a r t of a d i a l o g u e then (2) p i c k a well-known case and ask what the v a l u e of the dependent v a r i a b l e ( the v a r i a b l e t h a t depends on c a u s a l f a c t o r s ) i s f o r t h a t c a s e . Example : Ask the s t u d e n t "Do they grow r i c e i n China ?" Reason f o r use of r u l e : I t b r i n g s out any w e l l -1 4 known f a c t s the s t u d e n t knows about such as r i c e growing i n C h i n a . R u l e 2 : Ask f o r any f a c t o r s . I f TT) a s t u d e n t a s s e r t s t h a t a case has a p a r t i c u l a r v a l u e f o r the dependent v a r i a b l e , then (2) ask the s t u d e n t why. Example : i f the s t u d e n t says they grow r i c e i n C h i n a , ask why. Reason f o r use : T h i s d e t e r m i n e s what c a u s a l f a c t o r s or c h a i n s the s t u d e n t knows about.. A second-order t h e o r y of t e a c h i n g s t r a t e g y i s needed t o choose what r u l e s a r e most a p p r o p r i a t e t o invoke i n d i f f e r e n t s i t u a t i o n s . T h i s m i l e s t o n e proposes a p s y c h o l o g i c a l t h e o r y t h a t w i l l a ccount f o r b e h a v i o u r i n d i a l o g u e s i t u a t i o n s and a s e t of r u l e s f o r c o n s t r u c t i n g e f f e c t i v e i n s t r u c t i o n a l programs. For the r u l e s t o be adequate as a d e s c r i p t i v e t h e o r y , i t must be a b l e t o s u c c e s s f u l l y account f o r new d i a l o g u e p r o t o c o l s ( R e s n i c k , 1976). In C o l l i n s ' work, t h e r e i s no s p e c i f i c a t i o n of how many or what k i n d s of d i a l o g u e p r o t o c o l s a r e a c c o u n t e d f o r . Many more p r o t o c o l s w i l l have t o be a n a l y z e d b e f o r e the g e n e r a l i t y of C o l l i n s ' r u l e s can be e s t i m a t e d . For the r u l e s t o be adequate as a p r e s c r i p t i v e t h e o r y , i t s h o u l d produce d i a l o g u e s t h a t look l i k e the r e a l ones and t h a t d i d promote some k i n d of l e a r n i n g . R e s n i c k suggested t h a t the c o n d i t i o n p a r t of the r u l e s s h o u l d a l s o i n c l u d e , b e s i d e s immediate s t u d e n t r e s p o n s e s , a t l e a s t a b r i e f h i s t o r y of the s t u d e n t ' s responses and the t u t o r ' s i n t e n t i o n s d u r i n g the d i a l o g u e i t s e l f . More e m p i r i c a l s t u d i e s a r e needed t o judge whether the d i a l o g u e s do a c t u a l l y t e a c h . The t a s k of e v e n t u a l l y b u i l d i n g an automated d i a l o g u e e x p e r t f o r t u t o r i n g i s enormous and may not be r e a l i z e d f o r a 1 5 l o n g t i m e . However, the attempt i t s e l f , f o r c i n g a t t e n t i o n as i t does t o the d e t a i l s of n a t u r a l d i a l o g u e s , w i l l h e l p y i e l d g r e a t e r u n d e r s t a n d i n g of the t u t o r i n g p r o c e s s between human a c t o r s . 2.3.3 E v a l u a t i n g Student H y p o t h e s i s f o r C o n s i s t e n c y w i t h  Measurements taken An i n t e l l i g e n t i n s t r u c t i o n a l system which r e f l e c t s a major attempt to e x t e n d C a r b o n e l l ' s n o t i o n of m i x e d - i n i t i a t i v e CAL f o r the purpose of e n c o u r a g i n g a w i d e r range of s t u d e n t i n i t i a t i v e s i s SOPHIE (Brown et a l , 1976). U n l i k e p r e v i o u s systems which mimic the r o l e s of a human t e a c h e r , SOPHIE t r i e s t o t o c r e a t e a ' r e a c t i v e ' environment i n which the s t u d e n t l e a r n s by t r y i n g out h i s i d e a s r a t h e r than by i n s t r u c t i o n . SOPHIE a c t s as an e l e c t r o n i c s l a b o r a t o r y i n s t r u c t o r who h e l p s the s t u d e n t t r a n s f o r m h i s c l a s s r o o m knowledge of e l e c t r o n i c s i n t o an e x p e r i e n t i a l , i n t u i t i v e knowledge of i t s meaning and a p p l i c a t i o n . I t o p e r a t e s by p r e s e n t i n g the s t u d e n t w i t h a c i r c u i t schemata of an e l e c t r o n i c a p p a r a t u s , i n t o which i t has p r e v i o u s l y i n t r o d u c e d a f a u l t of some s p e c i f i e d degree of d i f f i c u l t y . The s t u d e n t ' s t a s k i s t o t r a c e t h i s f a u l t . He can p e r f o r m any sequence of measurements, ask s p e c i f i c q u e s t i o n s about the i m p l i c a t i o n s of these measurements , and even ask f o r a d v i c e about what t o c o n s i d e r n e x t , g i v e n what he has d i s c o v e r e d so f a r . At any t i m e , SOPHIE may encourage the s t u d e n t t o make a guess as t o what he t h i n k s might be wrong g i v e n the measurements he has made so f a r . I f he does, SOPHIE w i l l e v a l u a t e h i s h y p o t h e s i s . I f the i n f o r m a t i o n the s t u d e n t s h o u l d have been a b l e 16 t o d e r i v e from h i s c u r r e n t s e t of measurements i s l o g i c a l l y c o n t r a d i c t e d by h i s h y p o t h e s i s , SOPHIE i d e n t i f i e s and e x p l a i n s t h e s e c o n t r a d i c t i o n s . SOPHIE can a l s o judge the m e r i t s of any p a r t i c u l a r measurement w i t h r e s p e c t t o the p r i o r sequence of measurements he has made. For example, h i s new measurement may be l o g i c a l l y redundant i n t h a t no new i n f o r m a t i o n can be d e r i v e d from i t . SOPHIE'S e x p e r t i s e i s d e r i v e d from an e f f i c i e n t and p o w e r f u l i n f e r e n c i n g scheme t h a t uses m u l t i p l e r e p r e s e n t a t i o n s of knowledge i n c l u d i n g (1) s i m u l a t i o n models of i t s microcosm (2) p r o c e d u r a l s p e c i a l i s t s (of which the h y p o t h e s i s e v a l u a t i o n s p e c i a l i s t i s one) which c o n t a i n l o g i c a l s k i l l s and h e u r i s t i c s t r a t e g i e s f o r u s i n g t h o s e models (3) semantic n e t s f o r encoding t i m e - i n v a r i a n t f a c t u a l knowledge (Brown & B u r t o n , 1979). The power and g e n e r a l i t y of SOPHIE r e s u l t from the s y n e r g i s m o b t a i n e d by f o c u s i n g the d i v e r s e c a p a b i l i t i e s of the p r o c e d u r a l s p e c i a l i s t s on the i n t e l l i g e n t m a n i p u l a t i o n , e x e c u t i o n and i n t e r p r e t a t i o n of i t s s i m u l a t i o n models. SOPHIE i s a v e r y l a r g e program, but the r e s e a r c h e r s c l a i m t h a t the average response time t o a q u e s t i o n i s 3 seconds. W h i l e t h i s i s a s a t i s f a c t o r y measure of the program's e f f i c i e n c y , we l a c k e v i d e n c e about i t s e d u c a t i o n a l v a l u e . One b u i l t - i n a ssumption i s t h a t the s t u d e n t must have some knowledge of the b a s i c e l e c t r o n i c p r i n c i p l e s u n d e r l y i n g the d e s i g n and o p e r a t i o n of DC power s u p p l i e s . The measurements he makes ta k e on meaning i n the c o n t e x t of h i s mental model of the power s u p p l y , and t h i s 1 7 e n a b l e s him t o put f o r w a r d a h y p o t h e s i s . But i f h i s mental model i s wrong, h i s s o l u t i o n w i l l p r o b a b l y be wrong t o o . U n f o r t u n a t e l y , SOPHIE i s not s u f f i c i e n t l y i n t e l l i g e n t t o e x p l a i n why i t i s wrong. 2.3.4 Enumerating Bugs i n C a s u a l Reasoning T h i s m i l e s t o n e works towards a t h e o r y of t u t o r i a l i n t e r a c t i o n t h a t enumerates the t y p e s of c o n c e p t u a l bugs s t u d e n t s have i n t h e i r u n d e r s t a n d i n g of p h y s i c a l p r o c e s s e s , and t r i e s t o diagnose and c o r r e c t t h e s e bugs from d i f f e r e n t r e p r e s e n t a t i o n a l v i e w p o i n t s . Stevens et a l (1978) b u i l t a system based on t h i s t h e o r y , c a l l e d WHY, which t u t o r s the causes of r a i n f a l l . The t h e o r y i s f o r m a l i z e d as a s e t of S o c r a t i c t u t o r i n g r u l e s and a s c r i p t - l i k e knowledge s t r u c t u r e (Schank & A b e l s o n , 1977). The s c r i p t s t r u c t u r e r e p r e s e n t s the d i f f e r e n t t e m p o r a l and c a u s a l s t e p s i n p r o c e s s e s t h a t a f f e c t r a i n f a l l . A l t h o u g h the f i r s t v e r s i o n of the WHY system i s a b l e t o c a r r y on s i m p l e t u t o r i a l d i a l o g u e s about the causes of r a i n f a l l , i n t e r a c t i o n w i t h i t r e v e a l s t h a t i t can d e t e c t s u r f a c e e r r o r s l i k e m i s s i n g s t e p s i n r e a s o n i n g about the causes of r a i n f a l l , but f a i l t o d i a g n o s e the u n d e r l y i n g m i s c o n c e p t i o n t h a t the e r r o r r e f l e c t s . The r e s e a r c h e r s b e l i e v e t h a t one of the major s k i l l s a good t e a c h e r p o s s e s s e s i s knowledge about the t y p e s of c o n c e p t u a l bugs s t u d e n t s a r e l i k e l y t o have, the m a n i f e s t a t i o n s of t h e s e bugs and methods f o r c o r r e c t i n g them. So an i m p o r t a n t component of an ICAL system i s a method f o r r e p r e s e n t i n g , d i a g n o s i n g and c o r r e c t i n g bugs. To enumerate the bugs i n s t u d e n t s ' c a u s a l u n d e r s t a n d i n g of 18 r a i n f a l l , a q u e s t i o n n a i r e survey was c a r r i e d o u t . I t asks 32 q u e s t i o n s about the causes of heavy r a i n f a l l . From the s u b s t a n t i a l body of d a t a on e r r o r s and m i s c o n c e p t i o n s g a t h e r e d , the r e s e a r c h e r s i d e n t i f i e d 16 d i f f e r e n t bugs t h a t account f o r 72% of i n c o r r e c t answers. The next s t e p i s t o r e p r e s e n t t h e s e bugs i n a diagnose-and-c o r r e c t g o a l s t r u c t u r e . T h i s r e q u i r e s a d e t a i l e d f o r m a l i s m f o r r e p r e s e n t i n g the knowledge t a u g h t . S c r i p t s t r u c t u r e s can be used t o r e p r e s e n t o r d e r e d c a u s a l and tempor a l p r o c e s s e s , but t h i s h a n d l e s o n l y a s m a l l number of bug r e p r e s e n t a t i o n s and v i e w p o i n t s from which t o d i s c u s s them. C o l l i n s proposes a f u n c t i o n a l v i e w p o i n t which emphasizes the f u n c t i o n a l r e l a t i o n s h i p among the a t t r i b u t e s of the v a r i o u s o b j e c t s i n v o l v e d i n d i f f e r e n t p r o c e s s e s . The b a s i c u n i t i s a d e s c r i p t i o n of some p r o c e s s such as e v a p o r a t i o n or c o o l i n g . Here i s an example of the f u n c t i o n a l r e l a t i o n s h i p f o r e v a p o r a t i o n : A c t o r s ( w i t h a r o l e i n the p r o c e s s ) Source : Large- b o d y - o f - w a t e r D e s t i n a t i o n : Air-mass F a c t o r s (which a f f e c t the p r o c e s s ) Temperature (Source) Temperature ( D e s t i n a t i o n ) P r o x i m i t y (Source, D e s t i n a t i o n ) F u n c t i o n a l - r e l a t i o n s h i p (which h o l d amomg the f a c t o r s and r e s u l t ) P o s i t i v e (Temperature ( S o u r c e ) ) P o s i t i v e (Temperature ( D e s t i n a t i o n ) ) P o s i t i v e ( P r o x i m i t y ( S o u r c e , D e s t i n a t i o n ) ) R e s u l t (of p r o c e s s ) I n c r e a s e (Humidity ( D e s t i n a t i o n ) ) 19 M i s c o n c e p t i o n s a r e r e p r e s e n t e d as m e a n i n g f u l t r a n s f o r m a t i o n s of the b a s i c knowledge r e p r e s e n t a t i o n . For example, the r e p r e s e n t a t i o n f o r the c o o l i n g - b y - e x p a n s i o n bug i s : A c t o r s Source : Large-body-of-water D e s t i n a t i o n : Air-mass F a c t o r s P r e s s u r e ( D e s t i n a t i o n ) P r o x i m i t y (Source, D e s t i n a t i o n ) Funct i o n a l - r e l a t i o n s h i p I n v e r s e ( P r e s s u r e ( D e s t i n a t i o n ) ) P o s i t i v e ( P r o x i m i t y ( S o u r c e , D e s t i n a t i o n ) ) R e s u l t (of p r o c e s s ) I n c r e a s e ( H u m i d i t y ( D e s t i n a t i o n ) ) T h i s bug c o n s i s t s of a s u b s t i t u t i o n of p r e s s u r e f o r temperature as the r e l e v a n t a t t r i b u t e of the d e s t i n a t i o n i n the normal r e p r e s e n t a t i o n f o r e v a p o r a t i o n . Bugs can show up i n a l l p a r t s of the r e p r e s e n t a t i o n . I n s t e a d of v i e w i n g a s t u d e n t model as a s i m p l i f i c a t i o n of the e x p e r t ' s r u l e s , t h i s m i l e s t o n e t r e a t s i t as a s e t of ' s e m a n t i c a l l y m e a n i n g f u l d e v i a t i o n s ' from an e x p e r t ' s knowledge. 2.3.5 I n t e r p r e t i n g Student Behaviour i n terms of E x p e r t  Knowledge P a s t and c u r r e n t r e s e a r c h on an t h e o r y of s t u d e n t m o d e l l i n g has been f o c u s e d on the n o t i o n t h a t i f one has an e x p l i c i t , w e l l - f o r m u l a t e d knowledge base of an e x p e r t f o r a gi.ven problem-domain, then one can model a s t u d e n t ' s knowledge as a 20 s i m p l i f i c a t i o n of the r u l e s c o m p r i s i n g the e x p e r t ' s p r o c e d u r e s . G o l d s t e i n (1977) has c o i n e d the term ' o v e r l a y model' t o expand t h i s concept i n h i s Computer Coach r e s e a r c h . The main i d e a i s t o e x p l a i n d i f f e r e n c e s between the b e h a v i o u r of the e x p e r t and the s t u d e n t i n terms of the l a c k , on the s t u d e n t ' s p a r t , of some of the e x p e r t ' s s k i l l s . Thus, an o v e r l a y model i s a s e t of h y p o t h e s e s , each of which r e c o r d s the system's c o n f i d e n c e t h a t a s t u d e n t p o s s e s s a g i v e n s k i l l . O v e r l a y m o d e l l i n g has been deve l o p e d as p a r t of the COACH P r o j e c t a t MIT, whose con c e r n i s the development of A l - b a s e d CAI programs f o r t u t o r i n g the s k i l l s r e q u i r e d f o r s u c c e s s f u l l y p l a y i n g v a r i o u s computer games (WUSOR 2 f o r p l a y i n g WUMPUS and WEST f o r the PLATO game "How the West has won"). The computer s e r v e s as an a s s i s t a n t t o a l e a r n e r who i s i n the p r o c e s s of a c q u i r i n g the s k i l l s n e c e s s a r y t o p l a y the game w e l l . O v e r l a y m o d e l l i n g i s embodied i n a P s y c h o l o g i s t model, the component of the coach r e s p o n s i b l e f o r m a i n t a i n i n g such models of the p l a y e r ' s c u r r e n t s k i l l s ( the K model) and l e a r n i n g p r e f e r e n c e s ( t h e L model). These models are used by the T u t o r module t o prune complex, e x p l a n a t i o n s g e n e r a t e d by the e x p e r t . L i k e a human spe a k e r , the coach a b b r e v i a t e s i t s s t a t e m e n t s by e l i m i n a t i n g t h o s e f a c t s t h a t a r e a l r e a d y known by the l i s t e n e r and t h o s e f a c t s t h a t a r e too complex. The m o d e l l i n g i s performed by a s e t of P r u l e s t h a t are t r i g g e r e d by d i f f e r e n t s o u r c e s of e v i d e n c e , and whose e f f e c t i s t o m o d i f y a s e t of hypotheses r e g a r d i n g the s t u d e n t ' s f a m i l i a r i t y w i t h the e x p e r t ' s s k i l l s . A P c r i t i c m o n i t o r s t h e s e r u l e s t o d e t e c t d i s c o n t i n u i t i e s and i n c o n s i s t e n c i e s i n the 21 p l a y e r ' s b e h a v i o u r . I n c o n s i s t e n c i e s a r e e v i d e n c e t h a t t h e P r u l e s a r e f a i l i n g t o m o d e l t h e s t u d e n t p r o p e r l y , w h i l e d i s c o n t i n u i t i e s i n d i c a t e a c h a n g e i n t h e p l a y e r ' s k n o w l e d g e s t a t e . A s no s i n g l e s o u r c e o f e v i d e n c e i s a c e r t a i n i n d i c a t o r o f a l e a r n e r ' s k n o w l e d g e , t h e P s y c h o l o g i s t i s p r o v i d e d w i t h 4 s o u r c e s o f e v i d e n c e : (1) i m p l i c i t - The s t u d e n t ' s p l a y i n d i c a t e s h i s m a s t e r y o f v a r i o u s s k i l l s . The a s s u m p t i o n i s t h a t t h e p l a y e r h a s l e a r n e d t h o s e s k i l l s i n v o l v e d i n c h o o s i n g h i s p a r t i c u l a r move a n d r e j e c t i n g i t s i n f e r i o r s , a n d h a s y e t t o l e a r n t h o s e s k i l l s n e e d e d t o r e c o g n i z e s u p e r i o r m o v e s . (2) s t r u c t u r a l - The e x p e r t ' s s k i l l s a r e s t r u c t u r e d i n t o a s y l l a b u s w h i c h i s a n e t w o r k l i n k i n g t h e s k i l l s i n t e r m s o f t h e i r c o m p l e x i t i e s a n d d e p e n d e n c i e s . S t r u c t u r a l k n o w l e d g e -s u g g e s t s c o n s e r v a t i v e l y t h a t a s t u d e n t f a m i l i a r w i t h a c e r t a i n r e g i o n o f t h e s y l l a b u s ( a s i n d i c a t e d by t h e K m o d e l ) i s m o r e l i k e l y t o a c q u i r e a new s k i l l a t t h e f r o n t i e r o f t h i s r e g i o n r a t h e r t h a n d e e p i n t o unknown t e r r i t o r y . ( 3 ) e x p l i c i t - The t u t o r c a n o b t a i n e x p l i c i t e v i d e n c e by a s k i n g t h e s t u d e n t t w o t y p e s o f q u e s t i o n s : t e s t c a s e s a n d f o l l o w -up q u e s t i o n s . ( 4 ) b a c k g r o u n d - E v e r y t e a c h e r h a s e x p e c t a t i o n s a b o u t t h e p e r f o r m a n c e o f a s t u d e n t on t h e b a s i s o f t h a t s t u d e n t ' s b a c k g r o u n d . T h u s s k i l l l e v e l s a r e c l a s s i f i e d i n t o v a r i o u s l e v e l s , l i k e " n o v i c e " , " a m a t e u r " , o r " e x p e r t " , a n d c o r r e s p o n d t o a d i f f e r e n t i n i t i a l i z a t i o n f o r t h e o v e r l a y 22 model. The c o n t r i b u t i o n of o v e r l a y m o d e l l i n g i s t h a t i t i s e s s e n t i a l l y a l i n g u i s t i c t h e o r y of the speaker ( C a r r , 1977). Each of us, when f o r m u l a t i n g an e x p l a n a t i o n , a b b r e v i a t e s the e x p l a n a t i o n i n a c c o r d w i t h our model of the s p e a k e r . T h i s model i s based on our a n a l y s i s of the l i s t e n e r ' s b e h a v i o u r i n terms of the knowledge we know and the knowledge we b e l i e v e he needs t o know. O v e r l a y m o d e l l i n g performs a s i m i l a r f u n c t i o n f o r a computer t u t o r . Indeed, a person or computer can o n l y judge another i n terms of what he, she or i t knows i t s e l f . O v e r l a y m o d e l l i n g r e s t s on the assumption t h a t the s k i l l s employed by the s t u d e n t a r e a subset of those of an e x p e r t . T h i s i s not i n e v i t a b l e f o r a t l e a s t 3 reasons ( C a r r , 1977). F i r s t , the s t u d e n t may be s o l v i n g problems i n a f a s h i o n c o m p l e t e l y d i v e r g e n t from the e x p e r t - t h e r e may be m u l t i p l e paradigms f o r the p a r t i c u l a r problem domain. Second, the s t u d e n t may be u s i n g a n o n - o p t i m a l method f o r h i s own r e a s o n s . A computer game p l a y e r may be more concerned w i t h f i n i s h i n g q u i c k l y than a v o i d i n g r i s k , and choose t o a move t o a more i n f o r m a t i v e p o s i t i o n , d e s p i t e g r e a t e r r i s k . T h i r d , the s t u d e n t may p o s s e s s a s k i l l of the e x p e r t i n an i n c o r r e c t form, perhaps u s i n g i t i n a p p r o p r i a t e l y . M o d e l l i n g w i l l f a i l i f the complete absence o f a s k i l l cannot be d i s t i n g u i s h e d from i t s i n a p p r o p r i a t e use. Thus i t would be b e t t e r t o have a g e n e r a l t h e o r y of l e a r n i n g t h a t a d d r e s s s i t u a t i o n s i n which the s t u d e n t has an i n c o r r e c t s k i l l or an a l t e r n a t i v e s k i l l . 23 2.3.6 C o d i f y i n g D i s c o u r s e P r o c e d u r e s f o r Tea c h i n g So f a r , ICAL r e s e a r c h has fo c u s e d on the r e p r e s e n t a t i o n of domain e x p e r t i s e , the c o n s t r u c t i o n of a st u d e n t model, and t u t o r i n g p r i n c i p l e s f o r c o r r e c t i n g m i s c o n c e p t i o n s . I t has not d e a l t d i r e c t l y w i t h the problem of c a r r y i n g on a c o h e r e n t , p u r p o s e f u l t a s k - o r i e n t e d d i a l o g u e w i t h a s t u d e n t . In WEST and WUMPUS, f o r example, the t u t o r ' s remarks a r e a l l i n t e r r u p t i o n s or r e a c t i o n s t o the im m e d i a t e l y p r e c e d i n g move taken by the s t u d e n t . C l a n c e y (1979b) d i s c u s s e s a k i n d of m i x e d - i n i t i a t i v e d i a l o g u e t h a t c o n c e r n s a s i n g l e , complex t a s k t o be s o l v e d by a st u d e n t under a program's g u i d a n c e . Sequences of s t u d e n t / t u t o r remarks a re grouped i n t o ' d i s c o u r s e s i t u a t i o n s ' , some t y p i c a l examples of which a re : examining the s t u d e n t ' s u n d e r s t a n d i n g a f t e r he asks a q u e s t i o n t h a t shows unexpected e x p e r t i s e , and g i v i n g a d v i c e t o the st u d e n t a f t e r he makes an h y p o t h e s i s about a subproblem. C l a n c e y c a l l s the general' problem of s h a r i n g i n i t i a t i v e w i t h the stu d e n t and h a v i n g p r o v i s i o n s t o c a r r y out one's d i s c o u r s e g o a l s as ' d i a l o g u e management'. He d i s c u s s e d i t u s i n g GUIDON, the f i r s t t u t o r b u i l t on top of a complex e x p e r t system u s i n g MYCIN'S 400 p r o d u c t i o n r u l e s and t a b l e s f o r t e a c h i n g m e d i c a l d i a g n o s i s by the case method. GUIDON was f i r s t c o n c e i v e d as an e x t e n s i o n of the e x p l a n a t i o n system of the MYCIN c o n s u l t a t i o n program. With t h i s f o u n d a t i o n , a t u t o r i n g program would t a k e MYCIN'S s o l u t i o n t o a s t o r e d c o n s u l t a t i o n problem, a n a l y s e i t and use i t as the b a s i s f o r a d i a l o g u e w i t h a s t u d e n t t r y i n g t o s o l v e the same problem. The s t u d e n t i s g i v e n some i n f o r m a t i o n about a p a t i e n t expected 24 to have an i n f e c t i o u s d i s e a s e , and i s expected to request case data, as he sees necessary to draw c o n c l u s i o n s about the cause of the i n f e c t i o n . The t o p i c s of the dialog u e are p r e c i s e l y the goals that are determined by a p p l y i n g MYCIN'S r u l e s , l i k e the type of i n f e c t i o n . As the di a l o g u e proceeds, GUIDON i s able to c o l l e c t i n f o r m a t i o n about the student's knowledge of the case and i t s domain using an o v e r l a y model. T u t o r i a l remarks w i l l be given when a p p r o p r i a t e to make the students aware of any gaps or i n c o n s i s t e n c i e s i n h i s knowledge with respect to the u n d e r l y i n g expert r u l e base, and to c o r r e c t these d e f i c i e n c i e s . They range from s i n g l e p e r t i n e n t remarks to prolonged p r e s e n t a t i o n s that go beyond i n t e r r u p t i o n and r e p e t i t i v e q u e s t i o n / answering. B r i e f l y , the framework of GUIDON i n c o r p o r a t e s (1) domain knowledge i n the form of MYCIN-like r u l e base and records from the c o n s u l t a t i o n to be d i s c u s s e d with the student; (2) d i s c o u r s e knowledge i n the form of s e v e r a l hundred domain-independent t u t o r i n g r u l e s , organised i n t o d i s c o u r s e procedures f o r c a r r y i n g on the d i a l o g u e ; (3) a communication r e c o r d f o r r e c o r d i n g d i s c o u r s e goals and the dynamic s t a t e of the t u t o r i a l . Clancey represented the d i s c o u r s e knowledge i n the form of a t r a n s i t i o n diagram i n which the nodes are d i s c o u r s e s i t u a t i o n s ' and the l i n k s represent c h o i c e p o i n t s that l e a d to a l t e r n a t i v e d i a l o g u e s d i c t a t e d by domain l o g i c , economy of p r e s e n t a t i o n and t u t o r i n g g o a l s . These l i n k s represent the management d e c i s i o n s in which the t u t o r takes the i n i t i a t i v e to c o n t r o l d i a l o g u e s i t u a t i o n s . GUIDON a l s o p r o v i d e s f o r student i n i t i a t i v e by 25 a l l o w i n g him t o r e f e r back t o an e a r l y t o p i c and g a t h e r more d e t a i l s , t o make a c o n c l u s i o n when he i s ready, and t o change the d i a l o g u e t o p i c . One l i m i t a t i o n of the GUIDON framework of d i s c o u r s e p r o c e d u r e s i s t h a t i t can o n l y d i s c u s s r u l e - b a s e d knowledge, t h a t i s , t o p i c s t h a t can be e x p r e s s e d as p r o d u c t i o n r u l e s . A l s o , i n the c o u r s e of d e v e l o p i n g GUIDON some fundamental sh o r t c o m i n g s become c l e a r . There are 2 k i n d s of e x p l a n a t i o n s t h a t MYCIN cannot g i v e and GUIDON cannot t e a c h : i t cannot e x p l a i n why a p a r t i c u l a r r u l e i s c o r r e c t and i t cannot e x p l a i n the s t r a t e g y b e h i n d the d e s i g n of i t s g o a l s t r u c t u r e . MYCIN i s a p h a s i c - a b l e t o p e r f o r m , but unable t o t a l k about what i t knows. A human t e a c h e r can p r o v i d e a n a l o g i e s , m u l t i p l e v i e w s , and l e v e l of e x p l a n a t i o n s which are unknown t o MYCIN. MYCIN d i d not c a p t u r e a l l t h a t an e x p e r t knows, f o r example, how he o r g a n i z e s h i s knowledge, how he remembers i t , and s t r a t e g i e s he uses f o r s o l v i n g problems. C l a n c e y (1981) r e p o r t s t h a t many s t u d e n t s were unable t o remember the r u l e s , even a f t e r d i s c u s s i n g a s i n g l e problem w i t h GUIDON many t i m e s . D u r i n g 1979-80, a study was undertaken t o determine how an e x p e r t remembered MYCIN'S r u l e s and how he remembered t o use them. T h i s study ( o u t l i n e d i n C l a n c e y , 1981) u t i l i z e d s e v e r a l common AI methods f o r knowledge a c q u i s i t i o n , b u i l t upon them s i g n i f i c a n t l y through the development of an e p i s t e m o l o g i c a l framework f o r c h a r a c t e r i z i n g v a r i o u s k i n d s of knowledge. A new c o m p r e h e n s i b l e p s y c h o l o g i c a l model of m e d i c a l d i a g n o s i s was f o r m u l a t e d and implemented i n NEOMYCIN which i s a c o n s u l t a t i o n program i n which MYCIN'S r u l e s are r e c o n f i g u r e d t o make e x p l i c i t 26 d i s t i n c t i o n s t h a t are i m p o r t a n t f o r t e a c h i n g . The knowledge r e p r e s e n t a t i o n s e p a r a t e s out the i n f e r e n c e r u l e s ( s i m p l e d a t a / h y p o t h e s i s a s s o c i a t i o n s ) from the s t r u c t u r a l and s t r a t e g i c knowledge, t h a t i s , what a h e u r i s t i c i s from when i t i s t o be a p p l i e d . The s t r a t e g i e s and s t r u c t u r e model how an e x p e r t r e a s o n s . S e p a r a t i o n of problem knowledge ( i n f e r e n c e r u l e s ) and d i a g n o s t i c s t r a t e g y e n a b l e s a t u t o r i a l program t o p r e s e n t them s e p a r a t e l y t o a s t u d e n t , as w e l l as l o o k f o r them i n h i s b e h a v i o u r . With i t s t h e o r e t i c a l , e p i s t e m o l o g i c a l u n d e r p i n n i n g , NEOMYCIN i s d e s i g n e d t o p r e s e n t the s u b j e c t m a t e r i a l t h a t a new v e r s i o n of GUIDON, GUID0N2 can use t o e x p r e s s i m p o r t a n t t e a c h i n g p o i n t s . T h i s p r o v i d e s an example of how work i n ICAL has c o n t r i b u t e d t o new A l i d e a s and methods. 2.3.7 C o n s t r u c t i n g I n c o r r e c t P l a n s or P r o c e d u r e s T h i s m i l e s t o n e extends the work of Stevens e t a l (1978) i n d i a g n o s i n g m i s c o n c e p t i o n s i n u n d e r s t a n d i n g . Each s k i l l of the e x p e r t i s e x p l i c i t l y coded, a l o n g w i t h a s e t of p o t e n t i a l m i s c o n c e p t i o n s of t h a t s k i l l . The t a s k of i n f e r r i n g a d i a g n o s t i c  model then becomes one of d i s c o v e r i n g which set of v a r i a t i o n s or d e v i a t i o n s b e s t e x p l a i n s the s u r f a c e b e h a v i o u r of the s t u d e n t . T h i s view i s a l s o s i m i l a r t o but more s t r u c t u r e d than the approach taken by S e l f (1974) i n which he models the s t u d e n t as a s e t of m o d i f i e d p r o c e d u r e s taken from a p r o c e d u r a l e x p e r t p r o b l e m - s o l v e r . R e s e a r c h i n a d i a g n o s t i c model of b a s i c s k i l l s a r o s e from an i n v e s t i g a t i o n of the p r o c e d u r a l s k i l l s n e c e s s a r y t o s o l v e h i g h s c h o o l a l g e b r a problems (BUGGY, Brown e t a l , 1977). To 27 i l l u s t r a t e the model, we c o n s i d e r an example of t e a c h i n g a r i t h m e t i c s k i l l s . Brown (1978) noted t h a t i t i s no g r e a t c h a l l e n g e t o add or s u b t r a c t 2 numbers, but d i a g n o s i n g m i s c o n c e p t i o n s i n t h e s e s k i l l s can be q u i t e s u b t l e . C o n s i d e r a case study i n which we examine 5 " s n a p s h o t s " of a s t u d e n t ' s performance d o i n g a d d i t i o n as might be seen on a home work assignment : 41 328 989 66 216 + 9 + 917 + 52 + 887 + 13 50 1345 1141 1053 229 Example 1 In computer terms, the s t u d e n t , a f t e r d e t e r m i n i n g the c a r r y , f o r g e t s t o r e s e t the " c a r r y r e g i s t e r " t o 0 and hence the amount c a r r i e d i s accumulated a c r o s s the columns. The bug i s not so a b s u r d i f one c o n s i d e r s t h a t a c h i l d might use h i s f i n g e r s t o remember the c a r r y and f o r g e t t o bend back h i s f i n g e r s , a f t e r each c a r r y i s added. For a system t o be c a p a b l e of d i a g n o s i n g s t u d e n t ' s m i s c o n c e p t i o n s such as above, the p r o c e d u r a l s k i l l b e i n g t aught must be r e p r e s e n t e d i n a form amenable t o m o d e l l i n g i n c o r r e c t as w e l l as c o r r e c t subprocedures of t h a t s k i l l . F u r t h e r m o r e , the r e p r e s e n t a t i o n must a l l o w the i n t e r m i x i n g of both the c o r r e c t and i n c o r r e c t s k i l l s , so t h a t the model can c a p t u r e those p a r t s of a s k i l l t h a t are c o r r e c t as w e l l as wrong. The breakdown of the s k i l l i n t o shared s u b s k i l l s can a l s o account f o r the r e c u r r e n c e of s i m i l a r e r r o r s i n d i f f e r e n t s k i l l s . The r e p r e s e n t a t i o n a l t e c h n i q u e f o r d i a g n o s t i c models i s a p r o c e d u r a l network. A p r o c e d u r a l network model f o r a c o r r e c t 28 s k i l l c o n s i s t s of a c o l l e c t i o n of p r o c e d u r e s w i t h a n n o t a t i o n s i n which the c o n t r o l s t r u c t u r e between p r o c e d u r e s a r e made e x p l i c i t by a p p r o p r i a t e l i n k s . Each pro c e d u r e has 2 main p a r t s : a c o n c e p t u a l p a r t r e p r e s e n t i n g the i n t e n t of the p r o c e d u r e , and an o p e r a t i o n a l p a r t c o n s i s t i n g of methods f o r c a r r y i n g out t h a t i n t e n t . The methods are programs t h a t d e f i n e how the r e s u l t s of o t h e r p r o c e d u r e s a re combined t o s a t i s f y the i n t e n t of a p a r t i c u l a r p r o c e d u r e . Any proce d u r e can have more than one method, thus p r o v i d i n g a way t o model d i f f e r e n t methods f o r p e r f o r m i n g the same s k i l l . The p o s s i b l e m i s c o n c e p t i o n s i n each s k i l l a r e r e p r e s e n t e d i n the network by i n c o r r e c t methods a s s o c i a t e d w i t h subprocedures i n i t s d e c o m p o s i t i o n c a l l e d "bugs". Each buggy v e r s i o n c o n t a i n s i n c o r r e c t a c t i o n s taken i n p l a c e of the c o r r e c t ones. In Example 17 - we are p r o v i d e d w i t h s e v e r a l s u r f a c e m a n i f e s t a t i o n s of a bug i n the s t u d e n t ' s a d d i t i o n p r o c e d u r e . To uncover those p o s s i b l e subprocedures which a r e a t f a u l t , we use the p r o c e d u r a l network t o s i m u l a t e the b e h a v i o u r of buggy subprocedures over the s e t of pro c e d u r e s over the s e t of problems and note those which g e n e r a t e the same be h a v i o u r as e x h i b i t e d by the s t u d e n t . To c a t c h a s t u d e n t ' s m i s c o n c e p t i o n s t h a t i n v o l v e more than one f a u l t y subprocedure, we must be a b l e t o s i m u l a t e v a r i o u s c o m b i n a t i o n s of bugs. A d e e p - s t r u c t u r e model of the s t u d e n t ' s e r r o r s i s a s e t of buggy subprocedures t h a t , when i n v o k e d , r e p l i c a t e s those e r r o r s . Each buggy v e r s i o n has a s s o c i a t e d i n f o r m a t i o n such as what the u n d e r l y i n g causes of the bug may have been, as w e l l as s p e c i f i c r e m e d i a t i o n s , e x p l a n a t i o n s , i n t e r a c t i o n s , and examples of the 29 bug - a l l of which may be used by a t u t o r i n g system t o h e l p c o r r e c t the s t u d e n t ' s problem. The f i r s t problem t h a t n a t u r a l l y a r i s e s i s whether or not i t i s p o s s i b l e t o f o r m u l a t e the m o d e l l i n g problem so t h a t the c o m b i n a t o r i c s can be c o n t a i n e d . Brown and Bu r t o n note t h a t , g i v e n a s i z e a b l e number of buggy p r o c e d u r e s , the number of c o m b i n a t i o n s t o be c o n s i d e r e d i s e x t r e m e l y l a r g e . Sleeman and Smith (1981) propose s e v e r a l h e u r i s t i c s which reduce the s i z e of the s e a r c h space. Another i s s u e i s the p s y c h o l o g i c a l v a l i d i t y of the s k i l l d e c o m p o s i t i o n and buggy v a r i a n t s i n the network - how w e l l do the p r o c e d u r e s i n the network c o r r e s p o n d t o the s k i l l s t h a t we expect p e o p l e t o l e a r n ? I f the f u n c t i o n a l breakdown of the s k i l l i s not c o r r e c t , common bugs may be d i f f i c u l t t o model w h i l e those suggested by the model may be judged t o be " u n r e a l i s t i c " . We have a l s o l e f t open the e n t i r e i s s u e of a semantic t h e o r y of how p r o c e d u r e s a r e u n d e r s t o o d and l e a r n e d by a person and why bugs a r i s e i n the f i r s t p l a c e . An i n t e r e s t i n g t h e o r e t i c a l framework t h a t a c c o u n t s f o r the e n t i r e c o l l e c t i o n of e m p i r i c a l l y a r r i v e d a t bugs w i l l u ndoubtedly p r o v i d e i n s i g h t i n t o how t o c o r r e c t the t e a c h i n g p r o c e d u r e s t h a t produce them i n the f i r s t p l a c e . Moreover, such a t h e o r y would be the next s t e p i n a s e m a n t i c a l l y - b a s e d g e n e r a t i v e t h e o r y of s t u d e n t m o d e l l i n g . In BUGGY, bugs have t o be hand-coded i n t o the network. One can e n v i s i o n g e n e r a t i v e l y p r o d u c i n g bugs through i n a p p r o p r i a t e a nalogy from o t h e r o p e r a t i o n s or i n c o r r e c t g e n e r a l i z a t i o n from examples t h r o u g h a "semantic" t h e o r y . 30 2.3.8 R e l a t i n g I n c o r r e c t P r o c e d u r e s t o a G e n e r a t i v e Theory T h i s m i l e s t o n e marks c u r r e n t e f f o r t s t o form a g e n e r a t i v e t h e o r y of bugs i n p r o c e d u r a l s k i l l s . G iven a p r o c e d u r a l s k i l l , i t p r e d i c t s which s y s t e m a t i c e r r o r s or bugs w i l l o c cur i n the be h a v i o u r of s t u d e n t s l e a r n i n g the s k i l l . A c h i l d ' s e r r o r s a r e s a i d t o be s y s t e m a t i c i f t h e r e i s a proc e d u r e t h a t produces h i s erroneous answers. BUGGY and more r e c e n t l y DEBUGGY have been used t o a n a l y s e thousands of s t u d e n t ' s work ( B u r t o n , 1981 ; Vanlehn & F r i e n d , 1980). An e x t e n s i v e d a t a base of bugs was c o l l e c t e d and found t o be c o n v e r g i n g i n the sense t h a t they c o v e r a s u b s t a n t i a l number of st u d e n t e r r o r s and o n l y a s m a l l number of new bugs a r e b e i n g d i s c o v e r e d . The r e s e a r c h e r s i n v e s t i g a t e the cause of these bugs and the reasons they o c c u r . E f f o r t i s fo c u s e d on e x p l a i n i n g t h e s e known bugs i n terms of a s e t of f o r m a l p r i n c i p l e s t h a t t r a n s f o r m a p r o c e d u r a l s k i l l i n t o a l l of i t s buggy v a r i a n t s . A g e n e r a t i v e t h e o r y of bugs was de v e l o p e d t h a t e x p l a i n s how bugs a r i s e as a r e s u l t of s y s t e m a t i c e r r o r s i n p e r f o r m i n g a s k i l l . The t h e o r y must ge n e r a t e a l l the known or expected bugs f o r a p a r t i c u l a r s k i l l and i t must generate no o t h e r s . The t h e o r y i s m o t i v a t e d by the b e l i e f t h a t when a st u d e n t has u n s u c c e s s f u l l y a p p l i e d a pr o c e d u r e t o a g i v e n problem, he w i l l attempt a r e p a i r . Suppose he i s m i s s i n g a fragment of some c o r r e c t p r o c e d u r a l s k i l l , e i t h e r because he never l e a r n e d the fragment or he has f o r g o t t e n i t . I n s t e a d of q u i t t i n g because of an impasse, he w i l l o f t e n be i n v e n t i v e , i n v o k i n g h i s problem-s o l v i n g s k i l l s i n an attempt t o r e p a i r the impasse so t h a t he 31 can proceed t o execute the p r o c e d u r e , a l b e i t i n a p o t e n t i a l l y e r r o n e o u s way. The r e s e a r c h e r s b e l i e v e t h a t many bugs can best be e x p l a i n e d as "p a t c h e s " d e r i v e d from r e p a i r i n g a pr o c e d u r e t h a t has enc o u n t e r e d an impasse. Brown (1980) c a l l s the t h e o r y R e p a i r Theory. In the t h e o r y , a bug's d e r i v a t i o n has 2 p a r t s . The f i r s t i s a s e r i e s of o p e r a t i o n s t h a t g e n e r a t e an i n c o m p l e t e p r o c e d u r e , namely, a proce d u r e t h a t may r e a c h an impasse on c e r t a i n problems. The second p a r t i s a s e r i e s of o p e r a t i o n s t h a t r e p r e s e n t the r e p a i r of the proced u r e so t h a t i t can pr o c e e d . R e p a i r t h e o r y d e f i n e s the s e t of i n c o m p l e t e p r o c e d u r e s by a p p l y i n g a s e t of d e l e t i o n p r i n c i p l e s t o a f o r m a l r e p r e s e n t a t i o n of the c o r r e c t p r o c e d u r e f o r the g i v e n s k i l l . The s e t of r e p a i r s i s d e f i n e d by a s e t of r e p a i r h e u r i s t i c s and a s e t of c r i t i c s . When an i n c o m p l e t e p r o c e d u r e i s a p p l i e d t o a problem and reaches an impasse, a s e t of r e p a i r s i s performed by a gen e r a t e and t e s t p r o b l e m - s o l v e r . The s e t of r e p a i r h e u r i s t i c s suggest r e p a i r s and gen e r a t e bugs, and the c r i t i c s f i l t e r out the " s t a r - b u g s " a b s u r d bugs t h a t e x p e r t d i a g n o s t i c i a n s agree w i l l not be ob s e r v e d . The t h e o r y has been t e s t e d on the e x t e n s i v e database of bugs f o r m u l t i d i g i t s u b t r a c t i o n and not o n l y g e n e r a t e s the obs e r v e d bugs, but a l s o make p r e d i c t i o n s about the frequ e n c y and s t a b i l i t y of bugs (how o f t e n a bug o c c u r s i n the s t u d e n t s ' work and how l o n g a st u d e n t keeps a bug). While R e p a i r t h e o r y has been d e s i g n e d t o be r e l a t i v e l y domain-independent, i t has not been a p p l i e d t o domains o t h e r than p l a c e - v a l u e s u b t r a c t i o n . Brown(1980) argues t h a t R e p a i r t h e o r y can be a p p l i e d t o o t h e r domains and t h a t i t can be extended t o p r o v i d e a t h e o r y of 32 p r o c e d u r a l l e a r n i n g t h a t a c c o u n t s f o r bug a c q u i s i t i o n . 2.3.9 S e l f - I m p r o v i n g T e a c h i n g Systems One of the ways i n which CAL programs compare b a d l y w i t h human t e a c h e r s i s t h a t they do not b e n e f i t from t h e i r t e a c h i n g e x p e r i e n c e . A CAL program which t e a c h e s p o o r l y i n some way w i l l t e a c h p o o r l y i n e x a c t l y the same way a f t e r t e a c h i n g 10,000 s t u d e n t s . T h i s m i l e s t o n e a d d r e s s e s the i s s u e of the l a c k of l e a r n i n g c a p a b i l i t y i n CAL programs. O'Shea (1979) r e p o r t s o n l y t h r e e CAI programs i n the l i t e r a t u r e t h a t have a s e l f - i m p r o v i n g  c a p a b i l i t y - Smallwood's program (1962) t h a t t e a c h e s geometry, K i m b a l l ' s t u t o r (1973) f o r i n t e g r a t i o n and O'Shea's system f o r t e a c h i n g q u a d r a t i c e q u a t i o n s . S e l f - i m p r o v e m e n t c o u l d t a k e the form of i m p r o v i n g i t s i n t e r n a l r e p r e s e n t a t i o n of i t s t e a c h i n g m a t e r i a l . I t would mean l e a r n i n g new f a c t s , c o n c e p t s or s k i l l s from the s t u d e n t s b e i n g t a u g h t . For the most p a r t , such l e a r n i n g i s c o m p l e t e l y beyond the s t a t e of the a r t because of the way d o m a i n - s p e c i f i c knowledge i s r e p r e s e n t e d i n such programs (O'Shea, 1981). The o n l y example of a CAI program t h a t improves the i n t e r n a l r e p r e s e n t a t i o n of i t s t e a c h i n g m a t e r i a l i s t h a t of K i m b a l l ' s . In h i s program, i f a s t u d e n t ' s s o l u t i o n t o an a r c h i v e i n t e g r a t i o n problem i s b e t t e r (has fewer s t e p s ) than an a r c h i v e s o l u t i o n , then t h i s s t u d e n t ' s s o l u t i o n i s adopted and becomes the new a r c h i v e s o l u t i o n f o r t h a t problem. So the program's a b i l i t y t o c a r r y out i n t e g r a t i o n improves and hence i t s h i n t s t o the s t u d e n t s may change, but the e x t e n t ( r e s p o n s e - s e n s i t i v i t y ) , t o which i t can adapt t o the i n d i v i d u a l i z e d l e a r n i n g needs of i t s 33 remains f i x e d . 0'Shea proposes a d e s i g n f o r a s e l f - i m p r o v i n g t e a c h i n g system aimed a t i m p r o v i n g the q u a l i t y of i n s t r u c t i o n by a l t e r i n g and e x p e r i m e n t i n g w i t h those f e a t u r e s of CAI programs which r e l a t e t o t h e i r r e s p o n s e - s e n s i t i v i t y . Some s p e c i f i c examples of such f e a t u r e s a re : (a) the best o r d e r t o p r e s e n t a s e t of c o n c e p t s t o s t u d e n t s who have d i f f e r e n t s t y l e s (b) the p o i n t a t which a program m o n i t o r i n g a s t u d e n t p e r f o r m i n g a p r o b l e m - s o l v i n g t a s k s h o u l d i n t e r v e n e . The d e s i g n has two components. One component i s an a d a p t i v e t e a c h i n g program where the t e a c h i n g s t r a t e g y i s e x p r e s s e d as a set of p r o d u c t i o n r u l e s . The second component performs the s e l f -i m p r o v i n g f u n c t i o n of the system by making e x p e r i m e n t a l changes t o the s e t of p r o d u c t i o n r u l e s . T h i s component employs a d e d u c t i o n p r o c e d u r e which o p e r a t e s on a t h e o r y of i n s t r u c t i o n e x p r e s s e d as a s e t of mo d a l l y q u a l i f i e d a s s e r t i o n s . A t h e o r y of i n s t r u c t i o n i s concerned w i t h o p t i m i s i n g the l e a r n i n g p r o c e s s and can be re g a r d e d as an a c t i o n - d r i v e n p r o d u c t i o n system where the q u e s t i o n t o be answered by d e d u c t i v e i n f e r e n c e on the a s s e r t i o n s i s "What change i n t e a c h i n g s t r a t e g y w i l l improve t e a c h i n g performance wrt e d u c a t i o n a l o b j e c t i v e x ? " . The c y c l e of o p e r a t i o n s proposed f o r the system i s as f o l l o w s : s e l e c t an e d u c a t i o n a l o b j e c t i v e , make an e x p e r i m e n t a l change i n t e a c h i n g s t r a t e g y , s t a t i s t i c a l l y e v a l u a t e the r e s u l t i n g performance, and update both the s e t of p r o d u c t i o n r u l e s and the s e t of a s s e r t i o n s . A s e l f - i m p r o v i n g system was implemented f o r the t e a c h i n g of 34 q u a d r a t i c e q u a t i o n s by the d i s c o v e r y method. The system was used by 51 s t u d e n t s , and ex e c u t e d 5 e x p e r i m e n t a l changes on i t s t e a c h i n g s t r a t e g y . T h i s t r i a l d emonstrates t h a t i t was c a p a b l e of i m p r o v i n g i t s performance as a r e s u l t of e x p e r i m e n t a t i o n . Self-improvement i s p a r t i c u l a r l y a p p l i c a b l e t o those CAI programs i n t e n d e d t o run under v e r y l a r g e m u l t i - a c c e s s systems which a f f e c t v e r y l a r g e number of s t u d e n t s . These environments p r o v i d e c o n s i d e r a b l e amounts of performance d a t a which s h o u l d enable s e l f - i m p r o v i n g systems t o make r e l i a b l e m o d i f i c a t i o n s . The p r i n c i p a l c o n t r i b u t i o n of 0'Shea's program has been t o demonstrate the f e a s i b i l t y of c o n s t r u c t i n g an r e s p o n s e - s e n s i t i v e s e l f - i m p r o v i n g program. At p r e s e n t the system o n l y makes changes t o i t s t u t o r i a l s t r a t e g y . F u t u r e p o s s i b l e r e s e a r c h c o u l d be done on f a c i l i t a t i n g the e x p r e s s i o n and development of r i c h e r t h e o r i e s of i n s t r u c t i o n . 2.3.10 B u i l d i n g L e a r n i n g Environments G i v e n the k i n d s of deep p e d a g o g i c a l problems of CAL and the t e a c h e r ' s t r a d i t i o n a l d i s l i k e of machines i n the c l a s s r o o m , we can a n t i c i p a t e t h a t e x p e r t systems i n the shape of c o m p u t e r i s e d t u t o r s w i l l p l a y a minor r o l e f o r many y e a r s t o come (Howe, 1979). An a l t e r n a t i v e approach t o the use of computers i n e d u c a t i o n i s t o use the computer t o s i m u l a t e a m o d e l l i n g system which a l e a r n e r can use t o c a r r y out m o d e l - b u i l d i n g e x p e r i m e n t s . In the l a s t f i v e y e a r s , r e s e a r c h e r s have f o c u s e d on s u p p o r t i v e l e a r n i n g environments which attempt t o combine the problem-s o l v i n g e x p e r i e n c e and m o t i v a t i o n of ' d i s c o v e r y ' l e a r n i n g w i t h the e f f e c t i v e guidance of t u t o r i a l i n t e r a c t i o n s . 35 P i o n e e r i n g work has been done by F e u r z e i g and Papert i n mathematics l e a r n i n g . They emphasized the fundamental problem of i d e n t i f y i n g and naming the c o n c e p t s t h a t a b e g i n n e r needs t o e n a ble him t o e x p r e s s h i s t h o u g h t s i n a c l e a r way. With t h i s i n mind, they i n v e n t e d a s i m p l e but p o w e r f u l programming language c a l l e d LOGO which p r o v i d e s a c h i l d w i t h a language f o r d e s c r i b i n g p r o c e d u r e s . The c h i l d w i l l l e a r n t o i n v e n t and c a r r y out e x c i t i n g p r o j e c t s by h a v i n g a c c e s s t o computers and w i t h p e r i p h e r a l d e v i c e s c a p a b l e of p r o d u c i n g o n - l i n e r e a l - t i m e a c t i o n ( P a p e r t , 1971). In d o i n g so, he l e a r n s t o use computers i n a m a s t e r f u l way which can change the way he l e a r n s e v e r y t h i n g e l s e . A sound P i a g e t i a n p r i n c i p l e i s brought i n t o p l a y - new l e a r n i n g t a k e s p l a c e i n the framework of o l d knowledge, something the c h i l d a l r e a d y knows. There a r e two views c o n c e r n i n g the r e l e v a n c e of the a c t i v i t y of m o d e l - b u i l d i n g t o e d u c a t i o n . P a p e r t ' s view i s t h a t the programming approach s h o u l d emphasize p r o b l e m - s o l v i n g s k i l l s i n the e x p e c t a t i o n t h a t when a c h i l d has work i n s e v e r a l d i f f e r e n t domains, he w i l l r e c o g n i z e the s i m i l a r i t i e s between the methods used t o make p l a n s and t o debug them. In t h i s way, he w i l l b u i l d up genuine domain-independent s t u d y s k i l l s . O t hers t a k e the view t h a t these s k i l l s can o n l y be a p p r e c i a t e d when a person has e x t e n s i v e d o m a i n - s p e c i f i c knowledge, s u g g e s t i n g t h a t i n the e a r l y s t a g e s of l e a r n i n g emphasis s h o u l d be p l a c e d on c o n t e n t l e a r n i n g . E v i d e n c e of b e n e f i t of l e a r n i n g c o n t e n t or p r o b l e m - s o l v i n g s k i l l s has been s c a n t y . Some e v a l u a t i o n s t u d i e s (Howe, 1979) has shown t h a t LOGO has been s u c c e s s f u l i n t e a c h i n g d o m a i n - s p e c i f i c 36 knowledge l i k e mathematics and programming. When i t comes t o t e a c h i n g p r o b l e m - s o l v i n g s k i l l s , t h e r e i s l e s s e v i d e n c e of b e n e f i t . S t a t z (1973) r e c o r d s l i t t l e improvement i n c h i l d r e n ' s a b i l i t y t o cope w i t h p r o b l e m - s o l v i n g t a s k s a f t e r a y e a r ' s programming a c t i v i t y . Work i s a l s o done at the Xerox P a l o A l t o R esearch Center i n C a l i f o r n i a on d e s i g n i n g l e a r n i n g a c t i v i t i e s f o r ' c h i l d r e n ' of a l l ages. The aim i s t o p r o v i d e p o w e r f u l c o m p u t a t i o n a l f a c i l i t i e s and t e c h n i q u e s which can be a p p l i e d t o a d i v e r s e range of t a s k s i n s c h o o l and i n the o f f i c e , by c h i l d r e n and a d u l t s a l i k e (Kay, 1977). A new programming language c a l l e d S m a l l t a l k was d e v e l o p e d and i n i t , t r a n s a c t i o n s take the form of messages sent t o , or r e c e i v e d from, ' a c t i v i t i e s ' i n the system. Every a c t i v i t y belong t o a c l a s s , or f a m i l y of a c t i v i t i e s , each one of which has the a b i l i t y t o r e c o g n i z e and r e p l y t o messages. Each c l a s s a l s o has c e r t a i n c a p a b i l i t i e s , such as drawing p i c t u r e s , making m u s i c a l n o i s e s , or a d d i n g numbers. For example, t o program an a i r p l a n e s i m u l a t o r i n S m a l l t a l k , one would d e f i n e a c l a s s c a l l e d i n s t r u m e n t , and c r e a t e a c t i v i t i e s ( i n s t a n c e s ) of t h a t c l a s s t o draw the p a r t i c u l a r i n s t r u m e n t s on the d i s p l a y s c r e e n . Each i n s t r u m e n t would have i t s own p o s i t i o n on the s c r e e n , i t s own l a b e l and i t s own d i s p l a y e d v a l u e . A l t e r i n g one of the c o n t r o l s would cause messages t o be exchanged v i a the c l a s s which l o c a t e s the i n s t a n c e s to o b t a i n any v a l u e r e q u e s t e d or t o make a l t e r n a t i o n s t o t h e s e v a l u e s . A number of f e a t u r e s has been added t o S m a l l t a l k t o b u i l d T h i n g l a b ( B o r n i n g , 1979) which p r o v i d e s an o b j e c t - o r i e n t e d environment f o r b u i l d i n g s i m u l a t i o n s . T h i n g l a b a l l o w s the user 37 t o d e s c r i b e complex s i m u l a t i o n s e a s i l y by s p e c i f y i n g a l l the r e l a t i o n s ( c a l l e d c o n s t r a i n t s ) among the v a r i o u s o b j e c t s t h a t must be s a t i s f i e d and l e a v i n g i t up t o the system t o p l a n e x a c t l y how the c o n s t r a i n t s a r e t o be s a t i s f i e d . A l t h o u g h the i n t e r a c t i o n s among the p a r t s of s i m u l a t i o n system may be numerous, the user can s p e c i f y each r e l a t i o n w i t h o u t w o r r y i n g about the o t h e r s . A T h i n g l a b - s t y l e system might prove v a l u a b l e as p a r t of a geometry c u r r i c u l u m , or as an a d j u n c t t o a p h y s i c s l a b o r a t o r y . The l e a r n i n g environment i s viewed by some i n v e s t i g a t o r s such as P a p e r t as a s u b s t i t u t e f o r t r a d i t i o n a l c l a s s r o o m t e a c h i n g . P a p e r t saw the c l a s s r o o m as an a r t i f i c i a l and i n e f f i c i e n t l e a r n i n g environment and p e r c e i v e d t h a t s c h o o l s as we know them today w i l l have no p l a c e i n the f u t u r e ( P a p e r t , 1980). O t h e r s a r e l e s s r a d i c a l and a r e i n t e r e s t e d i n a d a p t i n g the l e a r n i n g environment t o the e x i s t i n g c l a s s r o o m , i n s t e a d of abandoning the e x i s t i n g c u r r i c u l a and s u b s t i t u t i n g the l e a r n i n g environment f o r i t . T h i s r a i s e s the i s s u e of e d u c a t i o n a l e v a l u a t i o n which we w i l l d i s c u s s l a t e r . 2.4 F u t u r e P r o s p e c t s Two i m p o r t a n t a r e a s which w i l l s u r e l y i n f l u e n c e ICAL a r e n a t u r a l language i n p u t and o u t p u t , and t e c h n o l o g i c a l advances. Most ICAL systems have some form of n a t u r a l language i n p u t / o u t p u t ( I / O ) , but the amount of language r e c o g n i s e d i s r a t h e r l i m i t e d . The u s u a l t e c h n i q u e s a re used : f i l l i n g i n t e m p l a t e s , f i n d i n g keywords or t h e i r synonyms, and a l i m i t e d degree of s p e l l i n g c o r r e c t i o n . Recent work i n n a t u r a l language 38 r e s e a r c h s u g g e s t s t h a t n a t u r a l language i n t e r f a c e s of c o n s i d e r a b l e power may be a v a i l a b l e f o r CAL systems. Gable & Page (1980) note t h a t The improvement i n communication between the s t u d e n t and the CAI system which o c c u r s because of improved language c a p a b i l i t y s h o u l d not be u n d e r e s t i m a t e d . I t would seem f a i r t o say t h a t a CAI system w i t h o u t e x t e n s i v e n a t u r a l language c a p a b i l i t y i s l i k e a t u t o r who speaks a language f o r e i g n t o the s t u d e n t . In the a r e a of human f a c t o r s e n g i n e e r i n g , i n t e l l i g e n t systems need t o exchange i n f o r m a t i o n smoothly and e f f i c i e n t l y w i t h the s t u d e n t ; t h a t i s , they s h o u l d be s e n s i t i v e t o the needs, c a p a c i t i e s and l i m i t a t i o n s of human b e i n g s . One p o s s i b i l i t y i s t o i n c l u d e some p a r t of the s t u d e n t ' s p s y c h o l o g i c a l s t a t e i n t o the s t u d e n t model i n o r d e r t o conduct a more a p p r o p r i a t e d i a l o g u e . The PARRY system of Col b y (1973) s i m u l a t e s a p a r a n o i d p e r s o n a l i t y and c o n s t r u c t s a model of the person u s i n g i t i n o r d e r t o be ready t o i n s u l t them l a t e r i n some t e l l i n g way. In an ICAL system, one c o u l d a n a l y z e unexpected or u n r e c o g n i z e d i n p u t s f o r s i g n s of boredom or anger i n o r d e r t o respond i n some a p p r o p r i a t e way. The p a r a n o i d a s p e c t of PARRY's p e r s o n a l i t y might make i t too human t o be an e f f e c t i v e t u t o r . I t may t y p i c a l l y become ' i m p a t i e n t ' or 'angry' and t e r m i n a t e s the s e s s i o n . But s t u d e n t s might e n j o y the p o s s i b i l i t y of c h o o s i n g the ' p e r s o n a l i t y ' of t h e i r t u t o r i a l system. Some might p r e f e r a m i l d l y p a r a n o i d t u t o r t o escape the monotony of e n d l e s s m e c h a n i c a l p a t i e n c e . V i s u a l a i d s have been used i n e d u c a t i o n f o r many y e a r s . The d e v e l o p i n g t e c h n o l o g y i n v i d e o r e c o r d i n g has extended the use of r e c o r d e d l e c t u r e s and d e m o n s t r a t i o n s i n t e a c h i n g . V i d e o s t o r a g e t e c h n o l o g y has been g r e a t l y enhanced by the v i d e o d i s k which has 39 the advantage of random a c c e s s and can s t o r e over 100,000 t e l e v i s i o n p i c t u r e s on a s i n g l e d i s k . C o s t s f o r s t o r a g e of a s i n g l e p i c t u r e a r e reduced 100 t i m e s over p r i n t i n g c o s t s , p r o v i d i n g a s i g n i f i c a n t i n c e n t i v e f o r use i n ICAL systems. Computers may be i n t e r f a c e d w i t h the v i d e o d i s k p r o v i d i n g s e l e c t i v e a c c e s s t o v i d e o frames or sequences. The v i d e o d i s k can a l s o be used t o s t o r e sound, l a r g e amounts of t e x t , or m i x t u r e s of t e x t , sound and moving p i c t u r e s . The use of v i d e o t e x f o r e d u c a t i o n a l s o h o l d s much promi s e . V i d e o t e x makes a v a i l a b l e computer-based i n f o r m a t i o n v i a v i s u a l d i s p l a y u n i t s , or a p p r o p r i a t e l y adapted t e l e v i s i o n s e t s , t o a d i s p e r s e d and r e a s o n a b l y numerous a u d i e n c e . In i n t e r a c t i v e v i d e o t e x ( l i k e P r e s t e l i n U. K. and T e l i d o n i n Canada), u s e r s can i n t e r a c t i n d i v i d u a l l y w i t h the computer, i n s t e a d of j u s t p a s s i v e l y r e c e i v i n g i n f o r m a t i o n . I n c r e a s i n g cheap CPU power t o cheap imaging systems means t h a t we can supplement or a l t e r the n a t u r e of ICAL systems from t e x t - b a s e d n a t u r a l language I/O t o g r a p h i c s or image-based I/O. The advent of i n e x p e n s i v e microcomputers makes a v a i l a b l e speech, sound, v i d e o and c o l o u r g r a p h i c s a t a c o s t s i g n i f i c a n t l y l e s s than many of the e a r l y e x p e n s i v e v i d e o d i s p l a y t e r m i n a l s . CAL s h o u l d be c o s t - e f f e c t i v e , as one reason t r a d i t i o n a l CAI has not p roved t o be as w i d e l y a c c e p t e d , p r a c t i s e d and d i s s e m i n a t e d i s t h a t t h e r e has been no o b v i o u s f i n a n c i a l advantages of CAI i n comparison t o c o n v e n t i o n a l e d u c a t i o n a l methods ( F i e l d e n , 1977). From a n o t h e r p e r s p e c t i v e , ICAL systems can be seen as e x p l o r a t i o n s i n t o how the d r a m a t i c advances i n computer t e c h n o l o g y can be used t o produce new k i n d s of l e a r n i n g 40 e n v i r o n m e n t s . F u t u r e paradigms f o r u s i n g computers i n e d u c a t i o n need not be c o n s t r a i n e d by s c a r c e c o m p u t a t i o n a l r e s o u r c e s . 2.5 The E v a l u a t i o n I s s u e The r a i s o n d ' e t r e of CAL i s perhaps i t s a b i l i t y t o p r o v i d e e f f e c t i v e i n d i v i d u a l i z e d t u t o r i n g . To c o n v i n c e p e o p l e o t h e r than i t s c r e a t o r s t h a t a CAL system i s w o r t h w h i l e , we have t o look a t the e v a l u a t i o n i s s u e , which poses two problems. On the one hand, t h e r e i s a c u r r e n t c r i s i s i n e d u c a t i o n a l r e s e a r c h (Howe, 1978) over the q u e s t i o n of what c o n s t i t u t e s an a c c e p t a b l e form f o r an e d u c a t i o n a l e v a l u a t i o n . On the o t h e r , we have the problem of e v a l u a t i n g CAL. One purpose of e d u c a t i o n a l e v a l u a t i o n i s t o p r o v i d e d e c i s i o n makers w i t h i n f o r m a t i o n about the e f f e c t i v e n e s s of an e d u c a t i o n a l program, p r o d u c t or p r o c e d u r e . W i t h i n t h i s p e r s p e c t i v e , e v a l u a t i o n i s viewed as a p r o c e s s i n which data a r e o b t a i n e d , a n a l y z e d , and s y n t h e s i z e d i n t o r e l e v a n t i n f o r m a t i o n f o r d e c i s i o n making. W h i l e th e s e i s b a s i c agreement about t h i s fundamental r o l e of e v a l u a t i o n i n e d u c a t i o n , t h e r e i s c o n s i d e r a b l e v a r i a n c e i n the c o n c e p t u a l framework, r e s u l t i n g i n numerous paradigms or models used by p r a c t i t i o n e r s ( B o r i c h et a l , 1981). The t a s k of e v a l u a t i n g a p r o t o t y p e ICAL system becomes one of c h o o s i n g the paradigm or model most a p p r o p r i a t e t o the e v a l u a t i o n problem. The g e n e r a l l y h i g h degree of s p e c i f i c i t y of CAL and i t s p o t e n t i a l f o r s a v i n g s t u d e n t r esponses o f f e r p o s s i b i l i t i e s f o r a d a p t i o n of i n s t r u c t i o n , and thus f o r e v a l u a t i o n t h a t a r e not p r a c t i c a l w i t h non-computer approaches. An ICAL system can 41 p e r f o r m i t s own s e l f e v a l u t i o n , c a l l e d i n t r i n s i c e v a l u a t i o n . Venezky (1983) proposed such a framework f o r e v a l u a t i n g ICAL systems. The o b j e c t i v e i s t o judge whether ICAL systems meet i n s t r u c t i o n a l needs and i s a d a p t a b l e t o the t o t a l c u r r i c u l u m . These t y p e s of e v a l u a t i v e i n f o r m a t i o n w i l l be needed : (1) the range of s t u d e n t s t r a t e g i e s the system i s c a p a b l e of d i a g n o s i n g ; (2) the p r o b a b i l i t i e s of d i a g n o s i n g each c o r r e c t l y ; (3) f o r each d i a g n o s i s , the e f f e c t i v e n e s s of the i n s t r u c t i o n t h a t f o l l o w s , i n terms of the achievement outcomes and the time spent l e a r n i n g . Venezky c h a r a c t e r i z e d ICAL programs as sequences of a s s e r t i o n s of the form ( S i , I i j , S j ) , where S i i s the l e a r n e r ' s c u r r e n t s t a t e , S j i s the next d e s i r e d s t a t e , and I i j i s the i n s t r u c t i o n g e n e r a t e d f o r moving from s t a t e S i t o s t a t e S j . Thus, a program a s s e r t s t h a t , based on i t s own d i a g n o s i s , the l e a r n e r i s i n s t a t e S i . F u r t h e r m o r e , i t a s s e r t s t h a t i n s t r u c t i o n I i j i s s u f f i c i e n t t o move the l e a r n e r t o s t a t e S j . The r o l e of e v a l u a t i o n i s t o a s s e s s the v a l i d i t y of both the s t a t e and i n s t r u c t i o n a s s e r t i o n s . To do t h i s , e v a l u a t i o n p r o c e d u r e s w i l l need t o be d e s i g n e d as an i n t e g r a l p a r t of the l e s s o n i t s e l f . ICAL systems s h o u l d be a d a p t i v e and c o n t i n u a l l y e v a l u a t e t h e i r own b e h a v i o u r and a d j u s t t h e i r i n s t r u c t i o n a l paradigms and t e a c h i n g s t r a t e g i e s a c c o r d i n g l y . To e v a l u a t e such systems ( l i k e O'Shea's s e l f - i m p r o v i n g program) e x t r i n s i c a l l y , i t w i l l be n e c e s s a r y t o d e t e r m i n e how the i n s t r u c t i o n a l approach changes w i t h s t u d e n t b e h a v i o u r . Another p e r s p e c t i v e i n e v a l u a t i n g ICAL i s t o p e r c e i v e i t 42 thr o u g h the e x p e r t v e r s u s the a p p r e n t i c e view of the automated t u t o r . We ask t h i s q u e s t i o n of any ICAL system : i s i t aimed a t r e p l a c i n g the t e a c h e r or a s s i s t i n g him or i s i t more of a t e s t -bed f o r e x p e r i m e n t i n g w i t h t h e o r i e s of i n t e l l i g e n c e , l e a r n i n g or t e a c h i n g . These 3 approaches use d i f f e r e n t means t o a c h i e v e t h e i r ends and thus s h o u l d be e v a l u a t e d on d i f f e r e n t c r i t e r i a . Indeed, a CAL system does not s t a n d or f a l l on i t s own m e r i t s . R a t h e r , i t s u t i l i t y depends on the manner i n which i t i s i n t e g r a t e d i n t o the c l a s s r o o m s e t t i n g and harmonized w i t h i n s t r u c t i o n a l o b j e c t i v e s . The a p p r e n t i c e view of an CAL system as a supplement t o t r a d i t i o n a l c l a s s r o o m t e a c h i n g i s more f r u i t f u l than the e x p e r t view of such a system s u p e r s e d i n g the t e a c h e r . The s t a t e - o f - t h e -a r t i n AI i s such t h a t the t a s k of m o d e l l i n g human i n t e l l i g e n c e i s s t i l l c o n s i d e r a b l e . There a r e not many examples of e x p e r t systems whose performance c o n s i s t e n t l y s u r p a s s e s t h a t of an e x p e r t . E v a l u a t i o n of t r a d i t i o n a l CAI has shown t h a t CAI i s more e f f e c t i v e i f i t supplements or i s supplemented by human i n s t r u c t o r s . A case i n p o i n t i s t h a t when the TICCIT system was used as a s o l e s o u r c e of i n s t r u c t i o n i n mathematics, the c o m p l e t i o n r a t e of the c o u r s e dropped s i g n i f i c a n t l y over t h a t of t r a d i t i o n a l c l a s s r o o m t e a c h i n g ( K e h l e r , 1 9 8 2 ) . ' ICAL r e s e a r c h has abandoned CAI's e a r l y o b j e c t i v e of p r o v i d i n g t o t a l c o u r s e s , and has c o n c e n t r a t e d on b u i l d i n g systems which p r o v i d e s u p p o r t i v e environments f o r more l i m i t e d t o p i c s (Brown & Sleeman, 1981). S i n c e the l e a r n i n g paradigm of ICAL emphasizes l e a r n i n g by d o i n g , i t seems u n l i k e l y t h a t the computer-based t u t o r w i l l be a b l e t o h a n d l e a l l s i t u a t i o n s t h a t 43 a r i s e . I t i s p r o b a b l e t h a t the main use of computers i n the c l a s s r o o m over the next decade w i l l not be f o r d e l i v e r y of complete c u r r i c u l a but as an a d j u n c t t o a t e a c h e r - d i r e c t e d c u r r i c u l u m . 2.6 Summary S i n c e i t s i n c e p t i o n about a decade ago w i t h an h i s t o r y not r e l a t i v e l y s h o r t f o r a c o m p u t e r - r e l a t e d f i e l d , ICAL r e s e a r c h has made some s i g n i f i c a n t advances t h r o u g h the m i l e s t o n e s d e s c r i b e d above. D i f f i c u l t c o n c e p t u a l i s s u e s s t i l l remain t o be s o l v e d b e f o r e the use of ICAL systems can be of e d u c a t i o n a l b e n e f i t . Most of the ICAL programs a r e e x p e r i m e n t a l and we can o n l y s p e c u l a t e whether or not thes e programs w i l l f i n d t h e i r way i n t o the c l a s s r o o m . In the s h o r t r u n , one of the key l i m i t a t i o n s t o the w i d e s p r e a d use of ICAL systems i s the heavy and e x a c t i n g demand p l a c e d on p r o c e s s i n g power, memory s i z e and s p e c i a l p e r i p h e r a l d e v i c e s , compared t o the a v a i l a b i l i t y of the s e r e s o u r c e s . In the l o n g r u n , the t e c h n o l o g i c a l c o n t e x t i s l i k e l y t o change i n ways which w i l l f a c i l i t a t e the i n t r o d u c t i o n of complex systems a t a l l l e v e l s i n the e d u c a t i o n a l system. In the next few y e a r s what we can a l s o e xpect t o see i s some f u r t h e r r e f i n e m e n t of our i n f o r m a t i o n - p r o c e s s i n g models of complex human a c t i v i t i e s such as s e e i n g , l e a r n i n g and t h i n k i n g . ICAL as an a p p l i c a t i o n a r e a f o r A l i s l i k e l y t o l e a d t o the f u r t h e r development of A l t e c h n i q u e s . On the o t h e r hand, e x c i t i n g A l i d e a s , methods and t e c h n i q u e s a r e p e r c o l a t i n g t h r o u g h i n t o the CAL f i e l d . 44 Chapter 3. Computer-Aided T e s t i n g , E v a l u a t i o n and A d v i c e (CATEA) 3.1 An Experiment i n W r i t i n g a CAL System We have seen t h a t one of the main f o c i of ICAL r e s e a r c h i s the d i a g n o s i s of m i s c o n c e p t i o n s or bugs i n u n d e r s t a n d i n g . One ob v i o u s a p p l i c a t i o n of work done i n t h i s a r e a i s i n the f i e l d of i n t e r a c t i v e c omputer-aided t e s t i n g (ICAT, C a r t w r i g h t & Derevensky, 1976) i n which the computer i s used t o a d m i n i s t e r a t e s t t o a s t u d e n t , e v a l u a t e h i s answer and p r o v i d e immediate feedback a f t e r each t e s t i t e m . An ICAT system can thus be used f o r t e a c h i n g , l e a r n i n g , d i a g n o s i s and e v a l u a t i o n . Research i n the d i a g n o s i s of s t u d e n t e r r o r s has emphasized the need t o know the t y p e s of c o n c e p t u a l bugs s t u d e n t s a r e l i k e l y t o have. Based on t h i s n o t i o n , we wi s h t o propose the d e s i g n and i m p l e m e n t a t i o n of an ICAT program. The o b j e c t i v e s of w r i t i n g such a CAL program are : (1) t o go th r o u g h an e x p e r i e n t i a l c y c l e of d e v e l o p i n g , t e s t i n g and e v a l u a t i n g a CAL program; (2) . t o e v a l u a t e how enumerating bugs and r e p r e s e n t i n g them can h e l p i n d i a g n o s i n g a s t u d e n t ' s m i s c o n c e p t i o n s ; (3) t o attempt some l i m i t e d use of A l t e c h n i q u e s i n d e v e l o p i n g the CAL program. The domain of i n t e r e s t has t o be r e s t r i c t e d so t h a t the t a s k of w r i t i n g a CAL program i s not overwhelming. We propose t o c o n s i d e r the assignment statement i n the P a s c a l programming language, e x p l o r e the m i s c o n c e p t i o n s s t u d e n t s have i n l e a r n i n g the statement, and w r i t e a program t o diagnose t h e s e m i s c o n c e p t i o n s . In the next s e c t i o n , we f i r s t l o o k a t the 45 d i f f i c u l t i e s n o v i c e s have w i t h the assignment s t a t e m e n t . 3.2 N o v i c e s ' M i s c o n c e p t i o n s of the P a s c a l Assignment Statement 3.2.1 Bayman and Mayer's work In r e c e n t y e a r s , some work has been done on the s u b j e c t of how n o v i c e s l e a r n programming (Boulay & O'Shea, 1981; Soloway e t a l , 1982; Bayman & Mayer, 1983; J o n i e t a l , 1983). The g e n e r a l o b j e c t i v e of th e s e works has been t o study m i s c o n c e p t i o n s i n u n d e r s t a n d i n g i n the minds of n o v i c e programmers. Of p a r t i c u l a r r e l e v a n c e t o t h i s t h e s i s i s the work done by Bayman and Mayer which f o c u s e s on 'what i s l e a r n e d ' when a s t u d e n t i s exposed t o h i s f i r s t programming language such as BASIC or P a s c a l . Bayman and Mayer p o s t u l a t e t h a t the outcome of l e a r n i n g can be viewed i n two d i s t i n c t ways : (1) L e a r n i n g BASIC or P a s c a l i n v o l v e s the a c q u i s i t i o n of new i n f o r m a t i o n and new r u l e s , such as how t o use quotes i n a PRINT or WRITE st a t e m e n t ; (2) L e a r n i n g BASIC or P a s c a l i n v o l v e s the a c q u i s i t i o n of a mental model, such as the i d e a of memory l o c a t i o n s f o r h o l d i n g numbers. They e x p l o r e the i d e a t h a t l e a r n i n g a programming language i n v o l v e s more than j u s t the a c q u i s i t i o n of s p e c i f i c f a c t s , r u l e s or s k i l l s . The b e g i n n i n g s t u d e n t a l s o d e v e l o p s mental models f o r the language i n the p r o c e s s of l e a r n i n g the e s s e n t i a l s of the language. A mental model r e f e r s t o the s t u d e n t ' s c o n c e p t i o n of the ' i n v i s i b l e ' i n f o r m a t i o n p r o c e s s i n g t h a t o c c u r s i n s i d e the computer. Bayman and Mayer (p. 677) note t h a t : 46 Most i n s t r u c t i o n a l e f f o r t i s d i r e c t e d s o l e l y at h e l p i n g the l e a r n e r a c q u i r e the new i n f o r m a t i o n and b e h a v i o u r s w i t h o u t g i v i n g much guidance t o the l e a r n e r f o r the a c q u i s i t i o n of u s e f u l mental models. A s t u d y was c a r r i e d out i n which 30 undergraduate s t u d e n t s l e a r n e d BASIC through a s e l f - p a c e d , mastery manual and s i m u l t a n e o u s l y had hands-on a c c e s s t o an Apple 2 computer. A f t e r i n s t r u c t i o n , the s t u d e n t s were t e s t e d on t h e i r mental models f o r the e x e c u t i o n of each of n i n e BASIC s t a t e m e n t s . 1 The r e s u l t s show t h a t b e g i n n i n g programmers, a l t h o u g h a b l e t o p e r f o r m a d e q u a t e l y on mastery t e s t s i n program g e n e r a t i o n , p o s s e s s e d a wide range of m i s c o n c e p t i o n s c o n c e r n i n g the s t a t e m e n t s they have l e a r n e d . In a wider p e r s p e c t i v e , Honi (1983) p r o v i d e s a c a t e g o r i z a t i o n f o r the t y p e s of m i s c o n c e p t i o n s t h a t m a n i f e s t themselves as bugs i n n o v i c e programmers' code : (1) A c l a s h between a s t u d e n t ' s preprogramming knowledge and h i s budding computer knowledge r e s u l t i n g i n a bug; (2) F a u l t y / i n c o m p l e t e u n d e r s t a n d i n g of programming c o n c e p t s . T h i s g e n e r a l c a t e g o r y can be broken down i n t o : a. O v e r g e n e r a l i z a t i o n of a concept : s t u d e n t s have d i f f i c u l t y d i s c e r n i n g the s p e c i f i c c o n t e x t i n which a concept i s a p p r o p r i a t e ; b. Hazy u n d e r s t a n d i n g of a c o n c e p t , t h a t does not m a n i f e s t i t s e l f i n s i m p l e programs, but comes t o l i g h t o n l y when more advanced t o p i c s a r e i n t r o d u c e d ; 1 0 f the n i n e s t a t e m e n t s , the assignment statement was the f o u r t h most d i f f i c u l t statement based on the p r o p o r t i o n of i n c o r r e c t c o n c e p t i o n s , a f t e r the INPUT, READ and IF s t a t e m e n t . 47 c. Simply not knowing the r u l e s of programming d i s c o u r s e t h a t guide the c o m p o s i t i o n of programming p l a n s i n t o u n d e r s t a n d a b l e and e x e c u t a b l e programs; (3) D i f f i c u l t i e s a r i s i n g from the c o o r d i n a t i o n of m u l t i p l e c o n s t r u c t s ; (4) S t u d e n t s may decompose the problem d i f f e r e n t l y from t h a t which was i n t e n d e d . In t h i s t h e s i s , by f o c u s i n g on the l e a r n i n g of one programming s t a t e m e n t , we have e x c l u d e d from d i s c u s s i o n any c o n s i d e r a t i o n of 2c, 3 and 4. 3.2.2 The P a s c a l Assignment statement The f i r s t statement a s t u d e n t l e a r n s i n h i s f i r s t programming language i s most p o s s i b l y the assignment . s t a t e m e n t , which i s a l s o the most f r e q u e n t l y used statement i n programming. As one of the most common languages t a u g h t i n f i r s t - y e a r computer s c i e n c e undergraduate c u r r i c u l a i s P a s c a l , we d e c i d e d t o c o n s i d e r how the assignment statement i n P a s c a l i s t a u g h t , l e a r n e d , u n d e r s t o o d or m i s u n d e r s t o o d . Appendix A shows how Programming i n P a s c a l . ( G r o g o n o , 1980), the t e x t f o r Computer S c i e n c e (CPSC) 114, " P r i n c i p l e s of Computer Programming I " , taught a t the U n i v e r s i t y of B r i t i s h C o l u m b i a , p r e s e n t s the assignment s t a t e m e n t . I t emphasizes t h a t e x e c u t i o n of an assignment statement r e s u l t s i n the l e f t - h a n d operand g e t t i n g the v a l u e of the r i g h t - h a n d s i d e . One might t h i n k t h a t the example "nextnumber := nextnumber+1" w i l l f o r c e a c o r r e c t mental model of the assignment statement (not c o n f u s i n g i t w i t h the a l g e b r a i c s t a t e m e n t ) . From t h e i r e m p i r i c a l s t u d y , 48 Soloway e t a l (1982) h y p o t h e s i z e t h a t s t u d e n t s might l e a r n or memorize the c o u n t e r v a r i a b l e update (I := 1+1) as an i n d i v i s i b l e u n i t or p a t t e r n . In o t h e r words, they do not decompose (I := 1+1) i n t o a l e f t - h a n d v a r i a b l e which has i t s v a l u e changed by the r i g h t - h a n d e x p r e s s i o n , and thus are not v i e w i n g (I := 1+1) as an example of the assignment s t a t e m e n t . Appendix B shows the 3 l e c t u r e s l i d e s used by i n s t r u c t o r s of the same c o u r s e f o r t e a c h i n g the statement. We observe t h a t the s l i d e s ' p r e s e n t a t i o n i s more comprehensive, i n t h a t they t r y to answer many doubts or m i s u n d e r s t a n d i n g s t h a t may a r i s e i n the mind of a s t u d e n t . By t a b u l a t i n g the v a l u e s of v a r i a b l e s b e f o r e and a f t e r e x e c u t i o n of an assignment s t a t e m e n t , they attempt t o i l l u s t r a t e v i v i d l y a c o r r e c t model f o r the s t a t e m e n t . I f we c o n c e p t u a l i z e the assignment statement as a l i s t of t r a n s a c t i o n s , a c o r r e c t model f o r the assignment statement A := B i n v o l v e s the f o l l o w i n g t r a n s a c t i o n s : (1) F i n d the number i n memory l o c a t i o n B; (2) E r a s e the number i n memory l o c a t i o n A; (3) W r i t e the number found i n (1) i n t o memory l o c a t i o n A. An e x p e r t programmer may have d e v e l o p e d an a c c u r a t e c o n c e p t i o n f o r a programming statement such as the assignment s t a t e m e n t . An n o v i c e may d i f f e r i n h i s mental model f o r the same statement or he may l a c k a c o h e r e n t mental model. I t may be t h a t the b e g i n n i n g s t u d e n t s t a r t s o f f w i t h an i n c o r r e c t model and as he a c q u i r e s new programming knowledge or more programming e x p e r i e n c e , he d i s c o v e r s , r e f i n e s or c o r r e c t s h i s i n c o r r e c t model on h i s own. We argue t h a t the t e a c h i n g p r o c e s s s h o u l d e x p e d i t e the e a r l y f o r m u l a t i o n of a c o r r e c t model i n the 49 s t u d e n t ' s mind, i n s t e a d of p e r m i t t i n g him t o harbour an i n c o r r e c t or i n c o h e r e n t one and l e a v i n g i t t o o t h e r ' e d u c a t i o n a l ' media t o r e c t i f y . How much t r a i n i n g one needs t o a c q u i r e a mental model has not y e t been e x p l o r e d i n r e s e a r c h . A f i r s t s t e p i n a d d r e s s i n g t h i s i s s u e i s t o study the n o v i c e u s e r ' s u n d e r s t a n d i n g of newly l e a r n e d programming statements (Bayman & Mayer, 1983). Based on e n c o u n t e r s w i t h n o v i c e s ' programs, we attempt t o enumerate the p o s s i b l e bugs or m i s c o n c e p t i o n s of the assignment s t a t e m e n t . The f i r s t bug i s the i n t e r p r e t a t i o n of A := B t o mean a s s i g n i n g the v a l u e of v a r i a b l e A t o v a r i a b l e B. We p o s t u l a t e t h a t t h i s semantic bug i s p o s s i b l e , though b i z a r r e , as we have seen m a n i f e s t a t i o n s of i t i n e x a m i n a t i o n s of s t u d e n t s who have a c t u a l l y gone t h r o u g h h a l f a term or one whole term of P a s c a l programming. The second bug r e f l e c t s the c o n f u s i o n of the e q u a l s i g n i n t r a d i t i o n a l a l g e b r a w i t h the assignment o p e r a t o r (Soloway e t a l , 1981). Soloway et a l (1982) observe t h a t a p o s s i b l e m a n i f e s t a t i o n of t h i s bug i s w r i t i n g a R u n n i n g - T o t a l update u s i n g l i n e s of code (Y := X + Z ; Z := Y) i n s t e a d of j u s t (Z := X + Z ) . W h i l e the presence of such s t a t e m e n t s as A := A+1 i n a s t u d e n t ' s program may i n d i c a t e the l a c k of t h i s bug, we cannot c o n c l u d e t h a t the s t u d e n t has t h i s bug from the absence of such s t a t e m e n t s . We p o s t u l a t e t h a t a c l e a r m a n i f e s t a t i o n of t h i s bug i s the e x p e c t a t i o n t h a t e x e c u t i o n of the l i n e s (A := 1; A := B; B := 2) w i l l r e s u l t i n both A and B a t t a i n i n g v a l u e s of 2. The t h i r d bug p o s s i b l y r e f l e c t s a hazy u n d e r s t a n d i n g of the 50 assignment s t a t e m e n t . Some s t u d e n t s when f i r s t e n c o u n t e r i n g the t a s k of swapping the v a l u e s of 2 v a r i a b l e s o f t e n come up w i t h (P := Q; Q := P ) . They expect P t o a t t a i n the v a l u e of Q, y e t somehow r e t a i n s i t s p r e v i o u s v a l u e . C o n c e i v a b l y , they have extended the ana l o g y of a v a r i a b l e as a ma i l b o x t h a t can h o l d one l e t t e r a t a time t o a m a i l b o x t h a t can h o l d s e v e r a l l e t t e r s . We c o n j e c t u r e t h a t i t i s a l s o p o s s i b l e t h a t they have taken a v a r i a b l e t o mean a queue. Thus P := Q would remove the f i r s t v a l u e of Q and append i t t o the queue of P. T h i s c o u l d e x p l a i n how (P := Q; Q := P) can be ex p e c t e d t o swap the v a l u e s of P and Q. The f o u r t h bug r e f l e c t s a c o n f u s i o n of the mail b o x w i t h i t s m a i l . Thus A := B i s taken t o mean t h a t c h a r a c t e r B, not the v a l u e of B, i s put i n t o v a r i a b l e A. The f i r s t t h r e e bugs a r e used as the f o u n d a t i o n f o r a ICAT program t h a t w i l l ask s t u d e n t t o w r i t e s i m p l e P a s c a l programs t h a t i l l u s t r a t e use of the assignment s t a t e m e n t . The f o u r t h bug i s not t e s t e d as s t u d e n t s who have o n l y j u s t l e a r n e d the assignment statement may not have known c h a r a c t e r t y p e s i n P a s c a l . The program w i l l attempt t o diag n o s e m a n i f e s t a t i o n s of th e s e bugs and p o s s i b l y detect- u n d i s c o v e r e d bugs. An e m p i r i c a l s t u d y of CATEA was c a r r i e d out w i t h some 47 v o l u n t e e r s t u d e n t s of CPSC 114 who had j u s t been taught the assignment statement i n c l a s s . In the next c h a p t e r , we s h a l l d e s c r i b e the d e s i g n and i m p l e m e n t a t i o n of CATEA. In Chapter 4, we s h a l l d e s c r i b e the r e s u l t s of the e m p i r i c a l s t u d y . 51 Chapter 4. Design and Implementation of CATEA 4.1 O v e r a l l S t r u c t u r e The g o a l of CATEA as an ICAT program i s t w o f o l d : e v a l u a t i o n and d i a g n o s i s . As an e v a l u a t i o n t o o l , CATEA t e s t s the a b i l i t y of s t u d e n t s t o w r i t e s i m p l e i n t r o d u c t o r y programs. As a d i a g n o s t i c t o o l , CATEA su g g e s t s m i s c o n c e p t i o n s i n the s t u d e n t ' s mind which u n d e r l i e i n c o r r e c t programs. W i t h the l i s t of our t h r e e enumerated bugs, each of which i n c o r p o r a t e s an i n c o r r e c t model of the assignment s t a t e m e n t , we d e s i g n t h r e e o s t e n s i b l y s i m p l e programming assignments ( h e r e a f t e r c a l l e d problems) f o r which the s t u d e n t has t o w r i t e a program. The problems ( F i g u r e 3) a r e d e s i g n e d so as t o e n t r a p the s t u d e n t i n t o m a n i f e s t i n g each of our enumerated bugs i n t h e i r programs, s h o u l d he posses s the u n d e r l y i n g m i s c o n c e p t i o n . The s t r u c t u r e of CATEA i s shown i n F i g u r e 4. CATEA d i s p l a y s a problem and the s t u d e n t ' s response w i l l be a t y p e d - i n program. CATEA w i l l attempt to c o m p i l e the program; i f t h e r e i s u n r e c o v e r a b l e s y n t a x e r r o r ( s ) , i t w i l l prompt the st u d e n t t o t r y a g a i n . O t h e r w i s e , CATEA w i l l e x e c u t e the program. I f c o r r e c t , the s t u d e n t r e c e i v e s a message t o t h a t e f f e c t and proceeds t o the next problem. I f i n c o r r e c t , the d i a g n o s t i c l o o p w i l l be i n v o k e d . 52 Problem 1 : W r i t e a P a s c a l program t h a t does the f o l l o w i n g : (1) D e c l a r e X, Y as i n t e g e r v a r i a b l e s (2) A s s i g n X the v a l u e of 1 (3) A s s i g n the v a l u e 2 t o Y (4) A s s i g n X t o Y (5) W r i t e out the v a l u e s of X and Y. Problem 2 : W r i t e a P a s c a l program t h a t does the f o l l o w i n g : (1) D e c l a r e A, B as i n t e g e r v a r i a b l e s (2) A s s i g n the v a l u e 1 t o A (3) A s s i g n the v a l u e A t o B (4) Now, make A and B have the v a l u e 2 (5) W r i t e out the v a l u e s of A and B. Probl-em 3 : W r i t e a P a s c a l program t h a t does the f o l l o w i n g : (1) D e c l a r e P, Q as i n t e g e r v a r i a b l e s (2) Read i n the v a l u e of P and Q (3) Now, exchange the v a l u e s of P and Q (4) W r i t e out the v a l u e s of P and Q. F i g u r e 3. Three Problems t e s t e d by CATEA The d i a g n o s t i c l o o p ( F i g u r e 5) w i l l attempt t o d e t e c t the u n d e r l y i n g bug which causes the i n c o r r e c t program. I f i t can n o t , i t w i l l d i s p l a y a ' F a i l - t o - d i a g n o s e ' message and move on t o the next problem. I f i t can diagnose a bug, r e m e d i a l a d v i c e ( p r e s t o r e d f o r each bug) w i l l be d i s p l a y e d f o l l o w e d by a m u l t i p l e - c h o i c e t e s t . The t e s t i s used t o f i n d out i f the s t u d e n t has g a i n e d a b e t t e r u n d e r s t a n d i n g , t h a t i s , become aware of t he bug. I f the s t u d e n t ' s answer t o the t e s t i s c o r r e c t , he w i l l p r o c eed t o the next problem or he can r e t r y the same problem. I f the s t u d e n t ' s answer i s wrong, he w i l l be o f f e r e d a c h o i c e - o f more r e m e d i a l a d v i c e or a second m u l t i p l e - c h o i c e t e s t . S h o u l d he get t h i s t e s t wrong a g a i n , the d i a g n o s t i c l o o p w i l l end w i t h a war n i n g t h a t he has y e t t o c o r r e c t h i s m i s c o n c e p t i o n Figure 4 . Structure of CATEA 54 I n c o r r e c t Response F i g u r e 5. D i a g n o s t i c Loop of CATEA (Blow-up of ' D i a g n o s i s ' bubble i n F i g u r e 4) 55 and a d v i s e s him t o t r y o t h e r r e m e d i a l s o u r c e s . When a l l q u e s t i o n s have been attempted or the s t u d e n t d e c i d e s he has had enough, he w i l l r e c e i v e a s c o r e which i n d i c a t e s how many of the t h r e e problems he has coded c o r r e c t l y . I f CATEA d e c i d e s t h a t the s t u d e n t s t i l l has m i s c o n c e p t i o n s , the s e s s i o n ends w i t h a summary of thes e m i s c o n c e p t i o n s . In Appendix C, we i l l u s t r a t e the d i a g n o s t i c l o o p i n g r e a t e r d e t a i l by t r a c i n g through a s t u d e n t ' s s e s s i o n as he a t t e m p t s Problem 3 (see F i g u r e 3 ) . Two i m p o r t a n t components of CATEA are the P a s c a l c o m p i l e r and the d i a g n o s t i c model. They a r e d e s c r i b e d i n the next two s e c t i o n s . 4.2 The P a s c a l C o m p i l e r As our f o c u s i s on programs t h a t i n c o r p o r a t e o n l y the use of the assignment s t a t e m e n t , we c o n s i d e r a subset of s t a n d a r d P a s c a l f o r our c o m p i l e r . Thus, i t w i l l a c c e p t as v a l i d o n l y a s i m p l e main program c o m p r i s i n g READ, WRITE or/and assignment s t a t e m e n t s . In the c o n s t a n t d e f i n i t i o n p a r t , the o n l y c o n s t a n t s c o n s i d e r e d v a l i d a r e i n t e g e r or boolean v a l u e s . In the v a r i a b l e d e c l a r a t i o n p a r t , the o n l y t y p e s c o n s i d e r e d v a l i d a r e INTEGER and BOOLEAN. The P a s c a l c o m p i l e r i s d e s i g n e d u s i n g the method of r e c u r s i v e descent ( D a v i s & M o r r i s i o n , 1981). The method c e n t r e s around the syn t a x a n a l y s i s phase which i s d i v i d e d i n t o a number of r e c o g n i t i o n p r o c e d u r e s , each of which has the t a s k of c h e c k i n g whether a p a r t i c u l a r k i n d of phrase i s p r e s e n t i n the i n p u t . Each r e c o g n i t i o n p r o c e d u r e can c a l l upon the s e r v i c e s of 56 o t h e r ones t o r e c o g n i s e the appearance of subphrases. The e r r o r d i a g n o s i s and r e c o v e r y scheme i s t h a t of Turner (1977) i n which an e r r o r i s d e t e c t e d when the c o m p i l e r e n c o u n t e r s a symbol i n the i n p u t t h a t i s not the g o a l symbol. Syntax a n a l y s i s c o n t i n u e s by s k i p p i n g the i n p u t u n t i l the next g o a l symbol and the i n p u t symbol match; t h i s b a l a n c e s the syntax t r e e and the i n p u t . A l l s y n t a x e r r o r messages have been w r i t t e n to make them as l u c i d and p r e c i s e as p o s s i b l e . The t a r g e t machine code w i l l be LISP s t r u c t u r e s . For example, the statement (X := 1) w i l l be c o m p i l e d i n t o the LISP l i s t (ASSIGNSY X 1 ) , which we c a l l a c l a u s e . Thus a program w i l l be c o m p i l e d i n t o a l i s t of such c l a u s e s which we c a l l a c l a u s e -l i s t and w i l l be the main o b j e c t f o r the next phase of program e x e c u t i o n . A s p e l l i n g c o r r e c t o r i s i n c o r p o r a t e d t o d e t e c t and - c o r r e c t s p e l l i n g e r r o r s of P a s c a l r e s e r v e d words. S p e l l i n g c h e c k i n g of a word from the i n p u t i s done o n l y a g a i n s t the s e t of r e s e r v e d words t h a t can be e x p e c t e d t o occur i n t h a t p o s i t i o n of the s y n t a x t r e e . The s p e l l i n g c o r r e c t i o n a l g o r i t h m i s t a k e n from the Ada i m p l e m e n t a t i o n of a s p e l l i n g c o r r e c t o r f o r an user i n t e r f a c e of Durham, et a l (1983). The s p e l l i n g e r r o r s i t l o o k s f o r a r e t r a n s p o s i t i o n of two a d j a c e n t l e t t e r s , one l e t t e r wrong, one l e t t e r e x t r a and one l e t t e r m i s s i n g . As the number of r e s e r v e d words i n our P a s c a l subset i s v e r y s m a l l , the s p e l l i n g c o r r e c t o r w i l l match a t most one c a n d i d a t e and so c o r r e c t i o n w i l l be done a u t o m a t i c a l l y . 57 4 . 3 The D i a g n o s t i c M o d e l F o r t h e d i a g n o s t i c m o d e l , we d r a w u p o n t h e w o r k o f B r o w n & B u r t o n ( 1 9 7 8 ) . B r o w n & B u r t o n u s e a s o p h i s t i c a t e d p r o c e d u r a l n e t w o r k m o d e l t o r e p r e s e n t t h e c o r r e c t p r o c e d u r e s o f a s k i l l . To d i a g n o s e b u g s , t h e n e t w o r k i s u s e d t o s i m u l a t e t h e b e h a v i o u r o f b u g g y v a r i a n t s o f t h e p r o c e d u r e s i n t h e n e t w o r k a n d n o t e t h o s e w h i c h g e n e r a t e t h e same b e h a v i o u r a s e x h i b i t e d by t h e s t u d e n t (BUGGY, B r o w n e t a l , 1 9 7 7 ) . I n C A T E A , we a d o p t e d a much s i m p l i f i e d d i a g n o s t i c m o d e l . A p r o c e d u r a l n e t w o r k i s n o t d e e m e d n e c e s s a r y a s u n d e r s t a n d i n g t h e a s s i g n m e n t s t a t e m e n t i s u n l i k e u n d e r s t a n d i n g a p r o c e d u r a l s k i l l s u c h a s a d d i t i o n o r s u b t r a c t i o n . To d i a g n o s e b u g s , CATEA s i m u l a t e s t h e b e h a v i o u r o f a n i n c o r r e c t m o d e l o f t h e a s s i g n m e n t s t a t e m e n t t o f i n d o u t i f t h e m o d e l e x p l a i n s t h e s u r f a c e - b e h a v i o u r o f t h e s t u d e n t ' s p r o g r a m , t h a t i s , t h e s t u d e n t ' s m e n t a l m o d e l w h i c h l e a d s h i m t o t h i n k t h a t h i s p r o g r a m i s c o r r e c t when i t i s n o t . We f e e l t h a t t h i s d i a g n o s t i c s t r a t e g y i s a d e q u a t e f o r o u r p u r p o s e s o f d i a g n o s i n g b u g s i n o u r n a r r o w d o m a i n a r e a . The o u t p u t o f t h e c o m p i l a t i o n p h a s e w i l l be a c l a u s e - l i s t c o n t a i n i n g a c l a u s e f o r e a c h e x e c u t a b l e p r o g r a m s t a t e m e n t . CATEA w i l l f i r s t e x e c u t e t h e p r o g r a m t o f i n d o u t i f i t i s c o r r e c t . I t w i l l e x e c u t e e a c h c l a u s e i n t h e c l a u s e - l i s t s e q u e n t i a l l y , a s s i g n i n g v a l u e s t o v a r i a b l e s a s s p e c i f i e d by e a c h a s s i g n m e n t s t a t e m e n t o r r e a d s t a t e m e n t . P r o g r a m c o r r e c t n e s s w i l l be d e t e r m i n e d by m a t c h i n g t h e v a l u e s o f p r e d e t e r m i n e d v a r i a b l e s t o p r e s t o r e d v a l u e s . F o r e x a m p l e , i n P r o b l e m 2 a c o r r e c t p r o g r a m (A := 1 ; B := A ; A := 2 ; B := 2) w i l l p u t v a l u e s o f 2 i n t o v a r i a b l e s A a n d B . I f t h e s t u d e n t ' s p r o g r a m a l s o p u t v a l u e s o f 2 58 i n t o A a n d B, i t w i l l be deemed c o r r e c t , o t h e r w i s e i n c o r r e c t . I f a s t u d e n t ' s p r o g r a m i s e v a l u a t e d t o be i n c o r r e c t , t h e n e x t t a s k o f CATEA w i l l be t o f i n d o u t w h i c h o f i t s e n u m e r a t e d bugs c a n e x p l a i n t h e b e h a v i o u r o f t h e p r o g r a m . CATEA w i l l s i m u l a t e an i n c o r r e c t m o d e l o f t h e a s s i g n m e n t s t a t e m e n t a nd e x e c u t e t h e c l a u s e - l i s t a g a i n . I f t h i s e x e c u t i o n a s s i g n s v a l u e s t o p r e d e t e r m i n e d v a r i a b l e s t h a t m a t c h t h a t o f p r e s t o r e d o n e s , t h e n CATEA w i l l p o s t u l a t e t h a t t h e i n c o r r e c t m o d e l i s t h e s o u r c e o f t h e bug. T h u s , i f a s t u d e n t i n d i c a t e s t h e p r e s e n c e o f t h e s e c o n d e n u m e r a t e d b u g , he may c o d e (A := 1; B := A; A := 2) f o r P r o b l e m 2 ( s e e F i g u r e 3, p. 52) w h i c h s p e c i f i e s t h a t A a n d B s h o u l d a t t a i n v a l u e s o f 2. He t h i n k s t h a t B := A i s l i k e an a l g e b r a i c s t a t e m e n t a nd t h e r e f o r e A := 2 w i l l a l s o c h a n g e t h e v a l u e o f B t o 2. L e t us s e e how CATEA s i m u l a t e s t h e s e c o n d bug i n t h e s t u d e n t ' s p r o g r a m . E x e c u t i n g A := 1, i t a s s i g n s ' " 1 t o A. E x e c u t i n g B := A, i t a s s i g n s t h e v a l u e o f A, t h a t i s , 1 t o B. E x e c u t i n g A := 2, i t a s s i g n s 2 t o A, s e a r c h e s f o r p r e c e d i n g a s s i g n m e n t s t a t e m e n t ( s ) t h a t h a s A i n i t s r i g h t - h a n d s i d e , f i n d s t h e s t a t e m e n t B := A, a n d a s s i g n s 2 t o B a s w e l l . I n t h e s t u d e n t ' s m i n d , h i s p r o g r a m w i l l e n d up w i t h v a l u e s o f 2 i n b o t h A a nd B, a n d t h e r e f o r e w o r k s . I f no model c a n e x p l a i n an i n c o r r e c t p r o g r a m ' s b e h a v i o u r , t h e n CATEA w o u l d h a v e f a i l e d t o d i a g n o s e t h e u n d e r l y i n g b u g . The t h r e e p r o b l e m s were d e s i g n e d so a s t o m i n i m i z e t h e p o s s i b i l i t y o f more t h a n one bug t h a t c a n e q u a l l y e x p l a i n t h e b e h a v i o u r o f an i n c o r r e c t p r o g r a m . P r o b l e m 1 i s d e s i g n e d t o e n t r a p t h e f i r s t e n u m e r a t e d b u g , P r o b l e m 2 t h e s e c o n d b u g , a n d P r o b l e m 2 t h e t h i r d b u g . T h i s a l s o s i m p l i f i e s o u r d i a g n o s t i c m o d e l by 59 o b v i a t i n g the need t o c o n s i d e r i n t e r a c t i o n of two or more bugs. The g u i d i n g metaphor of CATEA's d i a g n o s t i c model i s s i m u l a t i o n of bugs. A more s o p h i s t i c a t e d metaphor i s p a t t e r n matching at the p l a n l e v e l w i t h a program s o l u t i o n , which i s used i n MENO-II (Soloway e t a l , 1981), an i n t e l l i g e n t t u t o r i n g system b e i n g d e v e l o p e d f o r n o v i c e P a s c a l programmers. We p o s i t t h a t the s i m u l a t i o n approach i s s u f f i c i e n t f o r our purposes t o handle v e r y s i m p l e n o n - l o o p i n g programs. Moreover, t h i s d i a g n o s t i c approach a l l o w s CATEA t o ac c e p t m u l t i p l e ways of do i n g a t a s k . For example, i n Problem 2 (see F i g u r e 3 ) , CATEA w i l l a c c e p t a l l these programs as c o r r e c t : (A : = 1 ; B : = A; A : = A+ 1 ; B:=A) (A : = 1 ; B : = A; A : = 2*A; B:=2*B) (A : = 1 ; B : = A; A : = A+1 ; B:=B+1) (A : = 1 ; B : = A; A : = B+1 ; B:=B+1) (A : = 1 ; B : = A; B : = B+1 ; A:=B) 1 I f the f o u r t h statement i n each of these programs except the l a s t one i s removed,the program w i l l be a m a n i f e s t a t i o n of the second enumerated bug. For Problem 3 (see F i g u r e 3 ) , CATEA w i l l a c c e p t t h e s e programs as c o r r e c t : (P := P+Q; Q := P-Q; P := P-Q) (T1 := P; T2 := Q; Q := T1; P := T 2 ) 1 . We a l s o i n c o r p o r a t e two demons i n the d e s i g n of CATEA. The f i r s t demon i s invoked when redundant v a r i a b l e s a r e used as i n (Z := 1; ... X := Z) and Z i s not used i n the l e f t - h a n d s i d e of ^ 1 1 of t h e s e programs a r e a c t u a l s t u d e n t s ' programs i n our e m p i r i c a l s t u d y . B e f o r e the s t u d y , we had not thought of such programs as p o s s i b l e s o l u t i o n s t o the problems. 60 any o t h e r assignment statement. A message w i l l be d i s p l a y e d , s a y i n g t h a t t h i s c o u l d be e q u i v a l e n t l y coded as (X := 1) w i t h o u t i n t r o d u c i n g Z. The second demon checks f o r the i n c o r r e c t use of the t h i r d v a r i a b l e i n Problem 3. Thus i f a st u d e n t a t t e m p t s the use of the t h i r d v a r i a b l e but does i t i n c o r r e c t l y , CATEA w i l l remark t h a t h i s program i s i n c o r r e c t , but at the same time encourage him t h a t he has c o r r e c t l y p e r c e i v e d the requirement of a t h i r d v a r i a b l e . 4.4 Implementation CATEA i s w r i t t e n i n LISP/MTS ( W i l c o x & Hafner, 1974) and runs i n 200K b y t e s ( i n c l u d i n g the LISP i n t e r p r e t e r ) on an Amdahl V/8. 61 Chapter 5. An E m p i r i c a l Study of CATEA 5.1 D e s c r i p t i o n of Study An e m p i r i c a l study of CATEA was c a r r i e d out w i t h the p r i m a r y o b j e c t i v e of e x p l o r i n g how w e l l i t can d e t e c t bugs i n s t u d e n t s ' m i s u n d e r s t a n d i n g s of the assignment statement. S u b j e c t s were v o l u n t e e r s e n l i s t e d from the F a l l 1983 c l a s s of CPSC 114, P r i n c i p l e s of Computer Programming I . The f i r s t s e s s i o n of CATEA was a d m i n i s t e r e d t o a group of-20 s t u d e n t s , who had j u s t been taught the assignment statement t h a t v e r y week. Feedback from th e s e s t u d e n t s and t h e i r s e s s i o n p r o t o c o l s prompted improvements which were l a t e r i n c o r p o r a t e d i n t o CATEA. T h i s m o d i f i e d v e r s i o n of CATEA was a d m i n i s t e r e d t o a second group of 19 s t u d e n t s , who had a l s o been exposed t o the assignment statement i n the p r e v i o u s week. A l l of these 39 s t u d e n t s had y e t t o code t h e i r f i r s t programming assignment, and so CATEA p r o v i d e d them an o p p o r t u n i t y t o w r i t e t h e i r f i r s t P a s c a l programs. Feedback from t h i s second s e s s i o n a l s o g e n e r a t e d improvements i n CATEA. A week l a t e r , t he t h i r d s e s s i o n of CATEA was a d m i n i s t e r e d t o 9 s t u d e n t s who had done t h e i r f i r s t programming ass i g n m e n t s . Of t h e s e 9 s t u d e n t s , one had t r i e d CATEA b e f o r e . T h i s t h i r d s e s s i o n d i d not prompt any f u r t h e r r e f i n e m e n t t o CATEA. S u b j e c t s were g i v e n a q u e s t i o n n a i r e s u r v e y form t h a t c a n v a s s e d t h e i r o p i n i o n of t h e i r , i n t e r a c t i o n w i t h CATEA. A hardcopy p r o t o c o l l i s t i n g of each s t u d e n t ' s t e r m i n a l s e s s i o n was g e n e r a t e d f o r subsequent e v a l u a t i o n p u r p o s e s . In the next s e c t i o n , we d e s c r i b e the r e s u l t s of the e m p i r i c a l s t u d y . 62 5.2 R e s u l t s of Study In a s e s s i o n w i t h CATEA, the s t u d e n t w i l l be asked t o w r i t e programs as s o l u t i o n s t o a s e t of problems. For s c o r i n g p u r p o s e s , based on h i s or her response f o r each problem, we c l a s s i f y each s t u d e n t i n t o one of t h e s e c a t e g o r i e s : (1) Those who program c o r r e c t l y . T h e i r programs f o l l o w problem s p e c i f i c a t i o n s and a s s i g n v a l u e s t o p r e d e t e r m i n e d v a r i a b l e s which match those of s t o r e d ones; (2) Those who d i d not program c o r r e c t l y . E i t h e r t h e i r programs d i d not f o l l o w problem s p e c i f i c a t i o n or the v a l u e s of p r e d e t e r m i n e d v a r i a b l e s do not match those of p r e s t o r e d ones. We f u r t h e r s e p a r a t e t h i s c a t e g o r y i n t o two s u b c a t e g o r i e s : (a) Those whose e r r o r s CATEA can d e t e c t ; t h a t i s , one of CATEA's enumerated bugs i s i n s t a n t i a t e d i n t h e i r programs; (b) Those whose e r r o r s CATEA cannot d e t e c t ; (3) Those who g i v e up a f t e r some f u t i l e a t t e m p t s and opt f o r a s o l u t i o n t o be g i v e n ; (4) Those who d i d not attempt the problem and i n s t e a d s k i p p e d i t . T a b l e 1 t a b u l a t e s the r e s u l t s of the f i r s t two groups of 39 s t u d e n t s . We observe t h a t fewer than h a l f the s t u d e n t s got Problem 1 or Problem 3 c o r r e c t . Not s u r p r i s i n g l y , Problem 3 which i n v o l v e s the swapping of v a r i a b l e s ' v a l u e s p r o v e d the most d i f f i c u l t . T a b l e 2 shows the breakdown of s t u d e n t s who programmed 63 Table 1. Performance of the f i r s t two groups of 39 s t u d e n t s Problem 1 Problem 2 Problem 3 No. of s t u d e n t s who programmed c o r r e c t l y 19 48.7% 26 66.6% 18 46.0% No. of s t u d e n t s who programmed i n c o r r e c t l y 1 7 43.6% 1 1 28.2% 1 6 41.0% No. of s t u d e n t s who opted f o r s o l u t i o n t o be g i v e n 2 5.1% 1 2.6% 1 2.6% No. of s t u d e n t s who d i d not attempt 1 2.6% 1 2.6% 4 10.3% T o t a l no. of s t u d e n t s 39 1 00% 39 1 00% 39 1 00% T a b l e 2. Breakdown of s t u d e n t s i n f i r s t two groups who program  i n c o r r e c t l y No. of s t u d e n t s whose e r r o r s CATEA can d e t e c t 1 5 88% 6 55% 1 4 88% No. of s t u d e n t s whose e r r o r s CATEA c a n ' t d e t e c t 2 1 2% 5 45% 2 1 2% T o t a l no. of s t u d e n t s who programmed i n c o r r e c t l y 17 1 00% 1 1 100% 16 1 00% 64 i n c o r r e c t l y i n t o those whose e r r o r s CATEA can d e t e c t and those whose e r r o r s CATEA cannot d e t e c t . 88% (15 s t u d e n t s ) of s t u d e n t s who d i d Problem 1 i n c o r r e c t l y coded the assignment of X t o Y as X := Y, m a n i f e s t a t i o n s of our f i r s t enumerated bug. Most of the 55% (6 s t u d e n t s ) of s t u d e n t s who d i d Problem 2 i n c o r r e c t l y , coded (A := 1; B := A; A := 2 ) , m a n i f e s t a t i o n s of our second enumerated bug. The m a j o r i t y of the 88% (14 s t u d e n t s ) of s t u d e n t s who d i d Problem 3 i n c o r r e c t l y coded (P := Q) or (P := Q; Q := P ) . We b e l i e v e t h a t t h i s i s the s u r f a c e b e h a v i o u r of our t h i r d enumerated bug, i n which the s t u d e n t s do not have a c o r r e c t mental model of the assignment statement. As each problem has d e t a i l e d s t e p s on what t o w r i t e f o r the next s t a t e m e n t , we f e e l t h a t not a l l the e r r o r s a r e e x p l a i n a b l e s i m p l y as momentary 'mental s l i p s ' . Thus, we b e l i e v e t h a t the e r r o r s i n d i c a t e m i s c o n c e p t i o n s t h a t s t u d e n t s have about the assignment statement and cannot be a c c o u n t e d f o r by s i m p l y s a y i n g , "They make s i l l y e r r o r s . " In Problem 3, some of the s t u d e n t s who code (P := Q) or (P := Q; Q := P) were g i v e n the h i n t t h a t a t h i r d v a r i a b l e i s needed, but they s t i l l c o u l d not produce the c o r r e c t program. Some s t u d e n t s were observed t o s t i l l have d i f f i c u l t y even a f t e r CATEA has e x p l a i n e d and shown them the c o r r e c t way of swapping v a r i a b l e s (R := P; P := Q; Q := R ) . T h i s i s i n s p i t e of the f a c t t h a t swapping v a r i a b l e s has a l r e a d y been t a u g h t t o them i n c l a s s . I t was i n t r o d u c e d i m m e d i a t e l y a f t e r the assignment statement was t a u g h t . One p o s s i b l e e x p l a n a t i o n i s t h a t these s t u d e n t s see o n l y a p a t t e r n of the t h r e e assignment s t a t e m e n t s , i n s t e a d of the model (which i m p r i n t s more on the mind) beh i n d the s t a t e m e n t s . 65 L e t us l o o k a t those s t u d e n t s ' programs which c o n t a i n e r r o r s CATEA cannot d e t e c t . In the two c a s e s of Problem 1, the programs were (X := 1; Y := 2) which i g n o r e a s s i g n i n g X t o Y. We f.ix CATEA t o p a t t e r n match (ASSIGNSY Y X) i n the c l a u s e - l i s t so t h a t i t can d e t e c t and p i n p o i n t t h i s o m i s s i o n . In two c a s e s of Problem 2, the programs were (A := 1; B := 2) and (A := 1; A := B; A := 2; B := 2 ) . The second program a s s i g n s v a l u e s of 2 t o A and B which matches p r e s t o r e d answers and CATEA m i s t a k e n l y took i t t o be c o r r e c t . We p a t c h t h i s by d e t e c t i n g o m i s s i o n of the assignment statement t h a t a s s i g n s A t o B. For the o t h e r 3 c a s e s of Problem 2, the programs were (A := B ) , (A := 1; B := A; A := 2*A; B := 2*A) and (A := 1; B := A; B := 2 ) . For t h e s e , CATEA j u s t o f f e r e d i t s f a i 1 - t o - d i a g n o s e apology and proceeded t o the next problem. We p a t c h t h i s so t h a t CATEA can now g i v e the r e m e d i a l h i n t t h a t e i t h e r (or both) A or B has not a t t a i n e d the v a l u e of 2, as r e q u i r e d . For the two c a s e s of Problem 3, the programs were (READ ( P , Q ) ) . I t seems t h a t t h e s e two s t u d e n t s were at a l o s s of what t o do. CATEA f a i l e d t o say a n y t h i n g f o r these programs. We change CATEA so t h a t i t w i l l t e l l the s t u d e n t t h a t P has not a t t a i n e d the v a l u e of Q, and v i c e v e r s a . The use of a t h i r d v a r i a b l e i s o n l y suggested i f the s t u d e n t has a t t e m p t e d some more s t a t e m e n t s t o swap v a l u e s of P and Q, w i t h o u t u s i n g a t h i r d v a r i a b l e . The r e s u l t s of the t h i r d group of 9 s t u d e n t s a r e t a b u l a t e d i n T a b l e 3. 22% d i d Problem 1 i n c o r r e c t l y , about h a l f t h a t of 43.6% f o r the f i r s t 2 groups. 22% d i d Problem 2 i n c o r r e c t l y , l e s s than 28.2% f o r the f i r s t 2 groups. 44% d i d Problem 3 i n c o r r e c t l y s l i g h t l y more than 41.0% f o r the f i r s t 2 groups. 66 Table 3. Performance of the t h i r d group of 9 s t u d e n t s Problem 1 Problem 2 Problem 3 No. of s t u d e n t s who programmed c o r r e c t l y 6 67% 6 67% 5 55% No. of s t u d e n t s who programmed i n c o r r e c t l y 1 2 22% 2 22% 4 44% No. of s t u d e n t s who opted f o r s o l u t i o n t o be g i v e n 0 0% 0 0% 0 0% No. of s t u d e n t s who d i d not attempt 1 1 1% 1 1 1% 0 0% T o t a l no. of s t u d e n t s 9 1 00% 9 1 00% 9 1 00% 1CATEA was a b l e t o d e t e c t a l l of the s t u d e n t s ' e r r o r s 67 W h i l e the s m a l l sample s i z e of t h i s l a s t group makes the r e s u l t s l e s s s t a t i s t i c a l l y r e l i a b l e , we f e e l t h a t the r e s u l t s are i n t e r e s t i n g i n t h a t they i n d i c a t e s t u d e n t s even a f t e r they have w r i t t e n t h e i r f i r s t programs s t i l l harbour m i s c o n c e p t i o n s . In t h i s l a s t s e s s i o n , CATEA was a b l e t o d e t e c t a l l i n c o r r e c t programs and o f f e r r e m e d i a l h i n t s or h e l p . The s t u d e n t s ' p r o t o c o l s of a l l t h r e e s e s s i o n s r e v e a l e d no n o v e l bugs t h a t we have not enumerated, p o s s i b l y because each of the problems i s t a i l o r e d t o c a t c h one of the enumerated bugs. One s t u d e n t was both i n the f i r s t group and t h i r d group. In her f i r s t s e s s i o n , she wrote (Q := P; P := Q) f o r Problem 3. CATEA d i a g n o s e d t h i s and showed her the c o r r e c t way of d o i n g i t (R := P; P := Q; Q := R ) . In her second s e s s i o n two weeks l a t e r , she s t i l l got i t wrong by a t t e m p t i n g (Q := P; J := P; P := Q). I t seems t h a t a f t e r her f i r s t s e s s i o n , she remembered a p a t t e r n of assignment s t a t e m e n t s t h a t use a t h i r d v a r i a b l e but s t i l l c o u l d not c o n c e p t u a l i z e a c o r r e c t model. We summarize o t h e r o b s e r v a t i o n s we have g a t h e r e d from the s t u d e n t s e s s i o n s ' p r o t o c o l s : (1) Some s t u d e n t s attempted u s i n g the m u l t i p l e assignment statement (A,B := 2 or A+B := 2 or A := B := 2 ) , even though they do not have any p r e v i o u s computing e x p e r i e n c e ( w i t h programming languages l i k e PL/1 t h a t has such a s t a t e m e n t ) . One p o s s i b l e e x p l a n a t i o n i s t h a t the s t u d e n t e x t e n d s h i s mental model of the .assignment statement t o i n c l u d e m u l t i p l e a s s i g n m e n t s , s e e k i n g h i s own r e p a i r t o an impasse on the problem ( R e p a i r Theory of Brown, 1980). (2) E m p i r i c a l s t u d i e s of s y n t a c t i c e r r o r s i n u s e r s ' P a s c a l 68 programs have been done else w h e r e ( R i p l e y & D r u s e i k i s , 1978; Pugh & Simpson, 1979). Our r e s u l t s (which a p p l y t o n o v i c e s ) r e i t e r a t e two of t h e i r main f i n d i n g s : (a) The most e r r o r - p r o n e c o n s t r u c t i n P a s c a l i s the ( m i s s i n g ) s e m i c o l o n ; (b) S p e l l i n g e r r o r s a r e f a i r l y i n f r e q u e n t ; 5.3 Q u e s t i o n n a i r e Survey The r e s u l t s of the q u e s t i o n n a i r e survey a r e t a b u l a t e d i n Ta b l e 4. Do you t h i n k CATEA has h e l p e d you i n b e t t e r u n d e r s t a n d i n g the assignment statement i n P a s c a l ? YES 76% NO 8% PROBABLY 16% . Do you t h i n k CATEA has h e l p e d o t h e r f e a t u r e s of P a s c a l ? you i n b e t t e r u n d e r s t a n d i n g YES 62% NO 19% PROBABLY 19% Do you f e e l more c o n f i d e n t i n w r i t i n g P a s c a l programs ? YES 65% NO 11% PROBABLY 2 4% Tab l e 4. Student E v a l u a t i o n On the whole, s t u d e n t r e a c t i o n t o CATEA has been f a v o u r a b l e . I t appears t h a t s t u d e n t s f e e l t h a t t h i s e x p e r i e n c e was b e n e f i c i a l , e s p e c i a l l y i n i m p r o v i n g t h e i r u n d e r s t a n d i n g of the assignment s t a t e m e n t . The f o l l o w i n g q u e s t i o n s were a l s o i n the q u e s t i o n n a i r e : In what ways do you t h i n k CATEA can be improved? What e x t r a c a p a b i l i t y do you w i s h CATEA t o have? 69 In response t o the s e q u e s t i o n s , 38% of the s t u d e n t s suggest b e t t e r program e d i t i n g c a p a b i l i t y . C u r r e n t l y , i f a s t u d e n t ' s program has u n r e c o v e r a b l e s y n t a x e r r o r s , he has t o r e - e n t e r the program. In the t e r m i n a l on which CATEA was r u n , t h i s i n c o n v e n i e n c e can be p a r t i a l l y a l l e v i a t e d by moving the c u r s o r up t o the same l i n e i n the p r e v i o u s program, making the m o d i f i c a t i o n s on t h a t l i n e , and then h i t t i n g <return> t o e n t e r the l i n e , i n s t e a d of r e t y p i n g the l i n e . As most s t u d e n t s do not know how t o make use of t h i s keyboard f e a t u r e , t h i s might account f o r some of the s t u d e n t s ' c o m p l a i n t s . N e v e r t h e l e s s , we l e a r n something from t h i s ; t h a t i s , i n a CAL program, the st u d e n t do not l i k e t o be d i s t r a c t e d by s i d e - i s s u e s such as i n e f f i c i e n t human-tutor i n t e r f a c e s t h a t have no i m p o r t a n t b e a r i n g on the s u b j e c t domain. P a r t of the s t u d e n t s ' e n e r g i e s may be vent e d or consumed i n c o p i n g w i t h a bad human-computer i n t e r f a c e , and t h i s makes them l e s s i n c l i n e d t o l e a r n or perfor m w e l l the main t a s k s of the CAL program. Indeed, the i n t e r f a c e between the t u t o r and the s t u d e n t i s an im p o r t a n t component of any CAL system. O v e r a l l , e v a l u a t i o n of CATEA proved s a t i s f a c t o r y as i t . was" a b l e t o f u l f i l l i t s l i m i t e d o b j e c t i v e of d i a g n o s i n g m i s c o n c e p t i o n s i n the s t u d e n t s ' u n d e r s t a n d i n g of the assignment s t a t e m e n t . 70 Chapter 6 . C o n c l u s i o n While we d i d not set out i n t h i s t h e s i s to examine a wide range of i s s u e s d i r e c t l y r e l e v a n t to e d u c a t i o n , our study suggests some p o s s i b i l i t i e s that are worth c o n s i d e r i n g in the area of t e a c h i n g novices programming. By l o o k i n g at the kinds of e r r o r s that students make, we have focused on the l e a r n i n g l e v e l that they pass through as they l e a r n the assignment- statement. We f e e l that i n the l e a r n i n g of any new t o p i c , d i f f i c u l t i e s in the form of misconceptions do a r i s e , and i f the sources of the misconceptions are i n c o r r e c t mental models, a good a i d to l e a r n i n g i s to provide c o r r e c t e x p l i c i t models. A good t u t o r should adopt a teaching s t r a t e g y that a n t i c i p a t e s the kinds of misconceptions that can a r i s e and a i d s the f o r m u l a t i o n of c o r r e c t mental models. By choosing a narrow knowledge domain f o r our i n s t r u c t i o n a l program, we have avoided many d i f f i c u l t c o nceptual questions and assumptions that have a r i s e n i n the design of ICAL systems of much g r e a t e r s o p h i s t i c a t i o n . The design of CATEA i s o s t e n s i b l y simple. In order to extend CATEA to be able to understand and debug programming f e a t u r e s beyond the assignment statement, such as l o o p i n g c o n s t r u c t s , more s o p h i s t i c a t e d methods are needed. N e v e r t h e l e s s , we b e l i e v e that CATEA i s a demonstration of the p o t e n t i a l t u t o r i a l s k i l l which ICAL systems can manifest. In sum, we have w r i t t e n an ICAT program which diagnoses a student's i n c o r r e c t program by s i m u l a t i n g enumerated bugs in the program and observing which bug e x p l a i n s i t s s u r f a c e behaviour. An e m p i r i c a l study of CATEA shows that i t was a b l e to r e a l i s e 71 the o b j e c t i v e of d i a g n o s i n g m i s c o n c e p t i o n s i n a s t u d e n t ' s u n d e r s t a n d i n g of the assignment s t a t e m e n t . 72 R e f e r e n c e s A b e l s o n , H. & d i S e s s a , A. 1981. T u r t l e Geometry j_ The computer  as a medium f o r e x p l o r i n g mathematics. Cambridge, Mass. : MIT P r e s s . B a r r , A. & Feigenbaum, E. A. (eds) 1982. The Handbook of A I .  Volume 2. W i l l i a m Kaufmann, I n c . Bayman, P. & Mayer, R. E. 1983. A D i a g n o s i s of B e g i n n i n g  Programmers' M i s c o n c e p t i o n s of BASIC Programming Statements. Sept 1983, CACM, V o l 26 No 9, 677-679. B o r i c h , G. D. & Je m e l k a , R. P. 1981. E v a l u a t i o n . In O ' N e i l , H.F. J r . ( e d ) , CBI. A S t a t e - o f - t h e - A r t Assessment. Academic P r e s s , 1981. B o r n i n g , A. H. 1979. T h i n g l a b ^ h. c o n s t r a i n t - o r i e n t e d s i m u l a t e d  l a b o r a t o r y . Ph. D. T h e s i s , S t a n f o r d U n i v e r s i t y . B o u l a y , B. Du & O'Shea, T. Te a c h i n g N o v i c e s Programming. In M. J . Coombs & J . L. A l t y ( e d s ) , Computing S k i l l s and the User  I n t e r f a c e . Academic P r e s s , 1981. Brown, J . S., R u b i n s t e i n , R & B u r t o n , R. 1976. A r e a c t i v e  l e a r n i n g e n v i ronment f o r 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 . BBN r e p o r t No. 3314, Cambridge, M a s s a c h u s s e t t s . Brown, J . S. & B u r t o n , R. R. 1975. M u l t i p l e r e p r e s e n t a t i o n s of knowledge f o r t u t o r i a l r e a s o n i n g . In D.G. Bobrow & A. C o l l i n s ( e d s ) , R e p r e s e n t a t i o n and U n d e r s t a n d i n g , Academic P r e s s , 1975. Brown, J . S. & B u r t o n , R. R. 1977. A p a r a d i g m a t i c example of an  AI i n s t r u c t i o n a l system. F i r s t I n t e r n a t i o n a l Conference on A p p l i e d Systems R e s e a r c h , New York , 1977. Brown, J . S. & B u r t o n , R. R. 1978. 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 . C o g n i t i v e  S c i e n c e 2 ( 2 ) , 1978, 155-192. Brown, J . S. & Sleeman, D. H. 1981. I n t e l l i g e n t T u t o r i n g  Systems. Academic P r e s s , 1981. Brown, J . S. & V a n l e h n , K. 1980. R e p a i r t h e o r y : A g e n e r a t i v e t h e o r y of 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 . C o g n i t i v e S c i e n c e 4 ( 4 ) , 1980, 379-426. B u r t o n , R. R. & Brown, J . S. An i n v e s t i g a t i o n of computer c o a c h i n g f o r i n f o r m a l l e a r n i n g a c t i v i t i e s . The I n t e r n a t i o n a l  J o u r n a l of Man-Machine S t u d i e s , 11, 1979, 5-24. B u r t o n , R. R. 1981. DEBUGGY : D i a g n o s t i c of e r r o r s 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 . In D. H. Sleeman & J . S. Brown (eds) 73 I n t e l l i g e n t T u t o r i n g Systems, Academic P r e s s , 1981. C a r b o n e l l , J . R. 1969. I n t e r a c t i v e n o n - d e t e r m i n i s t i c CAI. I n t e r n a t i o n a l Symposium on Man-Machine Systems, 1969. C a r b o n e l l , J . R. 1970. M i x e d - i n i t i a t i v e man-computer  i n s t r u c t i o n a l d i a l o g u e s . T e c h n i c a l Report 1970, BBN, 1970. C a r r , B. & G o l d s t e i n , I . 1977. O v e r l a y s j_ A t h e o r y of m o d e l l i n g  f o r CAI. A l Memo 406, MIT, 1977. C a r t w r i g h t , G. F. & Derevensky, J . L. 1976. ICAT ±_ A f e a s i b i l i t y  p aper. Paper p r e s e n t e d a t the Annual Conference of the Canadian E d u c a t i o n a l Research A s s o c i a t i o n . L a v a l U n i v e r s i t y , Quebec. C l a n c e y , W. J . 1979a. T u t o r i n g r u l e s f o r g u i d i n g a case method d i a l o g u e . The I n t e r n a t i o n a l J o u r n a l of Man-Machine S t u d i e s 11, 1979, 25-49. C l a n c e y , W. J . 1979b. D i a l o g u e management f o r r u l e - b a s e d t u t o r i a l s . In P r o c e e d i n g s of the S i x t h I J C A I , 1979. C l a n c e y , W. J . 1979c. T r a n s f e r of r u l e - b a s e d e x p e r t i s e t h r o u g h a t u t o r i a l d i a l o g u e . Ph. D. T h e s i s . STAN-CS-769, S t a n f o r d U n i v e r s i t y , 1979. C l a n c e y , W. J . 1981. Methodology f o r b u i l d i n g an i n t e l l i g e n t  t u t o r i n g system. STAN-CS-81-894, S t a n f o r d U n i v e r s i t y , 1981. C l a n c e y , W. J . & Buchanan, B. 1982. E x p l o r a t i o n of t e a c h i n g and  p r o b l e m - s o l v i n g s t r a t e g i e s , 1979-1982. STAN-CS-82-910, S t a n f o r d U n i v e r s i t y , 1982. C o l b y , K.M. 1973. S i m u l a t i o n s of b e l i e f systems. In C o l b y , K.M. & e t a l ( e d s ) , Computer Models of Thought and Language. San F r a n c i s c o . C o l l i n s , A. 1977. P r o c e s s e s i n a c q u i r i n g knowledge. In R.C. Anderson & e t a l ( e d s ) , S c h o o l i n g and the a c q u i s i t i o n of  knowledge, Erlbaum A s s o c i a t e s , 1977. D a v i e , A. J . T. R e c u r s i v e Descent C o m p i l i n g . John W i l e y & Sons, 1981. Durham, I . , Lamb, D. A. & Saxe, J . B. 1983. S p e l l i n g C o r r e c t i o n i n User I n t e r f a c e s . CACM, Oct. 1983, V o l 26, No 10. F e u r z e i g , W. & P a p e r t , S & et a l , 1969. Programming languages as a c o n c e p t u a l framework f o r t e a c h i n g mathematics, Volumes 1 t o 4, BBN, Cambridge. F i e l d e n , J . 1977. The f i n a n c i a l e v a l u a t i o n of NDPCAL. B r i t i s h  J o u r n a l of E d u c a t i o n a l Technology, 8, 190-200. Ga b l e , A. & Page, C. V., 1980. The use of A l t e c h n i q u e s i n CAI : 74 an o v e r v i e w . The I n t e r n a t i o n a l J o u r n a l of Man-Machine  S t u d i e s , 12, 1980. G e n e s e r e t h , M. 1981. The r o l e of p l a n s i n ITS. In D. H. Sleeman & J . S. Brown ( e d s ) , I n t e l l i g e n t T u t o r i n g Systems, Academic P r e s s . Grogono, P. 1980. Programming i n P a s c a l . Addison-Wesley, 1980. J o n i , S.-N., Soloway, E. et a l , 1983. J u s t so s t o r i e s j_ How the  program got t h a t bug. SIGCUE B u l l e t i n , F a l l 1983. Howe, J . A. M. 1978. AI and CAI : Ten y e a r s on. In N. Rushby ( e d ) , S e l e c t e d Readings i n CAL, Kogan Page, 1981. Howe, J . A. M 1979. L e a r n i n g t h r o u g h m o d e l - b u i l d i n g . In D. M i t c h i e ( e d ) , E x p e r t Systems i n the M i c r o e l e c t r o n i c Age. E d i n b u r g h P r e s s . Kay, A. C. 1977. M i c r o e l e c t r o n i c s & the p e r s o n a l computer. Sc i e n t i f i c Amer i c a n , 237. K e h l e r , T. 1982. F u t u r e d i r e c t i o n s f o r C o m p u t e r - a s s i s t e d e d u c a t i o n . In C. Hernandez-Logan & M. Lewis ( e d s ) , Computer  Support f o r E d u c a t i o n . R & E R esearch A s s o c i a t e s . 1982. K i m b a l l , R. B. 1973. S e l f - o p t i m i z i n g c o m p u t e r - a s s i s t e d t u t o r i n g .  Theory & P r a c t i c e . T e c h n i c a l Report 206. 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 the S o c i a l S c i e n c e s , S t a n f o r d U n i v e r s i t y . O'Shea, Tim 1979. S e l f - i m p r o v i n g t e a c h i n g systems. Ph. D. T h e s i s , B i r k h a u s e r , 1981. O'Shin, L. 1980. CAI i n I s r a e l i d i sadvantaged elementary  s c h o o l s . C e n t r e f o r E d u c a t i o n a l Technology, Ramat A v i v , 1 980. P a p e r t , S. 1971. ' T e a c h i n g c h i l d r e n t h i n k i n g . MIT AI Lab Memo 247, 1971. P a p e r t , S. 1980. Mindstorms. C h i l d r e n , Computers and P o w e r f u l  T o o l s . B a s i c Books, 1980. Pugh, J . & Simpson, D. 1979. P a s c a l e r r o r s - e m p i r i c a l e v i d e n c e . Computer B u l l e t i n , 2, 26-28. R e s n i c k , L. B. 1977. H o l d i n g an i n s t r u c t i o n a l c o n v e r s a t i o n . In R.C. Anderson & e t a l ( e d s ) , S c h o o l i n g and the A c q u i s i t i o n  of Knowledge , Erlbaum A s s o c i a t e s , 197 7 1 R i p l e y , G. D. & D r u s e i k i s , F. C. 1978. S t a t i s t i c a l a n a l y s i s of s y n t a x e r r o r s . Computer Languages, 3, 227-240. Schank, R. & A b e l s o n , R. S c r i p t s , P l a n s , G o a l s and  U n d e r s t a n d i n g . Erlbaum A s s o c i a t e s , 1977. 75 S e l f , J . A. 1974. Student models i n CAI. The I n t e r n a t i o n a l  J o u r n a l of Man-Machine S t u d i e s 6, 1974. Sleeman, D. H. & Smith, M. J . 1981. M o d e l l i n g s t u d e n t ' s problem- s o l v i n g , A l 16. Sleeman, D. H. 1975. A p r o b l e m - s o l v i n g m o n i t o r f o r d e d u c t i v e r e a s o n i n g t a s k s . The I n t e r n a t i o n a l J o u r n a l of Man-Machine  S t u d i e s 7, 1975, 183-212. Smallwood, R. D. 1 962. A dec i s i o n s t r u c t u r e f o r t e a c h i n g  machines, Cambridge, M a s s a c h u s s e t t s : MIT P r e s s . Soloway, E., Lockhead, J . & Clement, J . Does computer programming enhances problem s o l v i n g a b i l i t y ? Some p o s i t i v e e v i d e n c e on a l g e b r a word problems. In R. S e i d e l , R. Anderson & B. Hunter ( e d s ) , Computer L i t e r a c y , Academic P r e s s , 1982. Soloway, E., E h r l i c h , K., et a l , 1982. What do n o v i c e s know about programming? In A. Badre & B. Shneiderman ( e d s ) , D i r e c t i o n s i n Human/Computer I n t e r a c t i o n , 1982. Soloway, E., Woolf, B. , et a l . MENO-II : An i n t e l l i g e n t t u t o r i n g system f o r n o v i c e programmers. I J C A I , 1981. S t a t z , J . 1973. P r o b l e m - s o l v i n g i n LOGO. Syracuse U n i v e r s i t y LOGO P r o j e c t , New York. Suppes, P. 1967. Some t h e o r e t i c a l models f o r Mathematics L e a r n i n g . J o u r n a l of Research & Development i n E d u c a t i o n , 1. S t a n s f i e l d , J . L. 1974. Programming a d i a l o g u e t e a c h i n g  s i t u a t i o n . Ph. D. T h e s i s , S c h o o l of A l , U n i v e r s i t y of Edi n b u r g h : Ed i n b u r g h ( 8 ) . T u r n e r , D. A. 1977. E r r o r d i a g n o s i s & r e c o v e r y i n one-pass computers, I n f o r m a t i o n P r o c e s s i n g L e t t e r s , Aug 1977, 6, 4, 113-115. Uhr L. 1969. T e a c h i n g machine programs t h a t g e n e r a t e problems as a f u n c t i o n of i n t e r a c t i o n w i t h s t u d e n t s . P r o c e e d i n g s of 24th  ACM N a t i o n a l Conference ( 8 ) . W i l c o x , B. & H a f e r , C. 1974. LISP/MTS U s e r ' s G u i d e , M e n t a l H e a l t h R e s e a r c h I n s t i t u t e , Ann Ar b o u r , 1974. Woods, P. & H a r t l e y , J . R. 1971.- Some l e a r n i n g models f o r a r i t h m e t i c t a s k s and t h e i r use i n CAL. B r i t i s h J o u r n a l of  E d u c a t i o n a l P s y c h o l o g y , 41, 1, 1971. Va n l e h n , K. & F r i e n d , J . 1980. R e s u l t s from DEBUGGY : An a n a l y s i s of s y s t e m a t i c s u b t r a c t i o n e r r o r s . Xerox P a l o A l t o  Sc i e n c e C e n t e r T e c h n i c a l R e p o r t , 1980. Venezky, R. L. E v a l u a t i n g CAI on i t s own terms. In A.C. W i l k i n s o n ( e d ) , C l a s s r o o m Computers and C o g n i t i v e S c i e n c e , 76 Academic P r e s s , 1983. Z i n n , K. L. 1978. An overview the US. In N. Rushby ( e d ) , Page, 1981. of c u r r e n t developments i n CAL i n S e l e c t e d Readings i n CAL, Kogan 77 Appendix A : How Programming i n P a s c a l (Grogono, 1980) p r e s e n t s the Assignment Statement An assignment statement has the form v a r i a b l e := e x p r e s s i o n The assignment statement i s asymmetric : r i g h t hand operand answers the q u e s t i o n 'what i s the v a l u e ? ' and the l e f t hand s i d e answers the q u e s t i o n 'to what v a l u e i s t h i s v a l u e t o be g i v e n ? ' I t i s p o s s i b l e t o w r i t e assignments s t a t e m e n t s such as f i r s t n u m b e r := 1 c i r c u m f e r e n c e := 2 * p i * r a d i u s and even nextnumber := nextnumber + 1 which has the e f f e c t of i n c r e a s i n g the v a l u e of nextnumber by 1. I t i s not m e a n i n g f u l , however, t o w r i t e s t a t e m e n t s l i k e 1 := f i r s t n u m b e r l e n g t h * w i d t h := a r e a because the l e f t hand s i d e s of t h e s e s t a t e m e n t s cannot be i n t e r p r e t e d as a d e s t i n a t i o n f o r a v a l u e . 78 Appendix B : How L e c t u r e S l i d e s used i n CPSC 114 p r e s e n t the Assignment Statement ASSIGNMENT The a c t i o n of ch a n g i n g the v a l u e of ( i . e . " c o n t a i n e d by") a var i a b l e . T h i s a c t i o n i s s p e c i f i e d , i n P a s c a l by an assignment s t a t e m e n t . FORM : v a r i a b l e := e x p r e s s i o n ACTION : The v a l u e of ' e x p r e s s i o n ' i s computed and becomes the new v a l u e of ' v a r i a b l e ' ( r e p l a c i n g any former v a l u e ) . Once a v a l u e i s a s s i g n e d t o a v a r i a b l e , i t r e t a i n s t h a t v a l u e u n t i l a nother v a l u e i s a s s i g n e d t o i t i n a subsequent s t e p of the program. E x p r e s s i o n s may c o n t a i n v a r i a b l e s as w e l l as c o n s t a n t v a l u e s . The v a l u e r e p r e s e n t e d by a v a r i a b l e i s the v a l u e most r e c e n t l y a s s i g n e d t o i t . Notes • V a r i a b l e s don't remember p r e v i o u s v a l u e s • Read "a := 3" as "a becomes 3", or "a g e t s the v a l u e 3"; don't read i t as "a e q u a l s 3". Examples 1 ) a : = 3 ; B e f o r e A f t e r 2) x : = x + 1 ; B e f o r e A f t e r x 82 x 83 ( f r y "x := x + 1" on a m a t h e m a t i c i a n !) Note x := y and y := x have d i f f e r e n t e f f e c t s , 80 Appendix C : The D i a g n o s t i c Loop i l l u s t r a t e d by t r a c i n g a s t u d e n t ' s s e s s i o n as he a t t e m p t s Problem 3 The f o l l o w i n g i s p a r t of an a c t u a l s t u d e n t ' s s e s s i o n p r o t o c o l a n n o t a t e d w i t h e x p l a n a t o r y n o t e s , which can be d i s t i n g u i s h e d by a 'C as the f i r s t c h a r a c t e r of t h e i r l i n e s . CATEA prompts i n p u t from the s t u d e n t w i t h a '*' > > Choose one of the f o l l o w i n g : > > (1) P l e a s e d i s p l a y r e s t r i c t i o n s of the P a s c a l c o m p i l e r . > > (2) Try Problem 2 a g a i n f o r more p r a c t i c e . > > (3) Proceed d i r e c t l y t o the next problem. > > E n t e r 1,2 or 3 : *3 > > Programming Assignment 3 > > W r i t e a P a s c a l program t h a t does the f o l l o w i n g > (1) D e c l a r e P, Q as i n t e g e r v a r i a b l e s > (2) Read i n the v a l u e of P u s i n g READ ( P ) ; > (3) Read i n the v a l u e of Q > (4) Now, exchange the v a l u e s of P and Q > (5) W r i t e out the v a l u e s of P and Q > > Now, e n t e r your P a s c a l program : > *PROGRAM TIRED; * VAR * P,Q :INTEGER; * BEGIN * READ (P,Q); * Q :=P; * P :=Q; * WRITE (P,Q); * END. C C CATEA w i l l attempt t o c o m p i l e the program. C I f t h e r e a r e u n r e c o v e r a b l e s y n t a x e r r o r s , C i t w i l l prompt the s t u d e n t t o r e - e n t e r the program. C I f a s t u d e n t s t i l l can not type i n a program f r e e of s y n t a x C e r r o r s a f t e r s i x a t t e m p t s , CATEA w i l l ask i f he wants t o g i v e C up and be p r o v i d e d w i t h the s o l u t i o n . C > S t a r t of C o m p i l a t i o n . > PROGRAM TIRED; > VAR > P,Q :INTEGER; > B E G I N > READ ( P , Q ) ; > Q : = P ; > P :=Q; > WRITE ( P , Q ) ; > E N D . > > No e r r o r d e t e c t e d . > E n d o f C o m p i l a t i o n . > Do y o u w a n t t o make a n y m o r e c h a n g e s t o y o u r p r o g r a m ? > To make c h a n g e s , y o u h a v e t o e n t e r t h e p r o g r a m a g a i n . > E n t e r Y o r N : *N > > To c o n t i n u e , h i t a n y k e y a n d t h e n t h e <RETURN> k e y . *x C C A s t h e s t u d e n t ' s p r o g r a m i s s y n t a c t i c a l l y c o r r e c t , . C CATEA p r o c e e d s t o e x e c u t e i t . C > > S t a r t o f E x e c u t i o n . > E x e c u t i n g READ ( P , Q ) ; > E n t e r i n p u t v a l u e f o r P > * 5 > E n t e r i n p u t v a l u e f o r Q > *8 > E x e c u t i n g Q := P ; > E x e c u t i n g P := Q ; > E x e c u t i n g WRITE ( P , Q ) ; > P r o g r a m w i l l p r i n t : > 5 5 > E n d o f E x e c u t i o n . > C C CATEA r e a l i z e s t h a t a s P a n d Q h a v e n o t s w a p p e d v a r i a b l e s , C t h e s t u d e n t ' s p r o g r a m i s i n c o r r e c t . C I t w i l l t h e n i n v o k e i t s d i a g n o s t i c m o d e l t o f i n d o u t w h i c h C o f i t s s t o r e d b u g s c a n e x p l a i n t h e s u r f a c e b e h a v i o u r o f t h e C s t u d e n t ' s p r o g r a m . C > > Y o u r p r o g r a m d o e s n ' t w o r k a s r e q u i r e d . > Do y o u know w h a t ' s w r o n g w i t h y o u r p r o g r a m ? > > To c o n t i n u e , h i t a n y k e y a n d t h e n t h e <RETURN> k e y . *x > C C CATEA p o i n t s o u t w h e r e t h e s t u d e n t ' s p r o g r a m i s w r o n g . C > > P h a s NOT a t t a i n e d t h e v a l u e o f Q , n a m e l y , 8 > > To c o n t i n u e , h i t a n y k e y a n d t h e n t h e <RETURN> k e y . 82 > C C c c c c > > > > > > > > > > > > > > > > > > > > > > > > *} > > > > > > > > > > > > > > > > > > > > > > > CATEA was a b l e t o d i a g n o s e t h e bug as i t s t h i r d s t o r e d e n u m e r a t e d bug. I t p r i n t s out a b l o c k o f r e m e d i a l a d v i c e ( p r e s t o r e d f o r e a c h bug) w h i c h i s most o f t e n an example f o l l o w e d by some d i s c u s s i o n , as i n t h i s c a s e . R e m e d i a l A d v i c e Look a t t h e f o l l o w i n g a s s i g n m e n t s t a t e m e n t s Q := 2 p u t s P : = p := i ; Q := 2; P := Q; Q := P; 1 i n t o 2 i n t o p Q Q p u t s t h e v a l u e of Q, t h a t i s , 2 i n t o P. P and Q b o t h has t h e v a l u e 2. Note t h a t P := Q d e s t r o y s t h e o l d v a l u e o f P, namely, 1. To r e t a i n t h i s o l d v a l u e of P, we need a THIRD v a r i a b l e . Q := P p u t s t h e v a l u e of P, t h a t i s , 2 i n t o Q. BOTH P and Q have t h e v a l u e 2. To c o n t i n u e , h i t any key and t h e n t h e <RETURN> key, L e t me g i v e you a t e s t t o see i f you have a b e t t e r u n d e r s t a n d i n g . Q u e s t i o n C o n s i d e r t h e f o l l o w i n g p r o g ram PROGRAM QUIZ; CONST A=TRUE; B=FALSE; VAR X, Y : BOOLEAN; BEGIN X := A; Y := B; X := Y; Y := X; WRITE (X, Y) END. What g e t s p r i n t e d ? { 1 } FALSE FALSE {2} FALSE TRUE {3} TRUE FALSE 83 > {4} TRUE TRUE > Type i n your answer ( 1 , 2, 3 or 4) : *2 > That'S WRONG. > The answer i s 1 > C C I f the s t u d e n t ' s answer i s c o r r e c t , CATEA w i l l t a k e i t t h a t C the s t u d e n t has become aware of the bug and proceed t o the C next problem or a l l o w the s t u d e n t t o r e t r y the same problem. C C CATEA g i v e s the s t u d e n t the c h o i c e of t r y i n g a n o ther t e s t or C s e e k i n g more a d v i c e . C > Choose one of the f o l l o w i n g by e n t e r i n g 1 or 2 : > {1} More a d v i c e > {2} Try a n o t h e r t e s t > > Now, e n t e r 1 or 2 : *1 > > Remedial A d v i c e > To exchange the v a l u e s of 2 v a r i a b l e s P and Q, > we use a t h i r d v a r i a b l e R i n the f o l l o w i n g way : > R := P; > P := Q; > Q := R; > > R i s used t o s t o r e the v a l u e of P, > so t h a t P can then get the v a l u e of Q. > A f t e r t h a t , Q g e t s the v a l u e of R, > which i s the o r i g i n a l v a l u e of P. > > Can you observe t h a t P and Q have exchanged v a l u e s ? > > > To c o n t i n u e , h i t any key and then the <RETURN> key. *x > C C CATEA g i v e s a n o t h e r t e s t t o f i n d out i f the s t u d e n t has become C aware of the bug i n h i s program. -C > > Q u e s t i o n > ======== > C o n s i d e r the f o l l o w i n g program ': > PROGRAM QUIZ; > CONST A=2; > B=4; > VAR P, Q, R : INTEGER; > BEGIN > P := A; > Q := B; > R := P; 84 > P := Q; > Q : = R; > WRITE (P, Q) > END. > > What l i n e of output g e t s p r i n t e d ? > {1 } 4 4 > {2} 2 2 > (3} 2 4 > {4} 4 2 > Type i n your answer ( 1 , 2, 3 or 4) : *4 > Tha t ' s RIGHT. > L e t ' s proceed t o the next problem. > C C T h i s ends the d i a g n o s t i c l o o p . C I f the s t u d e n t ' s program answer i s wrong, t h a t i s , C he has f a i l e d t o do the two m u l t i p l e - c h o i c e t e s t s c o r r e c t l y , C CATEA w i l l end the d i a g n o s t i c l o o p w i t h a warning t h a t he has C y e t t o c o r r e c t h i s m i s c o n c e p t i o n and a d v i s e s him t o t r y o t h e r C r e m e d i a l s o u r c e s . C > To c o n t i n u e , h i t any key and then the <RETURN> key. *x > > > Choose one of the f o l l o w i n g : > " > (1) P l e a s e d i s p l a y r e s t r i c t i o n s of the P a s c a l c o m p i l e r . > > (2) Try Problem 3 a g a i n f o r more p r a c t i c e . > > (3) Proceed d i r e c t l y t o the next problem. > > E n t e r 1,2 or 3 : 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items