Computer Science ›› 2016, Vol. 43 ›› Issue (3): 188-192.doi: 10.11896/j.issn.1002-137X.2016.03.035

Previous Articles     Next Articles

Fibrations Method of Co-inductive Data Types in Programming

MIAO De-cheng, XI Jian-qing, DAI Jing-guo and SU Jin-dian   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Traditional methods of co-inductive data types in programming,such as co-algebra and category theory,have some problems in analyzing semantics behaviors and describing co-inductive rules.Considering the status quo of co-inductive data types researches both at home and abroad,a fibrations method was proposed in this paper.Firstly, some basic logical structures of co-inductive data types are systematically analyzed over a fibration including reindexed functor,op-reindexed functor and truth functor,and the corresponding relationship between co-inductive data types and their semantic behaviors on program logic is established by equality functor and quotient functor.Then semantic behaviors of co-inductive data types are deeply analyzed .Secondly, co-recursive operations are constructed to describe abstractly co-inductive rules of co-inductive data types with universality by endo-functors in base categories and their equality-preserving lifting in total categories.At last applications of fibrations method are briefly introduced by examples.

Key words: Semantic behaviors,Co-inductive rules,Fibrations method,Co-inductive data types,Lifting

[1] Greiner J.Programming with inductive and co-inductive types:Tech.Report CMU-CS-92-109[R].Pittsburgh,USA:School of Computer Science,Carnegie Mellon University,1992
[2] Rutten J.Universal coalgebra:a theory of systems[J].Theoretical Computer Science,2000,249(1):3-80
[3] Zhou Xiao-cong,Shu Zhong-mei.A survey on the coalgebraicmethods in computer science[J].Journal of Software,2003,14(10):1661-1671(in Chinese) 周晓聪,舒忠梅.计算机科学中的共代数方法的研究综述[J].软件学报,2003,4(10):1661-1671
[4] Johnson M,Rosebrugh R.Fibrations and universal view upda-tability[J].Theoretical Computer Science,2007,388:109-129
[5] Johnson M,Rosebrugh R,Wood R J.Lenses,fibrations and universal translations[J].Mathematics Structure in Computer Science,2012,22:25-42
[6] Tews H.Coalgebra method for object-oriented specification[D].Dresden,Germany:Institute Theoretische Informatik,Technischen Universiy Dresden,2002
[7] Ghani N,Johann P,Fumex C.Generic fibrational induction[J].Logical Methods in Computer Science,2012,8(2):1-27
[8] Miao De-cheng,Xi Jian-qing,Jia Lian-yin,et al.Formal language algebraic model [J].Journal of South China University of Technology (Natural Science Edition),2011,39(10):74-78(in Chinese) 苗德成,奚建清,贾连印,等.一种形式语言代数模型[J].华南理工大学学报(自然科学版),2011,9(10):74-78
[9] Hermida C,Jacobs B.Structural induction and coinduction in a fibrational setting[J].Information and Computation,1998,5(2):107-152
[10] Barr M,Wells C.Category theory for computing science[M].NewYork:Prentice-Hall,1990:252-270
[11] He Wei.Category theory[M].Beijing:Science Press,2006:23-69(in Chinese) 贺伟.范畴论[M].北京:科学出版社,2006:23-69
[12] Ghani N,Johann P,Fumex C.Indexed induction and coinduction,fibrationally[J].Logical Methods in Computer Science,2013,9(3-6):1-31
[13] Hermida C.Fibrations,Logical Predicates and Related Topics[D].Edinburgh,UK:University of Edinburgh,1993
[14] Su Jin-dian,Yu Shan-shan.Coinductive data types and their applications in programming languages[J].Computer Science,2011,8(11):114-118(in Chinese) 苏锦钿,余珊珊.程序语言中的共归纳数据类型及其应用[J].计算机科学,2011,8(11):114-118
[15] Hagino T.A categorical programming language[D].Edin-burgh,UK:Laboratory for Foundations of Computer Science,Dept of Computer Science,University of Edinburgh,1987
[16] Nogueira P,Moreno-Navarro J.Bialgebra views:a way for poly-typic programming to cohabit with data abstract[C]∥Procee-dings of the ACM SIGPLAN Workshop on Generic Programming.ACM New York,NY:2008:61-73
[17] Poll E.Subtyping and inheritance for categorical datatypes[J].RIMS Lecture Notes,1998,3:112-125
[18] Hinze R.Reasoning about codata[J].Lecture Notes in Compu-ter Science,2010,9:42-93
[19] Gimenez E,Casteran P.A Turorial on Co-inductive Types in Coq.May 1998.http:www.labri.fr/perso/casteran/RecTutorial.pdf
[20] Vene V.Categorical programming with inductive and coinductive types[D].Tartu,Estonia:University of Tartu,2000

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!