Causal commutative arrows and their optimization
Causal commutative arrows and their optimization
复制标题
因果交换箭头及其优化
DOI：
10.1145/1596550.1596559
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
P. Hudak
中科院分区：
文献类型：
--
作者：
Hai Liu;Eric Cheng;P. Hudak
箭头是一种流行的抽象计算形式。它们比单子更通用，适用范围更广，特别是对于信号处理和数据流计算来说是一个很好的抽象。最值得注意的是，箭头构成了称为Yampa的领域特定语言的基础，该语言已用于各种具体应用程序，包括动画、机器人、声音合成、控制系统和图形用户界面。我们的主要兴趣是更好地理解Yampa捕获的抽象计算类。不幸的是，箭头不够具体，无法精确地做到这一点。为了纠正这种情况，我们引入了交换箭头的概念，它捕获了并发计算的一种不干涉性质。我们还添加了init操作符，并确定了捕获箭头效应因果性质的关键定律。我们称由此产生的计算模型为因果交换箭头。为了更详细地研究这类计算，我们定义了简单类型λ演算的一个扩展，称为因果交换箭头（CCA），并研究了它的性质。我们的主要贡献是确定了CCA的范式，称为因果交换范式（CCNF）。通过定义规范化过程，我们开发了一种优化策略，与传统的箭头实现相比，该策略在性能上有了显著提高。我们已经在Haskell中实现了这项技术，并进行了基准测试来验证我们方法的有效性。当与流融合相结合时，整个方法可以导致超过两个数量级的加速。
Arrows are a popular form of abstract computation. Being more general than monads, they are more broadly applicable, and in particular are a good abstraction for signal processing and dataflow computations. Most notably, arrows form the basis for a domain specific language called Yampa, which has been used in a variety of concrete applications, including animation, robotics, sound synthesis, control systems, and graphical user interfaces. Our primary interest is in better understanding the class of abstract computations captured by Yampa. Unfortunately, arrows are not concrete enough to do this with precision. To remedy this situation we introduce the concept of commutative arrows that capture a kind of non-interference property of concurrent computations. We also add an init operator, and identify a crucial law that captures the causal nature of arrow effects. We call the resulting computational model causal commutative arrows. To study this class of computations in more detail, we define an extension to the simply typed lambda calculus called causal commutative arrows (CCA), and study its properties. Our key contribution is the identification of a normal form for CCA called causal commutative normal form (CCNF). By defining a normalization procedure we have developed an optimization strategy that yields dramatic improvements in performance over conventional implementations of arrows. We have implemented this technique in Haskell, and conducted benchmarks that validate the effectiveness of our approach. When combined with stream fusion, the overall methodology can result in speed-ups of greater than two orders of magnitude.