Semantically Separating Nominal Wyvern for Usability and Decidability ∗ \ast Carnegie Mellon University, PA, USA, † \dagger Australian National University, Australia, ‡ \ddagger Victoria University of Wellington
Yu Xiang Zhu ∗ \ast, Amos Robinson † \dagger, Sophia Roshal ∗ \ast · 2025
Read Semantically Separating Nominal Wyvern for Usability and Decidability ∗ \ast Carnegie Mellon University, PA, USA, † \dagger Australian National University, Australia, ‡ \ddagger Victoria University of Wellington by Yu Xiang Zhu ∗ \ast, Amos Robinson † \dagger, Sophia Roshal ∗ \ast (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-2507-03867.txt.
Introduction
Yu Xiang Zhu and co-authors design a programming type system keeping a prized guarantee: the computer can always decide whether one type fits inside another. Their system, Nominal Wyvern, belongs to a family fusing object-oriented and functional ideas, gaining power such as self-referential type bounds. In older systems of this family, that power breaks decidability, or easy use is sacrificed to save it.
The new design separates two jobs that others merge. Types are declared by name, in the style programmers know, and refined structurally only at the point of use. That split steers users away from the recursive shapes that cause undecidable cases, and lets the authors adapt a known separation trick to prove decidability. The result keeps the expressiveness programmers use, including bounded polymorphism and modules. The authors pitch the system as proof usability and decidability need not trade off.
Catalog record
| CREATOR | Yu Xiang Zhu ∗ \ast, Amos Robinson † \dagger, Sophia Roshal ∗ \ast |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 142 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-03867
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Semantically Separating Nominal Wyvern for Usability and Decidability ∗ \ast Carnegie Mellon University, PA, USA, † \dagger Australian National University, Australia, ‡ \ddagger Victoria University of Wellington Yu Xiang Zhu ∗ \ast, Amos Robinson † \dagger, Sophia Roshal ∗ \ast Abstract The Dependent Object Types (DOT) calculus incorporates concepts from functional languages (e.g. modules) with traditional object-oriented features (e.g. objects, subtyping) to achieve greater expressivity (e.g. F-bounded polymorphism). However, this merger of paradigms comes at the cost of subtype decidability. Recent work on bringing decidability to DOT has either sacrificed expressiveness or ease of use. The unrestricted construction of recursive types and type bounds has made subtype decidability a much harder problem than in traditional object-oriented programming. Recognizing this, our paper introduces Nominal Wyvern, a DOT-like dependent type system that takes an alternative approach: instead of having a uniform structural syntax like DOT, Nominal Wyvern is designed around a “semantic separation” between the nominal declaration of recursive types on the one hand, and the structural refinement of those types when they are used on the other. This design naturally guides the user to avoid writing undecidably recursive structural types. From a technical standpoint, this separation also makes guaranteeing decidability possible by allowing for an intuitive adaptation of material/shape separation, a technique for achieving subtype decidability by separating types responsible for subtyping constraints from types that represent concrete data. The result is a type system with syntax and structure familiar to OOP users that achieves decidability without compromising the expressiveness of F-bounded polymorphism and module systems as they are used in practice. 1 Introduction The abstraction features of programming languages provide flexibility through their support for code reuse and modularization. However, while functions and methods are the agreed-upon way to abstract shared computation, the approach for how best to achieve type abstraction and polymorphism is less settled. On the one hand are pure object-oriented (OO) languages, where polymorphism is supported in the form of subtyping. In such languages, types are generally monomorphic except for the ability of specific types to act like general ones. On the other hand, are functional languages, where parametric polymorphism allows type variables to stand for concrete types. Programming language researchers have long wanted to get the best of both worlds. The Dependent Object Types (DOT) calculus [ 17 ] , on which Scala is based, is one of the prime examples of merging the two paradigms. By combining the modules of functional languages with the objects of the OO world, DOT supports more expressive types, with very general forms of features such as bounded quantification, which enable programmers to state more precise static guarantees about programs. However, the merger of functional and OO features is far from simple, since their features are deeply rooted in the philosophical and technical differences between structural and nominal types. Traditionally, OO languages are nominal, in that types with different names are semantically different, and may occupy different places in the subtype hierarchy, the backbone of OO abstraction. In contrast, functional languages have traditionally been more structural, meaning that the structure of a type is what defines the type, and the name is a mere convenience in referring to it. This difference is closely related to how abstraction is achieved in each paradigm, so the degree of nominality vs structurality is a key factor in designing a merger. While merging these paradigms provides additional expressiveness, in DOT it came at the cost of decidable type checking [ 10 ] . Traditional subtyping and parametric polymorphism are well-studied and easily decidable, yet it is easy to get an undecidable system after combining the two. It was proved early on that bounded quantification is an undecidable problem [ 18 ] . The reasons for undecidability are technically involved, but intuitively, a major issue is the ability to define types that subtype a type parameterized by themselves. This problem also manifests itself in practical languages that provide similar forms of quantification, including Scala [ 2 ] and Java [ 9 ] . Having an undecidable component in a language can pose real problems to the user. Programmers unfamiliar with the intricacies of their language’s type system may end up being unable to compile their “well-written” program. The compiler’s failure—which essentially comes in the form of a timeout—typically does not provide meaningful guidance on what the programmer should do to fix the problem. That such problems are rare in practice is of modest comfort when you consider how severely they would impact the programmer if and when they do occur. This paper presents Nominal Wyvern, a new core type system for the Wyvern programming language [ 16 , 12 ] , which is itself inspired by DOT. Nominal Wyvern takes an alternative route to merge structural and nominal types. DOT is fundamentally a structural calculus. To encode nominal restrictions in DOT, one uses abstract type members: path-dependent types are referred to by name since they, combined with the bounds on type members, make up the nominal subtype hierarchy. The rest of the DOT type system is structural. Instead of adding more restrictions on top of this system, Nominal Wyvern shifts the balance away from structural types and toward nominal types. By introducing explicit nominality, we are able to distinguish between semantically-distinct occurrences of nominal and structural types , which would use the same syntactic form in DOT. In particular, Nominal Wyvern’s nominal typing system introduces top-level type definitions, which separates the definition of a recursive type (such as List ) from refinements of that type (such as a list of integers, which is written as List { type Element = Int } ). It also separates the declaration of a type member’s bound (such as a type member declaration type Element <= Comparable within an ordered list type) from subtyping relationships between nominal types, which we now require to be explicitly declared at the top-level (written as subtype List <: Collection ). 1 1 1 In Section 4.3 we delve deeper into the expressivity implications and trade-offs that occur when adding further nominal types such as IntList . Both type declarations and subtyping are thus made more explicit and meaningful. Not only is this more natural to users familiar with traditional OO languages, the added nominality aids in separating the types that are designed to constrain recursive type definitions from the types that represent concrete data, a key step in achieving subtype decidability via material/shape separation [ 8 ] . This built-in separation overcomes the need for additional, artificial restrictions to the type hierarchy, such as were needed in prior work [ 13 , 14 ] , resulting in a simpler formulation of material/shape separation rules. The main contributions of this paper are 1) the design of a type system that combines nominal, recursive types with type members and type refinement; 2) a natural adaptation of material/shape separation to this type system, resulting in 3) guarantees of subtype decidability, without sacrificing 4) type safety, simplicity, and expressiveness. Section 2 discusses in detail the earlier research in DOT, subtype decidability, and nominality that motivated this paper. Section 3 presents the grammar and typing rules of Nominal Wyvern and explains how this design facilitates usability and decidability.