betaFeedback

WorksComputer Science

CIRT: Calculus of Inductive Refinement Types

Abstract

Refinement types are a powerful mechanism for statically verifying properties of programs. They have been successfully integrated into practical languages such as Haskell, Scala, and Rust. However, their metatheory is not yet fully understood. In this paper we present the first semantic model for a refinement type system that supports the full feature combination of subtyping, SMT-style equality, impredicative polymorphism, and (stratified) inductive types. Interactions between these features have led to inconsistencies in the past, and existing formalizations of refinement type systems omit at least one of them. We present a realizability model based on partial equivalence relations (PERs) over a Scott domain, which overcomes these obstacles. We use our model to prove the consistency of a core refinement type system and to give a semantic account of the annotation-independence property of refinement types. Our semantics uses two interpretations: a refined one, which interprets types and their refinements as PERs; and an unrefined one, consisting of complete uniform PERs with a bottom element (CUPERs), which models computational behaviour independently of refinements. We extend the model to positive and stratified inductive types, showing that both are consistent in the presence of impredicativity.

Introduction

Refinement types [41] extend a host language with logical predicates that constrain the values inhabiting types. For instance, the type {x:Int∣x≠0}\{x:\mathrm{Int} \mid x \ne0\} refines the type of integers, allowing us to statically forbid division by zero. Such systems have been integrated into practical languages, including Haskell (Liquid Haskell) [67], Scala (Stainless) [34], and Rust (Flux) [43]. Unlike most foundational type theories, refinement type systems were developed primarily as engineering artifacts: their design was driven by the goal of verifying existing programs with minimal disruption to the underlying language, often accepting a degree of “soundiness” [46] in return for practicability.

Despite their practical success, the metatheory of refinement types remains only partially understood. Over the last decade practical refinement type systems have accumulated several features that interact in non-trivial ways at the semantic level, and potentially lead to inconsistencies if not handled with care. For example, 1) subtyping combined with 2) unrefined equality (i.e. an SMT-style equality that we describe in Section 2.1.2) and function extensionality has led to inconsistencies in both Liquid Haskell and F* [49]. Additionally, 3) impredicative polymorphism combined with some classes of 4) non-strictly positive inductive definitions as supported in Liquid Haskell can be shown to be inconsistent in standard type-theoretic settings [21].

The desire to prevent inconsistency has led to several formalizations of refinement type systems. For example, Swamy et al. [64] prove normalization for a model of F*, but their calculus has no impredicative polymorphism. Hamza et al. [34] prove normalization for a model of Stainless which lacks subtyping. Ghalayini and Krishnaswami [30] construct a model for a system with explicit refinement types, but do not consider inductive types. Finally, Borkowski et al. [14] prove type soundness for a model of Liquid Haskell without higher-order unrefined equalities. As a result, there is currently no single semantic account that combines the four key features of refinement types. If we truly want to understand refinement types and prove their soundness, we need a semantic model that supports all of these features simultaneously.

Nevertheless, discovering such a semantic model is challenging. The set-theoretic semantics given by Ghalayini and Krishnaswami [30], which interprets each refined type as a subset of the interpretation of its erased type, does not extend to impredicative polymorphism, which has no set-theoretic model in classical set theory [57]; subtyping and unrefined equality further constrain how a model can interpret refined types, as we discuss in § 2.4. Second, modeling the non-strictly-positive inductive types of Liquid Haskell is not straightforward, as they do not have a direct analogue in type theory.

In this paper we present a model based on partial equivalence relations (PERs) over a Scott domain. In broad strokes, our model follows much of the standard structure of PER models: types are interpreted as PERs over the domain and terms as well-defined elements of these PERs [48]. Thus, the semantic counterpart of typing is membership in the domain of the PER, and equality is interpreted as the PER itself. The subtyping relation is interpreted as inclusions between PERs, so no cast operations are needed. We will show that the notion of unrefined equality used in refinements may also be modelled by the unrefined PER interpreting a type. Finally, the PERs offer enough structure to model impredicative polymorphism in the usual manner, viz. as set-theoretic intersection over the set of all PERs.

The realizability model that we designed interprets the key features of refinement type systems and is deliberately elementary so that it can serve as a reference model against which candidate features are checked before they are implemented. Concretely, our contributions are:

  • A model of refinement types as they are, not as they are convenient to model. We isolate four features of practical refinement type systems (implicit subtyping, SMT-style unrefined equality, impredicative polymorphism, and non-standard inductive types) whose interaction is precisely what has caused soundness bugs in real systems, and we model their combination without simplifying any of them away. No existing formalization supports all four (§ 2.3).

  • Modeling unrefined equality. Every type receives a refined interpretation as a PER, included in an unrefined interpretation as a CUPER over a Scott domain (§ 4 to § 7). This model explains how the SMT-style equality interacts with higher-order refined terms. So, our model does not merely avoid the extensionality inconsistencies of Liquid Haskell and F∗F^{*}, it explains them: they validate refined equalities that cannot coexist with unrefined equality (Section 2.1.2).

  • Consistency of positive and stratified inductive types under impredicativity (§ 8 and corollary 2). The model shows that positive and stratified types are consistent in a refined setting even with impredicative polymorphism. Our techniques are not specific to refinement types: they can be adapted to any type theory that admits a realizability model, for example MLTT. Ours is moreover the first denotational semantics of stratified indexed types, previously accounted for only by normalization or step-indexing arguments [34, 40]. The interpretation of an inductive type is an initial algebra: folding and unfolding form an isomorphism, and the eliminator may expose the recursive arguments, in contrast to Mendler-style weakly initial algebras. So, both positive and stratified types share a single, uniform introduction and elimination discipline (§ 8). The message is constructive: positive and stratified indexed types are a straightforward addition to refinement systems.

