Branching execution symmetry in Jeopardy by available implicit arguments analysis

Research output: Contribution to journalConference articleResearchpeer-review

Documents

  • Fulltext

    Final published version, 516 KB, PDF document

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.
Original languageEnglish
Book seriesNIKT: Norsk IKT-konferanse for forskning og utdanning
Volume2022
Issue number1
Pages (from-to)1-14
ISSN1892-0713
Publication statusPublished - 2023
EventNorwegian ICT Conference for Research and Education -
Duration: 27 Nov 202230 Nov 2022
Conference number: 35
https://www.uia.no/konferanser-og-seminarer/nikt-2022

Conference

ConferenceNorwegian ICT Conference for Research and Education
Number35
Period27/11/202230/11/2022
Internet address

ID: 375718252