Transfer Semantics in an Operating System Consultant: The Formalization of Actions Involving Object Transfer

1. Preconditions

The initial logical operand in any precondition set is usually AND. The reason for this is that mandatory conditions must be ANDed to other conditions in the set. The optional conditions in each precondition set are ORed together. The final ORed condition is a default. In Figure 3 there are three ORed preconditions which are ANDed to one mandatory precondition. Of course, the third ORed condition is the default.

Interpreting the above set, it is noted that the mandatory condition specifies that a directory file should not be printed. or course, it is possible to print a. directory by first listing it and then printing it. Yet, one does not usually print directories themselves, and this is what we are concerned with here. The first optional condition specifies a preference that files are printed and their contents are preferably visible byte sequences. The second optional condition declares in addition the existence of a printer queue. In order to print a file on the printer it is certainly useful to have a printer queue. Finally, the third condition in the set is a default, and is the same as the first condition. We do not worry about preconditions such as the system being up, the terminal working or keyboard on-line. These are simply assumed.

It is important that we represent the "weakest" precondition set for any action. By weakest, we mean the least number of (or least .constraining) preconditions necessary to characterize some action sufficiently. For example, we know non-directory files to be types of files (Figure 2} and that either can be preconditions for printing. The use of files (weak) as a precondition for printing will do just as well as non-directory files (stronger). That is exactly why we reflect files in the precondition set rather than say non-directory files (or device files or plain files) which are types of file. 2. Postconditions

Postconditions for any action denote preferred con­ ditions on objects resulting from the execution of that action. In all action frames the postconditions represent changes in state of the precondition set. The postcondi­ tions for the action frame "print" are shown in Figure 4.

In the postcondition set below there are no manda­ tory conditions. Hence, the initial logical operand is OR. There are three ORed conditions, the final one del­ imiting a default. The first condition declares that the file which we saw in the precondition set also exists in the postcondition set. The file doesn't disappear after printing as would be the case with a delete frame. The file still contains visible byte sequences although a filter is now also applied. Filters are items such as page­ headers, line numbers and dates. Also a device file exists to denote default standard output which is the terminal screen.

The second ORed condition tells us that a print . queue exists and has a print queue entry. Also, a filter may be applied to the contents of the file. The third postcondition in the set is again a default and specifies output to a device file.

(postconditions (OR (AND ((o·frame non-directory-file) ((o-frame contents) · (o-frame visible-byte-sequence) (o-frame filter))) (o-frame device-file)) (AND ((o-frame non-directory-file) ((o-frame contents) · (o-frame visible-byte-sequence) (o-frame filter))) (o-frame print-queue) (o-frame print-queue-entry)) (AND ((o-frame non-directory-file) ((o-frame contents) · (o-frame visible-byte-sequence)))

( o-frame device-file))))

Figure 4.

We try to represent the "strongest" postcondition set for any action. By strongest we mean the maximum number of (or most constraining) postconditions neces­ sary to characterize some action sufficiently. We know device files to be types of non-directory file (Figure 2) and that either could denote postconditions for printing files. However, the use of device files (strong) as a postcondition for printing rather than non-directory files (weaker} is a more precise definition about the effects of printing. That is why we reflect device-file in the postcondition set rather than say file or non-directory file. There is no harm in weakening the postcondition set. We will see in section four that the ability to weaken postconditions is, in fact, an advantage.

3. Precondition-Postcondition Correspondence

Now, one may think there is some redundancy in the condition sets for print. For example, one condition occurs twice in the precondition set. However, we have done this because there is an exact one-to-one correspondence between the ORed conditions in the precondition and postcondition sets. Say, { P 0, P 1, ... P. } denote the ORed preconditions for some action A. Then, these are related to the ORed postconditions { Q0, Q 1, ... Q. } so that P 0 => Q0, P 1 => Q 1, ... P. => Q. for action A. So, the first ORed precondition in the precondition set corresponds to the first in the postcon­ dition set, the second to the second, and so on. As there are no mandatory postconditions there is no correspondence for them at all.

The one-to-one correspondence between precondi­ tions and postconditions is implicit: it is the position of a particular condition in its precondition/postcondition set that determines correspondence. If it turns out that many some conditions need to be repeated exhaustively (it only happened once above) for action frames we can represent the correspondence explicitly by placing a marker on each condition. One may wonder what's the use of all this correspondence. Correspondence aids in predicting the most likely postcondition (or precondi­ tion} for some explicitly mentioned precondition (or postcondition) in a user query. It is the ability to predict preconditions and postconditions for user queries that gives added power to the system.

4. Actions and Actors

It is also necessary to specify the possible actions that cause transfer between preconditions and postcon­ ditions. Associated with each action will be a number of options. So, for the print frame actions are represented as:

(actions (OR (o-frame cat) (o-frame more) (o-frame lpr) (o-frame pr) (o-frame print)

(o-frame option-list)))

1' 1gure 1>.

Printing can be completed with any of the com­ mands in the ORed set of actions and their respective options. Finally, in Figure 6 we specify the actor per­ forming the action or transfer. Any user can print a file and this is represented in the actor set.

Figure 6.

To summarize, operating system actions are defined in terms of preconditions, postconditions, actions, and actors. Action frames reflect the behavior of operating system actions in terms of the effect of these actions on objects. We use the notation,

to denote the fact that some user U can execute the action A to transfer the precondition set P to the postcondition set Q. Now that we have described object frames and action frames it is possible to show how they may be used to interpret natural language queries about operating systems.

III LANGUAGE & TRANSFER SEMANTICS

In this section we will show how various queries could be interpreted using object and action frames. We adopt a distinction between concept description and dynamic queries. This distinction has been emphasized by Hegner (1987). Concept description queries are sim­ ple queries about objects involving no manipulation of those objects. Dynamic queries are those which involve actions transferring objects.

A. Concept Description Queries

In handling concept description queries such as, "What is read protection?" the hierarchy of object frames becomes very useful. From the network it is possible to locate relevant object frame relations. The following section of network is used in generating a static domain-specific representation of the latter query:

Now, say some user has used the TOPS-20 operat­ ing system for most of his computer time and decides to use UNIX for a change. Then he/she is likely to assume that UNIX is similar to TOPS-20. One could expect queries such as, "What is the permanent storage limit?".

The following relations from the object network are used:

directory-file

has permanent-storage-limit has application TOPS-20 has similarity disk-space-hard-limit.

The above relations denote the similarity between concepts from two operating systems. The similarity between disk-space-hard-limit and permanent-storage­ limit is marked using has relations. This mechanism is especially useful if a user thinks in terms of one operat­ ing system but is using another.

B. Dynamic Queries

The object hierarchy is availed of again for dynamic queries. However, as dynamic queries involve actions, action frames must be referenced. Say, for example we want to interpret the query, "What is the option on the cat command which numbers lines?". Looking at Figure 3, the first ORed condition would be matched. This condition constitutes the precondition for this particular query. The relevant postcondition is specified by the first ORed condition (Figure 4). This is done by moving down the object hierarchy from filter (Figure 4) to numbered-lines which are a type of filter. Also, the first action in Figure 5 is marked because "cat" was mentioned in the query. From Figure 6 we mark the user as being the relevant actor. Similarly, the query, "How do I print a file on the line printer?" matches ORed precondition two (Figure 3), ORed postcondition two (Figure 4), and no match is found in Figure 5. The actor is again "user" from Figure 6. C. Rules of Consequence

As we mentioned earlier, it is possible to "strengthen" preconditions and "weaken" postcondi­ tions for action frames without affecting the truth of the frame. Say, we have the query, "How do I print a dev­ ice file?". Even though we only represent files in the precondition set (Figure 3) it is possible to use inference rules to infer more specific preconditions. This inference capacity is implemented by moving down the object frame hierarchy from file to non-directory file to device file.

In this example the inference processes are rather straightforward. They simply involve moving down the object hierarchy from one object frame to another. In the example "How do I print a device file which has pageheaders?" the system should recognize pageheaders as being a precondition. Now, in the object network we can derive the relations:

pageheaders

is a type of filter is a type of visible-byte-sequence.

and from Figure 3 we know:

(o-rrame contents = (o-rrame visible-byte-sequence))

The inference processes used here involve com­ parison of objects such as pageheaders and visible-byte­ sequences. We use a process of projection to derive pageheaders as a precondition when they are not already specified.

It is also possible to "weaken" postconditions and still preserve the truth of {P} A {Q}. So, the query, "How do I print files on the printer?" will still be inter­ preted from the postcondition set in Figure 4 by weak­ ening the first ORed condition so that non-directory file becomes file.

The processes of strengthening and weakening above are definable by logical inference rules. More specifically, they are called the Rules of Consequence. The above rules and other inferencing techniques are described more completely in Me Kevitt (1986b ). In that paper there is a description of various rules and how they specify manipulation of action frames. The rules allow the system to directly infer new object preferences for action frames from the object hierarchy. Minsky (1975) also notes that we need some method of applying transformations between frames in a system. He says, "I do not understand the limitations of what can be done by simple processes working on frames. One could surely invent some "inference-frame technique" that could be used to rearrange terminals of other frames so as to simulate deductive logic."

