{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:53:32Z","timestamp":1776891212775,"version":"3.51.2"},"reference-count":21,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"3","license":[{"start":{"date-parts":[[2008,11,7]],"date-time":"2008-11-07T00:00:00Z","timestamp":1226016000000},"content-version":"unspecified","delay-in-days":5608,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[1993,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Based on Henglein's efficient binding-time analysis for the lambda calculus (with constants and \u2018fix\u2019) (Henglein, 1991), we develop three efficient analyses for use in the preprocessing phase of Similix, a self-applicable partial evaluator for a higher-order subset of Scheme. The analyses developed in this paper are almost-linear in the size of the analysed program. (1) A\n                    <jats:italic>flow analysis<\/jats:italic>\n                    determines possible value flow between lambda-abstractions and function applications and between constructor applications and selector\/predicate applications. The flow analysis is not particularly biased towards partial evaluation; the analysis corresponds to the closure analysis of Bondorf (1991b). (2) A (monovariant)\n                    <jats:italic>binding-time analysis<\/jats:italic>\n                    distinguishes static from dynamic values; the analysis treats both higher-order functions and partially static data structures. (3) A new\n                    <jats:italic>is-used analysis<\/jats:italic>\n                    , not present in Bondorf (1991b), finds a non-minimal binding-time annotation which is \u2018safe\u2019 in a certain way: a first-order value may only become static if its result is \u2018needed\u2019 during specialization; this \u2018poor man's generalization\u2019 (Holst, 1988) increases termination of specialization. The three analyses are performed sequentially in the above mentioned order since each depends on results from the previous analyses. The input to all three analyses are constraint sets generated from the program being analysed. The constraints are solved efficiently by a normalizing union\/find-based algorithm in almost-linear time. Whenever possible, the constraint sets are partitioned into subsets which are solved in a specific order; this simplifies constraint normalization. The framework elegantly allows expressing both forwards and backwards components of analyses. In particular, the new is-used analysis is of backwards nature. The three constraint normalization algorithms are proved correct (soundness, completeness, termination, existence of a best solution). The analyses have been implemented and integrated in the Similix system. The new analyses are indeed much more efficient than those of Bondorf (1991b); the almost-linear complexity of the new analyses is confirmed by the implementation.\n                  <\/jats:p>","DOI":"10.1017\/s0956796800000769","type":"journal-article","created":{"date-parts":[[2008,11,7]],"date-time":"2008-11-07T11:13:56Z","timestamp":1226056436000},"page":"315-346","source":"Crossref","is-referenced-by-count":51,"title":["Efficient analyses for realistic off-line partial evaluation"],"prefix":"10.46298","volume":"3","author":[{"given":"Anders","family":"Bondorf","sequence":"first","affiliation":[]},{"given":"Jesper","family":"J\u00f8rgensen","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2008,11,7]]},"reference":[{"key":"S0956796800000769_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BF01806312"},{"key":"S0956796800000769_ref015","first-page":"29","volume-title":"ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation","author":"Katz","year":"1992"},{"key":"S0956796800000769_ref008","doi-asserted-by":"crossref","unstructured":"Henglein Fritz . (1991) Efficient type inference for higher-order binding-time analysis. Pages 448\u2013472 of: Hughes John (ed), Conference on Functional Programming and Computer Architecture, Cambridge, Massachusetts. Lecture Notes in Computer Science 523. Springer-Verlag.","DOI":"10.1007\/3540543961_22"},{"key":"S0956796800000769_ref005","doi-asserted-by":"crossref","DOI":"10.1017\/S0956796800000769","volume-title":"Efficient analyses for realistic off-line partial evaluation: extended version","author":"Bondorf","year":"1993"},{"key":"S0956796800000769_ref018","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000770"},{"key":"S0956796800000769_ref020","unstructured":"Sestoft Peter. (1988) (Student Report 88-7-2, October). Replacing function parameters by global variables. M.Phil. thesis, DIKU, University of Copenhagen, Denmark."},{"key":"S0956796800000769_ref021","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000782"},{"key":"S0956796800000769_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15976-2_6"},{"key":"S0956796800000769_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(91)90002-F"},{"key":"S0956796800000769_ref003","doi-asserted-by":"crossref","unstructured":"Bondorf Anders . (1992) (June). Improving binding times without explicit cps-conversion. Pages 1\u201310 of: 1992 ACM Conference on Lisp and Functional Programming. San Francisco, California. LISP Pointers V, 1.","DOI":"10.1145\/141478.141483"},{"key":"S0956796800000769_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(91)90035-V"},{"key":"S0956796800000769_ref006","doi-asserted-by":"crossref","unstructured":"Consel Charles . (1990) (June). Binding time analysis for higher order untyped functional languages. Pages 264\u2013272 of: 1990 ACM Conference on Lisp and Functional Programming. Nice, France.","DOI":"10.1145\/91556.91668"},{"key":"S0956796800000769_ref002","volume-title":"Similix Manual, system version 4.0","author":"Bondorf","year":"1991"},{"key":"S0956796800000769_ref007","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000058"},{"key":"S0956796800000769_ref010","unstructured":"Holst Carsten Kehler . (1988) (Aug.). Poor man's generalization. Working note."},{"key":"S0956796800000769_ref009","unstructured":"Henglein Fritz . (1992) (Mar.). Simple closure analysis. Working note."},{"key":"S0956796800000769_ref011","unstructured":"IEEE standard for the Scheme programming language. IEEE Std 1178-1990. (1990) May."},{"key":"S0956796800000769_ref014","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen Jesper . (1992) (Jan.). Generating a compiler for a lazy language by partial evaluation. Pages 258\u2013268 of: Nineteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. Albuquerque, New Mexico.","DOI":"10.1145\/143165.143220"},{"key":"S0956796800000769_ref016","doi-asserted-by":"crossref","unstructured":"Launchbury John . (1991) Projection factorisations in partial evaluation. Distinguished Dissertations in Computer Science. Cambridge University Press.","DOI":"10.1017\/CBO9780511569814"},{"key":"S0956796800000769_ref017","doi-asserted-by":"crossref","unstructured":"Nielson Hanne R. , & Nielson Flemming . (1988) Automatic binding time analysis for a typed \u03bb-calculus. Pages 98\u2013106 of: Fifteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. San Diego, California.","DOI":"10.1145\/73560.73569"},{"key":"S0956796800000769_ref019","first-page":"465","volume-title":"Partial Evaluation and Mixed Computation","author":"Schmidt","year":"1988"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796800000769","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:17:56Z","timestamp":1776889076000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796800000769\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["S0956796800000769"],"URL":"https:\/\/doi.org\/10.1017\/s0956796800000769","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]}}}