Kahina for QType Tutorial Part 2: Basic Tracing

This tutorial assumes that the project QType Tutorials 1-3 was opened, and that the grammar has already been compiled from within Kahina. The most direct way to match these prerequisites is to follow the instructions in QTypeTutorial1. The basic terminology we use here to talk about interface components is also introduced there.

In this tutorial, you will learn how to start a parse process, and how to use Kahina with roughly the functionality of a simple Prolog tracer.

Starting a Parse

For our first parse, we will use uther as a very short test input. To start a parse, we select the menu item Grammar -> Parse ... and enter the sentence to be parsed in the input prompt which appears:

This causes QType to call the Prolog goal lc([uther]), but only entering its call port and transmitting step data to Kahina, then waiting for trace commands to be issued via the control panel. The contents of your Kahina window should look like this once the parse has been started:

The first step shows up in the step tree as the child of a virtual root node which is labeled [query] to indicate that the control flow originated in a query performed by the user. The standard view of the step tree presents the call tree in two levels of detail. On the left side, the entire call structure of the parse execution is visualized by indentation. By default, the currently active step is selected and highlighted in yellow. The right side presents the call hierarchy below the currently selected step on the left side in more detail. The color of the text at the nodes provides information about the port in the procedural box model that a goal is currently at. At the moment, our single first step is colored in black to indicate that it has only entered the call port yet.

The goal display shows the goal at the currently selected step in the control flow tree in a more human-readable fashion. The task of the step tree is to provide information on which steps are being performed in which order, whereas the goal view is the main display for step details. At the moment, we only see a slightly more optically pleasing representation of the instance of QType's top-level lc/1 predicate which has just been called.

The Procedural Box Model and Color Codes

In the step tree, nodes are colored according to the step state, which mostly corresponds to the port in Prolog's procedural box model that was last reached by the associated goal. In the following table, we give a list of the states by their internal names, which we will also use in this tutorial for convenience. The Color column explains the colors used by Kahina's default color model for Prolog debugging to indicate the different step states.

State	Color	Meaning
CALL	black	The associated goal is at the call port, i.e. it has merely been invoked.
EXIT	light green	The associated goal has reached the exit port once, i.e. it was successfully completed but further solutions may exist.
FAIL	red	The associated goal has reached the fail port, i.e. it has failed.
REDO	blue	The associated goal is at the redo port, i.e. it has been reinvoked during backtracking.
DET_EXIT	dark green	The associated goal has reached the exit port deterministically, i.e. there can be no further solutions.
EXCEPTION	pink	The associated goal has failed because of a Prolog-side exception.

The Control Panel

The execution of the program being traced is controled via the buttons in the control panel. We start with a quick overview of the relevant buttons.

	Creep: The smallest possible step. If you keep clicking the creep button, you step through the execution of a program in all available detail. Depending on the state of the program, creep leads to the creation of a new node, or to an existing node changing its status. After each creep operation, the affected step will be automatically selected.
	Fail: Forces the current goal to fail without execution. Can be useful to test parts of a program that would not normally be executed.
	Auto-complete: Activates a fast-forward mode, i.e. execution will keep creeping, until the node where we started changes its status. Auto-completion can be aborted at any time by clicking on the auto-complete button again, or interrupted and resumed using the pause button.
	Skip: Like auto-complete, but done on the Prolog side, i.e. the underlying Prolog debugger is told to skip execution of the step. This has the advantage of being much more efficient since substeps are not transmitted to Kahina. This is of course also a disadvantage: the descendant steps of the skipped step are never shown, so use this with care. Skip cannot be paused. Also, it is only possible to skip the most recently called or redone step, not arbitrarily selected steps.
	Leap: Activates a fast-forward mode which can be interrupted at any time by clicking the button again. Can be useful for letting (large parts of) a program execute completely to inspect the execution later. The name leap is used because the command is typically used together with Kahina's control agent system (see QTypeTutorial4) to emulate the behavior of a Prolog tracer's leap command.
	Pause: Clicking this button interrupts a running auto-complete, i.e. the fast-forward stops, but the step being autocompleted is remembered. When pause is clicked again, auto-complete of this step is resumed.
	Abort: Aborts the current program execution, equivalent to the 'a' command in a Prolog tracer.

Depending on the state of the underlying Prolog process (e.g. the state of the current goal), all buttons whose execution does not make sense will be greyed out.

Aborting a Parse

Before we start tracing, it is useful to know that at any point, you can click the Abort button to abort the trace. This will set back Kahina to the state at the beginning of this tutorial, except that the step data from the trace will still be displayed for inspection. The control panel will be greyed out to indicate that you are disconnected from the underlying Prolog process, and have no possibility to influence it other than by starting a new trace.

