Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Modeling Reachability Types with Logical Relations: Semantic Type Soundness, Termination, Effect Safety, and Equational Theory
 
research article

Modeling Reachability Types with Logical Relations: Semantic Type Soundness, Termination, Effect Safety, and Equational Theory

Bao, Yuyan
•
Jia, Songlin
•
Wei, Guannan
Show more
October 9, 2025
Proceedings of the ACM on Programming Languages

Reachability types are a recent proposal to bring Rust-style reasoning about memory properties to higher-level languages, with a focus on higher-order functions, parametric types, and shared mutable state -- features that are only partially supported by current techniques as employed in Rust. While prior work has established key type soundness results for reachability types using the usual syntactic techniques of progress and preservation, stronger metatheoretic properties have so far been unexplored. This paper presents an alternative semantic model of reachability types using logical relations, providing a framework in which we study key properties of interest: (1) semantic type soundness, including of not syntactically well-typed code fragments, (2) termination, especially in the presence of higher-order mutable references, (3) effect safety, especially the absence of observable mutation, and, finally, (4) program equivalence, especially reordering of non-interfering expressions for parallelization or compiler optimization.

  • Details
  • Metrics
Type
research article
DOI
10.1145/3763116
Author(s)
Bao, Yuyan

Augusta University

Jia, Songlin

Purdue University West Lafayette

Wei, Guannan

Tufts University

Bračevac, Oliver  

École Polytechnique Fédérale de Lausanne

Rompf, Tiark

Purdue University West Lafayette

Date Issued

2025-10-09

Publisher

Association for Computing Machinery (ACM)

Published in
Proceedings of the ACM on Programming Languages
Volume

9

Issue

OOPSLA2

Start page

1837

End page

1864

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LAMP1  
FunderFunding(s)Grant NumberGrant URL

NSF

2348334

Available on Infoscience
October 14, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/254927
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés