Several authors have investigatedthe correspondence between graph rewriting and term rewriting.Almost invariably they have considered only acyclic graphs.Yet cyclic graphs naturally arise from certain optimizations in implementing functional languages.They correspond to infinite terms, and their reductions correspond to transfinite term-reduction sequences, which have recently received detailed attention.We formalize the close correspondence between finitary cyclic graph rewriting and a restricted form of infinitary term rewriting, called rational term rewriting.This subsumes the known relation between finitary acyclic graph rewriting and finitary term rewriting.Surprisingly, the correspondence breaks down for general infinitary rewriting.We present an example showing that infinitary term rewriting is strictly more powerful than infinitary graph .

A simple calculus (the Director String Calculus-DSC) for expressing abstractions is introduced, which captures the essence of the “long reach” combinators introduced by Turner. We present abstraction rules that preserve the applicative structure of the original lambda term, and that cannot increase the number of subterms in the translation. A translated lambda term can be reduced according to the evaluation rules of DSC. If this terminates with a DSC normal form, this can be translated into a lambda term using rules presented below. We call this process of abstracting a lambda term, reducing to normal form in the space of DSC terms, and translating back to a lambda term an implementation . We show that our implementation of the lambda calculus is correct: For lambda terms with a normal form that contains no lambdas ( ground terms ), the implementation is shown to yield a lambda calculus normal form. For lambda terms whose normal forms represent functions, it is shown that the implementation yields lambda terms that are beta-convertible in zero or more steps to the normal form of the original lambda term. In this sense, our implementation involves weak reduction according to Hindley et al. [9].

The “referential transparency” principle of applicative language expressions stipulates that a single value exists for all occurrences of an expression in a given context (where a context is a set of bindings of variables to values). In principle, each such value therefore need to be computed only once. However, in applicative language systems supporting recursive programming or tasking notions, the bindings are not all precomputed and explicit. As a result, textual recognition of all multipleoccurrences is precluded, with the unfortunate consequence that such occurrences are recomputed. We elaborate upon the early notion of “memo function” for solving this problem. We suggest syntactic and semantic constructs providing programmer control for avoiding recomputation, which is incorporated into a “building-block” approach.

The empirical testing of error repair schemes for skeletons of source programs in a block-structured language leads to the problem of generating balanced parenthesis strings in a uniform random manner. An efficient generator which works from left to right must compute the correct probability for the next symbol at each stage of the generation. The associated enumeration problem may be solved by adopting a geometric interpretation usually associated with random walk problems. This solution leads immediately to an O ( n ) algorithm for the generator.