Programming of Reversible Systems in Computational Linguistics

Gerhard EngelienCOLING 1967

TL;DR

This paper explores the challenges and advantages of programming reversible systems for computational linguistics, focusing on a novel matrix-based approach developed by the LIMAS group. The authors argue that reversibility, while seemingly complex, actually simplifies debugging and analysis by allowing for simultaneous testing of both synthesis and analysis processes.

What Problem Does This Paper Address?

Computational linguistics often deals with complex, non-numerical systems where the relationship between input and output can be intricate. Traditional programming methods for these systems can make it difficult to debug and verify the accuracy of linguistic analysis and synthesis. The authors highlight the need for programming paradigms that can handle the bidirectional nature of linguistic processes – understanding how a form is constructed (synthesis) and how to break down a form into its constituent parts (analysis). They propose a reversible system as a solution to streamline this process and improve debugging efficiency.

Methods

The core of the proposed method is a reversible data flow matrix. This matrix uses "and" and "or" gates, along with elements that can block flow in one direction, to represent linguistic processes.

  • Analysis: Grammatical descriptions of inflected forms are determined by combining inflection class with endings. This process involves combining "channels" of information.
  • Synthesis: The process reverses this, using grammatical variables to determine the appropriate ending.
  • Reversibility: The key innovation is that the same matrix can be used for both analysis and synthesis. This allows for testing both directions simultaneously, greatly simplifying debugging.
  • List Processing: For implementation on conventional sequential computers, the paper discusses using list processing. This involves encoding endings, inflection classes, and grammatical information into bit combinations within a list. A search program then locates these combinations.
  • Formula-like Representation: An alternative is to represent the process using logical functions (Boolean algebra), where variables are indexed and related by equations. This can be automatically generated from lists.
  • Three-Dimensional Binary Matrix: The paper suggests that these lists can also be stored in a three-dimensional binary matrix for processing.

Datasets

Not discussed in the paper. The paper focuses on the methodology and theoretical framework rather than specific datasets.

Key Insights and Ideas

  • Reversibility as a Debugging Aid: The most significant insight is that reversibility doesn't complicate programming; it facilitates debugging. By being able to test both analysis and synthesis with the same system, errors become more apparent and easier to pinpoint.
  • Parallel Processing Simulation: The matrix approach inherently represents parallel processing, which, when simulated on sequential computers, increases running time but is acceptable for testing purposes.
  • Efficiency through List/Matrix Structures: The use of lists and matrices, especially when organized by frequency or divided into sublists, offers significant time-saving potential for searching and processing linguistic data.
  • Distinction Between Numerical and Non-Numerical Processing: The paper clearly outlines the fundamental differences, emphasizing the large input/output and extensive computation in numerical processing versus the large input/output, limited computation, and large storage needs of non-numerical processing.

Key Results

The paper doesn't present quantitative results in terms of accuracy or speedup percentages. Instead, it focuses on the conceptual advantages of the reversible system. The primary "result" is the demonstration that a reversible matrix-based approach can simplify the programming and debugging of computational linguistic systems. The authors suggest that if the matrices were internally wired, an acceleration factor of "about 1000" could be achieved, though this is a hypothetical scenario.

Limitations and Future Work

  • Simulation Overhead: The paper acknowledges that simulating parallel processing on sequential computers leads to an increase in running time. This is deemed irrelevant for testing but would be a factor in a production system.
  • Hardware Requirements: For optimal performance, the authors suggest desirable computer features like byte-structure storage, bidirectional tape readers, large disk storage, a high-speed printer with special characters, and sophisticated wired addressing procedures. The implication is that current conventional computers might not be ideal for large-scale implementation.
  • Future Work: The paper implicitly suggests that further development of the matrix hardware and software would be beneficial. The mention of annexing extra hardware like Dr. Hoppe's matrix points towards a direction of specialized hardware for linguistic processing. The authors also suggest that wired search and sorting programs would be practical.

Summary updated

BibTeX
@inproceedings{engelien1967programming,
  author = {Gerhard Engelien},
  title = {{Programming of Reversible Systems in Computational Linguistics}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1967},
}
Figure