同步数据流语言高阶运算消去的可信翻译
作者:
基金项目:

国家自然科学基金(61272086); 国家科技支撑计划(2013BAB05B05)


Trustworthy Translation for Eliminating High-Order Operation of a Synchronous Dataflow Language
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [19]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    Lustre是一种广泛应用于工业界核心安全级控制系统的同步数据流语言,采用形式化验证的方法实现Lustre到C的编译器可以有效地提高编译器的可信度.基于这种方法,开展了从Lustre*(一种类Lustre语言)到C子集Clight的可信编译器的研究.由于Lustre*与Clight之间巨大的语言差异,整个编译过程划分为多个层次,每个层次完成特定的翻译工作.阐述了其中高阶运算消去的翻译算法,翻译过程采用辅助定理证明工具Coq实现,并进行严格的正确性证明.

    Abstract:

    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.
    [8] Lustre V6. The lustre v6 reference manual (draft). 2009. http://wwwverimag.imag.fr/DISTTOOLS/SYNCHRONE/Lustre-v6/doc/ lv6-refman.pdf
    [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.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

刘洋,甘元科,王生原,董渊,杨斐,石刚,闫鑫.同步数据流语言高阶运算消去的可信翻译.软件学报,2015,26(2):332-347

复制
分享
文章指标
  • 点击次数:5811
  • 下载次数: 7234
  • HTML阅读次数: 2735
  • 引用次数: 0
历史
  • 收稿日期:2014-07-05
  • 最后修改日期:2014-10-31
  • 在线发布日期: 2015-02-06
文章二维码
您是第19727358位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号