Paddle(ID:1003/pad001)Transformation languageLanguage for transformations leading from specification to program. Used in POPART, a grammar-driven programming environment generator. Based on, and an extension to, GIST Related languages
References: Formal Development Structure We recorded the sequence of transformation applications to provide a derivation history. To examine this history, it was natural to use the Popart editor. This necessitated building a grammar for this structure, which in turn forced us to consider the language for expressing such structures. This led to the observation that rather than representing the derivation history directly, we should describe how to generate that history, i.e., a program for transformational derivation (called a formal development). The resulting language, Paddle, enabled us to operationally specify the structure of the sequence of transformations needed to implement some system. That specification could be executed to obtain the implementation. However, we could also use the Popart editor to modify the formal development and then reexecute it. Paddle's contribution lies in the combination of these two capabilities. It formally represented a structured transformational derivation, and the fact that this representation was generative provided us with the insight that such derivations should be iteratively and incrementally developed. In fact, it is also the basis for our approach to maintenance. As we described previously, we believe that maintenance should be performed by modifying the specification and rederiving the implementation. This. strategy is ideal when the implementation is fully automatic because the modified specification then only needs to be "recompiled. " in IEEE Transactions on Software Engineering, November 1985 view details Introduction In a previous issue of this Transactions, Balzer prelsented the transformational implementation (TI) model of software development. Since that article appeared, several research efforts have been undertaken to make TI a more useful tool. This paper reports on one such effort. A general model of software transformation can be summarized as follows: 1) we start with a formal specification P (how we arrive at such a specification is a separate research topic), 2) an agent S applies a transformation T to P to produce a new P. 3) step 2 is repeated until a version of P is produced that meets implementation conditions (e.g., it is compilable, it is efficient) [...] In the TI model, the specification language P is Gist, the agent S is an expert human developer, and T is taken from a catalog of correctness-preserving transformations2 (Section II discusses other bindings of P. S. and T ). Hence, the human is responsible for deciding what should be transformed next, and what transformation to use; the system checks the transformation's preconditions and applies it to produce a new state. As Balzer noted [...] , the TI model provides at least two advantages. 1) Focus is shifted away from consistency problems and towards design tradeoffs. 2) The process of developing a program is formalized as a set of transformations. Thus, the process itself can be viewed as an objecct of study. Since Balzer's article appeared, we have attempted to use the TI model on several realistic problems. This work has confirmed one of the article's conjectures: ". . . it is evident that the developer has not been freed to consider design tradeoffs. Instead of a concern for maintaining consistency, the equally consuming task of directing the low level development has been imposed. While the correctness of the program is no longer an issue, keeping track of where one is in a development and how to accomplish each step in all its fine detail diverts attention from tradeoff questions. It is quite clear that if transformation systems are to become useful, this difficulty must be removed. " One solution is to automate portions of a TI development,3 that is, find a way for the machine to automatically find and apply a portion of the transformations. This paper reports on our efforts to bring about this solution. In particular, we discuss the Glitter system, which uses problem-solving techniques to generate many of the steps of a development automatically. Glitter is a working system implemented in the expert system writing language Hearsay III [ 5 ] . We will present Glitter through an example in Section IV. Section V contains another, more lengthy example of a Glitter development. Extract: A closer look at the problem A closer look at the problem Glitter traces its roots to prior efforts in the area of transformational development. To produce a working transformational system, several portions of the abstract model in Fig. 1 must be further specified. First, the form of the initial P determines both the level of specification and the form the transformations will take. If our goal is to specify only what the problem is, as opposed to how to solve it, we want the initial P to be a high-level specification. On the other hand, if we are interested in applying efficiency tricks in a production language like Pascal, our initial P may be low- level, e.g., Pascal itself. The variety of specification levels possible is shown by a set of illustrative transformation systems. The TI model uses a high-level specification language called Gist as the initial starting point. The designers of Gist have set as a goal freeing the specification writer from any implementation concerns. Thus, both data and control representations are defined to allow, through skillful and careful construction, implementation- independent specifications. The form of transformations range from ones that deal with the most abstract design decisions, to ones that involve the nitty-gritty optimization of operations and data structures. The PSI system (in particular the PECOS/LIBRA component) starts with an abstract algorithm defined as a program model. In a program model, data remains at an abstract level, while control is more concrete. The form of transformations (called refinements) in PECOS ranges from intermediate to low-level design decisions. The Irvine transformational system starts with a program written in a Pascal-like language, Transforma. Here, and throughout the paper, we will use Tl development to mean the mapping of a specification into an implementation using transformations. Translations are source-to-source, and tend to involve optimization of expression evaluation, although some control optimizations are included. There are conflicting concerns in choosing the initial level of specification. The lower we start, the better are the chances of building a complete set of transformations: our software design knowledge at the lower levels is better studied. However, the higher we start, the better are the chances of bringing about real efficiency gains: it is often the high-level design decisions that most affect the final space and time taken by the implementation. Unfortunately, at the higher levels our design knowledge is less formal and not well charted. The result of this conflict is that systems that attempt to use a completely automatic model of transformation selection and application have necessarily been forced to use an initial specification that is either below the desired level, or at the right level but not expressive enough to handle realistic problems. More recent work has attempted to handle high-level specifications by involving the user in the transformation process. This is the first key idea on which Glitter builds: an interactive system stands a chance of transforming realistic, high-level specifications into an efficient implementation. This brings us to our second decision point, namely the constitution of the agents S. In completely automatic systems such as PSI, S is a computer-based component that decides 1) what portion of P to work on, 2) what set of transformations are applicable, and 3) which transformation to apply from the set. Conversely, in the TI model, S is a human. The human is responsible for all of the above items except transformation application, which is handled by the system. Other systems such as ZAP, CHI, Draco, and Glitter attempt to strike a better balance by automating more extensive portions of transformation selection and application, and leaving smaller portions to the human. The second key idea used in Glitter is then that interactive transformation systems can still have a significant degree of automation. Finally, there are various ways to control the search for the "right" set of transformations. The PSI system uses a modified best-first search. Systems such as PDS and the Irvine transformation system employ a formal production system approach which applies all transformations until none are applicable (this type of control is often found in rewrite systems where Church-Rosser properties hold). The PADDLE system allows backtracking to a decision point. In particular, PADDLE records the set of transformations used, and allows the user to replay or reurn them to an arbitrary point. Hence, if the user wishes to try an alternative to the kth transformation applied, he or she may request PADDLE to replay k -- 1 transformations. Thus, PADDLE treats a sequence of transformation selections and applications as a program. Parts or all of it can be deleted, modified, or executed. This leads to the third key idea used by Glitter: the process of selecting and applying transformations can be viewed as a product as well. Glitter declaratively stores all of the information it is able to capture during the transformation process. This can be used to aid in maintenance. To summarize, Glitter is built on three key ideas. 1) An expert human user must be included in the transformation process if we wish to study realistic problems. 2) An interactive model can still include useful automation. 3) Given that a transformational development is no more static than a normal software development, we will need to make changes to it. Hence, the process itself becomes an object of study. The focus of our work is on the second idea. We set out to see how far we could push automation in the TI model. In doing so, we found ourselves concerned with the third idea as well. Specifically, once we began to study the transformation process, we noticed a curious thing: only a small part of the process was being captured by the machine. In particular, the selection and application of a program transformation was only the tip of the problem-solving iceberg. Watching expert human developers, it became clear that the sophisticated planning necessary to generate one or more transformations would also have to be represented. Our goals became first to formalize the problemsolving steps used to generate transformation applications, and then to build a problem-solving system around them. The formalization would include the goals, strategies, selection rationale, and finally the transformations used by expert human developers. The system would include representations for the formal types of knowledge, and machinery for handling human-system interaction and problem solving control. In the remainder of the paper, we discuss the degree to which we were able to meet our goals. in IEEE Transactions on Software Engineering, November 1985 view details |