计算机科学中的范畴数据类型的研究综述

范畴数据类型是指以范畴论为数学理论基础研究数据类型的描述、计算、语义和应用。早期的范畴数据类型研究以归纳数据类型为主,采用代数从归纳的角度研究有限数据类型的构造语义和递归性质。近年来,归纳数据类型的对偶概念——共归纳数据类型逐渐引起计算机科学工作者的关注与研究,他们采用共代数从观察的角度研究无限数据类型的行为语义和共递归性质。利用范畴论可以为数据类型研究提供统一的数学理论基础,并将代数和共代数中的各种重要研究成果有机地融合在一起,如语法构造与动态行为、递归与共递归、同余与互模拟等。目前,范畴数据类型已经在程序语言、计算描述、理论证明器和并行计算等领域得到广泛的应用。对范畴数据类型的基本概念、数学理论基础、逻辑基础及应用等方面的最新研究成果进行介绍,以引起国内外相关研究领域的学者对计算机科学中的范畴数据类型理论的关注。     

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

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

程序语言中共归纳数据类型的一种fibrations方法

范畴论与共代数是程序语言中共归纳数据类型研究的传统方法,这些方法在语义行为分析与共归纳规则描述等方面存在一定的不足。针对以上问题,提出了一种fibrations方法以对共归纳数据类型的语义行为与共归纳规则进行研究。该方法系统分析了fibration上共归纳数据类型的重索引函子、对偶重索引函子与真值函子等基本逻辑结构,应用等式函子与商函子等工具建立共归纳数据类型与其语义行为在程序逻辑上的对应关系,深入分析共归纳数据类型的语义行为;并以基范畴上自函子及其在全范畴上保持等式的提升为工具构造共递归操作,抽象描述共归纳数据类型具有普适意义的共归纳规则;最后通过实例分析简要介绍了fibrations方法的应用。     

归纳数据类型的范畴论方法

归纳数据类型是类型论研究的重要分支,传统的数理逻辑或代数方法侧重于描述归纳数据类型的有限语法构造,在语义性质与归纳规则的分析与设计方面存在一定的不足.基于范畴论的方法,在集合范畴的框架内给出谓词的形式化定义,分析谓词范畴与代数范畴的构成与性质,并探讨集合范畴上自函子到谓词范畴上自函子的提升,最后利用伴随函子及其伴随性质深入分析了归纳数据类型具有普适意义的归纳规则.     

程序语言中基于Fibrations理论的索引共归纳数据类型

传统范畴论与共代数等方法在分析语义行为与描述共归纳规则方面存在不足,应用Fibrations理论对程序语言中索引共归纳数据类型(indexed co-inductive data type,ICDT)进行了研究。通过基变换构造索引Fibration,建立索引Fibration的等式函子与商函子等工具,应用伴随性质与保持等式的提升深入分析ICDT的语义行为;以此为基础,构造ICDT上参数化的共递归操作,在Fibrations理论框架内抽象描述具有普适意义的共归纳规则,并以实例分析简要介绍Fibrations理论在ICDT中的应用。与传统研究方法相比,Fibrations理论具有简洁的描述性与灵活的扩展性,可以精确分析ICDT的语义行为,具有高度的抽象性且不依赖特定的计算环境,描述了ICDT具有普适意义的共归纳规则。     

Fibrations理论在索引归纳数据类型语法构造中的应用

应用Fibrations理论对索引归纳数据类型的语法构造进行了研究。提出了索引fibration及其真值与内涵函子的定义,构造了索引与代数范畴,利用折叠函数与伴随函子等工具构造了索引范畴中一类相对复杂的索引归纳数据类型,辅以实例进行了简要分析,并通过相关工作的论述指出了Fibrations理论研究方法的优势。     

计算机科学中的共代数方法的研究综述

代数理论已经在抽象数据类型、程序语义等计算机科学领域有了广泛的应用,而代数的对偶概念--共代数,则直到20世纪90年代中后期才被越来越多的计算机学者关注.代数从"构造"的角度研究数据类型,而共代数则从"观察"的角度考察系统及其性质.共代数方法对研究基于状态的系统有独特的优越性,可以对系统的行为等价、不确定性等从数学上进行深入的探讨.目前,共代数理论已经逐步应用在自动机理论、并发程序的语义、面向对象程序的规范等领域.对共代数的基本概念、范畴理论基础、共代数逻辑及应用等方面的最新研究成果进行了介绍,以引起国内相关研究领域的学者对计算机科学中的共代数方法的关注.     

一种基于共代数的面向对象形式语义

针对面向对象方法的数学理论基础相对薄弱的问题,利用共代数方法从范畴论及观察的角度研究面向对象的形式语义及行为关系。首先,给出类和对象的共代数描述,其中抽象类定义成一个类规范,类定义为满足类规范的共代数,类的各个对象则看成共代数状态空间上的元素,并分别利用强Monads理论和断言给出方法的行为的参数化描述和语义约束;接着,利用共代数互模拟探讨了不同对象在强Monads下的行为等价关系;最后用实例说明如何通过PVS工具证明类规范的一致性及对象的行为关系。     

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

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

基于模态的嵌入式软件动态重构技术研究

