Andong Fan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Andong Fan has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Lionel Parreaux
Hong Kong University of Science and Technology, Hong Kong, Hong Kong
2 shared publications - Ningning Xie
University of Toronto, Toronto, Canada
2 shared publications - Aleksander Boruch-Gruszecki
EPFL, Lausanne, Switzerland
1 shared publication - Chun Yin Chau
Hong Kong University of Science and Technology, Hong Kong, Hong Kong
1 shared publication - Han Xu
Princeton University, Princeton, USA
1 shared publication
Latest Publications
- Open Access
- 1 October 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 1878-1905
Modular Type Safety for Traits with Extensible Variants and Deep Pattern Matching
Traits provide a powerful mechanism for code reuse, as they allow the definition of shared behaviors that can be composed into classes. Scala traits in particular have been used extensively in both academia and industry to help define reusable components, especially in the context of domain-specific language (DSL) compilers. Pattern matching on the extensible data types representing a DSL’s constructs plays a key role in these applications. However, guaranteeing static type safety in this context is challenging: in Scala, a program using traits may successfully type check but then throw a runtime exception due to non-exhaustive pattern matching. This paper proposes a novel trait language which, for the first time, combines several important features: extensible data types, deep pattern matching, method overriding, exhaustiveness guarantees, and separate type checking. The former three are crucial to supporting DSL analysis and optimization use cases, while the latter two are important for reliable and scalable software development in the large. We formalize our approach in the framework of Boolean-algebraic subtyping, but its core ideas could be adapted to other type systems; thanks to it, languages like Scala that feature traits and extensible variants can finally become type safe, improving the experience of developers working with DSL compilation and related use cases.
- 1 October 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 1878-1905
Open AccessModular Type Safety for Traits with Extensible Variants and Deep Pattern Matching
Traits provide a powerful mechanism for code reuse, as they allow the definition of shared behaviors that can be composed into classes. Scala traits in particular have been used extensively in both academia and industry to help define reusable components, especially in the context of domain-specific language (DSL) compilers. Pattern matching on the extensible data types representing a DSL’s constructs plays a key role in these applications. However, guaranteeing static type safety in this context is challenging: in Scala, a program using traits may successfully type check but then throw a runtime exception due to non-exhaustive pattern matching. This paper proposes a novel trait language which, for the first time, combines several important features: extensible data types, deep pattern matching, method overriding, exhaustiveness guarantees, and separate type checking. The former three are crucial to supporting DSL analysis and optimization use cases, while the latter two are important for reliable and scalable software development in the large. We formalize our approach in the framework of Boolean-algebraic subtyping, but its core ideas could be adapted to other type systems; thanks to it, languages like Scala that feature traits and extensible variants can finally become type safe, improving the experience of developers working with DSL compilation and related use cases.
- Open Access
- 10 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (PLDI) , 2180-2203
Practical Type Inference with Levels
Modern functional languages rely on sophisticated type inference algorithms. However, there often exists a gap between the theoretical presentation of these algorithms and their practical implementations. Specifically, implementations employ techniques not explicitly included in formal specifications, causing undesirable consequences. First, this leads to confusion and unforeseen challenges for developers adhering to the formal specification. Moreover, theoretical guarantees established for a formal presentation may not directly translate to the implementation. This paper focuses on formalizing one such technique, known as levels , which is widely used in practice but whose theoretical treatment remains largely understudied. We present the first comprehensive formalization of levels and demonstrate their applicability to type inference implementations.
- 10 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (PLDI) , 2180-2203
Open AccessPractical Type Inference with Levels
Modern functional languages rely on sophisticated type inference algorithms. However, there often exists a gap between the theoretical presentation of these algorithms and their practical implementations. Specifically, implementations employ techniques not explicitly included in formal specifications, causing undesirable consequences. First, this leads to confusion and unforeseen challenges for developers adhering to the formal specification. Moreover, theoretical guarantees established for a formal presentation may not directly translate to the implementation. This paper focuses on formalizing one such technique, known as levels , which is widely used in practice but whose theoretical treatment remains largely understudied. We present the first comprehensive formalization of levels and demonstrate their applicability to type inference implementations.
- Open Access
- 2 January 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 1418-1450
When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism
Type inference in the presence of first-class or “ impredicative ” second-order polymorphism à la System F has been an active research area for several decades, with original works dating back to the end of the 80s. Yet, until now many basic problems remain open, such as how to type check expressions like ( λ x . ( x 123 , x True ) ) id reliably. We show that a type inference approach based on multi-bounded polymorphism , a form of implicit polymorphic subtyping with multiple lower and upper bounds, can help us resolve most of these problems in a uniquely simple and regular way. We define F ≤ , a declarative type system derived from the existing theory of implicit coercions by Cretin and Rémy (LICS 2014), and we introduce SuperF, a novel algorithm to infer polymorphic multi-bounded F ≤ types while checking user type annotations written in the syntax of System F. We use a recursion-avoiding heuristic to guarantee termination of type inference at the cost of rejecting some valid programs, which thankfully rarely triggers in practice. We show that SuperF is vastly more powerful than all first-class-polymorphic type inference systems proposed so far, significantly advancing the state of the art in type inference for general-purpose programming languages.
- 2 January 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 1418-1450
Open AccessWhen Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism
Type inference in the presence of first-class or “ impredicative ” second-order polymorphism à la System F has been an active research area for several decades, with original works dating back to the end of the 80s. Yet, until now many basic problems remain open, such as how to type check expressions like ( λ x . ( x 123 , x True ) ) id reliably. We show that a type inference approach based on multi-bounded polymorphism , a form of implicit polymorphic subtyping with multiple lower and upper bounds, can help us resolve most of these problems in a uniquely simple and regular way. We define F ≤ , a declarative type system derived from the existing theory of implicit coercions by Cretin and Rémy (LICS 2014), and we introduce SuperF, a novel algorithm to infer polymorphic multi-bounded F ≤ types while checking user type annotations written in the syntax of System F. We use a recursion-avoiding heuristic to guarantee termination of type inference at the cost of rejecting some valid programs, which thankfully rarely triggers in practice. We show that SuperF is vastly more powerful than all first-class-polymorphic type inference systems proposed so far, significantly advancing the state of the art in type inference for general-purpose programming languages.