On correct procedure parameter transmission in higher programming languages

Abstract

The paper starts with the observation that in ALGOL 60 no specifications for formal procedure parameters are prescribed, whereas ALGOL 68 demands complete specifications. As a consequence, every ALGOL 68 program accepted by the compiler does not have wrong parameter transmissions at run time whereas ALGOL 60 programs may have them. The property of ALGOL 60 programs to have only correct parameter transmissions obviously is undecidable if all data, conditional statements, etc. have to be taken into consideration and it is unfair to demand that the compiler shall figure out these programs by a finite process. Therefore, we investigate this question of decidability under a much fairer condition, namely to take into consideration no data and no conditions and to give all procedure calls occurring in the same block equal rights. Even this fairer problem turns out to be algorithmically unsolvable, in general (Theorem 3), but it is solvable as soon as the programs do not have global formal procedure parameters (Theorem 1). Analogous answers can be given to the problems of formal equivalence of programs and of formal reachability, formal recursivity, and strong recursivity of procedures (Theorems 5-8). Procedures which are not strongly recursive have great importance in compilation techniques as is shown in Section X.