{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/3773"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/3773","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Monadic and Substructural Type Systems for Region-Based Memory Management","abstract":"Region-based memory management is a scheme for managing dynamically allocated data. A defining characteristic of region-based memory management is the bulk deallocation of data, which avoids both the tedium of malloc/free and the overheads of a garbage collector. Type systems for region-based memory management enhance the utility of this scheme by statically determining when a program is guaranteed to not perform any erroneous region operations. We describe three type systems for region-based memory management: * a type-and-effect system (a la the Tofte-Talpin region calculus); * a novel monadic type system; * a novel substructural type system. We demonstrate how to successively encode the type-and-effect system into the monadic type system and the monadic type system into the substructural type system. These type systems and encodings support the argument that the type-and-effect systems that have traditionally been used to ensure the safety of region-based memory management are neither the simplest nor the most expressive type systems for this purpose. The monadic type system generalizes the state monad of Launchbury and Peyton Jones and demonstrates that the well-understood parametric polymorphism of System F provides sufficient encapsulation to ensure the safety of region-based memory management. The essence of the first encoding is to translate effects to an indexed monad, trading the subtleties of a type-and-effect system for the simplicity of a monadic type system. However, both the type-and-effect system and the monadic type system require that regions have nested lifetimes, following the lexical scope of the program, restricting when data may be effectively reclaimed. Hence, we introduce a substructural type system that eliminates the nested-lifetimes requirement. The key idea is to introduce first-class capabilities that mediate access to a region and to provide separate primitives for creating and destroying regions. The essence of the second encoding is to ``break open'' the monad to reveal its store-passing implementation. Finally, we show that the substructural type system is expressive enough to faithfully encode other advanced memory-management features.","abstract_html":"Region-based memory management is a scheme for managing dynamically allocated data. A defining characteristic of region-based memory management is the bulk deallocation of data, which avoids both the tedium of malloc/free and the overheads of a garbage collector. Type systems for region-based memory management enhance the utility of this scheme by statically determining when a program is guaranteed to not perform any erroneous region operations. We describe three type systems for region-based memory management: * a type-and-effect system (a la the Tofte-Talpin region calculus); * a novel monadic type system; * a novel substructural type system. We demonstrate how to successively encode the type-and-effect system into the monadic type system and the monadic type system into the substructural type system. These type systems and encodings support the argument that the type-and-effect systems that have traditionally been used to ensure the safety of region-based memory management are neither the simplest nor the most expressive type systems for this purpose. The monadic type system generalizes the state monad of Launchbury and Peyton Jones and demonstrates that the well-understood parametric polymorphism of System F provides sufficient encapsulation to ensure the safety of region-based memory management. The essence of the first encoding is to translate effects to an indexed monad, trading the subtleties of a type-and-effect system for the simplicity of a monadic type system. However, both the type-and-effect system and the monadic type system require that regions have nested lifetimes, following the lexical scope of the program, restricting when data may be effectively reclaimed. Hence, we introduce a substructural type system that eliminates the nested-lifetimes requirement. The key idea is to introduce first-class capabilities that mediate access to a region and to provide separate primitives for creating and destroying regions. The essence of the second encoding is to ``break open&#x27;&#x27; the monad to reveal its store-passing implementation. Finally, we show that the substructural type system is expressive enough to faithfully encode other advanced memory-management features.","abstract_has_math":false,"creators":["Fluet, Matthew"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006-11-09T13:10:03Z","date_published":"2006-11-09T13:10:03Z","updated_at":"2026-11-19T03:18:04Z","subjects":["type systems","region-based memory management"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475876"],"render_values":[{"text":"6475876","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/3773","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/3773","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F3773","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Fluet, Matthew"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2006-11-09T13:10:03Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2006-11-09T13:10:03Z"]},{"key":"dc:date.issued","label":"Date","values":["2006-11-09T13:10:03Z"]},{"key":"dc:relation.isformatof","label":"Dc Relation Isformatof","values":["bibid: 6475876"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["type systems","region-based memory management"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475876"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/3773"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"4a7fc540-c067-4664-bf0e-e10399657eb2\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Monadic and Substructural Type Systems for Region-Based Memory Management</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2006-11-09T13:10:03Z</PublicationDate> <Authors> <Author> <DisplayName>Fluet, Matthew</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>type systems</Keyword> <Keyword>region-based memory management</Keyword> <Abstract>Region-based memory management is a scheme for managing dynamically allocated data. A defining characteristic of region-based memory management is the bulk deallocation of data, which avoids both the tedium of malloc/free and the overheads of a garbage collector. Type systems for region-based memory management enhance the utility of this scheme by statically determining when a program is guaranteed to not perform any erroneous region operations. We describe three type systems for region-based memory management: * a type-and-effect system (a la the Tofte-Talpin region calculus); * a novel monadic type system; * a novel substructural type system. We demonstrate how to successively encode the type-and-effect system into the monadic type system and the monadic type system into the substructural type system. These type systems and encodings support the argument that the type-and-effect systems that have traditionally been used to ensure the safety of region-based memory management are neither the simplest nor the most expressive type systems for this purpose. The monadic type system generalizes the state monad of Launchbury and Peyton Jones and demonstrates that the well-understood parametric polymorphism of System F provides sufficient encapsulation to ensure the safety of region-based memory management. The essence of the first encoding is to translate effects to an indexed monad, trading the subtleties of a type-and-effect system for the simplicity of a monadic type system. However, both the type-and-effect system and the monadic type system require that regions have nested lifetimes, following the lexical scope of the program, restricting when data may be effectively reclaimed. Hence, we introduce a substructural type system that eliminates the nested-lifetimes requirement. The key idea is to introduce first-class capabilities that mediate access to a region and to provide separate primitives for creating and destroying regions. The essence of the second encoding is to ``break open'' the monad to reveal its store-passing implementation. Finally, we show that the substructural type system is expressive enough to faithfully encode other advanced memory-management features.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Fluet, Matthew"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description","label":"Description","values":["Committee: Greg Morrisett (Chair), Andrew Myers, Andrew Galloway"]},{"key":"dc:description.abstract","label":"Abstract","values":["Region-based memory management is a scheme for managing dynamically allocated data. A defining characteristic of region-based memory management is the bulk deallocation of data, which avoids both the tedium of malloc/free and the overheads of a garbage collector. Type systems for region-based memory management enhance the utility of this scheme by statically determining when a program is guaranteed to not perform any erroneous region operations. We describe three type systems for region-based memory management: * a type-and-effect system (a la the Tofte-Talpin region calculus); * a novel monadic type system; * a novel substructural type system. We demonstrate how to successively encode the type-and-effect system into the monadic type system and the monadic type system into the substructural type system. These type systems and encodings support the argument that the type-and-effect systems that have traditionally been used to ensure the safety of region-based memory management are neither the simplest nor the most expressive type systems for this purpose. The monadic type system generalizes the state monad of Launchbury and Peyton Jones and demonstrates that the well-understood parametric polymorphism of System F provides sufficient encapsulation to ensure the safety of region-based memory management. The essence of the first encoding is to translate effects to an indexed monad, trading the subtleties of a type-and-effect system for the simplicity of a monadic type system. However, both the type-and-effect system and the monadic type system require that regions have nested lifetimes, following the lexical scope of the program, restricting when data may be effectively reclaimed. Hence, we introduce a substructural type system that eliminates the nested-lifetimes requirement. The key idea is to introduce first-class capabilities that mediate access to a region and to provide separate primitives for creating and destroying regions. The essence of the second encoding is to ``break open'' the monad to reveal its store-passing implementation. Finally, we show that the substructural type system is expressive enough to faithfully encode other advanced memory-management features."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:description.sponsorship","label":"Dc Description Sponsorship","values":["National Science Foundation, Air Force Office of Scientific Research, and Office of Naval Research"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["1228568 bytes"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Monadic and Substructural Type Systems for Region-Based Memory Management"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"4a7fc540-c067-4664-bf0e-e10399657eb2\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Monadic and Substructural Type Systems for Region-Based Memory Management</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2006-11-09T13:10:03Z</PublicationDate> <Authors> <Author> <DisplayName>Fluet, Matthew</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>type systems</Keyword> <Keyword>region-based memory management</Keyword> <Abstract>Region-based memory management is a scheme for managing dynamically allocated data. A defining characteristic of region-based memory management is the bulk deallocation of data, which avoids both the tedium of malloc/free and the overheads of a garbage collector. Type systems for region-based memory management enhance the utility of this scheme by statically determining when a program is guaranteed to not perform any erroneous region operations. We describe three type systems for region-based memory management: * a type-and-effect system (a la the Tofte-Talpin region calculus); * a novel monadic type system; * a novel substructural type system. We demonstrate how to successively encode the type-and-effect system into the monadic type system and the monadic type system into the substructural type system. These type systems and encodings support the argument that the type-and-effect systems that have traditionally been used to ensure the safety of region-based memory management are neither the simplest nor the most expressive type systems for this purpose. The monadic type system generalizes the state monad of Launchbury and Peyton Jones and demonstrates that the well-understood parametric polymorphism of System F provides sufficient encapsulation to ensure the safety of region-based memory management. The essence of the first encoding is to translate effects to an indexed monad, trading the subtleties of a type-and-effect system for the simplicity of a monadic type system. However, both the type-and-effect system and the monadic type system require that regions have nested lifetimes, following the lexical scope of the program, restricting when data may be effectively reclaimed. Hence, we introduce a substructural type system that eliminates the nested-lifetimes requirement. The key idea is to introduce first-class capabilities that mediate access to a region and to provide separate primitives for creating and destroying regions. The essence of the second encoding is to ``break open'' the monad to reveal its store-passing implementation. Finally, we show that the substructural type system is expressive enough to faithfully encode other advanced memory-management features.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Fluet, Matthew"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:creator":["Fluet, Matthew"],"dc:date.accessioned":["2006-11-09T13:10:03Z"],"dc:date.available":["2006-11-09T13:10:03Z"],"dc:date.issued":["2006-11-09T13:10:03Z"],"dc:description":["Committee: Greg Morrisett (Chair), Andrew Myers, Andrew Galloway"],"dc:description.abstract":["Region-based memory management is a scheme for managing dynamically allocated data. A defining characteristic of region-based memory management is the bulk deallocation of data, which avoids both the tedium of malloc/free and the overheads of a garbage collector. Type systems for region-based memory management enhance the utility of this scheme by statically determining when a program is guaranteed to not perform any erroneous region operations. We describe three type systems for region-based memory management: * a type-and-effect system (a la the Tofte-Talpin region calculus); * a novel monadic type system; * a novel substructural type system. We demonstrate how to successively encode the type-and-effect system into the monadic type system and the monadic type system into the substructural type system. These type systems and encodings support the argument that the type-and-effect systems that have traditionally been used to ensure the safety of region-based memory management are neither the simplest nor the most expressive type systems for this purpose. The monadic type system generalizes the state monad of Launchbury and Peyton Jones and demonstrates that the well-understood parametric polymorphism of System F provides sufficient encapsulation to ensure the safety of region-based memory management. The essence of the first encoding is to translate effects to an indexed monad, trading the subtleties of a type-and-effect system for the simplicity of a monadic type system. However, both the type-and-effect system and the monadic type system require that regions have nested lifetimes, following the lexical scope of the program, restricting when data may be effectively reclaimed. Hence, we introduce a substructural type system that eliminates the nested-lifetimes requirement. The key idea is to introduce first-class capabilities that mediate access to a region and to provide separate primitives for creating and destroying regions. The essence of the second encoding is to ``break open'' the monad to reveal its store-passing implementation. Finally, we show that the substructural type system is expressive enough to faithfully encode other advanced memory-management features."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:description.sponsorship":["National Science Foundation, Air Force Office of Scientific Research, and Office of Naval Research"],"dc:format.extent":["1228568 bytes"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["6475876"],"dc:identifier.uri":["https://hdl.handle.net/1813/3773"],"dc:language.iso":["en_US"],"dc:relation.isformatof":["bibid: 6475876"],"dc:subject":["type systems","region-based memory management"],"dc:title":["Monadic and Substructural Type Systems for Region-Based Memory Management"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T03:18:04Z"}