The Prop project involves the design and implementation of an environment and an extension language based on C++ for compiler construction and program transformation. An outgrowth of this project is the Prop C++ class library, which contains an extensive set of support algorithms and data structures. Since a typical compiler manipulates many complex tree, dag and graph objects with extended lifetime, manual memory management using C++'s constructors and destructors, reference counting smart pointers, or some other techniques is frequently complex and error prone. Furthermore, with the advent of new algorithms for garbage collection, manual memory management techniques do not necessarily provide better performance or space utilization. To make it possible to make use of garbage collection as a viable alternative for memory management in C++[ED93], we have implemented a garbage collection class hierarchy as part of the Prop library. The class library can be used directly by the users who'd like to program in C++; it can also be used as part of the runtime system of a highly level language implemented in C++, as we have done for Prop.
We have several good reasons to prefer garbage collection over manual memory management. The Prop language contains many declarative constructs and extensions such as algebraic datatypes, pattern matching, rewriting, and logical inference. When a user programs in Prop using these constructs, an applicative style of programming is the most natural paradigm.