Send us a comment. ATNs are just RTNS annotated with extra tests and actions, and so we can represent them as list structures simply by embellishing our existing notation. We will require that each network declare the registers that are to be used within it (as many programming languages require a function to declare its local variables). In addition, a network will specify tests and actions to be performed:
initially (i.e. when the network is entered) finally (i.e. when the network is exited) on all transitions (i.e. as each transition is made)
Here is our example ATN expressed in list notation (it also appears as lib atnarcs1). We use Lisp lists to represent the sequences of symbols built by the program. Code:atnarcs1.lsp
(setq networks '((S ((Registers (pps auxs mood mainverb arg0 arg1)) (Initial (0) t ((setq pps ()) (setq auxs ()))) (Final (3) t ((list mood (append (list mainverb (list (quote arg0) arg0) (list (quote arg1) arg1) ) pps)))) (From 0 to 1 by NP t ((setq arg0 star) (setq mood (quote add)))) (From 1 to 2 by V t ((setq mainverb star))) (From 2 to 2 by V t ((setq auxs (cons mainverb auxs)) (setq mainverb star))) (From 2 to 3 by NP t ((setq arg1 star))) (From 2 to 3 by |#| t ((setq arg1 ()))) (From 3 to 3 by PP t ((setq pps (cons star pps)))))) (NP ((Registers (res)) (Initial (0) t ()) (Final (1) t (res)) (From 0 to 1 by PN t ((setq res star))))) (PP ((Registers (p arg)) (Initial (0) t ()) (Final (2) t ((list p arg))) (From 0 to 1 by P t ((setq p star))) (From 1 to 2 by NP t ((setq arg star)))))))
(setq abbreviations '((PN abbreviates john mary susan peter) (P abbreviates with behind) (V abbreviates will see)))
Each network now has an additional Registers statement, which specifies the (local) registers that are going to be used within that network. At the end of each Initial or Final statement, as well as at the end of each transition statement, there are two extra list components, specifying the tests and actions to be performed. Tests and actions are represented by lists containing normal Lisp code, which may treat the local registers of the network and the global registers star (which represents *) and hold like normal Lisp variables. The instructions in these lists will then be executed at appropriate times. Many ATN systems use a restricted language for actions and tests, which are then evaluated by an interpreter. We will not present such a language: firstly, because the common actions of assignment and building lists are so naturally expressed in a normal programming language and, secondly, because there seems to be no principled way of restricting the actions and tests that might be needed. We therefore allow actions and tests to be arbitrary Lisp code, whose results may or may not be noticed, as appropriate. Tests are obviously expected to produce results, as are the actions associated with the Final parts of networks (whose results will be used as the value of the *-register in the network above). On the other hand, any results returned by other action code will simply be ignored.
Lib atnrecog implements a simple ATN traverser that works with ATNs represented as we have just discussed. Although the details of the implementation are unimportant and much of the following description can be skipped, it is important to have some conception of how the implementation of an ATN differs from that of an RTN. First of all, since the ATN list structures have more components that RTNs, we need to redefine our basic network accessing functions accordingly. Apart from redefining functions like initial_nodes to take account of the extra components, we need to introduce new functions to extract the tests and actions from various places in the networks: Code:atnrecog.lsp
(defun initial_tests (net) (nth 2 (assoc 'Initial net)))
(defun initial_actions (net) (nth 3 (assoc 'Initial net)))
(defun final_tests (net) (nth 2 (assoc 'Final net)))
(defun final_actions (net) (nth 3 (assoc 'Final net)))
(remember that nth numbers the elements of a list starting with 0). Here are two important functions to do with accessing registers:
(defun regs_used (net) (nth 1 (assoc 'Registers net)))
(defun initial_regs (net) (list (regs_used net) (mapcar #'not (regs_used net))))
regs_used just enables one to find out the local registers declared for a given network. initial_regs returns a list with two elements, the first being the list of register names, and the second being a list with the same length, each element of which is nil:
(regs_used (get_network 's))
(PPS AUXS MOOD MAINVERB SUBJ OBJ)
(initial_regs (get_network 's))
((PPS AUXS MOOD MAINVERB SUBJ OBJ) (() () () () () ()))
When we store the values of the registers of a network, we will use precisely this representation, a list of the register names followed by a list of the register values, where each value is associated with the corresponding element of the register name list. Here we use nil as the initial value of a register (as Lisp does for local variables) and so the initial_regs of a network represent the registers together with their initial values.
ATNs are an extension of RTNs because of the use of registers. But registers produce added complication in the implementation, because we have to deal with alternative values of registers in different search paths. A state of an ATN recognition can now be represented by the following:
R1. the current node (and network name). R2. the remaining symbols. R3. the stack of return points. R4. the values of the local registers. R5. the value of the HOLD register.
Of these, the first three are more or less the same as for the RTN case. The stack must, however, contain more complex objects in an ATN. When a POP occurs during recognition, the top element of the stack must hold enough information for the computation to resume in the higher network. This must include the values of the registers as they were when that network was pushed from and a record of any actions that have to be performed on the result of the subnetwork computation before the traversal in the higher network can be completed. It must also, as before, hold the network and node names specifying where the traversal in the higher network is to resume. The HOLD register needs special attention in the implementation as it is a global register, whereas all the other registers are local to particular subnetworks.
We can derive an ATN traverser from our RTN traverser in much the same way that we derived our RTN traverser from a FSTN traverser. That is, we can create an ATN traverser by appropriately enriching the notion of a state to include the values of the registers in all the networks being traversed. The appropriate next function header now looks like the following:
(defun atn_recognize_next (networkname node tape stack regs hold)
where regs is the set of registers and their values for the current network, and hold is the current value of the hold register. Where are the values of the registers in other active networks kept? They are kept in the stack, a stack element now being of the form:
(<networkname> <node> <regs> <tests> <actions>)
where <networkname> and <node> are as before - these specify in which network and to which node the system is to return. <regs>, <tests> and <actions> specify the current registers of that network and any tests and actions that have to be performed before the system can successfully return to that network. We will define the functions stacked_networkname, stacked_node, stacked_regs, stacked_tests and stacked_actions to retrieve these parts from the top element of a given stack. Notice that, although the hold register is global, its value is part of the search state, that is, it may have different values on different traversals of the network. This is why we do not actually implement it as a global variable in Lisp. Here is the definition of atn_recognize_next. As with the RTN recognizer, the main work is dealt with by specialized functions to push, pop and traverse an arc:
(defun atn_recognize_next (networkname node tape stack regs hold) (if (member node (final_nodes (get_network networkname))) (atn_recognize_pop networkname tape stack regs hold)) (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 (atn_recognize_push label networkname transition tape stack regs hold)) ;; interpret label as symbol/abbreviation (atn_recognize_traverse label networkname transition tape stack regs hold)))))
As in the RTN case, the first thing for atn_recognize_next to do is to try to pop from the current network. If node is a final node in the current network, then atn_recognize_pop is called:
(defun atn_recognize_pop (networkname tape stack regs hold) (if (dotests regs (final_tests (get_network networkname)) hold nil) (let ( (star_newhold (dopopactions regs (final_actions (get_network networkname)) hold nil))) (if (and (null stack) (null tape)) ;; end of top-level network (throw 'atn (car star_newhold)) (if (and stack ;; end of subsidiary network ;; do tests at end of original PUSH (dotests (stacked_regs stack) (stacked_tests stack) (cadr star_newhold) ; hold (car star_newhold))) ; star (result of POP) ;; execute actions at end of original PUSH (let ( (newregs_newhold (doactions (stacked_regs stack) (stacked_actions stack) (cadr star_newhold) ; hold (car star_newhold)))) ; star ;; proceed in original network, using stacked values (atn_recognize_next (stacked_networkname stack) (stacked_node stack) tape (cdr stack) (car newregs_newhold) (cadr newregs_newhold))))))))
Before initiating a pop, this function checks that the final tests associated with the network are satisfied (calling function dotests). The final actions, executed by the function dopopactions, then produce two results, one of which becomes the new value of the star register, and the second of which will be the new value of the hold register. Star is returned as the result of the whole analysis if both the stack and the tape are empty. If the stack is not empty, it is necessary to resume in a higher network, restoring the values that are saved in the stack. In this case, it is also necessary to apply the tests saved from the push arc before continuing.
After attempting to pop, the only other possibility is to find a network arc from node that can be traversed. Thus atn_recognize_next iterates through the arcs that leave this node. If the label is the name of a network, it calls atn_recognize_push to attempt to enter that subnetwork. If the initial tests in that network succeed, we push to the new network, producing a new stack which has the networkname, destination newnode of the arc, registers regs and the arc tests and actions pushed on the front:
(defun atn_recognize_push (label networkname transition tape stack regs hold) (let ((newnet (get_network label))) ;; try tests at start of proposed network (if (dotests (initial_regs newnet) (initial_tests newnet) hold nil) ;; execute actions at start of new network (let ((newregs_newhold (doactions (initial_regs newnet) (initial_actions newnet) hold nil))) ;; explore from all initial nodes (dolist (initialnode (initial_nodes newnet)) (atn_recognize_next label initialnode tape (cons ; new value of stack (list networkname ; network (trans_newnode transition) ; destination node regs ; registers (trans_tests transition) ; post tests (trans_actions transition) ; post actions ) stack) (car newregs_newhold) (cadr newregs_newhold)))))))
Notice that the tests and actions associated with the push arc are saved up to be tried when the subnetwork is finally popped from. If the label is not the name of a network, we move the tape in the standard way according to what the label is, and we also check that the arc tests succeed and compute the new registers and new value of hold that result from executing the arc actions. This is done by atn_recognize_traverse:
(defun atn_recognize_traverse (label networkname transition tape stack regs hold) ;; try moving the tape (dolist (newtape (recognize_move label tape)) ;; set the star register (let ((star (diff_tape newtape tape))) ;; try the arc tests (if (dotests regs (trans_tests transition) hold star) (let ( (newregs_newhold ;; execute the arc actions (doactions regs (trans_actions transition) hold star))) ;; continue from the destination node (atn_recognize_next networkname (trans_newnode transition) newtape stack (car newregs_newhold) (cadr newregs_newhold)))))))
This completes the definition of atn_recognize_next and its main subfunctions.
There are a few other main functions that remain to be defined. diff_tape is used to set the * register; it simply looks to see how much of the tape has been consumed by a transition. dotests is used to execute a set of tests, whereas doactions and dopopactions are used to execute a set of actions. dopopactions is for actions performed as a network is exited (which must return a value for '*'), whereas doactions is for other sets of actions (which do not produce results). doactions expects arguments as follows:
(defun doactions (regs actions hold star)
where regs is the current local registers and their values, actions is the list of actions to be performed and hold and star are the current values of the appropriate global registers The result will be a list of two values - the new local registers and the new value of the hold register after the actions have been performed. For instance, the call:
(doactions '((pps auxa mood mainverb arg0 arg1) (() () () () () ())) '((setq arg0 star)(setq mood (quote add))) '() 'np)
executes the actions:
(setq arg0 star) (setq mood (quote add))
in a network with registers pps, auxs, mood, mainverb, arg0 and arg1, all with values nil, in a context where hold is nil and star (the * register) is np. This call will produce a list of two items - first of all the new values of the registers and secondly the new value of the hold register, here simply nil:
(((pps auxa mood mainverb arg0 arg1) (() () add () np ())) ())
Notice how the register values returned reflect the changes to arg0 and mood. doactions works by creating a list of items representing a Lisp function which contains the appropriate actions. In this example, the function that results would be essentially what would arise from the following definition:
(defun xxx (star hold pps auxa mood mainverb arg0 arg1) (setq arg0 star) (setq mood 'add) (list (list '(pps auxa mood mainverb arg0 arg1) (list pps auxa mood mainverb arg0 arg1)) hold))
Finally, this function is called, by apply, with the appropriate arguments supplied, and the results are manipulated into the results of doactions. dotests and dopopactions are defined using very similar techniques.
Code:atnarcs2.lsp
Send us a comment.