one-way, dataflowconstraints are commonly used in graphical interface toolkits, programming environments, and circuit applications. Previous papers on dataflowconstraints have focused on the design and implementatio...
详细信息
one-way, dataflowconstraints are commonly used in graphical interface toolkits, programming environments, and circuit applications. Previous papers on dataflowconstraints have focused on the design and implementation of individual algorithms. In contrast, this article focuses on the lessons we have learned from a decade of implementing competing algorithms in the Garnet and Amulet graphical interface toolkits. These lessons reveal the design and implementation tradeoffs for different one-way, constraint satisfaction algorithms. The most important lessons we have learned are that (1) mark-sweep algorithms are more efficient than topological ordering algorithms;(2) lazy and eager evaluators deliver roughly comparable performance for most applications;and (3) constraint satisfaction algorithms have more than adequate speed, except that the storage required by these algorithms can be problematic.
dataflow languages provide natural support for specifying constraints between objects in dynamic applications, where programs need to react efficiently to changes in their environment. In this article, we show that on...
详细信息
dataflow languages provide natural support for specifying constraints between objects in dynamic applications, where programs need to react efficiently to changes in their environment. In this article, we show that one-way dataflow constraints, largely explored in the context of interactive applications, can be seamlessly integrated in any imperative language and can be used as a general paradigm for writing performance-critical reactive applications that require efficient incremental computations. In our framework, programmers can define ordinary statements of the imperative host language that enforce constraints between objects stored in special memory locations designated as "reactive." Reactive objects can be of any legal type in the host language, including primitive data types, pointers, arrays, and structures. Statements defining constraints are automatically re-executed every time their input memory locations change, letting a program behave like a spreadsheet where the values of some variables depend on the values of other variables. The constraintsolving mechanism is handled transparently by altering the semantics of elementary operations of the host language for reading and modifying objects. We provide a formal semantics and describe a concrete embodiment of our technique into C/C++, showing how to implement it efficiently in conventional platforms using off-the-shelf compilers. We discuss common coding idioms and relevant applications to reactive scenarios, including incremental computation, observer design pattern, data structure repair, and software visualization. The performance of our implementation is compared to problem-specific change propagation algorithms, as well as to language-centric approaches such as self-adjusting computation and subject/observer communication mechanisms, showing that the proposed approach is efficient in practice.
暂无评论