{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:53Z","timestamp":1750306733023,"version":"3.41.0"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,11,17]],"date-time":"2014-11-17T00:00:00Z","timestamp":1416182400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2015,1,20]]},"abstract":"<jats:p>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 \u201creactive.\u201d 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.<\/jats:p>","DOI":"10.1145\/2623200","type":"journal-article","created":{"date-parts":[[2014,11,18]],"date-time":"2014-11-18T14:21:03Z","timestamp":1416320463000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Reactive Imperative Programming with Dataflow Constraints"],"prefix":"10.1145","volume":"37","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irene","family":"Finocchi","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Ribichini","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,11,17]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/1504176.1504203"},{"volume-title":"Wiley Encyclopedia of Computer Science and Engineering","author":"Abraham Robin","unstructured":"Robin Abraham, Margaret M. Burnett, and Martin Erwig. 2008. Spreadsheet Programming. In Wiley Encyclopedia of Computer Science and Engineering. John Wiley & Sons, Inc.","key":"e_1_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/1480945.1480946"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/1328438.1328476"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1186632.1186634"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/1133981.1133993"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/1806596.1806650"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1017\/S0956796813000099"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.5555\/137406"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.5555\/320176.320180"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.5555\/1237975"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1090\/qam\/102435"},{"volume-title":"Handbook of Constraint Programming","author":"Bessiere Christian","unstructured":"Christian Bessiere. 2006. Constraint Propagation. In Handbook of Constraint Programming, F. Rossi, P. van Beek, and T. Walsh (Eds.). Elsevier.","key":"e_1_2_1_13_1"},{"volume-title":"The LabVIEW Style Book","author":"Blume Peter A.","unstructured":"Peter A. Blume. 2007. The LabVIEW Style Book. Prentice Hall.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/357146.357147"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1002\/(SICI)1097-024X(19981210)28:14%3C1531::AID-SPE218%3E3.0.CO;2-U"},{"doi-asserted-by":"publisher","unstructured":"Paul Caspi Daniel Pilaud Nicolas Halbwachs and John Plaice. 1987. Lustre a Declarative Language for Programming Synchronous Systems. In POPL. 178--188. 10.1145\/41625.41641","key":"e_1_2_1_17_1","DOI":"10.1145\/41625.41641"},{"doi-asserted-by":"publisher","unstructured":"Craig Chambers Bill Harrison and John Vlissides. 2000. A Debate on Language and Tool Support for Design Patterns. In POPL. 277--289. 10.1145\/325694.325731","key":"e_1_2_1_18_1","DOI":"10.1145\/325694.325731"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/2254064.2254100"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/11693024_20"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/645771.667929"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/512950.512973"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1006\/jvlc.1999.0143"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/567532.567544"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1006\/jvlc.2001.0208"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/1148493.1148502"},{"key":"e_1_2_1_28_1","volume-title":"Italiano","author":"Demetrescu Camil","year":"2005","unstructured":"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."},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/2048066.2048100"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.5555\/647382.724793"},{"doi-asserted-by":"crossref","unstructured":"C. Demetrescu A. V. Goldberg and D. S. Johnson. 2009. The Shortest Path Problem: Ninth DIMACS Implementation Challenge. American Mathematical Society.","key":"e_1_2_1_31_1","DOI":"10.1090\/dimacs\/074"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/949305.949314"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1007\/3-540-06720-5_15"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.5555\/1209814"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/28395.28434"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/258948.258973"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.5555\/1177265"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.5555\/560658"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.5555\/646150.679346"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.5555\/186897"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1145\/1094855.1094889"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.5555\/515361"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1109\/TASSP.1986.1164809"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1145\/1542476.1542480"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1145\/2048066.2048124"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.5555\/646448.692447"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.5555\/645815.758228"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1145\/130697.130699"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.1145\/117009.117012"},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1007\/11737414_18"},{"unstructured":"ISO. 2007. The C Programming Language: ISO\/IEC 9899:1999 Cor. 3:2007(E) - Technical Corrigendum 3. (2007).","key":"e_1_2_1_52_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_53_1","DOI":"10.1137\/0114108"},{"doi-asserted-by":"publisher","key":"e_1_2_1_54_1","DOI":"10.1038\/scientificamerican0984-52"},{"key":"e_1_2_1_55_1","first-page":"127","article-title":"Semantics of Context-Free Languages","volume":"2","author":"Knuth Donald E.","year":"1968","unstructured":"Donald E. Knuth. 1968. Semantics of Context-Free Languages. Theory of Computing Systems 2, 2 (1968), 127--145.","journal-title":"Theory of Computing Systems"},{"doi-asserted-by":"publisher","key":"e_1_2_1_56_1","DOI":"10.1007\/978-3-642-28869-2_24"},{"doi-asserted-by":"publisher","key":"e_1_2_1_57_1","DOI":"10.1145\/1094811.1094848"},{"doi-asserted-by":"publisher","key":"e_1_2_1_58_1","DOI":"10.1145\/291889.291895"},{"doi-asserted-by":"publisher","key":"e_1_2_1_59_1","DOI":"10.1109\/ASE.2009.92"},{"doi-asserted-by":"publisher","key":"e_1_2_1_60_1","DOI":"10.1145\/1069774.1069782"},{"doi-asserted-by":"publisher","key":"e_1_2_1_61_1","DOI":"10.1007\/s10515-006-0003-z"},{"doi-asserted-by":"publisher","key":"e_1_2_1_62_1","DOI":"10.1145\/1640089.1640091"},{"doi-asserted-by":"publisher","key":"e_1_2_1_63_1","DOI":"10.1016\/S0096-0551(01)00009-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_64_1","DOI":"10.1109\/2.60882"},{"doi-asserted-by":"publisher","key":"e_1_2_1_65_1","DOI":"10.1109\/32.601073"},{"doi-asserted-by":"publisher","key":"e_1_2_1_66_1","DOI":"10.1145\/581690.581695"},{"doi-asserted-by":"publisher","key":"e_1_2_1_67_1","DOI":"10.1002\/spe.4380210207"},{"doi-asserted-by":"crossref","unstructured":"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.","key":"e_1_2_1_68_1","DOI":"10.1201\/9781420040579.ch22"},{"doi-asserted-by":"publisher","key":"e_1_2_1_69_1","DOI":"10.1006\/jvlc.1993.1015"},{"doi-asserted-by":"publisher","key":"e_1_2_1_70_1","DOI":"10.1145\/75277.75305"},{"doi-asserted-by":"publisher","key":"e_1_2_1_71_1","DOI":"10.1006\/jagm.1996.0046"},{"doi-asserted-by":"publisher","key":"e_1_2_1_72_1","DOI":"10.1145\/512644.512645"},{"doi-asserted-by":"publisher","key":"e_1_2_1_73_1","DOI":"10.1145\/2166.357218"},{"doi-asserted-by":"publisher","key":"e_1_2_1_74_1","DOI":"10.1016\/1045-926X(92)90014-D"},{"doi-asserted-by":"publisher","key":"e_1_2_1_75_1","DOI":"10.1145\/1250734.1250770"},{"doi-asserted-by":"publisher","key":"e_1_2_1_76_1","DOI":"10.5555\/550196"},{"volume-title":"UA Census 2000 TIGER\/Line Files","author":"U.S. Census Bureau","unstructured":"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\/.","key":"e_1_2_1_77_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_78_1","DOI":"10.1145\/502907.502910"},{"doi-asserted-by":"publisher","key":"e_1_2_1_79_1","DOI":"10.1145\/506315.506318"},{"doi-asserted-by":"publisher","key":"e_1_2_1_80_1","DOI":"10.1002\/spe.v35:13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_81_1","DOI":"10.1145\/349299.349331"},{"doi-asserted-by":"publisher","key":"e_1_2_1_82_1","DOI":"10.1017\/S1471068405002590"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2623200","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2623200","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:46Z","timestamp":1750231186000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2623200"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,17]]},"references-count":80,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1,20]]}},"alternative-id":["10.1145\/2623200"],"URL":"https:\/\/doi.org\/10.1145\/2623200","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2014,11,17]]},"assertion":[{"value":"2012-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}