基于机器学习的类型推理方法综述

(武汉大学 计算机学院， 湖北 武汉 430072)

1 类型推理介绍

类型推理是一种轻量级的形式化方法，是编程语言中的自动推理部分或全部表达式类型的能力，通常在编译时完成.编译器能够推理变量的类型或函数的类型名，而不需要给出显式的类型注释.它包括分析一个程序，然后推理该程序中某些或所有表达式的不同类型，这样程序员就不需要每次在程序中使用变量时都显式地输入和定义数据类型.类型推理通常是函数式编程语言的编译器特性，而不是面向对象编程语言的编译器特性.编译器或解释器只需要最少的信息和上下文，就可以确定变量或表达式的数据类型.推理算法尝试确定参数类型和返回值类型，然后尝试找到与所有参数一起工作的最特定的数据类型.类型推理的输入可以是源代码、字节码或二进制代码，它是在编译时自动推理表达式的类型，使编译器能够在没有给出明确的类型注释的情况下推理出数据和函数的类型.在许多情况下，如果类型推理系统足够健壮，或者程序或语言足够简单，则可以完全省略程序中的类型注释.在程序编写和编译执行过程中，类型推理是一项很重要的功能.

传统的类型推理方法都是基于规则和语法结构[1]，传统的类型推理解决方案在方法上存在很大的差异.它们可以使用静态分析、动态分析以及它们的组合.如Troshina等[2]采用了静态分析的方法，Guo等[3]使用了动态分析的方法，Lee等[4]则采用了静态分析和动态分析的组合.另一方面，它们可以选择从不同的类型信息来源出发，如Raman等[5]和Srinivasan等[6]使用基于值的类型推理方法，而Chandra等[7]选择了基于流的类型推理方法.不同的类型推理方法还可以采用不同的数据结构，如抽象语法树、路径图、函数调用图等. 其中，函数调用图是利用程序中函数之间的调用关系建立起的模型，抽象语法树是利用程序语义建立起的模型.同时，对于所推理的类型也有很大的差异，包括基本类(如整数、浮点和指针等)、聚合数据类型(如数组)，以及面向对象程序中的类.它们也可以有不同的输入形式，如源码、二进制代码和字节码等.但是，由于传统的类型推理方法基于上下文与语法规则，所以其在许多实际应用的情况下会具有局限性.在传统的类型推理中，因为需要语法规则和类型推演规则，所以要求被推理的程序片段首先都是合法的表达式，即要通过完整的语法检查.然而随着软件技术的发展，在很多情况下获取所需要的类型信息时，并不要求程序在语法上是合法的，而且在很多实际应用的过程中，也无法保证所输入的推理程序一定能够通过语法检查，这种情况下，就无法继续进行类型推理.

对于动态类型语言，在缺乏上下文信息和语法规则的前提下，编译器都很难正常理解这些代码片段，所以采用传统的类型推理方式则很难解决这些问题.例如python语言，它的程序严重依赖外部APIs和动态语言的特性，而且python变量类型都是路径敏感的，对于不同的程序路径，变量可能会有不同的类型，对象的类型和属性集可以动态更改，大大增加了类型推断的难度，使得传统的方法并不适用.另一方面，现有的传统特性往往无法区分不同语义的代码区域，具有不同语义的程序文件可能具有相同值的传统特性，要能够区分这种语义差异的特性就需要能够建立更加精确的预测模型.所以在这些情况下，能够采用基于机器学习的方法对程序片段进行类型推理就显得尤为重要了.

编辑代码文件的开发人员与函数名、参数和变量名等各种标识符交互，这些标识符都存在于一个类型系统中，类型系统限制只接受定义它们的操作数.在编译时进行类型推理了解类型可以提高代码的性能，并允许早期检测错误.较强的类型系统对于软件开发工具也很有用，例如提高自动完成的准确性和调试信息.基于机器学习的类型推理可以被广泛应用于程序错误检测[8]、程序抽象、程序优化、代码补全、程序摘要、错误定位[9]等多个软件领域.

