|
 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
|
|
| |
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
|
|
| |
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
|
|
| |
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
|
|
| |
15
|
|
| |
16
|
|
| |
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
|
|
| |
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
|
|
| |
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.
|
CITED BY 93
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F. Hawrusik , K. N. Venkataraman , A. Yasuhara, Classes of functions for computing on binary trees (Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.19-27, May 11-13, 1981, Milwaukee, Wisconsin, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alan Demers , James Donahue , Glenn Skinner, Data types as values: polymorphism, type-checking, encapsulation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.23-30, January 23-25, 1978, Tucson, Arizona
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Gannon , Paul McMullin , Richard Hamlet, Data Abstraction, Implementation, Specification, and Testing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.3, p.211-223, July 1981
|
|
|
|
|
|
|
|
|
|
|
|
D. Tsichritzis , E. Fiume , S. Gibbs , O. Nierstrasz, KNOs: KNowledge acquisition, dissemination, and manipulation Objects, ACM Transactions on Information Systems (TOIS), v.5 n.1, p.96-112, Jan. 1987
|
|
|
|
|
|
D. Kapur , D. R. Musser , A. A. Stepanov, Operators and algebraic structures, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.59-64, October 18-22, 1981, Portsmouth, New Hampshire, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Roong-Ko Doong , Phyllis G. Frankl, Case studies on testing object-oriented programs, Proceedings of the symposium on Testing, analysis, and verification, p.165-177, October 08-10, 1991, Victoria, British Columbia, Canada
|
|
|
Robert Palumbo , Hossein Saiedian , Mansour Zand, The operational semantics of an active message system, Proceedings of the 1992 ACM annual conference on Communications, p.367-375, March 03-05, 1992, Kansas City, Missouri, United States
|
|
|
|
|
|
|
|
|
Ted J. Biggerstaff , D. Mack Endres , Ira R. Forman, Table: Object oriented editing of complex structures, Proceedings of the 7th international conference on Software engineering, p.334-345, March 26-29, 1984, Orlando, Florida, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Guttag , James Horning , John Williams, FP with data abstraction and strong typing, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.11-24, October 18-22, 1981, Portsmouth, New Hampshire, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P. Asirelli , P. Degano , G. Levi , A. Martèlli , U. Montanari , G. Pacini , F. Sirovich , F. Turini, A flexible environment for program development based on a symbolic interpreter, Proceedings of the 4th international conference on Software engineering, p.251-263, September 17-19, 1979, Munich, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thomas E. Cheatham, Jr. , Judy A. Townley , Glenn H. Holloway, A system for program refinement, Proceedings of the 4th international conference on Software engineering, p.53-62, September 17-19, 1979, Munich, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jean D. Ichbiah , Bernd Krieg-Brueckner , Brian A. Wichmann , John G. P. Barnes , Olivier Roubine , Jean-Claude Heliard, Rationale for the design of the Ada programming language, ACM SIGPLAN Notices, v.14 n.6b, p.1-261, June 1979
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Peer to Peer - Readers of this Article have also read:
-
Data structures for quadtree approximation and compression
Communications of the ACM
28, 9
Hanan Samet
-
A hierarchical single-key-lock access control using the Chinese remainder theorem
Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee
, Huizhu Lu
, D. D. Fisher
-
The GemStone object database management system
Communications of the ACM
34, 10
Paul Butterworth
, Allen Otis
, Jacob Stein
-
Putting innovation to work: adoption strategies for multimedia communication systems
Communications of the ACM
34, 12
Ellen Francik
, Susan Ehrlich Rudman
, Donna Cooper
, Stephen Levine
-
An intelligent component database for behavioral synthesis
Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen
, Daniel D. Gajski
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf