Traditional multiset rewriting arises from a fragment of polarized linear logic, deriving its semantics from focused proof search. In recent years, languages based on multiset rewriting have been used for ever more ambitious applications. As program size grows however, so does the overhead of team-based development and the need for reusing components. Furthermore, there is a point where keeping a large flat collection of rules becomes impractical. In this report, we propose a module system for a small logically-motivated rule-based language that subsumes traditional multiset rewriting. The resulting modules are nothing more than rewrite rules of a specific form, and therefore are themselves just formulas in logic. Yet, they provide some of the same features found in advanced module systems such as that of Standard ML, in particular name space separation, support for abstract data types, parametrization by values and by other modules (functors in ML). Additionally, our modules offer features that are essential for concurrent programming, for example facilities of sharing private names. This work establishes a foundation for modularity in rule-based languages and is directly applicable to many languages based on multiset rewriting, most forward-chaining logic programming languages and many process algebras.

63 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu