Reversible Functor: Immutable Aggregate with Constant Time Update Operation
Summary :
In logic programming or functional programming languages, data objects, such as terms and lists, are immutable. In a basic implementation of such language, updating one element of an aggregate (contiguous data structure, such as an array) involves making a new copy of the whole aggregate. However, such copying can be expensive, and can be avoided by using a destructive update. We introduce the concept of a wrapper which enables destructive operation on an immutable object. Based on this concept, we designed the reversible functor as a solution to the aggregate update problem. We implemented the reversible functor in the existing SB-Prolog system and carried out several benchmarks. These benchmark results show its effectiveness. When using a large functor and updating it many times, the performance is improved dramatically by implementing the reversible functor. It incurs some overhead at runtime, but the amount is small and acceptable.
- Publication
- IEICE TRANSACTIONS on Information Vol.E79-D No.12 pp.1646-1654
- Publication Date
- 1996/12/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Software Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tatsuya AOYAGI, "Reversible Functor: Immutable Aggregate with Constant Time Update Operation" in IEICE TRANSACTIONS on Information,
vol. E79-D, no. 12, pp. 1646-1654, December 1996, doi: .
Abstract: In logic programming or functional programming languages, data objects, such as terms and lists, are immutable. In a basic implementation of such language, updating one element of an aggregate (contiguous data structure, such as an array) involves making a new copy of the whole aggregate. However, such copying can be expensive, and can be avoided by using a destructive update. We introduce the concept of a wrapper which enables destructive operation on an immutable object. Based on this concept, we designed the reversible functor as a solution to the aggregate update problem. We implemented the reversible functor in the existing SB-Prolog system and carried out several benchmarks. These benchmark results show its effectiveness. When using a large functor and updating it many times, the performance is improved dramatically by implementing the reversible functor. It incurs some overhead at runtime, but the amount is small and acceptable.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_12_1646/_p
Copy
@ARTICLE{e79-d_12_1646,
author={Tatsuya AOYAGI, },
journal={IEICE TRANSACTIONS on Information},
title={Reversible Functor: Immutable Aggregate with Constant Time Update Operation},
year={1996},
volume={E79-D},
number={12},
pages={1646-1654},
abstract={In logic programming or functional programming languages, data objects, such as terms and lists, are immutable. In a basic implementation of such language, updating one element of an aggregate (contiguous data structure, such as an array) involves making a new copy of the whole aggregate. However, such copying can be expensive, and can be avoided by using a destructive update. We introduce the concept of a wrapper which enables destructive operation on an immutable object. Based on this concept, we designed the reversible functor as a solution to the aggregate update problem. We implemented the reversible functor in the existing SB-Prolog system and carried out several benchmarks. These benchmark results show its effectiveness. When using a large functor and updating it many times, the performance is improved dramatically by implementing the reversible functor. It incurs some overhead at runtime, but the amount is small and acceptable.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - Reversible Functor: Immutable Aggregate with Constant Time Update Operation
T2 - IEICE TRANSACTIONS on Information
SP - 1646
EP - 1654
AU - Tatsuya AOYAGI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 1996
AB - In logic programming or functional programming languages, data objects, such as terms and lists, are immutable. In a basic implementation of such language, updating one element of an aggregate (contiguous data structure, such as an array) involves making a new copy of the whole aggregate. However, such copying can be expensive, and can be avoided by using a destructive update. We introduce the concept of a wrapper which enables destructive operation on an immutable object. Based on this concept, we designed the reversible functor as a solution to the aggregate update problem. We implemented the reversible functor in the existing SB-Prolog system and carried out several benchmarks. These benchmark results show its effectiveness. When using a large functor and updating it many times, the performance is improved dramatically by implementing the reversible functor. It incurs some overhead at runtime, but the amount is small and acceptable.
ER -
English
