A model and stack implementation of multiple environments

ABSTRACT

Many control and access environment structures require that storage for a procedure activation exist at times when control is not nested within the procedure activated. This is straightforward to implement by dynamic storage allocation with linked blocks for each activation, but rather expensive in both time and space. This paper presents an implementation technique using a single stack to hold procedure activation storage which allows retention of that storage for durations not necessarily tied to control flow. The technique has the property that, in the simple case, it runs identically to the usual automatic stack allocation and deallocation procedure. Applications of this technique to multitasking, coroutines, backtracking, label-valued variables, and functional arguments are discussed. In the initial model, a single real processor is assumed, and the implementation assumes multiple-processes coordinate by passing control explicitly to one another. A multiprocessor implementation requires only a few changes to the basic technique, as described.

REFERENCES

• 1: Bobrow, D.G. Storage management in Lisp. In Symbol Manipulation Languages and Techniques, Bobrow (Ed.), North- Holland Pub. Co., Amsterdam, 1968.
• 2: Daniel G. Bobrow, Requirements for advanced programming systems for list processing, Communications of the ACM, v.15 n.7, p.618-627, July 1972 [doi>10.1145/361454.361491]
• 3: W. H. Burge, Some examples of the use of function-producing functions, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.238-241, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806292]
• 4: Dijkstra, E.W. Co-operating sequential processes. In Programm#lg Languages, Genuys (Ed.), Academic Press, New York, 1967.
• 5: Dijkstra, E.W. Recursive programming. Num. Math. 2 (1960), 312-318. Also in Programming Systems and Languages, S. Rosen (Ed.), McGraw-Hill, New York, 1967.
• 6: Robert R. Fenichel, On implementation of label, variables, Communications of the ACM, v.14 n.5, p.349-350, May 1971 [doi>10.1145/362588.362597]
• 7: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 8: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 9: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 10: Hewitt, C. PLANNER: A language for manipulating models and proving theorems in a robot. Proc. Internat. Joint Conf. on Artif. lntell. Washington, D.C., May 1969.
• 11: IBM System/360, PL/I Language Reference Manual, Form C28-8201-2, IBM (1969).
• 12: Johnston, J.B. The contour model of block structured processes. in Tou and Wegner {23}, pp. 55-82.
• 13: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 14: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 15: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 16: Joel Moses, The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem, ACM SIGSAM Bulletin [doi>10.1145/1093410.1093411]
• 17: Charles J. Prenner , Jay M. Spitzen , Ben Wegbreit, An implementation of backtracking for programming languages, Proceedings of the ACM annual conference, p.763-771, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805856]
• 18: Prenner, C. Multi-path control structures for programming languages. Ph.D. Th., Harvard U., Cambridge, Mass. May 1972.
• 19: Quam, L. Lisp 1.6 Ref. Manual. Stanford AI Lab.
• 20: John C. Reynolds, G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept, Communications of the ACM, v.13 n.5, p.308-319, May 1970 [doi>10.1145/362349.362364]
• 21: Sussman, G.J., and McDermott, D. Why conniving is better than planning. Proc. AFIPS 1972 FJCC, Vol. 41, Part 2, AFIPS Press, Montvale, N.J., pp. 1171-1179.
• 22: Thomas, R.H. A model for process representation and synthesis. Ph.D. Th., Proj. MAC Rept. TR-87, M.I.T. Cambridge, Mass., 1971.
• 23: Tou, J., and Wegner, P. (Eds.) Sigplan Notices--Proc. Symp. on Data Structures in Prog. Lang., 6, 2 (Feb. 1971).
• 24: A. van Wijngaarden, Report on the algorithmic language ALGOL 68, Printing by the Mathematisch Centrum, 1969
• 25: Wegbreit, B. Studies in extensible programming languages. Ph.D. Th., Harvard U., Cambridge, Mass. May 1970.
• 26: Wegbreit, B. The ECL programming system. Proc. AFIPS 1971 FJCC, Vol. 39, AFIPS Press, Montvale, N.J., pp. 253-262.
• 27: Wegner, P. Data structure models for programming languages. in Tou and Wegner {23}, pp. 55-82.
• 28: Weizenbaum, J. The funarg problem explained. M.I.T., Cambridge, Mass., Mar. 1968.

INDEX TERMS

Keywords:
FUNARG problem, access environments, backtracking, control structures, coroutines, dendrarchy, dynamic storage allocation, environments, extensible control structures, functional arguments, label-valued variables, multiprocessor systems, multitasking, retention, stack allocation