L^3: A Linear Language with Locations

Issue title: Typed Lambda Calculi and Applications 2005, Selected Papers

Article type: Research Article

Authors: Ahmed, Amal | Fluet, Matthew | Morrisett, Greg

Affiliations: Toyota Technological Institute at Chicago Chicago, IL 60637, USA. E-mail: amal@tti-c.org; fluet@tti-c.org | Harvard University, Cambridge, MA 02138, USA. E-mail: greg@eecs.harvard.edu

Abstract: We present a simple, but expressive type system that supports strong updates – updating a memory cell to hold values of unrelated types at different points in time. Our formulation is based upon a standard linear lambda calculus and, as a result, enjoys a simple semantic interpretation for types that is closely related to models for spatial logics. The typing interpretation is strong enough that, in spite of the fact that our core programming language supports shared, mutable references and cyclic graphs, every well-typed program terminates. We then consider extensions needed to model ML-style references, where the capability to access a reference cell is unrestricted, but strong updates are disallowed. Our extensions include a thaw primitive for re-gaining the capability to perform strong updates on unrestricted references. The thaw primitive is closely related to other mechanisms that support strong updates, such as CQUAL's restrict.

Journal: Fundamenta Informaticae, vol. 77, no. 4, pp. 397-449, 2007