Type inference for dynamic programming languages such as Python is an
important yet challenging task. Static type inference techniques can precisely
infer variables with enough static constraints but are unable to handle
variables with dynamic features. Deep learning (DL) based approaches are
feature-agnostic, but they cannot guarantee the correctness of the predicted
types. Their performance significantly depends on the quality of the training
data (i.e., DL models perform poorly on some common types that rarely appear in
the training dataset). It is interesting to note that the static and DL-based
approaches offer complementary benefits. Unfortunately, to our knowledge,
precise type inference based on both static inference and neural predictions
has not been exploited and remains an open challenge. In particular, it is hard
to integrate DL models into the framework of rule-based static approaches. This
paper fills the gap and proposes a hybrid type inference approach named HiTyper
based on both static inference and deep learning. Specifically, our key insight
is to record type dependencies among variables in each function and encode the
dependency information in type dependency graphs (TDGs). Based on TDGs, we can
easily integrate type inference rules in the nodes to conduct static inference
and type rejection rules to inspect the correctness of neural predictions.
HiTyper iteratively conducts static inference and DL-based prediction until the
TDG is fully inferred. Experiments on two benchmark datasets show that HiTyper
outperforms state-of-the-art DL models by exactly matching 10% more human
annotations. HiTyper also achieves an increase of more than 30% on inferring
rare types. Considering only the static part of HiTyper, it infers 2x ~ 3x more
types than existing static type inference tools.

本研究提出了一种混合类型推断方法 HiTyper，它基于静态推断和深度学习，用于 Python 等动态编程语言。实验结果表明，HiTyper 比最先进的深度学习模型表现更好，并且在推断罕见类型方面具有 30％以上的增加。仅考虑 HiTyper 的静态部分，它比现有的静态类型推断工具推断出 2 倍到 3 倍的类型。