Skip to main content

Common Subexpressions are Uncommon in Lazy Functional Languages

Chitil, Olaf (1998) Common Subexpressions are Uncommon in Lazy Functional Languages. In: Clack, Chris and Hammond, Kevin and Davie, Tony, eds. Implementation of Functional Languages. LNCS 1467 . pp. 53-71. ISBN 978-3-540-64849-9. E-ISBN 978-3-540-68528-9. (doi:10.1007/BFb0055424)

PDF - Author's Accepted Manuscript
Download (278kB) Preview
[img]
Preview
Official URL
http://dx.doi.org/10.1007/BFb0055424

Abstract

Common subexpression elimination is a well-known compiler optimisation that saves time by avoiding the repetition of the same computation. In lazy functional languages, referential transparency renders the identification of common subexpressions very simple. More common subexpressions can be recognised because they can be of arbitrary type whereas standard common subexpression elimination only shares primitive values. However, because lazy functional languages decouple program structure from data space allocation and control flow, analysing its effects and deciding under which conditions the elimination of a common subexpression is beneficial proves to be quite difficult. We developed and implemented the transformation for the language Haskell by extending the Glasgow Haskell compiler. On real-world programs the transformation showed nearly no effect. The reason is that common subexpressions whose elimination could speed up programs are uncommon in lazy functional languages.

Item Type: Conference or workshop item (Paper)
DOI/Identification number: 10.1007/BFb0055424
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Olaf Chitil
Date Deposited: 28 Oct 2016 17:03 UTC
Last Modified: 29 May 2019 18:06 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/58269 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year