TOWARD A MATHEMATICAL SEMANTICS FOR COMPUTER LANGUAGES

Abstract

Compilers for high-level languages are generally constructed to give the complete translation of the programs into machine language. As machines merely juggle bit patterns, the concepts of the original language may be lost or at least obscured during this passage. The purpose of a mathematical semantics is to give a correct and meaningful correspondence between programs and mathematical entities in a way that is entirely independent of an implementation. This plan is illustrated in a very elementary way in the introduction. The first section connects the general method with the usual idea of state transformations. The next section shows why the mathematics of functions has to be modified to accommodate recursive commands. Section 3 explains the modification. Section 4 introduces the environments for handling variables and identifiers and shows how the semantical equations define equivalence of programs. Section 5 gives an exposition of the new type of mathematical function spaces that are required for the semantics of procedures when these are allowed in assignment statements. The conclusion traces some of the background of the project and points the way to future work.