如今，已经涌现出了很多基于机器学习的方法进行类型推理，对在缺乏上下文和语法规则的情况下预测所需程序片段的类型提供了新思路.本文对目前的基于机器学习的方法进行类型推理的几个重要方面进行了归纳总结，分析了实验所采用的不同方法，总结各自的特点、实验中能够推理出的类型、具体的实现过程和实验结果的评估.同时，也对目前存在的问题和未来与之相关的研究方向进行了讨论.

2 基于机器学习的类型推理

在程序设计语言中，一个变量a的类型是它的所有可能的取值形成的集合Ta.传统的类型推理依据程序设计语言的类型系统，设计类型推理的规则，为程序中的任意一个合法的短语α，指派一个类型Tα.

基于机器学习的类型推理则使用机器学习的方法，利用海量的已知类型的源程序作为语料训练，学习出一个类型推理函数Δ:Σ*×Σ*→T，其中Σ*为所有串的集合.在推理阶段，给定程序P中的短语α，可以利用Δ(α,P)得到短语α的类型.

笔者对用机器学习的方法进行类型推理这一领域进行了研究，研究表明，用机器学习的方法进行类型推理是一个多学科的领域，在编程语言、软件工程和系统等多个领域都有相关的论文发表.本文系统地研究了基于机器学习的方法进行类型推理，选取研究的文献来自于OOPSL、APOPI、PLDI、ICSE等多个计算机领域的顶级会议.表1总结了本文讨论的基于机器学习的方法进行类型推理的几篇文献中所采用的方法，涉及到的编程语言.在本文的研究中，类型推理的输入均为源代码，因为传统的类型推理方法都是依赖于语法规则与类型推演规则，所以在缺乏上下文与语法规则的前提下进行对程序片段的类型推理很具有挑战性.源代码的类型推理受编程语言、操作系统和目标体系结构等的影响.编程语言是程序员选择的用于准确定义计算机所需要使用的数据类型,而操作系统和目标体系结构可能影响代码片段中数据的表示形式.虽然目前通常认为所有提出的类型推理的方法可能是通用的，但是大多数方法都是在特定的编程语言和体系结构组合上进行评估的.在之后的章节将具体地讨论基于机器学习的方法进行类型推理的几篇文献中实验的各个方面.

3 方 法

近年来，国内外涌现出了很多基于机器学习的方法进行类型推理的研究，在本文中，将所有的基于机器学习类型推理的方法进行了分类，分别为基于条件随机场的类型推理方法、基于其他概率模型的类型推理方法和基于深度学习的类型推理方法，然后，具体讨论实验研究过程中将如何运用这些方法进行类型推理.

表1 实验方法和程序语言的总结

3.1 基于条件随机场的类型推理方法

条件随机场(conditional random field)是一种判别式概率模型，是随机场的一种，常用于标注或分析序列资料，目前比较广泛地应用于自然语言处理中，进行中文分词和词性标注等词法分析工作.条件随机场的图模型为无向图模型，图中所有的顶点分别代表随机变量，而顶点间的连线则代表随机变量间的依赖关系.在图模型中，往往定义了两种特征：状态特征和转移特征，其中状态特征定义在结点上，表示这个结点是否拥有某个属性；而转移特征定义在边上，表示两个状态是否会因为某个特征而转移.P(y|x)为线性链条件随机场，则在X取x的条件下，Y取y的条件概率：

其中，Z(X)是归一化因子，tk和sl是特征函数，λk和μl是对应的权值，tk是定义在边上的特征函数，即转移特征，sl是定义在节点上的特征函数，即状态特征.特征函数的取值当满足特征条件时取1，否则取0.原则上，条件随机场的图模型布局是可以任意给定的，一般常用的布局是链接式的架构，链接式架构不论在训练、推理，还是解码上，都存在有效率的算法可供演算.条件随机场是一个典型的判别式模型，其联合概率可以写成若干势函数联乘的形式，其中最常用的是线性链条件随机场.

