Fig. 1 Illustration of HNCP for automatic program generation
图1 HNCP程序自动生成示例
教会机器理解代码、编写程序或构造可自学习的智能软件一直是人工智能的重要挑战问题之一[1].当前基于神经网络的深度学习在图像处理、语音识别、自然语言处理等领域从研究到应用取得了很大的成功，但是在程序生成上距离研究到实用仍有明显差距.许多学者在程序处理领域也使用神经网络深度学习方法进行了积极探索，提出了不少研究方法，取得了很好的效果，但是仍然未能有效解决泛化能力差、程序正确性、难以处理复杂程序结构的问题.当前基于神经网络的程序生成研究主要包括基于程序输入-输出数据样例的方法[2-6]、基于标注程序执行轨迹样例的方法[7-8]和基于标注源码的方法[9-13].
1) 基于程序输入-输出样例的方法.该方法以神经网络为待学习控制器，从输入-输出样例训练控制器学习预测对神经网络扩展外部存储的操作序列.该方法完全依赖输入输出数据对，存在从数据倒推操作序列的歧义性、泛化能力差、限定一个小的DSL(domain specific language)语言[14]空间、只能处理非常简单的程序结构等问题.比如著名的微软DeepCoder[2]只能处理自定义的一个小型DSL语言，主要预测5行以内、每行只有一个主标识符、顺序结构的平铺程序，不能处理分支、递归、跳转等复杂控制结构，因此习得的程序非常简单.
2) 基于标注程序执行轨迹样例的方法.该方法收集覆盖算法所有执行路径的逐步执行轨迹作为有监督训练数据，其标注方法是以下一步作为上一步的标注.DeepMind NPI[7]是最有代表性的相关研究之一，其优点是明显提高了泛化能力.缺点是数据标注成本高，同时考虑到每个执行轨迹是算法的特定路径，因此需要预先已知算法逻辑，所以本质上未能从输入-输出样例对中倒推学习到新代码逻辑，而是从标注执行路径中学习算法的神经网络表示；另外NPI是对标测试的主要模型之一，其泛化能力虽然有很大提升但仍然是有限的，对此实验分析部分有具体对比.
3) 基于标注源码的方法.对源代码做有监督标注.学习源码跟标注间的统计映射关系，然后通过输入标签反过来推荐源程序.该方法会面临由编程语言过多的规则、实现细节、源码本身丢失语义信息所带来的学习复杂度；同时未能输入源程序的背景知识，比如程序员预先学习的编程语言规范、计算机原理教程等,导致模型处理信息不完备.额外的复杂度加上不完备的信息给模型训练学习带来了巨大挑战.BAYOU[12]是最具代表性的相关研究之一，其优点是可以从注释标签生成大体正确的Java源代码推荐，不足是不能保证和自我检验生成的代码语法是否正确，因此生成的程序代码具有参考价值而不能直接解释执行.
因此，完全依赖神经网络，单一地以源代码标注、输入-输出对、程序执行轨迹做为训练数据输入构建程序生成模型存在局限性.比如程序生成模型在实际应用中一般需要关心模型的泛化能力、生成程序正确性、处理复杂程序结构3个指标，可以分别定性地解释为模型生成的程序表示需要具备一定程度的变通能力(举一反三是理想情况)、执行的准确率、可以处理有一定结构的程序从而能描述更大范围或有一定复杂度的任务，但是这些模型在应对3个指标时面临挑战.我们分析认为这主要是因为编程任务往往非常复杂、程序相对于自然语言有其特殊性，完全依靠神经网络构建的程序生成模型未能结合程序员的价值、未能获得丰富的输入信息(如背景知识).有意思的是观察人类学习编程的过程，程序员会预先学习编程语言的语法规则、计算机原理等背景知识；对比神经网络和人类，神经网络善于从大量数据进行自动化统计学习，人类善于问题分解、直觉感知、经验复用.受此启发，应对程序生成的复杂性和挑战性,我们探讨如何发挥神经网络和人类程序员的整合优势，实现优势互补.
因此本文提出一种融合程序员和神经网络各自优势的协作式编程范式HNCP.HNCP是一种高级可微分(“可微分”是使用反向传播算法求解神经网络权重参数的基础)编程语言，执行在一种提供端到端可微分运行环境的编程语言级抽象虚拟机(diff-erentiable virtual machine, dVM)上.在HNCP编程范式下，程序员用类C高级编程语言提供程序框架，由神经网络组件根据训练数据学习(可微分优化)生成程序的局部细节，因此最终完整确定的程序是由人类程序员和神经网络共同创作完成.如图1所示，图1(a)是一个程序框架，其功能是不完整的，其中空缺部分如图1(b)所示，无缝嵌入一个神经网络组件，程序的完整行为将由程序员提供的程序框架和通过训练数据(输入-输出对)参数化的神经网络组件共同确定.
Fig. 1 Illustration of HNCP for automatic program generation
图1 HNCP程序自动生成示例
本文主要贡献有3个方面：
1) 提出了神经网络与人工程序员协作的高级编程范式HNCP，它可以结合神经网络和程序员各自的优点，使程序生成适用于复杂的程序结构(如循环、递归、分支、函数调用等)；
2) 给出了一种高级过程化编程语言可微分运行环境(dVM)的实现方法.dVM是实现传统过程化程序结构跟神经网络组件无缝融合的基础，也是将离散的程序处理问题转换为能用可微分优化直接处理的问题的关键；
3) 实验表明，跟代表性同类程序生成模型相比，HNCP在程序生成任务上表现出更好的学习性能(泛化能力、样本复杂度、准确率、复杂程序结构).这表明整合人工程序员和神经网络的协作式编程是一种有潜力的研究方法，可以促进程序自动生成的实际应用能力.
文献[12]提出了一种基于Java源程序语法相似性的组合搜索生成源代码示例的方法.我们都用高级编程语言处理复杂的程序，但是文献[15]中的方法是以语法而不是语义为条件的，既不考虑生成程序的准确性，也不考虑生成程序的完整性，生成的代码示例具有参考价值而不能直接解释执行.因此，我们在研究目标和方法上都与之不同.文献[16]提出了基于C语言的程序骨架编程，它是基于SAT(Boolean satisfiability problem)的归纳综合过程，即使用搜索和符号推理来寻找满足人工定义规则的程序.但在本文中，我们采用的是神经网络可微分优化法，也不需要额外的人工定义规则，因此是明显不同的；文献[15-18]扩展了神经网络使之具有较大外部记忆存储，这为可微分存储器缓存的设计提供了有益的启发.但它们都缺乏高级编程接口，而在本文中，我们提供了一个具有外部存储器和高级C语言接口的可微分编程系统，这对于整合程序员的编程框架或者经验、无缝融合神经网络组件到过程化程序结构中是非常重要的.
HNCP是基于类C语法的扩展，增加了神经网络组件嵌入的语言构造.HNCP源程序首先需要编译成中间代码表示(intermediate representation, IR)，从而便于以可微分的矩阵计算方式进行程序解释执行和求解.IR的指令集设计参考了Forth[19]和SECD[20].表1对IR指令集的主要指令进行了说明.该指令集是一个栈式求值语言，我们基于该栈式求值模式构造了一个可微分的运行时环境，命名为dVM，它是一个语言级虚拟机，满足直接对IR程序的可微分解释执行，从而满足对HNCP的类C源程序的解释执行.程序在dVM上以端到端可微分的方式执行生成程序的计算图表示，包括神经网络组件构成计算图的组成部分.进一步，通过输入-输出样例训练计算图来确定嵌入的神经网络组件参数，从而学习生成一个完整、确定的程序表示.
Table 1 Instruction Set
表1 指令集
指令描述微指令CALL L保存返回地址(PC+1)到栈R,然后跳转到L.PR←PR+1;R[PR]←PC+1;PC←LRET跟CALL指令配对.从栈R弹出返回地址,然后跳转到该地址.PC←R[PR];PR←PR-1GOTO L跳转到LPC←LGOTOF L实现if-then-else结构.如果条件为假跳转到L,否则执行下条指令(PC++);条件取自栈S的栈顶值.if S[PS]==False then PC←L else PC←PC+1;PS← PS-1DO跟LOOP和ENDDO配对.在循环的开始从栈S拷贝参数到栈R.S栈顶是循环计数器,次顶是循环次数上限.PR←PR+2; [PR]←S[PS];PS←PS-1;R[PR-1]←S[PS];PS←PS-1;NEXTLOOP LR栈顶值增1.如R栈顶值小于次顶值跳转到L,否则退出该循环.R[PR]←R[PR]+1;if R[PR]<R[PR-1] then PC←L else PC← PC+1ENDLOOP‘do … loop endloop’循环结构,清空栈R中的参数.PR←PR-2;NEXTNEXT显示向前推进一步.PC←PC+1INCS栈顶值增1.S[PS]←S[PS]+1;NEXTDECS栈顶值减1.S[PS]←S[PS]-1;NEXTSWAP交换栈S的栈顶元素和次顶元素.t←S[PS];S[PS]←S[PS-1];S[PS-1]←t+以S栈顶元素和次顶元素为参数做加法,结果保存在S栈顶.t1←S[PS];PS←PS-1;t2←S[PS];S[PS]←ADD(t1,t2);-S栈顶元素减去次顶元素,结果保存在S栈顶.t1←S[PS];PS←PS-1;t2←S[PS];S[PS]←SUB(t1,t2);*S栈顶元素乘以次顶元素,结果保存在S栈顶.t1←S[PS];PS←PS-1;t2←S[PS];S[PS]←MUL(t1,t2);∕S栈顶元素除以次顶元素,结果保存在S栈顶.t1←S[PS];PS←PS-1;t2←S[PS];S[PS]←DIV(t1,t2);==检测S栈顶元素是否等于次顶元素,结果作为条件存S栈顶.t1←S[PS];PS←PS-1;t2←S[PS];S[PS]←EQ(t1,t2);>检测S栈顶元素是否大于次顶元素,结果作为条件存S栈顶.t1←S[PS];PS←PS-1;t2←S[PS];S[PS]←GT(t1,t2);<检测S栈顶元素是否小于次顶元素,结果作为条件存S栈顶.t1←S[PS];PS←PS-1;t2←S[PS];S[PS]←LT(t1,t2);SAVE将S中临时变量值存到H中,S栈顶元素是变量在H地址、次顶元素是变量值.a←S[PS];PS←PS-1;v←S[PS];PS←PS-1;H[a]←v;NEXTLOAD从H中加载变量值到S栈,S栈顶是变量在H中地址.a←S[PS];S[PS]←H[a];NEXTHALT停机,机器状态不再改变.PC←PC
注：该表给出了dVM的基本指令,描述了指令的过程化微操作逻辑，所以该表中的操作是标量.
Fig. 2 Overall processing flow of HNCP program
图2 HNCP程序处理的整体流程
图2所示是用HNCP协作式编程创作的源程序框架自动生成完整、确定的程序的整体处理流程.
首先通过编译技术将C语法的HNCP源程序翻译为更底层的(直接面向dVM)指令集表示的中间语言表示；然后根据分支、控制结构对程序进行分块，包括普通的中间语言代码块和神经网络块(统称代码块).
每个神经网络块都携带着可以通过训练数据来确定其行为的可学习参数(所以完整的程序行为是由程序框架和数据训练学习共同确定).每个代码块是用代码片段构成的函数来实现，而代码片段描述为矩阵代数运算(即指令集的可微分实现)，dVM的状态缓存部件以及对状态的访问、处理也用矩阵和矩阵代数表示，因此程序执行的每个基础步骤是寻址下一个代码块，在dVM的状态部件上做矩阵代数计算，程序的整体执行是由这些基础步骤一步一步推进构成的递归过程.dVM的状态由R(返回栈)、S(求值数据栈)、H(随机变量堆)这些状态缓存和PR(返回栈栈顶指针)、PS(数据栈栈顶指针)、PC(程序计数器指针)组成.
从公理语义[21]的角度将指令的执行和求值表示为虚拟机的状态转换.我们给出了一个全可微分计算系统(dVM)的实现方法，dVM支持高级类C编程语言，具有IR指令集和扩展内存.
2.2.1 可微分虚拟机整体结构
图3所示，可微分虚拟机dVM包括3个状态区(即相对于神经网络内部记忆空间的扩展内存)、1个控制器(对应于处理器)和状态转移指令集.扩展内存区包括2个栈结构(S，R)和一个随机内存结构(H)；控制器包括PS，PR，PC这3个寄存器，PS，PR分别是S，R栈顶指针，PC是程序计数器指针.支持编程控制，即支持输入用指令集写好的程序(程序框架)在虚拟机上执行.
Fig. 3 The dVM architecture
图3 可微分虚拟机整体结构
为了保证整个计算环境是连续可微分地执行程序，指令集(包括扩展内存访问指令)用算术矩阵操作实现为可微分函数(fun_foo)，扩展内存区用矩阵表示，寄存器用one-hot向量表示.控制器负责取指令、执行指令、更新抽象机状态，控制器还包括一个指示指令寻址的向量PC，用于实现执行控制转移.这些基本行为都以连续的可微分函数实现.
2.2.2 指令集与指令集的可微分实现
表1给出了dVM的主要指令集的说明.为了不影响阅读连贯性，我们在附录中给出了指令集可微分实现的详细数学表示，参见附录A.
内存读写的实现原理为，将栈指针看做分布在内存空间上的访问权重，基于此将内存访问(如READ，WRITE)表示为位置权重跟内存单元的矩阵计算，然后基于READ，WRITE的线性组合可以实现PUSH，POP等复杂的栈操作；指令集的可微分实现原理为，对dVM状态(扩展内存)的访问与改变实现为READ，WRITE，PUSH，POP的线性组合；对于算术逻辑操作、控制操作通过矩阵代数运算和运算的组合来实现，矩阵算术操作理论指导可参看双线性映射[22].因此所有的指令集都是用矩阵代数运算表示的连续可微分实现，可以跟神经网络(神经网络也是矩阵代数运算)无缝整合，因此可以用反向传播算法的可微分优化技术对程序生成、程序处理进行直接建模.
2.2.3 程序的可微分执行模型
算法1描述了过程化程序结构在dVM上可微分解释执行流程.从状态转换的角度，其执行过程被描述为从初始状态S0出发的steps步状态迁移.算法1中diffInstsLib是指令集的可微分实现函数库，通过字典结构索引.用到的FetchInst，step操作.dVM的初始状态设置，训练开始时先将dVM扩展内存(即S，R，H构成的状态区)清0，然后用标注数据“输入-输出”样例对的“输入”初始化填充dVM扩展内存，并将对应的栈指针初始化指向下一个空白位置，经过初始设置内存区构成初始状态S0.附录B是一段程序在dVM上运行过程例子.
算法1. 可微分虚拟机程序执行流程.
输入:S0是dVM初始状态、Code是待执行程序框架、steps是执行总步数；
输出:状态转换列表LTRACE=[S0,S1,…,Ssteps].
① function:run(S0,Code,steps)
② S←S0,PC←S.pc,LTRACE[];
③ LTRACE.append(S);
④ for (i=1;i≤steps;i++)
⑤ Weightstate←FetchInst(PC,Code);
⑥ for (j=1;j≤Code.size;j++)
⑦ Stmp←diffInstsLib[Code[j].key](S);
⑧ StatesVector.append(Stmp);
⑨ end for
⑩ Snext←step(Weightstate,StatesVector),
S←Snext;
LTRACE.append(S);
end for
return LTRACE.
算法1的执行过程是从初始状态开始的steps步连续状态迁移，每一步是通过寻址从代码空间选择指令在当前状态上执行并推进dVM迁移到下一个状态.因此整个执行过程构成一个steps步的RNN模型，程序的一遍执行可以描述为
exeTrace=(S1,S2,…,Si,…,Ssteps),
(1)
其中Si=step(Weightcode,Si-1)，S1是初始状态.
代码空间寻址是根据PC和代码矩阵Code计算在代码行的权重分布:
FetchInst(PC,Code)←(PC⊙Code)1T.
(2)
计算取指令，其中Code是需要执行程序的矩阵结构化表示，PC是程序计数器的向量表示，1是行向量(1,1,…,1)，⊙是哈达玛积.
step:(Weightcode,Statecurrent)→Statenext=
(3)
Fig. 4 Step forward to get the next state
图4 单步执行计算下一个状态
单步执行，其中Statecurrent是当前状态向量，Statenext是执行后迁移的下一个状态，Weightcode是取指令计算得到的指令执行权重分布(用softmax计算)，functionCBi是汇编后的代码块(即用函数代码片段给出的指令集可微分实现)，StatesVector是状态行向量.该求值逻辑如图4所示，SP是执行前当前状态，SN是单步执行后迁入的状态，Sn_i是dVM在SP状态下执行地址空间某个指令块得到的状态.
2.2.4 训练目标
对所有训练样本求解使模型推理状态y跟样本标注状态
之间的差距最小化的模型参数θ*，这可用交叉熵表示为对于每个训练样本i，求解使得与y之间的交叉熵最小化的模型参数θ*:
(4)
在求值时对状态值和y按照图5所示的扩展内存区分量进行分解计算：
(5)
我们在求值中发现通过PC，PS，PR指针计算状态分量的掩码(即只计算执行结束时扩展内存的有效区域)，可以免去PC，PS，PR分量的距离计算.
Fig. 5 dVM state buffer components
图5 dVM状态分量
HNCP原型实现是在C语法基础上扩展支持嵌入神经网络作为基本语言构造，称作NCP(neural network component placeholder).图6所示为HNCP前端语法产生式(grammar productions)的BNF描述；其中NCP的语法构造由
ncp
产生式衍生.作为原型验证ncp只给出了encoder-transform-decoder神经网络模型结构,其中encoder对程序上下文输入参数条件编码，transform对条件进行特征转换，decoder解码条件并基于此预测生成执行动作.得益于dVM可微分运行时环境，采用类似思路可增加其他可微分模型，如CNN(convolutional neural networks),seq2seq(sequence to sequence)等作为HNCP语法构造的编程原语.
HNCP使用栈式求值语言作为中间表示(IR)，通过BNF产生式语义规则可以定义将HNCP源程序编译为IR表示的语义动作；其基本思路是将C语法构造翻译为IR指令、语言构造表示，如while用do-loop-endloop，if-else用GOTOF，函数调用用CALL，函数返回用RET，变量定义用H堆内存分配，不同作用域的同名变量用可区分的命名前缀表示等.附录C给出了BNF产生式语义规则的实现样例.
Fig. 6 HNCP BNF grammar productions
图6 HNCP的BNF语法产生式
HNCP源程序的ncp原语翻译为IR表示后保持结构不变，但原语中引用的C语法变量会被替换为在S和R扩展内存区中分配的底层变量表示.下面对encoder-transform-decoder编程原语进行说明：
1) 在该神经原语中，encoder以上下文参数作为条件进行特征编码，transform做进一步特征转换，同时也是对ncp网络参数和层数做适当的调节，decoder解码并做出执行动作决策.
2) linear(out)增加输出宽度为out的线性变换层.
3) observe将dVM状态缓存的元素进行联合.元素取自求值数据栈(S)、控制返回栈(R)或随机访问内存堆(H)中的单元项.
4) choose(actioni,…,actionj)，执行每个动作action，取每个执行结果的权重(Wh)和作为最终结果.权重Wh的计算以transform的输出(h)为条件，即
以h为参数用softmax计算在action列表上概率权重分布.
图7所示为encoder-transform-decoder的典型神经网络拓扑，注意图中每个隐藏层可包含多层神经网络.
Fig. 7 A typical topology of encoder-transform-decoder
图7 encoder-transform-decoder网络拓扑
本节对模型的程序生成学习性能、处理复杂程序结构的能力进行分析评估，包括泛化能力、样本复杂度(训练样本消耗)、准确率的评估，以及代表性程序生成模型的主要指标对比性分析.DeepMind NPI[7]是生成直接可运行程序表示一类模型中表现最好的，seq2seq[23]是程序生成研究中普遍用来做参照的基准模型，因此HNCP主要跟这2个模型做对比.要比较的学习任务采用NPI中使用的冒泡排序(SORT)和多位数初等加法(ADD)，除了可以跟NPI,seq2seq做直接对比，还考虑到它们包含多层次的复杂程序结构，如函数调用、循环、分支、递归，这些结构是广泛的复杂任务编程关键，因此具有代表性.附录D给出了任务的程序框架详情.
泛化能力是评估程序生成模型实用性最重要的指标之一，定义为Gen=Lengthtest_max
Lengthtrain_max，Gen值越大越好，其中Lengthtrain_max是训练期间见过的最大任务规模(如排序任务的序列长度)，Lengthtest_max是测试期间可正确预测的最大任务规模.图8中，SORT任务：seq2seq模型泛化能力为1，即泛化能力差只能对训练期间见过的序列长度正确排序，当测试样本略长于训练样本时准确率立即迅速下降)；NPI泛化能力为3，即可正确完成3倍于训练样本长度的序列排序；HNCP表现了最佳泛化能力(实验最多测试了32倍规模).ADD任务：HNCP表现最好，seq2seq仍表现差，对于这个简单些的任务NPI泛化表现也很好.
Fig. 8 Strong vs. weak generalization
图8 泛化能力比较
实验表明，整合人工编程和神经网络自动生成构建程序生成模型有助于提升程序生成的泛化能力.
模型达到最佳泛化能力所消耗的训练样本数量，该指标值越小表示模型学习性能越好.图9所示，对于SORT任务，本文HNCP模型消耗约272个样本，比NPI和seq2seq明显少；对于ADD任务，本文模型消耗约320个样本，比NPI和seq2seq模型需求明显少.该实验表明通过整合人工程序员和神经网络优势构建程序生成模型可有效提高学习效率.
Fig. 9 Consumption of training samples
图9 训练样本消耗量
注意，NPI模型标注样本量是统计任务执行轨迹的步骤数，而不是直接计算输入-输出对.比如，SORT任务样本数是[m(m-1)2]n,ADD任务样本数是(10m)n,其中m是问题规模(如排序序列长度)，n是任务个数.
生成程序准确率：模型生成的程序执行结果完全正确的任务样本占总测试样本的比例.
如图10、图11所示，对于ADD和SORT任务，使用长度为2的样本训练的HNCP模型在比训练样本长很多的测试样本上可以获得100%的准确率，明显优于基线(NPI和seq2seq).测试发现seq2seq(LSTM实现)学习排序任务是很困难的，表现在当测试序列稍微比训练样本长时，准确率会立即快速下降.HNCP只需用长度为2的序列训练程序框架，便成功地学到了排序行为，并很好地泛化到很长的任务序列.
Fig. 10 Test accuracy of task ADD
图10 加法任务生成程序测试准确率
Fig. 11 Test accuracy of task BubbleSort
图11 排序任务生成程序测试准确率
跟对标基准方法一样，这里使用测试准确率来评估生成程序的精确性，可以很好地跟同类研究做性能指标对比.当前神经网络可解释性是一个难题，因此使用神经网络构建程序生成模型的相关研究主要采用测试样例准确率来评估生成程序的精确性.所以不同于一般意义上的程序正确性证明，对于这类程序生成模型，做到类似“形式语义”等方式实现严格的程序正确性证明是困难的.
本节对主要的代表性程序生成模型，结合主要指标进行对比性汇总分析.如表2所示：
Table 2 Summaries of Indexes of Program Generation Models
表2 程序生成模型主要指标对比汇总
模型GelCtlLanSamExeLrnRepNPI[7]GoodYesDSLMediumYesNoNetseq2seq[22]PoorNoNoHighYesYesNetBAYOU[12]YesJavaHighNoNoCodeDeepCoder[2]NoDSLHighNoYesCodeNTM[3]AverageNoNoHighYesYesNetHNCPExcellentYesCLowYesYesNet
泛化能力(Gel)：BAYOU和DeepCoder预测生成的代码样例不能保证正确、可运行，也没有正确性自动检测方法，所以生成程序的泛化能力无法评估.其中HNCP是表现最好的，NPI次之；复杂程序结构(Ctl)：HNCP和BAYOU表现最好，都支持循环、分支、函数等复杂控制结构，NPI在自定义的DSL专用小语言上支持函数嵌套、分支、跳转控制结构；编程语言支持(Lan)：HNCP和BAYOU都支持通用编程语言，NPI和DeepCoder支持自定义DSL专用语言，seq2seq和NTM不支持编程语言；样本复杂度(Sam)：该指标越低越好，HNCP样本消耗最低，其他都消耗偏多,NPI仅次于HNCP，但其样本标注需要预先知道程序所有执行路径，所以标注代价偏高；可执行(Exe)：BAYOU和DeepCoder生成的程序不能直接执行；是否学习到新的程序行为(Lrn)：根据是否需要提供完整的程序来区分，NPI是对给出的程序路径的神经网络编码，BAYOU需要收集大量功能相似的源码样例，剩下其他模型都可以从输入-输出样例对中学习到程序行为；学习生成的程序表示(Rep)：Code表示代码形式，Net表示用神经网络编码形式.
综合来看HNCP表现出更好的程序生成学习优势，这表明结合程序框架(人工程序员创作)和输入-输出数据对学习(神经网络自动生成)探索构建程序生成模型的研究是有价值的.
实验表明，本文方法跟同类代表性研究方法相比表现出更好的学习性能.结合模型与实验设计，我们有理由相信这种性能提升是因为融合了人工程序员和神经网络的协作，即模型将人工程序员的贡献整合进来发挥了作用；但因为当前神经网络模型的可解释性瓶颈，我们很难给出一个严格的证明.实验表明其性能提升明显、并能表达复杂程序结构，验证了这种整合模型的优势；而同时从某种意义上可能认为这种整合带来的性能优势是以牺牲全自动化程序生成为半自动化的便利性为代价(局限性)，但这需要结合技术发展阶段综合考虑：首先，我们在引言中结合相关工作和观察分析探讨过，当前完全依赖神经网络的全自动或者全黑盒的程序生成模型在关键指标上表现不足(因此全自动的便利性是尚不存在的)，在该背景下我们提出协作式模型并给出一种实现方法进行验证，实验表明这种融合程序员和神经网络的协助式程序生成模型表现出优势，结合分析表明这是有潜力、富有价值的研究思路；其次，考虑到程序生成总需要以一定的方式将需求提供给模型，结合引言中对程序员和神经网络各自的优势、不足的讨论，因此将程序员融合到自动化程序生成建模中是否是必要的，是一个开放性、多因素均衡问题，并且很可能会随着AI技术的发展阶段不同而需要做出不同选择.
关于实验评估测试任务的选择.主要选取对标基准模型(NPI,seq2seq)中用到的相同测试任务，这方便将我们的方法跟基准模型直接进行性能对比，其中NPI是这类模型中表现最好的，因此这种任务比较具有代表性；SORT，ADD任务包含循环、函数调用、递归、分支、顺序执行等复杂控制结构，对于当前的程序自动生成相关研究具有足够复杂性和挑战性，能够将代表性模型(如基准模型和本文模型)的性能指标进行有效区分，另外这些程序结构足以表达其他比较复杂的任务.
经过学者们长期的努力，自动化程序生成研究取得了明显进步，但与图像、语音处理等相比，距实际应用仍有很大的可提升空间.本文提出了一种结合“人工编程”与“神经网络自动化程序生成”构建程序生成模型的研究方法.实验表明整合人工程序员和神经网络各自优势的协作式程序生成模型可以明显提升程序生成的训练学习性能(泛化能力、准确率、样本复杂度)，并适应复杂程序结构.因此，本文探讨的思路是可行且高效的，值得未来做更广泛的研究探索.
提出一种协作式程序生成建模方法并实验验证其技术上的可行性和有效性只是研究工作的一个方面，最终希望走向广泛的实际应用.而在工程应用中不仅关心技术可行性，还需考虑比如丰富并总结程序员跟神经网络的编程任务分工的规则、设计丰富的编程原语、正确性验证等，因此我们认为，下一步有必要对4项工作进行探讨:
1) 丰富分工协作规则并进行总结.比如可以从应用场景、任务类型出发，全面探讨和总结在程序员和神经网络间高效的编程任务分工规则.并将这些规则以程序模板、编程原语或用户编程接口等方式封装呈现.参照Java,C++等编程模型发展经验,这不是一个完全可正向评估的纯技术问题,往往依赖于Java,C++等用户生态的编程创造性的反馈和迭代,即具有开放性和创造性.
2) 如何划分协作分工是一个开放性问题.本文实验验证采用的是“程序员负责框架编制、神经网络负责局部细节生成”的分工方法，该方法在呈现协作式程序生成的概念形态、证明协作式模型的可行性、验证可取得程序生成学习性能的明显改进等方面具有优势,从而证明本文方法理念在意义上是足够的；但未必是最合理的分工方式，并且肯定不能覆盖全部的可能分工模式或规则.因此设计不同的分工协作方法，并为新分工方法构建可实现、可验证的模型具有很大的探索空间，比如在本文思路基础上，如果能够适当地设计扩展模型使得神经网络可在“程序框架的编制”任务中参与分工，将是对程序员与神经网络协作式编程模型很有意义的贡献.
3) 考虑到程序需求场景的复杂性.程序自动生成的应用不仅仅是某个或某几个技术点问题，而是涉及一系列技术集成，因此与大范围应用的图像处理、语音识别等相比，距离工程应用仍有差距.制约程序自动生成应用的因素很多，其中对需求进行建模并能恰当地跟神经网络衔接是关键因素之一;而本文探讨的程序员和神经网络协作式模型中，程序员提供的程序框架其实也属于一种需求描述规范的表达方式，如果沿着这个思路拓展并总结一套系统化需求描述规范，输入给融合的神经网络组件处理，我们相信这是值得进一步拓展探索的研究工作.
4) 生成程序的准确性证明.当前基于神经网络的程序生成相关研究主要通过测试准确率评估生成程序的精确性，对生成程序进行严格的准确性证明是一个富有挑战性的工作.
[1]Manna Z, Waldinger R J. Toward automatic program synthesis[J]. Communications of the ACM, 1971, 14(3): 151-165
[2]Balog M, Gaunt A L, Brockschmidt M, et al. DeepCoder: Learning to write programs[J]. arXiv preprint, arXiv:1611.01989, 2016
[3]Graves A, Wayne G, Danihelka I. Neural turing machines[J]. arXiv preprint, arXiv:1410.5401, 2014
[4]Frankle J, Osera P M, Walker D, et al. Example-directed synthesis:A type-theoretic interpretation[J]. ACM SIGPLAN Notices, 2016, 51(1): 802-815
[5]Feser J K, Chaudhuri S, Dillig I. Synthesizing data structure transformations from input-output examples[J]. ACM SIGPLAN Notices, 2015, 50(6): 229-239
[6]Devlin J, Uesato J, Bhupatiraju S, et al. Robustfill: Neural program learning under noisy I
O[J]. arXiv preprint, arXiv:1703.07469, 2017
[7]Reed S, De Freitas N. Neural programmer-interpreters[J]. arXiv preprint, arXiv:1511.06279, 2015
[8]Xiao Da, Liao Jo-Yu, Yuan Xingyuan. Improving the univer-sality and learnability of neural programmer-interpreters with combinator abstraction[J]. arXiv preprint, arXiv:1802.02696, 2018
[9]Nguyen A T, Hilton M. API code recommendation using statistical learning from fine-grained changes[C] Proc of the 24th Int Symp on Foundations of Software Engineering. New York: ACM, 2016: 511-522
[10]Polosukhin I, Skidanov A. Neural program search: Solving programming tasks from description and examples[J]. arXiv preprint, arXiv:1802.04335, 2018
[11]Dagenais B, Robillard M P. Recommending adaptive changes for framework evolution[J]. ACM Transactions on Software Engineering and Methodology, 2011, 20(4): 1-35
[12]Murali V, Qi Letao, et al. Neural sketch learning for conditional program generation[J]. arXiv preprint, arXiv:1703.05698, 2017
[13]Lin Zeqi, Zhao Junfeng, Xie Bing. A graph database based method for parsing and searching code structure[J]. Journal of Computer Research and Development, 2016, 53(3): 531-540(in Chinese)(林泽琦, 赵俊峰, 谢冰. 一种基于图数据库的代码结构解析与搜索方法[J]. 计算机研究与发展, 2016, 53(3): 531-540)
[14]Van Deursen A, Klint P. Domain-specific language design requires feature descriptions[J]. Journal of Computing and Information Technology, 2002, 10(1): 1-17
[15]Bošnjak M, Rocktäschel T, Naradowsky J, et al. Programming with a differentiable forth interpreter[C] Proc of the 34th Int Conf on Machine Learning. Cambridge, MA: JMLR, 2017: 547-556
[16]Solar-Lezama A, Bodik R. Programsynthesis by sketching[D]. Berkeley: University of California, Berkeley, 2008
[17]Sukhbaatar S, Weston J, Fergus R. End-to-end memory networks[C] Proc of Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2015: 2440-2448
[18]Joulin A, Mikolov T. Inferring algorithmic patterns with stack-augmented recurrent nets[C] Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2015: 190-198
[19]Koopman Jr P J. A brief introduction to Forth[J]. ACM SIGPLAN Notices, 1993, 28(3): 357-358
[20]Kogge P M. The Architecture of Symbolic Computers[M]. New York: McGraw-Hill, Inc, 1990
[21]Nepomniaschy V A, Anureev I S, Promskii A V. Towards verification of C programs: Axiomatic semantics of the C-kernel language[J]. Programming and Computer Software, 2003, 29(6): 338-350
[22]Delsarte P. Bilinear forms over a finite field, with applications to coding theory[J]. Journal of Combinatorial Theory: Series A, 1978, 25(3): 226-241
[23]Sutskever I, Vinyals O, Le Q V. Sequence to sequence learning with neural networks[C] Proc of Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2014: 3104-3112
Zhou Peng, born in 1984. PhD. His main research interests include intelligent software, operating system, virtualization, system security.
周 鹏，1984年生.博士.主要研究方向为智能软件、操作系统、虚拟化、系统安全等.
Wu Yanjun, born in 1979. PhD, professor, PhD supervisor. His main research interests include operating system and system security.
武延军，1979年生.博士，研究员，博士生导师.主要研究方向为操作系统、系统安全.
Zhao Chen, born in 1967. PhD, professor, PhD supervisor. His main research interests include compiling, auto-testing, operating system, and networking software.
赵 琛，1967年生.博士，研究员，博士生导师.主要研究方向为编译、自动化测试、操作系统和网络软件等.
附录A 指令集的可微分实现
扩展内存(S,R,H)在逻辑上以内存矩阵表示，以索引指针提供内存矩阵的访问地址.因此内存区可以用2个分量的元组记为(Bk,Pk)，k∈{S,R,H}，其中Bk∈RV×L，Pk∈RL，L是内存矩阵长度，V是每个值元素向量的宽度(值向量的分量个数)；为了便于数据交换S，R，H统一值宽度为V，对于栈Pk是栈顶指针，对于堆Pk是变量地址.
(A1)
读内存操作的可微分实现，其中
是指针向量Pk的第i个分量,表示在内存区的第i个位置的访问权重，Pk采用类似attention机制做内存读，可用softmax实现，显然READ的实现对Pk和Bk是可微分的.
WRITE(x,Bk,Pk)←Bk⊙(1-Pk1T)+Pkx.
(A2)
写内存操作的可微分实现，其中x是值向量，1是元素全为1，形状为(V,1)的列向量.
分别是向量循环右移1位、循环左移1位的变换矩阵.
分别是内存地址指针右移、左移1个位置.
PUSHk(x)←{Pk=Pk++,
WRITE(x,Bk,Pk)}.
(A7)
POPk={r=READ(Bk,Pk),Pk=Pk--}.
(A8)
fone-hot(i):i→ni,i∈N0,
(A9)
整数的one-hot编码，其中i是非负整数,ni是行向量.
o∈{add,sub,mul,div}.
(A10)
通过构造3-D变换矩阵实现矩阵算术操作，相关理论指导可参看双线性映射数学体系.实现向量算术运算的3-D循环变换矩阵Ao是形状为(V,V,V)的3-D矩阵.
AOPo(a,b)←aTAob,o∈{add,sub,mul,div}.
(A11)
f(+)←{PUSHS(AOPadd(POPS,POPS))}.
(A12)
f(-)←{PUSHS(AOPsub(POPS,POPS))}.
(A13)
f(*)←{PUSHS(AOPmul(POPS,POPS))}.
(A14)
f()←{PUSHS(AOPdiv(POPS,POPS))}.
(A15)
φ(x):x→min(max(0,kx),1),x∈R,k∈R+.
(A16)
式(A16)是分段线性函数，将实数空间R映射到[0,1]空间，其中k系数控制了函数图形的陡峭程度.
GT(a,b)←{p=φ((wone-hot⊙(a-b))1T),
p⊙one+(1-p)⊙zero}.
(A17)
其中，one,zero分别是1,0的one-hot向量表示，wone-hot的形状为(V,1)的向量，(wone-hot)i=i,i∈N+.
EQ(a,b)←{p=φ((a⊙b)1T),
p⊙one+(1-p)⊙zero}.
(A18)
LT(a,b)←GT(b,a).
(A19)
LEQ(a,b)←LT(a,b)+EQ(a,b).
(A20)
NEQ(a,b)←LT(a,b)+GT(a,b).
(A21)
GEQ(a,b)←GT(a,b)+EQ(a,b).
(A22)
f(>)←{PUSHS(GT(POPS,POPS))}.
(A23)
f(<)←{PUSHS(LT(POPS,POPS))}.
(A24)
f(==)←{PUSHS(EQ(POPS,POPS))}.
(A25)
f(≤)←{PUSHS(LEQ(POPS,POPS))}.
(A26)
f(≠)←{PUSHS(NEQ(POPS,POPS))}.
(A27)
f(≥)←{PUSHS(GEQ(POPS,POPS))}.
(A28)
SAVE←{a=POPS,v=POPS,
WRITE(v,BH,a)}.
(A29)
LOAD←{a=READ(BS,PS),
WRITE(READ(BH,a),BS,PS)}.
(A30)
DECDIGIT(x):x→(wone-hot⊙x)1T.
(A31)
式(A31)是将one-hot编码整数转换到十进制编码的转换函数.
CALL(L)←{PUSHR(PC++),PC=fone-hot(L)}.
(A32)
RET←{PC=POPR}.
(A33)
NEXT←{PC++}.
(A34)
GOTO(L)←{PC=fone-hot(L)}.
(A35)
GOTOF(L)←{p=DECDIGIT(POPS),
有条件跳转，可用于if..then..else的可微分实现.
p=DECDIGIT(EQ(READ(BR,PR),
式(A37)～(A39)用于do..loop和while循环可微分实现.
HALT←{PC=PC}.
(A40)
SWAP←{a=POPS,b=POPS,
PUSHS(b),PUSHS(a)}.
(A43)
附录B dVM运行时过程示例
图B1示例是IR程序在dVM上执行过程，记录程序每步指令执行后dVM的(S,R)内存区值和PC指针变化轨迹.图B1(a)是该示例测试程序，主要由循环结构和循环内嵌函数调用构成，包含了循环、函数调用、函数返回、无条件跳转、顺序执行等复杂控制结构.这些程序结构足以表达复杂程序;PC是程序指针轨迹(one-hot)，S和R分别是相应的求值栈和返回栈内容变化，随着程序执行其记录值数据的可视化轨迹于图B1(b)(c)所示.该程序一共执行了16步,执行了2次循环，循环于图B1(b)中虚框所示，对应于图B1(a)虚框内代码，执行了2次函数调用-返回结构(CALL保存在R栈中的返回地址9被相应的RET获得，实现返回现场)，最后执行到停机指令正常终止.
附录C BNF语义规则的实现示例
图C1所示是语义规则的一个实现示例.
Fig. B1 An illustration of program execution on dVM
图B1 dVM程序执行过程的示例
Fig. C1 An implementation example of semantic rules
图C1 语义规则实现示例
附录D 程序任务样例
ADD和SORT任务分别如图D1和图D2所示:
