Abstract
Dataflow languages provide natural support for specifying constraints between objects in dynamic applications, where programs need to react efficiently to changes of their environment. Researchers have long investigated how to take advantage of dataflow constraints by embedding them into procedural languages. Previous mixed imperative/dataflow systems, however, require syntactic extensions or libraries of ad hoc data types for binding the imperative program to the dataflow solver. In this paper we propose a novel approach that smoothly combines the two paradigms without placing undue burden on the programmer. 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". Differently from previous approaches, 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 upon the values of other variables. The constraint solving 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, and data structure repair. The performance of our implementation is compared to ad hoc 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.
- M. Abadi, T. Harris, and M. Mehrara. Transactional Memory with Strong Atomicity Using Off-the-Shelf Memory Protection Hardware. In PPoPP, pages 185--196, 2009. Google ScholarDigital Library
- R. Abraham, M. M. Burnett, and M. Erwig. Spreadsheet Programming. In Wiley Encyclopedia of Computer Science and Engineering. John Wiley & Sons, Inc., 2008.Google Scholar
- U. A. Acar. Self-Adjusting Computation: (an Overview). In PEPM, pages 1--6, 2009. Google ScholarDigital Library
- U. A. Acar, G. E. Blelloch, M. Blume, and K. Tangwongsan. An Experimental Analysis of Self-Adjusting Computation. In PLDI, pages 96--107, 2006. Google ScholarDigital Library
- oglu}DBLP:conf/pldi/AcarBLTT10U. A. Acar, G. E. Blelloch, R. Ley-Wild, K. Tangwongsan, and D. Türkoglu. Traceable Data Types for Self-Adjusting Computation. In PLDI, pages 483--496, 2010. Google ScholarDigital Library
- B. Alpern, R. Hoover, B. K. Rosen, P. F. Sweeney, and F. K. Zadeck. Incremental Evaluation of Computational Circuits. In SODA, pages 32--42, 1990. Google ScholarDigital Library
- K. R. Apt. Principles of Constraint Programming. Cambridge University Press, 2003. Google ScholarDigital Library
- R. Bellmann. On a Routing Problem. Quarterly of Applied Mathematics, 16: 87--90, 1958.Google ScholarCross Ref
- C. Bessiere. Constraint Propagation. In F. Rossi, P. van Beek, and T. Walsh, editors, Handbook of Constraint Programming. 2006.Google Scholar
- P. A. Blume. The LabVIEW Style Book. Prentice Hall, 2007.Google Scholar
- A. Borning. The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory. ACM Transactions on Programming Languages and Systems, 3 (4): 353--387, 1981. Google ScholarDigital Library
- F. Boussinot and J.-F. Susini. The SugarCubes Tool Box: a Reactive Java Framework. Software: Practice and Experience, 28 (14): 1531--1550, 1998. Google ScholarDigital Library
- P. Caspi, P. Pilaud, N. Halbwachs, and J. Plaice. Lustre, a Declarative Language for Programming Synchronous Systems. In POPL, pages 178--188, 1987. Google ScholarDigital Library
- C. Chambers, B. Harrison, and J. Vlissides. A Debate on Language and Tool Support for Design Patterns. In POPL, pages 277--289, 2000. Google ScholarDigital Library
- G. H. Cooper and S. Krishnamurthi. Embedding Dynamic Dataflow in a Call-by-Value Language. In ESOP, pages 294--308, 2006. Google ScholarDigital Library
- A. Courtney. Frappé: Functional Reactive Programming in Java. In PADL, pages 29--44, 2001. Google ScholarDigital Library
- P. Cousot and R. Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In POPL, pages 238--252, 1977. Google ScholarDigital Library
- P. Crescenzi, C. Demetrescu, I. Finocchi, and R. Petreschi. Reversible Execution and Visualization of Programs with Leonardo. Journal of Visual Languages and Computing, 11 (2): 125--150, 2000.Google ScholarDigital Library
- A. J. Demers, T. W. Reps, and T. Teitelbaum. Incremental Evaluation for Attribute Grammars with Application to Syntax-Directed Editors. In POPL, pages 105--116, 1981. Google ScholarDigital Library
- C. Demetrescu. Fully Dynamic Algorithms for Path Problems on Directed Graphs. PhD thesis, Sapienza University of Rome, 2001.Google Scholar
- C. Demetrescu, I. Finocchi, and G. Italiano. Handbook on Data Structures and Applications, chapter 36: Dynamic Graphs. D. Mehta and S. Sahni (eds.), CRC Press, 2005.Google Scholar
- C. Demetrescu, A. V. Goldberg, and D. S. Johnson, editors. The Shortest Path Problem: Ninth DIMACS Implementation Challenge. American Mathematical Society, 2009.Google ScholarCross Ref
- C. Demetrescu, I. Finocchi, and A. Ribichini. Reactive Imperative Programming with Dataflow Constraints. Technical Report arXiv:1104.2293, April 2011.Google ScholarDigital Library
- B. Demsky and M. Rinard. Automatic Detection and Repair of Errors in Data Structures. In OOPSLA, pages 78--95, 2003. Google ScholarDigital Library
- C. Elliott and P. Hudak. Functional Reactive Animation. In ICFP, pages 263--273, 1997. Google ScholarDigital Library
- A. Ezust and P. Ezust. An Introduction to Design Patterns in C+ with Qt 4. Prentice Hall, 2006. Google ScholarDigital Library
- B. Freeman-Benson and A. Borning. Integrating Constraints with an Object-Oriented Language. In ECOOP, pages 268--286, 1992. Google ScholarDigital Library
- T. Groetker, S. Liao, G. Martin, and S. Swan. System Design with SystemC. Kluwer Academic Publishers, 2002. Google ScholarDigital Library
- P. L. Guernic, A. Benveniste, P. Bournai, and T. Gautier. SIGNAL - A Data Flow-Oriented Language for Signal Processing. IEEE Transactions on Acoustics, Speech and Signal Processing, 34 (2): 362--374, 1986.Google ScholarCross Ref
- M. Hammer, U. A. Acar, and Y. Chen. CEAL: a C-based Language for Self-Adjusting Computation. In PLDI, pages 25--37, 2009. Google ScholarDigital Library
- C. Holzbaur. Metastructures vs. Attributed Variables in the Context of Extensible Unification - Applied for the Implementation of CLP Languages. In PLILP, pages 260--268, 1992. Google ScholarDigital Library
- C. Holzbaur and T. Frühwirth. Compiling Constraint Handling Rules into Prolog with Attributed Variables. In PPDP, pages 117--133. 1999. Google ScholarDigital Library
- P. Hudak, S. Peyton Jones, and P. Wadler (editors). Report on the Programming Language Haskell, A Non-strict Purely Functional Language (Version 1.2). ACM SIGPLAN Notices, 27 (5), 1992. Google ScholarDigital Library
- S. E. Hudson. Incremental Attribute Evaluation: A Flexible Algorithm for Lazy Update. ACM Transactions on Programming Languages and Systems, 13 (3): 315--341, 1991. Google ScholarDigital Library
- D. Ignatoff, G. H. Cooper, and S. Krishnamurthi. Crossing State Lines: Adapting Object-Oriented Frameworks to Functional Reactive Languages. In FLOPS, pages 259--276, 2006. Google ScholarDigital Library
- A. Kay. Computer software. Scientific American, 251 (3): 191--207, 1984.Google ScholarCross Ref
- D. E. Knuth. Semantics of Context-free Languages. Theory of Computing Systems, 2 (2): 127--145, 1968.Google Scholar
- M. Z. Malik, K. Ghori, B. Elkarablieh, and S. Khurshid. A Case for Automated Debugging Using Data Structure Repair. In ASE, pages 620--624, 2009. Google ScholarDigital Library
- L. Mandel and M. Pouzet. ReactiveML, a Reactive Extension to ML. In PPDP, pages 82--93, 2005. Google ScholarDigital Library
- L. A. Meyerovich, A. Guha, J. Baskin, G. H. Cooper, M. Greenberg, A. Bromfield, and S. Krishnamurthi. Flapjax: a Programming Language for Ajax Applications. In OOPSLA, pages 1--20, 2009. Google ScholarDigital Library
- B. A. Myers, R. G. McDaniel, R. C. Miller, A. S. Ferrency, A. Faulring, B. D. Kyle, A. Mickish, A. Klimovitski, and P. Doane. The Amulet Environment: New Models for Effective User Interface Software Development. IEEE Transactions on Software Engineering, 23 (6): 347--365, 1997. Google ScholarDigital Library
- H. Nilsson, A. Courtney, and J. Peterson. Functional Reactive Programming, Continued. In HASKELL, pages 51--64, 2002. Google ScholarDigital Library
- S. Prasad and S. Arun-Kumar. An Introduction to Operational Semantics. In Compiler Design Handbook: Optimizations and Machine Code, pages 841--890. CRC Press, Boca Raton, 2002.Google Scholar
- G. Ramalingam and T. Reps. An Incremental Algorithm for a Generalization of the Shortest-Path Problem. Journal of Algorithms, 21 (2): 267 -- 305, 1996. Google ScholarDigital Library
- U.S. Census Bureau, Washington, DC. UA Census 2000 TIGER/Line Files. http://www.census.gov/geo/www/tiger/, 2002.Google Scholar
- B. T. Vander Zanden, R. Halterman, B. A. Myers, R. McDaniel, R. Miller, P. Szekely, D. A. Giuse, and D. Kosbie. Lessons Learned about One-Way, Dataflow Constraints in the Garnet and Amulet Graphical Toolkits. ACM Transactions on Programming Languages and Systems, 23 (6): 776--796, 2001. Google ScholarDigital Library
- Z. Wan and P. Hudak. Functional Reactive Programming from First Principles. In PLDI, pages 242--252, 2000. Google ScholarDigital Library
- N.-F. Zhou. Programming Finite-Domain Constraint Propagators in Action Rules. Theory and Practice of Logic Programming, 6: 483--507, 2006. Google ScholarDigital Library
Index Terms
- Reactive imperative programming with dataflow constraints
Recommendations
Reactive Imperative Programming with Dataflow Constraints
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 ...
Reactive imperative programming with dataflow constraints
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applicationsDataflow languages provide natural support for specifying constraints between objects in dynamic applications, where programs need to react efficiently to changes of their environment. Researchers have long investigated how to take advantage of dataflow ...
Imperative self-adjusting computation
POPL '08Self-adjusting computation enables writing programs that can automatically and efficiently respond to changes to their data (e.g., inputs). The idea behind the approach is to store all data that can change over time in modifiable references and to let ...
Comments