{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T21:06:37Z","timestamp":1792184797476,"version":"4.4.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100011322","name":"General Motors of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100011322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>\n            A software analysis is a computer program that takes some representation of a software product as input and produces some useful information about that product as output. A software product line encompasses\n            <jats:italic>many<\/jats:italic>\n            software product variants, and thus existing analyses can be applied to each of the product variations individually, but not to the entire product line as a whole. Enumerating all product variants and analyzing them one by one is usually intractable due to the combinatorial explosion of the number of product variants with respect to product line features. Several software analyses (e.g., type checkers, model checkers, data flow analyses) have been redesigned\/re-implemented to support variability. This usually requires a lot of time and effort, and the variability-aware version of the analysis might have new errors\/bugs that do not exist in the original one.\n          <\/jats:p>\n          <jats:p>\n            Given an analysis program written in a functional language based on PCF, in this paper we present two approaches to transforming (lifting) it into a semantically equivalent variability-aware analysis. A light-weight approach (referred to as\n            <jats:italic>shallow lifting<\/jats:italic>\n            ) wraps the analysis program into a variability-aware version, exploring all combinations of its input arguments. Deep lifting, on the other hand, is a program rewriting mechanism where the syntactic constructs of the input program are rewritten into their variability-aware counterparts. Compositionally this results in an efficient program semantically equivalent to the input program, modulo variability.\n          <\/jats:p>\n          <jats:p>We present the correctness criteria for functional program lifting, together with correctness proof sketches of shallow lifting. We evaluate our approach on a set of program analyses applied to the BusyBox C-language product line.<\/jats:p>","DOI":"10.1145\/3428225","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:40:14Z","timestamp":1606261214000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Automatic and efficient variability-aware lifting of functional programs"],"prefix":"10.1145","volume":"4","author":[{"given":"Ramy","family":"Shahin","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marsha","family":"Chechik","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110265"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2013.6606594"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951948"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2491976"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628136.2628155"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2012.86"},{"key":"e_1_2_2_7_1","volume-title":"Software Product Lines: Practices and Patterns","author":"Clements Paul","unstructured":"Paul Clements and Linda Northrop . 2001. Software Product Lines: Practices and Patterns . Addison-Wesley Professional . Paul Clements and Linda Northrop. 2001. Software Product Lines: Practices and Patterns. Addison-Wesley Professional."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561347_28"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063239.2063245"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254103"},{"key":"e_1_2_2_11_1","first-page":"35","volume-title":"Proc. of GPCE'08","author":"K\u00e4stner Christian","year":"2008","unstructured":"Christian K\u00e4stner and Sven Apel . 2008 . Integrating Compositional and Annotative Approaches for Product Line Engineering .. In Proc. of GPCE'08 . 35 - 40 . Christian K\u00e4stner and Sven Apel. 2008. Integrating Compositional and Annotative Approaches for Product Line Engineering.. In Proc. of GPCE'08. 35-40."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2211616.2211617"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048128"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371083"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360602"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806819"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491437"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908096"},{"key":"e_1_2_2_19_1","volume-title":"C (","author":"Midtgaard Jan","year":"2015","unstructured":"Jan Midtgaard , Aleksandar S. Dimovski , Claus Brabrand , and Andrzej W\u0105sowski . 2015. Systematic Derivation of Correct Variability-aware Program Analyses. Sci. Comput. Program. 105 , C ( July 2015 ), 145-170. Jan Midtgaard, Aleksandar S. Dimovski, Claus Brabrand, and Andrzej W\u0105sowski. 2015. Systematic Derivation of Correct Variability-aware Program Analyses. Sci. Comput. Program. 105, C ( July 2015 ), 145-170."},{"key":"e_1_2_2_20_1","volume-title":"Foundations for Programming Languages","author":"Mitchell John C.","unstructured":"John C. Mitchell . 1996. Foundations for Programming Languages . The MIT Press . John C. Mitchell. 1996. Foundations for Programming Languages. The MIT Press."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/smr.1595"},{"key":"e_1_2_2_22_1","volume-title":"Types and Programming Languages","author":"Pierce Benjamin C.","unstructured":"Benjamin C. Pierce . 2002. Types and Programming Languages ( 1 st ed.). The MIT Press . Benjamin C. Pierce. 2002. Types and Programming Languages (1st ed.). The MIT Press.","edition":"1"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"e_1_2_2_24_1","volume-title":"van der Linden","author":"Pohl Klaus","year":"2005","unstructured":"Klaus Pohl , G\u00fcnter B\u00f6ckle , and Frank J . van der Linden . 2005 . Software Product Line Engineering: Foundations, Principles and Techniques. Springer-Verlag , Berlin, Heidelberg. Klaus Pohl, G\u00fcnter B\u00f6ckle, and Frank J. van der Linden. 2005. Software Product Line Engineering: Foundations, Principles and Techniques. Springer-Verlag, Berlin, Heidelberg."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28872-2_20"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3131851.3131868"},{"key":"e_1_2_2_28_1","volume-title":"Practical Aspects of Declarative Languages","author":"Shahin Ramy","unstructured":"Ramy Shahin and Marsha Chechik . 2020. Variability-Aware Datalog . In Practical Aspects of Declarative Languages , Ekaterina Komendantskaya and Yanhong Annie Liu (Eds.). Springer International Publishing , 213-221. Ramy Shahin and Marsha Chechik. 2020. Variability-Aware Datalog. In Practical Aspects of Declarative Languages, Ekaterina Komendantskaya and Yanhong Annie Liu (Eds.). Springer International Publishing, 213-221."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338928"},{"issue":"2","key":"e_1_2_2_30_1","first-page":"0","article-title":"CUDD","volume":"2","author":"Somenzi Fabio","year":"1998","unstructured":"Fabio Somenzi . 1998 . CUDD : CU Decision Diagram Package Release 2 . 2 . 0 . (06 1998 ). Fabio Somenzi. 1998. CUDD: CU Decision Diagram Package Release 2.2.0. (06 1998 ).","journal-title":"CU Decision Diagram Package Release"},{"key":"e_1_2_2_31_1","volume-title":"Article 6 (","author":"Th\u00fcm Thomas","year":"2014","unstructured":"Thomas Th\u00fcm , Sven Apel , Christian K\u00e4stner , Ina Schaefer , and Gunter Saake . 2014. A Classification and Survey of Analysis Strategies for Software Product Lines. ACM Comput. Surv. 47, 1 , Article 6 ( June 2014 ), 45 pages. Thomas Th\u00fcm, Sven Apel, Christian K\u00e4stner, Ina Schaefer, and Gunter Saake. 2014. A Classification and Survey of Analysis Strategies for Software Product Lines. ACM Comput. Surv. 47, 1, Article 6 ( June 2014 ), 45 pages."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3280986"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428225","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428225","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:57Z","timestamp":1750197777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":32,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428225"],"URL":"https:\/\/doi.org\/10.1145\/3428225","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}