An efficient composition of bidirectional programs by memoization and lazy update
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Bidirectional transformations (BX) are a solution to the view update problem and widely used for synchronizing data. The semantics and correctness of bidirectional programs have been investigated intensively during the past years, but their efficiency and optimization are not yet fully understood. In this paper, as a first step, we study different evaluation methods to optimize their evaluation. We focus on the interpretive evaluation of BX compositions because we found that these compositions are an important cause of redundant computations if the compositions are not right associative. For evaluating BX compositions efficiently, we investigate two memoization methods. The first method, minBiGUL m , uses memoization, which improves the runtime of many BX programs by keeping intermediate results for later reuse. A disadvantage is the familiar tradeoff for keeping and searching values in a table. When inputs become large, the overhead increases and the effectiveness decreases. To deal with large inputs, we introduce the second method, xpg, that uses tupling, lazy update and lazy evaluation as optimizations. Lazy updates delay updates in closures and enables them to use them later. Both evaluation methods were fully implemented for minBiGUL. The experimental results show that our methods are faster than the original method of BiGUL for the non-right associative compositions.
Original language | English |
---|---|
Title of host publication | Functional and Logic Programming. : 15th International Symposium, FLOPS 2020 Akita, Japan, September 14–16, 2020 Proceedings |
Editors | Keisuke Nakano, Konstantinos Sagonas |
Publisher | Springer |
Publication date | 2020 |
Pages | 159-178 |
ISBN (Print) | 9783030590246 |
DOIs | |
Publication status | Published - 2020 |
Event | 15th International Symposium on Functional and Logic Programming, FLOPS 2020 - Akita, Japan Duration: 14 Sep 2020 → 16 Sep 2020 |
Conference
Conference | 15th International Symposium on Functional and Logic Programming, FLOPS 2020 |
---|---|
Land | Japan |
By | Akita |
Periode | 14/09/2020 → 16/09/2020 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12073 LNCS |
ISSN | 0302-9743 |
- Bidirectional transformation, Efficiency, Implementation technique, Optimization, Tupling
Research areas
ID: 249395716