In this chapter and the next, we will develop a number of programs for performing useful tasks with various kinds of networks. These programs will have a certain 'family resemblance' but will differ in their details. The first task we will consider is using a network for recognition (the task 'recognize'). The procedure recognize, given a network and a 'tape' (list of items), will return true or false, according to whether the list is accepted by the network. Here is its definition: Code:fsrecog.p
define recognize(network, tape); vars i; for i in initial_nodes(network) do recognize_next(i, tape, network) endfor; false enddefine;
Although the initial procedure called is recognize, the bulk of the work in this program is done by the procedure recognize_next. Recognize_next is given a node in the network, a tape (list of remaining words) and a network. Its job is to explore all the ways the network can be traversed, starting at the given node and using up precisely the words that are on the tape. So, initially we have to call recognize_next repeatedly, once with each initial node of the network. This ensures that all possible paths are explored:
define recognize_next(node, tape, network); vars newnode label newtape; if tape = [] and member(node, final_nodes(network)) then true; exitfrom(recognize) else foreach [From ^node to ?newnode by ?label] in transitions(network) do for newtape in [%recognize_move(label,tape)%] do recognize_next(newnode, newtape, network) endfor endforeach endif enddefine;
Looking first at the else part of the definition, we can see that recognize_next goes through the network arcs that originate from the node it is given. For each arc, it attempts to 'move the tape' as directed by the label on the arc. Recognize_move returns all the possible new values of the tape and these are collected in a list by the [% ... %] brackets. In fact, for recognition, there is always either one new value, if the required item is at the front of the tape, or no new value, if the required value is not. Then, for each of these possible new versions of the tape, recognize_next is called recursively, with the destination of the arc and the new tape. Thus, recognize_next finds all the possible ways of moving one step further in the network and, with each of these, delegates the problem of looking further to another call of recognize_next.
In terms of our previous discussion, each call of recognize_next is in charge of a single state, whose node and tape are given by the first two arguments. recognize_next works out what new states immediately follow from this and calls recognize_next on each of these in turn. Figure 2.6 shows the pattern of calls that results if we look at the sequence
[kim was a consumer and lee was stupid]
using the ENGLISH-1 network (with the network arguments omitted). In this tree, a procedure call is shown above the procedure calls that it invokes. Notice that the call tree in Figure 2.6 mirrors the search tree exactly.
It is readily seen from the figure that in this case there was hardly any search - each of the first three calls of recognize_next only produced a single new state. The calls marked with Xs produced no new states and yet were not successful final states. In investigating all the possibilities, our program tries all the states that arise from a given alternative before trying alternatives to it, traversing the tree from left to right. This means that it is doing a depth-first search. However, the program improves on the general search algorithm, in that it represents most of the pool of alternatives implicitly rather than explicitly. When a given call of recognize_next is generated, the next alternative at that level in the call tree is only actually computed when the first call returns - that is, it indicates failure.
Given that every call of recognize_next can end up calling another recognize_next, how does the program terminate? If the network can indeed be traversed, we can hope that eventually a call of recognize_next will be generated where the node is a final node of the network and the tape is empty. This is the case tested for by the if part of the definition. If the test succeeds, it is now known that the network can be traversed, and no more searching needs to be done. In general, we will be quite deep in recursive calls of recognize_next when this happens, and so we need to stop any further work being done in any of them. So, we use exitfrom to make the program abandon all of these, returning from the original call to recognize with the result true. What if the network cannot be traversed using the given tape? In this case, all the calls to recognize_next will eventually peter out, reaching states from which no further progress can be made. Once the whole set of possibilities has been searched and all calls of recognize_next have returned, we are back in the procedure recognize and can return the result false. There is only one problem remaining. If there could be infinitely many paths to try in order to traverse the network, we will not be able to search through all of them before announcing false. Indeed, we might spend so much time looking at infinite parts of the search space that we might never find a successful traversal, if it exists. Fortunately, the only way this could happen would be through the network having cycles (circular sequences of arcs) consisting of arcs labelled '#'. For instance, the network only needs to have a transition of the form:
[From n to n by #]
for the search among all possible traversals to be infinite in some cases. It is not a serious problem to avoid introducing cases like this into our networks.
With a definition of recognize_move, our program will be complete. recognize_move returns a new tape or nothing, depending on the label and the existing tape. If the first word in the tape is the same as the label (the SYM case), then the rest of the tape is returned. Similarly, if the next word is abbreviated by the label (the ABB case). Finally, if the label is '#' (the JMP case), the tape is returned unchanged. In all other cases, nothing is returned - we cannot take this arc in the network. Here is the definition of recognize_move: Code:fstape.p
define recognize_move(label, tape); if tape matches [^label ==] then tl(tape) elseif tape /= [] and abbreviations matches [== [^label == ^(hd(tape)) ==] ==] then tl(tape) elseif label = "#" then tape else ;;; return nothing endif enddefine;
Let us consider now what has to be done if we wish to adapt this program for the exhaustive generation of all the sequences that are allowed by a transition network. We still need to search all possible paths through the network, but now we are not constrained to traverse arcs that are compatible with an input tape. For generation, we will use the tape to record the words generated so far. Thus, the tape will start as the empty list and will get longer as we progress through the network. Here is the procedure for generating possible new tapes (corresponding roughly to the procedure recognize_move):
define generate_move(label, tape); vars x exps; if label = "#" then tape elseif abbreviations matches [== [^label abbreviates ??exps] ==] then for x in exps do [^^tape ^x] endfor else [^^tape ^label] endif enddefine;
Note that generate_move can produce several results. When the label on the network arc is an abbreviation, any of the words abbreviated can appear in the output tape. The procedures generate and generate_next used for exhaustive generation are very similar to the procedures recognize and recognize_next used for recognition. Here are their definitions: Code:fsgen.p
define generate_next(node, tape, network); vars newnode label newtape; if member(node, final_nodes(network)) then tape => endif; foreach [From ^node to ?newnode by ?label] in transitions(network) do for newtape in [%generate_move(label, tape)%] do generate_next(newnode, newtape, network) endfor endforeach enddefine;
define generate(network); vars i; for i in initial_nodes(network) do generate_next(i, [], network) endfor enddefine;
Note how the initial calls to generate_next have [] as the tape argument and that the test for termination in generate_next does not have to specify anything about the tape. In addition, since we are generating all the legal sequences, we do not want to exit back to the top procedure when we find a solution. Instead, the program prints out the successful tape and keeps going.
One trouble with exhaustive generation is that it cannot be allowed to run to completion if the network allows an infinite number of different strings. Nevertheless, it can still be useful to run such a system for a while, to get an idea of the range of the strings allowed by a network. If we try generating from the ENGLISH-1 network, however, we do not get any solutions and the program gets into an infinite loop. The trouble is that there are places in the network that allow certain constructions to be iterated indefinitely in the language. As the generate program makes choices in a fixed order, if it ever chooses to repeat a particular type of phrase, it will always choose to do this and so will try to produce an infinitely long sentence.
If the transitions of a network are reordered to avoid non-productive infinite loops, there is still a problem in that the program does not produce a 'representative sample' of the strings allowed. This is because, once the program has made a decision about part of the string, it is happy to go on investigating other decisions that it encounters later. Only if for some reason all future possibilities fail to work out will it remake this decision. Because of the way one call of generate_next has to return (exhaust all its possibilities) before another can run, the program will always focus on one alternative and further developments from it, before it tries other alternatives.
Send us a comment.