Abstract
A uniform treatment of algebraic specification is proposed to formalise data, programs, transformation rules, and program developments. It is shown by example that the development of an efficient transformation algorithm incorporating the effect of a set of transformation rules is analogous to program development: the transformation rules act as specifications for the transformation algorithms.
The research reported herein has been partially funded by the Commission of the European Communities under the ESPRIT Programme, Project #390, PROSPECTRA (PROgram development by SPECification and TRAnsformation)
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Wile, D.S.: Program Developments: Formal Explanations of Implementations. CACM 26: 11 (1983) 902–911. also in: Agresti, W. A. (ed.): New Paradigms for Software Development. IEEE Computer Society Press/North Holland (1986) 239–248.
Steinbrüggen, R..: Program Development using Transformational Expressions. Rep. TUM-I8206, Institut für Informatik, TU München, 1982.
Feijs, L.M.G., Jonkers, H.B.M, Obbink, J.H., Koymans, C.P.J., Renardel de Lavalette, G.R., Rodenburg, P.M.: A Survey of the Design Language Cold. in: Proc. ESPRIT Conf. 86 (Results and Achievements). North Holland (1987) 631–644.
Sintzoff, M.: Expressing Program Developments in a Design Calculus. in: Broy, M. (ed.): Logic of Programming and Calculi of Discrete Design. NATO ASI Series, Vol. F36, Springer (1987) 343–365.
Jähnichen, S., Hussain, F.A., Weber, M.: Program Development Using a Design Calculus. in: Rogers, M. W. (ed.): Results and Achievements, Proc. ESPRIT Conf. '86. North Holland (1987) 645–658.
Bauer, F.L., Berghammer, R., Broy, M., Dosch, W., Geiselbrechtinger, F., Gnatz, R., Hangel, E., Hesse, W., Krieg-Brückner, B., Laut, A., Matzner, T., Möller, B., Nickl, F., Partsch, H., Pepper, P., Samelson, K., Wirsing, M., Wössner, H.: The Munich Project CIP, Vol. 1: The Wide Spectrum Language CIP-L. LNCS 183, 1985.
Bauer, F. L., Wössner, H.: Algorithmic Language and Program Development. Springer 1982.
Pepper, P.: A Simple Calculus of Program Transformations (Inclusive of Induction). Science of Computer Programming 9:3 (1987) 221–262.
Krieg-Brückner, B., Hoffmann, B., Ganzinger, H., Broy, M., Wilhelm, R., Möncke, U., Weisgerber, B., McGettrick, AA.D., Campbell, I.G., Winterstein, G.: Program Development by Specification and Transformation. in: Rogers, M. W. (ed.): Results and Achievements, Proc. ESPRIT Conf. '86. North Holland (1987) 301–312.
Krieg.Brückner, B.: Integration of Program Construction and Verification: the PROSPECTRA Project. in: Habermann, N., Montanari, U. (eds.): Innovative Software Factories and Ada. Proc. CRAI Int'l Spring Conf. '86. LNCS 275 (1987) 173–194.
Broy, M., Wirsing, M.: Partial Abstract Types. Acta Informatica 18 (1982) 47–64.
Ganzinger, H.: A Completion Procedure for Conditional Equations. Techn. Bericht No. 243, Fachbereich Informatik, Universität Dortmund, 1987 (to appear in J. Symb. Comp.)
Hoare, C.A.R., Hayes, I.J., He, J.F., Morgan, C.C., Roscoe, A.W., Sanders, J.W., Sorensen, I.H., Spivey, J.M., Sufrin, B.A.: Laws of Programming. CACM 30: 8 (1987) 672–687.
Broy, M., Pepper, P., Wirsing, M.: On the Algebraic Definition of Programming Languages. ACM TOPLAS 9 (1987) 54–99.
Krieg-Brückner: Systematic Transformation of Interface Specifications. in: Meertens, L.G.T.L. (ed.): Program Specification and Transformation, Proc. IFIP TC2 Working Conf. (Tölz '86). North Holland (1987) 269–291
Heckmann, R.: A Functional Language for the Specification of Complex Tree Transformation. this volume.
Qian, Z.: Structured Contextual Rewriting. Proc. Int'l Conf. on Rewriting Techniques and Applications (Bordeaux). LNCS 256 (1987) 168–179.
Qian, Z.: Recursive Presentation of Program Transformation. PROSPECTRA Report M.1.1.S1-SN-17.1, Universität Bremen (1986).
Krieg-Brückner: Formalisation of Developments: An Algebraic Approach. in: Rogers, M. W. (ed.): Achievements and Impact. Proc. ESPRIT Conf. 87. North Holland (1987) 491–501.
Broy, M.: Predicative Specification for Functional Programs Describing Communicating Networks. IPL 25 (1987) 93–101.
Smith, D.R.: Top-Down Synthesis of Divide-and-Conquer Algorithms. Artificial Intelligence 27:1 (1985) 43–95.
Bird, R.S.: Transformational Programming and the Paragraph Problem. Science of Computer Programming 6 (1986) 159–189.
Broy, M.: Equational Specification of Partial Higher Order Algebras. in: Broy, M. (ed.): Logic of Programming and Calculi of Discrete Design. NATO ASI Series, Vol. F36, Springer (1987) 185–241.
Möller, B.: Algebraic Specification with Higher Order Operators. in: Meertens, L.G.T.L. (ed.): Program Specification and Transformation, Proc. IFIP TC2 Working Conf. (Tölz '86). North Holland (1987) 367–398.
von Henke, F.W.: An Algebraic Approach to Data Types, Program Verification and Program Synthesis. in: Mazurkiewicz, A. (ed.): Mathematical Foundations of Computer Science 1976. LNCS 45 (1976) 330–336.
Wile, D. S.: Organizing Programming Knowledge into Syntax Directed Experts. USC/ISI manuscript (1987).
Gordon, M., Milner, R., Wadsworth, Ch.: Edinburgh LCF: A Mechanised Logic of Computation. LNCS 78.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krieg-Brückner, B. (1988). Algebraic formalisation of program development by transformation. In: Ganzinger, H. (eds) ESOP '88. ESOP 1988. Lecture Notes in Computer Science, vol 300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-19027-9_3
Download citation
DOI: https://doi.org/10.1007/3-540-19027-9_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-19027-1
Online ISBN: 978-3-540-38941-5
eBook Packages: Springer Book Archive