NobleBlocks

Research indexPreprint

Explicit Refinement Types

Ghalayini, Krishnaswami

arXiv (Cornell University)23 Nov 2023Open access

NobleIDark:/48914/w1/20260515/73A5B3DADOI10.48550/arxiv.2311.13995

Free to read at the publisher

You can read the abstract here, or the full text at the publisher.

Read at the publisher

Abstract

We present λert, a type theory supporting refinement types with explicit proofs. Instead of solving refinement constraints with an SMT solver like DML and Liquid Haskell, our system requires and permits programmers to embed proofs of properties within the program text, letting us support a rich logic of properties including quantifiers and induction. We show that the type system is sound by showing that every refined program erases to a simply-typed program, and by means of a denotational semantics, we show that every erased program has all of the properties demanded by its refined type. All of our proofs are formalised in Lean 4.

Discussion

Topics

More

Suggest a correction or report