It is important to note that only the "best" condi­ tions are selected while matching a frame to an initial meaning representation of some query. For each condi­ tion we determine the ratio of matched to non-matched predicates. The best condition is the one with the highest ratio. For any condition to be best not all its preferences have to be satisfied. Indeed, we saw above that the process of weakening postconditions is required because local preferences in conditions are not satisfied.

D. The Rule of Composition

Many queries about UNIX involve more than one action to complete some process. For example, the query, "How do I stop a listing of my directory, which is printing on the line printer?" involves three actions: "removing", "listing" and "printing". We call these queries embedded queries. The previous query is an an example of explicit embedding where three actions are explicitly mentioned. Other types of embedding are described in (Me Kevitt 1986a).

We use the notation [A 1 < A 2 < ... A.] to denote an embedding set where action A 1 is embedded inside action A 2, and so on. One can think of embedding in terms of a stack where A. is pushed on top of A._1 and so on. Interpreting the stack, the postcondition {Q} from performing A 1 is passed as a precondition to A 2 and so on until we reach the top of the stack. For the previous query we have the embedding set, [LIST < PRINT < REMOVE] and for the query, "How do I print a listing of my directory on the line printer?" we get, [LIST < PRINT]. In the latter example a directory is initially listed and then printed. In effect, the concept of listing is embedded inside printing. Certainly, in order to interpret queries involving embedding, we need to use some other inference rule to process action frames. We describe such an inference rule using the notation below:

This general formula states that if {P} A 1 { Q} is true and {Q} A 2 {R} is also true then we can infer {P} [A 1 < A2] {R} to be true too. We call this inference rule the Rule of Composition. A more specific formula for the example query, "How do I print a listing of my directory on the line printer?" is:

Interpreting this inference rule we deduce that if the postcondition of LIST is applied as the precondition of PRINT then it is inferred that the postcondition of PRINT is the postcondition of executing both actions.

We can formulate the domain specific information needed for the query, "How do I print a listing of my directory on the line printer?", in terms of {P} LIST {Q}, {Q} PRINT {R}. Our inference rule tells us that this is equivalent to {P} [LIST < PRINT] {R}. Note that the system must derive the new ·postcondition set {R}. The techniques for developing interpretations of other queries involving embedding are aspects of ongo­ ing research.

IV CONCLUSION

It is concluded that Transfer Semantics is an appropriate mechanism for describing actions and how these actions transfer objects. It seems a particularly effective mechanism for abstracting characteristics of various computer operating system actions in a concise formalism. The use of Transfer Semantics in OSCON enables the production of complex formal queries to be instantiated by a fully formalized database. Sets of con­ ditions for action frames are only preferences in the sys­ tem which are typical of some action. We use prefer­ ences for two reasons: (1) in order to select the correct frame (2) if we specified all possible transfer conditions on frames they would certainly become very large. Yet, the system is not restricted to preferred conditions due to the presence of various inference rules.

It is a significant feature of Transfer Semantics that there exists a number of inference rules enabling manipulation of action frames. Therefore, by using the object frame hierarchy and these inference rules an action frame can circumscribe a large quantity of domain-specific relations. In this paper we have shown the usefulness of logical inference rules of consequence and composition. The consequence rules enable the sys­ tem to infer more detailed or less specific objects from an object hierarchy. Embedded queries involving many concepts can be interpreted effectively on application of the composition rule.

A particularly useful feature of Transfer Semantics is that similarities between object frames are marked. Therefore, even though a query may be presented to OSCON with TOPS-20 lingo, that query can be inter­ preted and answered in terms of UNIX. It is hoped that Transfer Semantics will be used to model other operat­ ing systems as research continues.

We are continuing to build action frames for other actions such as "mailing", "moving", and "creating". Of particular interest is the possibility of recognizing user misconceptions in queries. For example, say a user asks the query, "How do I print a file with the -Z option?". "-Z" is not an option on printing. Nor, can -Z be inferred for printing. So, the action frame for "print­ ing" does not specify a formula of the form < {P} A {Q} U> because A is not satisfied. We also hope to investigate the possibility of recognizing ill-formed embedding. For example, the query, "How do I delete my files and then list them?" doesn't make much sense at all.

We have not described the meaning representations of English queries before the frames are matched to them. These representations are discussed in Me Kevitt (1986a). In this paper we are interested only in the frames themselves. Further research includes develop­ ing robust matching processes that determine the right frame for some q~ery.

A~KNO~ED�EMENTS

We wish to acknowledge the Natural Language Group at the Computing Research Laboratory (CRL) for valuable discussion on the content of this paper. We are indebted to the referees for suggested revisioRs.