Procedural Types

FUF also implements a third notion of type in unification: procedural types correspond to user-defined data-structures that are unified by special-purpose unification methods. The unification method describes how elements of the type fit in a partial order structure. Typed features are explicitly described (extensionally) partial orders. With procedural types, the partial order is intensionally described by a Lisp procedure.

Procedural types therefore allow the grammar to integrate complex objects that could hardly be described by standard FDs alone. Examples of procedural types are pattern (with the pattern unification method enforcing ordering constraints), cset (with the cset unification method checking for set equality) and tpattern defined in gr7.l in the example directory which implements the semantics of tense selection.    

There are limitations to the use of procedural types:

1.

Procedurally typed objects are always considered as leaves in an FD: that is, no matter how complex is the object, the unifier does not know how to traverse it from the outside. It is viewed as a black box. There is no notion of ``path'' within the object.

2.

Typed objects can only be unified with objects declared of the same type.

3.

It is the responsibility of the user to make sure that the unification method actually implements a real partial-order.

The following is a trivial (read: useless) example of how procedural types can be used. The syntax of define-procedural-type is described in Section .

          


;; Unification of 2 numbers is the max: order is the total order of
;; arithmetic  (which is also a partial order!)


(defun unify-numbers (n1 n2 &optional path)
  (max n1 n2))


(define-procedural-type 'num 'unify-numbers :syntax 'numberp)


> (u '((num 1)) '((num 2)))
((num 2))


> (u '((num 1)) '((num 0)))
((num 1))


;; Unification of 2 lists is the list with the more elements.
;; That defines a (probably not very useful) total order on lists.
(defun unify-lists (l1 l2 &optional path)
  (if (> (length l1) (length l2))
      l1
    l2))


(define-procedural-type 'list 'unify-lists :syntax 'sequencep)


> (u '((list (1 2 3))) '((list (1 2 3 4))))
((list (1 2 3 4)))


> (u '((list (1 2))) '((list (a b c d))))
((list (a b c d)))