The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Ma... (ICFP 2020) скачать в хорошем качестве

The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Ma... (ICFP 2020)

The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Made Easy (Functional Pearl) More info about this talk: https://icfp20.sigplan.org/details/ic... Author: Lionel Parreaux, EPFL (presenting) Abstract: MLsub extends traditional Hindley-Milner type inference with subtyping while preserving compact principal types, an exciting new development. However, its specification in terms of biunification is difficult to understand, relying on the new concepts of bisubstitution and polar types, and making use of advanced notions from abstract algebra. In this paper, we show that these are in fact not essential to understanding the mechanisms at play in MLsub. We propose an alternative algorithm called Simple-sub, which can be implemented efficiently in under 500 lines of code (including parsing, simplification, and pretty-printing), looks more familiar, and is easier to understand. We present an experimental evaluation of Simple-sub against MLsub on a million randomly-generated well-scoped expressions, showing that the two systems agree. The mutable automaton-based implementation of MLsub is quite far from its algebraic specification, leaving a lot of space for errors; in fact, our evaluation uncovered several bugs in it. We sketch more straightforward soundness and completeness arguments for Simple-sub, based on a syntactic specification of the type system. This paper is meant to be light in formalism, rich in insights, and easy to consume for prospective designers of new type systems and programming languages. In particular, no abstract algebra is inflicted on readers. This is an official ICFP 2020 talk video edited from an author-submitted video. Video captions supported by Jane Street. On a desktop browser, you can view captions without overlapping the video by clicking the three dots to the right of “Save” and clicking “Open transcript”.