{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T21:35:53Z","timestamp":1769895353825,"version":"3.49.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>Fast analysis response times in IDEs are essential for a good editor experience.  \nIncremental type-checking can provide that in a scalable fashion.  \nHowever, existing techniques are not reusable between languages.  \nMoreover, mutual and dynamic dependencies preclude traditional approaches to incrementality.  \nThis makes finding automatic approaches to incremental type-checking a challenging but important open question.<\/jats:p>\n          <jats:p>In this paper, we present a technique that automatically derives incremental type-checkers from type system specifications written in the Statix meta-DSL.  \nWe use name resolution queries in scope graphs (a generic model of name binding embedded in Statix) to derive dependencies between compilation units.  \nA novel query confirmation algorithm finds queries for which the answer changed due to an edit in the program.  \nOnly units with such queries require reanalysis.  \nThe effectiveness of this algorithm is improved by  \n(1) splitting the type-checking task into a context-free and a context-sensitive part, and  \n(2) reusing a generic mechanism to resolve mutual dependencies.  \nThis automatically yields incremental type-checkers for any Statix specification.<\/jats:p>\n          <jats:p>Compared to non-incremental parallel execution, we achieve speedups up to 147x on synthetic benchmarks, and up to 21x on real-world projects, with initial overheads below 10%.  \nThis suggests that our framework can provide efficient incremental type-checking to the wide range of languages supported by Statix.<\/jats:p>","DOI":"10.1145\/3563303","type":"journal-article","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T20:23:35Z","timestamp":1667247815000},"page":"424-448","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Incremental type-checking for free: using scope graphs to derive incremental type-checkers"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1818-4245","authenticated-orcid":false,"given":"Aron","family":"Zwaan","sequence":"first","affiliation":[{"name":"Delft University of Technology, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5117-0921","authenticated-orcid":false,"given":"Hendrik","family":"van Antwerpen","sequence":"additional","affiliation":[{"name":"Delft University of Technology, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7384-3370","authenticated-orcid":false,"given":"Eelco","family":"Visser","sequence":"additional","affiliation":[{"name":"Delft University of Technology, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,31]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"ACTORS - a model of concurrent computation in distributed systems","author":"Agha Gul A.","unstructured":"Gul A. Agha . 1990. ACTORS - a model of concurrent computation in distributed systems . MIT Press . isbn:978-0-262-01092-4 Gul A. Agha. 1990. ACTORS - a model of concurrent computation in distributed systems. MIT Press. isbn:978-0-262-01092-4"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48483-3_1"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/571157.571177"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004257"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568243"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-20652-9_7"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263735"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133872"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/567532.567544"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1999.782606"},{"key":"e_1_2_2_12_1","unstructured":"Eclipse. 2021. JDT Core Component. https:\/\/www.eclipse.org\/jdt\/core\/ \t\t\t\t  Eclipse. 2021. JDT Core Component. https:\/\/www.eclipse.org\/jdt\/core\/"},{"key":"e_1_2_2_13_1","volume-title":"A Framework for Cut-Off Incremental Recompilation and Inter-Module Optimization","author":"Elsman Martin","unstructured":"Martin Elsman . 2008. A Framework for Cut-Off Incremental Recompilation and Inter-Module Optimization . IT University of Copenhagen , Copenhagen . 11. https:\/\/elsman.com\/pdf\/sepcomp_tr.pdf Martin Elsman. 2008. A Framework for Cut-Off Incremental Recompilation and Inter-Module Optimization. IT University of Copenhagen, Copenhagen. 11. https:\/\/elsman.com\/pdf\/sepcomp_tr.pdf"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814277"},{"key":"e_1_2_2_15_1","unstructured":"Sterling Greene. 2015. Introducing Incremental Build Support. https:\/\/blog.gradle.org\/introducing-incremental-build-support \t\t\t\t  Sterling Greene. 2015. Introducing Incremental Build Support. https:\/\/blog.gradle.org\/introducing-incremental-build-support"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1449814.1449858"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372123"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594324"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869459.1869497"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3238147.3238196"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814189.2817272"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/174675.176926"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46425-5_17"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/567067.567092"},{"key":"e_1_2_2_25_1","volume-title":"Renaming for Everyone: Language-parametric Renaming in Spoofax. Master\u2019s thesis","author":"Misteli Phil","unstructured":"Phil Misteli . 2021. Renaming for Everyone: Language-parametric Renaming in Spoofax. Master\u2019s thesis . Delft University of Technology . http:\/\/resolver.tudelft.nl\/uuid:60f5710d-445d-4583-957c-79d6afa45be5 Available at Phil Misteli. 2021. Renaming for Everyone: Language-parametric Renaming in Spoofax. Master\u2019s thesis. Delft University of Technology. http:\/\/resolver.tudelft.nl\/uuid:60f5710d-445d-4583-957c-79d6afa45be5 Available at"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46669-8_9"},{"key":"e_1_2_2_27_1","unstructured":"OpenJDK. 2021. Java Microbenchmark Harness (JMH). https:\/\/openjdk.java.net\/projects\/code-tools\/jmh\/ \t\t\t\t  OpenJDK. 2021. Java Microbenchmark Harness (JMH). https:\/\/openjdk.java.net\/projects\/code-tools\/jmh\/"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428195"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527329"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158710"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428248"},{"key":"e_1_2_2_32_1","unstructured":"Leonid Ryzhyk and Mihai Budiu. 2019. Differential Datalog.. http:\/\/budiu.info\/work\/ddlog.pdf \t\t\t\t  Leonid Ryzhyk and Mihai Budiu. 2019. Differential Datalog.. http:\/\/budiu.info\/work\/ddlog.pdf"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158702"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159883"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454026"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970298"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236454.3236485"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365438.3410942"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276484"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2021.1"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02654-1_15"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7071393"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:10Z","timestamp":1750178290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":42,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3563303"],"URL":"https:\/\/doi.org\/10.1145\/3563303","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2022-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}