@article{10.1145/3434290,
    Abstract = {Compact closed categories include objects representing higher-order functions and are well-established as models of linear logic, concurrency, and quantum computing. We show that it is possible to construct such compact closed categories for conventional sum and product types by defining a dual to sum types, a negative type, and a dual to product types, a fractional type. Inspired by the categorical semantics, we define a sound operational semantics for negative and fractional types in which a negative type represents a computational effect that ``reverses execution flow'' and a fractional type represents a computational effect that ``garbage collects'' particular values or throws exceptions. Specifically, we extend a first-order reversible language of type isomorphisms with negative and fractional types, specify an operational semantics for each extension, and prove that each extension forms a compact closed category. We furthermore show that both operational semantics can be merged using the standard combination of backtracking and exceptions resulting in a smooth interoperability of negative and fractional types. We illustrate the expressiveness of this combination by writing a reversible SAT solver that uses backtracking search along freshly allocated and de-allocated locations. The operational semantics, most of its meta-theoretic properties, and all examples are formalized in a supplementary Agda package.},
    Address = {New York, NY, USA},
    Author = {Chen, Chao-Hong and Sabry, Amr},
    File = {A computational interpretation of compact closed categories- reversible programming with negative and fractional types - 3434290 - a - d.pdf},
    Journal = {Proc. ACM Program. Lang.},
    Keywords = {Termination Proofs, Higher-Order Reversible Programming, Duality of Computation, Abstract Machines, Type Isomorphisms},
    Month = {January},
    Number = {POPL},
    Publisher = {Association for Computing Machinery},
    Title = {A Computational Interpretation of Compact Closed Categories: Reversible Programming with Negative and Fractional Types},
    URL = {https://doi.org/10.1145/3434290},
    Volume = {5},
    Year = {2021},
    articleno = {9},
    bdsk-url-1 = {https://doi.org/10.1145/3434290},
    date-added = {2021-01-05 10:53:24 +0100},
    date-modified = {2021-01-05 10:53:24 +0100},
    issue_date = {January 2021},
    numpages = {29},
    doi = {10.1145/3434290}
}

@article{10.1145/3434290, Abstract = {Compact closed categories include objects representing higher-order functions and are well-established as models of linear logic, concurrency, and quantum computing. We show that it is possible to construct such compact closed categories for conventional sum and product types by defining a dual to sum types, a negative type, and a dual to product types, a fractional type. Inspired by the categorical semantics, we define a sound operational semantics for negative and fractional types in which a negative type represents a computational effect that reverses execution flow'' and a fractional type represents a computational effect thatgarbage collects'' particular values or throws exceptions. Specifically, we extend a first-order reversible language of type isomorphisms with negative and fractional types, specify an operational semantics for each extension, and prove that each extension forms a compact closed category. We furthermore show that both operational semantics can be merged using the standard combination of backtracking and exceptions resulting in a smooth interoperability of negative and fractional types. We illustrate the expressiveness of this combination by writing a reversible SAT solver that uses backtracking search along freshly allocated and de-allocated locations. The operational semantics, most of its meta-theoretic properties, and all examples are formalized in a supplementary Agda package.}, Address = {New York, NY, USA}, Author = {Chen, Chao-Hong and Sabry, Amr}, File = {A computational interpretation of compact closed categories- reversible programming with negative and fractional types - 3434290 - a - d.pdf}, Journal = {Proc. ACM Program. Lang.}, Keywords = {Termination Proofs, Higher-Order Reversible Programming, Duality of Computation, Abstract Machines, Type Isomorphisms}, Month = {January}, Number = {POPL}, Publisher = {Association for Computing Machinery}, Title = {A Computational Interpretation of Compact Closed Categories: Reversible Programming with Negative and Fractional Types}, URL = {https://doi.org/10.1145/3434290}, Volume = {5}, Year = {2021}, articleno = {9}, bdsk-url-1 = {https://doi.org/10.1145/3434290}, date-added = {2021-01-05 10:53:24 +0100}, date-modified = {2021-01-05 10:53:24 +0100}, issue_date = {January 2021}, numpages = {29}, doi = {10.1145/3434290} }