The rest of the paper is structured as follows. In § 2 we present the key features of the system, compare them with existing formalizations, and explain why they require a semantic treatment beyond set-theoretic models. § 5 to § 8 develop the formal construction of the model CIRT and prove consistency. Finally, we present related works and conclude.

Every theorem in this paper is accompanied by a detailed proof in the supplementary material.

Refinement types: Syntax & Semantics

We start (§ 2.1) by presenting the key ingredients of practical refinement type systems that are relevant for the semantic development of this paper. Next (§ 2.3), we describe how these features are formalized in the literature and summarize their respective limitations. Finally (§ 2.4), we derive from these features the requirements that guide the design of our model.

Core Features of refinement type systems

A refinement type {x:τ∣ϕ}\{x:\tau\mid\phi\} consists of a base type τ\tau, a proposition ϕ\phi that constrains the values inhabiting τ\tau as the ones satisfying ϕ\phi. The language of propositions ϕ\phi includes boolean-valued expressions of the host language, equality predicates over terms (including equality that may not be decidable), and closure under standard logical connectives. Refinements are not restricted to base types, but may also appear throughout the type structure, for example in (dependent) function types, polymorphic types, and inductive types.

A key aspect of refinement type systems is that refinements act as an annotation layer over an existing language: they enrich static checking while leaving the operational semantics unchanged. This design enables deployment without runtime overhead, and further ensures that the behaviour of a program does not depend on refinement annotations. We call the independence of program behavior from verification annotations the annotation-independence property.

Refinement type systems are extended with several orthogonal mechanisms that interact in non-trivial ways at the semantic level. Next, we present the four main ingredients that appear in practical systems and that are relevant for the semantic issues studied in this paper.

2.1.1 Subtyping. A refinement that arbitrarily constrains the elements of a type may be naturally regarded as a subtype of another type; for example, positive integers are integers. This allows a term to be used at a less-refined or unrefined type without requiring explicit casts. Semantically, subtyping expresses inclusion between the meanings of types: every value inhabiting a subtype must also inhabit its supertype. Importantly, subtyping is implicit, meaning that, as presented in the rule Tm-Sub below, no type casts are required to use a term at a supertype. Function types, in turn, satisfy the standard contravariant/covariant subtyping rule Sub-Fun [18, 19].

Γ⊢t:τΓ⊢τ⪯σΓ⊢t:σ\frac{\Gamma\vdash t:\tau\qquad\Gamma\vdash\tau\preceq\sigma}{\Gamma\vdash t:\sigma}
Γ⊢σ⪯τΓ⊢ρ⪯πΓ⊢τ→ρ⪯σ→π\frac{\Gamma\vdash\sigma\preceq\tau\qquad\Gamma\vdash\rho\preceq\pi}{\Gamma\vdash\tau\to\rho\preceq\sigma\to\pi}

2.1.2 Unrefined equality. Refinements often use equality as an unrefined relation on terms, including terms of function type. This reflects the view of the SMT solver, which operates on a representation of these unrefined terms, and derives equalities without refined type information [68].

This notion of unrefined equality is the cause of many subtle soundness questions. For example, function extensionality was introduced in both Liquid Haskell [66] and F* [49] and later shown to be inconsistent. The inconsistency arises from the interaction between unrefined equality and subtyping: in a typed setting, equality is indexed by type and extensionality can be formulated so as to be harmless; with unrefined equality, the same axiom has greater force and Vazou and Greenberg [66] showed that admitting it leads to a proof of false.

2.1.3 Parametric Polymorphism. Most refinement type systems are built on top of languages that have parametric polymorphism, such as Haskell or Scala. We model such languages through impredicative type quantification à la System F [31, 58]. Thus, a quantified type has the same kind as the types over which it quantifies. For example, the type ∀X:Ty.X\forall\mathsf{X}:\mathsf{Ty}.\mathsf{X} itself has kind Ty\mathsf{Ty}, and may therefore be instantiated with arbitrary types of kind Ty\mathsf{Ty}, including itself. predicative polymorphism, where the quantified type lives at a strictly higher level than the types it quantifies over, in a stratified hierarchy [44].

Refinement types should interact smoothly with polymorphism: it should be possible to refine type variables, instantiate them with arbitrary types, and quantify over indexed type families.

Non-standard Inductive Types

To preserve consistency, general recursion must be excluded from a system of refinement types. However, simply replacing it with some flavour of structural recursion does not suffice, as it is well-known that recursive type definitions can also be used to encode general recursion [36, 54]. The canonical counterexample is:

data Bad where MkBad :: (Bad → Void) → Bad

where Void is the empty type. This type enables encoding self-application and yields a contradiction:

bad :: Bad → Void          worst :: Void
bad (MkBad f) = f (MkBad f) worst = bad (MkBad bad)

This term is a typed instance of Curry’s paradox; that admitting such negative datatypes breaks normalisation—and hence consistency—in the second-order λ\lambda-calculus is due to Mendler [53]. While this code is totally valid Haskell, it is rightfully rejected by Liquid Haskell, which aims to construct a consistent refinement type system. However, strict positivity is too strong a restriction: positive types and stratified negative types could be admitted without compromising consistency.

Positive types allow the inductive type to occur negatively, provided that each negative occurrence is itself under a negative function arrow; a canonical example is Hofmann’s routine type [12, 39]:

data Rou where Over :: Rou; Next :: ((Rou → [Nat]) → [Nat]) → Rou

While it is not immediately obvious, the class of positive types can also lead to inconsistencies in dependently typed systems built on CIC [21]. In contrast, our denotational model proves that they are harmless in a refinement type system.

