Beverly Park Woolf, Eric Rubin, Paul Barth: Meno-II: An Intelligent Tutoring System for Novice Programmers

Introduction

We all know and grumble --about the error messages that one gets from a computer system. That problem is magnified for the novice programmer who is learning a first programming language. With the number of individuals who are learning programming rapidly growing, there is a clear need for intelligent tutoring systems which can assist the novice at a most critical time: when he/she is alone, one-on-one; with thP. beast.

Objectives and Status of System

We are building an intelligent tutoring system, Heno-II, tailored to the needs of novice Pascal programmers. The goals of Heno-II are:

• catch run-time (semantic and pragmatic) bugs in the- student programs ··
• focus on introductory programs: straight line, branching, simple looping.
• must be fast and robust; at least 851 of student programs are buggy
• suggest misconceptions in the students' heads
• which underlie the bugs
• "talk" in language which is close to programming so student will understand

· This work was supported by the Army Research Institute for the Behavioral and Social Sciences, under .ARI Grant No. HDA903-80-C-0508. Any opinions, findings, conclusions or recommendations expressed in this report are those of the authors, and do not necessarily reflect the views of the u.s. Government.

·· While interesting, we are not concerning ourselves with syntax errors (see [1 1]).

MENO-II: AN INTELLIGENT TUTORING SYSTEM FOR NOVICE PROGRAMMERS ·

Elliot H. Soloway, Beverly Woolf, Eric Rubin, and Paul Barth

Computer and Information Science Department University of Massachusetts

Amherst, Massachusetts 01003

• instruct/tutor the student with respect to
• the misconceptions.

The current status of the system corresponding to these objectives is:

• Heno-II can find over two dozen bugs with
• respect to repetition and assignment
• Heno-II can suggest underlying misconceptions
• for a subset of those bugs
• tutoring has not yet been implemented in
• He no-II.

Leverage on Program Understanding: The ~ Finder

The Bug Finder must be able to recognize two types of bugs: problem independent ones, and problem dependent ones. An example of the former type is the explicit inclusion of an increment to the index variable in a for loop. Bugs of this sort reflect confusion about the semantics of the various programming language constructs.

In order to recognize problem dependent bugs, however, the Bug Finder must be told what the program is supposed to do; oftentimes a student program will run, but it will solve the "wrong" problem. For example, in Figure 1a, we depict a problem .for which the the program in Figure 1b is the correct solution; the program in Figure 1c does not solve the problem, but does in fact execute. In other intelligent tutoring systems, the student provided a specificiation of the goals of the program (e.g., [3]). In contrast, our approach is to have the teacher provide the specification, since everyone in the course will be working on the same problem.

The vehicle for this "intention specification" is a Problem Description Language (PDL) which we are developing for introductory programming problems. The PDL allows us to specify the components of a program solution to the intended problem. In Figure 2, the PDL solution for the problem in Figure 1 is given.

This language is based on what an expert prcgrammer might know about problems of this type. In particular, this knowledge is focussed on types of looping plans and the various roles which variables play in programs. For examplP., the program in Figure 1h illustrates what we call the New Value Controlled Running Total Loop Plan; it is }ust a special case of the- Running Total Loop Plan, in which the loop, while accumulating a total, is controlled by the value of the read variable (i.e., the New Value Variable). This knowledge is described at greater length in [8]. This characterization of programming knowledge draws on the work of [3], [5], [6], and [11].

The Bug Finder is given a POL specification of the program solution; currently this is in a procedural form, but eventually it will be table driven. The Bug Finder then parses as a student program into a syntax tree representation. In order to facilitate speedy retrieval, this structure has been augmented with: (1) extra links (e.g., all occurrences of a variable are chained together), (2) semantic annotations at a node which summarize the subtree below (e.g., the statement i:=i+1 would be summarized as "increment-by-one"). The POL solution description is then matched against this augmented parse tree. For example, in comparing the description in Figure 2 with the program in Figure 1c, the Bug Finder recognizes that the New Value Variable, Score, should have been modified in the loop by a read, as opposed to being modified like a counter. Bugs are then reported to the Tutor Module (described below).

