In gradual typing, different languages perform different dynamic type checks for the same program even though the languages have the same static type system. This raises the question of whether, given a gradually typed language, the combination of the translation that injects checks in well-typed terms and the dynamic semantics that determines their behavior sufficiently enforce the static type system of the language. Neither type soundness, nor complete monitoring, nor any other meta-theoretic property of gradually typed languages to date provides a satisfying answer.
In response, we present vigilance, a semantic analytical instrument that defines when the check-injecting translation and dynamic semantics of a gradually typed language are adequate for its static type system. Technically, vigilance asks if a given translation-and-semantics combination enforces the complete run-time typing history of a value, which consists of all of the types associated with the value. We show that the standard combination for so-called Natural gradual typing is vigilant for the standard simple type system, but the standard combination for Transient gradual typing is not. At the same time, the standard combination for Transient is vigilant for a tag type system but the standard combination for Natural is not. Hence, we clarify the comparative type-level reasoning power between the two most studied approaches to sound gradual typing. Furthermore, as an exercise that demonstrates how vigilance can guide design, we introduce and examine a new theoretical static gradual type system, dubbed truer, that is stronger than tag typing and more faithfully reflects the type-level reasoning power that the dynamic semantics of Transient gradual typing can guarantee.
Fri 25 OctDisplayed time zone: Pacific Time (US & Canada) change
13:50 - 15:30 | Types and Gradual Typing 2OOPSLA 2024 at Pasadena Chair(s): Fabian Muehlboeck Australian National University | ||
13:50 20mTalk | Degrees of Separation: A Flexible Type System for Safe Concurrency OOPSLA 2024 DOI | ||
14:10 20mTalk | Full Iso-recursive Types OOPSLA 2024 Litao Zhou University of Hong Kong, Qianyong Wan The University of Hong Kong, Bruno C. d. S. Oliveira University of Hong Kong DOI | ||
14:30 20mTalk | Gradually Typed Languages Should Be Vigilant! OOPSLA 2024 Olek Gierczak Northeastern University, Lucy Menon Northeastern University, Christos Dimoulas Northwestern University, Amal Ahmed Northeastern University, USA DOI | ||
14:50 20mTalk | Merging Gradual Typing OOPSLA 2024 Wenjia Ye National University of Singapore, Bruno C. d. S. Oliveira University of Hong Kong, MatÃas Toro University of Chile DOI | ||
15:10 20mTalk | Persimmon: Nested Family Polymorphism with Extensible Variant Types OOPSLA 2024 Anastasiya Kravchuk-Kirilyuk Harvard University, Gary Feng University of Waterloo, Jonas Iskander Harvard University, Yizhou Zhang University of Waterloo, Nada Amin Harvard University DOI |