Reference counting for reversible languages
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Modern programming languages and operating systems use heap memory
that allows allocation and deallocation of memory to be decoupled, so
they don't follow a stack discipline. Axelsen and Glück have
presented a reversible heap manager where allocation and deallocation
are each other's logical inverses: Freeing a block of memory is done
by running the allocation procedure backwards.
Axelsen and Glück use this heap manager to sketch implementation of a
simple reversible functional language where pattern matching a
constructor is the inverse of construction, so pattern-matching
implies deallocation. This requires the language to be linear: A
pointer can not be copied and it can only be eliminated by
deallocating the node to which it points.
We overcome this limitation by adding reference counts to nodes:
Copying a pointer to a node increases the reference count of the node
and eliminating a pointer decreases the reference count. We show
reversible implementations of operations on nodes with reference
counts. We then show these operations can be used when implementing a
reversible functional language RCFUN to the reversible imperative
language Janus.
that allows allocation and deallocation of memory to be decoupled, so
they don't follow a stack discipline. Axelsen and Glück have
presented a reversible heap manager where allocation and deallocation
are each other's logical inverses: Freeing a block of memory is done
by running the allocation procedure backwards.
Axelsen and Glück use this heap manager to sketch implementation of a
simple reversible functional language where pattern matching a
constructor is the inverse of construction, so pattern-matching
implies deallocation. This requires the language to be linear: A
pointer can not be copied and it can only be eliminated by
deallocating the node to which it points.
We overcome this limitation by adding reference counts to nodes:
Copying a pointer to a node increases the reference count of the node
and eliminating a pointer decreases the reference count. We show
reversible implementations of operations on nodes with reference
counts. We then show these operations can be used when implementing a
reversible functional language RCFUN to the reversible imperative
language Janus.
Original language | English |
---|---|
Title of host publication | Reversible Computation : 6th International Conference, RC 2014, Kyoto, Japan, July 10-11, 2014. Proceedings |
Editors | Shigeru Yamashita, Shin-ichi Minato |
Number of pages | 13 |
Publisher | Springer |
Publication date | 2014 |
Pages | 82-94 |
ISBN (Print) | 978-3-319-08493-0 |
ISBN (Electronic) | 978-3-319-08494-7 |
DOIs | |
Publication status | Published - 2014 |
Event | 6th International Conference on Reversible Computation - Kyoto, Japan Duration: 10 Jul 2014 → 11 Jul 2014 Conference number: 6 |
Conference
Conference | 6th International Conference on Reversible Computation |
---|---|
Nummer | 6 |
Land | Japan |
By | Kyoto |
Periode | 10/07/2014 → 11/07/2014 |
Series | Lecture notes in computer science |
---|---|
Volume | 8507 |
ISSN | 0302-9743 |
ID: 149085667