The Library
Efficient combinator code
Tools
Joy, Mike, Rayward-Smith, V. J. and Burton, F. W. (1985) Efficient combinator code. Computer Languages, Volume 10 (Number 3/4). pp. 211-224. doi:10.1016/0096-0551(85)90017-7 ISSN 0096-0551.
PDF
joy_raywardsmith_cl.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (844Kb) |
Official URL: http://dx.doi.org/10.1016/0096-0551(85)90017-7
Abstract
Some combinatory logics are examined as object code for functional programs. The worst-case performances of certain algorithms for abstracting variables from combinatory expressions are analysed. A lower bound on the performance of any abstraction algorithm for a finite set of combinators is given. Using the combinators S, K, I, B, C, S', B', C' and Y, the problem of finding an optimal abstraction algorithm is shown to be NP-complete. Some methods of improving abstraction algorithms for those combinators are examined, including "'balancing" (for asymptotic performance) and "peephole" optimisations (for smaller cases).
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Computer Languages | ||||
Publisher: | Oxford | ||||
ISSN: | 0096-0551 | ||||
Official Date: | 1985 | ||||
Dates: |
|
||||
Volume: | Volume 10 | ||||
Number: | Number 3/4 | ||||
Page Range: | pp. 211-224 | ||||
DOI: | 10.1016/0096-0551(85)90017-7 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 27 December 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |