Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Several alternatives for implementing abstract data types exist. One approach is the definition and implementation of a new language which directly supports abstract data type constructs. Another approach is to incorporate abstract data type constructs in an existing programming language. This paper describes recent and current research in the incorporation of a specification language for abstract data types within an operational compilable programming language. The synthesis of implementations of abstract data types from their specifications is discussed.

REFERENCES

• Aho77: Aho, A.V., Ullman, J.D. of Compiler Desiun, Addison-Wesley Publishing Company, Reading, Massachusetts (1977).
• Bar77: David Robbins Barstow, Automatic construction of algorithms and data structures using a knowledge base of programming rules., 1978
• Bel81: Boumediene Belkhouche, Automatic synthesis of abstract data type implementations from abstract specifications, 1983
• Ber79: Valdis Andris Berzins, Abstract model specifications for data abstractions, 1979
• Bie76: Biermann, A.W. "Approaches to Automatic Programming," In in Computers, VOl. 15, M. Rubinoff and M.C. Yovits (Editors), Academic Press, New YOrK (1976), pp 1-63.
• Cha71: Cnamberlin, D.D. "The 'Single-assignment' Approach to Parallel Processing," Proc. AFIPS 1971 FJCC, (November 1971), pp 263-269.
• Dew79: Robert K. Dewar , Arthur and Ssu-Cheng Liu and Jacob T. Schwartz and Edmond Schonberg, Programming by Refinement, as Exemplified by the SETL Representation Sublanguage, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.27-49, July 1979 [doi>10.1145/357062.357064]
• Ear76: Earley, J. "High Level Iterators and a Method for Automatically Designing Data Structure Representation," Journal of Computer Languages, Vol. I (1976), pp 321L342.
• Fon79: Amelia C. Fong, Inductively computable constructs in very high level languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567755]
• Gog79: Goguen, J.A. and Tardo, J.J. "An Introduction to OSJ: A Language For Writing and Testing Formal AlgeDraic Program Specifications," Proceedings of a Conference on Specifications of Reliable software, IEEE Computer Society (April 1979), pp 170-189.
• Gut78: Guttag, J.V., Horning, J.J. "The Algebraic Specifications of Abstract Data Types," Acta Informatica, 10,1 (1978), pp 27-52.
• Hoa72: Hoare, C.A.R. "Notes on Data Structuring," In Structured Programming. O. -J, E.W. Dijkstra, and C.A.R. Boare, Academic Pres, New YOrk (1972), pp 83-174
• Ich79: 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 [doi>10.1145/956653.956654]
• Jon76: Robert T. Johnson , James B. Morris, Abstract data types in the Model programming language, Proceedings of the 1976 conference on Data : Abstraction, definition and structure, p.36-46, March 22-24, 1976, Salt Lake City, Utah, United States
• Kan79: Elaine Kant, Efficiency considerations in program synthesis: a knowledge-based approach., 1979
• Lis75: Barbara Liskov , Stephen Zilles, Specification techniques for data abstractions, Proceedings of the international conference on Reliable software, p.72-87, April 21-23, 1975, Los Angeles, California
• Lis77: Liskov, B., Snyder, A., Atkinson, R., Scnaffert, C. "Abstraction Mecnanism in CLU," Computation Structures Group Memo 144-1, MIT (January 1977).
• Low78: James R. Low, Automatic data structure selection: an example and overview, Communications of the ACM, v.21 n.5, p.376-385, May 1978 [doi>10.1145/359488.359498]
• Man80: Zohar Manna , Richard Waldinger, A Deductive Approach to Program Synthesis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.90-121, Jan. 1980 [doi>10.1145/357084.357090]
• Moi82: Moitra, A. "Direct Implementations of Algeoraic Specification of Abstract Data Types," IEEE Transcations on Software Engineering SE-8 (I), (January 1982), pp 12-20.
• Pag79: Page, R. Formal Differentiation, Courant Institute of Mathematical Sciences, Computer Science Report NSO-15 (September 1979).
• Sch81: Edmond Schonberg , Jacob T. Schwartz , Micha Sharir, An Automatic Technique for Selection of Data Representations in SETL Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.126-143, April 1981 [doi>10.1145/357133.357135]
• Sco76: Scott, D. "Data Types as Lattices," SIAM Journal of Computing 5,3 (September 1976), pp 522-587.
• Sri80: Srivas, M.K. PhD Proposal, MIT Laooratory for Computer Science (1980).
• Sta78: Standish, T.A. "Data Structures- An Axiomatic Approacn," Chapter 4, Current Trends in Programming Metheodology, Vol. 4, Da~a Structuring, R.T. Yen (Editor), Prentice-Hall, New Jersey (1978), pp 30-59.
• Sub79a: Pasupathi Ananta Subrahmanyam, Towards a theory of program synthesis: automating implementations of abstract data types, 1979
• Wul76: Wulf, W.A., London, R.L. and Shaw, M. "An Introduction to the Construction and Verification of Alphard Programs," IEEE Transcations on Software Engineering SE-2 (4), (December 1976), pp 253-265.
• Zil81: Stephen N. Zilles, Introduction to Data Algebra, Proceedings of the Abstract Software Specifications, 1979 Copenhagen Winter School, p.248-272, January 22-February 02, 1979

INDEX TERMS

Keywords:
abstract data types, specifications, synthesis