Structured data structures

ABSTRACT

Programming systems which permit arbitrary linked list structures enable the user to create complicated structures without sufficient protection. Deletions can result in unreachable data elements, and there is no guarantee that additions will be performed properly. To remedy this situation, this paper proposes a Data Structure Description and Manipulation Language which provides for the creation of a restricted class of data structures but ensures the correctness of the program. This is accomplished by an explicit structure declaration facility, a restriction on the permissible operations, and execution-time checks.

REFERENCES

• 1: CODASYL--Data Base Task Group Report. Available from ACM, New York, (Apr. 1971)
• 2: Edsger W. Dijkstra, Letters to the editor: go to statement considered harmful, Communications of the ACM, v.11 n.3, p.147-148, March 1968 [doi>10.1145/362929.362947]
• 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: Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 5: Integrated Data Store. Honeywell Information Systems, Inc., Wellesly, Mass., 1971.
• 6: Kieburtz, R. Steps towards verifiable programs. Tech. Rep 12, Dep. Comput. Sci., SUNY at Stony Brook, N.Y.
• 7: Mills, H. Top down programming in large systems. From Debugging Techniques in Large Systems. Gourant Computer Science Symposium, pp. 41-53.
• 8: Terrence W. Pratt , Daniel P. Friedman, A language extension for graph processing and its formal semantics, Communications of the ACM, v.14 n.7, p.460-467, July 1971 [doi>10.1145/362619.362627]
• 9: S. Crespi-Reghizzi , R. Morpurgo, A language for treating graphs, Communications of the ACM, v.13 n.5, p.319-323, May 1970 [doi>10.1145/362349.362366]
• 10: Rosenberg, A. Data graphs and addressing schemes. J. Comput. and Syst. Sci. 5 (1971), 193-223.
• 11: Rosenberg, A. Exploiting addressability in data graphs. Rep. RC-3618 IBM, T.J. Watson Res. Cent., 1971.
• 12: Rosenberg, A. Symmetries in data graphs. SIAM J. Comput. 1, (1972), 40-65.
• 13: Senko, M.E., Altman, E.B., Astrahan, M.M., and Fehder, P.L. Data structures and accessing in data-base systems. IBM Syst. J. 12, 1 (1973).
• 14: Ben Abraham Shneiderman, Data structures: description, manipulation and evaluation, 1973
• 15: Niklaus Wirth, Program development by stepwise refinement, Communications of the ACM, v.14 n.4, p.221-227, April 1971 [doi>10.1145/362575.362577]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Languages, Management, Reliability

Keywords:
data base management system, data structures, structured programming