第五代编程语言设计与实现_韩济澎.pdf

99信息：理论与观点信息记录材料 2022年12月 第23卷第12期 0 引言编程语言的发展经历了机器语言、汇编语言、高级语言、函数语言、逻辑语言1。其中，逻辑编程语言亦被称作第五代编程语言。最早的逻辑语言是列表处理语言 LISP（LISt Processing），其特点是用符号表达式而不是数字进行计算；不足是数值运算能力较弱和数学语义不清晰 2。后来 PROLOG 问世，其特点是基于符号逻辑进行运算，通过模式匹配完成计算，语言清晰、可读、简洁3-4；不足是对规则和目标的表示有严格限制，难以适用于复杂的应用环境5-7。具体改进如下：第一，COOL支持面向过程与面向对象，便于应用于生产项目；第二，COOL 支持将表达式作为函数声明以及函数返回，同时支持将函数参数嵌入函数名字字符串中；第三，COOL 引入了权重机制并通过累计权重法加速推理过程；第四，COOL 引入正向函数、逆向函数的概念，以处理逻辑上具有先后顺序约束的问题；第五，通过回溯算法和动态规划算法实现计算机利用正向求解过程推导逆向求解过程；第六，引入预执行步骤，将推理过程从程序的执行过程中分离，提升程序的执行速度。1 语法1.1 函数函数构成了 COOL 的推理框架。此节介绍了返回表达式的函数、返回运算值的函数、附加权重的函数、正向函数、逆向函数、函数权重。在 COOL 中函数由函数声明和函数体两部分组成，表示相加的函数可以用如代码 1 的方式进行定义。代码 1 函数声明示例：add(a,b)return:a+b;通过为函数声明加上属性“exp”来表明此函数的返回是一个表达式。这种函数用来表述变换规则，用户不能直接调用此类函数，如代码 2 通过函数描述乘法分配律的逆运算。代码 2 返回表达式的函数示例：exp:a*c+b*c return:(a+b)*c;正向函数与逆向函数均指返回运算值的函数；返回表达式的函数不具备此属性。正向函数，即所有函数参数均确定，函数返回值待定的函数。正向函数的执行过程即利用输入参数推导函数的返回值。逆向函数，即函数返回值确定，函数输入参数中存在待定参数的函数。逆向函数的执行过程即利用函数的返回值与确定的输入参数计算待定的输入参数。函数权重用于控制推理系统的推理方向。用户可以为那些更容易导向正确推理结果的变换赋予更大的权重，不容易导向正确推理结果的变换赋予更小的权重。函数的权重在函数声明时确定，例如代码 3 中定义了一个权重为10 的函数：代码 3 具有权重的函数示例：(10)$a=b;a=b;1.2 变量COOL 的非临时变量在使用前必须被声明。变量的类型由最近一次所赋值的类型决定。默认类型为浮点数。变量从其被声明处至其所在作用域结束处之间均可被访问。一个表达式优先使用当前作用域的变量。用户可以通过使用“out”修饰变量以使表达式使用上层作用域的变量。例如代码 4：代码 4“out”使用示例：第五代编程语言设计与实现韩济澎，李陈志航(北京华规科技有限公司技术部 北京 100081)【摘要】为解决目前第五代编程语言存在语义不直观、所处理问题表述严苛、推理能力有限等问题，本文提出了一种第五代编程语言COOL（Constraint and Object Oriented Language），COOL 语言主要借鉴 PCHR 的设计思想，即通过概率控制约束求解过程。同时通过允许将表达式作为函数声明以及函数返回，克服了 LISP 的数学语义不清晰问题；通过实现对表达式的约束求解和逆推，克服了PROLOG推理能力不足的问题；提出预执行步骤将推理过程与执行过程分离，加快了执行速度，并通过支持面向对象，优化了大量约束的管理问题。【关键词】第五代编程语言；面向对象；约束求解；逆向推理；预执行【中图分类号】TP31 【文献标识码】A 【文章编号】1009-5624（2022）12-0099-06DOI:10.16009/13-1295/tq.2022.12.008100 信息：理论与观点信息记录材料 2022年12月 第23卷第12期 new:a=1;new:a=0;a=out:a+1;1.3 完整代码示例求解以下数学问题：对两个数字量 x，y 依次进行以下操作：将 x,y 求和，结果记为 a；修改 x 的值，使其满足x+1值等于y；求解变量z，满足z2+x*z+y等于100；x，y，a 求和，得到最终结果；求解问题的完整代码如代码 5，最终结果为 36.1005。代码 5 完整代码示例：/*定义求解二次方程的函数*/(100)a*$x2+b*x+c x=(-b+(b2-4*a*(c-ans)0.5)/(2*a);/*定义加法的逆向函数*/(10)$a+b a=ans-b;由(x)与(y)得结果 new:a=x+y;$x+1=y;new:z=0;1*$z2+x*z+y=100;return:a+x+z;=由($x)与(y)得结果;new:x=0;new:y=3;由($x)与(y)得结果=50;x-0;/*“-”表示输出，意为将 x 值以默认方式输出*/1.4 类解决相似问题的规则可以单独封装成类，通过继承用户可以更灵活地复用、修改和拓展规则，实现对复杂问题的分治处理和程序的模块化开发。在 COOL 中类由声明和类的作用域组成，在定义一个类时可以使其继承其他的类以使用其成员函数和变量，如代码 6 所示：代码 6 类继承示例system:MainProcessOperationLaw,QuadraticEquation 2 编译2.1 预编译预编译过程中将源代码标识符中出现的非 ASCII 码替换为 ASCII 码字符串；同时，将所有函数参数移动至函数名字字符串后，并保持函数参数顺序不变，在函数参数原来位置用特定字符串（例如：“_Arg_”）代替形成新的字符串；例如 add(A)and(B)to(C)在预编译后变形成 add_Arg_and_Arg_to(A,B,C)。2.2 代码类型通过词法分析程序与语法分析程序将预编译后的代码编译为字符码。字符码由三部分组成，包括代码类型标志位、四元式、四元式参数类型标志位数组。代码类型及其所描述的功能包括变量声明（声明一个变量）；函数操作（绑定函数声明作用域与函数体作用域，或绑定权重、返回类型与函数声明作用域）；推导函数（根据指定的正向函数推导逆向函数的实现逻辑）；域起始（表示作用域的起始）；域结束（表示作用域的结束）；表达式（表明此行代码的四元式是表达式的一部分，包括运算、函数调用、将属性（“$”“#”“out”）赋予变量）；跳转（当一定条件跳转到指定代码继续执行）；表达式结束（截断表达式）；返回（从函数返回）；成员访问（给计算机指明访问成员的路径）；类操作（用于声明类、继承类、将类名与作用域绑定）。四元式及四元式参数类型标志位数组：在代码类型为“表达式”时用于储存四元式的左运算对象、右运算对象、运算符、运算结果以及对应的数据类型；当代码为其他类型时仅用于储存参数。3 预执行3.1 加载字符码此步加载编译生成的字符码文件，将字符码转换为拓展代码，同时生成作用域表、函数表和类表。四元式形参标志位数组：当代码位于函数声明作用域时有效，标识四元式中参数是否为形式参数；当代码位于函数声明作用域外时有效，标识查询四元式中对应参数是从当前代码所在作用域内开始查询（标志位为真）还是从当前代码所在作用域的上层作用域开始查询（标志位为假）。四元式参数待定标志位数组：用于标识在此行代码被执行时，四元式中对应参数的值是否待定，若参数待定（标志位为真），则此参数的值将被视作未知（或无效）；若参数确定（标志位为假），则此参数的值将被视作已知条件；对于返回表达式的函数，由于很多情形下其代表的变换规则与变量是否待定无关，故允许其函数声明中的参数具有“待定”“确定”“无关”三种状态，相应地表示 101信息：理论与观点信息记录材料 2022年12月 第23卷第12期 为真、假、无关三种值。绑定函数地址：用以标识代码所绑定的函数的地址；由于 COOL 中所有函数声明均储存为语法树形式，因此调用某个函数需要将此函数的地址与函数声明表达式进行绑定，在执行此行段代码时就会调用所绑定的函数。此地址在函数根结点标志位为真，说明此行代码对应所绑定函数的声明表达式的根结点，为假则对应子结点。3.2 推理过程定义数据的表示格式a(bc)，表示数据a和 周期（匹配轮数）内被创建或赋值，在周期 c 内被使用；定义一种键值对的表示方式，其以 a 为键以 b 为值。在不引起歧义的情况下，本节允许代码段、表达式、语法树互相代指。（1）初始化复制当前执行代码所在最长的表达式对应代码段 e,获得以初始累计权重值 0 为键、复制代码段为值的键值对；将复制代码段键值对添加至当前代码仓 S；其中，S 为一个以累计权重值为键、代码段为值的二维表；(01)=S （1）代码仓的容量由用户设定，当尝试向一个已满的代码仓添加新键值对时，如果其键大于代码仓中最小的键，则代码仓删除键最小的键值对后再添加新的键值对；如果其键不超过代码仓中最小的键，则添加失败；此外，代码仓中不允许存在值完全一样的键值对。（2）第 k 轮匹配对 于 k N*，在 当 前 代 码 仓 S(k-1 k)不为 空 时，对 于 所 有 S(k-1 k)，i|i N icard(S(k-1|k)；将 ei中满足“任何结点所在代码均未有函数与之绑定”的所有语法树分支对应代码段与所有可以访问到的函数进行匹配；每当 ei的一个语法树分支与一个函数 fun 匹配成功，根据函数的类型对 ei进行代码替换或函数绑定，生成代码段 ej；ej对应权重值为将 fun 权重值 ei权重值相加的结果，即：jfuniwww=+（2）代码段匹配函数，指将代码段对应的表达式 exp1 与函数声明表达式 exp2 进行比较，若 exp1 与 exp2 的语法树结构相同，且任取 exp1 的一个结点 node1 以及 exp2 中与 node1 对位的结点 nod12，node1 与 node2 均满足以下五种情况之一，则匹配成功：node1 是具体值且 node2 是相同的值；node1 是具体值且 node2 是类型相同的形式参数；node1 是变量且 node2是类型相同的形式参数；node1与 node2 是同一个变量。当 fun 代表的是一个化简操作，在进行代码替换后，可能产生脱离表达式语法树的代码片段，如 1 中所示。+ans1tmp3ans1应用化简操作a*c+a*b a*(c+b)后一个表达式脱离原表达式+1x*tmp1y+1x*tmp3ztmp2tmp4+1x*tmp1tmp2+1x+yz脱离的分支图 1 分支脱离表达式语法树示例当 fun 代表的是一个化繁操作，则在使用返回表达式的函数进行代码替换后，表达式的语法树可能产生环状结构（例如变换(a+b)*(x+1)a*(x+1)+b*(x+1)在语法树只有一个 x+1 分支的时候会导致 a*(x+1)和 b*(x+1)引用同一个 x+1 分支的根结点，产生了环状结构）；如 2 中所示：+ans1应用化繁操作a*(c+b)a*c+a*b后形成环状结构ans1原表达式tmp1+1x*tmp1y*tmp1ztmp2tmp4+1x*tmp1tmp2+yz图 2 表达式语法树形成环状结构示例102 信息：理论与观点信息记录材料 2022年12月 第23卷第12期 因此每当代码替换后都需要查找并删除代码段中脱离表达式语法树的代码片段并展开生成的环状结构。（3）匹配结束条件当 ej满足所有代码均与函数绑定时，匹配过程以成功结束，用 ej替换掉当前执行代码所在最长的表达式对应的代码段；否则将 添加到 S(k k+1)中并继续进行匹配：jj(1)(1)Uw,es k ks k k+=+（3）当匹配轮数 k 超出用户规定上限时以失败结束；当本轮和下一轮均无可用元素参与匹配时以失败结束：(1)(1)s kks k k=+=（4）图3展示了在预执行结束后表达式与函数的绑定情况。a$ansz+=$ans2ans3