Search Results

Documents authored by Mycroft, Alan

Document
DOI: 10.4230/LIPIcs.FSCD.2022.32
Galois Connecting Call-by-Value and Call-by-Name

Authors: Dylan McDermott and Alan Mycroft

Published in: LIPIcs, Volume 228, 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)

Abstract
We establish a general framework for reasoning about the relationship between call-by-value and call-by-name. In languages with side-effects, call-by-value and call-by-name executions of programs often have different, but related, observable behaviours. For example, if a program might diverge but otherwise has no side-effects, then whenever it terminates under call-by-value, it terminates with the same result under call-by-name. We propose a technique for stating and proving these properties. The key ingredient is Levy’s call-by-push-value calculus, which we use as a framework for reasoning about evaluation orders. We construct maps between the call-by-value and call-by-name interpretations of types. We then identify properties of side-effects that imply these maps form a Galois connection. These properties hold for some side-effects (such as divergence), but not others (such as mutable state). This gives rise to a general reasoning principle that relates call-by-value and call-by-name. We apply the reasoning principle to example side-effects including divergence and nondeterminism.
Cite as

Dylan McDermott and Alan Mycroft. Galois Connecting Call-by-Value and Call-by-Name. In 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 228, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mcdermott_et_al:LIPIcs.FSCD.2022.32,
  author =	{McDermott, Dylan and Mycroft, Alan},
  title =	{{Galois Connecting Call-by-Value and Call-by-Name}},
  booktitle =	{7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-233-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{228},
  editor =	{Felty, Amy P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2022.32},
  URN =		{urn:nbn:de:0030-drops-163138},
  doi =		{10.4230/LIPIcs.FSCD.2022.32},
  annote =	{Keywords: computational effect, evaluation order, call-by-push-value, categorical semantics}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2020.15
Data-Flow Analyses as Effects and Graded Monads

Authors: Andrej Ivašković, Alan Mycroft, and Dominic Orchard

Published in: LIPIcs, Volume 167, 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)

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.
Cite as

Andrej Ivašković, Alan Mycroft, and Dominic Orchard. Data-Flow Analyses as Effects and Graded Monads. In 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 167, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ivaskovic_et_al:LIPIcs.FSCD.2020.15,
  author =	{Iva\v{s}kovi\'{c}, Andrej and Mycroft, Alan and Orchard, Dominic},
  title =	{{Data-Flow Analyses as Effects and Graded Monads}},
  booktitle =	{5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
  pages =	{15:1--15:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-155-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{167},
  editor =	{Ariola, Zena M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2020.15},
  URN =		{urn:nbn:de:0030-drops-123376},
  doi =		{10.4230/LIPIcs.FSCD.2020.15},
  annote =	{Keywords: data-flow analysis, effect systems, graded monads, correctness}
}
Document
DOI: 10.4230/DagRep.2.1.100
Analysis of Executables: Benefits and Challenges (Dagstuhl Seminar 12051)

Authors: Andy M. King, Alan Mycroft, Thomas W. Reps, and Axel Simon

Published in: Dagstuhl Reports, Volume 2, Issue 1 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12051 ``Analysis of Executables: Benefits and Challenges''. The seminar had two focus groups: security engineers who need to find bugs in existing software systems and people in academia who try to build automated tools to prove correctness. The meeting of these diverse groups was beneficial and productive for all involved.
Cite as

Andy M. King, Alan Mycroft, Thomas W. Reps, and Axel Simon. Analysis of Executables: Benefits and Challenges (Dagstuhl Seminar 12051). In Dagstuhl Reports, Volume 2, Issue 1, pp. 100-116, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{king_et_al:DagRep.2.1.100,
  author =	{King, Andy M. and Mycroft, Alan and Reps, Thomas W. and Simon, Axel},
  title =	{{Analysis of Executables: Benefits and Challenges (Dagstuhl Seminar 12051)}},
  pages =	{100--116},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{1},
  editor =	{King, Andy M. and Mycroft, Alan and Reps, Thomas W. and Simon, Axel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.1.100},
  URN =		{urn:nbn:de:0030-drops-34585},
  doi =		{10.4230/DagRep.2.1.100},
  annote =	{Keywords: Executable analysis, reverse engineering, malware detection, control flow reconstruction, emulators, binary instrumentation}
}
Document
DOI: 10.4230/DagSemRep.123
Abstract Interpretation (Dagstuhl Seminar 9535)

Authors: Patrick Cousot, Rhadia Cousot, and Alan Mycroft

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Patrick Cousot, Rhadia Cousot, and Alan Mycroft. Abstract Interpretation (Dagstuhl Seminar 9535). Dagstuhl Seminar Report 123, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1995)

Copy BibTex To Clipboard

@TechReport{cousot_et_al:DagSemRep.123,
  author =	{Cousot, Patrick and Cousot, Rhadia and Mycroft, Alan},
  title =	{{Abstract Interpretation (Dagstuhl Seminar 9535)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{1995},
  type = 	{Dagstuhl Seminar Report},
  number =	{123},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.123},
  URN =		{urn:nbn:de:0030-drops-150116},
  doi =		{10.4230/DagSemRep.123},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact