Data Linkage Dynamics with Shedding

• Autorzy: Bergstra J.A. , Middelburg C.A.
• Języki publikacji: EN

Abstrakty

EN

We study shedding in the setting of data linkage dynamics, a simple model of computation that bears on the use of dynamic data structures in programming. Shedding is complementary to garbage collection. With shedding, each time a link to a data object is updated by a program, it is determined whether or not the link will possibly be used once again by the program, and if not the link is automatically removed. Thus, everything is made garbage as soon as it can be viewed as garbage. By that, the effectiveness of garbage collection becomes maximal.

Słowa kluczowe

EN

data linkage dynamics; shedding; forecasting service

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 103, nr 1-4
• Strony: 31--52
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Bergstra J.A.

autor

Middelburg C.A.

• Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands,

Bibliografia

• [1] Agesen, O., Detlefs, D., Moss, J. E.: Garbage Collection and Local Variable Type-Precision and Liveness in Java Virtual Machines, ACM SIGPLAN Notices, 33(5), 1998, 269-279.
• [2] Appel, A. W.: Runtime Tags Aren't Necessary, Lisp and Symbolic Computation, 2(2), 1989, 153-162.
• [3] Baeten, J. C. M., Bergstra, J. A., Klop, J. W., Weijland, W. P.: Term-Rewriting Systems with Rule Priorities, Theoretical Computer Science, 67(2-3), 1989, 283-301.
• [4] Baker Jr., H. G.: List Processing in Real Time on a Serial Computer, Communications of the ACM, 21(4), 1978, 280-294.
• [5] Bergstra, J. A., Bethke, I.: Polarized Process Algebra and Program Equivalence, Proceedings 30th ICALP (J. C. M. Baeten, J. K. Lenstra, J. Parrow, G. J. Woeginger, Eds.), LNCS 2719, Springer-Verlag, 2003, 1-21.
• [6] Bergstra, J. A., Bethke, I., Ponse, A.: Thread Algebra and Risk Assessment Services, Logic Colloquium 2005 (C. Dimitracopoulos, L. Newelski, D. Normann, Eds.), Springer-Verlag, 2007, 1-17.
• [7] Bergstra, J. A., Loots, M. E.: Program Algebra for Sequential Code, Journal of Logic and Algebraic Programming, 51(2), 2002, 125-156.
• [8] Bergstra, J. A., Middelburg, C. A.: Thread Algebra for Strategic Interleaving, Formal Aspects of Computing, 19(4), 2007, 445-474.
• [9] Bergstra, J. A., Middelburg, C. A.: Data Linkage Algebra, Data Linkage Dynamics, and Priority Rewriting, Electronic Report PRG0806, Programming Research Group, University of Amsterdam,May 2008, Available from http://arxiv.org/: arXiv:0804.4565v2 [cs.LO].
• [10] Bergstra, J. A., Ponse, A.: Execution Architectures for Program Algebra, Journal of Applied Logic, 5(1), 2007, 170-192.
• [11] Boehm, H.-J., Weiser, M.: Garbage Collection in an Uncooperative Environment, Software Practice and Experience, 18(9), 1988, 807-820.
• [12] Collins, G. E.: A method for overlapping and erasure of lists, Communications of the ACM, 3(12), 1960, 655-657.
• [13] Dijkstra, E.W., Lamport, L.,Martin, A. J., Scholten, C. S., Steffens, E. F.M.: On-the-FlyGarbage Collection: An Exercise in Cooperation, Communications of the ACM, 21(11), 1978, 966-975.
• [14] Fenichel, R. R., Yochelson, J. C.: A LISP Garbage-Collector for Virtual-Memory Computer Systems, Communications of the ACM, 12(11), 1969, 611-612.
• [15] Gelernter, H., Hansen, J. R., Gerberich, C. L.: A Fortran-Compiled List-Processing Language, Journal of the ACM, 7(2), 1960, 87-101.
• [16] Goldberg, B.: Tag-Free Garbage Collection for Strongly Typed Programming Languages, PLDI '91, ACM Press, 1991, 165-176.
• [17] Hirzel, M., Diwan, A., Henkel, J.: On the Usefulness of Type and Liveness Accuracy for Garbage Collection and Leak Detection, ACM Transactions on Programming Languages and Systems, 24(6), 2002, 593-624.
• [18] Khedker, U. P., Sanyal, A., Karkare, A.: Heap Reference Analysis Using Access Graphs, ACM Transactions on Programming Languages and Systems, 30(1), 2007, Article 1.
• [19] Kung, H. T., Song, S.W.: An Efficient Parallel Garbage Collection System And Its Correctness Proof, FOCS 1977, IEEE Computer Society Press, 1977, 120-131.
• [20] Lieberman, H., Hewitt, C.: A Real-Time Garbage Collector Based on the Lifetimes of Objects, Communications of the ACM, 26(6), 1983, 419-429.
• [21] McCarthy, J.: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Communications of the ACM, 3(4), 1960, 184-195.
• [22] Minsky, M. L.: A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Memo 58 (Revised), Project MAC, Massachusetts Institute of Technology, December 1963.
• [23] Sannella, D., Tarlecki, A.: Algebraic Preliminaries, in: Algebraic Foundations of Systems Specification (E. Astesiano, H.-J. Kreowski, B. Krieg-Br¨uckner, Eds.), Springer-Verlag, Berlin, 1999, 13-30.
• [24] Schorr, H., Waite, W.: An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures, Communications of the ACM, 10(8), 1967, 501-506.
• [25] Shaham, R., Kolodner, E. K., Sagiv, M.: On Effectiveness of GC in Java, ISMM '00, ACM Press, 2000, 12-17.
• [26] Shaham, R., Kolodner, E. K., Sagiv, M.: Heap Profiling for Space-Efficient Java, ACM SIGPLAN Notices, 36(5), 2001, 104-113.
• [27] Shaham, R., Yahav, E., Kolodner, E. K., Sagiv,M.: Establishing Local Temporal Heap Safety Properties with Applications to Compile-Time Memory Management, Science of Computer Programming, 58(1-2), 2005, 264-289.
• [28] Steele Jr., G. L.: Multiprocessing Compactifying Garbage Collection, Communications of the ACM, 18(9), 1975, 495-508.
• [29] Wirsing,M.: Algebraic Specification, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Elsevier, Amsterdam, 1990, 675-788.