Storage allocation in typed languages

Butler Lampson


Citation: Proc. 5th Ann. III Conf: Implementation and Design of Algorithmic Languages, Guidel, France, 1977, pp 315-322.

Links: Abstract, Acrobat, Web page, Word.

Email: This paper is at



Several interfaces between a strongly typed language and a storage allocator or deallocator are defined. Using these interfaces, it is possible to program a wide variety of allocation and automatic deallocation strategies: boundary tag allocator, buddy system, reference counting, trace-and-mark garbage collection and many others. Provided the allocator and deallocator have certain well-defined properties, the type-safeness of the language can be guaranteed.