First-class Logical Refinement Types for Scala
summary
Prototype implements first-class logical refinement types for Scala, e.g. {x: Int | x > 0}, integrated into the compiler with flow-sensitive inference only when needed and capture checking to forbid mutable state in predicates. A custom solver does normalization and transitivity; heavy proofs can use Stainless integration. Supports runtime-checked casts, gradual runtime-check mode, and pattern-match checks. Demonstrations include sized zip/concat specs, color-component bounds, and a memoized Fibonacci equivalence proof. Measured compile overhead peaks at 13% overhead and is <4% when unused.
AI-written summary · about
chapters (21)
- 0:00Introduction and speaker background
- 0:26What are refinement types
- 1:50Syntax and desugaring examples
- 2:52Practical example with zip method
- 4:36Why not just use assertions
- 6:20Real-world example with Fansi library
- 7:21Performance optimization with refinement types
- 8:23Comparison with existing Scala libraries
- 9:25Goals of first-class refinement types
- 11:09Implementation details and constraints
- 12:35Capture checking and purity
- 13:17Type inference with refinement types
- 14:40Flow-sensitive typing examples
- 15:43Subtyping and solver design
- 17:31Runtime checks and gradual typing
- 19:17Integration with Stainless verifier
- 21:02Dependent maps and Fibonacci example
- 23:11Compile-time overhead measurements
- 24:15Future work and Scala integration
- 25:40How to try the prototype today
- 26:25Q&A session
