尊敬的读者您好。 本文将重点介绍一种根据问题的块模型自动生成程序的方法，解决反问题（从已生成的程序恢复原始问题的模型）以及解决已生成程序验证的问题。 主题本身非常严肃，但是我将尝试使该文章尽可能受欢迎（无需大量回顾类似物，严格规定的理论部分以及其他困难），并提供各种应用的示例和说明。

1.自动生成程序

要生成任何程序，您首先必须知道我们要解决的任务。 有了明确的问题正式陈述，就可以建立一些规则来将该陈述扩展为解决问题的计划，以及将解决方案转换为通用或特定算法语言的最终代码的规则。 在这种情况下，通常使用一种方法从预先创建的现成块中构建最终程序-典型的算法通过一些调用/服务代码链接。

让要解决的问题的初步表述以方框图的形式呈现（方框可以是基本的，也可以是子电路），例如，对象网络，每个对象都属于主题区域的类概念层次结构中的某个类。 这样的陈述对于个人和生成程序的系统都是非常清楚和可以理解的。 系统应将这种陈述转换为根据一些逻辑规则解决问题的计划。 因此，用某种逻辑编程语言编写这种转换的规则是合适的，我选择了GNU Prolog。 我注意到，实际上，您通常可以通过立即构建解决方案计划的描述（也以程序框图的形式）来“跳过”该第一阶段（问题的高级描述）。

正如我已经写过的那样，最终的解决方案应该转换成一个程序，该代码是连接解决问题“砖头”的典型算法的代码，例如以函数库的形式实现。 这里有多种方法，我将用几句话描述我使用的方法。 生成过程以事件序列的形式表示（例如，声明的生成，初始化部分的生成，主体部分的阶段，去初始化），对于每个对象，必须将对象网络级联（指的是网络的级联，该方案消除了处理事件时模型的循环），以响应生成相应的代码片段。 在这种情况下，对象依赖于事件的标识符，其参数的值（由用户在构造问题的块语句时设置）以及它们之间可以通过相互之间的关系传输的数据。 因此，解决方案计划中的每个对象都有用于响应此类事件的方法，这些事件会生成代码（通常情况下为任意文本）。 为了解决这个问题，我选择了PHP语言-它恰好可以生成任意文本片段。

通过开发适当的生成类层次结构，可以对主题区域进行系统调整。

生成脚本示例，该脚本为“向量处理（最小，最大，算术平均值）”类生成代码：

<? if ($Stage == stInit) { $argumentID = $Arg["ID"][0]; $argumentSize = $Arg["Size"][0]; $resultID = GetNextMail("result" . $this->ID); if ($this->Op == "Min") { echo " " . $resultID . " = 1E300;\n"; } else if ($this->Op == "Max") { echo " " . $resultID . " = -1E300;\n"; } elseif ($this->Op == "Avr") { echo " " . $resultID . " = 0.0;\n"; } ?> for (i = 0; i < <? echo $argumentSize; ?>; i++) <? if ($this->Op == "Min") { ?> if (<? echo $argumentID . "[i] < " . $resultID; ?>) <? echo $resultID . " = " . $argumentID . "[i];\n"; } else if ($this->Op == "Max") { ?> if (<? echo $argumentID . "[i] > " . $resultID; ?>) <? echo $resultID . " = " . $argumentID . "[i];\n"; } elseif ($this->Op == "Avr") { echo " " . $resultID . " += " . $argumentID . "[i];\n"; } if ($this->Op == "Avr") { echo " " . $resultID . " /= " . $argumentSize . ";\n"; } } ?> 

这是一个相对简单的方案。 实现这种生成方案的系统（PGEN ++）允许在以下领域生成决定性程序：

a）建立污染扩散过程的模型；
b）解决简单机器人操纵器的一些运动学问题；
c）用于处理矢量数据的简单培训程序（搜索最小值，最大值，算术平均值）；
d）开发心理测试系统PROFTEST的测试。

