Programming language data structures: a comparative study

Recently, Scott and Strachey [7,8] developed a mathematical semantics for programming languages. In their theory a program is viewed as a function on the set of states of the computation. To identify the function associated with a program via the semantics, two additional functions are defined, the environment function and the store function. In order that these two functions are well-defined, one must specify their domains and ranges; Strachey [9] proposed that a study of these two functions and their domains and ranges would reveal the basic structure of a language and clarify underlying differences between languages. He carried out such a study for Algol 60 and PAL. In this report we follow Strachey's approach and specify the domain and range structure of the two functions for Algol 60, Fortran IV, and SNOBOL4. The following section contains the definitions of the basic functions, domains, and ranges from the general theory. In section 3 the domain and range structure is given for each of the three languages. In the last section we compare the domain and range structure of the three languages and close with a discussion of the utility of this approach to characterizing programming languages.Technical report DCS-TR-3