Powered by
9th ACM SIGPLAN International Workshop on Type-Driven Development (TyDe 2024),
September 6, 2024,
Milan, Italy
9th ACM SIGPLAN International Workshop on Type-Driven Development (TyDe 2024)
Frontmatter
Papers
Intrinsically Typed Syntax, a Logical Relation, and the Scourge of the Transfer Lemma
Hannes Saffrich
,
Peter Thiemann , and Marius Weidner
(University of Freiburg, Germany)
Intrinsically typed syntax is an important and popular method for mechanized reasoning about programming languages. We explore the limits of this method in the setting of finitely-stratified System F using the Agda proof assistant. This system supports elegant definitions of denotational semantics as well as big-step operational semantics based on intrinsically typed syntax. While its syntactic metatheory (i.e., type soundness) works well, we demonstrate that its semantic metatheory poses technical challenges, by defining a logical relation and proving its fundamental lemma. Our logical relation connects a denotational semantics with an operational one, which exposes issues with transfer lemmas as well as minor issues with universe polymorphism.
Article Search
Normalizable Types
Stefan Monnier
(Université de Montréal, Canada)
In dependently typed programming languages, quotients can be introduced in two different ways: elements of each equivalence class can be made either propositionally equal, at the cost of having to manipulate those equality proofs, or definitionally equal, at the cost of requiring a normalization function. The convenience of definitional equality could make the requirement of a normalization function tolerable, if it were not for the fact that those quotients need to be normalized every time we look at them. In the context of proof assistants, this is sometimes acceptable since efficiency of the code is not always relevant, but for a programming language it means these kinds of quotient types (sometimes called normalized types) are usable only with normalization functions which are cheap, and in the end they do not offer very many benefits over the use of smart constructors which eagerly normalize their return value. We propose an adjustment to normalized types that allows manipulating values of such types without having to normalize them, thus offering much finer control over the code’s efficiency, as well as making those quotient types usable even when normalization functions are too costly or impractical at runtime.
Article Search
Term Search in Rust
Tavo Annus
and Philipp Joram
(Tallinn University of Technology, Estonia)
The Rust programming language offers a rich type system, including sum- and product types. Developer experience is often similar to that of a high-level functional programming language. Yet, it lacks a tool for interactively synthesizing programs based on types; a feature of many functional languages. We devise a general term search algorithm, and integrate it with rust-analyzer, Rust’s official language server, making it usable from any client supporting standard LSP features. It suggests expressions for unfinished parts of a Rust program (as long as their type is known), or offers terms of matching type while typing via autocompletion. We develop the algorithm in three iterations. The first iteration is a backward search, inspired by Agsy, a similar tool for Agda proof assistant. The second iteration reverses the search direction, simplifying the caching of intermediate results. In the final iteration, we implement a tactic-based bidirectional search. This algorithm can synthesize terms in many more situations than the previous iterations, without a significant decrease in performance. To evaluate the performance of our algorithm, we run it on 155 popular open-source Rust libraries. We delete parts of their source code, creating holes, and let the algorithm re-synthesize the missing code. We measure how many holes the algorithm can fill and how often it suggests the original code. We have upstreamed our code, and term search is available as part of the official rust-analyzer distribution starting from v0.3.1850.
Article Search
proc time: 2.88