跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2608.02596 · v3

Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring

首次提交 2026-08-04 01:58
版本更新 2026-11-13 18:10
雷达观测 2026-11-16 11:42
arXiv ↗PDF ↗

摘要

We give a temporal reading of graded coeffects: tropical grades carry guards on infinite computation. To illustrate it, we first define GTG_T, a polymorphic calculus with guarded recursive types that guarantees productive infinite computation, in the form of hereditary head normalisation. The calculus supports stream computing via the Scott encoding, and embeds Nakano's later modality. We then introduce ITI_T, a graded intersection type system with guarded infinitary types for the pure λ-calculus, whose typability allows for an exact characterisation of hereditary head normalisation. We prove that the characterising typability predicate is Π02Π_0^2, matching the recursion-theoretic complexity of the characterised property.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-13 18:10 · 最新观测版本

Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring

We give a temporal reading of graded coeffects: tropical grades carry guards on infinite computation. To illustrate it, we first define GTG_T, a polymorphic calculus with guarded recursive types that guarantees productive infinite computation, in the form of hereditary head normalisation. The calculus supports stream computing via the Scott encoding, and embeds Nakano's later modality. We then introduce ITI_T, a graded intersection type system with guarded infinitary types for the pure λ-calculus, whose typability allows for an exact characterisation of hereditary head normalisation. We prove that the characterising typability predicate is Π02Π_0^2, matching the recursion-theoretic complexity of the characterised property.

查看此版本解读 →查看此版本原文 ↗