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. Section II 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 IV explains the modification. Section V introduces the environments for handling variables and identifiers, and shows how the semantical equations define equivalence of programs. Section VI 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.