Raychev等[10]就是通过条件随机场对JavaScript进行程序属性的类型推理.它是首先对 JavaScript 程序进行语法分析后转换为依赖网络(Dependency Network)，然后利用已有的代码进行训练，从而能够预测JavaScript 变量的名称与简单类型.该研究着重于推理程序属性的一般问题，运用新的统计方法，通过从已经注释了这些属性的现有代码库中学习概率模型来预测给定程序的属性.通过学习大量的代码库来预测程序属性的核心思想是，将类型推理的问题表述为利用条件随机场对程序属性进行结构化预测，实现对程序属性的联合预测.通过条件随机场逐步预测程序属性的过程，首先就是建立依赖网络，然后基于该网络构建相应的特征函数，通过特征函数的定义可以进一步定义如何获取预测值y的得分.在网络中与所有其他节点断开连接的节点的预测可以独立于对其他节点的预测，而且因为条件随机场具有条件独立性的属性，所以在网络中被连接的两个节点仅通过已知的节点进行预测，两个节点的属性彼此独立的分配，不会相互影响.但是两个节点在不涉及已知节点的情况下，如果之间存在路径则意味着两个节点的预测可能相互依赖.该方法是已知的第一个展示如何在程序上下文中利用条件随机场进行研究的方法.

Uri等[11]也利用到了条件随机场，提出了一种从程序中学习一般的基于路径的表达，这种表示是纯粹语法上的，并且是自动提取.其主要思想是通过使用抽象语法树中的路径来表示程序.这种方法使学习模型能利用代码的结构化本质，而不是将其视为一组扁平的令牌序列.改进了条件随机场，在条件随机场中使用抽象语法树路径，而不是使用原始的因子.

3.2 基于其他概率模型的类型推理方法

机器学习领域的一个关键概念是不确定性，概率论为不确定性的量化和操作提供了框架，并形成了机器学习的核心基础之一.它与决策论相结合，可以根据一些可获得的信息做出最佳预测，即使这些信息可能并不完整.概率模型是用来描述不同随机变量之间关系的数学模型，通常情况下刻画了一个或多个随机变量之间的相互非确定性的概率关系.从数学上讲，该模型通常被表达为(Y，P)，其中Y是观测集合用来描述可能的观测结果，P是Y对应的概率分布函数集合.若使用概率模型，一般而言需假设存在一个确定的分布P生成观测数据Y.因此，通常使用统计推理的办法确定集合P中谁是数据产生的原因.在机器学习中基于概率模型的方法有很多，例如贝叶斯模型、决策树模型和线性回归模型等.

南京大学Xu等[12]针对 Python 语言的动态类型特点，利用机器学习得到从变量名称到类型的概率模型，再根据数据流、属性访问等信息得到概率约束，最后设计概率推理模型，从而实现小语料情况下的变量类型推理.本文提出使用概率推理来允许传播、聚合单个类型提示，并最终收敛于变量类型的概率.传统的类型推理方法由于路径敏感，所以对于python的类型推理并不适用.在python程序中有很多类型提示，然而这些类型提示中有很多是不确定不可靠的.所以此研究提出通过概率推理将所有不确定的类型提示关联起来，通过程序构件之间的关联(例如变量之间的数据流)进行传播和聚合，最后计算收敛于变量类型的概率.这种新的思想能够自然地对类型提示的不确定性建模，轻松处理动态特性.实验的系统结构由三个部分组成:变量名称分类器、概率约束生成器和概率约束生成器类型推理引擎.首先，它通过对可以使用现有静态类型推理技术进行类型化的变量执行机器学习来提取项目的命名约定；然后，从数据流、属性访问、类型检查谓词和变量名生成一组约束；接着，将这些生成的约束转换为一个概率推理网络因子图，利用置信度传播算法解析因子图，得到每个变量的个体类型概率；最后，对计算出的类型概率(每个变量)进行排序，并根据给定的阈值过滤出不太可能的类型.

Raychev等[13]提出了一种基于决策树学习的精确通用概率模型学习方法，从大型代码库中学习代码的概率模型来预测新程序，其关键思想是将学习代码概率模型的问题描述为学习特定语言中的决策树，而不是抽象语法树，这样可以在动态计算的上下文中对程序元素的预测设置条件.此研究提出的是一种学习精确概率模型的新方法，该方法能在预测时自动确定正确的上下文，关键的技术是递归地以类似于决策树的方式分割训练数据，然后学习树的每个分支更小的特定概率模型.此研究中扩展和调整了经典的ID3学习算法，使叶子不必对应于无条件的最大似然估计，但可以使用基于复杂特征的概率模型来表示.这种新的基于决策树的学习算法首先发现整个数据集的适当分解，学习每个部分的最佳条件设置上下文，然后允许将概率模型用作获得的决策树的叶子.此方法被应用到了Python和JavaScript构建概率模型的任务之中.

