A Student-Oriented Natural Language Environment For Learning LISP

Introduction

Aa an application area of Artificial Intelli­ gence, computer-aided instruction (CAl), has re­ ceived considerable interest (1). Carbonell's SCHOLAR (2) is perhaps the best known example of a "mixed-initiative" CAl system. Through SCHOLAR, students can ask questions about concepts relevant

to the geography of South America.

Koffman and Blount (3) have developed a sys­ tem to teach machine-language programming. This system can generate programming problems, and mon­ itor and assist students in coding their solution programs. This system concatenates a small set of problem primitives and associated solution rou­ tines in order to create and solve meaningful pro­

gr~ing problems.

Natural language understanding is becoming more important in CAl system. Many powerful par­ sers have been developed. for very extensive sub­ sets of English including Wood's parser (4) and Winograd's PROGRAMMER (5). These methods are be­ ginning to be of use for question answering sub­ systems and for interpreting student responses. Of particular interest is the work done by Brown et al (6). It is his semantically driven fuzzy

graMmar that has influenced this research .

Brown analyzed student scenarios involving electronic circuit trouble-shooting and discovered that the concepts and items discussed fell into

small numbers of semantic groupings or categories.

These included : measurements, control set­ tings, circuit elements, and circuit locations re­ lative to the electronic circuit. The parse was then accomplished by anticipating and looking for phrases which matched these semantic categories where they might be appropriate. The parser's fuzziness stems from the fact that words that are not understood can be skipped over .

Teaching a programming language embraces two major tasks. One is presenting new material in an

A STUDENT-ORIENTED NATURAL LANGUAGE ENVIRONMENT FOR LEARNING LISP

Richard 0. Hart University of New Hampshire Durham, New Hampshire

Elliot B. Koffman Temple University Philadelphia, Pennsylvania

orderly controlled fashion. The other involves making available a friendly, informative environ­ ment that allows experimentation, and that can re­ cognize errors and misconceptions and point them out. With ISLE (Interactive Student LISP Environ­ ment) we have concentrated on this second item by developing a computer-based environment for LISP. The system knows about the structure and semantics of the LISP language and can answer questions about LISP data structures, concepts and functions; both those functions defined ~y the student and the primitives internal to the system.

As an example consider the following dialogue:

STUDENT:

MACHINE:

STUDENT:

MACHINE:

Is Atom a function?

Yea, Atom is aubr.

How many arguments does it take?

Atom is a subr and takes 1 argument.

Notice that questions are answered with a complete statement to avoid any ambiguity, also note the use of the pronoun it by the student. Some limited anapboric ·reference is permitted by

the system to allow a more natural dialogue.

STUDENT: Describe it.

MACHINE: Atom is a subr. and a predicate func­ tion. It returns true (the Atom T) if ita argument is an atom, nil other­ wise.

STUDENT~

MACHINE:

'!-!hat is an Atom?

An Atom is the most elementary type of a-expression. It may be either a number or a literal atom.

Some words like atom can refer to more than one thing. The correct reference is found by look­ ing at the context of the word and making a de­ cision baaed on plural markers, determiners, or qualifying adjectives.

STUDENT:

MACHINE:

Are property lists kinds of lists? A property or P list is an alternating list of literal atom property names and corresponding property values. It can be searched using the function GET.

Subset-superset and part-part of relationships are used extensively by the system for answering questions of this type. A yes answer is implied here by giving the student a definition of the sub­ set item.

STUDENT: DEFINE ( ( (FACT (LAMBDA (X) (COND

((ZEROO X) 1)

(T (TIMES X (FACT (SUBl X)))))))))))

MACHINE: Arguments for Evalquote: DEFINE (((FACT (LAMBDA (X) (COND((ZEROO X) L) (T(TIMES X (FACT (SUBl X))))))))) VALUE IS: (FACT)

Any student input that has the form of a func­ tion followed by an argument list is assumed to be input for the evaluator. Here the student defines a function to compute factorials.

STUDENT: FACT (3)) MACHINE: Arguments for Evalquote: (3) VALUE IS: Undefined function found. It is ZEROO found in the function fact.

In defining FACT the student mistyped ZEROP. The error is found during evaluation and returned to the student. Notice that terminating symbols are necessary at the end of each student input line. They may be periods, question marks or an extra right parenthesis.

STUDENT: MACHINE: PRINT FACT

(LAMBDA (X) (COND & &))

When printing function definitions, only the highest elements of the definition appear; lower level structures are replaced with &.

STUDENT:

MACHINE:

3 2 P.

((ZEROO X) 1)

