The Design of a Computer Language for Linguistic Information

Stuart M. ShieberCOLING 1984

TL;DR

This paper introduces PATR-II, a computer language designed for encoding linguistic information. It leverages concepts from programming language design and semantics to create a powerful yet simple formalism for natural language processing, aiming to bridge the gap between linguistic theory and computational implementation.

What Problem Does This Paper Address?

The core challenge addressed is how to effectively endow computers with human language capabilities. This involves two main difficulties: our incomplete understanding of human language itself, and the primitiveness of current computational tools for representing and processing linguistic knowledge. The authors argue that existing approaches in computer science, particularly programming language design and semantics, offer valuable insights that can be adapted to create more robust and expressive languages for linguistic information.

Methods

The paper presents PATR-II, a formalism built upon an extended pattern-matching technique called unification. Unlike traditional logic-based unification, PATR-II operates on directed acyclic graphs (DAGs). These DAGs can represent atomic symbols or sets of label/value pairs, where values can themselves be DAGs. This allows for a unified representation of lexical, syntactic, and semantic information.

Key aspects of the PATR-II formalism include:

  • Context-Free Phrase Structure Rules: These define the basic structure of sentences.
  • Unifications: These specify equivalences that must hold among the DAGs associated with constituents in a rule.
  • Templates: A mechanism for defining reusable linguistic constructs and removing redundancy in the lexicon.
  • Lexical Rules: User-definable operations that allow for the derivation of word variants from a prototype entry, encoding relationships like passive voice or "there" insertion.

The formalism emphasizes declarativeness, meaning the order of operations does not affect the outcome, and modularity, achieved through templates and lexical rules.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unification on DAGs: The core innovation is applying unification, a powerful logical operation, to DAGs as the primary data structure for linguistic information. This provides a flexible and expressive way to represent complex linguistic features.
  • Unified Representation: PATR-II uses a single representation (DAGs) for lexical, syntactic, and semantic information, simplifying the overall system and facilitating the integration of different linguistic levels.
  • Bridging Linguistics and Computer Science: The paper demonstrates how established principles from programming language design (e.g., declarative semantics, modularity) can be directly applied to the design of computational linguistic tools, leading to more robust and well-founded formalisms.
  • Power and Decidability: While PATR-II is powerful enough to model complex linguistic phenomena (akin to a Turing machine), the authors discuss how constraints can be imposed to ensure decidability, a crucial property for practical computational systems.
  • Syntactic Sugar for Expressiveness: The introduction of templates and lexical rules is presented not as part of the core formalism but as "syntactic sugar" to enhance usability and allow users to tailor the system to specific linguistic theories and needs without compromising the underlying simplicity and well-foundedness.

Key Results

The paper does not present quantitative results in terms of specific performance metrics on datasets. Instead, it focuses on the design principles and capabilities of the PATR-II formalism. The key "results" are:

  • The successful modeling of a wide range of linguistic phenomena, including subcategorization, passive voice, "there" insertion, extraposition, raising, equi-NP constructions, unbounded dependencies (Wh-movement, relative clauses), head-feature percolation, and LFG-like semantic forms.
  • The existence of three dissimilar implementations of the PATR-II system, all yielding identical results on the same grammars. This demonstrates the implementability and robustness of the formalism across different parsing algorithms, unification methods, and rule compilation techniques.

Limitations and Future Work

  • Verbosity and Redundancy: The bare PATR-II formalism, as initially presented, is acknowledged to be verbose and redundant, necessitating the development of higher-level constructs like templates and lexical rules for practical use.
  • Decidability: While the formalism is powerful, ensuring decidability for all possible grammars is an ongoing concern, with suggestions to leverage properties like off-line parsability from context-free grammar skeletons.
  • Semantics: The paper mentions pursuing a less powerful model for the denotational semantics, suggesting that the full power of domain theory might not be necessary for all applications.
  • Extensions: The authors note that extensions such as disjunction and negation in graph structures have been implemented by others (e.g., at the University of Texas) and that these extensions are being considered for integration into the SRI systems.

Summary updated

BibTeX
@inproceedings{shieber1984design,
  author = {Stuart M. Shieber},
  title = {{The Design of a Computer Language for Linguistic Information}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1984},
}
Figure