UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Teaching Prolog using intelligent computer-assisted instruction and a graphical trace Fogel, Earl 1988

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

Item Metadata

Download

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

Full Text

TEACHING PROLOG USING INTELLIGENT COMPUTER-ASSISTED INSTRUCTION AND A GRAPHICAL TRACE by EARL FOGEL B.Sc. U n i v e r s i t y of Saskatchewan, 1980 Bachelor of Journalism, C a r l e t o n U n i v e r s i t y , 1982 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF COMPUTER SCIENCE We accept t h i s t h e s i s as conforming to the re q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA February, 1988 (c) E a r l Fogel, 1988 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date Afif'il 8J M M DE-6(3/81) A b s t r a c t Two methods f o r improving the q u a l i t y of Computer A s s i s t e d I n s t r u c t i o n are examined. They a r e : u s i n g I n t e l l i g e n t Computer A s s i s t e d I n s t r u c t i o n t e c h n i q u e s to make the CAI system more f l e x i b l e , and u s i n g g r a p h i c s t o i n c r e a s e the e f f i c a c y of t e a c h i n g . Two computer systems f o r t e a c h i n g the L o g i c Programming language P r o l o g were developed. The f i r s t i s an ICAI system which uses the p r e r e q u i s i t e r e l a t i o n s h i p s of the course m a t e r i a l t o p l a n a c o u r s e of s t u d y . I t d i s t i n g u i s h e s between methods of i n s t r u c t i o n and t o p i c s of i n s t r u c t i o n , g i v i n g s t u d e n t s a g r e a t d e a l of freedom i n choosing e i t h e r one. The second i s an animated t r a c e which g r a p h i c a l l y i l l u s t r a t e s the e x e c u t i o n of P r o l o g programs. I n f o r m a t i o n i s d i s p l a y e d i n t h r e e windows — one f o r P r o l o g g o a l s , one f o r the database, and one f o r output from the program b e i n g t r a c e d . R e s u l t s i n d i c a t e t h a t ICAI and g r a p h i c s can both be used e f f e c t i v e l y i n the t e a c h i n g of programming languages, p a r t i c u l a r l y i n c o m b i n a t i o n . TABLE OF CONTENTS Chapter One - In t r o d u c t i o n 1 1.1. Why Computers are Such T e r r i b l e Teachers 1 1.2. Why Computers are Such Good Teachers 2 1.3. Making Computers i n t o Better Teachers 3 1.4. Teaching Programming Languages 6 1.5. Teaching Prolog 7 1.6. T h i s Thesis 8 1.7. The Prolog ICAI System 8 1.8. The Animated Trace (Anilog) 10 1.9. Sample P r o t o c o l s 11 Chapter Two - L i t e r a t u r e Survey 16 2.1. Using More I n t e l l i g e n t Teachers 17 2.2. Broadened I n t e r a c t i o n s between Teacher, Student and Domain 26 2.3. Summing up the L i t e r a t u r e 28 Chapter Three - Prolog ICAI System Design 31 3.1. Design Goals 31 3.2. General Design 32 3.3. Methods of I n s t r u c t i o n 34 3.4. The P r e r e q u i s i t e S t r u c t u r e 36 3.5. Choosing a Topic of I n s t r u c t i o n 38 3.6. Choosing a Method of I n s t r u c t i o n 39 3.7. Deciding Which Topics are P r e v i o u s l y Known 40 3.8. Notes on I n s t r u c t i o n a l Methodology 41 3.9. The Implementation 41 Chapter Four - Animated Trace Design 43 4.1. I n t r o d u c t i o n 43 4.2. General Design 44 4.3. The Trace 44 4.4. The Animated Display 45 4.5. The Implementation 46 Chapter F i v e - E v a l u a t i o n and Conclusions 48 5.1. Prolog ICAI System: E v a l u a t i o n Procedure 48 5.2. The Animated Trace: E v a l u a t i o n Procedure 50 5.3. Prolog ICAI System: E v a l u a t i o n Results 51 5.4. The Animated Trace: E v a l u a t i o n Results 54 5.5. Conclusions 55 B i b l i o g r a p h y 58 Appendix One - The And/Or P r e r e q u i s i t e Tree 62 Appendix Two - Prolog CAI User's Manual 64 Appendix Three - A n i l o g User's Manual 65 Appendix Four - Animated Trace Example 66 - i i i -L i s t of F igures F i g u r e 1: Example of an And/Or P r e r e q u i s i t e Tree 9 F i g u r e 2: The S t a r t of the Prolog ICAI Course 12 F i g u r e 3: The F i r s t Topic S e l e c t e d 13 F i g u r e 4: The F i r s t Lesson Se l e c t e d 14 F i g u r e 5: Snapshot of the Prolog Animated Trace 15 F i g u r e 6: Prolog ICAI System Design 33 F i g u r e 7: Prolog ICAI E v a l u a t i o n Questionnaire 49 - i v -Acknowledgements The author would l i k e t o thank everyone who t r i e d out the two systems and gave a d v i c e d u r i n g t h e i r development. Many of the idea s f o r t e a c h i n g P r o l o g came from the e x c e l l e n t P r o l o g courses g i v e n by Ray R e i t e r and Harvey Abramson a t UBC, from the Programming i n P r o l o g t e x t by C l o c k s i n and M e l l i s h , and from the CP r o l o g Users Manual by Fernando P e r e i r a et a l . A l a n Mackworth, who s u p e r v i s e d t h i s r e s e a r c h , c o n t r i b u t e d l e a d s t o much of the ICAI l i t e r a t u r e and, w i t h g r e a t p e r s e v e r a n c e , convinced me of the advantages of g r a p h i c s i n t e a c h i n g programming languages. R i c h a r d Rosenberg has o f f e r e d some v a l u a b l e a d v i c e f o r the f i n a l d r a f t of t h i s t h e s i s , and h i s a s s i s t a n c e i s s i n c e r e l y a p p r e c i a t e d . F i n a n c i a l support f o r t h i s r e s e a r c h was p r o v i d e d by the N a t u r a l S c i e n c e s and E n g i n e e r i n g Research C o u n c i l of Canada. -v-Chapter One I n t r o d u c t i o n For more than 20 years, people have been w r i t i n g Computer Aided I n s t r u c t i o n (CAI) programs. Most of them are not very good. H o f s t e t t e r (1981) estimates that as many as 5000 out of the 7000 hours of i n s t r u c t i o n a l software w r i t t e n f o r P l a t o are u s e l e s s , yet P l a t o i s described as one of the most s u c c e s s f u l CAI systems. This chapter w i l l show why computers are such poor teachers, and w i l l put forward some ideas about what can be done to improve them. Two computer systems that i l l u s t r a t e these ideas w i l l then be described. 1.1 Why Computers are Such T e r r i b l e Teachers Consider the f o l l o w i n g locked room analogy. Imagine you are s i t t i n g a l l alone i n a locked, soundproof room, with nothing but a t y p e w r i t e r , some paper, and a book. On one w a l l of the room are two s l o t s , l a b e l l e d In and Out. Your job i s to teach the contents of that book to anyone who happens to be on the other s i d e of the w a l l , by passing notes through these s l o t s . You can know nothing about the subject of the book, you must give up most of your command of the language i n which i t i s w r i t t e n (and which the students use), and you must forget everything you know about teaching. (After Searle 1983). Under the circumstances, i t would be d i f f i c u l t f o r anyone to teach e f f e c t i v e l y , yet these are p r e c i s e l y the c o n d i t i o n s under which most CAI programs operate. -1-Knowing nothing about the subject they teach, they can only present the student with p r e v i o u s l y w r i t t e n pages of t e x t . Knowing nothing about the student, they cannot t a i l o r t h e i r p r e s e n t a t i o n to h i s or her needs. Knowing nothing about teaching, they are unable to vary t h e i r teaching s t r a t e g i e s to best s u i t a p a r t i c u l a r t o p i c or a p a r t i c u l a r student. Further, the only contact most CAI programs have with the r e a l world i s through the t e r m i n a l screen and keyboard. Students cannot pick up v i s u a l or voice-tone cues from the program, nor can i t pick up such cues from them. In summary, a t y p i c a l CAI program does not understand what i t i s teaching, who i t i s teaching, or how to teach. With these handicaps, i t i s no wonder computers are such poor teachers. In f a c t , i t i s a wonder they are as good as they are. 1.2 Why Computers are Such Good Teachers There are good CAI programs. There are, f o r example, about 2000 hours of P l a t o courseware (educational software) that H o f s t e t t e r d i d not dismiss as u s e l e s s . Some CAI programs succeed because t h e i r s u b j e c t s are e s p e c i a l l y w e l l s u i t e d to computer i n s t r u c t i o n . A few years ago, one study found that "95% are a r i t h m e t i c programs" (Ragsdale 1982). Much of CAI focuses on a r i t h m e t i c because a r i t h m e t i c i s easy to teach with computers. I t i s easy because computers can do a r i t h m e t i c , and students can watch them doing i t . -2-Indeed, a computer can help a student with a r i t h m e t i c , and can compare the student's answers with i t s own. Another promising subject for CAI i s computer programming. In t h i s area too, the computer can check the student's answers against i t s own. Looi has w r i t t e n a program which teaches the Pascal assignment statement (Looi 1984). His system checks the syntax of simple programs w r i t t e n by the student, runs them on predetermined t e s t cases, and v e r i f i e s the r e s u l t s . Other CAI programs succeed because they use s i m u l a t i o n s . With these, the student learns about a real- w o r l d system by experimenting with a model of that system. The models i n c l u d e economic systems, with the student p l a y i n g the stock market or running a T h i r d World country; or b i o l o g i c a l systems, showing population changes i n f i s h or b a c t e r i a . These programs a l l have one thing i n common competence i n t h e i r domain of e x p e r t i s e . They are unable to reason about t h e i r domain, nor can they e x p l a i n i t , but there i s enough domain knowledge b u i l t i n t o these programs that they can perform competently w i t h i n i t . Going back to the locked room analogy, these programs are s u c c e s s f u l because they know something about the subjects they are teaching. 1.3 Making Computers i n t o Better Teachers E f f o r t s to make computers be t t e r teachers can be c l a s s i f i e d i n t o two c a t e g o r i e s : * Allowing a broader spectrum of i n t e r a c t i o n s with the outs i d e world (unlocking the room). - 3 -* Improving t h e i r i n t e l l i g e n c e and t h e i r knowledge of the world (putting someone i n the room who knows the student, who knows the subject being taught, and who knows how to teach). 1.3.1 Unlocking the Room This i n v o l v e s breaking down the b a r r i e r s both between the teacher and student, and between the teacher and the subj e c t being taught. Human teachers can t a l k , gesture, draw p i c t u r e s , show movies and use computers to put ideas across, while students can t a l k , groan, s c r a t c h t h e i r heads, and so on. In the most b a s i c form of CAI, on the other hand, the only means of communication i s t e x t , typed at the keyboard and d i s p l a y e d on the screen. The use of l i g h t pens, touch s e n s i t i v e screens, s l i d e p r o j e c t o r s , videotapes, speech s y n t h e s i s and g r a p h i c a l d i s p l a y s can a l l e n r i c h t h i s i n t e r a c t i o n . One can a l s o e n r i c h the i n t e r a c t i o n between the computer and the subject i t teaches. A human teacher o f t e n has perso n a l experience with the subject being taught, and can support the lessons with r e a l world demonstrations. He or she can turn over a l e a f , or open up the hood of a car. I t i s e a s i e r to teach about t r e e s , f o r example, i f you know something about t r e e s , and i f you can point to a t r e e while you t a l k . Computers are good a r i t h m e t i c teachers because they can show the student how to do a r i t h m e t i c , and can check the student's work against t h e i r own. -4-One way to teach about a domain with which you can't i n t e r a c t i s given by Alan Bundy's notion of " s t o r i e s " . A s t o r y i s a model or an analogy which makes i t easy to grasp the c e n t r a l ideas behind the subject being taught. Learning i s much e a s i e r with a good s t o r y . Here, Bundy writes about s t o r i e s f o r teaching programming languages: [ I t ] i s important to give a model of what the computer w i l l do with his/her programs. The student must be able to a n t i c i p a t e the e f f e c t of running his/her program, otherwise he/she w i l l be unable to design i t , debug i t , modify i t , e t c . ... When teaching LOGO to school c h i l d r e n , Tim O'Shea and Ben du Boulay found the p r o v i s i o n of a s u i t a b l e model to be c e n t r a l to the design of the course and the language i n t e r f a c e (Bundy, 1983). In teaching about t u r t l e graphics, one has the analogy of l i v e t u r t l e s crawling around on the f l o o r , and one has a computer which simulates the t u r t l e on a screen. To summarize, one can make computers i n t o b e t t e r teachers by improving student-computer communications, by improving domain-computer i n t e r a c t i o n s , or by using a good 1.3.2 P u t t i n g a More I n t e l l i g e n t Teacher i n the Room Most CAI programs lack the knowledge to teach e f f e c t i v e l y . They don't understand students and they don't understand what they are teaching. Making computers i n t o b e t t e r teachers, by g i v i n g them knowledge of the r e a l world, and t e l l i n g them how to use i t , comes under the domain of A r t i f i c i a l I n t e l l i g e n c e . - 5 -Researchers who t r y to put knowledge about students, about teaching, and about what i s being taught i n t o CAI programs c a l l t h e i r f i e l d I n t e l l i g e n t Computer A s s i s t e d I n s t r u c t i o n (ICAI); presumably to d i s t i n g u i s h i t from the not so i n t e l l i g e n t kind of CAI. There are four general areas of ICAI research: * Increasing the computer's knowledge of students (with a student model). * Increasing i t s knowledge of the domain (with a domain model). * Increasing i t s knowledge of teaching and l e a r n i n g (with an e d u c a t i o n a l model). * Increasing i t s a b i l i t y to ca r r y out a n a t u r a l language d i a l o g with students. Each of these areas i n v o l v e s many i n t e r e s t i n g subproblems. Within student modelling, for example, there i s the problem of f i n d i n g out what students already know, what they don't know, and what misconceptions they have, as w e l l as the problem of changing the model as the student l e a r n s ( S e l f , 1974). 1.4 Teaching Programming Languages One good domain for CAI i s computers themselves. Computers can't do much with trees and c a r s , but they are ready made to teach about computers. A computer can't p o i n t , but when i t teaches about tape d r i v e s , i t can s p i n tapes back and f o r t h . When i t teaches computer programming, i t can tr a c e programs, and i t can check and d i s p l a y the r e s u l t s . -6-Teaching programming languages i s made e s p e c i a l l y easy because people have invented many s t o r i e s f o r programming: things l i k e flow c h a r t s , algorithms, data flow diagrams, modular design, and i n t e r a c t i v e trace programs. 1.5 Teaching Prolog Prolog i s a Logic Programming language. The execution procedure f o r a Prolog program i s . l a r g e l y embedded i n the Prolog i n t e r p r e t e r , and not i n the program i t s e l f . Whereas programs i n t r a d i t i o n a l programming languages have an e x p l i c i t c o n t r o l s t r u c t u r e (with s e q u e n t i a l execution, loops, and so on), Prolog programs are mainly d e s c r i p t i v e , based on the i m p l i c i t proof procedure of the i n t e r p r e t e r (top down d e p t h - f i r s t search with b a c k t r a c k i n g ) . Because i t d i f f e r s from t r a d i t i o n a l programming languages, Prolog requires d i f f e r e n t s t o r i e s . Some Prolog s t o r i e s are evaluated by Bundy (1983). These i n c l u d e : Or Trees and And/Or Trees (both from Kowalski, 1979); the Byrd Box, Arrows, the Flow of S a t i s f a c t i o n , and a Prolog t r a c e program ( a l l described i n C l o c k s i n and M e l l i s h , 1981). A l l the b e n e f i t s of teaching programming languages hold f o r P r o l o g . Students can write programs, which the computer can run and t r a c e , and there are good s t o r i e s f o r teaching P r o l o g . As w e l l , Prolog's d e c l a r a t i v e semantics make i t a very n i c e v e h i c l e for the use of ICAI techniques. In P r o l o g , i t i s easy to def i n e rule-bases f o r e d u c a t i o n a l , student, and domain models, and to use these i n d e c i s i o n making. -7-1 .6 T h i s T hesis Two computer systems for teaching Prolog were developed f o r t h i s t h e s i s . The f i r s t i s an ICAI program that teaches P r o l o g . I t uses knowledge of the student, the domain, and of teaching to determine which t o p i c to teach, and how to teach i t . The second provides an animated trace of the execution of Prolog programs. Students can use i t to follow the execution of t h e i r own programs, and of the programming examples provided by the ICAI program. Both programs were developed on a DEC VAX 11/780 running Berkeley UNIX. The ICAI program i s w r i t t e n i n CProlog. The t r a c e i s w r i t t e n i n CProlog and i n C, using the CURSES windowing package, which i n turn uses the UNIX Termcap te r m i n a l database. 1.7 The Prolog ICAI System 1.7.1 And/Or P r e r e q u i s i t e Trees The use of And/Or Trees to represent p r e r e q u i s i t e r e l a t i o n s f o r a CAI course i s described i n a number of papers by Darwin Peachey and Gordon McCalla at the U n i v e r s i t y of Saskatchewan (Peachey, 1982) (McCalla et a l , 1982). B r i e f l y , the course to be taught i s d i v i d e d i n t o an number of separate t o p i c s , l i n k e d together by p r e r e q u i s i t e r e l a t i o n s h i p s . The And/Or Tree l i n k s the t o p i c s of the course. -8-Some t o p i c s have no p r e r e q u i s i t e s — these may be taught immedia te ly . The o thers have p r e r e q u i s i t e s which shou ld be covered f i r s t . A t o p i c may have more than one p r e r e q u i s i t e — a l l o f which are r e q u i r e d . These are connected by AND l i n k s i n the p r e r e q u i s i t e t r e e . A l t e r n a t i v e l y , a t o p i c may have s e v e r a l p r e r e q u i s i t e s — only one of which i s r e q u i r e d . These are connected by OR l i n k s . Here i s a p a r t of the p r e r e q u i s i t e t r e e ( a c t u a l l y a d i r e c t e d graph) from the P r o l o g CAI course : P r o l o g Syntax OR I n t r o d u c t i o n to P r o l o g A Quick Look at P r o l o g I n t r o d u c t i o n to L o g i c Us ing the T u t o r i a l F i g u r e 1: Example of And/Or P r e r e q u i s i t e Tree In t h i s example there are two ways to s a t i s f y the p r e r e q u i s i t e requirements for "Prolog Syntax". E i t h e r s tudy " I n t r o d u c t i o n to P r o l o g " a long with both of i t s p r e r e q u i s i t e s , or study " I n t r o d u c t i o n to L o g i c " and i t s s i n g l e p r e r e q u i s i t e . - 9 -1.7.2 Who Hakes the Decisions? Using AND/OR Trees l e t s the system make reasonable choices f o r t o p i c s to be s t u d i e d , but care must be taken to ensure that the choices made are not too a u t h o r i t a r i a n . The system makes d e c i s i o n s based on incomplete i n f o r m a t i o n , and students must be able to o v e r r u l e these d e c i s i o n s when they choose. A major c o n s i d e r a t i o n i n the current research was to produce a system that gave the student a great deal of freedom of choice as to what to study, how to study i t , and when. The Prolog CAI system chooses t o p i c s f o r the student to study, and chooses methods for teaching those t o p i c s . These choices act as d e f a u l t s . Each student i s f r e e to accept the systems choices or to d i s r e g a r d them to pursue h i s or her own i n t e r e s t s . 1.8 The Animated Trace (Anilog) A n i l o g i s a window-oriented trace f o r Prolog programs (the name comes from ANImation of LOGic). I t d i s p l a y s i n f o r m a t i o n about the execution of Prolog goals, t h e i r success, f a i l u r e , backtracking, and r e c u r s i v e c a l l s to other g o a l s , as w e l l as showing the database clauses they use, and any output they generate. A l l of t h i s information i s d i s p l a y e d on the screen, i n three windows: one f o r goals, one f o r the Prolog database, and one f o r user output. 1.9 Sample P r o t o c o l s The f o l l o w i n g three pages show the beginning of a t y p i c a l s e s s i o n with the Prolog ICAI system. Following t h i s i s a snapshot of the animated t r a c e , part-way through s a t i s f y i n g the g o a l : ?- w r i t e ( h i ) , m e m b e r ( e l f , [ d w a r f , e l f , p i x i e ] ) , f a i l . A more complete example of the animated t r a c e may be found i n Appendix 4 . - 1 1 -PROLOG COURSE - TABLE OF CONTENTS Using Thi s T u t o r i a l A Quick Look at Prolog I n t r o d u c t i o n to Prolog I n t r o d u c t i o n to Logic Syntax Semantics U n i f i c a t i o n Proof Procedure S i d e - e f f e c t s Prolog Basics B u i l t - i n P r e d i c a t e s I n t r o d u c t i o n to the B u i l t i n s A r i t h m e t i c Input/Output I/O B a s i c s F i l e Access Character I/O Term I/O Reading-in Programs Convenience Operators C o n t r o l of Execution The Cut Comparison of Terms Meta-Logical Debugging Sets Program Information Changing the Data Base I n t e r n a l Data Base Environmental D e f i n i t e Clause Grammars Type <cr> and the system w i l l choose a t o p i c for you, (or type h f o r h e l p ) . [The user types a c a r r i a g e r e t u r n , so the system chooses a t o p i c ] F i g u r e 2: The s t a r t of the Prolog ICAI course -12-Prolog T u t o r i a l System *** A Quick Look at Prolog *** Options: 1 - lesson 2 - example Please choose one of the above options (or type h f o r help) [The user types a c a r r i a g e r e t u r n , so the system chooses an option] F i g u r e 3 : The f i r s t t o p i c s e l e c t e d -13-Welcome to CProlog Prolog attempts to answer questions based on the information i t has been given ( i t s data base). A statement in Prolog i s ca l l ed a clause. Here i s a small database, consist ing of 5 clauses. The comments to the right indicate the intended meaning of each clause. greek(souvlaki) . greek(socrates) . human(socrates). human(descartes) / * souvlaki is greek * / / * Socrates i s greek * / / * Socrates i s human * / / * Descartes i s human * / philosopher(X) : - human(X) / * a l l humans are philosophers The symbol : - means "if", or "is implied by", or "can be proven by", so the last clause above can be read as: - X i s a philosopher i f X is human. - X i s human implies X is a philosopher. - To prove that X is a philosopher, f i r s t prove that X is human. Prolog knows that socrates i s the name of a p a r t i c u l a r object , while X can be any object because X begins with a c a p i t a l l e t t e r . In computer programming terms, X i s a var iab le . A var iable i s a kind of place holder or blank space into which Prolog t r i e s to put the names of objects . Type <cr> to continue (or h for help) . Figure 4: The f i r s t lesson selected - 1 4 -Prolog Animated Trace Current Goal: (Level 1) w r i t e ( h i ) , m e m b e r ( e l f , [ d w a r f , e l f , p i x i e ] ) , < — current subgoal f a i l . P r olog Database: member(X,[X member(X,[ Y L ] ) . L l ) - member(X,L). < — t r y to u n i f y with subgoal User Output: h i F i g u r e 5: Snapshot of the Prolog Animated Trace -15-Chapter Two L i t e r a t u r e Survey This chapter surveys various attempts to improve the use of computers i n education. More d e t a i l s on these and other p r o j e c t s can be found i n Kearsley (1987), Jones (1986), Yazdani (1984), Sleeman and Brown (1982), and Barr and Feigenbaum (1982). Our d i s c u s s i o n i s d i v i d e d i n t o the two areas d i s c u s s e d i n Chapter One: 1) Using more i n t e l l i g e n c e . We w i l l look at four areas: understanding students, understanding the domain of i n s t r u c t i o n , understanding how to teach, and using n a t u r a l language dialogue. 2) Broadening the i n t e r a c t i o n between teacher, student, and the domain of i n s t r u c t i o n . We w i l l look at two areas: teaching i n s u i t a b l e domains, and using graphics to improve communication. Of course, some systems f i t i n t o more than one category. Guidon (Clancey 1979) f o r example, i s discussed under Domain Understanding, but i t could e q u a l l y w e l l have been i n the s e c t i o n on Understanding Students. S i m i l a r l y , WUSOR (G o l d s t e i n 1979) could be discussed i n three d i f f e r e n t p l a c e s , because i t s Genetic Graph i s student model, domain model, and e d u c a t i o n a l theory a l l r o l l e d up i n t o one. -16-2.1 Using More I n t e l l i g e n t Teachers 2.1.1 Understanding Students For teaching purposes, i t i s important to have a model of the student's knowledge of the subject being taught. A teacher (or ICAI system) compares what he or she b e l i e v e s the student knows with what he or she would l i k e the student to know. The simplest and most common type of student model i s simply a record of which lessons have been s t u d i e d . The next step up i s a record of which t o p i c s have been le a r n e d . G o l d s t e i n (1979) suggests a more complex student model which combines knowledge of the domain of study with knowledge of the l e a r n i n g process. He uses t h i s "Genetic Graph" i n a program c a l l e d WUSOR, which i s a tu t o r f o r the computer game WUMPUS. The Genetic Graph models the e v o l u t i o n of a student's knowledge. Nodes i n the graph represent the pro c e d u r a l s k i l l s that a student acquires i n changing from a novice i n t o an expert player of WUMPUS. Arcs i n the graph represent the l e a r n i n g processes that are used to acquire these s k i l l s . These processes i n c l u d e : analogy, s p e c i a l i z a t i o n , g e n e r a l i z a t i o n , p r e r e q u i s i t e and d e v i a t i o n . A student's knowledge of the game at any given time i s represented by a subset or p e r t u r b a t i o n of t h i s graph. The system decides what to teach, and how to teach i t , by f o l l o w i n g arcs from the area the student has mastered to new -17-areas of the graph. The new nodes (or s k i l l s ) are then added to the region representing the student's knowledge. It i s very d i f f i c u l t to f i n d out what i s going on i n the minds of students. It i s a l l very w e l l to say that the student model represents what the student knows, but how can an ICAI system f i n d out what a student does know? "Why Your Students Write Those Crazy Programs" (Soloway et a l . 1981) describes some of the mistakes made by students i n a beginning Pascal c l a s s , and speculates on the reasons f o r them. Proust (Johnson and Soloway 1987) i s a program which f i n d s bugs i n Pascal programs. Proust f i n d s bugs by comparing the program with a formal d e s c r i p t i o n of the problem the program i s intended to so l v e . Matz (1982) l i s t s some common reasons student e r r o r s i n high school algebra problems. These include e x t r a p o l a t i n g o l d r u l e s to f i t new s i t u a t i o n s when the o l d r u l e s do not, i n f a c t , apply, making e r r o r s through c a r e l e s s n e s s , and not having enough knowledge to deal with the problem. Burton and Brown (1977) d i d something a s i m i l a r study f o r simple a r i t h m e t i c . They l i s t e d over 100 common mistakes c h i l d r e n make i n performing two-column s u b t r a c t i o n problems, and there i s no reason to b e l i e v e that a l l the mistakes have been found. Their systems, BUGGY and l a t e r DEBUGGY, are aimed at diagnosing the problems students have; they do not go so f a r as to plan s t r a t e g i e s f o r c o r r e c t i n g the student's misconceptions. -18-Colburn (1982) i s a l s o concerned with d i a g n o s i s , t h i s time i n the area of reading problems. She proposes an expert system to advise a teacher or c o u n s e l l o r i n diagnosing reading problems i n c h i l d r e n . The system uses a database of d i a g n o s t i c r u l e s to recommend t e s t s and to analyse t h e i r r e s u l t s . L i k e BUGGY and DEBUGGY, t h i s system diagnoses problems, but i t does not go so f a r as to p r e s c r i b e c o r r e c t i v e a c t i o n . 2.1.2 Understanding the Domain of I n s t r u c t i o n A s i m u l a t i o n i s one type of domain model. I t can be used by students to see how a real-world system r e a c t s to d i f f e r e n t c o n d i t i o n s . For example, i t can demonstrate how an a i r p l a n e r e a c t s to having i t s wing f l a p s r a i s e d . ThingLab (Borning 1979) i s a general purpose s i m u l a t i o n t o o l k i t . I t provides a language f o r d e f i n i n g s i m u l a t i o n s i n terms of part-whole h i e r a r c h i e s and i n h e r i t a n c e s t r u c t u r e s , i n terms of the r e l a t i o n s h i p s between pa r t s of the model, and i n terms of c o n s t r a i n t s on those r e l a t i o n s h i p s . ThingLab a l s o provides a g r a p h i c a l d i s p l a y f o r s i m u l a t i o n s . The simulated system can be modified, and observed, by i n t e r a c t i v e l y changing parts of the d i s p l a y , and seeing what happens. For example, a Fahrenheit to C e l s i u s converter might be d i s p l a y e d as two inte r c o n n e c t e d thermometers. Lowering the reading on the Fahrenheit thermometer causes a corresponding reduction on the C e l s i u s s c a l e , and v i c e versa. -19-A more d i r e c t way to use a domain model i n teaching i s to use i t to understand what i s being taught, and to use that understanding to provide explanations to students. These can be summaries of p a r t i c u l a r concepts, or d e s c r i p t i o n s of the r e l a t i o n s h i p s between concepts. To date, most systems that use domain knowledge do not model the e n t i r e domain, they model i t s s t r u c t u r e . Going back to the a i r p l a n e example, such a system would know how r a i s i n g wing f l a p s a f f e c t s a i r speed, but would not know what a wing f l a p was. Stephens et a l . (1982) use reasoning about the s t r u c t u r e of the domain to teach about c l i m a t e . E s s e n t i a l l y , t h e i r domain model gives cause and e f f e c t r e l a t i o n s h i p s between such environmental f a c t o r s as warm ocean c u r r e n t s , r a i n f a l l , mountains, wind d i r e c t i o n , and warm and c o l d a i r masses. The system does not understand mountains, but i t does know how they a f f e c t a i r c u r r e n t s . SOPHIE (Brown et a l , 1976) teaches students how to diagnose f a u l t s i n e l e c t r i c a l c i r c u i t s . I t con t a i n s a simulator f o r e l e c t r o n i c c i r c u i t s , which i t uses to see how reasonable a student's troubleshooting s t r a t e g i e s are. When i t f i n d s things i n i t s model that the student does not seem to understand, i t can point them out. GUIDON (Clancey 1977) teaches d i a g n o s t i c s k i l l s to medical students by leading them through s e l e c t e d case s t u d i e s . It keeps track of expressed student i n t e r e s t s , and uses them i n choosing cases to present. -20-Guidon's domain model i s i n t e r e s t i n g because i t i s an e n t i r e l y independent expert system. MYCIN i s an expert system that diagnoses c e r t a i n kinds of blood d i s o r d e r s , using a database of d i a g n o s t i c r u l e s to make i t s d e c i s i o n s . Guidon teaches about MYCIN 'S r u l e s . I t runs MYCIN to ob t a i n a di a g n o s i s f o r a p a r t i c u l a r case. Then Guidon goes through the same case with a student. I t compares the student's d i a g n o s t i c procedures with those of MYCIN, and i t ex p l a i n s MYCIN 'S diagnosis to the student. To do t h i s , i t uses a database of explanations of MYCIN 'S r u l e s , and another database of teaching r u l e s . Guidon2 (teaching about NEOMYCIN) adds yet another database. T h i s contains r u l e s f o r analyzing the student's behavior (Clancey 1979) (Clancey 1987). I t attempts to uncover the d i a g n o s t i c process the student i s using, so that mistakes i n that process can be pointed out and c o r r e c t e d . Kimball's symbolic i n t e g r a t i o n t u t o r (Kimball 1973) uses s t r u c t u r a l knowledge i n a very d i f f e r e n t way. I t guides the student through the s o l u t i o n of symbolic i n t e g r a t i o n problems. When a s o l u t i o n i s produced, i t compares i t to a p r e v i o u s l y s t o r e d s o l u t i o n . I f the new s o l u t i o n i s sh o r t e r than the o l d one, i t i s deemed to be b e t t e r , and the system adopts i t as the new standard. Suppes (1972) suggests the use of "strands" to s t r u c t u r e the domain of i n s t r u c t i o n . In the school system, students o f t e n study a subject at d i f f e r e n t l e v e l s i n d i f f e r e n t grades, and a strand corresponds to such a s u b j e c t . -21-Suppes' strands can be though of as towers, with simple problems at the bottom, and more complex ones higher up. A student can be doing problems at one l e v e l on the a r i t h m e t i c s t r a n d , and be at q u i t e a d i f f e r e n t l e v e l on the o t h e r s . McCalla's L i s p Course (McCalla et a l . 1982) i s a general purpose system using the p r e r e q u i s i t e r e l a t i o n s h i p s between concepts to guide i t s teaching. Concepts i n the L i s p Course are l i n k e d together by an And/Or P r e r e q u i s i t e Tree. So, f o r example, the b a s i c concept of r e c u r s i o n i s a p r e r e q u i s i t e f o r both t a i l r e c u r s i o n and f o r i n d i r e c t r e c u r s i o n , and these i n turn are p r e r e q u i s i t e s for a mastery of the e n t i r e r e c u r s i o n t o p i c . The L i s p Course i s described i n more d e t a i l i n Chapters One and Three. The Scent automated advisor (McCalla et a l . 1986) i s intended to a i d students i n debugging L i s p programs. Using knowledge of L i s p , knowledge of general-purpose programming techniques, and knowledge of the s p e c i f i c task at hand, Scent analyses student programs i n a v a r i e t y of ways. Scent i s organized i n t o s e v e r a l components, which communicate through a "blackboard". Program behavior components produce traces and c r o s s - r e f e r e n c e l i s t i n g s ; s t r a t e g y judges attempt to determine which s o l u t i o n s t r a t e g y i s being used; d i a g n o s t i c i a n s look f o r e r r o r s i n s t r a t e g y ; while task experts look at how w e l l the program i s s o l v i n g the p a r t i c u l a r task at hand. -22-2.1.3 Understanding How to Teach LOGO (Papert 1980) i s based on discovery or P i a g e t i a n l e a r n i n g ( a f t e r Jean Piaget, an edu c a t i o n a l t h e o r i s t ) . Discovery l e a r n i n g i s n a t u r a l l e a r n i n g , without e f f o r t or teaching. An example of t h i s i s the way c h i l d r e n l e a r n t h e i r f i r s t language — by hearing i t and being i n t e r e s t e d , not by studying i t . The o r i g i n a l LOGO was a simple computer language which was used to c o n t r o l a mechanical t u r t l e . The t u r t l e r o l l e d around on the f l o o r , and i t had a pen i n i t s b e l l y , which could be r a i s e d or lowered. LOGO commands t o l d the t u r t l e to take so many " t u r t l e steps" forward, or to turn, and moving with the pen down would draw a p i c t u r e . More recent versions of LOGO propel a g r a p h i c a l t u r t l e around a computer terminal d i s p l a y . C h i l d r e n can pl a y with the t u r t l e , making i t draw d i f f e r e n t p i c t u r e s . They can a l s o p l a y i n micro-worlds. In one such micro-world, a t u r t l e i n motion tends to remain i n motion, while a t u r t l e at r e s t tends to remain at r e s t . Another extension to LOGO has been the i n c l u s i o n of some of the b a s i c l i s t handling f u n c t i o n s of LISP. LOGO i s now a popular f i r s t programming language, and i s a v a i l a b l e on many micro-computers. Some of the people who created LOGO are now working on a new program c a l l e d Boxer (DiSessa 1986). Designed to make the a c t i v i t y of programming more a c c e s s i b l e to students, Boxer i s based on one uniform metaphor — the box. In Boxer, - 2 3 -programs, data, environments and s p r i t e s are a l l represented v i s u a l l y as boxes. A program box i n s i d e another program box represents a subroutine, while a data box which co n t a i n s other data boxes represents a record s t r u c t u r e . One of the design c r i t e r i a behind Boxer i s the p r i n c i p l e of "naive r e a l i s m " : the appearance of the system should a c c u r a t e l y r e f l e c t i t s underlying s t r u c t u r e , so that an understanding of the appearance of the system "can be t r a n s l a t e d d i r e c t l y i n t o an understanding of the system". Boxes (and hence programs, data, etc.) can be a l t e r e d by d i r e c t manipulation of t h e i r on-screen r e p r e s e n t a t i o n s . O'Shea's (1979) Quadratic Tutor l e a r n s as i t teaches. I t changes i t s own teaching r u l e s i n an attempt to s e l e c t the most e f f e c t i v e teaching s t r a t e g y . I t can, f o r example, be d i r e c t e d to optimize i t s s t r a t e g y so as to decrease the time a student spends with the t u t o r . 2.1.4 N a t u r a l Language Dialogue Dialogue, i n which the student and program t a l k to each other i n n a t u r a l language, i s both one of the e a r l i e s t goals of ICAI and one of the f u r t h e s t from achievement. C a r b o n e l l (1970) wrote the f i r s t dialogue system, c a l l e d SCHOLAR. SCHOLAR taught geography. I t s knowledge of the subje c t was stored i n a semantic network, which i t used to generate questions f o r students, to check t h e i r answers, and to answer questions posed by students. C a r b o n e l l c a l l e d t h i s s o r t of i n t e r a c t i o n , which was sometimes guided by the -24-program and sometimes by the student, a m i x e d - i n i t i a t i v e d i a l o g u e . A more recent attempt at dialogue has been made by Curran (1982). He, along with students i n an A r t i f i c i a l I n t e l l i g e n c e course, wrote a "t e a c h e r / l e a r n e r " . T h i s program knows some things about the domain of computer s c i e n c e , and i t wants to l e a r n more. It has "a t h i r s t f o r o b t a i n i n g Computer Science information". Curran's program i s not intended to teach computer science, but to teach A r t i f i c i a l I n t e l l i g e n c e . Students study how the program works, not what i t knows. The program engages students i n a s i m p l i f i e d n a t u r a l language dialogue, modelled a f t e r Weizenbaum's E l i z a program (1965). I t "makes the machine appear more c l e v e r than i t i s " . The program "can be temperamental and change the su b j e c t , or respond with moody sentences r e f l e c t i n g any of s e v e r a l emotional s t a t e s " (quotations from Curran, 1982). The program gives more c r e d i b i l i t y to info r m a t i o n that comes from s e v e r a l sources, and l e s s to information when i t i s c o n t r a d i c t e d . Furthermore, i n d i v i d u a l s who f r e q u e n t l y input b e l i e v a b l e information are deemed more trustworthy than those who o f t e n enter c o n t r a d i c t o r y items. The program can c o n s t r u c t general r u l e s from s p e c i f i c information (unless and u n t i l i t f i n d s a counter example). F i n a l l y , i t " f o r g e t s " i n f o r m a t i o n which i s not very b e l i e v a b l e , or which i s not f r e q u e n t l y accessed by students. -25-2.2 Broadened I n t e r a c t i o n s among Teacher, Student and Domain 2.2.1 Teaching Programming Languages The main b e n e f i t of teaching about a programming language i s that the teaching program and the student can both run sample programs, p r o v i d i n g a ready made domain model. On the other hand, i t brings i t s own s p e c i a l problems as w e l l , p a r t i c u l a r l y understanding programs that students w r i t e . The B a s i c I n s t r u c t i o n a l Program, or BIP, (Dageforde et a l . 1978) teaches programming i n Basic through the use of aut h o r - s u p p l i e d example problems. The student w r i t e s a program to solve a given problem, then BIP runs i t and compares the r e s u l t s with a p r e v i o u s l y stored s o l u t i o n . BIP s t o r e s information about the s k i l l s needed to s o l v e each problem i n a Curriculum Information Network. I t chooses problems f o r a student by looking f o r ones that use one new s k i l l , along with s e v e r a l s k i l l s the student already has. Soloway and h i s colleagues (1983) have i n v e s t i g a t e d program understanding i n t h e i r system MENO-II. I t analyses student programs, and t r i e s to catch run time e r r o r s , both those that are problem dependent, and those that are problem independent. A s p e c i a l Problem D e s c r i p t i o n Language (PDL) i s used both by the student f o r program development, and by MENO fo r program understanding. MENO compares the PDL d e s c r i p t i o n of the student's program with a stored d e s c r i p t i o n of a bug-free v e r s i o n of the same program, by matching corresponding program structures (eg. loops). It can only cope with a few control structures, s p e c i f i c a l l y straight l i n e code, branching, and simple loops — the sort of things beginning programmers use. Laubsch and Eisenstadt (1981) propose a similar approach to program understanding. Their system attempts to translate programs written by students into "plan diagram notation". This encodes control flow and data flow information. It detects "unreasonable code", such as unused variables and duplicate statements. Then i t t r i e s to match the description of the student's program with one from i t s l i b r a r y . 2.2.2 Graphics Antics (Dionne and Mackworth 1978) was developed for a M.Sc. Thesis at the University of B r i t i s h Columbia. It i s used to produce animated films showing the execution of LISP programs. Antics graphically traces the evaluation of LISP functions, taking information about the S-expression being traced, the flow of control, and the assignment of values to variables, and displaying i t on different parts of the screen. Antics uses graphics to make programs written in a non-graphical language (LISP) easier to understand. The natural next step i s to abandon the o r i g i n a l language and to use the graphical representation d i r e c t l y for programming. This i s what Lakin proposes (Lakin 1980). LISP i s a symbol processing language, whose symbols are strings of text. Lakin's system Pam (for PAttern Manipulation) i s a -27-t e x t - g r a p h i c s processing language. Programs i n Pam are a mixture of text and graphics, and the o b j e c t s they process can l i k e w i s e be a mixture of the two. 2.3 Summing up the L i t e r a t u r e The systems examined i n t h i s chapter are l a r g e l y experimental i n nature. "Because of the s i z e and complexity of ICAI programs, most researchers tend to concentrate t h e i r e f f o r t s on the development of a s i n g l e part of what would c o n s t i t u t e a f u l l y usable system" (Barr and Feigenbaum 1982). I t i s not s u r p r i s i n g , t h e r e f o r e , to f i n d that few have found t h e i r way out of the lab o r a t o r y and i n t o everyday use. One aim of t h i s t h e s i s i s to develop a p r a c t i c a l ICAI system, and i t i s with t h i s i n mind that the f o l l o w i n g e v a l u a t i o n i s made. There have been few p r a c t i c a l advances i n student m o d e l l i n g . Soloway, Matz, Burton and Brown, and Colburn have each taken some steps towards the diagnosis of student misconceptions, but none of them has produced a complete system which can teach as w e l l as diagnose. G o l d s t e i n and McCalla, with l e s s ambitious student models, have each produced working experimental ICAI programs. I t i s i n t e r e s t i n g to compare G o l d s t e i n ' s Genetic Graph with McCalla's And/Or P r e r e q u i s i t e Tree. Both p l a c e the concepts to be learned i n t o a d i r e c t e d graph. Both represent the student's knowledge with a subset of t h i s graph, and both -28-represent l e a r n i n g by f o l l o w i n g arcs from the known t e r r i t o r y to the unknown. The main d i f f e r e n c e between the two i s that an a r c i n the Genetic Graph represents the l e a r n i n g process that a student i s b e l i e v e d to use i n t r a v e r s i n g i t , while an a r c i n the And/Or Tree simply represents a p r e r e q u i s i t e r e l a t i o n s h i p . The Genetic Graph i s a more ambitious approach, but i t seems to make l e s s sense for a p r a c t i c a l system. By attempting to a n t i c i p a t e the student's l e a r n i n g processes i t i s o v e r l y r e s t r i c t i v e (expecting a student to g e n e r a l i z e i n one case and to use analogy i n another). The And/Or Tree leaves the l e a r n i n g process, and the method of i n s t r u c t i o n , more open and more f l e x i b l e f o r i n d i v i d u a l students. The domain models described i n t h i s chapter are of two types. The type used i n SOPHIE to teach e l e c t r o n i c t r o u b l e s h o o t i n g uses a r e l a t i v e l y deep knowledge of the domain to show students the r e s u l t s of t h e i r a c t i o n s . The other kind, used i n WUSOR and i n the L i s p Course, simply model the s t r u c t u r e of the domain to show how d i f f e r e n t t o p i c s are r e l a t e d . In the long run, the greatest advances i n ICAI may come from research i n t o new educational t h e o r i e s or from the use of n a t u r a l language dialogue. For the present, however, the impact of these areas on p r a c t i c a l systems remains s l i g h t . LOGO i s the only system described i n t h i s chapter that has come i n t o widespread use, and i t s success can perhaps be -29-a t t r i b u t e d to three f a c t o r s . Rather than using inadequate student and domain models to p r e d i c t what the student should be studying (often i n c o r r e c t l y ) , Logo's d i s c o v e r y l e a r n i n g technique l e t s the student decide. I t has an a p p r o p r i a t e  domain (computer programming and problem s o l v i n g ) , which i s la r g e enough to be worth d i s c o v e r i n g , yet t r a c t a b l e enough that students can do much of the e x p l o r i n g on t h e i r own. F i n a l l y , Logo uses graphics to show students what t h e i r programs are doing. - 3 0 -Chapter Three Prolog ICAI System Design T h i s chapter d e s c r i b e s the design of the Prolog Computer A s s i s t e d I n s t r u c t i o n program. The Animated Trace program w i l l be d e s c r i b e d i n Chapter Four. 3.1 Design Goals The Prolog ICAI system was intended as a p r a c t i c a l t o o l f o r l e a r n i n g P r o l o g . As such, i t i s more important f o r i t to be easy to use and complete, than to be i n n o v a t i v e . When concepts from ICAI could make the system more f l e x i b l e and u s e f u l , they have been incorporated i n t o the design. When i t seemed they would d e t r a c t from the system's e f f e c t i v e n e s s or i t s ease of use, such ideas were not inc o r p o r a t e d . The system was a l s o designed to be n o n - a u t h o r i t a r i a n . While an attempt was made to have the system make i n t e l l i g e n t d e c i s i o n s , students o f t e n have a be t t e r idea of t h e i r own needs than the system does, so i t i s important to l e t students o v e r r u l e the system when they want to. The Prolog ICAI system's design i s independent of the sub j e c t matter of the course i t i s teaching, and i s a l s o independent of the i n s t r u c t i o n a l methods used to teach any i n d i v i d u a l t o p i c . F i n a l l y , i t was hoped that the system would be i n t e r e s t i n g . That i s , students should enjoy using i t . -31-3.2 General Design At the highest l e v e l , the system's design i s very simple. F i r s t i t chooses a t o p i c to teach. then i t chooses a way to teach i t , and then i t teaches i t . T h i s c y c l e repeats u n t i l the course has been completed. To make these choices, the system c o n s u l t s a l i s t of the course t o p i c s , a p r e r e q u i s i t e s t r u c t u r e (described below), and a l i s t of the i n s t r u c t i o n a l methods a v a i l a b l e f o r each t o p i c . In order to use the system to teach some other course, one need only change the t o p i c l i s t , the p r e r e q u i s i t e s t r u c t u r e , and the i n s t r u c t i o n a l modules themselves. Throughout the course, the <return> key i s used to l e t the system make d e c i s i o n s . By c o n t i n u a l l y p r e s s i n g <return>, a student can progress through the e n t i r e course, with the system choosing a l l the t o p i c s to be st u d i e d , and the methods f o r studying them. On the other hand, a student who wants to guide h i s or her progress i s f r e e to do so. The system's choices of t o p i c and method are only d e f a u l t s . Students can always: - Choose a t o p i c or a method of i n s t r u c t i o n f o r themselves. Go i n t o CProlog to t r y out something they have le a r n e d . Suspend the Prolog course, and resume i t l a t e r on, e x a c t l y where they l e f t o f f . Review a t o p i c , or review the p r e r e q u i s i t e s f o r a t o p i c . Try a l t e r n a t e methods of i n s t r u c t i o n , or a l t e r n a t e p r e r e q u i s i t e s f o r a t o p i c . - 3 2 -T h e f o l l o w i n g d i a g r a m i l l u s t r a t e s t h e d e s i g n o f t h e P r o l o g C A I s y s t e m . T O P I C S E L E C T I O N / L E S S O N \ I BANK J ( E X A M P L E \ I BANK J / SUMMARY \ I BANK ) METHOD S E L E C T I O N 3E I T E M P R E S E N T A T I O N ANIMATED TRACE LEGEND c o n t r o l f l o w d a t a f l o w ^> p r o c e d u r e I d a t a F i g u r e 6: P r o l o g C A I S y s t e m D e s i g n - 3 3 -The f i g u r e should be read from the top. A t o p i c i s s e l e c t e d using information from the p r e r e q u i s i t e t r e e , the student model and from student input. The student model i s b u i l t up as the student progresses through the course, and i s i n i t i a l l y empty. Once a t o p i c has been s e l e c t e d , the system chooses a method of i n s t r u c t i o n . This choice depends upon the l e s s o n s , examples, assignments, and summaries that are a v a i l a b l e f o r that p a r t i c u l a r t o p i c . One or more items ( l e s s o n s , examples, etc.) w i l l be presented u n t i l the t o p i c has been s a t i s f a c t o r i l y completed. The student model i s then updated, and the process repeats. Students may use the Animated Trace to f u r t h e r i n v e s t i g a t e many of the examples from the course. 3 . 3 M e t h o d s o f I n s t r u c t i o n The system teaches by reference to a bank of i n s t r u c t i o n a l m a t e r i a l s , which are d i v i d e d i n t o f i v e c a t e g o r i e s : l e s sons, examples, assignments, summaries, and anything e l s e . Lessons present new m a t e r i a l on a given t o p i c . A l e s s o n c o n s i s t s of one or more pages of t e x t . The student can s c r o l l back and f o r t h w i t h i n a lesson, or suspend i t i n order to go i n t o Prolog, or to look at an example. Examples may be small Prolog programs, or merely s y n t a c t i c a l l y c o r r e c t uses of a b u i l t - i n p r e d i c a t e . Students -34-can look at the examples, they can go i n t o Prolog to t r y them out, and they can use the Animated Trace to see how they work. Assignments c o n s i s t of one or more short answer or m u l t i p l e choice questions. An assignment i s complete when a l l of i t s questions have been c o r r e c t l y answered. To determine i f an answer i s c o r r e c t , the system compares i t with a set of p r e v i o u s l y stored answers. It does not attempt to evaluate the c o r r e c t n e s s of student-written programs, but students can examine these themselves using the Animated Trace. Summaries are short v e r s i o n s of lessons, used fo r review and to determine i f a student i s already f a m i l i a r with a t o p i c . Anything E l s e means i n s t r u c t i o n a l m a t e r i a l s that do not f i t e a s i l y i n t o one of the other groups. In g e n e r a l , these may c o n s i s t of an a r b i t r a r y Prolog p r e d i c a t e ( f o r example, a c a l l to a n a t u r a l language t u t o r i n g program). This category was used f o r the o n - l i n e e v a l u a t i o n q u e s t i o n n a i r e , d i s c u s s e d i n Chapter F i v e . Each t o p i c may have any number of i n s t r u c t i o n a l modules a v a i l a b l e , i n any of these groups. There may, f o r example, be s e v e r a l examples f o r a p a r t i c u l a r t o p i c , or s e v e r a l lessons using d i f f e r e n t teaching s t r a t e g i e s . -35-3 .4 The P r e r e q u i s i t e S t r u c t u r e To teach a t o p i c , the system w i l l normally f i r s t f i n d and teach a l l of i t s p r e r e q u i s i t e s . I t f i n d s them by l o o k i n g at the p r e r e q u i s i t e s t r u c t u r e . The r e p r e s e n t a t i o n used for t h i s p r e r e q u i s i t e i n f o r m a t i o n i s the And/Or Tree (McCalla et a l . , 1982). A diagram showing part of such a tree i s given i n Chapter One. A t o p i c may have s e v e r a l p r e r e q u i s i t e s , a l l r e q u i r e d , or i t may r e q u i r e only one of a group of p r e r e q u i s i t e s . T h i s i s r e a l i z e d i n the And/Or Tree as f o l l o w s . I f a node has s e v e r a l descendents connected by an AND a r c , then a l l are r e q u i r e d . I f an OR arc i s used, then any one of the p r e r e q u i s i t e s w i l l do. A t o p i c with AND p r e r e q u i s i t e s can be taught only a f t e r a l l of i t s p r e r e q u i s i t e s have been taught, while a t o p i c with OR p r e r e q u i s i t e s may be taught a f t e r any one of i t s p r e r e q u i s i t e s i s completed. McCalla's use of the And/Or tree works q u i t e w e l l , but i t does have one problem. To see what that i s , we w i l l have to look more c l o s e l y at the OR node. The meaning of an OR i s that there are s e v e r a l d i f f e r e n t ways of s a t i s f y i n g a p r e r e q u i s i t e requirement. In what circumstances does t h i s a c t u a l l y occur? In the most common case, there are s e v e r a l d i f f e r e n t methods of i n s t r u c t i o n f o r the same t o p i c (eg. analogy vs. l e a r n i n g by doing). Any one of the methods should r e s u l t i n the same knowledge being learned by the student. -36 -In the other case (much l e s s common), there are two separate bodies of knowledge, e i t h e r one of which i s an acceptable p r e r e q u i s i t e to some f u r t h e r concept. For example, the p r e r e q u i s i t e to a computer languages course might be a knowledge of any two computer languages. In McCalla's And/Or Trees, no d i s t i n c t i o n i s made between a l t e r n a t i v e methods of teaching a s i n g l e t o p i c , and a l t e r n a t i v e t o p i c s which are each acceptable p r e r e q u i s i t e s to some t h i r d t o p i c . Unfortunately, the two cases are not i d e n t i c a l , and should be tr e a t e d d i f f e r e n t l y . Consider the choice of method. A good teacher, or a good CAI program, can keep track of how w e l l students cope with d i f f e r e n t methods of i n s t r u c t i o n , and can use that knowledge to choose the methods which are most l i k e l y to succeed with each student. The choice of t o p i c i s more d i f f i c u l t . I t might be done with a s h o r t e s t path algorithm. The t o p i c chosen would be the one with the fewest p r e r e q u i s i t e s , so as to f u l f i l the p r e r e q u i s i t e requirements as q u i c k l y as p o s s i b l e . On the other hand, perhaps i t should be l e f t up to the students, s i n c e i t depends upon t h e i r p r i o r knowledge of Pro l o g , and t h e i r i n d i v i d u a l i n t e r e s t s . Since the choice of t o p i c d i f f e r s from the choice of method, the two are separated i n the Prolog CAI system. An And/Or t r e e i s used f o r the t o p i c s , and the choice of method i s made l a t e r on. -37-Mixing the choice of t o p i c and the choice of method of i n s t r u c t i o n i s not confined to McCalla's system. G o l d s t e i n ' s Genetic Graph, f o r example, a l s o mixes the two. 3 . 5 Choosing a Topic of I n s t r u c t i o n The system uses a r e c u r s i v e depth f i r s t search of the p r e r e q u i s i t e t r e e to choose a t o p i c of i n s t r u c t i o n . The search begins at the root of the t r e e (the end of the c o u r s e ) . I f t h i s node has no p r e r e q u i s i t e s , then i t can be taught immediately. I f i t has AND p r e r e q u i s i t e s , then each of these must be taught f i r s t , along with t h e i r p r e r e q u i s i t e s . I f i t has OR p r e r e q u i s i t e s i n s t e a d , then only one of these need be taught, along with i t s p r e r e q u i s i t e s . E v e n t u a l l y , the search reaches the leaves of the t r e e (those t o p i c s without p r e r e q u i s i t e s ) . The path that the search has taken through the tree i s one p o s s i b l e path that a student can take through the course. Beginning with the l e a f nodes, these t o p i c s are presented to the student, and, as each t o p i c i s completed, the student f o l l o w s the search path back towards the root of the t r e e . I f the student f a i l s to l e a r n a t o p i c , the system w i l l back up and look f o r an a l t e r n a t i v e path through the t r e e by t r y i n g other branches at OR nodes. If no b e t t e r r e s u l t s are achieved on any of the a l t e r n a t i v e paths, the system r e t u r n s to the f a i l e d t o p i c ( i n the hope that the student has lea r n e d something i n the i n t e r i m , and may be able to succeed where once he or she had f a i l e d ) . -38-The student does not need to go along with the system's choice of what to study. A student who i s bored with a topic can t e l l the system to look for another one (proceeding as i f the current topic had been successfully completed). A student who i s having trouble with a topic can ask the system to look for alternatives, or can review one or more of i t s prerequisites. F i n a l l y , a student who wants to guide his or her own studies can disregard a l l the system's choices, and pick each topic for himself or herself. 3.6 Choosing a Method of Instruction Associated with each topic in the course are one or more methods of instruction (lessons, examples, assignments and summaries). Once a topic has been chosen, the Prolog CAI system creates a menu l i s t i n g a l l of the methods of instruction for that topic (showing them in the same order in which they appear in the Prolog database), and presents that menu to the student. The student can pick any desired method, or he or she can l e t the system choose. The system chooses a method of instruction as follows: Standard Order: In general, the system w i l l present items in the order in which they appear in the menu. Normally, lessons appear f i r s t , followed by examples, assignments, and summaries. This may be changed for any topic by varying the order in which these items are l i s t e d in the Prolog database. - 3 9 -Multiple Entries: In some cases, several lessons exist for a single topic. These are alternative methods for studying the same topic, and so only one of them must be taught. It i s only i f the student feels the need for another approach that the others w i l l be taught. This would be true also for assignments and summaries as well, but as the course currently stands, no topic has more than one assignment or summary. 3.7 Deciding Which Topics are Previously Known Often, a student already knows some of the course material, or finds i t to be so self-evident that i t might as well be known ahead of time. A CAI system should be able to determine quickly which sections of the course a student already knows, and then use that information in choosing topics for individual students to study. At the same time, i t s belief that something i s known might turn out to be unfounded, so that any topics that are skipped because of i t are prime candidates for review i f a student has trouble later on. The Prolog CAI system leaves the decision of what to skip up to the student. The student can ask to leave any topic that seems unnecessary. Any such unfinished topics are included later on i f the system i s asked to find topics to review. -40 -3.8 Notes on I n s t r u c t i o n a l Methodology There i s no one best way to teach. Human teachers have a wide v a r i e t y of s t y l e s , and so do CAI programs. The s t r u c t u r e of the Prolog CAI system allows for a wide range of teaching s t y l e s to be used f o r i n d i v i d u a l t o p i c s . The P r e r e q u i s i t e O u t l i n e , the Topic L i s t , and the l i s t of i n s t r u c t i o n a l modules f o r each t o p i c are stored i n a r u l e -base. T h i s makes them easy to modify during course development, or l a t e r , during maintenance. Lessons, examples and summaries are no more than f i l e s of t e x t , which can be e a s i l y changed or augmented. Assignments are l i s t s of questions, each followed by the accepted responses, and by the a c t i o n to be taken, given each response. The procedures f o r changing the course (adding m a t e r i a l , or re-arranging or r e v i s i n g o l d ma t e r i a l ) i s de s c r i b e d i n the Appendices. 3.9 The Implementation The Prolog ICAI program was w r i t t e n e n t i r e l y i n P r o l o g . While t h i s made some of the program's features e s p e c i a l l y easy to implement (such as the c r e a t i o n and t r a v e r s a l of the p r e r e q u i s i t e t r e e ) , i t posed c e r t a i n problems as w e l l . CProlog ( v e r s i o n 1.1) does not provide any g r a p h i c a l p r e d i c a t e s , nor does i t allow a Prolog program to make system c a l l s , nor does i t allow a Prolog program to c a l l r o u t i n e s w r i t t e n i n other languages. The G r a p h i c a l Trace was intended -41-to be an i n t e g r a l part of the ICAI program, but these d e f i c i e n c i e s of CProlog made t h i s impossible. The a v a i l a b i l i t y of graphics from w i t h i n CProlog would a l s o have improved the menu pr e s e n t a t i o n used i n the Prolog ICAI program. Another problem with the implementation turned out to be the inadequacy of ordinary CRT d i s p l a y s f o r showing l a r g e q u a n t i t i e s of t e x t . A number of students i n d i c a t e d that they would rather have had the lesson t e x t s on paper than on the screen. T h i s s i t u a t i o n w i l l be ameliorated with the use of high r e s o l u t i o n bit-mapped workstations with windowing systems. - 4 2 -Chapter Four Animated Trace Design 4.1 I n t r o d u c t i o n T h i s chapter describes the design of the Prolog Animated Trace Program c a l l e d A n i l o g ( f o r Animation of L o g i c ) . Most tr a c e programs are s e q u e n t i a l . T h e i r output c o n s i s t s of l i n e a f t e r l i n e of t e x t , i n a t e r s e format that u s u a l l y omits important information such as assignments of values to v a r i a b l e s and the c r e a t i o n and use of data s t r u c t u r e s . The i n c l u s i o n of t h i s a d d i t i o n a l i n f o r m a t i o n to a s e q u e n t i a l t r a c e makes the output bulky and d i f f i c u l t to f o l l o w . Nevertheless, such information can be very u s e f u l i n understanding programs, and i t i s o f t e n used by human i n s t r u c t o r s i n the classroom, using such v i s u a l a i d s as flow c h a r t s , p o i n t e r s to program l i s t i n g s , data s t r u c t u r e diagrams, system o r g a n i z a t i o n charts and so on. A n i l o g teaches Prolog i n much the same way that a human i n s t r u c t o r might. I t shows the current g o a l , along with the r e l e v a n t p a r t s of the Prolog database, and i t p o i n t s to p o i n t s of i n t e r e s t as i t d e s c r i b e s what i s happening. A n i l o g l i e s i n between Dionne's A n t i c s and Lakin's Pam. I t i s not a f u l l - f l e d g e d programming language. One cannot, f o r example, write over part of the d i s p l a y e d program and have that change incorporated i n the running Prolog program. On the other hand, i t i s an i n t e r a c t i v e t r a c e ; i t can execute -43-P r o l o g programs and (to some extent) i t can c o n t r o l t h e i r e x e c u t i o n . 4.2 General Design There are two p a r t s to A n i l o g . The f i r s t i s an i n t e r a c t i v e P r o l o g t r a c e program, which produces voluminous s e q u e n t i a l ou tput . The second p a r t i s a g r a p h i c a l d i s p l a y program, which reads the output from the t r a c e and d i s p l a y s i t i n a compact g r a p h i c a l format on the t e r m i n a l s c r e e n . The two programs are intended to run c o n c u r r e n t l y , so tha t a l l of the i n t e r a c t i v e t r a c e opt ions are a v a i l a b l e a long w i t h the g r a p h i c a l d i s p l a y . When t h i s i s not p o s s i b l e (as happened i n the implementat ion) , then the two programs can be run i n sequence. One can run the t r a c e i n t e r a c t i v e l y , and then g r a p h i c a l l y d i s p l a y the r e s u l t s . The two p a r t s to A n i l o g w i l l be d e s c r i b e d s e p a r a t e l y below. A s h o r t sample p r o t o c o l for A n i l o g i s g iven at the end of Chapter One, and a more complete example may be found i n Appendix 4. 4 . 3 The Trace The s tandard P r o l o g t r a c e programs do not produce enough i n f o r m a t i o n about P r o l o g ' s database searches and about b a c k t r a c k i n g . A new t r a c e program was w r i t t e n , which does produce a l l the necessary i n f o r m a t i o n - i n c l u d i n g such t h i n g s as the -44 -database clauses that Prolog t r i e s to use to u n i f y with the c u r r e n t subgoal, and the v a r i a b l e bindings which r e s u l t . The t r a c e i s completely i n t e r a c t i v e . The user can step through the program, stopping at any of the entry, r e - e n t r y , success e x i t , and f a i l u r e e x i t p o i n t s f o r each g o a l . The user can jump over some goals, and can r e - d i r e c t the program's execution by f o r c i n g goals to succeed or to f a i l . When run s e p a r a t e l y from the g r a p h i c a l d i s p l a y program, t r a c e output i s w r i t t e n both to the terminal and to a f i l e f o r l a t e r g r a p h i c a l d i s p l a y . 4.4 The Animated D i s p l a y The animated trace appears on the terminal screen, with i n f o r m a t i o n d i s p l a y e d i n three windows - one f o r the c u r r e n t g o a l , one f o r the database, and the l a s t f o r output produced by the program being traced. The goal window shows the current goal and the l e v e l of r e c u r s i o n . The p o r t i o n of the goal that Prolog i s c u r r e n t l y working on (the current subgoal) i s h i g h l i g h t e d , and messages are produced d e s c r i b i n g the e v a l u a t i o n of the g o a l . T h i s window shows, for example, whether the current subgoal succeeds or f a i l s ; i t shows backtracking; and the i n s t a n t i a t i o n of v a r i a b l e values. The database window shows the clauses that P r o l o g accesses while t r y i n g to s a t i s f y the g o a l . Each clause that P r o l o g t r i e s to u n i f y with a subgoal i s d i s p l a y e d ; the c u r r e n t clause i s h i g h l i g h t e d ; and messages are produced to report whether u n i f i c a t i o n succeeds or f a i l s . The user window i s used to separate any output produced by the program being traced from output produced by the t r a c e program i t s e l f . When a new l e v e l of goal i s created (due to the s u c c e s s f u l u n i f i c a t i o n of a subgoal with the l e f t - h a n d s i d e of an i m p l i c a t i o n c l a u s e ) , a new goal window i s creat e d , and i s overlayed on top of the previous one. When t h i s goal i s completed, i t s window i s removed, and work resumes on the previous g o a l , which i s now uncovered. The d i s p l a y produced by the animated t r a c e has been slowed down to s u i t the average user. When i t i s not p o s s i b l e to run the animated d i s p l a y c o n c u r r e n t l y with the i n t e r a c t i v e t r a c e , the animated d i s p l a y w i l l pause p e r i o d i c a l l y and wait f o r the user to press <return>. The frequency of these stops can be c o n t r o l l e d by s e t t i n g the le a s h i n g mode (to f u l l , h a l f , or unleashed). 4 . 5 The Implementation The i n t e r a c t i v e trace p o r t i o n of A n i l o g was w r i t t e n using CProlog ( v e r s i o n 1.1). The g r a p h i c a l d i s p l a y p o r t i o n was w r i t t e n i n ' C , using the CURSES window graphics package, which i n turn uses the UNIX Termcap terminal c a p a b i l i t y database. It was i n i t i a l l y expected that the tra c e output could be piped to the g r a p h i c a l d i s p l a y , allowing both programs to run co n c u r r e n t l y . However, when t h i s was t r i e d , none of the tr a c e output was passed to the g r a p h i c a l d i s p l a y program -46 -u n t i l after the end of a CProlog session. Therefore, the Animated Trace i s not properly interactive. This si t u a t i o n would not have occurred with a more f u l l y functioned version of Prolog. Both Quintus Prolog and MProlog, for example, provide the user with an external language interface, allowing the direct use from Prolog of the necessary graphical primitives. The Animated Trace as implemented, correctly traces and displays the execution of a wide variety of small Prolog programs. For some larger programs, however, problems appeared. When the program to be traced exceeded 10 levels of recursion, or overflowed windows, information was occasionally written to the wrong part of the screen. It i s not clear to what extent this was due to bugs in the Animated Trace, and how much i t was due to problems with CURSES, and/or with Termcap. -47-Chapter Five Evaluation and Conclusions This chapter describes the procedures used to evaluate the Prolog CAI System and the Animated Trace, discusses the results of this evaluation, and presents some conclusions. 5.1 Prolog ICAI System: Evaluation Procedure Two evaluation procedures are b u i l t into the CAI system. The f i r s t i s an on-line comments f a c i l i t y . At any time during the course, a student can write comments on the course. These are stored in a f i l e which can later be edited and mailed to a system maintenance person. The other b u i l t - i n evaluation procedure i s an on-line questionnaire. After students have completed a few topics they are asked to answer some questions about the course. The questionnaire comes after the student has gained some f a m i l i a r i t y with the way the program works, but early enough that he or she w i l l s t i l l remember any d i f f i c u l t i e s in learning to use any of i t s features. Users who did not complete the questionnaire on-line were asked to complete i t by hand. The questionnaire i s reproduced on the following page. In addition to the on-line evaluation procedures, I talked informally with each of the system's users. I sat beside some of them as they were actually using i t , in order to see f i r s t hand the problems that came up. - 4 8 -P r o l o g C A I C o u r s e E v a l u a t i o n 1. How much P r o l o g d i d y o u know b e f o r e y o u s t a r t e d t h i s c o u r s e ? 2 . W h i c h o f t h e o p t i o n s ( d e s c r i b e d i n h e l p m e n u s ) h a v e y o u t r i e d ? W h i c h do y o u n e v e r u s e , a n d why? 3. How o f t e n d o y o u c h o s e t o p i c s f o r y o u r s e l f , i n s t e a d o f l e t t i n g t h e s y s t e m c h o o s e ? 4. I s t h e m a t e r i a l i n t h e c o u r s e p r e s e n t e d a t t h e r i g h t l e v e l f o r y o u ? 5 . H a v e y o u u s e d t h e T a b l e o f C o n t e n t s , t h e P r e r e q u i s i t e O u t l i n e , o r b o t h ? How u s e f u l a r e t h e y , a n d how c o u l d t h e y be i m p r o v e d ? 6 . I s t h e r e a n y t h i n g y o u w o u l d l i k e t o be a b l e t o d o , b u t c a n ' t ? 7 . W o u l d y o u r a t h e r n o t s e e t h e T o p i c M e n u s , a n d go d i r e c t l y i n t o l e s s o n s , e t c . ? 8 . A r e t h e H e l p m e s s a g e s u s e f u l ? 9. How d o e s t h i s s y s t e m c o m p a r e w i t h a n y o t h e r C A I s y s t e m s y o u h a v e u s e d , o r w i t h a P r o l o g t e x t , o r a p r o f e s s o r ? F i g u r e 7: P r o l o g C A I E v a l u a t i o n Q u e s t i o n n a i r e A b o u t a d o z e n p e o p l e p a r t i c i p a t e d i n t h e e v a l u a t i o n . F i v e o f t h e s e w e r e c o m p u t e r s c i e n c e g r a d u a t e s t u d e n t s a n d P r o f e s s o r s ; t h e r e s t h a d l i t t l e o r no p r e v i o u s e x p e r i e n c e w i t h c o m p u t e r s . A l l o f t h e u s e r s w e r e t h r o w n a t t h e s y s t e m w i t h v e r y l i t t l e p r e p a r a t i o n . T h r e e h a d p r e v i o u s e x p e r i e n c e w i t h P r o l o g , b u t t h e r e s t knew o n l y t h a t t h e y w o u l d be t a u g h t a l a n g u a g e c a l l e d P r o l o g . T h e y w e r e n o t g i v e n a n y a d v a n c e d e s c r i p t i o n o f t h e s y s t e m , o r o f P r o l o g . - 4 9 -5.2 Animated Trace: E v a l u a t i o n Procedure In h i s paper, "What S t o r i e s should we t e l l P r o l o g Students", Alan Bundy (1983) considers the advantages and the disadvantages of s i x d i f f e r e n t methods of demonstrating Prolog's proof procedure. He l i s t s 10 i d e a l s f o r a Pr o l o g s t o r y , and these w i l l be used to evaluate the Animated Trace. The Ideal Prolog Story 1. The o v e r a l l search space of the c a l l would be conveyed; i n p a r t i c u l a r , the backtracking p o i n t s would be i n d i c a t e d , and i t would be obvious when ul t i m a t e success has been a t t a i n e d . 2. The flow of c o n t r o l through the search space would be i n d i c a t e d . 3. Each subgoal l i t e r a l would be d i s p l a y e d . 4. The clauses that r e s o l v e i t away would be d i s p l a y e d . 5. The u n i f i e r s produced by these r e s o l u t i o n s would be d i s p l a y e d . 6. The remaining l i t e r a l s would be d i s p l a y e d . 7. The other clauses that could r e s o l v e with the s e l e c t e d l i t e r a l would be d i s p l a y e d . 8. The f i n a l i n s t a n t i a t i o n of the o r i g i n a l goal would be d i s p l a y e d . 9. D i f f e r e n t i n s t a n t i a t i o n s of a clause would be d i s t i n g u i s h e d . 10. The e f f e c t of a cut on the search space would be i n d i c a t e d . In a d d i t i o n , a Prolog s t o r y should not be so c l u t t e r e d with i n f o r m a t i o n as to be unreadable. Bundy notes that a l l of the s t o r i e s he st u d i e d can be extended to cover the above p o i n t s , but doing so would leave them too c l u t t e r e d to be u s e f u l f o r a l l but the simplest of problems. -50-5 . 3 P r o l o g I C A I S y s t e m : E v a l u a t i o n R e s u l t s M o s t o f t h e n a i v e u s e r s were c o n t e n t t o t y p e < r e t u r n > a n d l e t t h e s y s t e m g u i d e t h e i r s t u d i e s . O c c a s i o n a l l y , o n e w o u l d c h o o s e a t o p i c f r o m t h e T o p i c L i s t , b u t f o r t h e m o s t p a r t , t h e y d i d n o t t r y o u t most o f t h e o p t i o n s a v a i l a b l e t o t h e m . T h e m o r e a d v a n c e d u s e r s e x p e r i m e n t e d w i t h m o r e o f t h e o p t i o n s , a n d most f o u n d them u s e f u l . T h e o n l y t h i n g t h a t was r e g a r d e d a s u n n e c e s s a r y was t h e P r e r e q u i s i t e O u t l i n e ( w h i c h was s e e n a s d u p l i c a t i n g t h e f a c i l i t i e s o f t h e T o p i c L i s t ) . One c o m p l a i n t was t h a t t h e r e was n o t h i n g i n t h e s y s t e m t o g u i d e t h e u s e r s i n t h e i r c h o i c e o f t o p i c s . S i n c e t h a t i s p r e c i s e l y t h e g o a l o f t h e P r e r e q u i s i t e O u t l i n e ( s h o w i n g t h e s t r u c t u r e o f t h e c o u r s e ) , c l e a r l y i t was n o t b e i n g a s h e l p f u l a s was i n t e n d e d . S t u d e n t s who knew no P r o l o g t h o u g h t t h e c o u r s e m a t e r i a l was a t a n a p p r o p r i a t e l e v e l f o r t h e m , a n d e v e r y o n e who u s e d t h e h e l p m e s s a g e s l i k e d them ( w i t h r e s e r v a t i o n s n o t e d b e l o w ) . T h e u s e o f a m i x e d - i n i t i a t i v e d i a l o g u e w o r k e d o u t w e l l . N a i v e u s e r s t e n d e d t o l e a v e most c h o i c e s up t o t h e s y s t e m , w h i l e more e x p e r i e n c e d u s e r s ( p a r t i c u l a r l y t h o s e w i t h some P r o l o g b a c k g r o u n d ) made most d e c i s i o n s f o r t h e m s e l v e s . T h e r e was a s e r i e s o f c o m p l a i n t s a b o u t r e a d i n g t e x t f r o m a t e r m i n a l s c r e e n . Th e p r o g r a m ' s u s e r s s h o u l d h a v e b e e n p r o v i d e d w i t h a h i g h e r q u a l i t y p a p e r c o p y o f a l l o f t h e p r o g r a m ' s l e s s o n s . - 5 1 -Several students had trouble going back to review s p e c i f i c points from e a r l i e r on in the course. They would know what they wanted to review, but would not know exactly where to find i t . In general the system proved to be useful, but i t cannot stand alone. Everyone who participated in the evaluation agreed that i t was useful for learning Prolog. Most, however, had some trouble in learning how to use the system. Sophisticated users had the fewest problems. They were used to learning the ins and outs of new computer systems, and had l i t t l e trouble adjusting to this one. Naive users, on the other hand, had a great deal of d i f f i c u l t y learning to use the system unaided. The particular problems varied from individual to indi v i d u a l , but at some point each needed to be helped along. While they liked the system's help messages, the naive users wanted more. They would have preferred a natural language explanation of just what was happening, and of what was expected of them at any time. Naive users were often not familiar with the idea that there can be several ways of using a system (or modes), with different actions expected at each. They would, for example, try to address Prolog from within the CAI system without f i r s t c a l l i n g CProlog, or they would try to choose a Topic L i s t command, when they were in the middle of a lesson describing the Topic L i s t . - 5 2 -S t u d e n t s o f t e n m i s j u d g e d t h e i r own c a p a c i t y t o a b s o r b new m a t e r i a l . T h e y w o u l d r e a d s e v e r a l l e s s o n s i n a r o w , a n d t h e n go i n t o P r o l o g t o t r y many t h i n g s a t o n c e . B y t h i s t i m e , h o w e v e r , t h e y h a d f o r g o t t e n some o f t h e m a t e r i a l t h e y h a d j u s t c o v e r e d , a n d h a d t o r e t u r n t o t h e t u t o r i a l t o t r y t o f i n d i t a g a i n . To f a c i l i t a t e t h i s r e v i e w p r o c e s s , t h e p r o g r a m s h o u l d a l l o w u s e r s t o s c r o l l b a c k w a r d s t h r o u g h t h e c o u r s e , i n much t h e same way o n e c a n f l i p b a c k t h r o u g h a b o o k . A s i t s t a n d s , t h e P r o l o g C A I C o u r s e l e t s t h e u s e r s c r o l l b a c k w a r d s w i t h i n a l e s s o n , b u t n o t f r o m o n e l e s s o n o r t o p i c t o a n o t h e r . T h e c o u r s e m a t e r i a l i t s e l f c o u l d be m o r e i n t e r e s t i n g . T h e t h i n g s t h a t p e o p l e l i k e d m o s t w e r e t h e e x a m p l e s a n d t h e A n i m a t e d T r a c e ( s e e b e l o w ) . I n p a r t i c u l a r s t u d e n t s a s k e d f o r m o r e i n t e r a c t i v e e x a m p l e s . T h e y l i k e d h a v i n g a d a t a b a s e w h i c h t h e y c o u l d q u e r y a n d c h a n g e , a n d t h e y l i k e d u s i n g t h e t r a c e t o s t u d y how P r o l o g r e s p o n d e d t o t h e i r q u e r i e s a n d c h a n g e s . One g o a l f o r t h e P r o l o g C A I s y s t e m was t o be f l e x i b l e , a n d i t i s . New t o p i c s c a n be a d d e d ; o l d o n e s c a n be r e -a r r a n g e d . L e s s o n s , e x a m p l e s , a s s i g n m e n t s a n d s u m m a r i e s c a n l i k e w i s e be a d d e d o r c h a n g e d . T h e s y s t e m c o u l d e v e n be u s e d t o t e a c h t o p i c s c o m p l e t e l y u n r e l a t e d t o P r o l o g , by u s i n g a n a p p r o p r i a t e p r e r e q u i s i t e t r e e , a n d by w r i t i n g new i n s t r u c t i o n a l m o d u l e s . M o s t o f t h e p r o g r a m ' s f a c i l i t i e s w o u l d c a r r y o v e r u n c h a n g e d , a l t h o u g h t h e a b i l i t y t o e s c a p e d i r e c t l y i n t o P r o l o g w o u l d o n l y be u s e f u l - 5 3 -i f you were teaching about something that could be shown from Prolog - l i k e the Prolog debug package, or a text editor that could be call e d from Prolog. 5 . 4 The Animated Trace: Evaluation Results The Animated Trace s a t i s f i e s most of Bundy's c r i t e r i a for a good Prolog story. Backtracking i s shown; i t i s obvious when ultimate success (or failure) is reached; the flow of control i s displayed; each subgoal l i t e r a l i s shown, along with the clauses that resolve i t away; the u n i f i e r s produced are shown, as are the remaining l i t e r a l s ; clauses not in the f i n a l solution path are s t i l l shown when they are t r i e d during a proof; the f i n a l instantiation of the o r i g i n a l goal i s displayed; and the effect of a cut i s shown, not so much on the search space, but on the movement of the proof procedure through a goal. The Animated Trace (as implemented) p a r t i a l l y f a i l s points 7 and 9. It does not show clauses unless they are t r i e d during a proof, and i t does not show the instantiations of database clauses. There i s , however, no conceptual reason why i t could not do both of these things, and indeed i t would be a f a i r l y simple task to include them. The main f a i l i n g of the Animated Trace relates to showing the entire search space. It shows that portion of the search space which i s traversed during a proof, including blind a l l e y s , but i t has no way of showing the remainder (things that might have been). This means i t f a l l s short of the ideal for points 7 and 10 as well. Clauses which could resolve with the selected l i t e r a l are shown only when they are tr i e d during a proof. When they are not tr i e d , they are not shown. Similarly, the effect of a cut i s only shown on that portion of the search space which i s investigated during a proof. When altered to cover points 7 and 9, the Animated Trace comes nearer to the "ideal Prolog story" than do any of the stories Bundy describes. Furthermore, i t displays i t s information in a more concise and more easily followed format than they do. 5 . 5 Conclusions In this research I have t r i e d to show how Computer Assisted Instruction can be improved through the use of A r t i f i c i a l Intelligence techniques, and good teaching s t o r i e s . The Prolog ICAI program and the Prolog Animated Trace were designed to be f l e x i b l e and easy to use. These goals have been successfully met. The And/Or Prerequisite Tree proved to be a natural way to represent the structure of the domain. As added benefits, t h i s structure was easily created and searched, and i t helped make the course f l e x i b l e and easy to change. The Prolog CAI program uses a very simple student model a subset of the Prerequisite Tree. While simple, t h i s student model proved to be entirely adequate. Other, more -55-authoritarian, CAI programs require highly complex student models to reduce their chances of making bad decisions. The Prolog CAI program can make do with a simple student model because i t has the student's help with every decision i t makes. The Animated Trace worked especially well in demonstrating Prolog's proof procedure. Students could use i t both to study examples from the CAI course and to follow the execution of their own programs. By using graphics i t gives more information than t r a d i t i o n a l Prolog trace programs, without swamping the student with d e t a i l s . Future versions of the Animated Trace should be more f u l l y interactive. Ideally, students should be able to change the database, rewrite part of the goal, or a l t e r the flow of execution while the trace i s in progress. The problems that were encountered in this research were largely the result of inadequate tools. CProlog version 1.1 i s en t i r e l y lacking in access to the graphical primitives necessary for the Animated Trace, while the poor quality of text on the display made i t a chore for students to read through a l l the lessons. Future users of the CAI program should be provided with a high resolution workstation. Aside from i t s lack of graphics, Prolog proved to be a nice language for the implementation. The construction and traversal of the prerequisite tree was p a r t i c u l a r l y simple in Prolog, as was the coding of a modified Prolog interpreter which provided information needed by the Animated Trace. - 5 6 -T h e P r o l o g CAI p r o g r a m ' s l e s s o n s c o v e r m o s t o f t h e f e a t u r e s o f C P r o l o g , b u t t h e t r e a t m e n t i s a t t i m e s s p a r s e . M o r e work n e e d s t o be d o n e t o r e v i s e a n d e x p a n d u p o n t h e l e s s o n m a t e r i a l , a n d t o p r o v i d e more e x a m p l e s a n d s u m m a r i e s . A s m o o t h e r m e t h o d o f p a g i n g f o r w a r d a n d b a c k t h r o u g h t h e c o u r s e m a t e r i a l s h o u l d be i m p l e m e n t e d , a n d t h e d i s p l a y o f t h e P r e r e q u i s i t e T r e e s h o u l d be i m p r o v e d . O v e r a l l t h o u g h , t h e p r o g r a m s h a v e shown t h a t w e d d i n g A r t i f i c i a l I n t e l l i g e n c e t e c h n i q u e s w i t h g o o d t e a c h i n g s t o r i e s c a n be u s e d t o i m p r o v e C o m p u t e r A i d e d I n s t r u c t i o n . -57-References [I] Barr, A. and Feigenbaum, E. eds (1982), The Handbook of  A r t i f i c i a l Intelligence, Vol. II, Heuristech Press, Stanford C a l i f o r n i a . [2] Borning, Alan (1979), Thinglab - A Constraint Oriented Simulation Laboratory, Stanford Computer Science Report, STAN-CS-79-749, Standord University, C a l i f o r n i a . [3] Bundy, Alan (1983), What Stories Should We T e l l Prolog Students?, DAI working paper #156, University of Edinburgh, Edinburgh, Scotland. [4] Burton, R.R., Rubinstein, R. and Brown, J.S. (1976), A Reactive Learning Environment for Computer-Assisted Learning, Bolt, Beranek, and Neuman, BBN report #3314, Cambridge Mass. [5] Burton, R.R. and Brown, J.S. (1977), A Paradigmatic Example of an AI Instructional System, F i r s t International Conference on Applied Systems Research, New York. [6] Carbonell, J.S. (1970), Mixed-initiative Man-Computer Instructional Dialogues, Bolt Beranek, and Neuman, Technical Report. [7] Clancey, W. (1979), Tutoring Rules for Guiding a Case Method Dialogue, In Intelligent Tutoring Systems (Sleeman, D. and Brown, J.S. eds), pp. 201-225, Academic Press, London, U.K. [8] Clancey, W. (1987), Methodology for Building an Intelligent Tutoring System, In A r t i f i c i a l Intelligence  and Instruction (Kearsley, G. ed.), Chapter 9, Addison-Wesley. [9] Clocksin, W.F., and Mellish, C.S., (1981), Programming  in Prolog, Springer-Verlag, Berlin-Heidelberg-New York. [10] Colbourn, M. (1982), An Expert System for the Diagnosis of Reading D i f f i c u l t i e s , Proceedings of Expert Systems, Engham, England. [II] Curran, W.S. (1982), A Teacher/Learner, SIGCSE B u l l e t i n , Vol. 14, No. 1, pp. 229-231. [12] Crawford, S. (1981), A Standards Guide for the Authoring of Instructional Software, Joint Education Management (JEM) Research, V i c t o r i a , B r i t i s h Columbia. -58-[13] Dageforde, M. and Beard, M.H. (1978), The BASIC Instructional Program Supervisor's Manual, ERIC Educational Database, microfiche #2902. [14] Dionne, M.S. and Mackworth, A.K. (1978), ANTICS: A System for Animating LISP Programs, Computer Graphics and Image Processing, Vol. 7, No. 1. [15] diSessa, A. (1986), Principles for the Design of an Integrated Computational Environment for Education, in Children in an Information Age (Sendov, B. and Stanchev 1. eds.), Pergamon Press, Oxford, U.K. [16] Fine, G. (1980), The Design of an Intelligent Lisp CAI Tutor, M.Sc. Thesis, University of B r i t i s h Columbia, Vancouver, B.C. [17] Fogel, E. (1982), Computers and Education, Honours Research Project, Carleton University, Ottawa, Ontario. [18] Fogel, E. (1983), A Guide to Intelligent Computer Assisted Instruction, Class essay, CPSC 522, University of B r i t i s h Columbia, Vancouver, B.C. [19] Forman, D. (1982), Search of the Literature, in Instructional Use of Microcomputers, B r i t i s h Columbia Ministry of Education, V i c t o r i a , B.C. [20] Goldstein, I. (1979), The Genetic Graph: A Representation for the Evolution of Proceedural Knowledge, International Journal of Man-Machine Studies, Vol 11, No. 1, pp. 51-77. [21] Hofstetter, F.T. (1981), Using the PLATO System, ECCO Newsletter, Vol. 2, No. 3, pp. 23-32, Educational Computing Organization of Ontario, Ontario. [22] Johnson, L. and Soloway, E. (1987) Proust, in A r t i f i c i a l Intelligence and Instruction, (Kearsley, G. ed), Chapter 3, Addison-Wesley. [23] Jones, M. ed. (1986), Computational Intelligence, Special Issue: AI Approaches to Education, Vol. 2, No. 2, National Research Council of Canada, Canada. [24] Kearsley, G. ed. (1987), A r t i f i c i a l Intelligence and  Instruction, Addison-Wesley, 1987. [25] Kimball, R. (1973), A Self-Improving Tutor for Symbolic Integration, Intelligent Tutoring Systems, (Sleeman, D. and Brown, J.S. eds), pp. 201-225, Academic Press, London, U.K. -59-[26] Kowalski, R. (1979), A r t i f i c i a l Intelligence Series: Logic for Problem Solving, North Holland. [27] Laubsch, J. and Eisenstadt, M. (1981) Domain Spec i f i c Debugging Aids for Novice Programmers, IJCAI-81, pp. 962-969. [28] Lakin, F. (1980), Computing with Text-Graphic Forms, Proceedings of the Lisp Conference at Stanford University, Stanford, C a l i f o r n i a . [29] London B. and Clancey, W. (1982), Plan Recognition Strategies in Student Modelling: Prediction and Description, Stanford University Technical Report, STAN-CS-82-909, Stanford, C a l i f o r n i a . [30] Looi, C. (1984), Explorations of Programming Learning Behavior of Novices through Computer Aided Learning, M. Sc. Thesis, University of B r i t i s h Columbia, Vancouver, B.C. [31] Matz, M. (1982), Towards a Process Model for High School Algebra Errors, in Intelligent Tutoring Systems, (Sleeman, D. and Brown, J.S. eds), pp. 201-225, Academic Press, London, U.K. [32] McCalla, G., Peachey, D. and Ward, B. (1982), An Architecture for the Design of Large Scale In t e l l i g e n t Teaching Systems, 1982. [33] McCalla, G., Bunt, R. and Harms, J. (1986), The Design of the Scent Automated Advisor, in Computational Intelligence, Vol 2., No. 2, National Research Council of Canada, Canada. [34] O'Shea, T. (1979), Self-Improving Teaching Systems, in Intel l i g e n t Tutoring Systems, (Sleeman, D. and Brown, J.S. eds), pp. 201-225, Academic Press, London, U.K. [35] Papert, S. (1980), Mindstorms: Children, Computers and  Ideas, Basic Books, New York. [36] Peachey, D. (1982), An Architecture for Plan-Based Computer Assisted Instruction, M.Sc. Thesis, University of Saskatchewan, Saskatoon, Saskatchewan. [37] Ragsdale, R. (1982), Computers in the Schools: a Guide for Planning, Ontario Institute for Studies in Education Press, Toronto, Ontario. [38] Searle, J.R. (1980), Minds, Brains, and Programs, The Behavioral and Brain Sciences, Vol. 3, pp. 417-422, Cambridge University Press, Cambridge, England. -60-t [39] Self, J. (1974), Student Models in Computer-Aided Instruction, International Journal of Man-Machine Studies, Vol. 6, pp. 261-276. [40] Sleeman, D. and Brown, J.S. (1982), In t e l l i g e n t  Tutoring Systems, Academic Press, London, U.K. [41] Soloway, E., Woolf, B., Rubin, E. and Barth, P. (1983), MENO-II: An Intelligent Tutoring System for Novice Programmers, IJCAI-81, pp. 975-977. [42] Soloway, E., Woolf, B., Rubin, E., Barth, P., Bonar, J. and E r l i c h , K. (1981), Why your Students Write Those Crazy Programs, Proceedings of the National Educational Computing Conference, Texas, USA. [43] Stephens, A., C o l l i n s , A. and Goldin, S.E. (1982), Misconceptions in Students' Understanding, in Intelligent Tutoring Systems, (Sleeman, D. and Brown, J.S. eds), pp. 201-225, Academic Press, London, U.K. [44] Suppes, P. (1972), Computer Assisted Instruction, in Display Use for Man-Machine Dialog (Handler, W. and Weizenbaum, J. eds), Munich, West Germany. [45] Weizenbaum, J. (1965), ELIZA-A Computer Program for the Study of Natural Language Communication between Man and Machine, Communications of the ACM, Vol. 9, pp. 36-45. [46] Yazdani, M. (1984), New Horizons in Educational  Computing, John Wiley & Sons, Rexdale, Ontario. -61-APPENDIX 1 - T h e A n d / O r P r e r e q u i s i t e T r e e A p o r t i o n o f t h i s t r e e i s shown g r a p h i c a l l y , t h e n t h e i n t e r n a l r e p r e s e n t a t i o n f o r t h a t p o r t i o n o f t h e t r e e i s g i v e n . F i n a l l y , t h e e n t i r e t r e e i s g i v e n , i n t h e same m a n n e r t h a t i t i s shown t o s t u d e n t s u s i n g t h e c o u r s e . A n d / O r T r e e : G r a p h i c a l R e p r e s e n t a t i o n P r o l o g S y n t a x OR I n t r o d u c t i o n t o P r o l o g A Q u i c k L o o k a t P r o l o g I n t r o d u c t i o n t o L o g i c U s i n g t h e T u t o r i a l A n d / O r T r e e : I n t e r n a l R e p r e s e n t a t i o n p r e r e q ( ' A Q u i c k L o o k a t P r o l o g ' , ' I n t r o d u c t i o n t o P r o l o g ' ) . p r e r e q ( ' U s i n g T h i s T u t o r i a l ' , ' I n t r o d u c t i o n t o P r o l o g ' ) . p r e r e q ( ' U s i n g T h i s T u t o r i a l ' , ' I n t r o d u c t i o n t o L o g i c ' ) . o r p r e r e q ( ' I n t r o d u c t i o n t o P r o l o g ' , ' S y n t a x ' ) . o r p r e r e q ( ' I n t r o d u c t i o n t o L o g i c ' , ' S y n t a x ' ) - 6 2 -A n d / O r T r e e : U s e r ' s V i e w P r o l o g B a s i c s P r o o f P r o c e d u r e U n i f i c a t i o n S e m a n t i c s - I n t r o d u c t i o n t o P r o l o g A Q u i c k L o o k a t P r o l o g U s i n g T h i s T u t o r i a l - I n t r o d u c t i o n t o L o g i c U s i n g t h i s T u t o r i a l S i d e - e f f e c t s S y n t a x - I n t r o d u c t i o n t o P r o l o g - I n t r o d u c t i o n t o L o g i c B u i l t - i n P r e d i c a t e s I n p u t / O u t p u t S i d e - e f f e c t s F i l e A c c e s s C h a r a c t e r I / O T e r m I / O R e a d i n g - i n P r o g r a m s A r i t h m e t i c O p e r a t o r s S y n t a x C o n v e n i e n c e C o n t r o l o f E x e c u t i o n T h e C u t C o n t r o l o f E x e c u t i o n C o m p a r i s o n o f T e r m s M e t a - L o g i c a l D e b u g g i n g S e t s P r o g r a m I n f o r m a t i o n E n v i r o n m e n t C h a n g i n g t h e D a t a B a s e I n t e r n a l D a t a B a s e D e f i n i t e C l a u s e Grammars S y n t a x E a c h t o p i c i s shown w i t h i t s p r e r e q u i s i t e s i n d e n t e d b e n e a t h i t . ' O r ' p r e r e q u i s i t e s a r e i n d i c a t e d w i t h a p r e c e e d i n g m i n u s s i g n . F o r c o n c i s e n e s s , a t o p i c ' s p r e r e q u i s i t e s a r e o n l y shown o n c e , t h e f i r s t t i m e t h a t t h e t o p i c a p p e a r s . - 6 3 -APPENDIX 2 - Prolog ICAI User's Manual STARTING UP Assuming the CAI system i s in a f i l e called ' c a i f i l e ' , type: CProlog (Call CProlog from the shell) [ c a i f i l e ] . (Load the system) c a i . (Remember the period!) lines(N). (where N i s the number of lines on your terminal) If N = 60, you can skip t h i s . If N < 40, things won't f i t on the screen. LEAVING THE SYSTEM Type either: CProlog (puts you in CProlog) save (saves what you've done, then puts you in CProlog) LEAVING CPROLOG Type 'cai.' to resume the t u t o r i a l , Type 'halt.' to quit. Remember the P.E.R.I.O.D.S. RESTORING SAVED STATES Suppose the state i s in f i l e 'oldstate'. Next time you start CProlog, type: CProlog oldstate COMMENTS, GRIPES, ETC. Mail them to me. From within the system, type 'comment'. Everything that you type from then on, u n t i l an end-of-file (tD or -rC), w i l l be put into a f i l e called 'mailtofogel'. You can figure out what to do with that yourself. -64-APPENDIX 3 - Anilog Users Manual STARTING UP Anilog's input i s the output from a special CProlog trace program. If that i s in a f i l e called 'traceout': Type: anilog traceout USING ANILOG At times, Anilog pauses to l e t you think about what you are seeing. Here i s what you can type at these times, <cr> - continue the trace quit - abort the trace f u l l - set leashing to f u l l (pause more often) half - set leashing to half (pause occasionally) unleash - turn off leashing (never pause for input) BUGS Anilog i s not robust, and i s not guaranteed to work on arbitrary Prolog goals. When i t bombs, the terminal may be in an unusual state. To get i t back to normal, type: <linefeed> (NOT return) reset (NOT the reset key, type the l e t t e r s r e s e t ) <linefeed> MAKING NEW INPUT FILES Load the f i l e ~fogel/cai/trace/trace into CProlog. C a l l mytrace(G), where G i s the goal to be traced. eg. ?- mytrace( (write(hi), write(hi)) ). Output w i l l be displayed on the terminal, and w i l l also be written to a f i l e named 'traceout' in your current directory. - 6 5 -APPENDIX 4 - Animated Trace Example The Example Program and Query: i _ l i k e ( r i c e ) . i_like(Thing) :- has_fur(Thing). i_like(Thing) :- can_walk(Thing), can_talk(Thing). has_fur(dog). can_walk(X) :- person(X). can_talk(radio). can_talk(X) :- person(X). person(marc). ?- i _ l i k e ( Y ) , has_fur(Y), write(Y). - 66 -Prolog Animated Trace Current Goal: (Level 1) i _ l i k e ( Y ) , has_fur(Y), write(Y). Prolog Database: User Output: - 67 -Prolog Animated Trace Current Goal: (Level 1) | i _ l i k e ( Y ) , <— current subgoal |has_fur(Y), Iwrite(Y). Prolog Database: i _ l i k e ( r i c e ) . <- try to unify with subgoal User Output: - 68 -Prolog Animated Trace Current Goal: (Level 1) | i _ l i k e ( Y ) , <— current subgoal |has_fur(Y), Iwrite(Y). Prolog Database: i l i k e ( r i c e ) . <- unified User Output: Prolog Animated Trace Current Goal: (Level 1) I i _ l i k e ( r i c e ) , <— s u c c e s s | h a s _ f u r(Y), I w r i t e ( Y ) . Prolog Database: User Output: - 70 -Prolog Animated Trace Current Goal: (Level 1) I i _ l i k e ( r i c e ) , Ihas_fur(rice), <-- current subgoal Iwrite(Y). Prolog Database: has_fur(dog). <— try to unify with subgoal User Output: - 71 -Prolog Animated Trace Current Goal: (Level 1) I i _ l i k e ( r i c e ) , I h a s _ f u r ( r i c e ) , <— c u r r e n t s u b g o a l I w r i t e ( Y ) . Prolog D a t a b a s e : h a s _ f u r ( d o g ) . <— n o t u n i f i e d User Output: Prolog Animated Trace Current Goal: (Level 1) i _ l i k e ( r i c e ) , h a s _fur(rice), <-- f a i l e d write(Y). Prolog Database: User Output: Prolog Animated Trace Current Goal: (Level 1) i _ l i k e ( Y ) , <— redo subgoal has_fur(Y), write(Y). Prolog Database: i _ l i k e ( r i c e ) . i_like(Thing) :- has_fur(Thing). <— try to unify with subgoal User Output: Prolog Animated Trace Current Goal: (Level 1) | i _ l i k e ( Y ) , <— redo subgoal |has_fur(Y), Iwrite(Y). Prolog Database: i _ l i k e ( r i c e ) . i_like(Thing) :- has_fur(Thing). <-- unified User Output: Prolog Animated Trace Current Goal: (Level 1) I Current Goal: (Level 2) I|has_fur(Thing). <— current subgoal Prolog Database: Ihas_fur(dog). <-- try to unify with subgoal User Output: - 76 -Prolog Animated Trace Current Goal: (Level 1) Current Goal: (Level 2) Ihas_fur(Thing). <— current subgoal Prolog Database: has_fur(dog). <— unified User Output: - 77 -P r o l o g An imated T r a c e C u r r e n t G o a l : ( L e v e l 1.) I C u r r e n t G o a l : ( L e v e l 2) I 11 has f u r ( d o g ) . 1 1 1 1 1 1 G o a l s u c c e e d s I I I I I I I I P r o l o g D a t a b a s e : U se r O u t p u t : - 78 -Prolog Animated Trace Current Goal: (Level 1) I i _ l i k e ( d o g ) , <— s u c c e s s | h a s _ f u r(Y), I w r i t e ( Y ) . Prolog Database: User Output: P r o l o g An imated T r a c e C u r r e n t G o a l : ( L e v e l 1) I i _ l i k e ( d o g ) , I h a s _ f u r ( d o g ) , <— c u r r e n t s u b g o a l I w r i t e ( Y ) . P r o l o g D a t a b a s e : h a s _ f u r ( d o g ) . <— t r y t o u n i f y w i t h s u b g o a l U se r O u t p u t : - 80 -Prolog Animated Trace Current Goal: (Level 1) I i _ l i k e ( d o g ) , Ihas_fur(dog), <— current subgoal Iwrite(Y). Prolog Database: has_fur(dog). <— unified User Output: - 81 -Prolog Animated Trace Current Goal: (Level 1) I i _ l i k e ( d o g ) , I h a s _ f u r ( d o g ) , <— s u c c e s s I w r i t e ( Y ) . Prolog Database: User Output: P r o l o g An imated T r a c e C u r r e n t G o a l : ( L e v e l 1) I i _ l i k e ( d o g ) , I h a s _ f u r ( d o g ) , I w r i t e ( d o g ) . <— c u r r e n t s u b g o a l P r o l o g D a t a b a s e : U s e r O u t p u t : Prolog Animated Trace Current Goal: (Level 1) I i_like(dog), ihas_fur(dog), Iwrite(dog). <— B u i l t - i n Succeeds Prolog Database: User Output: dog - 84 -Prolog Animated Trace Current Goal: (Level 1) I i _ l i k e ( d o g ) , Ihas_fur(dog), Iwrite(dog). <— Goal succeeds Prolog Database: User Output: dog 

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-0051936/manifest

Comment

Related Items