Skip to main content
Kent Academic Repository

Common Subexpression Elimination in a Lazy Functional Language

Chitil, Olaf (1997) Common Subexpression Elimination in a Lazy Functional Language. In: Clack, Chris and Davie, Tony and Hammond, Kevin, eds. Draft Proceedings of the 9th International Workshop on Implementation of Functional Languages. . pp. 501-516. (KAR id:21455)


Common subexpression elimination is a well-known compiler optimisation that saves time by avoiding the repetition of the same computation. To our knowledge it has not yet been applied to lazy functional programming languages, although there are several advantages. First, the referential transparency of these languages makes the identification of common subexpressions very simple. Second, 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 and measured its effectiveness on real-world programs.

Item Type: Conference or workshop item (Paper)
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Funders: University of St Andrews (
Depositing User: Olaf Chitil
Date Deposited: 01 Aug 2009 15:08 UTC
Last Modified: 12 Jul 2022 10:39 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.