Data structure models for programming languages
Author:
Open Access
- 1 February 1971
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 6 (2) , 1-54
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.Keywords
This publication has 24 references indexed in Scilit:
- Some thoughts on graduate education in computer scienceACM SIGCSE Bulletin, 1970
- The importance of implementation models in ALGOL 68ACM SIGPLAN Notices, 1970
- A List Structure Form of Grammars for Syntactic AnalysisACM Computing Surveys, 1970
- Recovery of reentrant list structures in SLIPCommunications of the ACM, 1969
- Properties of Programs and the First-Order Predicate CalculusJournal of the ACM, 1969
- On the formal description of PL/IAnnual Review in Automatic Programming, 1969
- Semantics of context-free languagesTheory of Computing Systems, 1968
- Structure of a LISP system using two-level storageCommunications of the ACM, 1967
- A formal semantics for computer languages and its application in a compiler-compilerCommunications of the ACM, 1966
- A General Translation Program for Phrase Structure LanguagesJournal of the ACM, 1962