Allamanis等[14]回顾了机器学习和统计自然语言处理方法应用于源代码的新兴领域，关注于代码的概率模型，并引入一个源代码的分类概率模型.Seidel等[15]则实验了逻辑回归、决策树、随机森林、神经网络等学习方法，定位与分析程序中的类型错误.

3.3 基于深度学习的类型推理方法

在深度学习中[18]，深度置信网络(Deep Belief Networks)是一种生成图模型，通过训练其神经元间的权重，可以使整个神经网络按照最大概率来生成训练数据.不仅可以使用 DBN 识别特征、分类数据，还可以用它来生成数据.它是由多层潜在变量组成的一类深度神经网络，在层之间具有连接但在每层内的单元之间没有连接.当在没有监督的情况下对一组示例进行训练时，深度置信网络可以学习概率重建其输入.然后这些层充当特征检测器.在该学习步骤之后，可以进一步训练深度置信网络以进行分类.DBNs是由多个限制玻尔兹曼机层组成，一个典型的神经网络类型被“限制”为一个可视层和一个隐层，层间存在连接，但层内的单元间不存在连接.隐层单元被训练去捕捉在可视层表现出来的高阶数据的相关性.深度置信网络通过采用逐层训练的方式，解决了深层次神经网络的优化问题，通过逐层训练为整个网络赋予了较好的初始权值，使得网络只要经过微调就可以达到最优解.近年来，深度学习的研究越来越深入，在各个领域获得了不少突破性的进展.基于注意力机制的神经网络也逐渐成为了最近神经网络研究的一个热点[19-20].

Wang等[16]提出了一种强大的表征学习算法，为了弥补程序语义信息与用于缺陷预测的特征之间的差距，通过深度学习的方法从源代码中自动学习程序的语义表示.具体来说，就是利用深度置信网络从程序抽象语法树中提取令牌向量，从而自动学习语义特征，然后利用这些特征训练缺陷预测模型.此研究方法将训练集和测试集的源代码中的标记作为输入，并从中生成语义特性，然后使用这些语义特性来构建和评估用于预测缺陷的模型.实际过程中首先从训练集和测试集中的每个文件的源代码中提取一个令牌向量.由于深度置信网络需要整数向量形式的输入数据，所以将在整数和令牌之间建立映射，并将令牌向量转换为整数向量.为了生成语义特征，需要先使用训练集的整数向量来构建深度置信网络.然后，利用深度置信网络从训练集和测试集的整数向量中自动生成语义特征.最后基于生成的语义特征，从训练集构建缺陷预测模型，并在测试集上评估其性能.研究过程中的四个主要步骤：①将源代码解析为令牌；②将令牌映射为整数标识符，整数标识符是深度置信网络的期望输入；③利用深度置信网络自动生成语义特征；④利用训练数据和测试数据的学习语义特征构建缺陷预测模型并预测缺陷.实验显示，与传统方法相比，自动学习的语义特性可以显著提高项目内部和跨项目缺陷预测.

递归神经网络(Recursive Neural Network)是具有树状阶层结构且网络节点按其连接顺序，对输入信息进行递归的人工神经网络，是深度学习算法之一 .它被视为循环神经网络的推广 .当递归神经网络的每个父节点都仅与一个子节点连接时，其结构等价于全连接的循环神经网络 .递归神经网络具有灵活的拓扑结构且权重共享，适用于包含结构关系的机器学习任务，在自然语言处理领域有重要应用.由于标准的RNN随着递归往往会出现权重指数级爆炸和梯度消失的问题，会丧失学习到连接远距离信息的能力，于是出现了两种新的递归神经网络的变体，分别是长短期记忆网络(Long Short-Term Memory)和门控循环单元(Gated Recurrent Unit).其中，GRU是LSTM网络的一种效果很好的变体，它较LSTM网络的结构更加简单，而且效果也很好.

