Skip to Main content Skip to Navigation

Lazier Imperative Programming

Rémi Douence 1 Nicolas Tabareau 1, 2 
1 ASCOLA - Aspect and composition languages
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : Laziness is a powerful concept in functional programming that enables reusing general functions in a specific context, while keeping performance close to the efficiency of dedicated definitions. Lazy evaluation can be used in imperative programming too. Twenty years ago, John Launchbury was already advocating for lazy imperative programming, but the level of laziness of his framework remained limited: a single effect can trigger numerous delayed computations, even if those are not required for the correctness of the evaluation. Twenty years after, the picture has not changed. In this article, we propose an Haskell framework to specify computational effects of imperative programs as well as their dependencies. Our framework is based on the operational monad transformer which encapsulates an algebraic presentation of effectful operations. A lazy monad transformer is then in charge of delaying non-necessary computations by maintaining a trace of imperative closures. We present a semantics of a call-by-need λ-calculus extended with imperative strict and lazy features and prove the correctness of our approach. While originally motivated by a less rigid use of foreign functions, we show that our approach is fruitful for a simple scenario based on sorted mutable arrays. Furthermore, we can take advantage of equations between algebraic operations to dynamically optimize imperative computations composition.
Document type :
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Nicolas Tabareau Connect in order to contact the contributor
Submitted on : Wednesday, July 23, 2014 - 11:38:20 AM
Last modification on : Wednesday, April 27, 2022 - 4:22:41 AM
Long-term archiving on: : Tuesday, November 25, 2014 - 2:06:35 PM


Files produced by the author(s)


  • HAL Id : hal-01025633, version 2


Rémi Douence, Nicolas Tabareau. Lazier Imperative Programming. [Research Report] RR-8569, INRIA. 2014. ⟨hal-01025633v2⟩



Record views


Files downloads