Prop: a C++ based pattern matching language


Prop is a multi-paradigm extension of C++ that includes string matching, algebraic datatypes, Standard ML-style pattern matching, pretty printing, term and graph rewriting, inference, and simple persistence as built-in features. Prop is designed as a development language for interpreters, compilers, and language translation and transformation tools. It simplifies the construction of these systems by providing high level declarative and rule based formalisms on top of the traditional procedural and object-oriented paradigms of the base language.

We design Prop with two main objectives in mind: the first objective is to improve the productivity of programmers working in a mainstream imperative language--- especially in domains such as compilers and language implementation--- by introducing high level formalisms based on trees and attributed labeled graphs, tree and graph rewriting, and finite set theory. By providing the users with a wide array of high level data structures and program combining forms, we encourage the use of the appropriate level of abstraction in each component of a language processing system. Rather than restricted to a single imperative mode of thinking, users can utilize applicative, transformational, equational, deductive, imperative or even a combination of formalisms in a cooperative manner. For example, syntactic analysis can be performed with the parsing/lexical analysis constructs of Prop; semantic analysis with pattern matching, tree rewriting, and inference; optimization with the SETL-style sub-language and graph rewriting; and, finally, code generation and machine language level tools development with tree reduction with dynamic programming and bit-string pattern matching.

The second objective is high performance and portability. Programs written in Prop are lightweight and efficient: i.e. unneeded features are never included in the runtime system of a program, and those that are included are first transformed into interpretation free C++ code. All features are translated into C++ (using a source to source translator written in itself) using efficient algorithms. Maximal compatibility with the base language is maintained by mapping all high level data structures of directly into C++ classes. These classes can be used transparently as if they are written by the user. Thus we minimize the data impedance mismatch between different abstraction levels. A result of this is that high level programs written in Prop can readily utilize existing code and libraries with little change. An optional conservative garbage collector can also be linked into the runtime system for Prop programs that desire automatic memory reclamation.

Additional Information

These are some unfinished documents on the language.


Currently the following features have been implemented:

Sample Programs

The following are some simple programs written in Prop version 2.3.0.

Source Code

The source code is available in tar'ed and gzipped form. To compile the translator and the runtime support library, g++ 2.5.8, 2.6.3, or 2.7.x is required.

Here are the versions currently available. The latest non-alpha version is usually the most up-to-date and stable. The reference manual is included in all distributions.

Validate this page