Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01025633
Contributor : Nicolas Tabareau <>
Submitted on : Wednesday, July 23, 2014 - 11:38:20 AM
Last modification on : Wednesday, December 5, 2018 - 1:22:15 AM
Long-term archiving on: : Tuesday, November 25, 2014 - 2:06:35 PM

File

RR-8569.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01025633, version 2

Citation

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

Share

Metrics

Record views

562

Files downloads

475