Abstract
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 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, 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.
- Martín Abadi, Tim Harris, and Mojtaba Mehrara. 2009. Transactional Memory with Strong Atomicity Using Off-the-Shelf Memory Protection Hardware. In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'09). 185--196. Google ScholarDigital Library
- Robin Abraham, Margaret M. Burnett, and Martin Erwig. 2008. Spreadsheet Programming. In Wiley Encyclopedia of Computer Science and Engineering. John Wiley & Sons, Inc.Google Scholar
- Umut A. Acar. 2009. Self-Adjusting Computation: (An Overview). In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM'09). 1--6. Google ScholarDigital Library
- Umut A. Acar, Amal Ahmed, and Matthias Blume. 2008. Imperative Self-Adjusting Computation. In POPL, George C. Necula and Philip Wadler (Eds.). ACM, 309--322. Google ScholarDigital Library
- Umut A. Acar, Guy E. Blelloch, and Robert Harper. 2006a. Adaptive Functional Programming. ACM Transactions on Programming Languages and Systems 28, 6 (2006), 990--1034. Google ScholarDigital Library
- Umut A. Acar, Guy E. Blelloch, Matthias Blume, and Kanat Tangwongsan. 2006b. An Experimental Analysis of Self-Adjusting Computation. In Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation (PLDI'06). 96--107. Google ScholarDigital Library
- Umut A. Acar, Guy E. Blelloch, Ruy Ley-Wild, Kanat Tangwongsan, and Duru Türkoglu. 2010. Traceable Data Types for Self-Adjusting Computation. In Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation (PLDI'10). 483--496. Google ScholarDigital Library
- Umut A. Acar, Matthias Blume, and Jacob Donham. 2013. A Consistent Semantics of Self-Adjusting Computation. Journal of Functional Programming 23, 3 (2013), 249--292.Google ScholarCross Ref
- Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall. Google ScholarDigital Library
- Bowen Alpern, Roger Hoover, Barry K. Rosen, Peter F. Sweeney, and F. Kenneth Zadeck. 1990. Incremental Evaluation of Computational Circuits. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'90). 32--42. Google ScholarDigital Library
- Krzysztof R. Apt. 2003. Principles of Constraint Programming. Cambridge University Press. Google ScholarDigital Library
- Richard Bellmann. 1958. On a Routing Problem. Quarterly Applied Mathematics 16, 1 (1958), 87--90.Google ScholarCross Ref
- Christian Bessiere. 2006. Constraint Propagation. In Handbook of Constraint Programming, F. Rossi, P. van Beek, and T. Walsh (Eds.). Elsevier.Google Scholar
- Peter A. Blume. 2007. The LabVIEW Style Book. Prentice Hall.Google Scholar
- Alan Borning. 1981. The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory. ACM Transactions on Programming Languages and Systems 3, 4 (1981), 353--387. Google ScholarDigital Library
- Frdric Boussinot and Jean-Ferdy Susini. 1998. The SugarCubes Tool Box: A Reactive Java Framework. Software: Practice and Experience 28, 14 (1998), 1531--1550. Google ScholarDigital Library
- Paul Caspi, Daniel Pilaud, Nicolas Halbwachs, and John Plaice. 1987. Lustre, a Declarative Language for Programming Synchronous Systems. In POPL. 178--188. Google ScholarDigital Library
- Craig Chambers, Bill Harrison, and John Vlissides. 2000. A Debate on Language and Tool Support for Design Patterns. In POPL. 277--289. Google ScholarDigital Library
- Yan Chen, Joshua Dunfield, and Umut A. Acar. 2012. Type-directed Automatic Incrementalization. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 299--310. Google ScholarDigital Library
- Gregory H. Cooper and Shriram Krishnamurthi. 2006. Embedding Dynamic Dataflow in a Call-by-Value Language. In ESOP. 294--308. Google ScholarDigital Library
- Antony Courtney. 2001. Frappé: Functional Reactive Programming in Java. In PADL. 29--44. Google ScholarDigital Library
- Patrick Cousot and Radhia Cousot. 1977. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In POPL. 238--252. Google ScholarDigital Library
- Pierluigi Crescenzi, Camil Demetrescu, Irene Finocchi, and Rossella Petreschi. 2000. Reversible Execution and Visualization of Programs with Leonardo. Journal of Visual Languages and Computing 11, 2 (2000), 125--150. Google ScholarDigital Library
- Alan J. Demers, Thomas W. Reps, and Tim Teitelbaum. 1981. Incremental Evaluation for Attribute Grammars with Application to Syntax-Directed Editors. In POPL. 105--116. Google ScholarDigital Library
- Camil Demetrescu. 2001. Fully Dynamic Algorithms for Path Problems on Directed Graphs. Ph.D. Dissertation. Sapienza University of Rome.Google Scholar
- Camil Demetrescu and Irene Finocchi. 2001. Smooth Animation of Algorithms in a Declarative Framework. Journal of Visual Languages and Computing 12, 3 (2001), 253--281. Google ScholarDigital Library
- Camil Demetrescu and Irene Finocchi. 2006. A Data-Driven Graphical Toolkit for Software Visualization. In Proceedings of the ACM 2006 Symposium on Software Visualization, Brighton, UK, September 4--5, 2006. ACM, 57--66. Google ScholarDigital Library
- Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano. 2005. Dynamic Graphs. In Handbook on Data Structures and Applications, D. Mehta and S. Sahni (Eds.). CRC Press.Google Scholar
- Camil Demetrescu, Irene Finocchi, and Andrea Ribichini. 2011. Reactive Imperative Programming with Dataflow Constraints. In Proceedings of the 26th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'11). ACM, 407--426. Google ScholarDigital Library
- Camil Demetrescu, Irene Finocchi, and John T. Stasko. 2001. Specifying Algorithm Visualizations: Interesting Events or State Mapping? In Software Visualization. Lecture Notes in Computer Science, Vol. 2269. Springer, 16--30. Google ScholarDigital Library
- C. Demetrescu, A. V. Goldberg, and D. S. Johnson. 2009. The Shortest Path Problem: Ninth DIMACS Implementation Challenge. American Mathematical Society.Google Scholar
- Brian Demsky and Martin Rinard. 2003. Automatic Detection and Repair of Errors in Data Structures. In Proceedings of the Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'03). 78--95. Google ScholarDigital Library
- Jack B. Dennis, John B. Fosseen, and John P. Linderman. 1974. Data Flow Schemas. In Proceedings of the International Symposium on Theoretical Programming, Andrei Ershov and Valery A. Nepomniaschy (Eds.), Vol. 5. Springer, Berlin, 187--216. DOI:http://dx.doi.org/10.1007/3-540-06720-5_15Google ScholarCross Ref
- Stephan Diehl. 2007. Software Visualization: Visualizing the Structure, Behaviour, and Evolution of Software. Springer. Google ScholarDigital Library
- Paul Dietz and Daniel Sleator. 1987. Two Algorithms for Maintaining Order in a List. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC'87). 365--372. Google ScholarDigital Library
- Conal Elliott and Paul Hudak. 1997. Functional Reactive Animation. In Proceedings of the 1997 ACM SIGPLAN International Conference on Functional Programming (ICFP'97). 263--273. Google ScholarDigital Library
- Alan Ezust and Paul Ezust. 2006. An Introduction to Design Patterns in C++ with Qt 4. Prentice Hall. Google ScholarDigital Library
- Raphael A. Finkel. 1996. Advanced Programming Language Design. Addison-Wesley, Menlo Park, CA. Google ScholarDigital Library
- Bjorn Freeman-Benson and Alan Borning. 1992. Integrating Constraints with an Object-Oriented Language. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP'92). 268--286. Google ScholarDigital Library
- Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. 1994. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley. Google ScholarDigital Library
- Michael Gorbovitski, Tom Rothamel, Yanhong A. Liu, and Scott D. Stoller. 2005. Implementing Incrementalization Across Object Abstraction. In Companion to the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications. ACM, 112--113. Google ScholarDigital Library
- Thorsten Groetker, Stan Liao, Grant Martin, and Stuart Swan. 2002. System Design with SystemC. Kluwer Academic. Google ScholarDigital Library
- Paul Le Guernic, Albert Benveniste, Patricia Bournai, and Thierry Gautier. 1986. SIGNAL - A Data Flow-Oriented Language for Signal Processing. IEEE Transactions on Acoustics, Speech and Signal Processing 34, 2 (1986), 362--374.Google ScholarCross Ref
- Matthew Hammer, Umut A. Acar, and Yan Chen. 2009. CEAL: A C-based Language for Self-Adjusting Computation. In Proceedings of the ACM SIGPLAN 2009 Conference on Programming Language Design and Implementation (PLDI'09). 25--37. Google ScholarDigital Library
- Matthew A. Hammer, Georg Neis, Yan Chen, and Umut A. Acar. 2011. Self-Adjusting Stack Machines. In OOPSLA, Cristina Videira Lopes and Kathleen Fisher (Eds.). ACM, 753--772. Google ScholarDigital Library
- Christian Holzbaur. 1992. Metastructures vs. Attributed Variables in the Context of Extensible Unification - Applied for the Implementation of CLP Languages. In Proceedings of the International Symposium on Programming Language Implementation and Logic Programming (PLILP'92). 260--268. Google ScholarDigital Library
- Christian Holzbaur and Thom Frühwirth. 1999. Compiling Constraint Handling Rules into Prolog with Attributed Variables. In Proceedings of the International Conference on Principles and Practice of Declarative Programming (PPDP'99). 117--133. Google ScholarDigital Library
- Roger Hoover. 1987. Incremental Graph Evaluation. Ph.D. Dissertation. Department of Computer Science, Cornell University, Ithaca, NY. Google ScholarDigital Library
- Paul Hudak, Simon Peyton Jones, and Philip Wadler (Eds.). 1992. Report on the Programming Language Haskell, a Non-Strict Purely Functional Language (Version 1.2). ACM SIGPLAN Notices 27, 5 (1992). Google ScholarDigital Library
- Scott E. Hudson. 1991. Incremental Attribute Evaluation: A Flexible Algorithm for Lazy Update. ACM Transactions on Programming Languages and Systems 13, 3 (1991), 315--341. Google ScholarDigital Library
- Daniel Ignatoff, Gregory H. Cooper, and Shriram Krishnamurthi. 2006. Crossing State Lines: Adapting Object-Oriented Frameworks to Functional Reactive Languages. In Proceedings of the 8th International Symposium on Functional and Logic Programming (FLOPS'06). 259--276. Google ScholarDigital Library
- ISO. 2007. The C Programming Language: ISO/IEC 9899:1999 Cor. 3:2007(E) - Technical Corrigendum 3. (2007).Google Scholar
- Richard M. Karp and Raymond E. Miller. 1966. Properties of a Model for Parallel Computations: Determinancy, Termination, Queueing. SIAM Journal of Applied Mathematics 14, 6 (1966), 1390--1411.Google ScholarDigital Library
- Alan Kay. 1984. Computer Software. Scientific American 251, 3 (1984), 191--207.Google ScholarCross Ref
- Donald E. Knuth. 1968. Semantics of Context-Free Languages. Theory of Computing Systems 2, 2 (1968), 127--145.Google Scholar
- Ruy Ley-Wild, Umut A. Acar, and Guy E. Blelloch. 2012. Non-Monotonic Self-Adjusting Computation. In Proceedings of the 21st European Symposium on Programming (ESOP'12), Helmut Seidl (Ed.), Vol. 7211. Springer, 476--496. Google ScholarDigital Library
- Yanhong A. Liu, Scott D. Stoller, Michael Gorbovitski, Tom Rothamel, and Yanni Ellen Liu. 2005. Incrementalization Across Object Abstraction. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM, 473--486. Google ScholarDigital Library
- Yanhong A. Liu, Scott D. Stoller, and Tim Teitelbaum. 1998. Static Caching for Incremental Computation. ACM Transactions in Programming Languages and Systems 20, 3 (1998), 546--585. Google ScholarDigital Library
- Muhammad Zubair Malik, Khalid Ghori, Bassem Elkarablieh, and Sarfraz Khurshid. 2009. A Case for Automated Debugging Using Data Structure Repair. In Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering (ASE'09). 620--624. Google ScholarDigital Library
- Louis Mandel and Marc Pouzet. 2005. ReactiveML, a Reactive Extension to ML. In Proceedings of the International Symposium on Symposium on Principles and Practice of Declarative Programming (PPDP'05). 82--93. Google ScholarDigital Library
- Guillaume Marceau, Gregory H. Cooper, Jonathan P. Spiro, Shriram Krishnamurthi, and Steven P. Reiss. 2007. The Design and Implementation of a Dataflow Language for Scriptable Debugging. Automated Software Engineering 14, 1 (2007), 59--86. Google ScholarDigital Library
- Leo A. Meyerovich, Arjun Guha, Jacob Baskin, Gregory H. Cooper, Michael Greenberg, Aleks Bromfield, and Shriram Krishnamurthi. 2009. Flapjax: A Programming Language for Ajax Applications. In Proceedings of the 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications (OOPSLA'09). 1--20. Google ScholarDigital Library
- Mauro Mosconi and Marco Porta. 2000. Iteration Constructs in Data-Flow Visual Programming Languages. Computer Languages 26, 2--4 (2000), 67--104. Google ScholarDigital Library
- Brad A. Myers. 1990. Garnet: Comprehensive Support for Graphical, Highly-Interactive User Interfaces. IEEE Computer 23 (1990). Google ScholarDigital Library
- Brad A. Myers, Richard G. McDaniel, Robert C. Miller, Alan S. Ferrency, Andrew Faulring, Bruce D. Kyle, Andrew Mickish, Alex Klimovitski, and Patrick Doane. 1997. The Amulet Environment: New Models for Effective User Interface Software Development. IEEE Transactions on Software Engineering 23, 6 (1997), 347--365. Google ScholarDigital Library
- Henrik Nilsson, Antony Courtney, and John Peterson. 2002. Functional Reactive Programming, Continued. In Proceedings of the 2002 ACM SIGPLAN Workshop on Haskell (HASKELL'02). 51--64. Google ScholarDigital Library
- Ronald A. Olsson, Richard H. Crawford, and W. Wilson Ho. 1991. A Dataflow Approach to Event-Based Debugging. Software: Practice and Experience 21, 2 (1991), 209--229. Google ScholarDigital Library
- Sanjiva Prasad and S. Arun-Kumar. 2002. An Introduction to Operational Semantics. In Compiler Design Handbook: Optimizations and Machine Code. CRC Press, Boca Raton, FL, 841--890.Google Scholar
- Blaine A. Price, Ronald M. Baecker, and Ian S. Small. 1993. A Principled Taxonomy of Software Visualization. Journal of Visual Languages and Computing 4, 3 (1993), 211--266.Google ScholarCross Ref
- William Pugh and Tim Teitelbaum. 1989. Incremental Computation via Function Caching. In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, 315--328. Google ScholarDigital Library
- Ganesan Ramalingam and Thomas Reps. 1996. An Incremental Algorithm for a Generalization of the Shortest-Path Problem. Journal of Algorithms 21, 2 (1996), 267--305. Google ScholarDigital Library
- Thomas W. Reps, Carla Marceau, and Tim Teitelbaum. 1986. Remote Attribute Updating for Language-Based Editors. In Proceedings of the 13th Annual ACM Symposium on Principles of Programming Languages (POPL'86). 1--13. Google ScholarDigital Library
- Thomas W. Reps, Tim Teitelbaum, and Alan J. Demers. 1983. Incremental Context-Dependent Analysis for Language-Based Editors. ACM Transactions on Programming Languages and Systems 5, 3 (1983), 449--477. Google ScholarDigital Library
- Gruia-Catalin Roman, Kenneth C. Cox, C. Donald Wilcox, and Jerome Y. Plun. 1992. Pavane: A System for Declarative Visualization of Concurrent Computations. Journal of Visual Languages and Computing 3, 2 (1992), 161--193.Google ScholarCross Ref
- Ajeet Shankar and Rastislav Bodík. 2007. DITTO: Automatic Incrementalization of Data Structure Invariant Checks (in Java). In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 310--319. Google ScholarDigital Library
- John T. Stasko, John Domingue, Mark H. Brown, and Blaine A. Price. 1997. Software Visualization. MIT Press, Cambridge, MA. Google ScholarDigital Library
- U.S. Census Bureau. 2002. UA Census 2000 TIGER/Line Files. U.S. Census Bureau. Washington, DC. Retrieved from http://www.census.gov/geo/www/tiger/.Google Scholar
- Bradley T. Vander Zanden and Richard Halterman. 2001. Using Model Dataflow Graphs to Reduce the Storage Requirements of Constraints. ACM Transactions on Computer-Human Interaction 8, 3 (2001), 223--265. Google ScholarDigital Library
- Bradley T. Vander Zanden, Richard Halterman, Brad A. Myers, Rich McDaniel, Rob Miller, Pedro Szekely, Dario A. Giuse, and David Kosbie. 2001. Lessons Learned About One-Way, Dataflow Constraints in the Garnet and Amulet Graphical Toolkits. ACM Transactions on Programming Languages and Systems 23, 6 (2001), 776--796. Google ScholarDigital Library
- Bradley T. Vander Zanden, Richard Halterman, Brad A. Myers, Rob Miller, Pedro Szekely, Dario A. Giuse, David Kosbie, and Rich McDaniel. 2005. Lessons Learned from Programmers' Experiences with One-way Constraints. Software: Practice and Experience 35, 13 (2005), 1275--1298. Google ScholarDigital Library
- Zhanyong Wan and Paul Hudak. 2000. Functional Reactive Programming from First Principles. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI'00). 242--252. Google ScholarDigital Library
- Neng-Fa Zhou. 2006. Programming Finite-Domain Constraint Propagators in Action Rules. Theory and Practice of Logic Programming 6 (2006), 483--507. Google ScholarDigital Library
Index Terms
- Reactive Imperative Programming with Dataflow Constraints
Recommendations
Reactive imperative programming with dataflow constraints
OOPSLA '11Dataflow 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 ...
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