Elementary data structures in ALGOL-like languages (Q909449)

The author compares the applicative (or functional) programming paradigm with the imperative (or procedural) one and examines programming languages for whether they are able to support both styles adequately. Although no existing or proposed language achieves this ambitious ideal, ALGOL 60 combines some desirable attributes of both styles to such an extent that this language provides us with a frame work for designing a language which approaches the goal. The introduction discusses the principles that are characteristic of ALGOL-like languages. The next four sections summarize well-known theoretical results on types, abstract syntax, semantics, coercions and conjunctive types. Sections 6 and 7 present the main features of the author's solution, i.e., facilities for creating and using composite objects such as records and arrays. He distinguishes phrase-type structures that are denotable by identifiers from data-type structures that may be assigned to variables. In both cases, he discusses products, sums and arrays. The semantics is given in a denotational way. It seems to be easier to reason about programs in a language as it is presented here because both the laws of the lambda calculus and Hoare- like axioms are valid; the author, however, does not suppress some open problems. The list of references is very comprehensive and valuable. The paper can be recommended to anyone who is interested in the fundamentals of programming languages.