Send us a comment. We can represent recursive transition networks as list structures in the same way as finite-state networks. In general, we now need to present more than one network simultaneously, however. We also need to allow networks to be named and arcs to have network names as labels, as well as symbols, abbreviations and #s. The way that we will achieve this is to have a global variable networks which will contain a list of all the networks and their names. In the networks list we will adopt the convention that network names alternate with networks, each name immediately preceding its network. So here are the ENGLISH-2 networks in Pop11 form:
[ S [ [Initial 0] [Final 2] [From 0 to 1 by NP] [From 1 to 2 by VP]] NP [ [Initial 0] [Final 2] [From 0 to 1 by DET] [From 1 to 2 by N] [From 2 to 3 by WH] [From 3 to 2 by VP]] VP [ [Initial 0] [Final 1 2] [From 0 to 1 by V] [From 1 to 2 by NP] [From 1 to 3 by that] [From 3 to 2 by S]] ] -> networks;
Here, of course, NP is the name of a network whereas V is only an abbreviation. Our network traverser can tell what the possibilities are, because only words that appear at the top level of networks name networks. When our network traversers come across a label that is not #, we will assume that if the label is not in networks, then it must be either an abbreviation or a simple symbol.
To make our network traversal programs of Chapter 2 work with recursive networks, we need to revise our concept of state and incorporate this revision into the arguments for the relevant next procedures. A state now has an extra component - a stack of locations to return to. Our previous next procedures, for various recognition and generation tasks, took arguments as follows:
define next(node, tape, network); ...
where node was the name of the node in the network, tape was the list of symbols remaining to be processed and network was the network. For recursive networks, we will revise this to be:
define next(networkname, node, tape, stack); ...
where networkname and node together say where the kangaroo is (in which network and at what node of that network), tape gives the list of symbols and stack represents the line of waiting kangaroos.
We need to have ways to manipulate the stack of locations; in particular, to push an item on to the top of a stack, yielding a new stack; to pop the top item off a stack, to discover what the item is and what is left of the stack; finally, it is useful to be able to test whether a stack is empty. In fact, it is very straightforward to implement stacks as lists, where the head of the list is the top element of the stack and the tail of the list is the remaining stack. If we use this representation, pushing an item on to a stack amounts to using '::' to create a new list with that item on the front, popping an item from a stack amounts to using the matcher to access the head and tail of the list and, finally, the empty stack is represented by the empty list.
We now need some ways of manipulating locations themselves. Previously, when we were restricted to a single network, a location could be simply the name of a node. Now, we will represent a location by a pair of values:
[?net ?node]
where net is the name of a network and node is the name of a node in that network. Having the network name explicitly available inside the location data structure means that we can quickly tell which network we are in and can switch networks quickly. It is also essential if we have used the same node names in different networks. Code:rtnrecog.p
The top-level procedure for RTN recognition is very similar to the finite-state case. However, note that we pass in the name of the network (that is, a word) through the first argument networkname, rather than the network itself (that is, a complex list structure). In RTN traversal, we are constantly passing around references to different networks; hence, it will make things like trace output much more comprehensible if we pass around the names rather than the list structures.
define rtn_recognize(networkname, tape); vars i; for i in initial_nodes(get_network(networkname)) do rtn_recognize_next(networkname, i, tape,[]) endfor; false enddefine;
Notice that each initial state considered has an empty stack (the last argument to rtn_recognize_next). We will frequently need to get the network list structure from the name of a network and the procedure get_network will do this job for us:
define get_network(name) -> network; networks --> [== ^name ?network ==] enddefine;
Here now is the next procedure (called rtn_recognize_next) for recognition with RTNs. As in the finite-state case, it exits as soon as it has made a successful traversal.
define rtn_recognize_next(networkname, node, tape, stack); vars newnode label; if member(node,final_nodes(get_network(networkname))) then rtn_recognize_pop(networkname, node, tape, stack); endif; foreach [From ^node to ?newnode by ?label] in transitions(get_network(networkname)) do if member(label, networks) then rtn_recognize_push(label, networkname, newnode, tape, stack) endif; rtn_recognize_traverse(label, networkname, newnode, tape, stack) endforeach enddefine;
For this definition, the main work is parcelled up in three subprocedures. The procedure RTN_RECOGNIZE_TRAVERSE contains a kernel (dealing with the SYM', ABB' and JMP' rules), like the non-recursive RECOGNIZE_NEXT. Its job is to deal with the consequences of traversing a single arc:
define rtn_recognize_traverse(label,networkname,newnode,tape,stack); vars newtape; for newtape in [%rtn_recognize_move(label,tape)%] do rtn_recognize_next(networkname,newnode,newtape,stack) endfor enddefine;
This subprocedure calls rtn_recognize_move to move the tape in all possible ways, parcelling up each new tape into a new state which will be examined by another RTN_RECOGNIZE_NEXT. As well as RTN_RECOGNIZE_TRAVERSE, RTN_RECOGNIZE_NEXT also calls the subprocedures RTN_RECOGNIZE_PUSH and RTN_RECOGNIZE_POP, corresponding to the PUSH and POP rules. The POP rule can be tried if NODE is a final node in its network. If the stack is empty and the tape is also exhausted, then we have successfully finished the original traversal. If on the other hand the stack is not empty, we take the top item off the stack, storing the new stack in NEWSTACK. The top item is the location to return to; its network name is put in NEWNETWORKNAME and its node in NEWNODE. We then explore the new state that results from resuming at this point with the popped stack:
define rtn_recognize_pop(networkname,node,tape,stack); vars newnetworkname newnode newstack; if stack = [] and tape = [] then true; exitfrom(rtn_recognize) elseif stack matches [[?newnetworkname ?newnode] ??newstack] then rtn_recognize_next(newnetworkname,newnode,tape,newstack) endif enddefine;
With the PUSH rule (which applies if an arc label is an element of NETWORKS), we construct a new state for each initial node of the subnetwork. This state has the same tape as the original state and a stack which has the destination of the arc pushed onto it. So when we emerge from that network, we will continue from wherever this arc leads:
define rtn_recognize_push(label,networkname,newnode,tape,stack); vars i; for i in initial_nodes(get_network(label)) do rtn_recognize_next(label,i,tape,[[^networkname ^newnode] ^^stack]) endfor enddefine;
Note that even if the PUSH rule does apply for a given arc, in RTN_RECOGNIZE_NEXT we still check for the label being an abbreviation, a symbol, etc. in the usual way (using RTN_RECOGNIZE_TRAVERSE).
We still have not defined rtn_recognize_move, which finds all legal ways of moving the tape during the traversal of an arc. This procedure is exactly the same as the one used in the finite-state network recognizer:
recognize_move -> rtn_recognize_move;
Send us a comment.