The guiding metaphor of the Bug Finder is pattern matching at the loop plan level. Thus, two different programs, which solve the same problem can be recognized as such. The Bug Finder keys off the loop being used and calls in knowledge specialized to that particular loop to help in the matching. Currently, the Bug Finder does not do exhaustive control or data flow analysis; it does do spatial data flow analysis to recognize that:

X : = Sum;

Sum := X + Nu_Value;

is equivalent to Sum := Sum + Nu Value. Nor do we map the progam into a logic formalism and do the analysis in this latter representation; we feel that without extensive translation the explanation that would result from this type of approach would be "to far away" from the student's understanding of the program to be of much help.

Tying Bugs to Misconceptions: the Student Building ~Hodel of

Given a bug in the program, one needs to infer the underlying misconceptions, in the head of the student, which could have caused the bug ([2]). Based on the expert's plan knowledge we have built a knowledge network, the Competence Hodel, which describes the correct components of a loop and their relationships. We also have built a ~ Hodel which specifies the surface characteristics in the program of the common bugs which we have identified ([7], [8]). Finally, a set of inference routines tie the Bug Hodel to the Competence Hodel in order to derive the Performance Hodel, i.e., a model of the student's possible misconceptions. Both the Bug Hodel and the Competence Hodel are implemented in a version of KL-ONE ([1]) which we have augmented with some special arcs to facilitate quick retrieval.

For example, the bug in the program in Figure 1c could have been caused by the following misconceptions, which would be inferred by our Tutor Module: (1) the student simply misunderstood the problem, (2) the student did not understand how to get new, successive values, or (3) the student did not understand how the read statement worked. For example, the student might have thought that the variable Score was declared to be of "type read" and that if 1 were to be added to it, then the system "would know" to. do a read.

Currently, the Competence Hodel contains about 200 concepts which represent loop plans, variable roles, and the various relationships among these entities. The Bug Model contains approximately 50 bugs associated primarily with the improper initialization and modification of various variables. We are expanding both networks, and we are developing rules which can better diagnose misconceptions (e.g., if there are multiple, related bugs, then this should help focus the diagnosis). Stilt to be worked in is the history of the student's interactions.

Tutoring

The current system functions as a "smart compiler"; it finds bugs, diagnoses misconceptions, and simply lists this analysis to the student. We plan to have the Tutor engage in a dialogue with the student for better diagnosis and instruction purposes. However, we do not plan on allowing the user to communicate via natural language; rather, we plan to use dynamically generated multiple choice questions presented via a menu screen. We will, however, allow the user to submit program fragments in response to questions from the system. With this system, we want to explore the range of possible interaction scenarios. In particular, our objective is to "parameterize" the amount and type of interaction in order to instruct along the continuum from tutoring ([9]) to coaching ([4)).

Concluding Remarks

There underlie questions. are a number of assumptio~s which our approach, and which are still open For example:

1. Can we define a POL sufficient problems under that this will affirmative. consideration? be answered for the We feel in the
2. Will the pattern matching approach, without exhaustive data or control flow analysis be sufficient to handle the looping problems? Can this be extended to handle programs with procedures? Can we continue heuristically handling questions that typically required rigorous deduction systems? These are the the most troublesome questions.

1. Will our analysis, in terms of plans and variable roles, provide enough leverage into the students' thinking? Since we do not see the history of the design, as Hiller's SPADE-0 system does ([5]), it is unclear whether we can sufficiently reconstruct the student's plan ·from simply the raw code.

These are empirical questions which we plan to explore through tests of the system. In the fall semester of 1981, we plan to try out Heno-II in a class of 700 students taking introductory Pascal programming. They certainly will exercise the system, and tax it to its limits.