Data structure models for programming languages

ABSTRACT

This paper introduces a class of models (information structure models) for characterizing computations in terms of the data structures to which they give rise during execution, shows how such models can be used to characterize automata, digital computers and programming languages, considers in some detail the data structures generated during the execution of programs in block structure languages, develops a model for a non-block structure language (SNOBOL 4) and indicates how information structure models may be used in the semantic definition and formal characterization of programming languages. Sections 1 and 2 discuss the reasons for studying the relation between data structures and programming languages, section 3 introduces the notion of an information structure model and considers the classification of interpreters, and section 4 shows how automata, computers and programming languages may be characterized as sequential information structure models. Section 5 underlines the importance of introducing cells and references as semantic primitives of computational models. Section 6 develops models of implementation of block structure languages, section 7 considers the limitations of stack structure, and section 8 considers the hardware realization of block structure implementation of the Burroughs B6500. Section 9 develops an information structure model for the non-block structure language SNOBOL 4, while section 10 briefly discusses information structure models of language definition and the use of information structure models in proofs that programs have certain property. A final subsection considers the relative merits of axiomatic definition versus implementation-dependent definition of programming languages.

REFERENCES

• 1: Atchison et al., Curriculum 68, CACM 11, no. 3, March 1968.
• 2: Barron, D., et al., The main features of CPL, Computer Journal 6, 2, July 1963.
• 3: Berry, D. M., Introduction to Oregano, SIGPLAN Notices, February 1971 (this proceedings).
• 4: Daniel M. Berry, The importance of implementation models in ALGOL 68: or how to discover the concept of necessary environment, ACM SIGPLAN Notices, v.5 n.9, September 1970 [doi>10.1145/987429.987432]
• 5: Berry, D. M., Block structure: retention or deletion?, TR 70-29, Center for Computer and Information Sciences, Brown University, December 1970.
• 6: Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
• 7: R. A. Brooker , D. Morris, A General Translation Program for Phrase Structure Languages, Journal of the ACM (JACM), v.9 n.1, p.1-10, Jan. 1962 [doi>10.1145/321105.321106]
• 8: Burroughs B6500/7500 information processing systems characteristics manual, 1970.
• 9: Cheatham, T. E., and Sattley, K., Syntax-directed compiling, Proc. AFIPS Spring Joint Computer Conference, 1964.
• 10: Cleary, J. G., Process handling on the Burroughs B6500, Proceedings of the Fourth Australian Computer Conference, Adelaide, 1969.
• 11: Doron J. Cohen , C. C. Gotlieb, A List Structure Form of Grammars for Syntactic Analysis, ACM Computing Surveys (CSUR), v.2 n.1, p.65-82, March 1970 [doi>10.1145/356561.356565]
• 12: Ole-Johan Dahl , Kristen Nygaard, SIMULA: an ALGOL-based simulation language, Communications of the ACM, v.9 n.9, p.671-678, Sept. 1966 [doi>10.1145/365813.365819]
• 13: Dennis, J. B., Computation structures, notes for subject 6.232, M.I.T. Department of Electrical Engineering, 1970.
• 14: Domolki, B., An algorithm for syntactic analysis, Computational Linguistics 3, 1964 (Hungarian journal).
• 15: Jerome A. Feldman, A formal semantics for computer languages and its application in a compiler-compiler, Communications of the ACM, v.9 n.1, p.3-9, Jan. 1966 [doi>10.1145/365153.365156]
• 16: Floyd, R. W., Assigning meanings to programs, Proc. Symp. Applied Mathematics, American Mathematical Society, 1967.
• 17: Ralph E Griswold, The SNOBOL 4 programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 18: Henhapl, W., and Jones, C. B., The block concept and some possible implementations, with proofs of equivalence, TR 25.104, IBM Vienna, April 1970.
• 19: Holt, A., Events and conditions, Applied Data Research Report, 1970.
• 20: Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]
• 21: Johnston, J. B., The contour model of block structure processes, Proceedings of Symposium on Data Structures in Programming Languages, SIGPLAN Notices, February 1971.
• 22: Knuth, D. E., The art of computer programming, Vol. 1, Addison-Wesley, 1968.
• 23: Knuth, D. E., The semantics of programming languages, Mathematical System Theory 2, no. 2., 1968.
• 24: Lucas, P., et al., Method and notation of the formal definition of programming languages, TR 25.087, IBM Laboratory Vienna, 1968.
• 25: Lucas, R., Two constructive realizations of the block concept and their equivalence, TR 25.085, IBM Laboratory Vienna, 1968.
• 26: Lucas, P., and Walk, K., On the formal description of PL/I, Annual Review of Automatic Programming 6, part 3, 1969.
• 27: Zohar Manna, Properties of Programs and the First-Order Predicate Calculus, Journal of the ACM (JACM), v.16 n.2, p.244-255, April 1969 [doi>10.1145/321510.321516]
• 28: Markovitz, H., et al., SIMSCRIPT Manual, Prentice-Hall, 1963.
• 29: McCarthy, J., Towards a mathematical science of computation, Proc. IFIPS Congress 1962, North-Holland, 1963.
• 30: McCarthy, J., A basis for a mathematical theory of computation, in Computer programming and formal systems, ed. P. Braffort and B. Hirschberg, North-Holland, 1963.
• 31: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 32: McCarthy, J., and Painter, J., Correctness of a compiler for arithmetic expressions, TR CS38, Computer Science Department, Stanford University, 1966.
• 33: Clement Leo Mcgowan, III, Correctness results for lambda calculus interpreters, 1971
• 34: McGowan, C., and Wegner, P., The equivalence of sequential and associative information structure models, Proceedings of Symposium on Data Structures in Programming Languages, Gainesville, Florida, SIGPLAN Notices, February 1971.
• 35: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 36: Organick, E. I., and Cleary, J. G., A data structure model of the B6700 computer system, Proceedings of the Symposium on Data Structures in Programming Languages, Gainesville, Florida, SIGPLAN Notices, February 1971.
• 37: Perlis, A. J., Computer science and mathematics, SIGCSE Bulletin, September-October 1970.
• 38: PL/I Reference Manual, IBM System Reference Library, File No. 5360-24, Form No. C28-8201-1, 1968.
• 39: Standish, T. C., private communication.
• 40: Stearns, R. E., and Lewis, P. M., Property grammars and table machines, Information and Control 14, 1969.
• 41: Strachey, C., Fundamental concepts in programming languages, NATO Conference, Copenhagen, 1967.
• 42: A. van Wijngaarden, Report on the algorithmic language ALGOL 68, Printing by the Mathematisch Centrum, 1969
• 43: Peter. Wegner, Programming Languages, Information Structures, and Machine Organization., McGraw Hill Text, 1968
• 44: Wegner, P., Three computer cultures - computer technology, computer mathematics and computer science, Advances in Computers 10, 1970.
• 45: Wegner, P., Information structure models for programming languages, TR 70-26, Center for Computer and Information Sciences, Brown University, September 1970.
• 46: Wegner, P., The Vienna Definition Language, TR 70-21-2, Center for Computer and Information Sciences, Brown University, May 1970.
• 47: Peter Wegner, Some thoughts on graduate education in computer science, ACM SIGCSE Bulletin, v.2 n.4, p.30-40, September-October 1970 [doi>10.1145/873661.873663]
• 48: Peter Wegner, The Structure of SNOBOL4, Cornell University, Ithaca, NY, 1968
• 49: Wegner, P., The Domolki algorithm, TR 68-18, Department of Computer Science, Cornell University, May 1968.
• 50: Joseph Weizenbaum, Recovery of reentrant list structures in SLIP, Communications of the ACM, v.12 n.7, p.370-372, July 1969 [doi>10.1145/363156.363159]
• 51: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]
• 52: Conway, M. E., A multiprocessor system design, Proc. Fall Joint Computer Conference, 1963.