Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper explores the tropical semiring over natural numbers as a grading space in graded coeffect typing, demonstrating its ability to model time passage while ensuring the productivity of well-typed programs. By introducing a graded type system with recursive and polymorphic types, the authors establish that a specific restriction on recursive types suffices to guarantee productivity, enabling the definition of streams and recursive programs. Additionally, they present a novel intersection typing method using "timed" sets, proving that typable terms correspond to those with hereditarily head normal forms and that typability is a $\Pi_0^2$ property in the arithmetical hierarchy.
Graded coeffect typing in the tropical semiring not only models time but also guarantees the productivity of recursive programs, revealing a surprising connection between typing and temporal semantics.
We show that the tropical semiring over the natural numbers, when used as the grading space in graded coeffect typing, faithfully models the passage of time while simultaneously guaranteeing productivity of well-typed programs. A grade a, when assigned to a function parameter, indicates that the parameter is not necessarily available immediately, but will become available after a time steps. We investigate this idea through two formal systems. We first introduce a graded type system featuring recursive and polymorphic types, and show that, in this setting, a natural restriction on recursive types is sufficient to guarantee productivity, while still allowing the definition of streams and recursive programs on them. In particular, we prove that Nakano's later modality can be embedded directly into our system. We then show that tropical grading naturally suggests a novel form of intersection typing, in which the role traditionally played by sets or multisets of types is instead taken by"timed"sets, i.e., functions assigning to each type A the earliest time, represented as a grade, from which the underlying term is available with type A. For the resulting system, we prove not only that productivity is guaranteed, but that it is also characterized: the typable terms are exactly those with hereditarily head normal forms. Remarkably, the system is recursion-theoretically optimal, i.e., typability can be directly proved to be a $\Pi_0^2$ property in the arithmetical hierarchy.