基于统计的类型推理方法研究

Type systems are lightweight formalisms which play an important role in programming languages. In the new scenarios of code search, code completion, code summarization, etc., the code snippets may be not well formed or lack proper context. Traditional rule-based type systems are not capable of inferring types for such code snippets, as they rely on language syntax and type inference rules. In this project, we propose a novel type inference approach, which learns statistical type models from open source programs and inference types for terms in code snippets, without the support of any explicit syntax or inference rules. In order to infer complex types, we propose the type prediction approach, which is based on BLSTM-CRF, to predict initial type labels for terms, according to a global probabilistic model. We design the type refinement algorithm, which is based on the sequence-to-sequence model, to generate final types by refining the initial type labels. By accomplishing the research tasks of this project, we will tackle several scientific problems like structural learning for programs, structural learning for types, etc. Our work will provide great benefits to many software tasks, including bug localization, defect prediction, etc.

类型系统作为轻量级的形式化方法，是程序设计语言的重要组成部分。在代码搜索、代码补全、程序摘要等新的软件应用场景中，需要在上下文不完整甚至语法不正确的情况下对程序片段进行类型分析与推理，而传统基于规则的类型系统依赖于语法规则与以及类型推演规则，无法胜任这样的任务。本课题针对软件应用的新需求，提出基于统计的类型推理方法，在不需要显式的语法和类型推演规则的前提下，利用统计模型与机器学习算法，对程序片段中的短语或单词的类型进行推理。为了能够推理复杂的类型，我们首先提出了基于BLSTM-CRF的类型预测方法，利用全局的概率模型，为单词预测初始的类型标签。我们设计了基于sequence-to-sequence的类型求算法，利用局部的上下文模型，对初始的类型进行精化得到最终的类型。通过本课题的研究，拟解决程序结构学习、类型结构学习等关键科学问题，并为相关研究提供基于统计的类型推理的理论基础与应用支持。

类型推理作为轻量级的形式化方法，是程序语言的重要组成部分。在代码搜索、代码补全、程序摘要等新的应用场景中，需要在上下文不完整甚至语法不正确的情况下对程序片段进行类型分析与推理，而传统基于规则的类型系统依赖于语法规则以及类型推演规则，无法胜任这样的任务。本课题针对软件应用的新需求，提出基于统计的类型推理方法，在不需要显式的语法和类型推演规则的前提下，利用统计模型与机器学习算法，对程序片段中的短语或单词的类型进行推理。为了能够推理复杂的类型，我们将整个系统分为了两个阶段。在预测阶段，我们利用全局的概率模型，为每个单词预测初始的类型标签，得到程序中的所有简单类型；在求精阶段，我们采用了三种不同的类型生成模型，对初始的类型进行细化，得到最终的复杂类型。与现有的基于机器学习的方法不同，我们将类型推理看作从序列到图的解析问题，而不是分类问题。根据我们的实验结果，预测阶段的预测准确率达到了了96.40%，对简单类型和复杂类型的预测准确率分别为 97.37%和92.29%。求精阶段三个模型中表现最好的是类型表达式生成模型，通过将复杂类型表示为有向图（类型图），类型表达式生成模型对复杂类型的类型相似度为 77.36%，对零样本复杂类型而言，类型相似度为59.61%。同时，整个系统具备十分良好的实时性，可以用在包括代码搜索、代码推荐、代码补全、程序总结、缺陷预测和故障定位等需要对任意代码片段进行类型推理的软件工程任务中。