2018/08/24 by Sergio Antoy, Antoy, Sergio, Steven Libby +1 · 1 voice
Computer Science · #Logic, programming, and type systems #Parallel Computing and Optimization Techniques #Teaching and Learning Programming #cs.PL
paper · pdf · doi:10.48550/arxiv.1808.07990
openalex publication_date 2018/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Bubbling is a run-time graph transformation studied for the execution of non-deterministic steps in functional logic computations. This transformation has been proven correct, but as currently formulated it requires information about the entire context of a step, even when the step affects only a handful of nodes. Therefore, despite some advantages, it does not appear to be competitive with approaches that require only localized information, such as backtracking and pull-tabbing. We propose a novel algorithm that executes bubbling steps accessing only local information. To this aim, we define graphs that have an additional attribute, a dominator of each node, and we maintain this attribute when a rewrite and/or bubbling step is executed. When a bubbling step is executed, the dominator is available at no cost, and only local information is accessed. Our work makes bubbling practical, and theoretically competitive, for implementing non-determinism in functional logic computations.