Reference. Dependent Type Refinements for Futures

Type refinements combine the compositionality of typechecking with the expressivity of program logics, offering a synergistic approach to program verification. In this paper we apply dependent type refinements to SAX, a futures-based process calculus that arises from the Curry-Howard interpretation of the intuitionistic semi-axiomatic sequent calculus and includes unrestricted recursion both at the level of types and processes. With our type refinement system, we can reason about the partial correctness of SAX programs, complementing prior work on sized type refinements that supports reasoning about termination. Our design regime synthesizes the infinitary proof theory of SAX with that of bidirectional typing and Hoare logic, deriving some standard reasoning principles for data and (co)recursion while enabling information hiding for codata. We prove syntactic type soundness, which entails a notion of partial correctness that respects codata encapsulation. We illustrate our language through a few simple examples.

Cite

Cite as @somayyajula-2023-dependent (helia, typst) · \cite{somayyajula-2023-dependent} (LaTeX)
BibTeX
bibtex · 1 line
@article{somayyajula-2023-dependent, title={Dependent Type Refinements for Futures}, volume={Volume 3 - Proceedings of...}, ISSN={2969-2431}, url={http://dx.doi.org/10.46298/entics.12286}, DOI={10.46298/entics.12286}, journal={Electronic Notes in Theoretical Informatics and Computer Science}, publisher={Centre pour la Communication Scientifique Directe (CCSD)}, author={Somayyajula, Siva and Pfenning, Frank}, year={2023}, month=Nov }
hayagriva YAML (typst)
yaml · 16 lines
somayyajula-2023-dependent:
  type: article
  title: Dependent Type Refinements for Futures
  author:
  - Somayyajula, Siva
  - Pfenning, Frank
  date: 2023-11
  url: http://dx.doi.org/10.46298/entics.12286
  serial-number:
    doi: 10.46298/entics.12286
    issn: 2969-2431
  parent:
    type: periodical
    title: Electronic Notes in Theoretical Informatics and Computer Science
    publisher: Centre pour la Communication Scientifique Directe (CCSD)
    volume: Volume 3 - Proceedings of...
Cites 72 works (6 here)
With notes (6)

Data Layout from a Type-Theoretic Perspective deyoung-2023-data

The specifics of data layout can be important for the efficiency of functional programs and interaction with external libraries. In this paper, we develop a type-theoretic approach to data layout that could be used as a typed intermediate language in a compiler or to give a programmer more control. Our starting point is a computational interpretation of the semi-axiomatic sequent calculus for intuitionistic logic that defines abstract notions of cells and addresses. We refine this semantics so addresses have more structure to reflect possible alternative layouts without fundamentally departing from intuitionistic logic. We then add recursive types and explore example programs and properties of the resulting language.
DOI · arXiv

Bidirectional Typing dunfield-2021-bidirectional

Bidirectional typing combines two modes of typing: type checking, which checks that a program satisfies a known type, and type synthesis, which determines a type from the program. Using checking enables bidirectional typing to support features for which inference is undecidable; using synthesis enables bidirectional typing to avoid the large annotation burden of explicitly typed languages. In addition, bidirectional typing improves error locality. We highlight the design principles that underlie bidirectional type systems, survey the development of bidirectional typing from the prehistoric period before Pierce and Turner’s local type inference to the present day, and provide guidance for future investigations.
DOI · arXiv

Iris from the ground up: A modular foundation for higher-order concurrent separation logic jung_etal_iris_ground_up_2018

Iris is a framework for higher-order concurrent separation logic, which has been implemented in the Coq proof assistant and deployed very effectively in a wide variety of verification projects. Iris was designed with the express goal of simplifying and consolidating the foundations of modern separation logics, but it has evolved over time, and the design and semantic foundations of Iris itself have yet to be fully written down and explained together properly in one place. Here, we attempt to fill this gap, presenting a reasonably complete picture of the latest version of Iris (version 3.1), from first principles and in one coherent narrative.
PDF · DOI · pldb

Integrating Linear and Dependent Types krishnaswami_integrating_2015

In this paper, we show how to integrate linear types with type dependency, by extending the linear/non-linear calculus of Benton to support type dependency.
PDF · DOI · pldb

Dependent session types via intuitionistic linear type theory toninho-2011-dependent

DOI

Dependent types in practical programming xi-1999-dependent

PDF · DOI · pldb
External (66)
somayyajula-2023-dependent reference entries/refs/somayyajula-2023-dependent/somayyajula-2023-dependent.hel