这是以框图形式表示的问题初始说明（简单的矢量数据处理程序） 的示例 ：



这是生成程序的结果 ：

2.逆问题：根据生成的程序重建问题的陈述（初始模型）。 验证生成的程序

首先，为什么有必要解决这个问题。 我认为，最直接的应用是自动生成程序的验证。 如果我们有模型A，并在其上构建了程序P，然后从中重建了模型B，则如果模型A和B一致，则该程序最有可能是正确的。

提出以下简单的解决方案。 在程序的自动生成中，出现了生成属于主题区域的类别的特定层次结构的对象。 他们只有生成方法。 向他们添加识别方法。 然后，通过每个类别的识别方法依次扫描源程序（或通常情况下的任何文本），然后在成功识别后生成该类别的一个或多个对象。 我们得到了有序的（按“阅读”文本的顺序）一组参数化模型元素。 仍然需要根据对象序列及其参数之间的关系来确定它们之间的关系。 为此，可以应用特殊的决策规则。

在我的实现中，识别方法由识别部分（这是一组修改后的正则表达式）和决定性部分（用GNU Prolog编写）组成。 正则表达式的修改方式是在解析阶段进行一些预处理（字典检查，根据Levenshtein的模糊检查相似性，检查括号中表达式的平衡），为此，它们增加了包含各种链的功能（检查，添加，删除，训练“快速”谓词的神经网络。

该电路也可以工作。 作为直接的应用程序，它被用来重建用于处理矢量数据的简单课程（搜索最小值，最大值，算术平均值），在这种情况下，通过比较原始模型和重建模型，它相当成功地证明了生成程序的可能验证。 但是还有其他应用，关于它们的进一步介绍。

3.程序生成系统的自然语言界面

在求解反问题时（如上所述），对于用于重建所求解问题的模型的源材料类型没有限制。 它很可能是自然语言的文本。 只需编写适当的识别方法即可。 因此，反问题的意外应用可能是对生成系统的自然语言接口的实现：

a）用简化的自然语言写出问题的陈述；
b）解决了反问题-从自然语言陈述（主题领域的物元网络）提取形式陈述；
c）启动系统，根据获得的正式声明生成程序。

而且该电路也可以工作。 针对使用矢量数据的简单训练程序的相同情况，开发了一个示例。

