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 be an association list associating network names with networks. So here are the English2 networks in Lisp form:
(setq networks '((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)))))
Here, of course, NP is the name of a network, whereas V is an abbreviation. Our network traverser can tell what the possibilities are, because the network names are the atoms that appear as keys in networks. When our network traversers come across a label that is not #, we will assume that if the label is not a key in networks then it must be either an abbreviation or a simple symbol.
To make our network traversal programs of Chapter 2 work with RTNs, we need to revise our concept of state and incorporate this revision into the arguments for the relevant next functions. A state now has an extra component - a stack of locations to return to. Our previous next functions, for various recognition and generation tasks, took arguments as follows:
(defun next (node tape network) ...
where node was the name of the node in the network and tape was the list of symbols remaining to be processed. For RTNs we will revise this to be:
(defun 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, and in particular to push an item onto the top of a stack, yielding a new stack, and to pop the top item off a stack, to discover what this 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 car of the list is the top element of the stack and the cdr of the list is the remaining stack. If we use this representation, pushing an item onto a stack amounts to using cons to create a new list with that item on the front, popping an item from a stack amounts to using car and cdr to access the first element and remaining elements of the list; finally, the empty stack is represented by the empty list, NIL.
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:
(<networkname> <node>)
- where <networkname> 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 might have the same node names used in different networks. Code:rtnrecog.lsp
The top level function for RTN recognition is very similar to the finite state case. However, note that we pass in the name of the network (i.e. an atom) through the first argument networkname, rather than the network itself (i.e. a complex list structure). In RTN traversal we are constantly passing around references to different networks; it will make things like TRACE output much more comprehensible if we pass around the names rather than the list structures.
(defun rtn_recognize (networkname tape) (catch 'rtn (dolist (initialnode (initial_nodes (get_network networkname))) (rtn_recognize_next networkname initialnode tape ())) nil))
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 function get_network will do this job for us:
(defun get_network (name) (cadr (assoc name networks)))
Here now is the next function (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.
(defun rtn_recognize_next (networkname node tape stack) (if (member node (final_nodes (get_network networkname))) (rtn_recognize_pop tape stack)) (dolist (transition (transitions (get_network networkname))) (if (equal (trans_node transition) node) (let ((label (trans_label transition)) (newnode (trans_newnode transition))) (if (get_network label) ;; interpret label as network name (rtn_recognize_push label networkname newnode tape stack)) ;; interpret label as symbol/abbreviation (rtn_recognize_traverse label networkname newnode tape stack)))))
For this definition, the main work is parcelled up in three subfunctions. The function 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:
(defun rtn_recognize_traverse (label networkname newnode tape stack) (dolist (newtape (rtn_recognize_move label tape)) (rtn_recognize_next networkname newnode newtape stack)))
This subfunction 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 subfunctions 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 call rtn_recognize_next with the stored elements on the top of the stack:
(defun rtn_recognize_pop (tape stack) (if (and (null stack) (null tape)) (throw 'rtn t) (if (not (null stack)) ; not finished (rtn_recognize_next (caar stack) ; stacked networkname (cadar stack) ; stacked node name tape (cdr stack)))))
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:
(defun rtn_recognize_push (label networkname newnode tape stack) (dolist (initialnode (initial_nodes (get_network label))) (rtn_recognize_next label initialnode tape (cons (list networkname newnode) stack))))
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 function is exactly the same as the one used in the finite state network recognizer:
(defun rtn_recognize_move (label tape) (recognize_move label tape))
Send us a comment.