An efficient composition of bidirectional programs by memoization and lazy update

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

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.
TitelFunctional and Logic Programming. : 15th International Symposium, FLOPS 2020 Akita, Japan, September 14–16, 2020 Proceedings
RedaktørerKeisuke Nakano, Konstantinos Sagonas
ISBN (Trykt)9783030590246
StatusUdgivet - 2020
Begivenhed15th International Symposium on Functional and Logic Programming, FLOPS 2020 - Akita, Japan
Varighed: 14 sep. 202016 sep. 2020


Konference15th International Symposium on Functional and Logic Programming, FLOPS 2020
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind12073 LNCS

ID: 249395716