English-Based Method Editor
Surya Ramachandran and Jim Blythe
MOTIVATION
1) If successful, this can be a very useful tool in the hands of the Novice and semi-expert EXPECT user.
The ability to change the contents of the Knowledge Base without knowing the coding language and just a basic understanding of the domain.
To allow the user to make relatively small modifications - changing some of the steps or perhaps adding a new method using analogy.
2) Knowledge Acquisition made easy.
Domain experts need not know any LISP/LOOM/EXPECT programming constructs to modify and possibly enter new knowledge.
WORKINGS
Functional decomposition for method editing into 3 basic parts:
I) The Code to English Parser
a) Representational issues
i) Hierarchical decomposition
The code that existed to display methods in English used a flat generation scheme. The code was parsed and the resulting string was then displayed to the user. For the purposes of selection of a single word that represented some atomic code, this was adequate. But for the ability to select different sections of code through their corresponding English string, there had to be some structure to the code and English that was generated from it. LISP inherently uses nested function calls, this aids a functional decomposition of the code.
ii) Four-element parse structure
Thus with the decomposition of the code (into some form of a parse tree) each node will now represent a piece of code. Associated with this code is the English text that it generates, and all its children and the English text that they generate. Thus each node can be represented as a four element list with first element being the English form, the second being the code that generates this English form, the third is a unique index number and the last element is a list (4-ele) of all its children (NIL when there are no children).
b) Facilitated by EXPECT grammar
i) Typing and Method structure
All structures in EXPECT have (or return) a value that is of the EXPECT Data Type (EDT) this greatly facilitates the ability of the interface to derive the type for a given piece of code. This in turn allows for efficient alternatives generation. The method structure has clearly delineated sections and code changes to one can be easily mapped to changes in other sections of the method (eg: when we change the variable reference in the capability section of a method, say from "seaport" to "airport", then the associated variable in the body, say "?port1" now represents an instance of an airport).
ii) Resembling (only very slightly) ATNs in natural language.
During the generation of the parse structure, the interface makes use of an inherent hierarchy in the EXPECT code that (well, remind me) of some sort of an augmented transition network (eg: A structure can be either a sub-goal, a relation,... and a sub-goal can be further broken up into parameters, relations, instances....)
c) Issues and/with Example :
Consider a part of a problem solving method that determines if the ships of "port1" do actually fit in "port2" represented by the code snippet :
(DETERMINE-WHETHER (OBJ (R-SHIPS ?PORT1)) (FITS-IN ?PORT2))
After parsing the code the resultant parse structure will resemble :
(" " (DETERMINE-WHETHER (OBJ (R-SHIPS ?PORT1)) (FITS-IN ?PORT2)) 1
(("determine whether" DETERMINE-WHETHER 2 NIL)
(" " (OBJ (R-SHIPS ?PORT1)) 3
((" " OBJ 4 NIL)
(" " (R-SHIPS ?PORT1) 5
(("the ships of" R-SHIPS 6 NIL)
("the first seaport" ?PORT1 7 NIL)))))
(" " (FITS-IN ?PORT2) 8
(("fits in" FITS-IN 9 NIL)
("the second seaport" ?PORT2 10 NIL)))))
And the English transliteration would be the first element of every list in sequential order which would look like :
" determine.whether
...the.ships.of.the.first.seaport.fits.in.the.second.seaport""-_________-_______--- ___-_____-__-___-_____-_______-____-__-___-______-_______"
"1_________________345_______________________________8__________________________"
(the second string has dashes to mark blank spaces and the third string marks the places according to the index of blank parsed lists in the form)
Simple observations :
a) There seems to be some structure (based on the pprint indentations) but how and why ???
If the code resembles (a (b (c d)) (e (f g)))
then the resulting hierarchy will be (indented)
(a (b (c d)) (e (f g))) ;;The entire String
(a) ;;Its (code's) first child (first of three)
(b (c d)) ;;The (code's) entire second child (second of three)
(c d) ;;Its (b's) sub-children (as a whole)
(c) ;;b's first sub-child
(d) ;;b's second sub-child
(e (f g)) ;;The (code's) entire third child (third of three)
(f g) ;;Its (e's) sub-children (as a whole)
(f) ;;e's first sub-child
(g) ;;e's second sub-child
The leap from there is quite simple, just picture each element in the hierarchy as a four element list! So that was the "how" part. Which leads us to the "..why on earth would you..."
The "why" is primarily motivated by the following factors :
i) User's intent: The user may want to change only a piece of this code,
which may be a single construct/atomic-unit or some contiguous (?) sequence of them. Decomposition helps capture user's intent more precisely.
ii) LISP structures: nested functions, parameters and its wonderful plethora of parens...
More detailed observations :
Looking at the string that is generated from the parsed form;
a) It seems that there are a lot of blank spaces between the words.
i) This is because some of the code does not have English translation (eg: OBJ does not translate into anything meaningful that can be put in its place).
ii) Blank spaces represent a nesting of sequential elements. So if it is the user's intent to change (e (f g)) or (f g) as a whole unit, because of the hierarchical form of the parsed code, there will always be a blank that denotes every contiguous chunking of nested code. For example the annotated string (with the blank spaces selectively numbered) blank 1 will (when the mouse pointer is brought over it) cause the entire code segment to be selected for placement. Similarly 3,4,5 and 8 represent different chunks of code which can be seen by the index on the appropriate four element list
b) How do you get stuff like "seaport" instead of "?port1" and even "the second seaport" instead of "?port2". And for the more observant; how do you call the "(inst-of seaport)" in the capability section as "the second seaport" the same reference made in the method body to "?port2" to also translate to "the second seaport".
i) During the process of parsing an association list is built with the variables and their associated types. The associated EXPECT Data Type (EDT) for the variable is obtained from the capability section which will have "(?port1 is (inst-of seaport))". So this association list (or a part of it) would look like : (... (?port1 (inst-of seaport)) (?port2 (inst-of seaport)) ....)
This is then used whenever a variable is encountered to generate a more descriptive translation of the variable by using the "format" with "~:R" option.
ii) But the treatment of these variables is slightly different in the method capability and the method body. When in the capability section of a method the code (?PORT1 IS (INST-OF SEAPORT)) gets translated into "the first seaport" and while in the method body, the (corresponding) code ?PORT1 also gets translated into "the first seaport".
II) Display Windows, Buttons and Clickable Selections
The CLIM window for English editing is based on the CLIM window for modifying a method directly, and shows the user three sub-windows. The first shows the English version of the method currently being edited. The second shows two fields, "old text" and "new text" and the third displays a list of alternatives for the selection in "old text", whenever there is one.
All entries in the method window and the alternatives window can be selected by the user to fill either the "old text" or "new text" fields. To choose a piece of the method to modify, either from the capability or the body, the user can select it to fill "old text". The method display makes use of the hierarchical parse described above so the user can click on any coherent statement - for example if a sub-goal in the body is
"determine whether the ships of the first port fits in the second port"
the user could click on the whole sub-goal, or "the ships of the first port", or just "the ships" or "determine whether".
When a selection is made for the "old text" field, the alternatives window is filled with possible alternatives to be selected for the "new text" field. The alternatives all belong to the same classification in the grammar, eg relation name, parameter name, or something that can be expanded to be an instance or concept. This helps the user make changes that are grammatical. The next section discusses how the alternatives are chosen, and how they are ordered in the window.
Once the user selects a value for the "new text" field, he or she can select "update" in the middle window to make the change in a copy of the method. When this is done, the method window changes to show an English language version of the modified method. However, the method is not changed in Expect until the user selects "done".
III) Alternatives Generation and Commission
This section consists of the user's intent to replace a selected piece of text with another (hopefully appropriate) one and then committing one or more of these changes.
a) Alternatives generation
i) User's intent over selected text (to be replaced).The user selects some text from the English language translation of the method capability or the method body. The response should be to display (in English) a list of relevant and ordered possible replacements in the alternate window. The relevance here signifies the neighborhood with respect to the text selected. The ordering of the list of alternatives reflects what the user is most lightly to select. More will be said in the next section.
ii) Once the selection of the replacement text has been made, the user can refresh (see the changes in the original code) by the use of the "update" button. All text that is displayed in the alternatives window and in the 4-element list format (they may be a single list with no children or a hierarchical parsed form).
iii) This process (of selection and updating) continues until the user is satisfied with the new method. At this point the user can either commit these changes to the knowledge base or cancel out of the operation.
b) Choosing Alternatives
When the user selects a string (as the one to be replaced), the interface decides the list and orderings of the alternatives to be displayed. This is governed by:
i) What piece of code is chosen
ie: Variable, Relation, Sub-goal, etc.
ii) The type (EDT) of the code chosen (the return type)
This is established by the type hierarchy.
ie: The method body has a return type based on the result field.
We shall now look at some selection of alternatives :
i) Concept and instance descriptions. eg: (inst-of seaport), (spec-of ship), (set-of (inst-of seaport)).. For all these we currently find all sibling concepts, which make up the list that will be displayed in the alternatives window.
ii) Relations. eg: r-ships (here the user has selected the relation-name only)
Currently, the alternatives are made up of all the relations that are defined on the same EDT as the one selected.
iii) Goal/Sub-goal names. eg: find, filter, compute....
Similar goal names (got from looking at all the sub-concepts of expect actions) are displayed.
iv) Parameters. eg: WITH, FROM, ON, TO, IN.....
As these are expect action roles, they comprise the alternatives displayed.
v) Goals/Sub-goals.
eg:(DETERMINE-WHETHER (OBJ (R-SHIPS ?PORT1)) (FITS-IN ?PORT2))OK, we get into the slightly more intricate stuff here. The list is ordered with the following:List is made up of variables that match the return-EDT of the goal,
relations that have the same EDT,
and other goals that have the same return/result type.
(Note: The list of alternatives generated for each of these "classes/types" can be extended/modified with ease as the contents of this list follow the same 4-element format)
vi) Variables. eg: ?port1, ?port2, ?s, ....
The list is ordered with the following:
Similar variables in the plan (with the same EDT),
relations based on the EDT of the code selected,
and goals that have the same return type (EDT) as the selected code.
vii) Instances. eg: constants, etc.
The list is ordered with the following:
List of similar instances that may be part of the method,
list of other instances from the domain (matching EDT),
list of variables from the domain (matching EDT),
list of relations with the same EDT,
and possibly sub-goals that have the same return type.
There are a lot of improvements that can be made here, but most of them should be simple as long as the list to be included for a particular class/type has the parse-list format.
c) Commission
i) The real use of the unique index field in the 4-element list structure is here where it is used to track down a particular section of the parse tree for replacement. There may be several pieces of code that are identical (like the same variable being referenced) and replacement may be over only one of them. The index of the text/code selected for replacement defines its position in the actual plan. After determining this replacement is trivial.
ii) At the end of the replacements, the code is committed as the actual method to EXPECT and then is flagged for book-keeping.
FUTURE
a) Additional functionality
i) Have a "Save As" button that will allow a modified method to be saved under a different name.
ii) Type checking for alternatives that are typed in by the user (eg: constants).
b) Beyond simple editing
i) Creation of new declarations like Constants, Variables and Relations that may map directly to LOOM (or EXPECT) declarations.
ii) Creation of new problem solving methods (from scratch).Possibly a hybrid version of the adaptive forms idea but in English?
iii) Reverse parse: so the user can type "the ports of the region" and have the editor recognize this as a retrieval, generating the expression (r-ports ?region) and the related issue of being able to search (as ontosaurus does) so they can type "ports" in the "new text" field and get every alternative that mentions the string "ports", rather than have to scroll through a potentially huge list of alternatives looking for the ones they need. The problem we're trying to address here is that in a large KB there may already be a relation, achievable goal or concept related to what the user wants, but they might not know its exact name.