具有上下文优化功能的带改进措施的术语评估系统
《Science of Computer Programming》:Typed term evaluation systems with refinements for contextual improvement
【字体:
大
中
小
】
时间:2026年08月13日
来源:Science of Computer Programming 1.6
编辑推荐:
摘要:在编程语言中,项重写扮演着两种不同角色:运行时重写,即求值;以及编译时重写,即优化。求值决定了操作语义,而优化则用于描述程序转换与优化过程,因此必须基于求值结果进行验证。本文提出了一种基于重写理论的证明方法,用以确立上下文改进这一定量正确性标准,该标准可确保优化不会改变可观
摘要:在编程语言中,项重写扮演着两种不同角色:运行时重写,即求值;以及编译时重写,即优化。求值决定了操作语义,而优化则用于描述程序转换与优化过程,因此必须基于求值结果进行验证。本文提出了一种基于重写理论的证明方法,用以确立上下文改进这一定量正确性标准,该标准可确保优化不会改变可观察结果,也不会增加求值步骤数。该方法以局部一致性为核心概念,这一充分条件使得能够对求值与优化之间的交互进行局部分析。为阐述和分析这种交互,我们引入了项求值系统与项求值及优化系统,这些框架在统一的重写理论体系中明确了求值上下文、优化规则及数值。研究表明,通过关键对分析可建立局部一致性,从而将上下文改进问题转化为对优化规则的有限且系统化的分析。该理论既可在一阶环境中构建,也可在简单类型二阶环境中构建:一阶环境用于提炼核心思想,而二阶环境则用于处理变量绑定、元变量及高阶关键对所带来的额外技术难题。通过函数式编程中的多种示例,包括具有效应和共享功能的计算模型,证明了该方法的适用性。
引言:项重写是一种通用且成熟的计算模型。在编程语言领域,重写通常表现为两种形式:运行时重写,即求值;编译时重写,即优化。求值与优化的区别在于重写规则在何种上下文中应用——求值受求值上下文约束,而优化则可在任意上下文中应用。这一差异可通过以下推理规则概括:
(l→r)∈EE∈Ectx → E[lθ]→EE[rθ]
(l?r)∈RC∈Ctx → C[lθ]?RC[rθ]
其中θ表示替换操作,求值上下文E∈Ectx规定了求值规则可应用的范围,通常要求遵循确定的求值顺序;而优化规则则可在任意上下文C∈Ctx中应用,用于实现编译时的程序转换。若优化旨在保持或提升程序行为,则必须基于求值结果进行验证。本文采用Sands[1][2]提出的上下文改进这一定量概念来解决这一验证问题。上下文改进不仅要求保留可观察结果,还要求优化不会增加求值步骤数。我们的主要贡献是一种基于重写理论的证明方法,用于确立上下文改进。该方法的核心是局部一致性,这一充分条件使得能够对求值与优化之间的交互进行局部分析。研究表明,可通过关键对分析对局部一致性进行系统化分析,从而为证明上下文改进提供具体有效的手段。为精准表述这一方法,我们引入了项求值系统与项求值及优化系统这两种框架。它们明确了求值上下文、优化规则及数值,使得求值与优化能在统一的重写理论体系中进行分析。这两种框架并非旨在提出新的重写范式,而是为上下文改进的分析提供形式化基础。研究工作分步进行:首先通过一阶环境提炼核心思想与证明技巧,随后将框架扩展到简单类型二阶环境,此时由于变量绑定、元变量及高阶关键对的出现,会带来新的技术挑战。这一扩展表明,所提出的方法可适用于带类型的二阶抽象语法,同时仍以上下文改进为核心目标而非类型系统的表达能力。首先,我们通过示例介绍了本文所构建的项求值系统与项求值及优化系统这两种新框架,并展示了我们的主要成果——一种通过局部一致性实现上下文改进的方法。标准的从左到右值传递lambda演算属于项求值系统。术语t、t′及其对应的值v定义如下,而值传递的求值策略则通过求值上下文E及相应的求值规则来规定:
E[t,t′]::=x∣v∣tt′
E[E]::=□∣Et∣v
(λx.t)v→t[v/x]
在此规范中,值v起着重要作用。求值上下文的定义中包含了v?E这一条款,即限制左子项v只能为值,这保证了应用t?t′时能从左到右进行求值;只有当左子项t被求值为值后,才能对右子项t′进行求值。此外,红екс(λx.t)v也限制了右子项v只能为值,从而确保了应用操作的值传递特性。简化的计算lambda演算λml* [3]属于项求值及优化系统。其术语要么为值v、v′,要么为计算表达式p、p′,其求值方式(已有相关研究[4])通过求值上下文E及两条求值规则来规定:
E[p,p′]::=return(v)∣letx=pinp′∣vv′
E[E]::=□∣letx=Einp
(λx.p)v→p[v/x]
letx=return(v)inp→p[v/x]
可见,求值上下文限定了求值规则可应用的范围,即letx=pinp′中的子项p。同样,求值规则中的值也确保了应用操作与let绑定能以值传递方式完成。最初,lambda演算λml*是通过方程而非求值规则来定义的。这些定向方程可视为以下五条优化规则:
?: (λx.p)v?p[v/x]
letx=return(v)inp?p[v/x]
λx.vx?v(x不是自由变量时)
letx=pinreturn(x)?pletx1=(letx2=p2inp1)inp3?letx2=p2inletx1=p1inp3
前两条规则对应β转换,第三条对应η转换,第四条用于消除冗余的let绑定,最后一条则用于简化let绑定。可见,后三条规则可简化术语结构。至此,我们得到了一个兼具求值与优化功能的lambdaml*项求值及优化系统。接下来,我们要探讨优化在求值框架下的有效性,目标即为证明上下文改进——即对于任何优化规则t?Ru及任意上下文C∈Ctx,若C[t]的求值能终止,则C[u]的求值也能在相同或更少的求值步骤数内终止。为证明上下文改进,需分析每一步求值如何影响优化规则t?Ru,这实际上就是分析每条求值规则l?→?r可能与哪条优化规则l′?r′产生冲突,而这正是关键对分析要解决的任务。关键对分析通常用于证明局部汇合性,这是项重写的基本性质。该方法首先列出两条重写规则发生冲突的情形,再判断这两个冲突的重写结果是否可以合并。如图1左侧所示,合并部分用虚线箭头标出,"*"表示任意数量的重写步骤。在我们的研究中,我们利用关键对分析来证明上下文改进,更具体地说,是证明局部一致性。分析重点在于求值规则→与优化规则?之间的冲突,我们探讨能否通过求值与优化操作将这些冲突合并,见图1右侧。为确保实现改进,我们的局部一致性概念要求合并后的结果满足关于求值步骤数的不等式1+k≥n。为证明局部一致性的可合并性,需谨慎处理求值上下文,需证明1+k步的求值过程E[lθ]→EE[rθ]→kEu可以通过n步的求值过程s→nEs′来模拟。直观上,可通过证明求值规则l?→?r也可应用于术语s来实现这一点,但这需要确保该规则能在求值上下文中应用,而这并非易事——因为求值上下文E可能会因优化规则E[lθ]?Rs而被修改,优化规则不应将求值上下文转变为非求值上下文(见定义2.9((ii)))。需要注意的是,局部一致性可视为交换性[5]的推广形式,见图1中间部分。交换性是指k=0、n=1的情况,此时仅允许一次优化操作?R而非?*R。本文的贡献可总结如下:1. 我们提出了项求值系统与项求值及优化系统这两种框架,明确了求值与优化之间的区别,并为分析二者交互提供了统一的重写理论体系;2. 我们将局部一致性视为上下文改进的充分条件,从而为基于求值结果验证优化提供了清晰且模块化的标准;3. 我们证明了可通过关键对分析建立局部一致性,进而为上下文改进提供了具体且系统化的证明方法;4. 我们在一阶环境与简单类型二阶环境中分别发展了这一理论:一阶环境用于提炼核心思想,二阶环境则用于处理变量绑定、元变量及高阶关键对带来的技术难题;5. 通过函数式编程中的多种示例,包括具有效应和共享功能的计算模型,我们证明了该方法在实践中的适用性,即可通过局部分析验证上下文改进效果。本文是对会议论文[6]经过全面修改与扩展后的版本,结构如下:第2节阐述了第一阶项求值及优化系统的相关理论,该环境以简洁的形式介绍了核心定义与证明技巧,与标准的一阶项重写理论密切相关;第3节将框架扩展到简单类型二阶环境,该环境纳入了变量绑定、元变量及类型概念,同时解决了高阶重写中出现的额外技术问题,包括高阶关键对问题,而关于上下文改进与局部一致性的核心结论在该环境中依然成立;第4节给出了另一个示例,即按需调用lambda演算,说明了该方法如何应用于具有共享机制及复杂求值策略的计算模型;第5节探讨了基于项求值系统的求值方法与现有重写策略之间的关系,包括最内层重写与上下文敏感重写,该节旨在明确所提框架的适用范围,而非进行全面比较;最后,第6节与第7节分别讨论了相关研究、研究结论以及未来研究方向。
章节片段:
预备知识:设N为自然数集。对于任意n∈N,[n]表示集合{1,…,n}(注意起始点);例如,?[0]=?,[1]={1},[2]={1,2}。用A ̄表示序列A1,…,An,|A ̄|表示其长度(即n),空序列记为?。给定集合S上的二元关系→,用→*表示该关系的自反闭包与传递闭包。对于任意k∈N,→k表示→的k重复合。若元素x∈S不存在满足条件的x′∈S使得……则称x为相对于→的正规形式。
简单类型二阶项求值及优化系统:接下来我们将框架扩展到二阶环境。所谓二阶,指的是使用包含变量绑定与元变量的二阶抽象语法[11][12],这使得我们能够像在二阶代数理论[13]及二阶计算系统[14][15]中那样,对高阶项语言进行形式化处理。
进一步示例:按需调用lambda演算:示例4.1为带类型的按需调用lambda演算[24]。按需调用lambda演算的TERS CBNeedλ结构如图6所示。本文中仅有残差语法类不是通过BNF规则定义的,变量x的残差r仅包含x一次,且对于r中x所在的位置p,有r[□]p∈Ectx。与示例3.3中的最后一条优化规则类似,优化规则(r5)使用了let(M,x.N)这一表示法,以确保N中不会出现变量x。这种TERS CBNeedλ具有确定性、值不变性,且表现良好。它具备……
求值形式化与重写策略:本节的目的是明确本文所提出的项求值系统在现有基于重写的求值建模方法中的定位,尤其关注那些在项重写领域已被广泛研究的重写策略,如最内层重写与上下文敏感重写。本节的讨论可作为对项求值系统框架的合理性检验,我们将证明……
相关研究:在明确了项求值系统在现有重写策略中的地位之后,我们现在探讨与上下文改进及其在程序转换验证中的应用直接相关的现有研究。
结论与未来工作:我们在一阶环境与简单类型二阶环境中都发展出了用于证明上下文改进的基于重写理论的证明方法。我们确定局部一致性是上下文改进的充分条件,并证明可通过关键对分析建立局部一致性。我们还通过具有效应与共享功能的计算模型演示了该证明方法的有效性。这一形式化研究依赖于我们所提出的项求值系统与项求值及优化系统这两种框架。作者贡献声明
Koko Muroya:写作——审稿与编辑,写作——初稿撰写,方法论,研究设计,资金获取,定量分析,概念构建。Makoto Hamana:写作——审稿与编辑,写作——初稿撰写,方法论,研究设计,资金获取,定量分析,概念构建。
利益冲突声明
作者们声明存在以下可能被视为潜在利益冲突的财务利益/个人关系:Koko Muroya表示获得了JSPS的财政支持;Makoto Hamana也表示获得了JSPS的财政支持。其他作者则声明没有已知的可能影响本文所述研究的财务利益或个人关系。
Koko Muroya | Makoto Hamana
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号