Skip to main content

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 (896kB) Preview
[thumbnail of dataflow-effect-monads.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:
https://dx.doi.org/10.4230/LIPIcs.FSCD.2020.15

Abstract

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 (https://ror.org/0439y7842)
Depositing User: Dominic Orchard
Date Deposited: 26 Jun 2020 08:57 UTC
Last Modified: 12 Jul 2022 10:41 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/81880 (The current URI for this page, for reference purposes)
Ivašković, Andrej: https://orcid.org/0000-0002-1347-4884
Mycroft, Alan: https://orcid.org/0000-0001-7013-8572
Orchard, Dominic: https://orcid.org/0000-0002-7058-7842
  • Depositors only (login required):

Downloads

Downloads per month over past year