FUF(ID:4195/fuf001)

Functional Unification Formalism  

for Functional Unification Formalism

Michael Elhadad, Columbia University, 1989.



Structures:
Related languages
FUF => CFUF   Compiled by
References:
  • Elhadad, Michael. "FUF: The universal unifier user manual." Technical report, Department of Computer Science, Columbia University, 1989. view details ps ps
  • Kharitonov, Mark "CFUF: A Fast Interpreter for the Functional Unification Formalism" MSc thesis Ben-Gurion University of the Negev 1999 view details Abstract: Functional Unification is a popular formalism for the implementation of nat- ural language generation (NLG) system. The FUF programming language is a particular implementation of this formalism that is widely used within the NLG community. I present in this work the design, implementation and evaluation of CFUF, a fast interpreter for the FUF language.

    CFUF is fully compatible with the existing reference implementation of FUF that has been available since 1990. It can, in particular, run unchanged the SURGE generation grammar of English which has been developed in FUF.

    CFUF is built on the model of a virtual machine for the execution of FUF programs. The overall process of execution in CFUF is to compile input FUF terms (called functional descriptions or FDs) into an internal graph repre- sentation. The set of commands to manipulate such graph representations (FDC) is the base language of the FDVM (FD Virtual Machine).

    FUF grammars are translated into an AND-OR tree where each and- node contains a sequence of FDC commands. The FUF interpreter traverses the AND-OR tree in a non-deterministic manner and executes the FDC commands in the right context (as encoded in the set of registers of the FDVM). It also handles backtracking.

    The design of the FDVM takes into account the empirical fact that FUF programs are extremely non-deterministic and include lots of backtracking. We have therefore favored in the design decisions fast handling of backtracking and undoing. Particular attention has been paid to avoid copying struc- tures in memory as well, which is known to cost a lot of the practical runtime of unification-based formalisms. The result is a design based on a "clock mechanism" where modifications to the FD graph are never undone, but simply made invalid when a clock is advanced. Traversal of the graph is made, as a result more expensive, but the tradeoff is shown to be beneficial.

    Detailed performance evaluation is provided that demonstrates the well- foundedness of the major design decisions. An implementation of the CFUF design is provided and compared with the existing FUF interpreter. On large inputs, CFUF proves to be close to 100 times faster than the existing interpreter. ps