Now using commands to the editor, the student looks at the lower level where he remembers ZEROP should go.

STUDENT: MACHINE: 1 (1 ZEROP) P. (ZEROP X)

The error is now corrected and this can be checked by evaluation or by asking another ques­ tion.

STUDENT: Does FACT call any undefined func­ tions? MACHINE: FACT calls no undefined functions. STUDENT: MACHINE: FACT (3)) Arguments for Evalquote. FACT (3) VALUE IS: 6

System Organization

The system is built around several submodules as shown in figure 1. Each student command or re­ quest is received by the monitor where it is clas­ sified as input for either the editor, the eval­ uator, or the parser. Any input which is not either a list of edit commands or a function fol­ lowed by an argument list is assumed to be a re­ quest for information and so is passed to the parser. Anything the parser cannot handle is re­ jected and the student is asked to rephrase or break up the question.

The parser and the semantic rountines work together to answer factual questions about the LISP language, its data structures and functions, and about the functions the student has defined. The parse mechanism has a semantic basis in that specific words or phrases are looked for that re­ fer to things the system knows about, i.e., func­ tions, definitions, or entries in the semantic network. These items are divided into groups or categories that are semantically similar.

Semantically similar items are those that might fit in a given slot in a sentence or ques­ tion, and that fall into a superset classification such as data structures or function names. The result of the parse is an executable LISP function whose evaluation causes a response to be generated for the student.

The evaluator evaluates student functions when called upon, accepting nearly any LISP 1.5 constructions. When student errors are found, it reports the type of error and in what function it occured to the student. Editor commands can be used to look around inside of function definitions and to insert, delete, and change parts of the

definition.

Semantic ~ategories

The ISLE system uses four semantic categor­ ies. These categories allow the parser to be somewhat selective in choosing what to look for next while processing the student's input. The semantic categories are the following: (1) Func­ tions (2) function types (3) data structures (4) other general concepts.

Each semantic category is represented in the implementation by a LISP function which will check, beginning at the head of the current sen­ tence, for a phrase that matches an element in that category. Depending on the fuzziness set by the grammar at that moment, one or more of the initial words in the current sentence may be skipped.

The first semantic category is that of func­ tion names. It is represented in the grammar by FNNAME. This category consists of all functions that are currently defined in the system; that is, all SUBRS and FSUBRS plus any functions that may have been defined as EXPRS or FEXPRS by the user. FNNAME and the other three semantic cate­ gory matching routines all operate in the same manner. They operate like any other grammar rule function in that they accept some tail of the in­ put sentence. They can return NIL if they find no match at some point in that tail. If they do find a match, they return the next tail (consisting of the original tail minus the matched portion).

They also set the atom RESULT with a global (CSET) value that specifies what semantic elements were matched along with their semantic category. As an example, consider the tail 'THF Fr~CTION FACT CALL ANY SUBRS' passed as an argument to FNNAME. (Perhaps as part of the question: "Can the function FACT call any subrs?") FNNAME would match the three words 'THE FUNCTION FACT'. It would return the tail, 'CALL ANY SUBRS' and set the value of RESULT to the list (FN FACT). FACT

is the semantic entity matched, while FN represents the category, function names. Table 1 shows some phrases that might be matched by FNNAME and the corresponding value of RESULT generated.

Table 1

Translations by the function FNNAME

Input Phrase Value of RESULT

'CAR 1

(FN CAR)

'CAR and CDR'

(FN CDR CAR)

'THE TWO FUNCTIONS CAR AND CDR' (FN CDR CAR)

'THE 3 FUNCTIONS X, Y, AND Z'

(FN Z Y X)

The semantic category consisting of function types is represented in the grammar by FN/TYPE. The operation of this function is very similar to that of FNNAME. In thie case, a word or phrase that somehow describes or classifies a group of functions is looked for. This includes function types like expr, subr, fsubr, and fexpr as well as things like arithmetic functions and conditional functions. Table 2 shows the value of RESULT that will be produced for a few input phrases.

Perhaps the largest semantic category is that consisting of LISP data structures. This is rep­ resented in the grammar by STRUCTURES and in the implementation by a function of the same name. Table 3 shows some of the phrases accepted in this category by the function STRUCTURES.

The fourth and last semantic category serves as a catch-all for anything not included in the other three. This category is represented by CONCEPTS in the grammar and the implementation. A few phrases recognized by the CONCEPTS function are shown in Table 4.

Table 3

Translations by Structures

Table 4

The Grammar And Its Implementation

The heart of the English understanding com­ ponent of the system is a BNF grammar. After a line has been read in, an interpretation of it is attempted. In the SOPHIE system (6), every non­ terminal is considered a semantic entity to be searched for when necessary. In the ISLE system, however, only a few of the rules are actually con­ cerned with semantic entities or categories.

These semantic. entities are defined as only those things which have entry in the semantic network. The rules which embody certain semantic groups have already been described. The rest of the grammer rules are used to identify requests for certain relationships or properties of the seman­ tic entities.

Most programs which make use of a grammar use some kind of parser or grammar interpreter. This parser (a program} then uses a table or array in which the grammar rules are stored (data). Special control structures must be set up to con­ trol backing up when an incorrect parse is begun. In ISLE, this grammar :lv implemented directly in LISP. For each rule (nonterminal) in the grammar, there is a corresponding LISP function with the same name implementing that rule. The LISP con­ trol structures make this implementation relative­ ly easy due to the recursive definition of LISP functions in general and the use of the special built-in functions; COND, AND, and OR. Backup is automatic as each rule-function can let its cal­ ling rule-functions know of its failure on return. All pointers and variable values will again be those originally set in the calling function. There is nothing to undo or redo as the LISP cor.­ trol structure handles this automatically.

The Semantic Routines

The parsing operation, if it is successful, will produce another LISP function to be eval­ uated. Some of these functions and the sentences that produced them are given in Table 5. Each is a call to a predefined semantic routine. The functions FN, PTYPE, CONCEPT, and STRUCTURE re­ trieve the desired semantic information for their arguments. In this way words such as ATOM are disambiguated. For example, (FN ATOM) will re­ trieve information relevant to the function ATOM, while (STRUCTURE ATOM) will retrieve the info~a­ tion for pronouns which it does by matching its arguments against the semantic categories of prev­ iously mentioned items.

Table 5

~entences and their Translation into LISP Functions

IS ATOM A FUNCTION? (RELATE (FN ATOM) (FTYPE FUNCTION)

HOW MANY ARGUMENTS DOES IT TAKE? (ARGCOUNT (LIST (PREF FN)))

(DESCRIBE (LIST (PREF FN FTYPE CONCEPT

DESCRIBE IT. STRUCTURE)})

WHAT IS AN ATOM?

(DESCRIBE (LIST (STRUCTURE ATOM }})

ISLE's semantic routines are all specialists for answering their own types of questions. Some take information directly from the network to be given to the student or to be used in comparison or relationship tests. DESCRIBE, for example, gives the student a pre-defined definition or des­ cription if it exists. In the case of student defined functions, it tells the student the type of function it is. RELATE reports on 'superset', 'subset', and 'part-of' relationships between its argument, or in the case of student defined func­ tions--the actual function definition, to tell how many arguments a particular function has.

The permanent semantic information used by these functions is set up as association lists of relationships and values for each semantic entity. Table 6 shows this information for the structural item atom. The value of the relationship TEST is the name of a predicate function which tests for the associated semantic entity. In this case, the function ATOM tests for the structure which is an atom. TYPE and TYPE OF indicate subset and super­ set relationships, and DESCRIPTION indicates a literal definition of the item.

Table 6

S~ntic Information for the Structure Atom ( ( TEST · ATOM) (TYPE OF · (S-EXPRESSION INDICATOR)) TYPE · (LITERAL NUMBER)) PART OF · (S-EXPRESSION DOTTED-PAIR LIST)) DESCRIPTION · ((AN ATOM IS THE HOST ELEMENTARY TYPE OF S-EXPRESSION (DOT))

(IT HAY BE EITHER A NUMBER OR A LITERAL ATOM (DOT)))))

Other, temporary information that might be used by the semantic routines can be created and changed in various ways. When a student defines a function, the function is analyzed and lists of the variables it binds or uses and the functions it calls are created. This information is used by the routines which handle questions about the student's functions and is updated whenever a function is edited or redefined. The editor and the evaluator also store information that could be used by the question-answering system. This is done whenever errors occur and includes informa- · tion about the current state of the evaluator or editor (e.g., the association list) and the cause of the error. This would allow the student to ob­ tain more information about the source of the error and what the evaluator (or editor) was doing before the error occured.

Knowing About Student Defined Functions

Knowledge concerning functions defined by the student falls into two distinct categories. The first is the category that might be called seman­ tics; that is what the function does (or should do or perhaps what the student thinks it should do). This involves why the function does what it does, when it does it, and how it does it. The other category is that of syntax or function structure. The function structure consists of only the infor­ mation contained in its definition--the functions it calls, the variables it binds, sets, or uses, its arguments and any discernable relationships between these basic components. We have concen­ trated on this second category and ignored the first one. This system handles knowledge of user's or student's functions in two places. First the functions must each be scanned as they are defined. Information concerning the use of variables and function calls is recorded to be used by the semantic routines when needed. This is a sort of preprocessing to collect information for the se­ mantic routines.

During the scan, the following proper~ies are representative of the ones set up on the function name's property list:

VFNS- variable functions; those functions that the given function calls which are not defined.

EFNS- EXPR'S- those EXPRS that ·the given function calla.

SFNS- SUBR'a-thoae SUBR'S that the func­ tion calls.

SETVRS- those variables which the func­ tion seta.

BINDS- those variables which the function binds, those that are found in PROG and lambda expression variable lists.

These properties are then used by the seman­ tic routines which answer questions about the user defined functions. These include questions like:

WHAT VARIABLES DOES FOO SET? DOES FIE CALL FUM? DOES FOO CALL ANY SUBRS?

WHAT VARIABLES ARE BOUND BY FUM THAT FOO SETS?

Once the call to these semantic routines has been generated the answer to. the question is easily determined through the use of the above property values for the desired functions.

Problema Encountered

The problems encountered in dealing with natural language seem to fall into four separate areas. It is difficult to measure the extent of each of these problems at present. There are vi­ able approaches to the solution of each which should be examined.

a) The use of adjective and modifying phrases.

Students can be expected to try to describe various things concerning their programs in many different ways. At present, modifiers are looked for by the grammar at certain points and then ignored or, if necessary, used in writing the se­ mantic interpretation functions. Problema can occur when one of the basic semantic entities is used as a modifier, for example in phrases like LIST VARIABLES and VARIABLE LISTS. This problem would be solved by adding more information to the semantic network. The parser could then use this information to decide how to handle the· semantic entities when they are used as either modifiers or as nouns. Certain other modifiers that are not classified as semantic entities should be included in the network to allow variations of meaning to be understood that are now ignored.

b) Cause and effect relationships.

Often during the writing and debugging of a progra~ students will want to ask 'What happens if ... ' or 'Why' questions. To answer questions of this type it is usually necessary to compare desired with actual results. It is also necessary to know about various aide-effects that might oc­ cur such as setting Klobal or free variables. The information necessary to handle such questions could be obtained by tracing the evaluation of the student's functions. This could then be checked for validity in some way (i.e., compared against some desired result) or reported back to the student. It would also be useful to allow the system to simulate the evaluation of certain forms or lisp functions. This might take care of a large class of 'what happen if ..· ' type questions. Others might be handled by adding more information to the network, (i.e., that an error will occur when CAR is called with an atom as its argument).

At the present, none of these cause and ef­ fect type questions can be asked because of a lack of the necessary semantic information. If it were available, the addition of a few more rules to the grammar would allow many such question to be asked.

c) Verbs and action relationships.

The system now can only handle simple binary relationships between the semantic entities known to it. These relations can only describe static situations such as subset-superset (an EXPR is a FUNCTION), part-part of (a VARIABLE LIST is part of a LAMBDA-EXPRESSION) and function structure (function X can call function Y). When talking about writing and using LISP functions, students often need to use verbs specifying actions or re­ lationships involving two or more things. These verbs include the following among others--DO, MAKE, EDIT, CHANGE, INSERT, STOP, and REMOVE. A taxonomy· of the ways students use these verbs would be very helpful. The number of such verbs that might be needed may be small enough to keep the system relatively efficient. The best place to try this would be to attempt some additions to the grammar that would allow the student to edit LISP functions using English sentences instead of edit commands. Most edition operations involve actions on various object and subject nouns.

d) Pronouns, anaphoric deletion, and ellipsis.

Students often use pronouns or leave out words completely that might seem obvious. We have attempted to allow the use of pronouns, but in some cases the results are not the desired ones. For example, the following dialogue:

STUDENT:

MACHINE:

STUDENT:

MACHINE:

What are atoms?

An atom is the most elementary type of a-expression

It may be either a number or a lit­ eral atom.

How many arguments does PLUS need? PLUS is a FSUBR and can take any number of arguments.

STUDENT: Describe them.

At this point the system would not have rec­ ognized the relationship between 'PLUS' and 'ar­ guments' due to its inability at present to rec­ ognize the relationship between modifier and modi­ fied entity . A very minimal history of the pre­ vious dialogue is kept so that, although the sys­ tem remembers that PLUS was discussed previously, it does not remember that it was its arguments that were in ·question. Therefore, the system thinks that 'them' refers to 'atoms' and not the arguments of PLUS, and describes an atom. This particular problem could be solved by handling modifiers in a better, more consistant manner and by keeping a more complete history of the previous dialogue.

The handling of anaphoric deletion and el­ lipsis is, however, even more difficult. The following, seemingly natural dialogue, would not be accepted:

STUDENT:

MACHINE:

STUDENT:

IS X AN ATOM?

YES, X IS AN ATOM.

AND Y?

The student has deleted most of the question 'IS Y AN ATOM?' assuming that Y is to be substi­ tuted for X in the previous question . There are many similar deletions to be found in nearly any natural dialogue. Verbs, . subjects, object, modi­ fiers, or any combination of these might be dele­ ted. A study and classification of the various types of ellipsis that might occur in a student­ teacher dialogue would be very helpful here.

The most important lesson learned concerns the interaction of semantic and syntactic infor­ mation in dealing with and understanding natural language. Heavy use is made of semantic infor­ mation during the parsing operation. A parse will in fact fail if it does not make sense based on what the system knows, eve~ though it may be syn­ tactically correct.

The shortcomings here involve the structur­ ing and use of the semantic information. There is a large literature describing how to form and use grammars and other syntactic structures; how­ ever, similar studies for semantic structures are not yet available.

There are many models under study such as semantic networks and conceptual models (7). However, as yet, there are no definitive measures of the capabilities and limitations for these various techniques. Also, there are no studies comparing various means of implementation and the storage requirements of these model~. Hopefully, research along these lines would aid those at­ tempting to use these models for CAl in other ap­ plication areas.

Conclusions

This system is undergoing continued develop­ ment. The question-answerer is being expanded to allow the student to get more of the information he or she might want and to perform more edit functions in English.

ISLE is implemented in LISP which runs inter­ actively on an IBM 360/65. This interactive LISP is an improved version of the Waterloo LISP which uses a cathode-ray display as the active user terminal. The system runs in 250k bytes of mem­ ory. Each question is processed in one second or less.

Preliminary indications are that the system will serve as a useful tool for familiarizing a student with LISP concepts. The question answer­ ing capability allows a student to inquire about the semantics of LISP; he can use the· LISP stu­ dent evaluator to test his knowledge of LISP syn­ tax and to help him correct his errors. The expanded diagnostic information presented should help him clear-up initial misconceptions and ease his transition from ISLE to the standard LISP evaluator.

This approach appears to be general in that one could present any material of a factual nature in a similar manner. SOPHIE (6) is an example of a similar system for teaching electronic-circuit analysis and trouble-shooting. Other programming languages, logic circuit design, and basic algebra and calculus might possibly be taught using a sim­ ilar computer environment.

The important lesson learned concerns the in­ teraction of semantic and syntactic information in dealing with and understanding natural lanauaae. Heavy use is made of semantic information during the parsing operation. A parse will in fact fail if it does not make sense based on what the system knows, even though it may be syntactically correct.

The shortcomings here involve the structuring and use of the semantic information. There is a large literature describing how to form and use grammars and other syntactic structures; however, similar studies for semantic structures are not yet available.

There are many models under study such as se­ mantic networks and conceptual models (7). How­ ever, as yet there are not definitive measures of the capabilities and limitations of these various techniques. Also, there are no studies comparing various means of implementation and the storage requirements of these models. Hopefully, research along these lines would aid those attempting to use these models for CAl or other application areas.

1. E. B. Koffman, Generative computer assisted instruction: An Application of Artificial Intelligence to CAI, Proceedings of the 1st USA-Japan Computer Conference, Tokyo, 1972.
2. J. R. Carbonell, AI in CAl: · An Artificial Intelligence Approach to Computer-Assisted Instruction, IEEE Transactions on Man-Ma­ chine Systems, Vol. MMS-11, No. 4, December, 1970.
3. E. B. Koffman and S. E. Blount, Artificial Intelligence and Automatic Programming In CAl, Proceedings of the 2nd International Joint Conference on Artificial Intelligence, 1973.
4. W. A. Woods, Transition Network Grammars For National Language Analysis, Communications ol The ACM, Vol. 13, No. 10, October, 1974.
5. T. Winograd, Understanding National Language, Academic Press, New York, 1973.
6. J. S. Brown, R. R. Burton, and A. G. Bell, SOPHIE: A Sophisticated Instructional En­ vironment for Teaching Electronic Trouble­ shooting, Bolt, Beranek, and Newman Report No. 2790, Cambridge, Massachusetts, March, 1974.
7. R. C. Schank, Identification of Conceptual­ izations Underlying National Language, in Computer Models of Thought and Language, edited by R. C. Schank and K. M. Colby, W. H. Freeman & Co., San Francisco, 1973.