Lambda the Ultimate

A new completely rewritten and improved version of my previous Going Against the Flow paper. Abstract:

This paper introduces a novel type system that can infer an object's composition of traits (mixin-style classes) according to its usage in a program. Such "trait inference" is achieved with two new ideas. First, through a polyvariant treatment of assignments (a := b) and implied field sub-assignments, assignment can usefully encode trait extensions, method calls, overriding, and so on. Second, rather than unify term types or solve inequality constraints via intersection, we instead propagate trait requirements "backward" to assignees, ensuring that trait requirements are compatible only for terms used in the program. We show how this system is feasible without type annotations while supporting mutability, sub-typing, and parametricity.

The main innovation in this work is a treatment of fields and assignment to support it. We have found that assignment between a term's fields is parametric with respect to the assignments of that term! Intuitive but semantically tricky. Soundness proof of this treatment is included in the paper, along with a feasible (but unproved) way of implementing it. Anyways, once that's done, we can model the entire type system in terms of assignments and fields, which I don't think has been done before.