An Experimental Applicative Programming Language for Linguistics and String Processing

P.a.c. Bailes, L.h. ReekerCOLING 1980

TL;DR

This paper introduces Post-X, an experimental programming language designed for linguistics and string processing. It modernizes Markov algorithms and SNOBOL's pattern matching within an applicative framework, aiming to provide a powerful and flexible tool for computational linguistics and beyond.

What Problem Does This Paper Address?

The authors identify a need for a programming language that excels at string and tree processing, particularly for applications in computational linguistics. Existing languages like COMIT and SNOBOL, while foundational, have limitations. The paper aims to address these by:

  • Modernizing Pattern Matching: Moving beyond the traditional Markov algorithm approach, which can be rigid.
  • Enhancing Applicative Programming: Integrating pattern matching into an applicative paradigm, inspired by figures like Backus, for more functional and potentially clearer code.
  • Bridging Linguistics and Programming: Incorporating natural language processing concepts into programming language design, as suggested by Hsu and Reeker.
  • Improving on SNOBOL: Retaining the powerful pattern matching of SNOBOL4 while addressing its perceived weaknesses in generalization, syntactic structure, and variable management.

Methods

Post-X introduces a novel data structure called a FORM for pattern matching. A FORM consists of a series of PATTERNS and associated ACTIONS.

  • PATTERNS: These define the structure of strings to be matched. They are composed of concatenated elements, which can be other PATTERNS, PRIMITIVE PATTERNS (similar to SNOBOL4 primitives), or literal STRINGS.
  • FORMS as Parameters: FORMS can accept parameters, which are then used within the pattern or action.
  • "Parse Tree" Return Value: A successful pattern match returns a "parse tree" representing the matched structure, rather than just a boolean success/failure. This tree can be manipulated by subsequent actions.
  • Selectors: The parse tree uses selectors (e.g., $1`, `$2) to refer to specific substrings or subtrees matched by pattern components. These selectors are local to a FORM, providing a cleaner scope than SNOBOL's persistence variables.
  • Applicative Framework: Pattern matching is integrated into an applicative style, meaning patterns must return values that can be used by other functions.
  • Conditional Constructs: Post-X supports conditional logic (if, elif, else) and sequence processing (do...od).
  • Tree Processing: The language extends pattern matching to trees, representing them as bracketed strings. Specialized functions like FUSE are provided for tree manipulation.

Datasets

Not discussed in the paper. The paper focuses on language design and illustrates its capabilities with examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • FORMS as Generalizable Patterns: The FORM concept is a significant generalization of SNOBOL patterns, allowing for more complex and structured pattern definitions.
  • Applicative Pattern Matching: Integrating pattern matching into an applicative paradigm is a key innovation, enabling functional composition and potentially more elegant solutions for linguistic tasks.
  • Local Selectors for Clarity: The use of local selectors for referring to matched substrings is a practical improvement over SNOBOL's global persistence variables, reducing the risk of naming conflicts and improving code readability.
  • Unified String and Tree Processing: The approach of representing trees as bracketed strings and applying similar pattern-matching mechanisms to both strings and trees simplifies the language and its conceptual model.
  • Linguistic Devices in Programming: The paper emphasizes the incorporation of natural language concepts (like extraposition) into programming language constructs, aiming for a more intuitive and expressive language for linguists.

Key Results

The paper presents Post-X as an experimental language and demonstrates its capabilities through examples of:

  • Arithmetic Expression Parsing: Showing how Post-X can parse and potentially evaluate arithmetic expressions, generating both unlabelled and labelled parse trees.
  • Random Sentence Generation: Illustrating how context-free grammars can be implemented and used for random sentence generation.
  • KWIC Index Generation: Demonstrating the language's ability to process sequences of strings, tag words, sort them, and produce a Keyword-in-Context index.
  • Linguistic Transformations: Providing formal specifications for English transformations like Equi NP Deletion and There Insertion using Post-X's tree processing features.

Limitations and Future Work

  • Experimental Nature: The "X" in Post-X signifies its experimental status, with features subject to change. The authors acknowledge that tree forms are not yet as natural as string forms and expect further changes.
  • Complexity of Sequence Generalization: The paper notes that generalizing pattern-directed processing to sequences without adding excessive complexity is an ongoing area of research.
  • Future Work: The authors suggest that further work is needed to determine how effectively pattern-directed processing can be generalized to sequences. They also imply that the language's design is still evolving, with the ultimate goal of a stable "Post" language.

Summary updated

BibTeX
@inproceedings{bailes1980experimental,
  author = {P.A.C. Bailes and L.H. Reeker},
  title = {{An Experimental Applicative Programming Language for Linguistics and String Processing}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1980},
}

Loading related content...

Figure