zbMATH — the first resource for mathematics

Compatibility of parameter passing and implementation of parameterized data types. (English) Zbl 0553.68015
The basis for this paper are the concepts of parameterization and implementation of abstract data types which have been developed in the theory of algebraic specifications with initial algebra semantics. In this paper we combine both concepts defining implementations of parameterized data types and studying the compatibility of parameter passing and implementation of parameterized data types. In our main result we show that parameter passing commutes with implementation. This is an important step in order to apply the theory of algebraic specifications to development and stepwise refinement of software systems. We illustrate our notion and results by a small example implementing binary trees over arbitrary data by corresponding strings with brackets. Finally we consider the problem of 2-dimensional compatibility of parameter passing and implementation and discuss the kind of compatibility results which have been shown by other authors in the case of loose and final algebra semantics.

68P05 Data structures
Full Text: DOI
[1] Goguen, J.A.; Thatcher, J.W.; Wagner, E.G., An initial algebra approach to the specification correctness and implementation of abstract data types, (), 80-149, (1976)
[2] Thatcher, J.W.; Wagner, E.G.; Wright, J.B.; Thatcher, J.W.; Wagner, E.G.; Wright, J.B., Data type specification: parameterization and the power of specification techniques, Proc. SIGACT 10th ann. symp. on theory of computing, ACM toplas, 4, 4, 711-732, (1982) · Zbl 0495.68020
[3] Ehrig, H.; Kreowski, H.-J.; Thatcher, J.W.; Wagner, E.G.; Wright, J.B., Parameterized data types in algebraic specification languages (short version), Proc. 7th ICALP noordwijkerhout, Lncs, 88, 157-168, (1980), revised version, Theoret. Comput. Sci., to appear.
[4] Ehrig, H.; Kreowski, H.-J.; Thatcher, J.W.; Wagner, E.G.; Wright, J.B., Parameter passing in algebraic specification languages, (), Lncs, 134, 322-369, (1982)
[5] Ehrig, H.; Thatcher, J.W.; Wagner, E.G., Algebraic constraints for specifications and cannonical form results, (), Lncs, 954, (1983), short version. in: Proc. 10th ICALP, Barcelona · Zbl 0518.68019
[6] Broy, M.; Dosch, W.; Partsch, H.; Pepper, P.; Wirsing, M., Existential quantifiers in abstract data types, Proc. 6th ICALP, Graz; LNCS, 71, 73-87, (1979) · Zbl 0404.68026
[7] Burstall, R.M.; Goguen, J.A., CAT, a system for the structure elaboration of correct programs from structured specifications, (1979/1980), preliminary draft · Zbl 0456.68024
[8] Burstall, R.M.; Goguen, J.A., The semantics of CHAR, a specification language, Proc. 1979 Copenhagen winter school on abstract software specifications, Lncs, 86, 292-332, (1980) · Zbl 0456.68024
[9] Ehrich, H.-D., On the theory of specification, implementation and parameterization of abstract data types, Res. rept., Dortmund., J. ACM, 29, 1, 206-227, (1978) · Zbl 0478.68020
[10] Ehrig, H., Algebraic theory of parameterized specifications with requirements, Proc. 6th CAAP., Lncs, 112, 1-24, (1981) · Zbl 0465.68006
[11] Ehrig, H.; Fey, W., Methodology for the specification of software systems: from formal requirements to algebraic design specifications, München; informatik-facberichte, 50, 225-269, (1981), Proc. G^{1} 81
[12] Ehrig, H.; Fey, W.; Kreowski, H.-J., Some examples of algebraic specifications and implementations: part 1, (1980), Techn. Univ. Berlin, Rept. No. 80-31
[13] Ehrig, H.; Kreowski, H.-J., Parameter passing commutes with implementation of parameterized data types, (), Lncs, 140, 197-211, (1983) · Zbl 0553.68015
[14] Ehrig, H.; Kreowski, H.-J.; Padawitz, P., Stepwise specification and implementation of abstract data types, (), Lncs, 62, 205-226, (1978), Report
[15] Ehrig, H.; Kreowski, H.-J.; Padawitz, P., Algebraic implementation of abstract data types: concept, syntax, semantics, correctness, (), Lncs, 85, 142-156, (1980) · Zbl 0457.68019
[16] Ehrig, H.; Kreowski, H.-J.; Mahr, B.; Padawitz, P., Algebraic implementations of abstract data types, (), Theoret. comput. sci., 20, 209-264, (1982), Rept. No. 80-32 · Zbl 0483.68018
[17] Ehrig, H.; Kreowski, H.-J.; Weber, H., Algebraic specification schemes for data base systems, Proc. conf. very large data bases, 427-440, (1978), Berlin
[18] Floyd, Ch.; Kopetz, H., Software engineering—entwurf und spezifikation, ()
[19] Ganzinger, H., Parameterized specifications: parameter passing and implementation, with respect to observability, (), TOPLAS (submitted). · Zbl 0511.68010
[20] Gianotana, V.; Giomona, F.; Montanari, U., Observability concepts in abstract data type specification, Lncs, 45, 576-587, (1976), Proc. MFCS’76
[21] Goguen, J.; Meseguer, J., Universal realization, persistent interconnection and implementation of abstract modules, (), Lncs, 140, 265-281, (1983) · Zbl 0493.68014
[22] Guttag, J.V., Abstract data types and development of data structures, Sigplan, 8, (1976), supplement to Proc. Conf. on Data Abstraction, Definition, and Structure
[23] Herrlich, H.; Strecker, G., Category theory, (1973), Allyn and Bacon Rockleigh · Zbl 0265.18001
[24] Hupbach, U.L., Abstract implementation and parameter substitution, Proc. 3rd Hungarian comput. sci. conf., (1981), Budapest · Zbl 0499.68011
[25] Lipeck, U., Ein algebraischer kalkül für einen strukturierten software-entwurf, (), Draft version · Zbl 0519.68020
[26] Maclane, S., Categories for the working Mathematician, (1971), Springer New York-Heidelberg-Berlin
[27] Reichel, H., Initially restricting algebraic theories, (), Incs, 88, 505-515, (1980) · Zbl 0469.68026
[28] Sanella, D.; Wirsing, M., Implementation of parameterized specifications, (), Lncs, 140, 473-488, (1983)
[29] Wand, M., Final algebra semantics and data type extensions, Jcss, 19, 27-44, (1979) · Zbl 0418.68020
[30] Zilles, S., Algebraic specification of data types, MIT project MAC progress rep., XL, 52-58, (1974), Cambridge
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.