<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T08:27:59Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/3773" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/3773</identifier><datestamp>2026-05-13T16:37:03Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Fluet, Matthew</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-11-09T13:10:03Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-11-09T13:10:03Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2006-11-09T13:10:03Z</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/3773</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">6475876</dim:field>
   <dim:field mdschema="dc" element="description" lang="en_US">Committee: Greg Morrisett (Chair), Andrew Myers, Andrew Galloway</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">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&#xd;
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.&#xd;
&#xd;
&#xd;
We describe three type systems for region-based memory management:&#xd;
* a type-and-effect system (a la the Tofte-Talpin region calculus);&#xd;
* a novel monadic type system;&#xd;
* a novel substructural type system.&#xd;
We demonstrate how to successively encode the type-and-effect system into the monadic type system and the monadic type system into the&#xd;
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&#xd;
neither the simplest nor the most expressive type systems for this purpose.&#xd;
&#xd;
&#xd;
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.&#xd;
&#xd;
&#xd;
However, both the type-and-effect system and the monadic type system require that regions have nested lifetimes, following the lexical&#xd;
scope of the program, restricting when data may be effectively reclaimed.  Hence, we introduce a substructural type system that&#xd;
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.&#xd;
&#xd;
&#xd;
Finally, we show that the substructural type system is expressive enough to faithfully encode other advanced memory-management features.</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="sponsorship" lang="en_US">National Science Foundation, Air Force Office of Scientific Research, and Office of Naval Research</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">1228568 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en_US">en_US</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="isformatof">bibid: 6475876</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">type systems</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">region-based memory management</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">Monadic and Substructural Type Systems for Region-Based Memory Management</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Fluet, Matthew</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="4a7fc540-c067-4664-bf0e-e10399657eb2">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en_US&lt;/Language>
   	&lt;Title>Monadic and Substructural Type Systems for Region-Based Memory Management&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2006-11-09T13:10:03Z&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Fluet, Matthew&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>type systems&lt;/Keyword>
    &lt;Keyword>region-based memory management&lt;/Keyword>
   	&lt;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&#xd;
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.&#xd;
&#xd;
&#xd;
We describe three type systems for region-based memory management:&#xd;
* a type-and-effect system (a la the Tofte-Talpin region calculus);&#xd;
* a novel monadic type system;&#xd;
* a novel substructural type system.&#xd;
We demonstrate how to successively encode the type-and-effect system into the monadic type system and the monadic type system into the&#xd;
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&#xd;
neither the simplest nor the most expressive type systems for this purpose.&#xd;
&#xd;
&#xd;
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.&#xd;
&#xd;
&#xd;
However, both the type-and-effect system and the monadic type system require that regions have nested lifetimes, following the lexical&#xd;
scope of the program, restricting when data may be effectively reclaimed.  Hence, we introduce a substructural type system that&#xd;
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&amp;apos;&amp;apos; the monad to reveal its store-passing implementation.&#xd;
&#xd;
&#xd;
Finally, we show that the substructural type system is expressive enough to faithfully encode other advanced memory-management features.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>