Stratified types, introduced by Jacob-Rao et al. [40] and also used by Hamza et al. [34], are indexed inductive types whose recursive occurrences appear at ‘strictly smaller indices’ both in positive and negative positions, ensuring well-foundedness. As an example, consider the shallow embedding of the simply-typed lambda calculus (STLC) in Liquid Haskell (from [25, 26]) where the data types Typ and Val, respectively, embed types and values of STLC:

data Typ = TIota | TArr Typ Typ
data Val where {-@ stratified Val @-}
{-@ VIota :: Int → Ix Val TIota @-}
VIota :: Int → Val
{-@ VArr :: t:Typ → u:Typ → (Ix Val t → Ix Val u) → Ix Val (TArr t u) @-}
VArr :: Typ → Typ → (Val → Val → Val) → Val

The type Typ contains the base type (TIota) and the function type (TArr). The family Val is indexed by such types; intuitively, Val t contains exactly the values of object-language type t. The Ix annotation is Liquid Haskell’s notation for attaching such an index to a datatype.

Ignoring the refinement annotations, Val can be viewed as the solution of the recursive domain equation of the untyped λ\lambda-calculus, which is sufficiently expressive to encode general recursion. The refinement annotations, however, equip values with a type index. A value indexed by TIota must be constructed using VIota, whereas a value indexed by TArr t u must be constructed using VArr. The recursive occurrences of Val appearing in the argument of VArr are indexed by t and u, which are strict subcomponents of the result index TArr t u. Consequently, recursive occurrences only appear at smaller indices, allowing the family Val to be interpreted by induction on the structure of the index rather than as an arbitrary recursive domain equation. The stratified Val annotation enables the stratification checker to verify the well-formedness of the type: as explained in § 9, it checks that the indices of the recursive occurrences are indeed strictly smaller than the index of the result type, and accepts the definition of Val⁡\operatorname{Val}.

Existing formalizations

We give a high-level overview of existing formalizations of refinement type systems, and the extent to which they model the features described in § 2.1. Table 1 summarizes the four formalizations that we discuss: μF⋆\mu F^\star [64] that models F⋆F^\star, System FR [34] that models Stainless, λRF\lambda_{RF} [14] that models Liquid Haskell, and explicit refinement types [30] that models a system with explicit refinement types. For each system we indicate the extent to which it supports the four features of refinement types, and the semantics used to model them.

SystemModelsSubtypingEqualityPolymorphismInductive typesConstruction
μF⋆\mu F^\star(F⋆)(F^\star)YesBase typesPredicativeNoNormalization
System FR(Stainless)NoReductionYesStep-IndexedNormalization
λRF\lambda_{RF}(Liquid Haskell)YesBase typesYes, LimitedNoSafety
Explicit Refinement TypesNoTyped βη\beta\etaNoNoSet model

Table 1. High level comparison of the formalizations of refinement type systems of: μF⋆\mu F^\star [64], System FR [34], λRF\lambda_{RF} [14], and explicit refinement types [30].

Subtyping. Many formal models of refinement types, such as explicit refinement types and System FR, do not include explicit subtyping. Instead they rely on a reflection rule:

Γ⊢t ⁣: ⁣τΓ⊢ϕ(t) okΓ⊢t ⁣: ⁣{x ⁣: ⁣τ∣ϕ}Tm-Refl\frac{\Gamma\vdash t\!:\!\tau\qquad\Gamma\vdash\phi(t)\ \mathit{ok}}{\Gamma\vdash t\!:\!\{x\!:\!\tau\mid\phi\}} \quad\mathsf{Tm\text{-}Refl}

Subtyping is then implicitly possible, as whenever ϕ\phi implies ψ\psi, any term Γ⊢t ⁣: ⁣{x ⁣: ⁣τ∣ϕ}\Gamma\vdash t\!:\!\{x\!:\!\tau\mid\phi\} is also a term of type Γ⊢t ⁣: ⁣{x ⁣: ⁣τ∣ψ}\Gamma\vdash t\!:\!\{x\!:\!\tau\mid\psi\}. However, this is not equivalent to the explicit formulation. To see why, suppose we have a free variable f ⁣: ⁣Int→{x ⁣: ⁣Int∣x≥0}f\!:\!\mathrm{Int} \to\{x\!:\!\mathrm{Int} \mid x \ge0\} which we wish to use as a function of type {x ⁣: ⁣Int∣x≥0}→Int\{x\!:\!\mathrm{Int} \mid x \ge0\} \to\mathrm{Int}. This cannot be derived from reflection alone, as refinement information cannot flow through type formers. The eta-expansion λx. f⋅x\lambda x.\,f \mathbin{\cdot} x does have this type, a technique that goes back to Barendregt et al. [11], but it is a different term from ff. Explicit subtyping, as presented in section 2.1.1, is instead designed with specific rules for each type former, e.g. contravariance on the domain of the function.

Equality. Most systems, including those of λRF\lambda_{RF} and μF⋆\mu F^\star, restrict equality to base types, such as Int\mathrm{Int}. This is sound as the refined equality coincides with the unrefined one on base types. However, it is too restrictive, as it rules out equalities between higher-order terms entirely.

In System FR equality is reduction-based, so that t≡ut \equiv u if and only if tt and uu reduce to a common value. This is untyped and by consequence also unrefined, but too fine-grained. For example, reduction almost always uses weak head normal form, and natural equalities at higher-order types do not hold, e.g. making {x ⁣: ⁣Unit∣λy. 1+2≡λy. 3}→⊥\{x\!:\!\mathrm{Unit} \mid\lambda y.\,1+2 \equiv\lambda y.\,3\} \to\bot inhabited. Unfortunately, such equalities arise naturally in refinement types when encoding the equivalence of terminating functional programs.

