In this thesis we investigate some of the issues involved in creating a reversible variant of the formal software development language B. We consider the effects of regarding computation as a potentially reversible process, yielding a number of new programming structures which we integrate into an implementation-level language RB0, a more expressive variant of B0, the current implementation-level language for B. Since reversibility simplifies garbage collection, in RB0 we make use of more abstract, set-based data types, normally available in B only at the specification level. Similarly, we propose extending the domain of abstract functions currently specifiable in B to allow them to become concrete functions, thereby furnishing B with a functional sub-language. We also investigate expanding the use of Lambda calculus from the abstract stage of B to the implementation. Unlike B0, RB0 will not disallow non-determinism, and can also specify what we call Prospective Value computations (which are described). The executable language implements all of these features. After introducing some preliminary concepts, we review the work leading to the rise of Reversible Computing as a possible answer to the growing problem of energy dissipation in modern processors. We describe the language RB0, and demonstrate the use of its features, introducing the companion language RB1 and its role in the process. We then introduce our execution platform, the Reversible Virtual Machine (RVM), and translate some of the examples developed earlier into RVM code. For the concrete functions, we provide a proposed syntax and translation schema to enable consistent translation to RVM, and introduce a postfix Lambda notation to link the RB0 specification to the RVM’s own postfix notation. We provide comprehensive translation schemas for those parts of RB0 which would be found in B operations; these will form the basis of an automated translation engine. In addition, we look at a denotational semantics for Bunch theory, which has proved useful in formalising the underlying concepts.

Made available in DSpace on 2016-03-15T19:38:08Z (GMT). No. of bitstreams: 1 Guilherme Kronemberger.pdf: 1225637 bytes, checksum: 6f698faf7a8661b382c4977e4b07f631 (MD5) Previous issue date: 2008-01-28 / Cellular automata have been studied as computer models in many different areas. They have many properties, one of them being reversibility. Reversible cellular automata can be used, among other applications, for data compressing and encryption. Apparently, the reversible rules featured in the literature seem to have been derived through exhaustive searches in their corresponding spaces. However, it would be important the availability of an algorithm that would allow their direct and easy construction, different from what occurs in literature. This is the aim of this work. Along this line, we tried to come up with an algorithm to allow the identification of one-dimensional, reversible cellular automaton rules. This was based on reversible rules with 2 states and 2, 3, 4 and 5 cells per neighborhood, and on those with 3 states and 2 and 3 cells per neighborhood, all of them drawn out of exhaustive analysis and from the literature. By studying these rules it was possible to verify in each space that: all reversible rules are balanced; they are symmetrically distributed; a subset of them herein denoted primitive reversible rules, RPs have a simple formation law, defined by homogeneous blocks of states; and, if a rule is reversible, so are all its dynamically equivalent rules. In the attempt to obtain the targetted algorithm, an approach was explored in which the non-primitive reversible rules (the so-called derived rules, RDs) were supposed to be obtained from the primitives. Along this line, two ways to construct the RDs were tried out, one based upon using all RPs jointly as a group, and another, using them individually; however, neither of them led to a positive result. Additionally, relations between the properties of reversibility and conservativity of a rule have also been studied in the rule spaces considered. / Autômatos celulares têm sido estudados como modelos computacionais em diversas áreas, sendo que muitas são as suas propriedades, entre elas a reversibilidade. Autômatos celulares reversíveis podem ser usados, entre outras aplicações, para compactação ou encriptação de dados. Aparentemente, as regras reversíveis apresentadas na literatura parecem ter sido derivadas apenas através de buscas exaustivas em seus espaços correspondentes. No entanto, seria importante a existência de um algoritmo que permitisse construí-las fácil e diretamente, diferente do que acontece na literatura. Este é o objetivo deste trabalho. Neste sentido, buscou-se um algoritmo que permitesse identificar regras de autômatos celulares unidimensionais reversíveis. Para tanto, foram obtidas em análises exaustivas e na literatura todas as regras reversíveis de 2 estados e vizinhanças de 2, 3, 4 e 5 células, e de 3 estados e vizinhanças de 2 e 3 células. Com o estudo destas regras constatou-se em cada espaço que: todas as regras reversíveis são balanceadas; elas se distribuem simetricamente; um subconjunto delas aqui denominadas regras reversíveis primitivas, RPs possui lei de formação simples, definida por blocos homogêneos de estados; e, se uma regra é reversível, todas as suas equivalentes dinâmicas também o são. Na tentativa de se obter o algoritmo desejado explorou-se uma abordagem em que as regras reversíveis não primitivas (denominadas regras derivadas, RDs), seriam obtidas a partir das primitivas. Nesse sentido foram testados dois esquemas de construção das RDs, um baseado na utilização conjunta de todas as RPs, e outro, utilizando-as individualmente; entretanto, ambos não levaram a resultado positivo. Adicionalmente, estudou-se a relação entre as propriedades de reversibilidade e conservatividade de regras nos espaços considerados.

Programming languages traditionally describe computations going one way: a program might compute a hash value from a string, or an encrypted message from a plaintext. However, sometimes it is also of interest to go the other way around: for encryption, we not only want to encrypt messages but also to decrypt them, and to be sure that the decryption correctly reproduces the original message. In an invertible programming language, a single program specifies two directions of a transformation, and the language guarantees that the two correspond as inverses. Invertible languages often require programs to be composed from atomic invertible fragments, a property known as local invertibility. This requirement has connections to applications such as low-energy and quantum computing. However, many invertible algorithms are more naturally expressed as depending unidirectionally on some inputs, e.g., the encryption key—this property is known as partial invertibility. Existing work largely lacks a systematic treatment of partial invertibility, and the connection to the locally invertible paradigm is not yet well-understood. In this thesis, we show that with the right design tradeoff, partial invertibility can be expressed within a locally invertible setting. We present KALPIS, a new functional language supporting expressive partial invertibility, yet maintaining a straightforward locally invertible semantics. This is made formal by a novel arrow combinator language RRARR, with primitives embodying functions, parameterized bijections, and interactions between the two. The formulation is based on recent work on effects in invertible computation, namely the irreversibility effect and the reversible reader. We substantiate the work with a prototype implementation of KALPIS, and demonstrate its utility through a number of nontrivial examples. Further, we give a complete formalization of the two systems, including the operational semantics and type system of KALPIS and a locally invertible interpretation and equational characterization of RRARR. Finally, we give a compositional translation from KALPIS into RRARR, motivating us to call it an arrow metalanguage. Most of the formalization is mechanized using the proof assistant Agda. / Programmeringsspråk beskriver traditionellt beräkningar som går åt ett håll: ett program kan till exempel beräkna ett hash-värde från en sträng eller ett krypterat meddelande från en klartext. Ibland är det dock även av intresse att gå åt andra hållet: vid kryptering vill vi inte bara kryptera meddelanden utan också avkryptera dem, och vara säkra på att avkrypteringen korrekt återskapar det ursprungliga meddelandet. I ett inverterbart programmeringsspråk beskriver ett enskilt program två riktningar av en transformation, och språket garanterar att de två motsvarar varandra som inverser. Inverterbara språk kräver ofta att program konstrueras från enskilt inverterbara komponenter, en egenskap som kallas lokal inverterbarhet. Denna egenskap har kopplingar till tillämpningar som lågenergioch kvantdatorer. Å andra sidan är det ofta naturligt att inverterbara algoritmer beror enkelriktat på vissa indata, till exempel krypteringsnyckeln—något som kallas partiell inverbarhet. Tidigare forskning saknar i stor utsträckning en systematisk behandling av partiell inverterbarhet, och kopplingen till lokal inverterbarhet är ännu inte välförstådd. I denna avhandling visar vi att med rätt designavvägning kan partiell inverterbarhet uttryckas ovanpå en lokalt inverterbar grund. Vi presenterar KALPIS, ett nytt funktionellt språk som stöder uttrycksfull partiell inverterbarhet, samtidigt som det bibehåller en enkel lokalt inverterbar semantik. Detta formaliseras genom ett nytt Arrow-kombinatorspråk RRARR, vars primitiver representerar funktioner, parameteriserade bijektioner och interaktioner mellan de två. Formuleringen baseras på ny forskning om sidoeffekter i inverterbar beräkning, nämligen irreversibilitetseffekten och reversible reader. Vi substantierar arbetet med en prototypimplementation av KALPIS och visar dess användbarhet genom ett antal icketriviala exempel. Dessutom ger vi en komplett formalisering av de två systemen, inklusive operativ semantik och typsystem för KALPIS och en lokalt inverterbar tolkning och ekvationskaraktärisering av RRARR. Slutligen ger vi en kompositionell översättning från KALPIS till RRARR, vilket motiverar oss att kalla det ett Arrow-metaspråk. Det mesta av formaliseringen är mekaniserad med hjälp av bevisassistenten Agda.