Transformational program development in a particular problem domain (Q1081295)

Transformational programming is a methodology which supports the process of constructing a program that meets a given specification. Starting with a formal problem definition, an algorithm to solve the problem is derived (formally) by applying correctness-preserving transformation rules in a step-by-step fashion. In this way, the resulting program is not only guaranteed (by construction) to meet its specification, but also will satisfy further constraints depending on an appropriate choice of rules. For the practical use of transformational program development, a suitable set of rules plays a crucial role. In the past neither the 'catalog approach' (i.e. huge sets of compact, all-purpose rules) nor the 'generative set approach' (i.e. a small, relatively complete set of basic rules out of which further rules can be deduced) have turned out to be really practicable. Therefore, it seems to be an obvious compromise to base on a small set of powerful basic rules and to derive compact rules for particular classes of problems. The paper investigates the feasibility of this compromise, i.e. given a particular problem domain, to find out methodological principles (rules, tactics, strategies) that are needed to derive algorithms typical for the respectivel domain. According to its basic intention, the paper consists of two main parts. The first part deals with compact rules and strategies for the development of algorithms in connection with arbitrary deduction systems. The focus of interest here is the transition from a given descriptive (i.e. non-operational) specification to an operational solution. The techniques investigated comprise embedding (i.e. generalization) of specifications, a general strategy for deriving initial recursive solutions from descriptive specifications (following the known 'unfold/fold strategy'), a strategy for deriving algorithms that compute partial functions from solutions for the restricting predicate, compact rules for finite sets (e.g. for computing closures) which are one of the central data structures in the chosen problem domain, elimination of existential quantifiers and manipulations of applicative programs (inversion, combination, and composition) in order to increase efficiency. In the second part these techniques are applied to typical problems from the area of context-free grammars (as typical representative of the chosen problem domain) such as recognition and parsing (including not only a variety of parsing strategies, but also different representations of the parsing structure), and manipulation of grammars (e.g. elimination of empty productions and left recursion, or construction of parser tables).