Computer Science ›› 2017, Vol. 44 ›› Issue (1): 199-202, 218.doi: 10.11896/j.issn.1002-137X.2017.01.038

Previous Articles     Next Articles

Semantics Computational Model of Formal Languages Based on Monads

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

  • Online:2018-11-13 Published:2018-11-13

Abstract: Traditional semantics modelling methods of formal languages have some drawbacks to interpret semantics and describe rule,and this paper explored semantics computation of formal languages by monads which is categorical method.It firstly constructed Kleisli category by monads,presented a semantics computational model in the formal framework of Kleisli category,and then applied it by example.Compared with traditional semantics modelling methods,the semantics computational model presented by this paper is universal and has more strong abilities of semantics interpreting and rule descripting.

Key words: Semantics computing,Monads,Ad joint functor,Formal languages,Kleisli category

[1] CHEN Y Q.Formal Languages and Automata[M].Beijing:China Machine Press,2008.(in Chinese) 陈有祺.形式语言与自动机[M].北京:机械工业出版社,2008.
[2] HE W.Category theory[M].Beijing:Science Press,2006.(inChinese) 贺伟.范畴论[M].北京:科学出版社,2006.
[3] HAGINO T.A Categorical programming language[D].Edin-burgh,UK:Laboratory for Foundations of Computer Science,Dept.of Computer Science,University of Edinburgh,1987.
[4] POLL E.Subtyping and inheritance for categorical data types[C]∥Proc.of Theories of Types and Proofs,Kyoto:Japan,RIMS Lecture Notes 1023.1998:112-125.
[5] NOGUEIRA P,MORENO-NAVARRO J.Bialgebra views:away for polytypic programming to cohabit with data abstract[C]∥Proceedings of the ACM SIGPLAN Workshop on Generic Programming,New York,2008.NY:ACM,2008:61-73.
[6] SU J D,YU S S.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.
[7] SU J D,YU S S.Comonadiccorecursions on strong coinductive data types[J].Journal of South China University of Technology(Natural Science Edition),2014,2(1):128-134.(in Chinese) 苏锦钿,余珊珊.强共归纳数据类型上的Comonadic共递归[J].华南理工大学学报(自然科学版),2014,2(1):128-134.
[8] DOREL L,VLAD R.Program equivalence by circular reasoning[J].Formal Aspects of Computing,2015,7(4):701-726.
[9] GHANI N,REVELL T,ATKEY R,et al.Fibrational units of measure [EB/OL].[2015-03-21].
[10] KENNEDY A J.Relational parametricity and units of measure[C]∥Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages(POPL ’97).New York:ACM,1997:442-455.
[11] DENIS B,ALEXANDER D,ANNIE F.Categorical grammarswith iterated types form a strict hierarchy of k-valued languages[J].Theoretical Computer Science450,2012,450(13):22-30.
[12] USA:Department of Computer Science,University of Illinois at Urbana-Champaign[R].Formal semantics and analysis of behavioral AADL models in real-time Maude,2010.
[13] BARR M,WELLS C.Category theory for computing science[M].NewYork:Prentice-Hall,1990.
[14] QU Y W.Formal semantics foundation and formal description(2nd Version)[M].Beijing:Science Press,2010.(in Chinese) 屈延文.形式语义学基础与形式说明(第二版)[M].北京:科学出版社,2010.
[15] MIAO D C,XI J Q,JIA L Y,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.
[16] LI W.Mathematical Logic[M].Beijing:Science Press,2008.(in Chinese) 李未.数理逻辑[M].北京:科学出版社,2008.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .