A Critic for LISP

1. Introduction

Our goal is to establish the conceptual foundations for using the COf'Tllutatlonal power that is or will be available on computer systems. We believe that Artificial Intelligence methodologies and technologies provide the unique opportunity to achieve the goal of improving productivity by addressing, rather than ignoring, human needs and potential. We are building systems which augment human intelligence. Winograd and Flores (Winograd, Flores 86) argue that the development of tools for conversation where the computer serves as a structured dynamic medium for conversation in systematic domains, Is a more realistic and more relevant goal to successfully exploit information and communication technologies than the most widely perceived goal of AI "to understand and to build autonomous, intelligent, thinking machines· [Stefik 86). In addition to the fact, that the track record of the latter approach is not too good (e.g., high quality fully automatic translation, automatic programming), we believe, that partial autonomous systems pose greater design challenges than fully automated do (evidence for this view comes from many sources, e.g., in the development of cockpits for future aircrafts the pilot's assistant is a more challenging goal than the electronic copilot [Chambers, Nagel85)).

"This paper describes wori< done in the Department of Computer Science and the Institute of Cognitive Science at the University of Colorada, 8oulder. It was supported In part by grant No. N00014-85-K-0842 from the Office of Naval Research, the German Ministry for Research and Technology, and Triumph Adler Corporation, Nuernberg.

In this paper we argue that to successfully learn and use complex computer system, incremental learning, learning on demand, user and task specific advice has to be supported. Intelligent support systems are one approach to provide these support structures. We describe in detail one of these systems, the LISP-CRITIC, which enhances incremental learning and supports learning on demand.

2. Incremental Learning

2.1 Facts of Life

The functionality of modem computer systems is constantly expanding (see Figure 2-1) . This increase in functionality is of little use if we do not find ways for people to take advantage of it. Online help systems usually do not do much more than present the same information found in the printed documentation, although the better ones provide additional assistance like keyword-based access and bookmarks that leave a trace of an information-seeking session.

The existence of documentation and other support information does not guarantee that people know how to use it, or that they read it or understand it. It is a fact of life that people quickly settle on plateaus of suboptimal behavior. There are two reasons for this. One is that people do not want to learn. They use computers because they want to get something accomplished. The positive side of this behavior is that people focus on their work, the negative side is that they are not motivated to spend time learning about the system just to find out what they can do. This phenomena is called the "production paradox" by Carroll and Rosson [Carroll, Rosson 86). People have a tendency to stick with what they know best. When situations occur that could be more effectively handled by new procedures, they are willing to deal with them in suboptimal ways that they personally consider to be safe. People intentionally do things suboptimally; they have a subjective metric for cost­ effectiveness.

Another reason for suboptimal behavior is that learning Is often restricted. Even if people want to learn, they may not be able to. For example, if the context for new information is missing, people often do not understand the relevance and applicability of new commands. We verified this effect in small-scale experiments with the editor command "Query-Replace" in EMACS. This command steps through all occurrences of a string of text, and the user has to confirm or deny the replacement for each occurrence. It happens quite frequently that while users are in "Query-Replace mode" they detect an error in the immediate environment that they would like to correct. To do so, either they have to make a note to go back to the Incorrect text after they complete the whole replacement cycle, or they have to leave the cycle and set it up again to take care of the rest of the file. An advanced feature provided by EMACS Is the "recursive edit", which allows the user to do some modifications and then restart the "Query-Replace" cycle. Our experiments show that people reading through a description of this command do not understand what recursive edit does, what it is good for and in which situations it can be used. Only after using the basic command for some time do people start to appreciate an advanced feature of this kind. It is within the scope of our active help system (Fischer, Lemke, Schwab 85) to give a hint about the usefulness of the recursive edit at a time when the command can be used successfully.

Number of Computational Objects In Systems

EMACS:

• 170 function keys and 462 commands

UNIX:

• more than 700 commands and a large number of embedded systems

LISP-Systems:

• FRANZ-LISP: 685 functions
• WLISP: 2590 LISP functions and 200 ObjTalk classes
• SYMBOLIC$ LISP MACHINES: 23000 functions and 2600flavors

Amount of Written Documentation

Symbollcs LISP Machines:

• 12 books with 4400 pages
• does not include any application programs

SUN wort<statlons:

• 15 books with 4600 pages
• additional Beginner's Guides: 8 books totaling 800 pages

Figure 2·1: Quantitative Analysis of Some Systems

Our preliminary empirical findings indicate that the following problems prevent many users from successfully exploiting the potential of high-functionality systems:

1. Users do not know about the existence of tools (and therefore they are not able to ask for them);
2. Users do not know how to access tools;
3. Users do not know when to use these tools;
4. Users do not understand the results that tools produce for them;
5. Users cannot combine, adapt, and modify a tool to their specific needs.

A consequence of these problems is that many systems are underused. We are strongly convinced that what is needed Is not quantitatively more Information but qualitatively new ways to structure and present information.

2.2 Modes of Learning

In our research we want to determine the balance between supporting an exploratory learning style of learning by doing which is the basic philosophy behind the interest worlds in LOGO environments [Papert 80), and a guided learning experience through coaching assistance, which is the primary strategy supported by systems in intelligent computer-assisted instruction (Sleeman, Brown 82). There are different modes of learning that can complement each other depending on whether the user's goal is the completion of an action or the acquisition of new knowledge, and depending on whether users are inexperienced with a system or familiar with It and able to help themselves.

Unguided, active exploration. The advantage of this mode of learning is that users can fully control what they would like to do and how they would like to do it. It Is important that an environment of this kind supports safe experimentation (e.g., UNDO mechanisms are crucial) and that it is intuitively approachable. Examples of systems that support unguided learning are: LOGO-based learning environments (Papert 80), spreadsheets and construction kits (Fischer, Lemke 87).

Tutoring. Tutoring is an adequate mode of learning for getting started learning a new system. One can predesign a sequence of microworlds (see section 2.3) and lead a user through lhem [Anderson et al. 84; Anderson, Reiser 85). But Moring is of little help in supporting learning on demand when intermediate users are involved in their "own doing". Tutoring is not task-driven because the total set o; tasks cannot be anticipated. Instead, the system controls the dialogue, and the user has little control over what to do next.

Asking for Help. In passive help systems, users actively have to seek for help. In complex systems, even experienced users know only a minority of the large set of commands available (Fischer 87]; their expertise lies not In having learned enough to solve any problem immediately, but in having become skilled in gathering information and supplementing what they know by active use of external sources of information. But finding information in these systems is far from easy. Help systems have become large systems in their own right, and finding needed information Is a problem because there is usually a huge gap between the initial mental form of the query and the corresponding expression required by the system. Documentation and help are structured at the level of the system modules (commands) and not at the task level; to accomplish a specific task may require reading through a substantial amount of information.

Answerw flrwt, then Questions. To ask a question, one must know how to ask it, and one cannot ask questions about knowledge whose existence is unknown. Owen (Owen 86) has implemented a program called DYK ("Did You know"), which volunteers information and supports the acquisition of information by chance. It supports an unstructured learning process, but there is a fair chance that users occasionally pick up some relevant piece of knowledge.

Learning on Demand. Active help systems and critics support learning on demand. Users are often unwilling to learn more about a system or a tool than is necessary for the immediate solution of their current problem. To be able to successfully cope with new problems as they arise, users require a consultant that generates advice tailored to their specific need. This approach provides information only when it becomes relevant. It eliminates the burden of learning many things in neutral settings when the user does not know whether the information will ever be used and when it is difficult for the learner to imagine an application (see the "Query­ Replace· example in section 2.1) . Active help systems and critics overcome the problem of asking a question. They allow users to do whatever they want and interrupt only when users' plans, ways of achieving something or products are considered significantly inferior to what the program would have recommended. They offer new information only if it is needed. A potential drawback might be that they offer help only in related areas; this can be overcome by accessing knowledge structures that allow the system to present information in related areas in a goal-directed "DYK" fashion (see Figure 4-5) .

Human Assistance. Human assistance, if available on a personal level, . is in almost all cases the most useful source of advice and help. The mode of learning can best" be characterized as a cooperative problem-solving process. Learners and advice seeking persons can ask a question in an infinite variety of ways, they can articulate their problem in the "situation model" rather than being required to express their needs in a "system model" [Dijk, Kintsch 83). Many systems to support information and advice seeking (with some notable exceptions like RABBIT [Tou et al. 82) and ARGON [Patei-Schneider, Brachman, Levesque 84)) have assumed, that persons know what they are looking for. Studying human advisory dialogues [Webber, Finin 84) has shown, that this assumption does not hold: the most valuable assistance is often in formulating the question.

2.3 Increasingly Complex Microworlds: An Architecture to Support Incremental Learning

Over the last several years we have developed a general paradigm for instruction that is best described as a sequence of "Increasingly Complex Micro worlds (ICM)" [Fischer 81; Burton, Brown, Fischer 83).

The ICM paradigm was developed to capture instructional processes for complex skills that are difficult to l~arn because the starting state and goal state are too far apart. The student is exposed to a sequence of increasingly complex microworlds, which provide stepping stones and intermediate levels of expertise so that within each level the student can see a challenging but attainable goal. Increasingly complex microwor1ds can also be used to provide protective shields for novices and prevent them from being dumped into unfamiliar areas of the system. The paradigm requires a precise representation of the knowledge that is learned in a specific microworld and of the method for choosing the next microworld. As a model, it captures the essence of the incremental learning processes.

The LISP-CRITIC provides a rich environment for pursuing interesting questions within the ICM paradigm:

1. What is the right grain size for microworlds?
2. How do we generate microworlds? By constructing tools to eliminate the necessity of learning subskills? By providing defaults? By cbnstralning the design space thereby decreasing the objective computability of the system but increasing the subjective computability [Fischer, Lemke 87])?
3. What is the right topology of a sequence of microworlds? For people involved in their own work do we need multiple start states? For people having different goals, do we need multiple goal states?
4. What initiates the transition of one microwor1d to another one? Does the user initiate it or the system? Why should a transition take place?
5. How do we identify a user with a microworld? By taking into account which rules of the LISP-CRITIC (see section 4.3) fire and how often the user code can be matched against the right-hand side of rules (indicating the actual and suggested use of certain concepts)? By doing a statistical analysis of user's programs? By self-evaluation of the user? By instantiating the user's knowledge structures of LISP and comparing them with stored representations of expert knowledge [Fischer 87)?

By creating and studying the LISP-CRITIC that is codifying an idea as a system, we were able to raise issues such as these, which are difficult to articulate concretely in theoretical terms.

2-4 Goals of Incremental Learning

The major goals we can pursue by supporting incremental learning are:

• the elimination of suboptimal behavior, thereby increasing efficiency;
• the enlargement of possibilities, thereby increasing functionality;
• the support of learning on demand by presenting new information when it is relevant;
• the structuring of complex systems so that they have no threshold and no ceiling. It should be easy to get started; that is, microworlds should provide entry points; but these systems should also offer a rich functionality for experienced users;
• the use of models of the user to make systems more responsive to the needs of individual users and the tailoring of explanations to the user's conceptualization of the task.

3. Intelligent Support Systems

In our research work we have used the computational power of modem computer systems to construct a variety of intelligent support systems (see Figure 3-1). These support systems are called intelligent, because they have knowledge about the task, knowledge about the user and they support communication capabilities which allow the user to interact with them in a more "natural" way. They are used to enhance incremental learning processes, to provide help and documentation, to support the understanding of existing programs and advice given, to assist in the construction of new systems. They are described In the following documents:

1. a documentation system that assists In the incremental development and understanding of a program (Fischer, Schneider 84);
2. a passive and an active help system for an EMACS-like editor [Fischer, Lemke, Schwab 85];
3. components of a "software oscilloscope" that serve as visualization tools [Boecker, Fischer, Nieper 86);
4. design kits which support and guide the designer In the construction of complex artifacts [Fischer, Lemke 87);
5. a critic for LISP that is described in this paper.

4. Description of the LISP-CRITIC

4.1 A Critiquing Model

One model frequently used in human-computer systems (e.g., MVCIN [Buchanan, Shortliffe 84)) is the consuffation model. From an engineering point of view, it has the advantage of being clear and simple: the program controls the dialogue (much as a human consultant or a tutoring system [Anderson et al. 84; Anderson, Reiser 85] does) by asking for specific items of data about the problem at hand. The disadvantages are that It does not support users In their own doing, it prevents the user from volunteering relevant Information and it sets up the program as an ·expert", leaving the user In the undesirable position of asking a machine for help. We are In the process of developing a critiquing model which allows users to pursue their own goals and the program Interrupts only if the behavior of the user Is judged to be significantly Inferior to what the program would have done.

The critiquing model will be used to support cooperative problem solving. When a novice and an expert communicate much more goes on than just the request for factual information. Novices may not be able to articulate their questions without the help of the expert, the advice given by the expert may not be understood and/or the advisee requests an explanation for it; persons may hypothesize that their communication partners misunderstood them or the experts may give advice which they were not explicitly asked for (the last aspect we have also explored in our work on active help systems [Fischer, Lemke, Schwab 85)).

4.2 The Functionality of the LISP-CRITIC

The LISP-CRITIC suggests how to Improve LISP code. Improvements can make the code either more cognitively efficient (e.g., more readable and concise) or more machine efficient (e.g., smaller and faster). Users can choose the kind of suggestions they are interested ln.

The system Is used by two user groups, who have different purposes. One group consists of Intermediate users who want to

The "LispCritic" pane provides the basic interface through which the user can Initiate an action by clicking a button. The "FunctionCode" pane displays the text of the program that the LISP-CRITIC works on. The other three windows show some of the transformations carried out on the program. The "?" in the title line of the windows is the button for starting the explanation system, which allows the user to browse through additional knowledge structures.

team how to produce better LISP code. We have tested the usefulness of the LISP.CRmc for this purpose by gathering statistical data on the programs written by students in an Introductory LISP course. The other group consists of experienced users who want to have their code "straightened out". Instead of doing that by hand (which in principle, these users can do), they use the LISP-CRITlC to carefully reconsider the code they have written. The system has proven especially useful with code that is under development and is continuously changed and modified.

Figure 4-1 shows the system in operation. The LISP·CRmc is able to criticize a user's code in the following ways:

• replace compound calls of LISP functions by simple calls to more powerful functions (e.g., (not (evenp a)) may be replaced by < oddp a) ) ;
• suggest the use of macros (e.g., (setq a (cons b a)) may be replaced by (push b a));
• find and eliminate 'dead' code (as in (cond < ... l <t . . . ) (dead code)));
• lind alternative forms of conditional or arithmetic expressions that are simpler or faster (see Figure 4-2);
• replace garbage-generating expressions by non­ copying expressions (e.g., (append (explode word) chars) may be replaced by (nconc (explode word) chars); see Figure 4-4);
• specialize functions (e.g., replace equal by eq; use Integer Instead of floating point arithmetic wherever possible);
• evaluation or partial evaluation of expressions (e.g., (sum a 3 b 4) maybeslmplifiedto (sum a b 7)).

4.3 The Architecture of the LISP-CRITIC

The knowledge of the subject domain (concepts, goals, functions, rules and examples) is represented in a network of Interrelated nodes. The user can selectively browse through the knowledge. The LISP-CRITIC operates by applying a large set of transformation rules that describe how to improve code. Figure 4-2 shows two of the rules in the system. The user's code is matched against these rules, and the transformations suggested by the rules are given to the user. The modified code is written to a new file, and the user can inspect the modifications and accept or deny them. On demand, the system explains and justifies its suggestions.

The structure of the overall system is given in Figure 4-3. The user's code is simplified and analyzed according to the transformation rules and two protocol files, ·people.PR" and "machine.PR", are produced. They contain information (see Figure 4-1) that is used together with conceptual knowledge structures about LISP to generate explanations (see Figure 4-5). The user model (for a more detailed discussion see [Fischer 87]) obtains information from the rules that have fired, from the statistical analyzer and from the knowledge structures that have been visited . In return, It determines which rules should fire and what kind of explanations should be generated. The statistical analyzer provides important information to the user model, for example, which subset of buih-in functions the user is using, whether the user is using macros, functional arguments, nonstandard flow of control, etc ..

Transform a "COND" Into an "AND" (rule cond-to-and-1 (cond (?condition ?action)) -> (and ?condition ?action) aafe <-chine people) ) the ~ of the rule the original code the replac-nt rule category Example <·- riqurea ABBCIU'l'IC and KXPL) : (cond (Yalue (eq (cadr ·alue) 1.0))) ---> (and ·alue (eq (cadr value) 1 . 0)) Replace a Copying Function with a Deatructlve Function (rule append/.1-new.cona.cella-to-nconc/.1 .. . (?foo: (append append1) (restrict ?ezpr (cona-cell-qenerating-ezpr ezpr)) ?b) -> ( (COIIIpute-it : (cdr (aaaq (get-binding foo) '((append . nconc) ?ezpr ?b) aafe <-chine) ) (appendl . nconc1))))) Example <·- riqure ltUS'l'LB) : the name of the rule the condition (rule can only be applied if cona cella are generated by "?expr") rule category (append (ezplode word) char) ---> (nconc (ezplode word) char)

4.4 Support for Understanding the Criticism

Our experience with the LISP-CRITIC in our LISP courses has shown that the criticism it gives is often not understood. Therefore we use additional system components to illustrate and explain the LISP-CRITIC's advice. KAESTLE, a visualization tool that is part of our software oscilloscope [Boecker, Fischer, Nieper 86], allows us to illustrate the functioning and validity of certain rules. In Figure 4-4 we use KAESTLE to show why the transformation (append (explode word) chars) ---> (nconc (explode word) chars) is a safe one (because explode is a cons-generating function; see the rule in Figure 4-2), whereas the transformation (append chars (expl ode word)) ---> (nconc chars (explode word)) is an unsafe one (because the destructive change of the value of the first argument by nconc may cause undesirable side-effects) .

In addition to the visualization support, we have developed an explanation component that operates as a user-directed browser in the semantic net of LISP knowledge. This component contains: textual explanations that justify rules, related functions, concepts, goals, rules and examples (see Figure 4-5). Currently textual explanations are extracts from a LISP textbook [Wilensky 84]). The information structures in the explanation component should help the student to understand the rationale for the advice given by the LISP-CRITIC, and they should also serve as a starting point for a goal­ directed "Did you know (DYK)" mode of learning (see section 2.2).

4.5 Tutorial Strategies

With these features we can pursue different tutorial strategies in the framework provided by the LISP-CRITIC. The information accumulated in the system's model of the user is used to decide when a user should be criticized, what advice should be given and how the advice should be given (e.g., as a textual explanation from the manual, a KAESTLE visualization, or as a convincing example) . These issues are not independent, and have to be perceived from the user's state of knowledge, not the designer's. We must guess and determine the knowledge state of the user in order to make critics such as the LISP-CRITIC respond at the user's level of understanding,

Crucial issues in designing the LISP-CRITIC were the distribution of initiative between the user and the system and the amount of control over the system. After the LISP-CRITIC has provided an initial starting point for a learning process, we feel that the user can and should be able to proceed in a self-directed mode. A specific user may personally dislike some of the rules and should be able to turn them off. If the system notices that a user never accepts the changes suggested by a rule, it could be turned off automatically [Fischer, Lemke, Schwab 85].

5. Experiences with and Evaluation of the LISP­ CRITIC

The LISP-CRITIC has been In operation for two years and has been useful for many groups of LISP users. Our Informal evaluations indicate that the LISP-CRITIC had an l!'11)act on the process of learning LISP. One study showed that as students gained experience In LISP programming, the number of rules fired decreased over time. Students learn new functions, new concepts and ways of structuring their knowledge about LISP. Instructors can use the output of the LISP-CRITIC as a basis for personal advice to their students. Experts also used the LISP-CRITIC to have their code "straightened out". The rules In the knowledge base of the LISP-CRITIC generated an ongoing discussion about the merits of different styles of LISP programming. Surprises from our empirical work. were, that our statistical analysis showed that even experts only use a relatively small fraction of the total number of primitive LISP functions, and that the LISP-CRITIC suggested many improvements for the Implementation of generally used systems (e.g., for the LISP implementation of OPSS and for the system code of FRANZ-LISP).

To discover suboptimal behavior requires a metric. For our ACTIVIST system [Fischer, Lemke, Schwab 85], we chose a very simple metric: the number of keystrokes needed to perform a specific task. In the LISP-CRITIC, a set of over two hundred rules defines a metric (currently for the FRANZ-LISP dialect). These rules state how a LISP program should be written. Like the UNIX Writers Workbench tools [Cherry 81), they define a style or standard that the authors believe leads to greater clarity and understandability in a program or piece of code. It goes without saying that we do not expect universal agreement on issues of style (we have applied the UNIX writers workbench tools (e.g., DICTION) to the Gettysburg address and the system suggested some modifications).

The LISP-CRITIC in its current form Is not restricted to a specific class of LISP functions or domain of application. It accepts any LISP code. Its generality is the reason for some obvious shortcomings. The critic operates only on the code; the system does not have any knowledge of specific application areas or algorithms, and It is naturally limited to Improvements that derive from Its low-level knowledge about LISP. As we pointed out In section 2.2, human assistance Is by comparison much more powerful than the LISP-CRITIC, because determining and addressing user's goals can extend advisory dialogues far beyond the capabilities of the LISP-CRITIC. Systems like the PROUST system [Johnson, Soloway 84) are able to do a much deeper analysis, but they are very restricted in the range of problems to which they can be applied to. We have designed a module to extend the framework of the LISP-CRITIC by providing expert solutions to problems assigned to students In a course. Comparison of these expert solutions with the work of the students provides additional sources of information for the LISP-CRITIC.

The LISP-CRITIC's understanding has to be extended beyond lines of code or Individual. functions. Knowledge structures derived from programs like MASTERSCOPE [Teitelman, Masinter 81) and a knowledge-base of cliches (representing intermediate and higher­ level programming constructs [Waters 85; Waters 86) would be useful for the LISP-CRITIC to operate on.

6. Future Research

To get a better understanding of the empirical consequences of the many design choices which one faces In building a system of this sort, more research in studying naturally occurring advisory situations Is urgently needed. The LISP-CRITIC has been an Interesting starting point towards our long-range goal to build Intelligent support systems and to support cooperative problem solving processes between humans and computers. The LISP-CRITIC has a few features, which extend the system beyond a "one-shot affair": it allows the user to ask for an illustration of the advice given (see Figure 4-4) and the user can use the advice as a starting point to explore related concepts, functions and goals (see Figure 4-5).

The LISP-CRITIC Is a first operational example of the class of systems we are interested in. However, we doubt that the general domain of LISP programming Is the best area for a critic. An preliminary analysis of more restricted domains like our user Interface construction kit WLISP [Fischer, Lemke, Rathke 87] and the formatting system SCRIBE have lead us to believe that critics may be even more useful for less general systems where a system has a better chance to Infer the goals of the users.

Acknowledgements

Many people have contributed to the development of the LISP-CRITIC over the last few years. The author would like to thank especially Heinz-Dieter Boecker, who developed many of the original ideas, the set of rules and the interpreter for it; Andreas Lemke, who contributed to the general framework for incremental learning; Helga Nieper, who developed KAESTLE; Christopher Morel, who implemented the explanation capabilities; Bart Burns, who implemented the statistical analysis package; Catherine Cormack, who analyzed user programs with the statistical package; and Janet Grassia who assisted in editing this paper.