{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:19Z","timestamp":1761611179605},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":8685,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1990,6]]},"abstract":"<jats:p>A computer handles <jats:italic>\u03bb<\/jats:italic>-terms more easily if these are translated into combinatory terms. This translation process is called bracket abstraction. The simplest abstraction algorithm\u2014the (fab) algorithm of Curry (see Curry and Feys [6])\u2014is lengthy to implement and produces combinatory terms that increase rapidly in length as the number of variables to be abstracted increases.<\/jats:p><jats:p>There are several ways in which these problems can be alleviated:<\/jats:p><jats:p>(1) A change in order of the clauses in the algorithm so that (f) is performed as a last resort.<\/jats:p><jats:p>(2) The use of an extra clause (c), appropriate to <jats:italic>\u03b2\u03b7<\/jats:italic> reduction.<\/jats:p><jats:p>(3) The introduction of a finite number of extra combinators.<\/jats:p><jats:p>The original 1924 form of bracket abstraction of Sch\u00f6nfinkel [17], which in fact predates <jats:italic>\u03bb<\/jats:italic>-calculus, uses all three of these techniques; all are also mentioned in Curry and Feys [6].<\/jats:p><jats:p>A technique employed by many computing scientists (Turner [20], Peyton Jones [16], Oberhauser [15]) is to use the (fab) algorithm followed by certain \u201coptimizations\u201d or simplifications involving extra combinators and sometimes special cases of (c).<\/jats:p><jats:p>Another is either to allow a fixed infinite set of (super-) combinators (Abdali [1], Kennaway and Sleep [10], Krishnamurthy [12], Tonino [19]) or to allow new combinators to be defined one by one during the abstraction process (Hughes [7] and [8]).<\/jats:p><jats:p>A final method encodes the variables to be abstracted as an <jats:italic>n<\/jats:italic>-tuple\u2014this requires only a finite number of combinators (Curien [5], Statman [18]).<\/jats:p>","DOI":"10.2307\/2274655","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:35:29Z","timestamp":1146954929000},"page":"656-669","source":"Crossref","is-referenced-by-count":6,"title":["Some improvements to Turner's algorithm for bracket abstraction"],"prefix":"10.1017","volume":"55","author":[{"given":"M. W.","family":"Bunder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200026050_ref007","volume-title":"The design and implementation of programming languages","author":"Hughes","year":"1983"},{"key":"S0022481200026050_ref009","volume-title":"The complexity of a translation of \u03bb-calculus to combinators","author":"Kennaway","year":"1984"},{"key":"S0022481200026050_ref016","volume-title":"The implementation of functional programming languages","author":"Jones","year":"1986"},{"key":"S0022481200026050_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90161-X"},{"key":"S0022481200026050_ref005","volume-title":"Categorical combinators, sequential algorithms and functional programming","author":"Curien","year":"1986"},{"key":"S0022481200026050_ref006","volume-title":"Combinatory logic","volume":"1","author":"Curry","year":"1958"},{"key":"S0022481200026050_ref001","first-page":"222","volume":"41","author":"Abdali","year":"1976","journal-title":"An abstraction algorithm for combinatory logic"},{"key":"S0022481200026050_ref015","first-page":"1","volume-title":"Graph reduction (proceedings, Santa Fe, New Mexico, 1986)","volume":"279","author":"Oberhauser","year":"1987"},{"key":"S0022481200026050_ref020","first-page":"267","volume":"44","author":"Turner","year":"1979","journal-title":"Another algorithm for bracket abstraction"},{"key":"S0022481200026050_ref003","first-page":"590","volume":"54","author":"Bunder","year":"1989","journal-title":"On adding (\u03be) to weak equality"},{"key":"S0022481200026050_ref008","first-page":"1","volume-title":"Conference record of the 1982 ACM symposium on LISP and functional programming","author":"Hughes"},{"key":"S0022481200026050_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-18317-5_5"},{"key":"S0022481200026050_ref010","volume-title":"Counting director strings","author":"Kennaway","year":"1984"},{"key":"S0022481200026050_ref002","volume-title":"On adding further forms of (\u03be) to weak equality in combinatory logic","author":"Bunder","year":"1987"},{"key":"S0022481200026050_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90014-X"},{"key":"S0022481200026050_ref014","volume-title":"Complexity of combinatorial code","author":"Mulder","year":"1985"},{"key":"S0022481200026050_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448013"},{"key":"S0022481200026050_ref018","volume-title":"An optimal translation of \u03bb terms into combinators","author":"Statman","year":"1983"},{"key":"S0022481200026050_ref012","unstructured":"[12] Krishnamurthy V. , Parallelism in functional languages using combinators and delayed evaluation, Ph.D. thesis, University of Waikato, Hamilton, New Zealand, 1986."},{"key":"S0022481200026050_ref019","unstructured":"[19] Tonino M. M. E. , private communication, 1984 (see Mulder [14])."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200026050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T21:13:16Z","timestamp":1558213996000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200026050\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["S0022481200026050"],"URL":"https:\/\/doi.org\/10.2307\/2274655","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}