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: standish, T.A. A data definition facility for programming languages Ph.D. Th., Carnegie-Mellon U., 1967.
• 2: Pratt, T.W. Semantic modeling by hierarchical graphs. U. of Texas, 1969.
• 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: Reynolds, J.C. Automatic computation of data set definitions. Proc. IFIP Congress 1968, Vol. 1, North Holland Pub. Co., Amsterdam, pp. 456-461.
• 5: John C. Reynolds, G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept, Communications of the ACM, v.13 n.5, p.308-319, May 1970 [doi>10.1145/362349.362364]
• 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: Strachey, C. Towards a formal semantics. In Formal Language Description Languages. North-Holland Pub. Co., Amsterdam, 1966.
• 8: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 9: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 10: Knuth, D.E. Fundamental Algorithms. Addison Wesley, Reading, Mass., 1968.
• 11: Floyd, R.W. Assigning meaning to programs. Proc. Symp. Appl. Math., Vol. 19, pp. 19-31.
• 12: Kenneth C. Knowlton, A programmer's description of L6, Communications of the ACM, v.9 n.8, p.616-625, Aug. 1966 [doi>10.1145/365758.365792]
• 13: Niklaus Wirth, PL360, a Programming Language for the 360 Computers, Journal of the ACM (JACM), v.15 n.1, p.37-74, Jan. 1968 [doi>10.1145/321439.321442]
• 14: Deutsch, P., and Lampson, B. QSPL reference manual. U. of California, Berkeley, 1968.
• 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: Balzer, R. Dataless programming. Proc. AFIPS 1967 FJCC, Vol. AFIPS Press, Montvale, N.J., pp. 535-544.
• 17: Holt, A.W., et al. Final report for the information system theory project. Applied Data Research, Inc., 1968.
• 18: Earley, J. VERS-An extensible language with an implementation facility. Comput. Sci. Dep., U. of California, Berkeley, 1969.
• 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: Reynolds, J.C. A set-theoretic approach to the concept of type. Argonne Nat. Lab., 1969.
• 21: Dennis, J.B. Programming generality, parallelism, and computer architecture. Project MAC, UlT, 1968.
• 22: Mealy, George H. Another look at data. Proc. AFIPS 1967 FJCC, Vol. 31, AVIPS Press, Montvale, N.J., pp. 525-534.
• 23: Douglas T. Ross, A generalized technique for symbol manipulation and numerical calculation, Communications of the ACM, v.4 n.3, p.147-150, March 1961 [doi>10.1145/366199.366256]
• 24: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 25: Earley, J. and Caizergues, P. VERS Manual. Comput. Sci. Dep., U. of California, Berkeley, 1971.
• 26: Schwartz, J. Set theory as a language for program specification and programming. New York U., 1970.

INDEX TERMS

Keywords:
data structures, graph, implementation, programming language, semantic formalism