The Theory and Practice of Causal Commutative Arrows.
详细信息
文摘
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 Yampa, a functional reactive programming FRP) language embedded in Haskell. 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 for the lack of a domain specific knowledge. In this thesis, we present a more constrained class of arrows called causal commutative arrows CCA) that introduces an init operator to capture the causal nature of arrow effects, as well as two additional laws. Our key contribution is the identification of a normal form for CCA, and by defining a normalization procedure we have developed an optimization strategy that yields dramatic improvements in performance over conventional implementations of arrows. To study this abstract class of computation more concretely, we explore three different and yet related applications of CCA, namely, synchronous dataflow, ordinary differential equation, and functional reactive programming. For each application, we develop an arrow based DSL that is an instance of CCA, and we show their significant advantages at improving programs run-time behavior, such as eliminating hideous space leaks, and boosting performances by orders of magnitude.