Roshan P. James, Zachary Sparks, Jacques Carette and Amr Sabry
In previous work, we developed a first-order, information- preserving, and reversible programming language Π founded on type isomorphisms. Being restricted to first-order types limits the expressiveness of the language: it is not possible, for example, to abstract common program fragments into a higher-level combinator. In this paper, we introduce a higher-order extension of Π based on the novel concept of fractional types 1/b. Intuitively, a value of a fractional type 1/v represents negative information. A function is modeled by a pair (1/v1 , v2 ) with 1/v1 representing the needed argument and v2 representing the result. Fractional values are first-class: they can be freely propagated and transformed but must ultimately ‐ in a complete program ‐ be offset by the corresponding amount of positive information.
The (submitted) paper is available, as well as the standalone Haskell code.