On procedures as open subroutines. I

Summary

An ALGOL program with open subroutines or macro program is a program whose procedures may be implemented as open subroutines. A macro program may be considered to be an abbreviated notation of a program without procedures. It is proved that the so called macro program problem is algorithmically unsolvable for ALGOL 60 and other ALGOL-like languages : There does not exist any algorithm which decides for any given program whether it is a macro program or not (Theorem 4.3 and 4.4 in part II). Sublanguages of ALGOL-like languages for which the macro program problem is solvable are furtheron investigated (Theorem 4.1, 5.2–5.5 in part II). For this purpose macro grammars theory is applied.

The methods of the paper are developped in part I and the key lies in a generalized langugage ALGOL 60-P-G which has the so called modularity property : There is an effective process which constructs for every original ALGOL 60-P-G program a formally equivalent one without procedure nesting (Theorem 3.3). The process mainly works by eliminating global procedure parameters (Theorem 3.1). ALGOL 60 and other known ALGOL-like languages do not have the modularity property (Theorem 3.4). Elimination of global procedure parameters is successful only for sublanguages of ALGOL 60 (Theorem 2.3–2.7).