Branching execution symmetry in Jeopardy by available implicit arguments analysis

Publikation: Bidrag til tidsskriftKonferenceartikelForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 516 KB, PDF-dokument

When the inverse of an algorithm is well-defined – that is, when its output can be deterministically transformed into the input pro- ducing it – we say that the algorithm is invertible. While one can describe an invertible algorithm using a general-purpose programming language, it is generally not possible to guarantee that its inverse is well-defined without additional argument. Reversible languages enforce determinis- tic inverse interpretation at the cost of expressibility, by restricting the building blocks from which an algorithm may be constructed. Jeopardy is a functional programming language designed for writing in- vertible algorithms without the syntactic restrictions of reversible pro- gramming. In particular, Jeopardy allows the limited use of locally non- invertible operations, provided that they are used in a way that can be statically determined to be globally invertible. However, guaranteeing invertibility in Jeopardy is not obvious. One of the central problems in guaranteeing invertibility is that of de- ciding whether a program is symmetric in the face of branching control flow. In this paper, we show how Jeopardy can solve this problem, us- ing a program analysis called available implicit arguments analysis, to approximate branching symmetries.
OriginalsprogEngelsk
BogserieNIKT: Norsk IKT-konferanse for forskning og utdanning
Vol/bind2022
Udgave nummer1
Sider (fra-til)1-14
ISSN1892-0713
StatusUdgivet - 2023
BegivenhedNorwegian ICT Conference for Research and Education -
Varighed: 27 nov. 202230 nov. 2022
Konferencens nummer: 35
https://www.uia.no/konferanser-og-seminarer/nikt-2022

Konference

KonferenceNorwegian ICT Conference for Research and Education
Nummer35
Periode27/11/202230/11/2022
Internetadresse

ID: 375718252