The Language

  The Prop language is fashioned as a superset of C++ and contains a number of extensions. While the extension language does not provide very high level symbolic manipulation and deductive formalisms offered in modern program transformation systems, it does provide a convenient set of constructs for many common symbolic programming tasks, features that are either impossible or hard to simulate using C++ 's classes or object oriented programming. The language provides:

• an algebraic datatype specification language to define the structure of user defined data;
• a grammar-based specification language that generates parsers and pretty printers that translate between text and abstract syntax; and
• rule based pattern matching, rewriting and inference constructs that manipulate and transform datatypes.

The datatype compiler is responsible for generating low level classes and their member functions to implement these high level datatypes. For example, it is possible to annotate an algebraic datatype to be garbage collectible, which signals the datatype compiler to automatically generate member functions that provide type feedback to the garbage collector. Similarly, a datatype defined to be persistent will have a number of member functions generated automatically to perform the task of serialization and reconstitution.

Aspects of object oriented programming have also been integrated with the datatype specification language. For example, it is possible to attach members, member functions or destructors to variants of a datatype. A datatype or a variant of a datatype may also inherit from other classes. In general, non-virtual inheritance can be seen as a sort of cartesian product while datatype variants can be seen as its dual: the sum.

Furthermore, to provide direct control of the data structure mapping process and to provide reuse of existing classes, it is possible for the user to directly specify the datatype to class mapping using the view mechanism. Using this mechanism, existing classes can be manipulated in an algebraic form transparently in the pattern matching constructs.

Pattern matching, rewriting, and inferences are compiled into inlined or table driven code with the pattern matching compiler in the translator. Since Prop began as an experiment on efficient compilation of pattern matching constructs, pattern matching code generated by the translator are very efficient, comparable to, if not surpassing, handcrafted code.

ML-style pattern matching, which is performed top-down, is compiled into a DFA-like decision tree, then transformed into inlined switch and if statements. An algorithm derived from the work on adaptive matching[] is used in the pattern matching optimizer. Rewriting in Prop is currently performed in a bottom-up manner. Rewriting rules are gathered and compiled into a bottom-up tree automaton using algorithms described in[Cha87,]. Finally, inference rules are compiled into a table-driven RETE-network.

Design principles

Although the design and development of Prop have progressed in an ad hoc manner, mostly driven by need, and sometimes by passing interesting, certain design principles have been maintained. These are as follows:

• Keep the extension language syntactically simple. First C++ is a language with few keywords and has a complex(many would say unreadable) syntax. In extending the language, we often opt to introduce new keywords rather than taking advantage of unused combinations of existing symbols and keywords. The syntax is in many regard borrowed directly from Standard ML: the syntax for algebraic datatype definitions is almost identical. The advantage of this approach is that it is immediately clear where the extension language is being utilized.
• Strong static typing. Unlike languages such as Lisp, SETL, or Prolog, in which the high level data structures used, i.e. s-expressions, sets and Herbrand terms are essentially untyped, strong static typing is used in Prop 's datatypes. This makes it possible detect many semantic errors at compile time and it also makes it possible to generate fast matching code.
• Algebraic datatypes as unifying data. We use algebraic datatypes as a unifying data structure in Prop . Cooperation between various high level formalisms in Prop is achieved by using algebraic datatypes as a common medium. For example, using algebraic datatypes to represent abstract syntax trees, ASTs created in the syntactic formalism can be used directly in subsequent pattern matching, rewriting, and inference phases of an application. Datatypes can be readily converted into text format using the pretty printing formalism, or marshalled into binary form and stored in an object store using the persistence capability.

Compromises

For a number of reasons, some unavoidable compromises have been made in the design and implementation of Prop :

• Since C++ is a complex language, both in syntax and semantics, it is nearly impossible to perform semantics analysis on C++ programs without extraordinary efforts. In particular, the work of a compiler frontend would have to be duplicated in order to gather enough information for analysis and transformation. We feel that the effort should be put into the efficient compilation of the extension language, so in the current version of the translator semantics information is not gathered for C++ code fragments.
• To retain maximum compatibility, even binary compatibility, with existing C++ code, libraries and applications, the code generated by Prop must be C++ obeying the usual calling convention, memory layout, etc.

  For example, although it would have been a good thing to provide first class functions in Prop , for this to be possible in a general way local variables must be transformed and packaged into closures, which would have altered the calling convention of functions. Since we have to provide binary compatibility with C++ , this transformation is undesirable. Thus until a satisfactory scheme is discovered Prop cannot have first class functions.

• Finally, C++ users who are unfamiliar with higher level programming languages are typically suspicious of features that incur a cost in runtime speed or space, even if the cost is well-justified by other concerns such as programming ease. Thus in the implementation of Prop we have omitted many higher level features(such as higher order unification, Prolog style logical variables, etc), that are desirable but cannot be efficiently mapped into C++ without additional research.

• Algebraic datatypes and pattern matching
• Tree rewriting
• Inference
• Syntactic formalisms
• Meta syntax
• Persistence
• Logical Variables, Feature Trees and Constraints
• Paradigm composition