Limits of the "algebraic" specification of abstract data types

ABSTRACT

This paper deals with the feasibility of the algebraic specification technique for abstract data types, which consists of a declaration of the operations of a data type and a finite set of "axioms" for the operations. We discuss some inherent difficulties arising from this technique and present a simple example of an abstract type for which the method cannot be applied.

REFERENCES

• 1: R. Bayer: Aggregates: A Software Design Method and its Application to a Family of Transitive Closure Algorithms. Report No. 7432, Technical University Munich, Germany, September 1974.
• 2: James H. Morris, Jr., Types are not sets, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.120-124, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512938]
• 3: Jay Earley, Toward an understanding of data structures, Communications of the ACM, v.14 n.10, p.617-627, Oct. 1971 [doi>10.1145/362759.362764]
• 4: C.A.R. Hoare: Proof of correctness of data representations. Acta Informatica, Vol. 1 (1972) p. 271--281.
• 5: J. Spitzen and B. Wegbreit: The verification and synthesis of data structures. Acta Informatica, Vol. 4 (1975), p. 127--144.
• 6: O.J. Dahl, B. Myhrhang and K. Nygaard: The SIMULA 67 Common base language. Publication S-22, Norwegian Computing Center, Oslo, 1970.
• 7: Barbara Liskov , Stephen Zilles, Programming with abstract data types, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.50-59, March 28-29, 1974, Santa Monica, California, United States
• 8: T.A. Standish: Data Structures: an Axiomatic Approach. BBN Report No. 2639, Bolt, Beranik and Newmann, Cambridge, Mass., 1973.
• 9: I.R. Shoenfield: Mathematical Logic. Reading, Mass. Addison-Wesley, 1967.
• 10: S.N. Zilles: Algebraic Specification of Data Types. Mass. Inst. of Technology, Cambridge, Project Mac Progress Report 11, to appear.
• 11: J.V. Guttag: The Specification and Application to Programming of Abstract Data Types. Technical Report CSR6-59, Computer Systems Research Group, University of Toronto, 1975.
• 12: J.A. Goguen, J.W. Thatcher, E.G. Wagner and J.B. Wright: Abstract data types as initial algebras and correctness of data representations. Proceedings of the Conference on Computer Graphics, Pattern Recognition and Data Structure, (May 1975).
• 13: M.E. Majster: Erweiterte gerichtete Graphen, ein Modell für Datenstrukturen und Datenstrukturklassen. Ph.D.-Thesis 1975, Technische Universität München, Germany.
• 14: A.L. Rosenberg: Data graphs and addressing schemes. Journal of Computer and System Sciences, 5 (1971) p. 193--238.
• 15: D. L. Parnas, A technique for software module specification with examples, Communications of the ACM, v.15 n.5, p.330-336, May 1972 [doi>10.1145/355602.361309]
• 16: B. Liskov and S.N. Zilles: Specification techniques for data abstractions. IEEE Transactions on Software Engineering, Vol. SE-1, No. 1 (March 1975) p. 8--18.
• 17: M.E. Majster: Extended directed graph, a formalism for structured data and data structures. Accepted for publication in Acta Informatica, to appear in January 1977.