Abstract
In this paper, two implementations of generalized block-structured languages are presented and their time requirements compared. One implementation, the lifetime stack model (LSM), implements the deletion strategy with lifetime checks; the other, the partial reference count contour machine (PRCCM), implements the retention strategy. For a large subset of the lifetime well-stacking programs, which are precisely those that run correctly on the first model, the two models are shown to require nearly the same order of magnitude of time. The use of full-label values is shown to have a detrimental effect on the time efficiency of the latter model. Part 1, in this issue, gives a general description of the machines and part of their definitions, and proves the results. Part 2, in the next issue, serving as an appendix to Part 1, contains most of the formal definitions of the machines.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. M. Berry, “The importance of implementation models in Algol 68 or how to discover the concept of necessary environment,”SIGPLAN Not. 5 (9) (September 1970).
D. M. Berry, “Introduction to Oregano,”DSIPL (1971).
D. M. Berry, “Block Structure: Retention vs. Deletion,”Proceedings of the Third SIGACT Symposium on Theory of Computation, Shakes Heights, Ohio (1971).
D. M. Berry, “On the Design and Specification of the Programming Language Oregano,” UCLA-ENG-7388, Computer Science Department, University of California, Los Angeles (January 1974).
D. M. Berry and A. Sorkin, “Time required for garbage collection in retention block-structured languages,”Int. Comput. Inf. Sci., accepted.
D. B. Bobrow and B. Wegbreit, “A model and stack implementation of multiple environments,”Commun. ACM 16 (10) (October, 1973).
H. Bowlden, private communication (September 1971).
P. Branquart and J. Lewi, “A Scheme of Storage Allocation and Garbage Collection for ALGOL 68,” inALGOL 68 Implementation, J. E. L. Peck, Ed. (North Holland, Amsterdam, 1970).
L. M. Chirica, T. A. Dreisbach, D. F. Martin, J. G. Peetz, and A. Sorkin, “Two PARALLEL EULER run time models: The dangling reference, imposter environment, and label problems,” Proceedings of ACM Symposium on High Level Language Computer Architecture,SIGPLAN Not. 8 (11) (November 1973).
E. W. Dijkstra, “Notes on Structured Programming,” inStructured Programming, Dahl, Dijkstra, and Hoare, Eds. (Academic Press, New York, 1972).
M. J. Fischer, “Lambda calculus schemata,” Proceedings of ACM Conference on Proving Assertions about Programs,SIGPLAN Not. 7 (1) (January 1972).
J. B. Johnston, “The Contour Model of Block Structured Processes,”DSIPL (1971).
J. B. Johnston, D. M. Berry, and D. P. Murphy, “Expression Stack Management in Nested Declaration Computation,”Eighth Annual Princeton Conference on Information Science and Systems (March 1974).
J. R. Kelly, private communication (June 1973).
H. J. Lane, “An ALGOL 68 Machine and Translator,” Ph.D. thesis, University of California, Los Angeles (June 1973).
P. Lucas and K. Walk, “On the formal description of PL/I,”Ann. Rev. Autom. Program. 6 (3) (1969).
P. Naur, “Revised report on the algorithmic language ALGOL 60,”Commun. ACM 6 (1) (January 1963).
E. I. Organick,Computer Systems Organization (Academic Press, New York, 1973).
J. E. L. Peck (Ed.),ALGOL 68 Implementation (North Holland, Amsterdam, 1970).
B. Randall and L. J. Russell,ALGOL 60 Implementation (Academic Press, New York, 1964).
J. D. Reynolds, “GEDANKEN—A simple typeless language based on the principle of completeness and the reference concept,”Commun. ACM 13 (5) (May 1970).
D. Scott and C. Strachey, “Toward a Mathematical Semantics for Computer Languages,”Proceedings of the Symposium on Computers and Automata, Polytechnic Institute of Brooklyn (1972).
A. van Wijngaardenet al., “Report on the algorithmic language ALGOL 68,”Num. Math. 14:79–218 (1969).
A. van Wijngaardenet al, “Revised Report on the Algorithmic Language ALGOL 68,” Technical Report TR74-3, Computer Science Department, University of Alberta, Edmonton, Alberta (March 1974).
K. Walket al., Formal Definition of PL/I, ULD Version III (IBM, Vienna, 1969).
P. Wegner, “Data structure models for programming languages”,DSIPL (1971).
J. M. Wozencraft and A. Evans, “Notes on Programming Linguistics,” Electrical Engineering Department, Massachusetts Institute of Technology (1970).
Author information
Authors and Affiliations
Additional information
Supported [in part] by the National Science Foundation, Grant No. DCR75-08659.
Note:DSIPL is used for Proceedings of ACM Symposium on Data Structures in Programming Languages, SIGPLAN Notices, Vol. 65 No. 2 (February 1971).
Rights and permissions
About this article
Cite this article
Berry, D.M., Chirica, L.M., Johnston, J.B. et al. Time required for reference count management in retention block-structured languages. Part 1. International Journal of Computer and Information Sciences 7, 11–64 (1978). https://doi.org/10.1007/BF00991939
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00991939