EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Two-Level Linear Dependent Type Theory

Qiancheng Fu, Hongwei Xi

ACM Transactions on Computational Logic · 31.07.2026 · 27 (3) · 1-33

DOI: 10.1145/3819821 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 15.07.2026. Verfasst von Qiancheng Fu und 1 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present a type theory combining both linearity and dependency by stratifying typing rules into a level for logics and a level for programs. The distinction between logics and programs decouples their semantics, allowing the semantics to be independently tailored to suit the needs of theorem proving and programming. A natural notion of irrelevancy is established where all proofs and types occurring inside programs are fully erasable without compromising their operational behavior. Through a heap-based operational semantics, we show that extracted programs always make computational progress and run memory clean without the need for runtime garbage collection. Additionally, programs can be freely lifted into the logical level for conducting deep proofs in the style of standard dependent type theories. This enables one to write resource-safe programs and verify their correctness using a unified language.

Zitieren

APA

Fu, Q., & Xi, H. (2026). A Two-Level Linear Dependent Type Theory. ACM Transactions on Computational Logic, 27(3), 1-33. https://doi.org/10.1145/3819821

Vancouver

Fu Q, Xi H. A Two-Level Linear Dependent Type Theory. ACM Transactions on Computational Logic. 2026;27(3):1-33. doi:10.1145/3819821

BibTeX
@article{Fu2026,
  author = {Fu, Qiancheng and Xi, Hongwei},
  title = {A Two-Level Linear Dependent Type Theory},
  journal = {ACM Transactions on Computational Logic},
  year = {2026},
  volume = {27},
  number = {3},
  pages = {1--33},
  doi = {10.1145/3819821}
}
Kostenlos starten →