In this tutorial, you will only need to abort the trace if you accidentally clicked a wrong button or get lost for some other reason. You may want to try aborting and and starting the same parse again right now, before you start losing tracing data by aborting. Notice that the displayed contents of the message console and the step tree are only reset once the new parse was started.

Restarting a Parse

As an alternative option for aborting the trace of a parsing process and starting the same parse from scratch, the Grammar menu offers the item Restart parse. In our case, this will have the same consequences as if you had clicked on the Abort button and had started the same parse again via Grammar -> Parse ..., except that the grammar will first recompiled. Once the compilation has finished (e.g. after you skipped it), Kahina will automatically restart the last parse. Since we will not be making changes to any grammar files, this option will not be used in this tutorial. Nevertheless, you could still try this out now.

The Creep Command

We will now go through the parse of "uther" in full detail and very slowly, making sure that the graphical tracer as well as the internals of QType which are relevant for debugging grammars with Kahina are presented in a very thorough fashion. A first-time user of a Kahina-based debugger should invest the time to patiently follow the remaining sections of this tutorial, although it might cause tracing to seem like a very slow and burdensome task.

The efforts will pay off, for after making sure that the exact procedure is once correctly understood, starting with QTypeTutorial4 we will introduce advanced features which allow a grammar developer to get into this much detail only at the places where it really matters. The strength of Kahina lies in the ability to dynamically fine-tune the degree of detail, which makes it possible to sift out relevant details from computations which are almost impossible to trace otherwise. In order to learn to make use of these abilities, however, it is recommendable to only use Kahina like a graphical variant of a classical Prolog tracer, until the concepts are thoroughly understood.

So let us begin our first trace. Just like in a Prolog tracer, we can go through the goal resolution step-by-step by using the creep command. In Kahina, this operation is accessed via the keyboard shortcut 'C' or via the Creep button in the control panel.

When we click the Creep button once, QType is asked to descend one layer into the computation, calling the first subgoal of lc([uther]). QType sends the information that it has now called the subgoal lc(top,[uther]) back to Kahina, where it is displayed as a child of our first step in the step tree:

Note that the new step is now twice indented, showing the child-parent relation to the call of lc([uther]). Because the new node is automatically selected, the detail view on the right now only displays the new step.

When we move forward by another Creep, we see that the first thing lc/2 does is to call the predicate lexentry_existence/2, whose task is to check whether all the words in the sentence are defined in the grammar's lexicon. After one more Creep, we see that lexentry_existence/2 calls db_word/4 to retrieve the lexical entry for the first and only word on the list, uther:

Note that the lexentry_existence/2 step in the overview tree is now displayed in bold font, indicating that the step now contains substeps which are not displayed in the overview call tree, but can be seen in the detailed call tree if the step is selected. The bold font therefore gives the user a visual hint whether a step in the overview tree hides more steps which can be inspected by selecting it.

In this step, we can also see that the goal display is color-coded: black color is used for predicates, grey color for Prolog constants, and green color highlights Prolog variables.

The next step shows us that a lexical entry for uther was successfully retrieved, and it showcases both the code location display and the feature structure rendering abilities of the goal view:

This is the first time that we can see a step leaving its procedural box via the exit port. The successful completion of the call to db_word/4 puts the corresponding step into the DET_EXIT state, which is indicated by the dark green color of the corresponding node in the step tree.

Moreover, the goal display now represents the state of the predicate's arguments both before and after the call. The in part shows the state of the arguments at the call port (and is therefore identical to the structure we saw in the last step), whereas the new out part shows the instantiation of the arguments after reaching the exit port. As the second argument of db_word/4 in the "out" part of the goal view, we can see the feature structure which represents the lexical entry for uther in the grammar. Note that the types of the feature logic receive a blue signal color in the goal display.

Finally, the retrieval of this lexical entry was our first interaction with the grammar file. The code location view automatically displays the relevant file, highlighting the line which was relevant for the current step (in this case, a line defining a lexical entry for the string "uther" using the @name macro).

Now that the word list has successfully been processed by lexentry_existence/2, the predicate is about to enter and exit its base case. Two Creep commands later, this innermost call has successfully and deterministically exited. Note that the source code view is back to highlighting the subgoal which led to the base case.

After the next Creep, the base call to lexentry_existence/2 reaches the exit port, causing the entire call hierarchy under it to be colored in dark green. Note that the yellow marking of the selected step in the call tree moves up as well, always marking the last step which reached one of the ports. On the message console, all the messages that concerned the selected step are highlighted, putting a bracket around all the steps which occurred between the ports. Note that the source code highlighting also moves back to the line where the base call to lexentry_existence/2 was issued.

This completes the first phase of the parse. QType has checked for the existence of lexical entries for all the words in the sentence, and we have been able to follow this process in considerable detail. In most cases, the user will not want to see all these details, meaning that the entire part of the trace we just completed will usually be skipped. However, in the case where unexpectedly some lexical entry could not be retrieved, it is useful to be able to check where the retrieval went wrong.

The Skip Command

After another Creep step, the processing of lc(top,[uther]) enters its next subgoal, a call to mgu/2 in order to generate the most general satisfier of the description top. In the code view, we see that this is because we need the MGS of the trivial prediction top for QType's left-corner parsing scheme.

The processing of this subgoal would take place entirely in the detail tree, reflecting that a user will not often be interested in the exact details of how a call to mgu/2 is processed. We will soon enough see some parts of QType's feature logic mechanism at work, but for now, we will do what a grammar engineer will do in most cases for calls to mgu/2: we will skip over this goal, leaving the inner workings to the Prolog process and not cluttering up our step tree with the rather extensive details of its execution. After issuing the Skip command, your Kahina window should display roughly the following contents:

Note that the mgu/2 step is almost immediately put into the DET_EXIT state, and that the message console now contains a line saying that you (the user) have caused a skip operation at the mgu/2 step. The details of the involved computation can be seen neither on the message console nor in the step tree. This shows the trade-off involved whenever you use the skip command: it is a lot faster than creeping through the details, but it also has the disadvantage that none of the computation details is transmitted to and accessible from Kahina. The goal display gives us information about the changes in the goal's arguments during its execution. The second argument was just an anonymous variable before, now it contains the trivial feature structure, which is indeed the most general satisfier of the trivial description top.

The Fail Command

The next Creep command lets QType descend into the next phase of the parsing process, which is started by a call to the lc/5 predicate. In its first two arguments, the lc/5 predicate builds a constituent structure and a feature structure. The third argument receives the prediction feature structure (which is the trivial structure for this initial call), and the last two arguments are responsible for processing the list of input symbols:

If we descend into this goal call using Creep, we see that the next step consists in retrieving the lexicon entry for uther. One more Creep that the corresponding call to db_word/2 succeeds and retrieves a feature structure for uther which we can inspect in the goal view. The next Creep carries us onward to the next subgoal of lc/5, a call to check_link/2 which serves to retrieve a category from the precompiled grammar for prediction within the left-corner parsing scheme. In our case, because the feature structure for uther is of type name, check_link/2 will list all categories which can start with a constituent of type name according to the grammar.

One Creep later, we see that check_link/2 non-deterministically exits with check_link(name,s), proposing that the left-corner parser should try to build a constituent of type s starting with the lexical entry for uther. After the next Creep, we see in the goal display that this information is handed on to a call of lc_complete/8 as the 4th and 5th arguments. Since we have already consumed the entire input, the last three arguments are empty lists.

Our knowledge of the left-corner parsing algorithm tells us that a completion cannot succeed when there is no input to consume. If you would creep through this execution of lc_complete/8, it would therefore fail eventually. However, if we already know that this goal will fail, there is no need any more to inspect how exactly this happens. In such a situation, we can tell Kahina to just give up proving the current goal by issuing the Fail command. As a result, the color of the associated step changes to red, and we can expect backtracking to happen in the next step.

After another Creep command, you will see that QType has backtracked into our check_link/2 step, which is now colored in blue because we have entered its REDO port. This is a situation where the two-layer tree display potentially becomes a little confusing, so let us discuss in detail what happened in this view.

If you do not fiddle about the step tree in any way during a trace, it will always display the part of the call tree that represents the hierarchy of goal calls leading to the current position in Prolog's search space. This means that during backtracking, the part of the call hierarchy below the last choicepoint will vanish and subsequently be replaced by the call structure which arises while Prolog explores the new branch in its search space.

The interesting point now is that unlike other graphical debuggers, Kahina keeps the steps on failed branches accessible via a second dimension in the step tree. In addition to the call tree of the current goal invocation, the step tree also represents the search tree consisting of choice points and branches. At each choice point where multiple alternatives have been tried, the step tree view will display little arrows next to the step, which allow the user to flip between different branches of the search tree.

This feature of Kahina goes beyond ordinary tracing by making it possible to inspect almost all details of a Prolog process even after the execution, which will be the main subject of QTypeTutorial3. The reader should feel encouraged to flip back and forth between the current branch and the failed branch of the execution right now. It is not necessary to revert to the new branch before continuing, as with the next tracing command the step tree display will automatically flip back to the active branch.

