In this paper, we present a novel calculus of inductive linear constructions (CILC), combining linear types and dependent types. Our type theory addresses a looming issue in the research on linear dependent types: the lack of a general mechanism for defining sound linear inductive types. CILC allows one to encode in a straightforward manner the linear connectives that must be baked into the core of other systems. This greatly lowers the difficulty of encoding various data structures and makes writing non-trivial programs humanly feasible. We study the standard meta theory of our calculus, showing that it is sound in the usual sense. Through a heap-based operational semantics, we show that CILC safely manipulates resources and runs memory clean. We have formalized and proven correct most of the reported results in the Coq Proof Assistant.
Mon 4 SepDisplayed time zone: Pacific Time (US & Canada) change
11:00 - 12:30 | TyDe: Type-Driven TypesTyDe at St Helens Chair(s): Reynald Affeldt National Institute of Advanced Industrial Science and Technology (AIST), Japan | ||
11:00 22mTalk | A Calculus of Inductive Linear Constructions TyDe DOI | ||
11:22 22mTalk | A Dependently Typed Language with Dynamic Equality TyDe Mark Lemay Autodesk, Qiancheng Fu Boston University, William Blair Boston University, Cheng Zhang Boston University, Hongwei Xi Boston University DOI | ||
11:45 22mTalk | Combining Dependency, Grades, and Adjoint Logic TyDe DOI | ||
12:07 22mTalk | Infix-Extensible Record Types for Tabular DataRecorded TyDe DOI |