Reversible Functor: Immutable Aggregate with Constant Time Update Operation

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 1996-12-25

著者

• Aoyagi Tatsuya

  Faculty Of Electro-communications The University Of Electro-communications

関連論文

• Reversible Functor: Immutable Aggregate with Constant Time Update Operation

スポンサーリンク