终结共代数上的互模拟是等价关系,这一性质为对象的行为等价提供了一种基于共归纳原理的证明方法。首先,利用共代数给出面向对象方法中的抽象类、类和对象的形式化描述,其中抽象类被定义为一个包含方法和断言声明的类规范,类被定义为满足类规范的共代数,类的各个对象看成是共代数状态空间上的元素,而对象中方法的各种行为结构则通过强Monads进行参数化描述;接着,利用类规范的终结共代数给出对象行为等价关系的证明方法以及在各种不同Monads结构下的终结共代数语义;最后,通过实例说明如何利用PVS工具对研究结果进行验证。     

Coalgebras in functional programming and type theory

This is a survey article on the use of coalgebras in functional programming and type theory. It presents the basic theory underlying the implementation of coinductive types, families and predicates. It gives an overview of the application of corecursive methods to the study of general recursion, formal power series, tabulations of functions on inductive data. It also sketches some advanced topics in the study of the solutions to non-guarded corecursive equations and the design of non-standard type theory.     

Computable Functions on Final Coalgebras

This paper tackles computability issues on final coalgebras and tries to shed light on the following two questions: First, which functions on final coalgebras are computable? Second, which formal system allows us to define all computable functions on final coalgebras?In particular, we give a definition of computability on final coalgebras, deriving from the theory of effective domains. We then establish the admissibility of coinductive definitions and of a generalised μ-operator. This gives rise to a formal system, in which every term denotes a computable function.     

Proofs, Programs, Processes

The objective of this paper is to provide a theoretical foundation for program extraction from inductive and coinductive proofs geared to practical applications. The novelties consist in the addition of inductive and coinductive definitions to a realizability interpretation for first-order proofs, a soundness proof for this system, and applications to the synthesis of non-trivial provably correct programs in the area of exact real number computation. We show that realizers, although per se untyped, can be assigned polymorphic recursive types and hence represent valid programs in a lazy functional programming language such as Haskell. Programs extracted from proofs using coinduction can be understood as perpetual processes producing infinite streams of data. Typical applications of such processes are computations in exact real arithmetic. As an example we show how to extract a program computing the average of two real numbers w.r.t. the binary signed digit representation.     

Generalized Coiteration Schemata

Coiterative functions can be explained categorically as final coalgebraic morphisms, once coinductive types are viewed as final coalgebras. However, the coiteration schema which arises in this way is too rigid to accommodate directly many interesting classes of circular specifications. In this paper, building on the notion of T-coiteration introduced by the third author and capitalizing on recent work on bialgebras by Turi-Plotkin and Bartels, we introduce and illustrate various generalized coiteration patterns. First we show that, by choosing the appropriate monad T, T-coiteration captures naturally a wide range of coiteration schemata, such as the duals of primitive recursion and course-of-value iteration, and mutual coiteration. Then we show that, in the more structured categorical setting of bialgebras, T-coiteration captures guarded coiterations schemata, i.e. specifications where recursive calls appear guarded by predefined algebraic operations.     

Coinductive Models of Finite Computing Agents

This paper explores the role of coinductive methods in modeling finite interactive computing agents. The computational extension of computing agents from algorithms to interaction parallels the mathematical extension of set theory and algebra from inductive to coinductive models. Maximal fixed points are shown to play a role in models of observation that parallels minimal fixed points in inductive mathematics. The impact of interactive (coinductive) models on Church's thesis and the connection between incompleteness and greater expressiveness are examined. A final section shows that actual software systems are interactive rather than algorithmic. Coinductive models could become as important as inductive models for software technology as computer applications become increasingly interactive.     

Regular corecursion in Prolog

Corecursion is the ability of defining a function that produces some infinite data in terms of the function and the data itself, as supported by lazy evaluation. However, in languages such as Haskell strict operations fail to terminate even on infinite regular data, that is, cyclic data.Regular corecursion is naturally supported by coinductive Prolog, an extension where predicates can be interpreted either inductively or coinductively, that has proved to be useful for formal verification, static analysis and symbolic evaluation of programs.In this paper we use the meta-programming facilities offered by Prolog to propose extensions to coinductive Prolog aiming to make regular corecursion more expressive and easier to program with.First, we propose a new interpreter to solve the problem of non-terminating failure as experienced with the standard semantics of coinduction (as supported, for instance, in SWI-Prolog). Another problem with the standard semantics is that predicates expressed in terms of existential quantification over a regular term cannot directly defined by coinduction; to this aim, we introduce finally clauses, to allow more flexibility in coinductive definitions.Then we investigate the possibility of annotating arguments of coinductive predicates, to restrict coinductive definitions to a subset of the arguments; this allows more efficient definitions, and further enhance the expressive power of coinductive Prolog.We investigate the effectiveness of such features by showing different example programs manipulating several kinds of cyclic values, ranging from automata and context free grammars to graphs and repeating decimals; the examples show how computations on cyclic values can be expressed with concise and relatively simple programs.The semantics defined by these vanilla meta-interpreters are an interesting starting point for a more mature design and implementation of coinductive Prolog.     

The continuum as a final coalgebra

We define the continuum up to order isomorphism, and hence up to homeomorphism via the order topology, in terms of the final coalgebra of either the functor N×X, product with the set of natural numbers, or the functor 1+N×X. This makes an attractive analogy with the definition of N itself as the initial algebra of the functor 1+X, disjoint union with a singleton. We similarly specify Baire space and Cantor space in terms of these final coalgebras. We identify two variants of this approach, a coinductive definition based on final coalgebraic structure in the category of sets, and a direct definition as a final coalgebra in the category of posets. We conclude with some paradoxical discrepancies between continuity and constructiveness in this setting.