Language for Modular Programming on Term Rewriting Systems

In a few years, term rewriting systems[5] becomes popular and common as a computation model, especially a model for functional programming languages. Because it has special features, e. g. its denotational or algebraic semantics is corresponding to its operational semantics under some condition. Nevertheless it has no features of modularization for the structural programming, so it is claimed that term rewriting systems have the same computation power as turing machines and we can program anything by term rewriting systems, but we may not program large scale one because term rewriting systems have no modularization mechanism in themselves. In a couple of years, the direct sum system of term rewriting systems[5][6][7] that is a disjoint union of term rewriting systems ; renaming symbols appearing in them so that no name conflict can arise, was proposed for a key to the solution. But the direct sum system is too weak to modularize term rewriting systems because it is so hard to divide the programming into pieces that process shared resources, i. e. in the direct sum system, a module can not know any data representation of other modules. In this paper we propose a programming language MT for which we may describe a term rewriting system by a set of smal1 scale ones. We will show the structural programming, i. e. the modularization, in term rewriting systems later.