AFAndong Fan

Andong Fan

*This is an algorithmically generated author record based on publicly available information.

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


Andong Fan has a total of 5 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Modular Type Safety for Traits with Extensible Variants and Deep Pattern Matching

    by Andong Fan, Lionel Parreaux, Ningning Xie

    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

    Practical Type Inference with Levels

    by Andong Fan, Han Xu, Ningning Xie

    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

    When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism

    by Lionel Parreaux, Aleksander Boruch-Gruszecki, Andong Fan, Chun Yin Chau

    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.