A Bowtie for a Beast: Overloading, Eta Expansion, and Extensible Data Types in F⋈
The typed \emph{merge operator} offers the promise of a compositional
style of statically-typed programming in which solutions to
the expression problem arise naturally. This approach, dubbed
\emph{compositional programming}, has recently been demonstrated by
Zhang et al.
Unfortunately, the merge operator is an unwieldy beast. Merging values from
overlapping types may be ambiguous, so
\emph{disjointness relations} have been introduced to rule out undesired
nondeterminism and obtain a well-behaved semantics. Past type systems using a
disjoint merge operator rely on intersection types, but extending such systems
to include union types or overloaded functions is problematic: naively adding
either reintroduces ambiguity. In a nutshell: the elimination forms of unions
and overloaded functions require values to be distinguishable by case analysis,
but the merge operator can create exotic values that violate that
requirement.
This paper presents $\mathrm{F}_{\bowtie}$, a core language that demonstrates how unions,
intersections, and overloading can all coexist with a tame merge operator. The
key is an underlying design principle that states that any two inhabited types can support
either the deterministic merging of their values, or the ability to distinguish
their values, but never both. To realize this invariant, we decompose
previously studied notions of disjointness into two new, dual relations that
permit the operation that best suits each pair of types. This duality respects
the polarization of the type structure, yielding an expressive language that we
prove to be both type safe and deterministic.
Fri 20 JanDisplayed time zone: Eastern Time (US & Canada) change
09:00 - 10:15 | |||
09:00 25mTalk | A Bowtie for a Beast: Overloading, Eta Expansion, and Extensible Data Types in F⋈ POPL Nick Rioux University of Pennsylvania, Xuejing Huang University of Hong Kong, Bruno C. d. S. Oliveira University of Hong Kong, Steve Zdancewic University of Pennsylvania DOI | ||
09:25 25mTalk | Making a Type Difference: Subtraction on Intersection Types as Generalized Record Operations POPL Han Xu Peking University, Xuejing Huang University of Hong Kong, Bruno C. d. S. Oliveira University of Hong Kong DOI | ||
09:50 25mTalk | Quantitative Inhabitation for Different Lambda Calculi in a Unifying Framework POPL Victor Arrial Université Paris Cité - CNRS - IRIF, Giulio Guerrieri Aix Marseille Université - CNRS - LIS; Edinburgh Research Centre - Central Software Institute - Huawei, Delia Kesner Université Paris Cité - CNRS - IRIF; Institut Universitaire de France DOI |