Skip to main content
Kent Academic Repository

Data-flow analyses as effects and graded monads

Ivašković, Andrej, Mycroft, Alan, Orchard, Dominic (2020) Data-flow analyses as effects and graded monads. 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020), 167 . (doi:10.4230/LIPIcs.FSCD.2020.15) (KAR id:81880)

PDF Author's Accepted Manuscript
Language: English

Download this file
[thumbnail of dataflow-effect-monads.pdf]
Request a format suitable for use with assistive technology e.g. a screenreader
Official URL:


In static analysis, two frameworks have been studied extensively: monotone data-flow analysis and type-and-effect systems. Whilst both are seen as general analysis frameworks, their relationship has remained unclear. Here we show that monotone data-flow analyses can be encoded as effect systems in a uniform way, via algebras of transfer functions. This helps to answer questions about the most appropriate structure for general effect algebras, especially with regards capturing control-flow precisely. Via the perspective of capturing data-flow analyses, we show the recent suggestion of using effect quantales is not general enough as it excludes non-distributive analyses e.g., constant propagation. By rephrasing the McCarthy transformation, we then model monotone data-flow effects via graded monads. This provides a model of data-flow analyses that can be used to reason about analysis correctness at the semantic level, and to embed data-flow analyses into type systems.

Item Type: Article
DOI/Identification number: 10.4230/LIPIcs.FSCD.2020.15
Uncontrolled keywords: data-flow analysis, effect systems, graded monads, correctness
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Q Science > QA Mathematics (inc Computing science) > QA 9 Formal systems, logics
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Funders: Engineering and Physical Sciences Research Council (
Depositing User: Dominic Orchard
Date Deposited: 26 Jun 2020 08:57 UTC
Last Modified: 12 Jul 2022 10:41 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.