Journal of South China University of Technology(Natural Science Edition) ›› 2011, Vol. 39 ›› Issue (12): 44-50.

• Computer Science & Technology • Previous Articles     Next Articles

Bialgebraic Structure of Abstract Data Types

Su Jin-dian1  Yu Shan-shan2   

  1. 1. School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China; 2. School of Information Science and Technology,Sun Yat-Sen University,Guangzhou 510275,Guangdong,China
  • Received:2011-03-24 Revised:2011-07-17 Online:2011-12-25 Published:2011-11-04
  • Contact: 苏锦钿(1980-) ，男，博士，讲师，主要从事形式化方法、形式语义、构件技术、共代数与双代数研究． E-mail:sujd@scut.edu.cn
  • About author:苏锦钿(1980-) ，男，博士，讲师，主要从事形式化方法、形式语义、构件技术、共代数与双代数研究．
  • Supported by:

    国家自然科学基金资助项目( 61103039) ; 高等学校博士学科点专项科研基金资助项目( 20100172120043) ; 华南理工大学中央高校基本科研业务费专项资金资助项目( 2009ZM0158)

PDF

1243

Abstract:

As algebraic or coalgebraic methods have some disadvantages in analyzing the relationships and properties between the syntactic constructions and the dynamic behaviors of abstract data types,this paper presents a bialgebraic structure of abstract data types based on the category theory and the distributive laws,usesλ -bialgebras to naturally describe the transformation between the syntactic constructions and the dynamic behaviors,and employs distributive laws to functorially lift coalgebraic and algebraic functors,thus lifting initial algebras ( or final coalgebras) to initial ( or final)λ -bialgebra. Moreover,the functorial lifting is applied to the definition and computation of recursive and corecursive functions. Case study indicates that,as the functorial lifting extends the inductive principles of algebras and the coinductive principles of coalgebras,it helps to improve the abilities of programming languages in describing or proving the properties of abstract data types.

Key words: abstract data type, coalgebras, bialgebras, corecursion

CLC Number: