Abstract
Abstract data types provide a powerful tool for the representation independent specification of data structures. This paper applies theoretical results to a simple example and demonstrates how to work with this algebraic specification technique: Polynomials are defined by a hierarchical type. For this specification the class of all models is analyzed and properties of initial and terminal models are discussed.
A normal form serves as the basis for data type developments leading to a specification of polynomials with efficient sequential or parallel evaluation. Then relations between the derived types are studied and their implementation is discussed. Finally additional operations are added by a data type extension.
Throughout the paper program transformation, methods like embedding, recursion introduction and recursion elimination are used.
This research was supported in part by the Sonderforschungsbereich 49 –Programmiertechnik, Munich.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
J.A. Goguen, J.W. Thatcher, E.G. Wagner: An initial algebra approach to the specification, correctness and implementation of abstract data types. In: R.T. Yeh (ed.): Current Trends in Programming Methodology, Vol. 3, Data Structuring, N.J.: Prentice Hall, 1978
J.W. Thatcher, E.G. Wagner, J.B. Wright: Data type specification: Parameterization and the power of specification techniques. Proc. SIGACT 10th Annual Symposium on the Theory of Computing, 1978
G. Ausiello, G.F. Mascari: On the design of algebraic data structures with the approach of abstract data types. In: E.W. Ng (ed.): Symbolic and Algebraic Computation, LNCS 72, 515–530 (1979)
F.L. Bauer: Einführung in die Informatik I. Vorlesungsskriptum, Technische Universität München (1980)
F.L. Bauer, H. Wössner: Algorithmic language and program development. Berlin-Heidelberg-New York: Springer-Verlag. To appear
J.A. Bergstra, J.V. Tucker: Algebraic specifications of computable and semicomputable data structures. Afdeling Informatice Amsterdam, IW 115/79
J.A. Bergstra, J.V. Tucker: A natural data type with a finite equational final semantics specification but no effective equational initial semantics specification. To appear
A. Bertoni, G. Mauri, P.A. Miglioli, M. Wirsing: On different approaches to abstract data types and the existence of recursive models. Bulletin of EATCS 9, 47–57 (1979)
M. Broy: Transformation parallel ablaufender Programme. Dissertation, Technische Universität München, Fakultät für Mathematik (1980)
M. Broy, W. Dosch, H. Partsch, P. Pepper, M. Wirsing: Existential quantifiers in abstract data types. In: H.A. Maurer (ed.): Proc. 6th ICALP, Graz, LNCS 71 73–87 (1979)
M. Broy, R. Gnatz, M. Wirsing: Problemspezifikation — eine Grundlage für Programmentwicklung. Workshop on Reliable Software, Bonn University, Sept. 22–23, 1978. Hanser Verlag (1979)
M. Broy, M. Wirsing: Programming languages as abstract data types. Proc. 5th Colloquium on “Arbres en Algèbre et en Programmation”, Lille 1980
R.M. Burstall, J.A. Goguen: Putting theories together to make specifications. Proc. of the Fifth Int. Joint Conf. on Artificial Intelligence, MIT, Cambridge, Mass., 1045–1058 (1977)
H.D. Enrich: On the theory of specification, implementation and parameterization of abstract data types. To appear
H. Ehrig, H.J. Kreowski, P. Padawitz: Stepwise specification and implementation of abstract data types. Proc. 5th ICALP, Udine, LNCS 62, 205–226 (1978)
M.C. Gaudel: Spécifications incomplètes mais suffisantes de la représentation des types abstraits. IRIA Rapport de Recherche No. 320 (1978)
V. Giarratana, F. Gimona, U. Montanari: Observability concepts in abstract data type specification. Proc. of the 5th MFCS Symposium. LNCS 45, 576–587 (1976)
J.V. Guttag: The specification and application to programming of abstract data types. Ph. D. Thesis, Univ. of Toronto, Dept. of Comp. Science, Rep. CSRG-59 (1975)
J.V. Guttag, E. Horowitz, D.R. Musser: The design of data specifications. USC/Information Sciences Institute, RR-76–49 (1976)
D.E. Knuth: The art of computer programming., Vol. 1,2. Reading Mass.: Addison-Wesley (1971, 1975)
D. Knuth, P. Bendix: Simple word problems in universal algebras. In: J. Leech Ced.): Computational Problems in Abstract Algebra. Pergamon Press 1970
Etude algébrique et relationnelle des types abstraits et de leurs représentations. Thèse de Doctorat, Université de Nancy 1979
M. Majster: Data types, abstract data types and their specification problem. TCS 8, 89–127 (1979)
M. Wand: Final algebra semantics and data type extensions. Indiana University, Comp. Science Department, Technical Report No. 65 (1978)
M. Wirsing, M. Broy: Abstract data types as lattices of finitely generated models. To appear in the Proc. 9th MFCS, Rydzyna, Poland (1980)
M. Wirsing, P. Pepper, H. Partsch, W. Dosch, M. Broy: On hierarchies of abstract data types. Technische Universität München, Institut für Informatik, TUM 18007 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1980 Springer-Verlag Berlin · Heidelberg
About this paper
Cite this paper
Dosch, W., Wirsing, M., Ausiello, G., Mascari, G.F. (1980). Polynomials — The Specification, Analysis and Development of an Abstract Data Type. In: Wilhelm, R. (eds) GI - 10. Jahrestagung. Informatik-Fachberichte, vol 33. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-67838-7_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-67838-7_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-10388-2
Online ISBN: 978-3-642-67838-7
eBook Packages: Springer Book Archive