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
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.
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.
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.
Integrating Linear and Dependent Types krishnaswami_integrating_2015
Dependent session types via intuitionistic linear type theory toninho-2011-dependent
Dependent types in practical programming xi-1999-dependent
External (66)
- How to safely use extensionality in Liquid Haskell (2022)
- Replicate, Reuse, Repeat: Capturing Non-Linear Communication via Session Types and Graded Modal Types (2022)
- Polarized Subtyping (2022)
- Nested Session Types (2022)
- Coinduction inductively: mechanizing coinductive proofs in Liquid Haskell (2022)
- Type-Based Termination for Futures (2022)
- Foundations of regular coinduction (2021)
- Refinement Types: A Tutorial (2021)
- A Decade of Dependent Session Types (2021)
- SteelCore: an extensible concurrent separation logic for effectful dependently typed programs (2020)
- Semi-Axiomatic Sequent Calculus (2020)
- Session Types with Arithmetic Refinements (2020)
- Actris: session-type based reasoning in separation logic (2019)
- Towards Races in Linear Logic (2019)
- Value-dependent session design in a dependently typed language (2019)
- Circular Proofs as Session-Typed Processes: A Local Validity Condition (2019)
- Label-dependent session types (2019)
- Effpi: A Toolkit for Verified Message-Passing Programs in Dotty (2019)
- Parallel complexity analysis with temporal session types (2018)
- Program Verification by Coinduction (2018)
- Depending on Session-Typed Processes (2018)
- Modeling Concurrency in Dafny (2018)
- Mixed Inductive-Coinductive Reasoning Types, Programs and Logic (2018)
- Dependent Session Types (2017)
- Refinement Reflection: Complete Verification with SMT (2017)
- Certifying data in multiparty session types (2016)
- Well-definedness and observational equivalence for inductive–coinductive programs (2016)
- Type Theory based on Dependent Inductive and Coinductive Types (2016)
- Practical Foundations for Programming Languages (2016)
- A Coinduction Proof Rule for Hoare Doubles (2016)
- Deductive Verification of Parallel Programs Using Why3 (2015)
- Balanced polymorphism and linear lambda calculus (2015)
- Communicating State Transition Systems for Fine-Grained Concurrent Resources (2014)
- Co-induction simply (2014)
- Refinement Types for Haskell (2014)
- Higher-Order Processes, Functions, and Sessions: A Monadic Integration (2013)
- Copatterns (2013)
- Abstract Refinement Types (2013)
- Deterministic parallelism via liquid effects (2012)
- Correct-by-Construction Concurrency: Using Dependent Types to Verify Implementations of Effectful Resource Usage Protocols (2010)
- Subtyping, Declaratively (2010)
- Separation and information hiding (2009)
- Mixing Induction and Coinduction (2009)
- A Hoare Logic for Call-by-Value Functional Programs (2008)
- Liquid types (2008)
- Des types aux assertions logiques : preuve automatique ou assistée de propriétés sur les programmes fonctionnels (2007)
- Relating State-Based and Process-Based Concurrency through Linear Logic (2006)
- Coinductive Big-Step Operational Semantics (2006)
- A Sequent Calculus for Type Theory (2006)
- Cyclic Proofs for First-Order Logic with Inductive Definitions (2005)
- Resources, Concurrency and Local Reasoning (2004)
- Tridirectional typechecking (2004)
- Induction and Co-induction in Sequent Calculus (2004)
- Towards a Theory of Parallel Programming (2002)
- Local type inference (2000)
- Call-by-Push-Value: A Subsuming Paradigm (1999)
- Hidden coinduction: behavioural correctness proofs for objects (1999)
- Subtypes for specifications: predicate subtyping in PVS (1998)
- Coinductive Axiomatization of Recursive Type Equality and Subtyping (1997)
- Subtyping dependent types (1996)
- On the Meanings of the Logical Constants and the Justifications of the Logical Laws (1996)
- Telescopic mappings in typed lambda calculus (1991)
- MULTILISP: a language for concurrent symbolic computation (1985)
- Reasoning about recursively defined data structures (1978)
- Program invariants as fixed points (1977)
- Proof of correctness of data representations (1972)