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).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aho, A. V.: Indexed grammars — an extension of the contextfree grammars. J. ACM 15, 647–671 (1968)
Dennis, J. B.: Modularity. In: Bauer, F. L. (ed.): Advanced course on software engineering. Lecture Notes in Economics and Math. Syst. 81, 128–182, Berlin-Heidelberg-New York: Springer 1973
Fischer, M. J.: Grammars with macro-like productions. Harvard University, Cambridge (Mass.), Report No. NSF-22. Math. Ling. and Autom. Translation, May 1968
Langmaack, H.: On correct procedure parameter transmission in higher programming languages. Acta Informatica 2, 110–142 (1973)
Langmaack, H.: Über eine Beziehung zwischen ALGOL-Programmen und Makro-Grammatiken. In: Hotz, G., und Langmaack, H. (Hrsg.): Tagung über Automatentheorie und formale Sprachen, Oberwolfach 29. Okt.–4. Nov. 1972. Bonn: Mitteilungen der GMD Nr. 73/6, 1973
Naur, P. (ed.): Revised report on the algorithmic language ALGOL 60. Num. Math. 4, 420–453 (1963)
Rounds, W. C.: Mappings and grammars on trees. Math. Systems Theory 4, 257–287 (1970)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Langmaack, H. On procedures as open subroutines. I. Acta Informatica 2, 311–333 (1973). https://doi.org/10.1007/BF00289503
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00289503