Clock-directed modular code generation for synchronous data-flow languages

ABSTRACT

The compilation of synchronous block diagrams into sequential imperative code has been addressed in the early eighties and can now be considered as folklore. However, separate, or modular, code generation, though largely used in existing compilers and particularly in industrial ones, has never been precisely described or entirely formalized. Such a formalization is now fundamental in the long-term goal to develop a mathematically certified compiler for a synchronous language as well as in simplifying existing implementations.

This article presents in full detail the modular compilation of synchronous block diagrams into sequential code. We consider a first-order functional language reminiscent of LUSTRE, which it extends with a general n-ary merge operator, a reset construct, and a richer notion of clocks. The clocks are used to express activation of computations in the program and are specifically taken into account during the compilation process to produce efficient imperative code. We introduce a generic machine-based intermediate language to represent transition functions, and we present a concise clock-directed translation from the source to this intermediate language. We address the target code generation phase by describing a translation from the intermediate language to JAVA and C.

References

1. T. Amagbegnon, L. Besnard, and P. Le Guernic. Implementation of the data-flow synchronous language signal. In Programming Languages Design and Implementation (PLDI), pages 163--173. ACM, 1995.
2. A. Benveniste, P. Caspi, S.A. Edwards, N. Halbwachs, P. Le Guernic, and R. de Simone. The synchronous languages 12 years later. Proceedings of the IEEE, 91(1), January 2003.
3. Sandrine Blazy, Zaynah Dargaye, and Xavier Leroy. Formal verification of a C compiler front-end. In FM 2006: Int. Symp. on Formal Methods, volume 4085 of Lecture Notes in Computer Science, pages 460--475. Springer-Verlag, 2006.
4. P. Caspi, N. Halbwachs, D. Pilaud, and J. Plaice. Lustre: a declarative language for programming synchronous systems. In 14th ACM Symposium on Principles of Programming Languages. ACM, 1987.
5. Paul Caspi and Marc Pouzet. A Co-iterative Characterization of Synchronous Stream Functions. In Coalgebraic Methods in Computer Science (CMCS'98), Electronic Notes in Theoretical Computer Science, March 1998. Extended version available as a VERIMAG tech. report no. 97--07 at www.lri.fr/~pouzet.
6. Jean-Louis Colaço, Bruno Pagano, and Marc Pouzet. A Conservative Extension of Synchronous Data-flow with State Machines. In ACM International Conference on Embedded Software (EMSOFT'05), Jersey city, New Jersey, USA, September 2005.
7. Jean-Louis Colaço and Marc Pouzet. Clocks as First Class Abstract Types. In Third International Conference on Embedded Software (EMSOFT'03), Philadelphia, Pennsylvania, USA, october 2003.
8. Jean-Louis Colaço and Marc Pouzet. Type-based Initialization Analysis of a Synchronous Data-flow Language. International Journal on Software Tools for Technology Transfer (STTT), 6(3):245--255, August 2004.
9. Sacres consortium. The declarative code dc+ , version 1.4. Technical report, Esprit project EP 20897 : Sacres, 1997.
10. The coq proof assistant, 2007. http://coq.inria.fr.
11. Thierry Gautier and Paul Le Guernic. Code generation in the sacres project. In Towards System Safety, Proceedings of the Safety-critical Systems Symposium, SSS'99, pages 127--149, Huntingdon, UK, Feb 1999. Springer.
12. Alain Girault. A survey of automatic distribution method for synchronous programs. In International Workshop on Synchronous Languages, Applications and Programs (SLAP), Edinburg, UK, April 2005. ENTCS.
13. Georges Gonthier. Sémantiques et modèles d'exécution des langages réactifs synchrones. PhD thesis, Université Paris VI, Paris, 1988.
14. N. Halbwachs. The declarative code DC, version 1.2a. Vérimag, Grenoble, France, October 1995. unpublished report.
15. N. Halbwachs, P. Raymond, and C. Ratel. Generating efficient code from data-flow programs. In Third International Symposium on Programming Language Implementation and Logic Programming, Passau (Germany), August 1991.
16. N. Halbwachs and Pascal Raymond. A tutorial of lustre. http://www-verimag.imag.fr/SYNCHRONE/, 2002.
17. F. Maraninchi and Y. Rémond. Mode-automata: a new domainspecific construct for the development of safe critical systems. Science of Computer Programming, (46):219--254, 2003.
18. The MathWorks. http://www.mathworks.com/products/simulink.
19. Steven S Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.
20. B. C. Pierce. Types and Programming Languages. MIT Press, 2002.
21. Pascal Raymond. Compilation séparée de programmes lustre. Technical report, Projet SPECTRE, IMAG, juillet 1988.
22. SCADE. http://www.esterel-technologies.com/scade/, 2007.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Source code generation