Abstract: In this paper, we show that one benefit of FUG, the ability to state global constraints on choice separately from syntactic rules, is difficult in generation systems based on augmented context free grammars (e.g., Definite Clause Grammars). They require that such constraints be expressed locally as part of syntactic rules and therefore, duplicated in the grammar. Finally, we discuss a reimplementation of FUG that achieves the similar levels of efficiency as Rubinoff's adaptation of MUMBLE, a deterministic language generator.
Introduction
In the field of Natural Language Generation (NLG), a primary challenge is determining the most appropriate way to express a specific idea. A single semantic concept can often be realized through multiple syntactic structures—for instance, choosing between an active voice ("The girl pet the cat") and a passive voice ("The cat was petted by the girl"). These choices are typically driven by pragmatic constraints such as "focus," which dictates which information the speaker intends to emphasize.
Historically, developers have faced a trade-off between the mathematical elegance of Functional Unification Grammar (FUG) and the computational efficiency of augmented context-free grammars like Definite Clause Grammars (DCG). This paper revisits FUG, arguing that its ability to handle global constraints makes it superior for NLG, and demonstrates that previous concerns regarding its performance were largely a matter of implementation rather than inherent flaws in the formalism.
The Problem: Rule Explosion in DCGs
In traditional formalisms like DCGs, pragmatic and syntactic constraints are often inextricably linked. Because DCGs require constraints to be expressed locally within syntactic rules, a developer who wishes to account for different focus options must often duplicate grammar rules for every possible combination of focus and syntax.
For example, if a grammar has three different ways to focus a sentence, the number of rules might triple to accommodate every variation. This "rule explosion" makes grammars difficult to maintain and scale. The core issue is that DCGs force a procedural approach: the developer must define exactly how to build a sentence for every specific case, rather than describing what the final result should look like.
The FUG Advantage: Separation of Constraints
Functional Unification Grammar offers a declarative alternative. In FUG, a constraint—such as "the focused item should be the subject"—can be stated as a single, independent pattern. This pattern then unifies with various syntactic structures during the generation process.
Key advantages of this approach include:
- Global Constraints: Constraints like voice or focus can be stated once and applied globally, rather than being repeated across every verb phrase rule.
- The Power of Paths: FUG utilizes "paths" (pointers within the grammar) that allow the system to build complex structures, such as relative clauses, by pointing to existing constituents. This simplifies tasks like "Focus Shift," where the system must decide whether to combine two sentences into a single complex one.
- Declarative Logic: By focusing on the properties of the output rather than the procedure for creating it, FUG allows for more elegant and maintainable grammar design.
Achieving Efficiency: The TAILOR System
Despite its elegance, FUG has historically been dismissed as too slow for practical use. The authors argue that this reputation stemmed from early, unoptimized "brute force" unifiers. To prove FUG's viability, they developed TAILOR, a reimplementation featuring several key optimizations:
- Category Indexing: Instead of attempting to unify input against every possible grammar category sequentially, TAILOR immediately selects the correct category.
- Lexical Retrieval: The system employs direct retrieval of lexical items, bypassing exhaustive searches.
- Pruning: By configuring the system to generate only the first successful sentence—rather than exploring every redundant syntactic variation—the search space is significantly reduced.
Evaluation and Results
The TAILOR system was evaluated using the TEXT system's appendix, a benchmark of 57 sentences. Performance was compared against the original TEXT tactical component and MUMBLE, a deterministic language generator known for its speed. To ensure a fair comparison across different hardware (including VAX-780, Symbolics 3600, and IBM 4381), the authors used benchmarks from Gabriel (1985) to normalize results.
Key Findings
- Significant Speedup: The new implementation achieved an average speed of 2.3 seconds per sentence on an IBM 4381. This represents a 130x speedup over the original FUG implementation used in the TEXT system.
- Competitive Performance: Even when accounting for hardware differences, TAILOR is estimated to be at least 3.5 times faster than previous state-of-the-art FUG unifiers.
- Parity with Determinism: Despite FUG being a non-deterministic formalism, TAILOR achieved speeds comparable to MUMBLE. This demonstrates that FUG is a practical choice for real-time generation tasks.
Conclusion
The findings suggest that the perceived inefficiency of Functional Unification Grammar was an implementation detail rather than a theoretical limitation. By separating global constraints from syntactic rules, FUG provides a more robust and elegant framework for NLG than DCGs. With modern optimization techniques, FUG systems can achieve the performance levels required for practical applications while maintaining the flexibility necessary for complex linguistic expression.
Future work remains in balancing global and local constraints, as some syntactic structures still require local representation. Additionally, for extremely complex logic, integrating external LISP functions may complement the unification formalism. Nonetheless, FUG stands as a powerful, efficient tool for the next generation of language systems.
Summary updated