Introducing Linear Implication Types to λ G ​ T \lambda_{GT} for Computing With Incomplete Graphs

Jin Sano, Naoki Yamamoto, Kazunori Ueda · 2025

Read Introducing Linear Implication Types to λ G ​ T \lambda_{GT} for Computing With Incomplete Graphs by Jin Sano, Naoki Yamamoto, Kazunori Ueda (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17429.txt.

Introduction

Programming with tangled pointer structures is error prone, and Jin Sano, Naoki Yamamoto, and Kazunori Ueda work on a language that replaces pointers with graphs. Their language treats hypergraphs as the basic data, lets programmers operate on them declaratively by pattern matching, and uses its type system to keep those operations safe. Two gaps remained: the type system could not describe incomplete graphs, where parts of a structure are still missing, and it fell back on runtime checks during pattern matching.

Sano and his co-authors close both gaps by adding linear implication types to the language, with fresh constraints that keep the enlarged system sound. The change lets programmers write and check programs that build graphs piece by piece, a common pattern in real data structures. The paper lays out the new typing rules and the reasoning behind them.

Catalog record

CREATORJin Sano, Naoki Yamamoto, Kazunori Ueda
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE1.2 MB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-17429

Browse the full library · About the Tower of Babel