The next Creep lets check_link/2 exit with a different variable binding. This time, the compiled grammar provides us with the (trivial) information that a structure of type name can also start a constituent of type name, which is of course exactly what we need here.

One Creep later, we are back in lc_complete/8 with much more promising arguments than the last time. The ensuing process of creating a constituent of type name out of a feature structure of that type might seem trivial, but it will of course still require QType to execute a number of steps.

The Auto-Complete Command

After another Creep, you will see in the source code display that QType has conveniently already entered the termination clause of lc_complete/8, where it tries to unify the predicted feature structure with the current constituent. The corresponding unify/2 goal has already been called, and we could now step through the entire complex process of determining whether two feature structures which are already identical can actually be unified.

Usually, one would want to skip calls to unify/2 just as we skipped the call to mgu/2 before. However, if a parse fails, the reasons for this failure will in most cases be failed unifications. While skipping over unify/2 nodes will tell you whether unifications fail or succeed, they will not allow you to more closely inspect the reasons in case of failure. To avoid this, we can use the auto-complete command which combines some of the advantages of creeping and skipping. Unlike in skip mode, all the internal details of the step will be transferred to Kahina for later inspection. This makes the auto-complete operation a lot slower than skipping, but it is still a lot faster than creeping through the entire execution because Kahina will not update its various views during he process, saving a lot of execution time.

You should now click on the Auto-Complete button to start the process. You will not see any updates to the step tree, the source code view or the goal display, but much information about the called steps will arrive at the message console. Note that you can interrupt and continue a running auto-complete operation at any point by using the Pause button. It is also possible to abort an auto-complete operation by clicking the Auto-Complete button again to unlock it. This will cause the operation to stop somewhere in the middle, and it will not be possible to resume the auto-complete operation because Kahina will have forgotten at which node you started it.

After a few seconds, you should witness the views being updated, and the unify/2 step now colored in dark green. Below this node, you should see a lot of new steps in the detail view of the step tree. These are the inner workings of the unify/2 predicate, and being able to inspect them in such detail can be of great help in determining where some tricky unification went wrong. However, in our case we are happy that the unification succeeded as inspected, and that the out section of the goal display shows both arguments identified.

The Leap Command

After the next Creep, you see that the next step of lc_complete/8 involves using mgu/2 to construct a constituent structure out of an empty goal list. The parsing process is essentially complete at this point, and the remaining steps mostly consist of assembling the final constituent and feature structures and handing them up to calling predicates. We are not interested in these details any more, so we want to get to the end result of the parse as fast as possible.

For such situations, where we want to auto-complete entire processes without stopping whenever we get back to the step where we started auto-completion, Kahina offers the leap command. This commands starts the leap mode, which will become very useful once we know how to automatize the issuing of break commands. For the moment, we will only learn how to use in the spirit of a primitive cassette recorder's fast-forward mode.

After clicking on the Leap button, you will again see a lot happening on the message console, but no updates to the other components. The leap mode can be interrupted at any point by clicking on the Leap button again to release it. If you keep leaping to the end of the trace, the result will look like this:

Although the entire step tree seems to be colored in red now, this does not mean that the entire parse has failed. We are still at the last active branch, and we only see red because this last backtracking branch has failed.

Inspecting a Finished Parse

So how do we get to the parse results? The answer of course is that we need to navigate through the search dimension of our step tree using the little arrows provided. As a shortcut for going to the leftmost and rightmost branches, the tree displays have little buttons with double arrows at the upper left corner. After clicking on the double arrow to the left at the top of the overview tree, you should start to see a lot more green. We have actually switched back to the branch which we manually caused to fail earlier. However, we can see now that it was only a subbranch which we caused to fail. The calling lc/2 goal succeeded in another branch.

In the current version of Kahina, the parsing results are somewhat buried in the step details, but they are easy to find if you know where to look. The trick is to select the topmost invocation of lc/2 right below the lexentry_existence/2 check. The following screenshot shows which node to select in our case:

The fact that the selected lc/2 has exited means that we will have some structures to inspect in the goal display. You will see that in addition to the usual sections labeled in and out, we now have an fs section showing the final feature structure representing the sentence, and a constituent tree under the label cs.

If multiple parses where found, each of these parses will correspond to one such lc/2 node in the search tree. In future versions of Kahina, we are planning to make parsing results more conveniently accessible, probably with a list of pointers into the relevant positions of the step tree.

Further Steps

The next tutorial QTypeTutorial3 will make you familiar with post-mortem inspection in Kahina. But if you are more interested in Kahina's mechanisms for control automation, which make tracing a lot more enjoyable, you can also proceed to QTypeTutorial4 immediately.