Abstract data types and the development of data structures

ABSTRACT

Abstract data types can play a significant role in the development of software that is reliable, efficient, and flexible. This paper presents and discusses the application of an algebraic technique for the specification of abstract data types. Among the examples presented is a top-down development of a symbol table for a block structured language; a discussion of the proof of its correctness is given. The paper also contains a brief discussion of the problems involved in constructing algebraic specifications that are both consistent and complete.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Batey, M., Ed. Working Draft of ECMA/ANSI PL/I Standard Tenth Rev., ANSI, New York, (Sept. 1973).
	2	Birkhoff, G., and Lipson, J.D. Heterogeneous algebras. J. Combinatorial Theory 8 (1970), 115-133.
	3	Ole-Johan Dahl, SIMULA 67 common base language, (Norwegian Computing Center. Publication), 1968
	4	Dijkstra, E.W. Notes on structured programming. In Structured Programming, Academic Press, New York, 1972.
	5	Floyd, R.W. Assigning Meaning to Programs. Proc. Symp. in Applied Math., Vol. XIX, AMS, Providence, R.I., 1967, pp. 19-32.
	6	John Dennis Gannon, Jr., Language design to enhance programming reliability., 1975
	7	Good, D.I., London, R.L., and Bledsoe, W.W. An interactive program verification system. IEEE Trans. on Software Engineering SE-1, 1 (March 1975), 59-67.
	8	John Vogel Guttag, The specification and application to programming of abstract data types., 1975
	9	Guttag, J.V. and Horning, J.J., The algebraic specifications of abstract data types. Acta Informatica (to appear).
	10	Guttag, J.V., Horowitz, E., and Musser, D.R. Abstract data types and software validation. Tech. Rep., Inform. Sci. Inst., U. of Southern California, Los Angeles, 1976.
	11	John V. Guttag , Ellis Horowitz , David R. Musser, The design of data type specifications, Proceedings of the 2nd international conference on Software engineering, p.414-420, October 13-15, 1976, San Francisco, California, United States
	12	Hoare, C.A.R., Proof of correctness of data representations. Acta Informatica 1 (1972), 271-281.
	13	Hoare, C.A.R., and Wirth, N. An axiomatic definition of the programming language PASCAL. Acta lnformatica 2 (1973), 335- 355.
	14	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
	15	William M. McKeeman, Symbol Table Access, Compiler Construction, An Advanced Course, 2nd ed., p.253-301, January 1976
	16	James B. Morris, Programming by semantic refinement, Proceeding of ACM SIGPLAN - SIGOPS interface meeting on Programming languages - operating systems, p.120-122, January 1973
	17	Musser, D. Private communication, 1975.
	18	Palme, J. Protected program modules in SIMULA 67. FOAP Rep. C8372-M3(E5), Res. Inst. of National Defense, Stockholm, 1973.
	19	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]
	20	Parnas, D.L. Information distribution aspects of design methodology. Information Processing 71, North Holland Pub. Co., Amsterdam, 1971, pp. 339-344.
	21	Spitzen, J., and Wegbreit, B. The verification and synthesis of data structures. Acta Informatica 4 (1975), 127-144.
	22	Standish, T.A. Data structures: An axiomatic approach. BBN Rep. No. 2639, Bolt, Beranek and Newman, Cambridge, Mass., (1973).
	23	Ben Wegbreit , Jay M. Spitzen, Proving Properties of Complex Data Structures, Journal of the ACM (JACM), v.23 n.2, p.389-396, April 1976 [doi>10.1145/321941.321957]
	24	Wulf, W.A., London, R.L., and Shaw, M. Abstraction and verification in Alphard: Introduction to language and methodology. USC Inform. Sci. Tech. Rep., U. of Southern California, Los Angeles, 1976.
	25	Zilles, S.N. Abstract specifications for data types. IBM Res. Lab. San Jose, Calif., 1975.