目前Hellendoorn等[17]提出了一种深度学习模型，它能够理解哪些类型在特定的上下文和关系中是自然发生的，并能够提供类型建议，即使它不能在一开始就推理出类型，但是这些建议往往都可以由类型检查器进行验证.此研究受到了现有的自然语言处理任务的启发，比如词性标注和命名实体识别等.利用序列到序列(sequence-to-sequence)的模型，将一个令牌序列转换为一个类型序列.为了很好地结合单词左右两边的相关上下文，提出了一种双向的递归神经网络的结构，因为存在有许多不同的递归神经网络模型，此研究中选用的是门控循环单元模型.双向的递归神经网络的结构结合了两个反向运行的递归神经网络，一个向前遍历序列，另一个反向遍历序列.于是单个令牌的上下文表示形式称为将正向和反向的状态连接起来.此时，所形成的网络体系结构结社为每个令牌生成的注释彼此独立，这在自然语言中往往正确，但是在源码中却不一样，因为变量可以在整个代码中多次使用，但是它真正的类型与声明时的类型相同，所以还不能够忽略多个令牌之间的相互依赖关系.为了解决这个问题，文章还提出了一个一致性层作为标准双向递归神经网络的拓展，提高了文件中类型注释的一致性和准确性.

4 具体实现

本章节将系统总结在基于机器学习的方法进行类型推理的实验实现中，所选取的代码片段、主要的推理类型、采用的平台、指令集体系结构、操作系统和实现等情况.

4.1 代码片段的选取

本文研究的所有基于机器学习进行类型推理的方法都选择以源代码作为输入.然而，源代码的编程语言选择有很多种，本文研究的文章中选择的编程语言分别有Java，Python，JavaScript，Typescript等.Uri等[11]提出的用基于抽象语法树路径的表示方式学习条件随机场中还使用到了C#.大部分研究中选择的编程语言都是Python和JavaScript，Wang等[16]提到希望未来能将它们的方法扩展到C/C++的项目之中.很少有研究选择C/C+的原因可能是这两个程序语言的结构更加复杂，依赖信息更多.

4.2 推理类型

本节讨论在不同的类型推理方法中所捕获的不同类型.研究发现，类型推理可以针对许多不同的类型，包括初始类型、类、数组、字符串、抽象类和函数类型等.但是没有一项工作是试图恢复所有类型，如联合体几乎没有工作支持，而抽象类则受到比较少的关注.对于类型推理的最终输出，大多数方法都是生成标识变量的单个类型.基本类型是最小的类型单元，由编程语言作为内置类型提供，如Integer、char、float、pointer等.目前基于机器学习的方法进行类型推理的主要推理类型，都是围绕基本类型来讨论的.类是一种面向对象计算机编程语言的构造，由某种特定的元数据所组成的内聚的包，它描述了所创建的对象共同的属性和方法.面向对象程序中的类也是类型推理的一个流行目标，但是目前方法提及到的对于类的推理都是一些可以单一标记的类型，对于一些复杂的构造类型则无法推理了，更不用说递归类型了.递归类型是存储递归指针的聚合类型，这种复杂类型涉及到更多更加复杂的程序操作，需要将每一步的复杂类型分析清楚十分困难.数组是同一类型元素序列的常见内置类型，在数组中，所有元素都具有相同的类型，一旦推理出元素的类型，就知道数组的类型了.字符串是具有特定编码的字符序列，字符串很难从底层表示(如字符数组)中区分出来，所以对于区分数组和字符串的方法，以及标识它们的类型形式，目前的相关研究并不多.函数类型能够捕获函数的原型，即参数和返回值的数量、位置和类型，恢复函数的类型，获取函数参数类型和返回值类型，也是目前对于恢复函数类型的一项挑战.

4.3 体系结构和操作系统

Wang等[16]进行了几个实验来研究提出的语义特征的性能，并与现有的传统特征进行了比较.他们选择在一台2.5 GHz i5-3210M、4GB RAM的机器上进行实验.Raychev等[10]则是在一台32核机器上执行了性能评估，该机器有4个2.13 GHz Xeon处理器，运行Ubuntu 12.04和64位OpenJDK Java 1.7.0_51.其他的实验研究论文中并未详细说明实验方案中具体选用实施的体系结构和操作系统.

5 评估测试方法

本节将讨论不同的实验研究过程中都是如何评估基于机器学习的方法进行类型推理的效果的，将从评估基准和评估方法两个方面进行讨论.

5.1 评估基准

在基于机器学习的方法进行类型推理的研究中，为了考量实际的实验效果，研究中往往会采用一些度量值来量化分析推理结果.评估基准基本上都是对实验结果的准确性和一致性进行预测评估，部分实验同时还会综合评估时间效率的问题.常用到的四个度量值：精确率、召回率、F1参数和准确率，这四个指标被广泛用于评估类型推理技术.准确率反映了对于给定的测试数据集进行类型推理，正确推理的样本数与总样本数之比.准确率表示了预测为真的样本中有多少是真正的样本，它是针对实际类型推理的预测结果而言的.召回率则说明了样本中的正例有多少被预测正确了，它是针对原来的样本而言的.F1参数则同时考虑到了精确率和召回率.

5.2 评估方法

实验过程中的评估方法基本上都是首先选择从大量的训练语料库中进行机器学习，然后根据文章中提出的基于机器学习进行类型推理的方法获取实验结果，再计算相应的精确率、召回率、F1参数等进行有效的评估，并与之前有相似实验方法的文章进行对比讨论，总结评估文章的改进和优势.Xu等[12]将概率图模型与Raychev等[10]的实验模型进行了对比，认为他们的方法实现了局部最优性，对单个变量具有更好的精确度和召回率.Raychev等[13]将计算出的新的决策树模型的准确率与之前的PCFG、3-garm和DeepSyn进行了对比，显示准确率有了明显提升.

6 讨 论

本节将根据现有的用机器学习的方法进行类型推理，讨论目前实验方案中的局限性、存在的问题以及未来需要迎接的挑战.

与传统的基于规则的类型推理方法相比，基于统计与机器学习的类型推理方法具有较好的鲁棒性，能够在不完整上下文的情况下进行推理，解决更多的实际问题，并为更多的应用场景提供服务.但是目前这些工作还存在很多不足.首先仍然比较依赖于分析的程序符合语法要求，否则无法正确有效地提取出所需要的特征进行学习和推理.其次，目前的方法所能支持推理的类型比较有限，大多数为简单的类型，如int、float、char等这些比较单一的类型，对于一些复杂的构造类，尤其是递归类型和抽象类等并没有相应的具体方法进行推理，而对于复杂类型的推理在程序分析中显得更加重要，能够帮助我们更好地了解参数信息，寻找更深层次的错误信息.最后，虽然通常认为所有提出的类型推理的方法可能是通用的，但是大多数方法都是在特定的编程语言和体系结构组合上进行评估的，而且这些方法大多数选择python和JavaScript这些相对来说结构更加简单的程序语言，然后对于C/C++等约束条件更多更复杂的程序语言来说，比较少涉及.

对于未来的工作，可以基于目前所存在的问题进行改进.一方面是希望基于机器学习的方法进行类型推理能够更少的依赖于程序本身的语法分析，使得对于类似于带有未解析的宏的程序片段等情况下，也能够采用机器学习的方法进行类型推理.另一方面是扩展类型推理的程序语言和推理类型.将基于机器学习进行类型推理的方法应用于更多的程序语言，而不仅仅局限于python和JavaScript这些结构相对来说比较简单的语言.对于推理的类型应该扩展到一些复杂的类型，比如数组、字符串、递归类型、联合体、抽象类，还有函数类型，包括函数中的参数类型和返回值类型等.

7 总 结

传统的类型推理方法都是基于规则和语法结构的，然而随着软件技术的发展，在新的软件应用场景中，需要研究新的在缺乏上下文与语法规则的前提下对程序片段进行类型推理的方法.基于机器学习的方法进行类型推理是一个比较具有挑战性的问题，基于它对程序错误检测、程序优化、代码补全、错误定位等方面都有很大的帮助，人们在这一方面进行了大量的研究，涌现出了许多基于机器学习进行类型推理的方法.本文研究了已存在的基于机器学习进行类型推理的方法，并从几个重要方面进行了系统化的总结，包括实验方法、具体的实现和评测方法等，还讨论了目前已有的类型推理方法的局限性、存在的问题和未来需要解决的问题.