Abstract
Region-based memory management scheme has been proposed for the programming language ML. In this scheme, a compiler statically estimates the lifetime of each object by performing an extension of type inference (called region inference) and inserts code for memory allocation and deallocation. Advantages of this scheme are that memory objects can be deallocated safely (unlike with manual memory management using malloc/free) and often earlier than with run-time garbage collection. Since the region inference is an extension of the ML type inference, however, it was not clear whether the region-based memory management was applicable to dynamically-typed programming languages like Scheme. In this paper, we show that the region-based memory management can be applied to dynamically-typed languages by combining region inference and Cartwright et al.’s soft type system.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aiken, A., Fahndrich, M., Levien, R.: Better static memory management: Improving region-based analysis of higher-order languages. In: Proc. of PLDI, pp. 174–185 (1995)
Birkedal, L., Tofte, M., Vejlstrup, M.: From region inference to von Neumann machines via region representation inference. In: Proc. of POPL, pp. 171–183. ACM Press, New York (1996)
Boyapati, C., Salcianu, A., Beebee, W., Rinard, J.: Ownership types for safe region-based memory management in Real-Time Java (2003)
Calcagno, C., Helsen, S., Thiemann, P.: Syntactic type soundness results for the region calculus. Info. Comput. 173(2), 199–221 (2002)
Cartwright, R., Fagan, M.: Soft typing. In: Proc. of PLDI, pp. 278–292 (1991)
Crary, K., Walker, D., Morrisett, G.: Typed memory management in a calculus of capabilities. In: Proc. of POPL, New York, NY, pp. 262–275 (1999)
Deters, M., Cytron, R.K.: Automated discovery of scoped memory regions for real-time java. In: Proceedings of ISMM 2002, pp. 25–35. ACM Press, New York (2002)
Gabriel, R.: Scheme version of the gabriel lisp benchmarks (1988)
Gay, D., Aiken, A.: Memory management with explicit regions. In: Proc. of PLDI, pp. 313–323 (1998)
Gay, D., Aiken, A.: Language support for regions. In: Proc. of PLDI, pp. 70–80 (2001)
Grossman, D., Morrisett, G., Jim, T., Hicks, M., Wang, Y., Cheney, J.: Region-based memory management in Cyclone. In: SIGPLAN Conference on Programming Language Design and Implementation, pp. 282–293 (2002)
Hallenberg, N., Elsman, M., Tofte, M.: Combining region inference and garbage collection. In: Proc. of PLDI, pp. 141–152. ACM Press, New York (2002)
Igarashi, A., Kobayashi, N.: Resource usage analysis. ACM Trans. Prog. Lang. Syst. (to appear); A summary appeared in Proc. of POPL, pp. 331–342 (2002)
Kelsey, R., Clinger, W., Rees, J. (eds.): Revised5 report on the algorithmic language Scheme. ACM SIGPLAN Notices, vol. 33(9), pp. 26–76 (1998)
Kobayashi, N.: Quasi-linear types. In: Proc. of POPL, pp. 29–42 (1999)
Lee, O., Yang, H., Yi, K.: Inserting safe memory reuse commands into ml-like programs. In: Cousot, R. (ed.) SAS 2003. LNCS, vol. 2694, pp. 171–188. Springer, Heidelberg (2003)
Makholm, H.: Region-based memory management in Prolog. Master’s thesis, DIKU, University of Copenhagen (2000)
Makholm, H.: A region-based memory manager for Prolog. In: B. Demoen (ed.) First Workshop on Memory Management in Logic Programming Implementations, CL 2000, vol. CW 294, London, England, pp. 28–40, Katholieke Universiteit Leuven (2000)
Nagata, A., Kobayashi, N., Yonezawa, A.: Region-based memory management for a dynamically-typed language (2004), Full version, available from: http://www.yl.is.s.u-tokyo.ac.jp/~ganat/research/region/
Pessaux, F., Leroy, X.: Type-based analysis of uncaught exceptions. In: Proc. of POPL, pp. 276–290 (1999)
Rehof, J.: Polymorphic dynamic typing. Aspects of proof theory and inferencej. Master’s thesis, DIKU, University of Copenhagen (August 1995)
Tofte, M., Birkedal, L.: A region inference algorithm. ACM Trans. Prog. Lang. Syst. 20(4), 724–767 (1998)
Tofte, M., Talpin, J.-P.: Implementing the call-by-value lambda-calculus using a stack of regions. In: Proc. of POPL, pp. 188–201. ACM Press, New York (1994)
Turner, D.N., Wadler, P., Mossin, C.: Once upon a type. In: Proc. of Functional Programming Languages and Computer Architecture, San Diego, California, pp. 1–11 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nagata, A., Kobayashi, N., Yonezawa, A. (2004). Region-Based Memory Management for a Dynamically-Typed Language. In: Chin, WN. (eds) Programming Languages and Systems. APLAS 2004. Lecture Notes in Computer Science, vol 3302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30477-7_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-30477-7_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23724-2
Online ISBN: 978-3-540-30477-7
eBook Packages: Springer Book Archive