Typical List Traversal in FUF

Once lists are encoded as FDs, grammars need to be defined to traverse the lists and unify them according to the specific semantic of each list. Lists are traversed by recursive grammars, using the constituent traversal mechanism implemented by cset. The following example shows how to use the input shown above to build a clause out of the semantic input, by composing elements of the appropriate type. The grammar contains the categories semantic, find1 and find2. The easiest way to explain how this function works is by taking a procedural interpretation of the FUF flow of control. This procedural interpretation is explained in detail in Appendix . A constituent can be viewed as a procedure, that receives a certain set of parameters and computes new return values. In this example, the constituent semantic receives as input the features ents and rels which as shown in the FD input above. It computes a new feature clause as output, which is a linguistic constituent. To this end, it also uses two local variables stored in the features ent1 and rel1. All in all, the function of this category is to map a description of a semantic content into a linguistic clause description.

The grammar also implements two other categories, find1 and find2, which are the ones related to list processing. These categories can be interpreted as procedures searching a list for one or two matches. The simpler one is find1. Find1 receives two input parameters in1 and 1st-match which are a list of FDs and an FD. The category searches the list for the first-match in the list which can be unified with the feature 1st-match. When it is found, the feature 1st-match and the element in the list are unified (conflated). The category find2 operates the same way but for two features 1st-matchA and 1st-matchB.

          
;; A grammar to find matching elements in the list of semantic binary
;; relations and compose the matched elements into a linguistic clause
;; structure.
(def-grammar rules ()
 (clear-bk-class)
 '((ALT
    (((cat semantic)
      (ent1 ((cat find2)
	     (in2 {^2 ents})
	     (1st-matchA ((concept player) (name stockton)))
	     (1st-matchB ((concept stat)))))
      (rel1 ((cat find1)
	     (in1 {^2 rels})
	     (1st-match ((concept stat-rel)
			 (args ((carrier {^4 ent1 1st-matchA})
				(stat {^4 ent1 1st-matchB})))))))
      (cset ((= ent1 rel1)))
      (clause ((cat clause)
	       (process stat)
	       (args {^2 rel1 1st-match args}))))


;; LIST PROCESSING CONSTITUENTS:
     ;; Find one element in a list in1 that matches 1st-match and unifies
     ;; it with 1st-match.
     ;; If no element in list in1, fail
     ;; If first element matches 1st-match, unify and stop recursion
     ;; Else recurse on rest of in1.
     ;; 1st-match is always linked to the top-level 1st-match feature in
     ;; the embedded structure of recursive calls.
     ((cat find1)
      (fset (in1 1st-match rest cat cset))
      (ALT find1 (((1st-match {^ in1 car})
		   (cset ()))
		  ((rest ((cat find1)
			  (1st-match {^2 1st-match})
			  (in1 {^2 in1 cdr})))
		   (cset ((= rest)))))))


;; Find 2 elements in a list in2 that match 1st-matchA and 1st-matchB
     ;; and unify them.
     ((cat find2)
      (fset (in2 1st-matchA 1st-matchB restA restB cat cset))
      (cset ((= restA restB)))
      (restA ((cat find1)
	      (1st-match {^2 1st-matchA})
	      (in1 {^2 in2})))
      (restB ((cat find1)
	      (1st-match {^2 1st-matchB})
	      (in1 {^2 in2}))))))))


;; To test:
;; (setq output (uni-fd (input) (rules)))
;; (top-gdp output {clause args carrier})
;; (top-gdp output {clause args stat})
          
          

The list traversal is implemented in the category find1. The grammar for find1 contains a typical list recursion, similar to the following Lisp function:

          
(defun find1 (in1 match1)
  (if (equal match1 (car in1))
      match1
      (find1 (cdr in1) match1)))
          
          

Naturally, since the grammar is written in FUF it performs differently, but the structure is similar. The if test is implemented as an alt, and the recursive call is implemented by a cset expansion to the sub-constituent rest. This structure is typical of the FUF list traversal categories and can be found in a similar form in the SURGE segment dealing with conjunctions.