Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China ;School of Information Science and Engineering, Xinjiang University, Urumqi 830046, China 在期刊界中查找 在百度中查找 在本站中查找
Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China ;School of Computer Science, Taiyuan University of Technology, Taiyuan 030021, China 在期刊界中查找 在百度中查找 在本站中查找
Lustre is a synchronous dataflow language widely used in safety critical industrial control system. Formal verification is efficient to improve the reliability of the compiler which translates Lustre to C. Based on this approach, this paper conducts a research on the trustworthy compiler for translating Lustre*(a Lustre-like language) to Clight (a subset language of C). The entire compiling process is divided into different stages to tackle the large difference between Lustre* and Clight. Each stage performs a specific translation task. This paper describes a translation algorithm which eliminates high-order operations. The implementation of translation process is assisted by theorem proving tool Coq, and a strict proof of correctness of the process is also provided.
[1] Halbwachs N. A synchronous language at work: The story of Lustre. In: Proc. of the 2nd ACM/IEEE Int'l Conf. on Formal Methods and Models for Co-Design (MEMOCODE 2005). IEEE Computer Society Washington, 2005.[doi: 10.1109/MEMCOD. 2005.1487884]
[2] Benveniste A, Caspi P, Edwards SA, Halbwachs N, Le Guernic P, de Simone R. The synchronous languages twelve years later. Proc. of the IEEE, 2003,91(1):64-83.[doi: 10.1109/JPROC.2002.805826]
[3] Caspi P, Pilaud D, Halbwachs N, Plaice J. Lustre: A declarative language for programming synchronous systems. In: Proc. of the 14th ACM Symp. on Principles of Programming Languages (POPL'87). 1987.
[4] CompCert home page. http://compcert.inria.fr/
[5] Xavier Leroy. Formal verification of a realistic compiler. Communications of the ACM—CACM,2009,52(7):107-115.[doi: 10. 1145/1538788.1538814]
[6] Blazy S, Leroy X. Mechanized semantics for the Clight subset of the C language. Journal of Automated Reasoning, 2009,43(3): 263-288.[doi: 10.1007/s10817-009-9148-3].
[7] Halbwachs N, Caspi P, Raymond P, Pilaud D. The synchronous dataflow programming language LUSTRE. Proc. of the IEEE, 1991, 79(9):1305-1320.
[9] Paulin C, Pouzet M. Certified compilation of scade/lustre. 2006. http://www.lri.fr/paulin/lustreincoq.pdf
[10] Le Sergent T. SCADE: A comprehensive framework for critical system and software engineering. In: Proc. of the Intergrating System and Software Modeling. LNCS 7083, Berlin, Herdelberg: Springer-Verlag, 2012. 2-3.
[11] Ngo VC, Talpin JP, Gautier T, Le Guernic P, Besnard L. Formal verification of synchronous data-flow compilers. Project-Team ESPRESSO Research Report, No.7921. 2012.
[12] The Coq Development Team. The Coq proof assistant reference manual version V8.3. 2010. http://coq.inria.fr/
[13] Shi G, Wang SY, Dong Y, Ji ZY, Gan YK, Zhang LB, Zhang YC, Wang L, Yang F. Construction for the trustworthy compiler of a synchronous data-flow language. Ruan Jian Xue Bao/Journal of Software, 2014,25(2):341-356 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4542.htm[doi: 10.13328/j.cnki.jos.004542]
[14] Gan YK, Zhang LB, Shi G, Wang SY, Dong Y, Zhang ZH, Wang YH. A verified sequentializer for synchronous data-flow programs. Computer Applications and Software, 2014,31(5):1-6.
[15] Pnueli A, Siegel M, Singerman E. Translation validation. In: Proc. of the TACAS'98. LNCS 1384, 1998.
[16] Pnueli A, Shtrichman O, Siegel M. Translation validation for synchronous languages. In: Proc. of the ICALP'98. LNCS 1443, 1998. 235C246.
[17] Biernacki D, Cola_co JL, Hamon G, Pouzet M. Clock-Directed modular code generation for synchronous data-flow languages. In: Proc. of the LCTES. 2008. 121-30.[doi: 10.1145/1375657.1375674]
[18] Auger C, Cola_co JL, Hamon G, Pouzet M. A formalization and proof of a modular lustre compiler. 2012. http://www.di.ens.fr/ pouzet/cours/mpri/cours4/scp12.pdf
[19] Zhang LB, Gan YK, Shi G, Wang SY, Dong Y, Zhang ZH, Wang YH. A certified translation for eliminating temporal feature of a synchronize dataflow program. Computer Engineering and Design, 2014,35(1):137-143.