这是识别方法的示例 （“输入向量或标量”小键盘类），分为两个版本（识别程序文本（编程模式）或识别俄语中的问题陈述的片段（俄语模式））。 顶部是识别部分，然后是GNU Prolog中的谓词。

 @versions(Programmatical) @global_unique(PROCESS,infinity):- (\s*for\s*\(i\s*\=\s*0\;\s*i\s*\<\s*(\d+)->{N}\;\s*i\+\+\)\s*\{\\n\s*printf\(\"(\w+)->{VECTOR} \[\%i\]\s*\=\s*\"\,\s*i\)\;\\n\s*scanf\(\"\%lf\"\,\s*\&(\w+)==>{VECTOR}\[i\]\)\;\\n\s*\}\\n)| (\s*printf\(\"(\w+)->{SCALAR}\s*\=\s*\"\)\;\\n\s*scanf\(\"\%lf\"\,\s*\&(\w+)==>{SCALAR}\)\;\\n). @versions(Russian) @nearest(db_vvedem,2,"db_vvedem.csv"). @fast(db_var,"db_var.csv"). @global_unique(PROCESS,infinity):- (()->{VAR}([--]+)?=>{db_vvedem($)}\s+((\s+\s+)?)->{KEYB} ([--]+)?=>{db_var($,$VAR)}\s+(\w+)->{ID}((\s+\s+)?)!=>{KEYB}\s*\.). @versions(Russian) handle:-xpath('PROCESS','//ID/text()',[VText]), xpath('PROCESS','//VAR/text()',['0']), simple_vector(_,VText,_), global_id(GID),assertz(simple_act(GID,in,VText,'')),!. handle:-xpath('PROCESS','//ID/text()',[SText]), xpath('PROCESS','//VAR/text()',['1']), global_id(GID),assertz(simple_act(GID,in,SText,'')),!. @versions(Programmatical) handle:-xpath('PROCESS','//VECTOR/text()',[VText]), xpath('PROCESS','//N/text()',[NText]), simple_vector(_,VText,NText), global_id(GID),assertz(simple_act(GID,in,VText,'')),!. handle:-xpath('PROCESS','//SCALAR/text()',[SText]), simple_scalar(_,SText), global_id(GID),assertz(simple_act(GID,in,SText,'')),!. @versions(Programmatical,Russian) @goal:- handle,!. @done:- clear_db. 

俄语中的问题陈述示例：

  .   max.   min.   V  10 .   V  .    V      min.     V      max.   min  .   max  .   V  .      . 

以及系统从上述自然语言描述中获得的问题的模型 ：

4.反问题的其他应用

解决反问题时，没有什么能阻止我们考虑不仅识别某个程序，而且“经过改进”或其他（任意字符）处理的情况。 特别是，有可能开发出一个用C编写的可识别程序的“自动并行化器”。它对识别的代码进行静态和部分动态的分析，并将来自Cilk / Cilk ++扩展的并行化指令插入其中。 通过识别方法（在GNU Prolog中）来实现此改进任务。

并行器处理的计算C程序的示例（他插入了cilk_spawn和cilk_sync指令）：

 #include <stdio.h> #include <math.h> #include <omp.h> #define PI 3.14159265358 #define NX 100 #define NY 100 #define MaxT 0.001 #define h 0.01 #define tau 0.00001 #define cilk_spawn _Cilk_spawn #define cilk_sync _Cilk_sync void F( double x, double y, double t, double * val ){ double r = sqrt(x*x + y*y); double result = 0.0; int i; for ( i = 0; i < 300; i++ ) result += exp(-r*t)*sin(0.1*i*r + 0.5*PI); *val = result; } int main( ){ double f[NY][NX] = {0.0}; double v[NY][NX] = {0.0}; double v1[NY][NX] = {0.0}; double t; int x, y; double start = omp_get_wtime(); for ( t = 0.0; t < MaxT; t += tau ) { for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) cilk_spawn F(x*h, y*h, t, &f[y][x]); for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) { cilk_sync; v1[y][x] = v[y][x] + tau*((v[y-1][x]+v[y+1][x]+v[y][x-1]+v[y][x+1]-4.0*v[y][x])/h/h - f[y][x]); } for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) v[y][x] = v1[y][x]; } for ( y = 0; y < NY; y++ ) { for ( x = 0; x < NX; x++ ) printf("%lf ", v[y][x]); printf("\n"); } printf("Total time = %lf\n", omp_get_wtime() - start); return 0; } 

5.有点虚构。 验证和识别带有封闭源代码的任意程序

在这里，我们谈论的是由程序员和/或系统生成的根本没有源代码的程序编写的任意程序。 让它需要检查这种程序的正确功能，甚至了解它在做什么。 在这种情况下，可以使用一个或另一个版本的所谓的“元层” —操作系统的一个假设组件，该组件跟踪程序的整个序列（调用函数，修改内存中的数据等）并在其中构造其逻辑的近似模型。一种等效于任何编程语言中程序功能的形式。 然后剩下的是解决此类程序的逆问题-恢复可能允许至少评估正确性或了解程序目的的一个或多个初始模型。 作者曾针对C / C ++程序开发过这种“介层”的原型；虽然不可能，但有一定用处。 也许有一天某人会想要完全执行这样的工作。

6.结论

我希望我能够证明程序的自动生成和逆问题的解决不是纯粹的学术问题，而是有用的，直接的实际后果。 同时，这里提出的决定并不假装是完整的和显而易见的，而是被实施并且假装具有某种新颖性。