(A) let-polymorphic type-inference algorithm that fixes the bottleneck of M

Abstract

The Hindley/Milner let-polymorphic type system has two different type-inference algorithms: one is de facto standard algorithm W that is context-insensitive, and the other is context-sensitive algorithm M. We present the bottleneck of the M algorithm and propose a hybrid algorithm, named H, for its remedy. The H algorithm is made out of M adopting W on the application part. We show that H stops still earlier than W but later than M when the input program has type errors.