In explicit refinement types equality is the typed βη\beta\eta-equality of the underlying simply-typed terms; Ghalayini and Krishnaswami [30] already suggest moving to a semantics based on partial equivalence relations, which our model also uses.

Polymorphism. λRF\lambda_{RF} allows the refinement of type variables, but they can only be instantiated with base types. Similarly, the calculus of System FR includes indexed types, but quantification ranges only over fully applied types. As the system of μF⋆\mu F^\star is dependent, they only have predicative polymorphism: ∀x ⁣: ⁣Ty. Int\forall x\!:\!\mathrm{Ty}.\,\mathrm{Int} is only a type at the strictly higher level than Ty\mathrm{Ty}, and hence it cannot be instantiated with itself. Finally, in explicit refinement types there is no polymorphism.

Inductive types. In System FR they have step-indexed inductive types, which are similar to stratified types in the sense of Jacob-Rao et al. [40], but they do not have a direct analogue of positive types. In the rest of the systems there are no inductive types at all, so no direct analogue of either positive or stratified types.

Design requirements for a realizability model

The simplest models of type theories are set-theoretic: types are interpreted as sets and terms as elements of these sets [37]. The core features described above impose three requirements on the design of our model.

The first requirement is support for impredicative polymorphism. Set-theoretic models of impredicative polymorphism cannot exist because of size issues [57], at least not within classical logic [55]. So our model interprets types as PERs over a fixed domain: these form a set, so type quantification can be interpreted as an intersection over them.

The second requirement is that subtyping be interpreted as inclusion. It fails in models that interpret each function type as the set of all functions between the interpretations of its domain and codomain: in such a model, subtyping between function types requires cast operations. For example, type Int→Int\mathrm{Int} \to\mathrm{Int} is interpreted as the set of total functional relations R⊆Z×ZR \subseteq\mathbb{Z} \times\mathbb{Z}. Computationally, this type is a subtype of {x ⁣: ⁣Int∣x≥0}→Int\{x\!:\!\mathrm{Int} \mid x \ge0\} \to\mathrm{Int}. However, the latter is interpreted as the set of total functional relations R⊆N×ZR \subseteq\mathbb{N} \times\mathbb{Z}. The first set is not a subset of the second, as it contains pairs ⟨n,m⟩\langle n,m\rangle with n<0n < 0. To pass from one to the other we must cast, discarding the offending pairs. This example exhibits the general principle of coercive subtyping, which interprets each subtyping judgment as such a cast inserted at every use of subsumption [19]. This is unfortunate on two counts. First, the denotation of a term comes to depend not on the term alone but on the shape of its typing derivation; this is the classical coherence problem, and well-definedness can be recovered only by a theorem showing that all derivations of a judgment agree [16, 59]. Second, and more seriously for us, the cast genuinely removes elements, so that the meaning of a term comes to depend on the refinements appearing in its type, and annotation-independence is lost. Interpreting subtyping as inclusion requires no casts [18, 28, 48]. This is the case in the subset model of refinement types [51], where a refined type is a subset of its underlying type; our model has the same structure, with PERs in place of raw sets.

The third requirement is that the meaning of a term not depend on the refinements in its type, so that unrefined equality can observe its behavior outside them. Unrefined equality cannot be modeled in the presence of the cast operations described above: a cast removes elements from the interpretation of a functional term, and there is no way to recover them to check whether two terms are equal on their unrefined domain.

Our approach: PERs over a Scott domain

To meet these requirements, we use a model based on partial equivalence relations (PERs) over a Scott domain D\mathcal{D}. Our terms are interpreted as elements of D\mathcal{D} and types are interpreted as PERs over D\mathcal{D}, so that the semantic counterpart of typing is membership in a PER rather than membership in a set, and the equality is interpreted by the relation described by the PER itself. The subtyping relation is interpreted as set inclusion between PERs, so no cast operations are needed and annotation independence holds by construction. The unrefined equality can be modeled by carefully designing the unrefined PERs so that two terms are related by unrefined equality exactly when they are identified by the unrefined interpretation of their type. Finally, the PERs offer enough structure to model impredicative polymorphism as set-theoretic intersection over the set of all PERs.

Background

This section collects the domain-theoretic preliminaries on which our model rests. We follow the standard accounts of Davey and Priestley [23], Abramsky and Jung [5], Gunter [33], Amadio and Curien [8], and Streicher [63], to which we refer the reader for proofs.

Definition 1 (PER). A partial equivalence relation (PER) over a set AA is a symmetric and transitive relation over AA, in other words it is a set S⊆A×AS \subseteq A \times A such that (i) if ⟨a,b⟩∈S\langle a,b\rangle\in S then ⟨b,a⟩∈S\langle b,a\rangle\in S, and (ii) if ⟨a,b⟩∈S\langle a,b\rangle\in S and ⟨b,c⟩∈S\langle b,c\rangle\in S then ⟨a,c⟩∈S\langle a,c\rangle\in S.

Definition 2 (Domain of a PER). Given a PER SS over AA, its domain is the set of elements of AA which are related to themselves, i.e. dom⁡(S)={a∈A∣⟨a,a⟩∈S}\operatorname{dom}(S) = \{a \in A \mid\langle a,a\rangle\in S\}.

Definition 3 (Diagonal PER). The diagonal PER of any set AA is given by Δ(A)={⟨a,a⟩∣a∈A}\Delta(A) = \{\langle a,a\rangle\mid a \in A\}.

