抽象数据类型的双代数结构及其计算

程序语言中的许多抽象数据类型包含了可递归定义的语法构造和可共递归定义的动态行为特征,因此单纯利用代数或共代数难以给出完整的描述.双代数是同一载体集上的代数和共代数对,提供了一种从范畴论的角度探讨抽象数据类型上的语法构造和动态行为关系及性质的可行途径.给出抽象数据类型的双代数结构,并利用代数函子对共代数函子的分配律描述了语法构造与动态行为之间的自然转换关系;利用分配律对共代数和代数函子进行函子化提升,给出一种构造初始代数(或终结共代数)上的共代数(或代数)结构,并将其提升为初始(或终结)λ-双代数的方法.在此基础上,进一步将函子化提升应用于各种递归(包括迭代和原始递归)及共递归函数(包括共迭代和原始共递归)的定义及计算中,并给出相应的计算定律.

抽象数据类型的双代数结构

对抽象数据类型的语法构造和动态行为的性质及两者的关系而言,单纯利用代数或共代数方法进行研究存在一定的不足.文中结合范畴论及分配律给出抽象数据类型的双代数结构,并通过λ-双代数自然地描述了语法构造与动态行为之间的转换关系;分别利用分配律对共代数函子及代数函子进行函子化提升,证明这种函子化提升可以将初始代数(或终结共代数)提升为初始(或终结)λ-双代数,并将其应用于递归及共递归函数的定义及计算中.实例表明,这种函子化提升可以扩展代数中的归纳原理和共代数中的共归纳原理,从而提高程序语言对抽象数据类型的描述与性质证明能力.

共归纳数据类型上的共递归操作及其计算定律

范畴论框架下的共归纳数据类型可以看成是某个共代数函子下的终结共代数中的载体,针对该特点,结合范畴论给出程序语言中共归纳数据类型的共代数描述,并根据终结共代数的终结性给出相应的共递归操作的定义及其共代数计算定律;同时,利用双函子及类型函子对参数化共归纳数据类型进行抽象描述,并结合自然转换给出类型函子上的单元和融合等计算定律,证明这些计算定律可用于简化共递归数据类型上的计算,从而提高程序语言对数据类型的动态行为描述能力.

强共归纳数据类型上的Comonadic共递归

针对共归纳数据类型上的unfold无法描述带参数的共递归计算的问题,首先证明了笛卡尔封闭范畴上的终结共代数是强终结的,并给出强共归纳数据类型的范畴论定义及其上一种带固定参数的共递归——punfold,使得共归纳数据类型上的共递归计算可以包含额外的参数作为计算的输入;然后利用基于Comonads的Comonadic共递归给出了unfold和punfold的一种统一的描述,并进一步分析了punfold上的各种计算律,从而将Pardo对基于Comonads的带参数的递归计算研究扩展到共归纳数据类型.

程序语言中的共归纳数据类型及其应用

归纳数据类型利用代数方法从构造的角度归纳地描述数据类型的有限语法结构,但在描述动态行为方面存在一定的不足。作为归纳数据类型的范畴对偶概念,共归纳数据类型利用共代数方法从观察的角度共归纳地描述了数据类型的动态行为。首先,从范畴论和代数的角度给出程序语言中的归纳数据类型定义,并分析了相应的递归操作;接着,利用共代数给出共归纳数据类型的范畴论定义,并根据共归纳数据类型的终结性分析了相应的共递归操作;最后,指出如何利用λ-双代数及分配律将归纳与共归纳数据类型有机地融合起来,探讨数据类型的语法构造与动态行为关系。

类型化π演算的双代数语义

证明互模拟同余通常冗长且易出错.双代数为解决该问题提供统一的框架:若行为函子保持弱回拉,共代数范畴到基范畴的忘却函子有右伴函子,则最大共代数互模拟同余.但已有双代数理论建模类型化π演算存在以下困难:行为函子不保持弱回拉,进程互模拟与共代数互模拟不一致.为解决以上两个问题,用稠密拓扑导出布尔范畴作为语义范畴,令行为函子保持弱回拉;定义一类行为函子,使最大进程互模拟与最大共代数互模拟一致,而迟语义和早语义对应的行为函子属于该类函子.进而给出π演算最大进程互模拟同余的双代数模型,为进一步应用双代数框架对其他复杂演算建模奠定了理论基础.

带参数的共递归操作及其计算律

针对共归纳数据类型上的unfold无法描述带参数的共递归操作的问题,证明了笛卡儿封闭范畴上的有限扩展多项式函子的终结共代数在固定参数和累积参数下都是强终结的,并利用该强终结性给出强共归纳数据类型的定义以及带固定参数和累积参数的共递归操作——punfold和aunfold,从而将Pardo对强归纳数据类型及带参数的递归计算pfold和afold的研究扩展到共归纳数据类型上,使得unfold可直接包含额外的参数用于作为计算的输入或者保存临时的计算结果,避免采用高阶函数的方式.从范畴论的角度给出punfold和aunfold的各种性质、计算律及在函数式程序语言Haskell中的实现,并指出它们在程序推导、转换和优化中的应用.

范畴数据类型上的子类型

为探讨包含构造操作和观察操作的范畴数据类型上的子类型关系及性质,将双代数作为范畴数据类型上构造操作和观察操作的统一数学描述,分析了归纳数据类型上代数子类型和共归纳数据类型上共代数子类型的范畴论定义及其语义,给出了双代数结构中代数子类型和共代数子类型的范畴论定义及其语义解释,从而将代数子类型和共代数子类型的研究扩展到双代数上.

广义共迭代及其计算律

针对函数式编程中的共归纳数据类型上的各种共递归操作缺乏统一描述的问题,利用Monads及其与共代数函子之间的分配律给出了共归纳数据类型上的一种广义共迭代定义——gunfold,证明了gunfold可以为共迭代、原始共递归和Course-of-Value共迭代提供一种统一和抽象的描述.在此基础上进一步从范畴论的角度分析了gunfold上的各种性质和计算律.

弱Hopf代数的L-R弱Smash积

将L-RSmash积推广到弱Hopf代数上,引进了L-R弱Smash积的概念,证明了弱Smash积是L-R弱Smash积的特殊情况.并给出了L-R弱Smash积代数成为弱Hopf代数的一个充分条件.

德摩根代数一个可拟一致化的充要条件

给出德摩根双拓扑代数 (L,Q,τ,σ)可拟一致化的一个充要条件。

Schrodinger-Virasoro型李共形代数的共形双导子和自同构群

本文确定了两类Schrodinger-Virasoro型李共形代数TSV(a,b)和TSV(c)的共形双导子和自同构群.作为主要定理的推论,本文得到了李共形代数W(a,b)的共形双导子和自同构群.

两类N=2超共形代数上的超双导子和超交换映射

确定广义Topological N=2超共形代数和Twisted N=2超共形代数上的超斜对称双导子.证明在这两类超代数上的所有超双导子都是超双内导子.应用此结论,得到在广义Topological N=2超共形代数上的线性超交换映射是非标准的,而Twisted N=2超共形代数上的线性超交换映射是标准的.

一种带参数的Hylomorphisms及其计算律

针对函数式程序语言中的一般hylomorphisms无法描述带参数的递归计算的问题,利用完全偏序范畴上的多项式函子分别给出带固定参数和累积参数的hylomorphisms——phylo射和ahylo射,证明了它们在固定参数和累积参数下都是唯一的,从而将Pardo对带参数的递归计算pfold和afold的研究扩展到hylomorphisms中,使得在hylomorphisms中可以直接包含额外的参数用于作为计算的输入或者保存临时的累积计算结果;从范畴论的角度分析了phylo射和ahylo射与其他各种递归及共递归之间的关系及其计算律,并利用函数程序语言Haskell给出相应的实现.