{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T20:34:43Z","timestamp":1693859683796},"reference-count":48,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2008,11,7]],"date-time":"2008-11-07T00:00:00Z","timestamp":1226016000000},"content-version":"unspecified","delay-in-days":6247,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[1991,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Traditional functional languages do not have an explicit distinction between binding times. It arises implicitly, however, as one typically instantiates a higher-order function with the arguments that are known, whereas the unknown arguments remain to be taken as parameters. The distinction between \u2018<jats:italic>known<\/jats:italic>\u2019 and \u2018<jats:italic>unknown<\/jats:italic>\u2019 is closely related to the distinction between <jats:italic>binding times<\/jats:italic> like \u2018<jats:italic>compile-time<\/jats:italic>\u2019 and \u2018<jats:italic>run-time<\/jats:italic>\u2019. This leads to the use of a combination of <jats:italic>polymorphic type inference<\/jats:italic> and <jats:italic>binding time analysis<\/jats:italic> for obtaining the required information about which arguments are known.<\/jats:p><jats:p>Following the current trend in the implementation of functional languages we then transform the run-time level of the program <jats:italic>(not<\/jats:italic> the compile-time level) into <jats:italic>categorical combinators<\/jats:italic>. At this stage we have a natural distinction between two kinds of program transformations: <jats:italic>partial evaluation<\/jats:italic>, which involves the compile-time level of our notation, and <jats:italic>algebraic transformations<\/jats:italic> (i.e., the application of algebraic laws), which involves the run-time level of our notation.<\/jats:p><jats:p>By reinterpreting the combinators in suitable ways we obtain specifications of <jats:italic>abstract interpretations<\/jats:italic> (or data flow analyses). In particular, the use of combinators makes it possible to use a general framework for specifying both <jats:italic>forward<\/jats:italic> and <jats:italic>backward analyses<\/jats:italic>. The results of these analyses will be used to enable program transformations that are not applicable under all circumstances.<\/jats:p><jats:p>Finally, the combinators can also be reinterpreted to specify <jats:italic>code generation<\/jats:italic> for various (abstract) machines. To improve the efficiency of the code generated, one may apply abstract interpretations to collect extra information for guiding the code generation. Peephole optimizations may be used to improve the code at the lowest level.<\/jats:p>","DOI":"10.1017\/s0956796800000204","type":"journal-article","created":{"date-parts":[[2008,11,7]],"date-time":"2008-11-07T16:14:25Z","timestamp":1226074465000},"page":"459-494","source":"Crossref","is-referenced-by-count":4,"title":["Using transformations in the implementation of higher-order functions"],"prefix":"10.1017","volume":"1","author":[{"given":"Hanne Riis","family":"Nielson","sequence":"first","affiliation":[]},{"given":"Flemming","family":"Nielson","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,11,7]]},"reference":[{"key":"S0956796800000204_ref047","volume-title":"Proc. Functional Programming Languages and Computer Architectures","volume":"201","author":"Turner","year":"1985"},{"key":"S0956796800000204_ref046","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380090105"},{"key":"S0956796800000204_ref045","volume-title":"Partial Evaluation and Mixed Computation","author":"Schmidt","year":"1988"},{"key":"S0956796800000204_ref044","volume-title":"The Implementation of Functional Programming Languages","author":"Peyton","year":"1987"},{"key":"S0956796800000204_ref041","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90155-B"},{"key":"S0956796800000204_ref039","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90091-1"},{"key":"S0956796800000204_ref026","volume-title":"TAPSOFT 1989, Lecture Notes in Computer Science","author":"Mogensen","year":"1989"},{"key":"S0956796800000204_ref036","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(88)90025-1"},{"key":"S0956796800000204_ref048","volume-title":"Abstract Interpretation of Declarative Languages","author":"Wadler","year":"1987"},{"key":"S0956796800000204_ref040","doi-asserted-by":"crossref","unstructured":"Nielson H. R. and Nielson F. 1989. Transformations on higher-order functions. Proc. Functional Programming and Computer Architecture Conference.ACM Press.","DOI":"10.1145\/99370.99380"},{"key":"S0956796800000204_ref004","volume-title":"Proc. Functional Programming Languages and Comput. Architectures","author":"Bjerner","year":"1989"},{"key":"S0956796800000204_ref008","unstructured":"Cardelli C. 1983. The functional abstract machine. Bell Labs. Technical Report TR-107."},{"key":"S0956796800000204_ref042","volume-title":"Proc. ESOP '90","volume":"432","author":"Nielson","year":"1990"},{"key":"S0956796800000204_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90111-6"},{"key":"S0956796800000204_ref011","unstructured":"Damas L. 1985. Type assignment in programming languages. PhD Thesis CST-33-85, University of Edinburgh, Scotland."},{"key":"S0956796800000204_ref022","doi-asserted-by":"crossref","unstructured":"J\u00f8rring U. and Scherlis W. L. 1986. Compilers and staging transformations. Proc. 13th ACM Symposium on Principles of Programming Languages.ACM Press.","DOI":"10.1145\/512644.512652"},{"key":"S0956796800000204_ref033","volume-title":"Abstract Interpretation of Declarative Languages","author":"Nielson","year":"1987"},{"key":"S0956796800000204_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(87)90020-7"},{"key":"S0956796800000204_ref032","doi-asserted-by":"crossref","unstructured":"Nielson H. R. and Nielson F. 1986. Semantics directed compiling for functional languages. Proc. ACM Conf. on LISP and Functional Programming.ACM Press.","DOI":"10.1145\/319838.319867"},{"key":"S0956796800000204_ref035","volume-title":"Partial Evaluation and Mixed Computation","author":"Nielson","year":"1988"},{"key":"S0956796800000204_ref002","doi-asserted-by":"publisher","DOI":"10.1145\/359576.359579"},{"key":"S0956796800000204_ref010","volume-title":"Categorical Combinators, Sequential Algorithms and Functional Programming","author":"Curien","year":"1986"},{"key":"S0956796800000204_ref043","doi-asserted-by":"crossref","unstructured":"Nielson H. R. and Nielson F. 1990 c. Context information for lazy code generation. Proc. LISP and Functional Programming Conference.ACM Press.","DOI":"10.1145\/91556.91665"},{"key":"S0956796800000204_ref037","volume-title":"Proc. ESOP 1988","volume":"300","author":"Nielson","year":"1988"},{"key":"S0956796800000204_ref001","volume-title":"Compilers \u2013 Principles, Techniques and Tools","author":"Aho","year":"1986"},{"key":"S0956796800000204_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(86)90017-1"},{"key":"S0956796800000204_ref038","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90006-X"},{"key":"S0956796800000204_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(86)90010-9"},{"key":"S0956796800000204_ref017","doi-asserted-by":"crossref","unstructured":"Hughes J. 1982. Supercombinators: a new implementation method for applicative languages. Proc. 1982 ACM Conf. on LISP and Functional Programming.ACM Press.","DOI":"10.1145\/800068.802129"},{"key":"S0956796800000204_ref006","volume-title":"Proc. Functional Programming Languages and Comput. Architectures Conf","volume":"274","author":"Burn","year":"1987"},{"key":"S0956796800000204_ref023","volume-title":"Introduction to Higher Order Categorical Logic","author":"Lambek","year":"1986"},{"key":"S0956796800000204_ref007","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321996"},{"key":"S0956796800000204_ref012","volume-title":"Partial Evaluation and Mixed Computation","author":"Darlington","year":"1988"},{"key":"S0956796800000204_ref013","unstructured":"Despeyroux J. 1986. Proof of translation in natural semantics. Symposium on Logic in Computer Science.IEEE Computer Society Press."},{"key":"S0956796800000204_ref015","doi-asserted-by":"publisher","DOI":"10.1145\/357153.357154"},{"key":"S0956796800000204_ref020","doi-asserted-by":"crossref","unstructured":"Hudak P. and Young J. 1988. A collecting interpretation of expressions (without powerdomains). Proc. 15th ACM Symposium on Principles of Programming LanguagesACM Press.","DOI":"10.1145\/73560.73570"},{"key":"S0956796800000204_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(88)90052-4"},{"key":"S0956796800000204_ref018","volume-title":"Proc. Programs as Data Objects","volume":"217","author":"Hughes","year":"1986"},{"key":"S0956796800000204_ref021","volume-title":"Proc. Rewriting Techniques and Applications","volume":"202","author":"Jones","year":"1985"},{"key":"S0956796800000204_ref019","volume-title":"Partial Evaluation and Mixed Computation","author":"Hughes","year":"1988"},{"key":"S0956796800000204_ref024","unstructured":"Milner R. 1984. The standard ML core language. Proc. ACM Conference on LISP and Functional Programming.ACM Press."},{"key":"S0956796800000204_ref025","article-title":"A theory of type polymorphism in programming","volume":"17","author":"Milner","year":"1978","journal-title":"J. Comput. Systems"},{"key":"S0956796800000204_ref027","doi-asserted-by":"crossref","unstructured":"Montenyohl M. and Wand M. 1988. Correct flow analysis in continuation semantics. Proc. 15th ACM Symposium on Principles of Programming Languages.ACM Press.","DOI":"10.1145\/73560.73578"},{"key":"S0956796800000204_ref028","unstructured":"Mycroft A. 1981. Abstract interpretation and optimizing transformations for applicative programs. PhD Thesis CTS-15-81, University of Edinburgh, Scotland."},{"key":"S0956796800000204_ref029","doi-asserted-by":"crossref","unstructured":"Mycroft A. 1980. The theory and practice of transforming call-by-need into call-by-value. Proc. 4th International Symposium on Programming. Volume 83 of Lectures Notes in Computer Science. Springer-Verlag.","DOI":"10.1007\/3-540-09981-6_19"},{"key":"S0956796800000204_ref030","volume-title":"Proc. ICALP 1983","volume":"154","author":"Mycroft","year":"1983"},{"key":"S0956796800000204_ref031","doi-asserted-by":"publisher","DOI":"10.1145\/3916.3917"},{"key":"S0956796800000204_ref034","doi-asserted-by":"crossref","unstructured":"Nielson F. 1987 b. Strictness analysis and denotational abstract interpretation (extended abstract). ACM Conf. on Principles of Programming Languages.ACM Press.","DOI":"10.1145\/41625.41636"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796800000204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T20:13:52Z","timestamp":1558124032000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796800000204\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,10]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1991,10]]}},"alternative-id":["S0956796800000204"],"URL":"https:\/\/doi.org\/10.1017\/s0956796800000204","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,10]]}}}