Explore mode revisited

VL's Query and Explore mode are quite separate and distinct in function and purpose. Query mode is closely tied to conflict theory and is intended to be used primarily as a platform for computing meta-logical constructs related to that theory. Explore mode, on the other hand, does not compute conflicted and supported propositions. In addition, the nature of Explore mode would seem to preclude computing 'conflicted' and 'supported' as it requires a) constructing closed clause trees for both the proposition and its negation and b) checking interior nodes for conflict. Hence, Explore is rather disconnected from conflict theory in general and Query mode in particular. (A trivial exception is the feature which allows data exchange between the explore and query window.)

What Explore mode does do is provide an interesting way to view the execution space of logic programs. With the first prototype, Explore's capabilities were sufficiently compelling to warrant further experimentation. Since then, additional search of both the World Wide Web and the literature has uncovered systems similar to Explore. In particular, TPM (Transparent Prolog Machine) is a sophisticated and mature system which seems to do what Explore does and more. Although Explore mode does have some unique features of its own, the existence of these systems has a bearing on the question of how additional enhancements to Explore should be made.

There are at least two avenues for further development of Explore. One is to create a full-fledged visual tracer for logic programs in general and/or Prolog in particular. This would involve, among other things, showing logic program execution in much greater detail, including unification, variable propagation, etc. Since the current program relies partly on Prolog to perform unification, this approach would require extensive overhaul of the existing code, even possibly a rewrite using a lower-level language such as C. In any event, the resulting program would only duplicate some features found in more powerful systems. Therefore, a second, more sensible approach may be to retain the overall structure of Explore, concentrate on its unique features and strengths, and make incremental enhancements where feasible. Desirable features and interesting ideas in other systems should be borrowed and incorporated into Explore mode, provided that the benefits far outweigh the costs. (The costs of an addition or modification will be considered in term of a) how difficult its implementation will be; and b) how much it will complicate the current system, thereby detracting from its clarity and simplicity.) With this in mind then, the next section proposes steps for improving Explore mode.

Enhancing Explore mode

The first obvious improvement is to apply to Explore mode some of the techniques proposed earlier for viewing large trees in Query mode, namely, granularity and scaling. Once again, implementing the three levels of details would mainly involve modifying the methods for rendering the node object. Scaling may be a bit trickier since the trees in Explore constantly change. However, so long as the drawing methods at both the tree and node level keep track of the current scaling factor, it should not make a difference whether the trees are static or dynamic.

The second improvement relates to the way Explore performs redo. Recall that whenever a node P is redone, Explore automatically restores any node Q in the tree if Q was initially expanded after P. In other words, it prunes the current tree T_Qo rooted at Q and throws away the works done to expand Q. Typically, the user then has to re-expand Q, if only to get back to T_Qo. In some instance, it may be preferable to have a redo method that is less destructive, so to speak. This alternative redo would restore Q only if a) P and Q share one or more variables; and b) the shared variables are modified by the redo action. The motivation is to retain as much of the tree as possible, thereby minimizing having to re-expand the same nodes over and over. The caveat is that performing redo this way would not guarantee that all possible derivations can be obtained. What's more, providing yet another method of redo may prove too confusing to the user. Nevertheless, this may be an interesting idea worth pursuing.

Another potentially useful addition is a 'replay' facility that allows the user to retrace steps taken and to move forward. There are at least three ways to implement this feature. The first is to save a copy of the tree as the user performs operations on it. This essentially produces a snapshot of the tree though each step. When the user wishes to step backward, the program simply displays the previous tree, then the tree before that, and so forth. To go back to the beginning ('rewind'), the program displays the first recorded tree. Similarly, it displays the next tree in the sequence to step forward. The drawback of this method is that since only the graphical tree object is being saved, the program is merely replaying the execution in a VCR-like manner. No action -- expand, redo, etc. -- can be taken while in replay mode. To continue the execution, the user must first get out of replay mode by stepping forward to the end of the sequence; that is, the user must first return to the current point.

A second method remedies this flaw by saving all the data records associated with the nodes in the tree rather than just the graphical object. The recorded tree is not merely a static image but is actually 'live.' In essence, there is no difference between the recorded tree and the current tree: the user may perform any action with the former that can be done with the latter. Therefore, it is easy to step back to some previous point in the execution and choose a different branch to expand (for example).

Both these methods may potentially utilize a great deal of memory, especially for large trees. One way to reduce memory usage is to limit the number of steps that can be retraced. A more sophisticated approach, which constitutes the third method of implementing 'replay,' is to record only the action taken by the user. To step backward / forward, the program must then construct the previous / next tree by undoing / applying the recorded action to the current tree. This method would entail the least memory usage. Unfortunately, it may be unduly difficult to implement given the present program's structure.

Lastly, here are some additional miscellaneous improvements:

• Source code highlighting. Add an option to automatically highlight the appropriate clauses in the source file. That is, as a node is being expanded and redone, the clause being used should be highlighted in the source file window. The implementation would require retaining associations between the original clauses in the source file and their internal representations, i.e., the converted contrapositive clauses.

• Showing more information about nodes (with minimal effort). Distinguish between nodes whose subtrees have not been completely expanded and nodes whose subtrees have been completely expanded but are not closed. (Currently, Explore considers both types of nodes as identical and displays them in black.) This may be done by assigning a different color or shape to each type. In addition, it may be desirable to save past exploration result for each node, as is done by TPM. For example, the program may indicate in some way that a given node was 'evident' earlier but through subsequent backtracking no longer is.

• Dealing with the watch windows clutter. The watch windows provide convenient ways to show additional information for a node, to view matching clauses, and to select an arbitrary clause to expand or redo a node with. However, since each node may have its own watch window, the screen can quickly become very cluttered. Rather than having individual watch windows, it may be preferable to create a single, large watch window for all nodes. Needless to say, there should be means to quickly add and remove nodes to and from this window. Some experimentation will be required to determine how this capability can best be achieved.

• Detecting infinite looping (again). In light of the fact that VL does not have a rigorous infinite looping detection scheme and that the problem in general is difficult, if not insoluble, at the very least there should be a means for the user to stop a runaway execution or tree expansion. Though not entirely satisfactory, this seems to be a simple solution that is applicable to both Query and Explore mode. Other practical means can be devised to avoid the problem of infinite looping. For example, in Explore mode the user may tell the program to "expand this tree/subtree to no more than n levels deep." Also, it may be possible to pre-process the clause database and warn the user of an "unsafe" program, that is, one that may potentially lead to infinite recursion. (As a trivial case, a program with no function symbol is always safe.) To be of much use, the pre-processor must have a sufficiently sophisticated algorithm so that it does not classify nearly all programs as "unsafe." It is not known at this point whether such an algorithm exists or (if it does) whether it is efficient.