论文标题
记忆的套牌用于功能逻辑编程
Memoized Pull-Tabbing for Functional Logic Programming
论文作者
论文摘要
Pull-Tabbing是功能逻辑程序的评估技术，它计算单个图结构中所有非确定性结果。 Pull-Tab步骤是局部图转换，将非确定性选择移至表达式的根。套牌独立于搜索策略，因此可以使用不同的策略（深度优先，广度优先，平行）来提取计算结果。它已被用来将功能性逻辑语言汇编成命令或纯粹的功能性目标语言。在共享子表达的情况下，Pull-Tab步骤可能会复制选择。与回溯实现相比，这可能导致执行时间急剧增加。在本文中，我们提出了一种改进，可以避免此效率问题，同时保留所有贴套的良好特性。我们评估了朱莉娅编程语言中这种改进技术的首次实施。
Pull-tabbing is an evaluation technique for functional logic programs which computes all non-deterministic results in a single graph structure. Pull-tab steps are local graph transformations to move non-deterministic choices towards the root of an expression. Pull-tabbing is independent of a search strategy so that different strategies (depth-first, breadth-first, parallel) can be used to extract the results of a computation. It has been used to compile functional logic languages into imperative or purely functional target languages. Pull-tab steps might duplicate choices in case of shared subexpressions. This could result in a dramatic increase of execution time compared to a backtracking implementation. In this paper we propose a refinement which avoids this efficiency problem while keeping all the good properties of pull-tabbing. We evaluate a first implementation of this improved technique in the Julia programming language.
