Syntax and semantics of universal programming languages

Abstract

Three topics are treated in this paper:

1) The function-computed abstract definition of a programming language based on Rogers' work is presented with a discussion of its virtues and deficiences as a revealing model. Examples from recursion theory are discussed in terms of language design. (Section 2)

2) Some properties of programming languages which are associated intuitively with details of syntax and with the idea of ‘flow of control’ are shown to hold in a slight extension of the Rogers model which is too weak to express these ideas. The results involve the impossibility of detecting certain ‘stylistic’ errors in syntax. (Section 3)

3) Despite the unexpected power of the Rogers model illustrated in Section 3, the question of additional semantics to capture how programs compute is an important one in computer science.Two ideas, the measures of Blum and meaning inherited through a compiler, are explored with reference to the particular question: ‘Must a compiler work by preserving a correspondence between source and object computations ?’ Although a number of ways are given for a compiler to avoid such a correspondence, the question remains open. (Section 4)

Keywords:

• Abstract programming language
• Gödel numbering
• syntax
• semantics
• programming style
• compiler
• Hartley Rogers, Jr

C.R. Categories:

• 4.24
• 5.25
• 4.2