We will use the notation P ⁣E ⁣R(A)\mathcal{P\!E\!R}(A) to denote the set of PERs over AA. The PER structure will be used to model types, following a long line of work that interprets types as partial equivalence relations over a domain or a combinatory algebra [1, 7, 20]: the domain of a PER gives us the membership information, while the relation itself gives us the equality relation. While the definition of a PER does not give us reflexivity, it satisfies a weaker property that we call partial reflexivity: if ⟨a,b⟩∈S\langle a,b\rangle\in S then ⟨a,a⟩∈S\langle a,a\rangle\in S.

Definition 4 (Pointed PER). Let AA be a set with a distinguished element ⊥∈A\bot\in A. A pointed PER over AA is a PER S∈P ⁣E ⁣R(A)S \in\mathcal{P\!E\!R}(A) such that ⟨⊥,⊥⟩∈S\langle\bot,\bot\rangle\in S

The point will be used to model a nonterminating element, in the manner of Amadio [7].

Theorem 3.1 (Knaster-Tarski fixed point theorem). Let (L,≤)(L,\leq) be a complete lattice and f:L→Lf : L \to L be a monotone function. Then the set of fixed points of ff forms a complete lattice, and in particular there is a least fixed point lfp⁡f=⨆{x∈L∣f(x)≤x}\operatorname{lfp} f = \bigsqcup\{x \in L \mid f(x) \leq x\} and a greatest fixed point \operatorname{gfp} f = \bigsqcap\{x \in L \mid x \leq f(x)\} [65].

Definition 5 (Scott domain). A Scott domain is a complete partial order that is moreover ω\omega-algebraic and bounded-complete. It is ω\omega-algebraic when every element is the directed least upper bound of the countably many compact elements below it—an element cc is compact just if c≤⨆Xc \leq\bigsqcup X for a directed XX implies c≤xc \leq x for some x∈Xx \in X. It is bounded-complete when every subset that has an upper bound has a least upper bound [5, 33, 61].

Definition 6 (Chain of projections). A chain of projections on a Scott domain DD is an increasing family of continuous functions (πn)n∈N(\pi_n)_{n \in\mathbb{N}}, where each πn:D→D\pi_n : D \to D is idempotent and below the identity, with π0\pi_0 the constant function ⊥\bot, and which moreover satisfies ⨆nπn=id⁡\bigsqcup_n \pi_n = \operatorname{id}.

Given an element d∈Dd \in D we define the nn-th approximation of dd to be dn≔πn(d)d_n \coloneqq\pi_n(d).

In the rest of this section DD is a Scott domain equipped with a chain of projections. To model types we restrict attention to PERs that interact well with this order- and approximation structure, in the manner of the ideal and realizability models of MacQueen et al. [48], Abadi and Plotkin [1], and Amadio [7]. The uniformity condition below is the analogue for PERs of the uniform ideals.

Definition 7 (Complete, uniform, and pointed PERs).

  1. A PER S⊆D×DS \subseteq D \times D over a domain DD is complete whenever every directed subset {⟨ai,bi⟩}i∈I⊆S\{\langle a_i,b_i\rangle\}_{i\in I} \subseteq S (with respect to the product order on D×DD \times D) has a least upper bound ⟨⨆i∈Iai,⨆i∈Ibi⟩\langle\bigsqcup_{i\in I} a_i,\bigsqcup_{i\in I} b_i\rangle in SS.

  1. A PER S⊆D×DS \subseteq D \times D over a domain DD is uniform whenever for every ⟨a,b⟩∈S\langle a,b\rangle\in S and every n∈Nn \in\mathbb{N} we have ⟨πn(a),πn(b)⟩∈S\langle\pi_n(a),\pi_n(b)\rangle\in S.

  1. In this paper, a CUPER is a pointed, complete, and uniform PER. We write CUPER(D)\mathcal{CUPER}(D) for the collection of such PERs over a domain DD.

Completeness asks that a type be closed under the directed least upper bounds of D×DD \times D, so that the limits along which recursive computations converge remain within it and least fixed points can be interpreted there [7]. Uniformity asks instead that membership be stable under approximation: a related pair remains related at every stage πn\pi_n. In the presence of completeness, an element then belongs to a type exactly when all of its approximations do.

Recursive and inductive types will be interpreted as fixed points (§ 8). We adapt the contractive construction of Amadio [7]: because ⨆nπn=id\bigsqcup_n \pi_n = id, a CUPER is determined by its approximations, and a contractive operator—one that sharpens agreement by one approximation per unfolding—has a unique fixed point.

Definition 8 (Approximation of a relation). The nn-th approximation of a relation A⊆D×DA \subseteq D \times D is its pairwise image under the nn-th projection, An≜{⟨πn(v),πn(w)⟩∣⟨v,w⟩∈A}A_n \triangleq\{\langle\pi_n(v),\pi_n(w)\rangle\mid\langle v,w\rangle\in A\}.

References

  1. [1]Martín Abadi and Gordon D. Plotkin. 1990. A PER Model of Polymorphism and Recursive Types. In Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science (LICS ’90) (1990-06). 355–365. doi:10.1109/LICS.1990.113761
  2. [2]Andreas Abel. 1999. A Semantic Analysis of Structural Recursion. Diplomarbeit. Ludwig-Maximilians-Universität München.
  3. [3]Andreas Abel. 2008. Semi-Continuous Sized Types and Termination. Logical Methods in Computer Science 4, 2 (2008). doi:10.2168/LMCS-4(2:3)2008DOI
  4. [4]Andreas Abel. 2012. Type-Based Termination, Inflationary Fixed-Points, and Mixed Inductive-Coinductive Types. Electronic Proceedings in Theoretical Computer Science 77 (2012), 1–11. arXiv:1202.3496 [cs.LO] doi:10.4204/EPTCS.77.1DOI
  5. [5]Samson Abramsky and Achim Jung. 1994. Domain Theory. In Handbook of Logic in Computer Science (Vol. 3): Semantic Structures, S. Abramsky, Dov M. Gabbay, and T. S. E. Maibaum (Eds.). Oxford University Press, 1–168.
  6. [6]Robin Adams and Zhaohui Luo. 2010. Classical Predicative Logic-Enriched Type Theories. Annals of Pure and Applied Logic 161, 11 (2010), 1315–1345. doi:10.1016/j.apal.2010.04.005DOI
  7. [7]Roberto M. Amadio. 1991. Recursion over Realizability Structures. Information and Computation 91, 1 (1991), 55–85. doi:10.1016/0890-5401(91)90074-CDOI
  8. [8]Roberto M. Amadio and Pierre-Louis Curien. 1998. Domains and Lambda-Calculi. Number 46 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press. doi:10.1017/CBO9780511983504DOI
  9. [9]Stefan Banach. 1922. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicae 3, 1 (1922), 133–181. doi:10.4064/fm-3-1-133-181DOI
  10. [10]Henk Barendregt. 1991. Introduction to generalized type systems. Journal of Functional Programming 1, 2 (1991), 125–154. doi:10.1017/S0956796800020025DOI
  11. [11]Henk Barendregt, Mario Coppo, and Mariangiola Dezani-Ciancaglini. 1983. A Filter Lambda Model and the Completeness of Type Assignment. Journal of Symbolic Logic 48, 4 (1983), 931–940. jstor:2273659 doi:10.2307/2273659DOI
  12. [12]Ulrich Berger, Ralph Matthes, and Anton Setzer. 2019. Martin Hofmann’s Case for Non-Strictly Positive Data Types. In 24th International Conference on Types for Proofs and Programs (TYPES 2018) (2019) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 130), Peter Dybjer, José Espírito Santo, and Luís Pinto (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 1:1–1:22. doi:10.4230/LIPIcs.TYPES.2018.1DOI
  13. [13]Lars Birkedal, Rasmus Ejlers Møgelberg, and Rasmus Lerchedahl Petersen. 2007. Domain-Theoretical Models of Parametric Polymorphism. Theoretical Computer Science 388, 1-3 (2007), 152–172. doi:10.1016/j.tcs.2007.06.016DOI
  14. [14]Michael H. Borkowski, Niki Vazou, and Ranjit Jhala. 2024. Mechanizing Refinement Types. Proc. ACM Program. Lang. 8 (2024), 70:2099–70:2128. Issue POPL. doi:10.1145/3632912DOI
  15. [15]Matt Bovel, Viktor Kunčák, and Martin Odersky. 2026. First-Class Refinement Types for Scala. doi:10.48550/ARXIV.2605.08369DOI
  16. [16]Val Breazu-Tannen, Thierry Coquand, Carl A. Gunter, and Andre Scedrov. 1991. Inheritance as Implicit Coercion. Information and Computation 93, 1 (1991), 172–221. doi:10.1016/0890-5401(91)90055-7
  17. [17]Kim B. Bruce and John C. Mitchell. 1992. PER Models of Subtyping, Recursive Types and Higher-Order Polymorphism. In Proceedings of the 19th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (New York, NY, USA, 1992) (POPL ’92). ACM, 316–327. doi:10.1145/143165.143230DOI
  18. [18]Luca Cardelli. 1984. A Semantics of Multiple Inheritance. In Semantics of Data Types (Berlin, Heidelberg, 1984) (Lecture Notes in Computer Science, Vol. 173), Gilles Kahn, David B. MacQueen, and Gordon Plotkin (Eds.). Springer, 51–67. doi:10.1007/3-540-13346-1_2DOI
  19. [19]Luca Cardelli and Peter Wegner. 1985. On understanding types, data abstraction, and polymorphism. Comput. Surveys 17, 4 (1985), 471–523. doi:10.1145/6041.6042DOI
  20. [20]Felice Cardone. 1989. Relational Semantics for Recursive Types and Bounded Quantification. In Automata, Languages and Programming (Berlin, Heidelberg, 1989) (Lecture Notes in Computer Science, Vol. 372), Giorgio Ausiello, Mariangiola Dezani-Ciancaglini, and Simona Ronchi Della Rocca (Eds.). Springer, 164–178. doi:10.1007/BFb0035759
  21. [21]Thierry Coquand and Christine Paulin. 1990. Inductively Defined Types. In COLONG-88: International Conference on Computer Logic (Berlin, Heidelberg, 1990), Per Martin-Löf and Grigori Mints (Eds.). Springer, 50–66. doi:10.1007/3-540-52335-9_47DOI
  22. [22]Karl Crary. 1998. Admissibility of Fixpoint Induction over Partial Types. In Automated Deduction — CADE-15 (Berlin, Heidelberg, 1998), Claude Kirchner and Hélène Kirchner (Eds.). Springer, 270–285. doi:10.1007/BFb0054265
  23. [23]Brian A. Davey and Hilary A. Priestley. 2002. Introduction to Lattices and Order (2 ed.). Cambridge University Press. doi:10.1017/CBO978051809088DOI
  24. [24]Dimitrios J. Economou, Neel Krishnaswami, and Jana Dunfield. 2023. Focusing on Refinement Typing. ACM Trans. Program. Lang. Syst. 45, 4 (2023), 22:1–22:62. doi:10.1145/3610408DOI
  25. [25]Alessio Ferrarini and Niki Vazou. 2025. Large Elimination and Indexed Types in Refinement Types. In 31st International Conference on Types for Proofs and Programs (TYPES 2025), Book of Abstracts (Glasgow, Scotland, 2025). https://msp.cis.strath.ac.uk/types2025/abstracts/TYPES2025_paper33.pdf
  26. [26]Alessio Ferrarini, Niki Vazou, and Wouter Swierstra. 2026. PLEX: Normalization for Refinement Types. Proc. ACM Program. Lang. 10 (2026), 140:1321–140:1347. Issue OOPSLA1. doi:10.1145/3798248DOI
  27. [27]Tim Freeman and Frank Pfenning. 1991. Refinement Types for ML. SIGPLAN Not. 26, 6 (1991), 268–277. doi:10.1145/113446.113468DOI
  28. [28]Alain Frisch, Giuseppe Castagna, and Véronique Benzaken. 2008. Semantic Subtyping: Dealing Set-Theoretically with Function, Union, Intersection, and Negation Types. J. ACM 55, 4 (2008), 19:1–19:64. doi:10.1145/1391289.1391293DOI
  29. [29]Nicola Gambino and Peter Aczel. 2006. The Generalised Type-Theoretic Interpretation of Constructive Set Theory. Journal of Symbolic Logic 71, 1 (2006), 67–103. doi:10.2178/jsl/1140641163DOI
  30. [30]Jad Elkhaleq Ghalayini and Neel Krishnaswami. 2023. Explicit Refinement Types. Proc. ACM Program. Lang. 7 (2023), 195:187–195:214. Issue ICFP. doi:10.1145/3607837
  31. [31]Jean-Yves Girard. 1972. Interprétation fonctionelle et élimination des coupures de l’arithmétique d’ordre supérieur. Thèse d’État. Université Paris VII.
  32. [32]Jean-Yves Girard. 1989. Proofs and Types. Number 7 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press.
  33. [33]Carl A. Gunter. 1992. Semantics of Programming Languages: Structures and Techniques. MIT Press.DOI
  34. [34]Jad Hamza, Nicolas Voirol, and Viktor Kunčák. 2019. System FR: Formalized Foundations for the Stainless Verifier. Proc. ACM Program. Lang. 3 (2019), 166:1–166:30. Issue OOPSLA. doi:10.1145/3360592DOI
  35. [35]Robert Harper. 1992. Constructing Type Systems over an Operational Semantics. Journal of Symbolic Computation 14, 1 (1992), 71–84. doi:10.1016/0747-7171(92)90026-ZDOI
  36. [36]Robert Harper. 2016. Practical Foundations for Programming Languages (2 ed.). Cambridge University Press. doi:10.1017/CBO9781316576892DOI
  37. [37]Leon Henkin. 1950. Completeness in the theory of types. Journal of Symbolic Logic 15, 2 (1950), 81–91. doi:10.2307/2266967DOI
  38. [38]Brandon Hewer and Graham Hutton. 2024. Quotient Haskell: Lightweight Quotient Types for All. Proceedings of the ACM on Programming Languages 8, POPL (2024), 27:785–27:815. doi:10.1145/3632869DOI
  39. [39]Martin Hofmann. 1993. Non Strictly Positive Datatypes in System F. https://www.seas.upenn.edu/~sweirich/types/archive/1993/msg00027.html
  40. [40]Rohan Jacob-Rao, Brigitte Pientka, and David Thibodeau. 2018. Index-Stratified Types. In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018) (2018) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 108), Hélène Kirchner (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 19:1–19:17. doi:10.4230/LIPIcs.FSCD.2018.19
  41. [41]Ranjit Jhala and Niki Vazou. 2020. Refinement Types: A Tutorial. arXiv:2010.07763 [cs]. doi:10.48550/arXiv.2010.07763arxiv.org/abs/2010.07763
  42. [42]Kenneth Knowles and Cormac Flanagan. 2010. Hybrid Type Checking. ACM Trans. Program. Lang. Syst. 32, 2 (2010), 6:1–6:34. doi:10.1145/1667048.1667051DOI
  43. [43]Nico Lehmann, Adam T. Geller, Niki Vazou, and Ranjit Jhala. 2023. Flux: Liquid Types for Rust. Proc. ACM Program. Lang. 7 (2023), 169:1533–169:1557. Issue PLDI. doi:10.1145/3591283DOI
  44. [44]Daniel Leivant. 1991. Finitely stratified polymorphism. Information and Computation 93, 1 (1991), 93–113. doi:10.1016/0890-5401(91)90053-5DOI
  45. [45]Rodolphe Lepeigre. 2016. A Classical Realizability Model for a Semantical Value Restriction. In Programming Languages and Systems: 25th European Symposium on Programming, ESOP 2016 (Berlin, Heidelberg, 2016) (Lecture Notes in Computer Science, Vol. 9632), Peter Thiemann (Ed.). Springer, 476–502. doi:10.1007/978-3-662-49498-1_19
  46. [46]Benjamin Livshits, Manu Sridharan, Yannis Smaragdakis, Ondřej Lhoták, J. Nelson Amaral, Bor-Yuh Evan Chang, Samuel Z. Guyer, Uday P. Khedker, Anders Møller, and Dimitrios Vardoulakis. 2015. In Defense of Soundness: A Manifesto. Commun. ACM 58, 2 (2015), 44–46. doi:10.1145/2644805
  47. [47]Giuseppe Longo and Eugenio Moggi. 1991. Constructive natural deduction and its ω-set interpretation. Mathematical Structures in Computer Science 1, 2 (1991), 215–254. doi:10.1017/S0960129500001298DOI
  48. [48]David MacQueen, Gordon Plotkin, and Ravi Sethi. 1986. An Ideal Model for Recursive Polymorphic Types. Information and Control 71, 1-2 (1986), 95–130. doi:10.1016/S0019-9958(86)80019-5DOI
  49. [49]Kenji Maillard. 2018. Incompatibilities between Functional Extensionality, Subtyping, and Untyped Equality · Issue #1542 · FStarLang/FStar. GitHub. https://github.com/FStarLang/FStar/issues/1542
  50. [50]Ralph M. Morris. 1999. Monotone (Co)Inductive Types and Positive Fixed-Point Types. RAIRO - Theoretical Informatics and Applications 33, 4-5 (1999), 309–328. doi:10.1051/ita:1999120
  51. [51]Paul-André Melliès and Noam Zeilberger. 2015. Functional Type Theories Are Type Refinement Systems. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (2015) (POPL ’15). Association for Computing Machinery, 3–16. doi:10.1145/2676726.2676970
  52. [52]Nax Paul Mendler. 1991. Inductive Types and Type Constraints in the Second-Order Lambda Calculus. Annals of Pure and Applied Logic 51, 1-2 (1991), 159–172. doi:10.1016/0168-0072(91)90069-X
  53. [53]Nax Paul Mendler. 1987. Recursive Types and Type Constraints in Second-Order Lambda Calculus. In Proceedings of the Symposium on Logic in Computer Science (LICS ’87) (Ithaca, NY, USA, 1987). IEEE Computer Society Press, 30–36.
  54. [54]Benjamin C. Pierce. 2002. Types and Programming Languages. MIT Press.
  55. [55]Andrew M. Pitts. 1987. Polymorphism is set theoretic, constructively. In Category Theory and Computer Science, David H. Pitt, Axel Pigné, and David E. Rydeheard (Eds.). Vol. 283. Springer, Berlin, Heidelberg, 12–39. doi:10.1007/3-540-18508-9_18DOI
  56. [56]Andrew M. Pitts. 1996. Relational Properties of Domains. Information and Computation 127, 2 (1996), 66–90. doi:10.1006/inco.1996.0052DOI
  57. [57]John C. Reynolds. 1984. Polymorphism Is Not Set-Theoretic. In Semantics of Data Types (Berlin, Heidelberg, 1984), Gilles Kahn, David B. MacQueen, and Gordon Plotkin (Eds.). Springer, 145–156. doi:10.1007/3-540-13346-1_7DOI
  58. [58]John C. Reynolds. 1984. Types, Abstraction, and Parametric Polymorphism. In Information Processing 83: Proceedings of the IFIP 9th World Computer Congress, Paris, France, September 19–23, 1983 (Amsterdam, 1984), R. E. A Mason (Ed.). Elsevier Science Publishers B. V. (North-Holland), 513–523.
  59. [59]John C. Reynolds. 1980. Using Category Theory to Design Implicit Conversions and Generic Operators. In Semantics-Directed Compiler Generation (Berlin, Heidelberg, 1980) (Lecture Notes in Computer Science, Vol. 94), Neil D. Jones (Ed.). Springer, 211–258. doi:10.1007/3-540-10250-7_24DOI
  60. [60]Patrick M. Rondon, Ming Kawaguchi, and Ranjit Jhala. 2008. Liquid Types. SIGPLAN Not. 43, 6 (2008), 159–169. doi:10.1145/1379022.1375602DOI
  61. [61]Dana S. Scott. 1976. Data Types as Lattices. SIAM J. Comput. 5, 3 (1976), 522–587. doi:10.1137/0205037
  62. [62]Michael B. Smyth and Gordon D. Plotkin. 1982. The Category-Theoretic Solution of Recursive Domain Equations. SIAM J. Comput. 11, 4 (1982), 761–783. doi:10.1137/0211062DOI
  63. [63]Thomas Streicher. 2006. Domain-Theoretic Foundations of Functional Programming. World Scientific. doi:10.1142/6284DOI
  64. [64]Nikhil Swamy, Cătălin Hriţcu, Chantal Keller, Aseem Rastogi, Antoine Delignat-Lavaud, Simon Forest, Karthikeyan Bhargavan, Cédric Fournet, Pierre-Yves Strub, Markulf Kohlweiss, Jean-Karim Zinzindohoue, and Santiago Zanella-Béguelin. 2016. Dependent Types and Multi-Monadic Effects in F*. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (New York, NY, USA, 2016-01-11) (POPL ’16). Association for Computing Machinery, 256–270. doi:10.1145/2837614.2837655DOI
  65. [65]Alfred Tarski. 1955. A Lattice-Theoretical Fixpoint Theorem and Its Applications. Pacific J. Math. 5, 2 (1955), 285–309. doi:10.2140/pjm.1955.5.285DOI
  66. [66]Niki Vazou and Michael Greenberg. 2022. How to Safely Use Extensionality in Liquid Haskell. In Proceedings of the 15th ACM SIGPLAN International Haskell Symposium (New York, NY, USA, 2022-09-06) (Haskell 2022). Association for Computing Machinery, 13–26. doi:10.1145/3546819.3549919arxiv.org/abs/2103.02177
  67. [67]Niki Vazou, Eric L. Seidel, Ranjit Jhala, Dimitrios Vytiniotis, and Simon Peyton Jones. 2014. Refinement Types for Haskell. SIGPLAN Not. 49, 9 (2014), 269–282. doi:10.1145/2692915.2628161DOI
  68. [68]Niki Vazou, Anish D. Thakur, Vikraman Choudhary, Ryan G. Scott, Ryan R. Newton, Philip Wadler, and Ranjit Jhala. 2017. Refinement Reflection: Complete Verification with SMT. Proc. ACM Program. Lang. 2 (2017), 53:1–53:31. Issue POPL. doi:10.1145/3158141DOI

Paper details

vlnc:W_ast58wau
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents