Toward an understanding of data structures

Abstract

This paper presents a notation and formalism for describing the semantics of data structures. This is based on directed graphs with named edges and transformations on these graphs. In addition, and implementation facility is described which could be part of a programming language, which allows a programmer who has expressed the semantics of an algorithm in terms of the graphs to then specify the implementation of some of his data structures in order to gain efficiency.

References

1. 1 standish, T.A. A data definition facility for programming languages Ph.D. Th., Carnegie-Mellon U., 1967.
2. 2 Pratt, T.W. Semantic modeling by hierarchical graphs. U. of Texas, 1969.
3. 3 Holt, A.W. n-Theory, a mathematical method for the description and analysis of discrete finite information systems. Applied Data Research, Inc., 1965.
4. 4 Reynolds, J.C. Automatic computation of data set definitions. Proc. IFIP Congress 1968, Vol. 1, North Holland Pub. Co., Amsterdam, pp. 456-461.
5. 5 Reynolds, J.C. OEDANKEN-A simple typeless language which permits functional data structures and coroutines. Comm. ACM 13, 5 (May 1970), 308-319.
6. 6 Childs, D.C. Feasibility of a set-theoretic data structure. Proc. IFIP Congress 1968, Vol. 1, North Holland Pub. Co., Amsterdam, pp. 420-430.
7. 7 Strachey, C. Towards a formal semantics. In Formal Language Description Languages. North-Holland Pub. Co., Amsterdam, 1966.
8. 8 McCarthy, J., et al. Lisp 1.5 programmers manual. MIT Press, 1968.
9. 9 McCarthy, J. Recursive functions of symbolic expressions and their computation by machine, Part I. Comm. ACM 3, 4 (Apr. 1960), 184-195.
10. 10 Knuth, D.E. Fundamental Algorithms. Addison Wesley, Reading, Mass., 1968.
11. 11 Floyd, R.W. Assigning meaning to programs. Proc. Symp. Appl. Math., Vol. 19, pp. 19-31.
12. 12 Knowlton, K. A programmer's description of L. Comm. ACM 9, 8 (Aug. 1966), 616-625.
13. 13 Wirth, N. PL360, a programming language of the 360 computers. J. ACM 15, (Jan. 1968), 37-74.
14. 14 Deutsch, P., and Lampson, B. QSPL reference manual. U. of California, Berkeley, 1968.
15. 15 Richards, M. BCPL: A tool for compiler writing and system programming. Proc. AFIPS 1969 SJCC, Vol. 34, AFIPS Press, Montvale, N.J., pp. 557-566.
16. 16 Balzer, R. Dataless programming. Proc. AFIPS 1967 FJCC, Vol. AFIPS Press, Montvale, N.J., pp. 535-544.
17. 17 Holt, A.W., et al. Final report for the information system theory project. Applied Data Research, Inc., 1968.
18. 18 Earley, J. VERS-An extensible language with an implementation facility. Comput. Sci. Dep., U. of California, Berkeley, 1969.
19. 19 Christensen, Carlos. An example of the manipulation of directed graphs in the AMBIT/G programming language. In Interactive Systems for Applied Mathematics. Klerer and Reinfelds (Eds.) Academic Press, New York, 1968.
20. 20 Reynolds, J.C. A set-theoretic approach to the concept of type. Argonne Nat. Lab., 1969.
21. 21 Dennis, J.B. Programming generality, parallelism, and computer architecture. Project MAC, UlT, 1968.
22. 22 Mealy, George H. Another look at data. Proc. AFIPS 1967 FJCC, Vol. 31, AVIPS Press, Montvale, N.J., pp. 525-534.
23. 23 Ross, D.T. A generalized technique for symbol manipulation and numerical calculation. Comm. ACM 4, 3 (Mar. 1961), 147-150.
24. 24 Codd, E.F. A relational model of data for large shared data banks. Comm. ACM 13, 6 (June 1970), 377-387.
25. 25 Earley, J. and Caizergues, P. VERS Manual. Comput. Sci. Dep., U. of California, Berkeley, 1971.
26. 26 Schwartz, J. Set theory as a language for program specification and programming. New York U., 1970.

Index Terms

• Information systems

  • Information storage systems

    • Record storage systems

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures