{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T20:53:27Z","timestamp":1770238407930,"version":"3.49.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T00:00:00Z","timestamp":1723680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["1846350"],"award-info":[{"award-number":["1846350"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,8,15]]},"abstract":"<jats:p>\n                    Attheheartofefficientprogramanalysisimplementationsareincrementalsolutionstofixpointproblems.These solutions can be interpreted as the derivative of the underlying analysis function. Methods that describe how to systematically derive higher-order analyses from program semantics, such as Abstracting Abstract Machines,\n                    <jats:italic toggle=\"yes\">don\u2019t<\/jats:italic>\n                    shed light on how to efficiently\n                    <jats:italic toggle=\"yes\">implement<\/jats:italic>\n                    those analyses. In this paper, we explore complementary techniques to optimize the derivative computation towards deriving efficient implementations. In particular, we use static specializations (by partial evaluation and rewriting) and dynamic specializations (in the form of tracking dependencies during the fixpoint), yielding efficient incremental fixpoints. We present how these optimizations apply to an example analysis of continuation-passing-style \ud835\udf06-calculus, and describe how they pair particularly well with tunable and optimized workset-based fixpoint methods. We demonstrate the efficacy of this approach on a flow analysis for the Standard ML language, yielding an average speed-up of 56x over an existing fixpoint method for higher-order analyses from the literature.\n                  <\/jats:p>","DOI":"10.1145\/3674650","type":"journal-article","created":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T12:49:04Z","timestamp":1723726144000},"page":"728-755","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Deriving with Derivatives: Optimizing Incremental Fixpoints for Higher-Order Flow Analysis"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6922-9706","authenticated-orcid":false,"given":"Benjamin","family":"Quiring","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9201-6864","authenticated-orcid":false,"given":"David","family":"Van Horn","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,15]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"Serge Abiteboul Richard Hull and Victor Vianu. 1995. Foundations of Databases."},{"key":"e_1_3_1_3_1","unstructured":"Michael Arntzenius. 2017. Static differentiation of monotone fixed points. (2017). http:\/\/www.rntz.net\/files\/fixderiv.pdf"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371090"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4980-1_17"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61053-7_62"},{"key":"e_1_3_1_7_1","unstructured":"Hyunjun Eo. 2004. A Differential Fixpoint Iteration Method for Static Analysis Specifications.https:\/\/api.semanticscholar.org\/CorpusID:16795054"},{"key":"e_1_3_1_8_1","unstructured":"Hyunjun Eo and Kwangkeun Yi. 2002. An Improved Differential Fixpoint Iteration Method for Program Analysis. 285-301."},{"key":"e_1_3_1_9_1","first-page":"90","article-title":"Propagating Differences: An Efficient New Fixpoint Algorithm for Distributive Constraint Systems.","volume":"5","author":"Fecht Christian","year":"1998","unstructured":"Christian Fecht and Helmut Seidl. 1998. Propagating Differences: An Efficient New Fixpoint Algorithm for Distributive Constraint Systems. Nordic Journal of Computing 5, 90-104.","journal-title":"Nordic Journal of Computing"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837631"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500604"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/222124.222146"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908096"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187671.2187672"},{"key":"e_1_3_1_15_1","unstructured":"Anders M\u00f8ller and Michael I. Schwartzbach. 2023. Static Program Analysis. https:\/\/cs.au.dk\/~amoeller\/spa\/spa.pdf"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547645"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","unstructured":"Benjamin Quiring and David Van Horn. 2024. Experiments for \u201cDeriving with Derivatives: Optimizing Incremental Fixpoints for Higher-Order Flow Analysis\u201d. https:\/\/doi.org\/10.5281\/zenodo.11906121 10.5281\/zenodo.11906121","DOI":"10.5281\/zenodo.11906121"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_1_19_1","first-page":"91","volume-title":"Control-Flow Analysis of Higher-Order Languages, or Taming Lambda","author":"Shivers Olin","year":"1991","unstructured":"Olin Shivers. 1991. Control-Flow Analysis of Higher-Order Languages, or Taming Lambda. Ph. D. Dissertation. School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania. Technical Report CMU-CS-91-145."},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454044"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970298"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863553"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3674650","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3674650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T07:50:23Z","timestamp":1770191423000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3674650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,15]]},"references-count":21,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2024,8,15]]}},"alternative-id":["10.1145\/3674650"],"URL":"https:\/\/doi.org\/10.1145\/3674650","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,15]]},"assertion":[{"value":"2024-02-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}