H.R.Walters and J.F.Th.Kamperman
Equational programming is the use of (confluent) term rewriting systems as an implementation language with don't care non-determinism, against a formal background of algebraic specification with term rewriting as a concrete model.
EPIC is an equational programming language primarily developed as a `formal system language'. That is, it is strongly based on equational specification and term rewriting, but its operational semantics are too specific for a specification language.
EPIC has two main applications:
Historically, EPIC has evolved in the context of the algebraic specification language ASF+SDF [2];
It must be said from the start, however, that EPIC has little to offer as a programming language. Suitability as a programming language is at odds with suitability as a target language.
EPIC's syntax is intentionally abstract: when used as a target language, generating the abstract syntax directly (as a data structure or in a textual representation aimed at machine readability) avoids producing and parsing human readable text. A concrete syntax for the use of EPIC as a system programming language is provided, but doesn't offer many of the features commonly available in programming languages. The EPIC tool set - a collection of software for the support of EPIC, including the compiler and run-time system, - uses a front-end written in, and accepting this concrete syntax, and producing EPIC's abstract syntax.
EPIC's type-system is liberal: it is single-sorted, requiring only the usual restrictions for TRSs (the left-hand side of a rule is not a sole variable, and is linear; all functions have a fixed arity; and every variable in the right-hand side of a rule must also occur in the left-hand side of that rule), and one restriction concerning modules (free and external functions may not become defined).
The simplicity of EPIC's type-system makes EPIC a suitable target for many different source languages. Type correctness is established at source level, and need not be checked again; and the translation to EPIC isn't complicated by a complex target structure.
EPIC features (left-linear) rewrite rules with syntactic specificity ordering [7] (a simplified version of specificity ordering [1]). It supports external data types and separate compilation of modules.
An EPIC module consists of a signature and a set of rules. The signature declares functions, each with an arity (number of arguments). In addition, functions can be declared external (i.e., defined in another module, or directly in C), or free (i.e., not defined in any module).
Rules are ordered by a syntactic specificity ordering: a more specific rule has higher precedence than a more general rule.
The EPIC tool set includes the following tools:
In addition several stand-alone tools exist:
EPIC is available via www at Babelfish.
The development of EPIC and its supporting tools is fueled by our conviction that term rewriting isn't less efficient, intrinsically, than any other implementation mechanism.
Accordingly, all tools relating to EPIC are themselves TRSs written in EPIC; the single exception is the run-time system, which is the abstract rewriting machine uArmdiscussed in Section 5.
All tools in the EPIC tool set are based on a simple design principle: they consume and produce text. They are usually composed of four parts: a parser, which interprets the input text and builds the term it represents; the essential computation performed by the tool; a (pretty) printer which produces a text given the term resulting from the computation; and a `top module' which glues the three together. Obviously intermediate printing and parsing is avoided when tools are combined. The graph exchange language GEL [4] can be used to store or pass on, in a very compact form approaching one byte per node, terms, dags and graphs, where sharing should be preserved.
uArmis an efficient abstract machine for hybrid term rewriting, which allows for an incremental style of software development and supports the transparent combination of compiled (stable) code with interpreted code still earlier in the software development cycle.
uArmsupports external functions and data types, and uArm's dispatcher uses a combination of directly and indirectly threaded code to achieve an efficient, transparent interface between different types of functions.
uArmhas efficient memory management, where garbage collection takes up less than 5% of the overall execution time. In addition, uArm uses a space-efficient innermost reduction strategy, whilst allowing for lazy rewriting when this is desired (as described in [6]).
Finally, uArmis parameterized with a small number of C macro's which can be defined either for portable ANSI C, or for a machine specific variant which performs two to three times better. In this manner ports for SUN SPARC, SGI R5000, and Macintosh (680xx) have been defined.
A precursor of uArmis described in [5]; a successor in [7].
We have investigated several fundamental extensions to innermost term rewriting which are deemed desirable for practical application of EPIC.
EPIC was designed specifically with efficiency in mind, where a balance was struck between compilation speed and execution speed. In lieu of the former, an interpreter is used for the intermediate (abstract machine) level; this interpreter has been optimized and fine-tuned to achieve acceptable execution speeds.
In [3] a compute-bound benchmark comparing implementations of functional languages is reported on in which uArmpresented itself as the most efficient interpreted system. Since the benchmark relies heavily on floating point computations, with little control-flow overhead, it favors compiling implementations, which fare better in that benchmark.
The (portable; non machine-specific) uArminterpreter performs 350000 simple reductions per second (of the form f(x) -> x ) on a SUN SPARC. On the same platform, the Larch Prover (LP 3.1a) performs 488 reductions per second, on the identical example. This is not mentioned as a comment on LP, but rather to provide a basis for comparison with other platforms.