@inproceedings{6ffcfc60235e4578bfb27ee5ad8923fc,
title = "Alias types for recursive data structures",
abstract = "Linear type systems permit programmers to deallocate or explicitly recycle memory, but are severely restricted by the fact that they admit no aliasing. This paper describes a pseudo-linear type system that allows a degree of aliasing and memory reuse as well as the ability to define complex recursive data structures. Our type system can encode conventional linear data structures such as linear lists and trees as well as more sophisticated data structures including cyclic and doubly-linked lists and trees. In the latter cases, our type system is expressive enough to represent pointer aliasing and yet safely permit destructive operations such as object deallocation. We demonstrate the flexibility of our type system by encoding two common space-conscious algorithms: Destination-passing style and Deutsch-Schorr-Waite or “link-reversal” traversal algorithms.",
author = "David Walker and Greg Morrisett",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 3rd International Workshop on Types in Compilation, TIC 2000 ; Conference date: 21-09-2000 Through 21-09-2000",
year = "2001",
doi = "10.1007/3-540-45332-6_7",
language = "English (US)",
isbn = "3540421963",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "177--206",
editor = "Robert Harper",
booktitle = "Types in Compilation - Third InternationalWorkshop, TIC 2000 Montreal, Canada, September 21, 2000 Revised Selected Papers",
address = "Germany",
}