Abstract
Synchronous functional languages such as Lustre or Lucid define a restricted class of Kahn Process Networks which can be executed with no buffer. Every expression is associated to a clock indicating the instants when a value is present. A dedicated type system, the clock calculus, checks that the actual clock of a stream equals its expected clock and thus does not need to be buffered. The n-synchrony relaxes synchrony by allowing the communication through bounded buffers whose size is computed at compile-time. It is obtained by extending the clock calculus with a subtyping rule which defines buffering points.
This paper presents the first implementation of the n-synchronous model inside a Lustre-like language called Lucy-n. The language extends Lustre with an explicit buffer construct whose size is automatically computed during the clock calculus. This clock calculus is defined as an inference type system and is parametrized by the clock language and the algorithm used to solve subtyping constraints. We detail here one algorithm based on the abstraction of clocks, an idea originally introduced in [5]. The paper presents a simpler, yet more precise, clock abstraction for which the main algebraic properties have been proved in Coq. Finally, we illustrate the language on various examples including a video application.
This work is funded by the French “Action d’envergure” INRIA Synchronics.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Buck, J.T.: Scheduling Dynamic Dataflow Graphs with Bounded Memory Using the Token Flow Model. Ph.D. thesis, EECS Department, University of California, Berkeley (1993)
Caspi, P., Pilaud, D., Halbwachs, N., Plaice, J.A.: Lustre: a declarative language for real-time programming. In: POPL ’87: Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pp. 178–188. ACM, New York (1987)
Caspi, P., Pouzet, M.: Synchronous kahn networks. In: ACM SIGPLAN International Conference on Functional Programming, pp. 226–238. ACM Press, New York (1996)
Cohen, A., Duranton, M., Eisenbeis, C., Pagetti, C., Plateau, F., Pouzet, M.: N-Synchronous Kahn Networks: a Relaxed Model of Synchrony for Real-Time Systems. In: ACM International Conference on Principles of Programming Languages (POPL’06), pp. 180–193. ACM Press, New York (2006)
Cohen, A., Mandel, L., Plateau, F., Pouzet, M.: Abstraction of clocks in synchronous data-flow systems. In: Ramalingam, G. (ed.) APLAS 2008. LNCS, vol. 5356, pp. 237–254. Springer, Heidelberg (2008)
Colaço, J.L., Pouzet, M.: Clocks as First Class Abstract Types. In: Alur, R., Lee, I. (eds.) EMSOFT 2003. LNCS, vol. 2855, pp. 134–155. Springer, Heidelberg (2003)
Glpk: Gnu linear programming kit
Kahn, G.: The semantics of a simple language for parallel programming. In: Rosenfeld, J.L. (ed.) Information processing, pp. 471–475. North Holland, Amsterdam (August 1974)
Lee, E., Messerschmitt, D.: Synchronous dataflow. IEEE Trans. Comput. 75(9), 1235–1245 (1987)
Parks, T.M., Pino, J.L., Lee, E.A.: A comparison of synchronous and cycle-static dataflow. In: ASILOMAR ’95: Proceedings of the 29th Asilomar Conference on Signals, Systems and Computers, vol. 2, p. 204. IEEE Computer Society, Washington (1995)
Parks, T.M.: Bounded scheduling of process networks. Ph.D. thesis, EECS Department, University of California, Berkeley, Berkeley, CA, USA (1995)
Plateau, F.: Modèle n-synchrone pour la programmation de réseaux de Kahn à mémoire bornée. Ph.D. thesis, Université Paris-Sud 11 (January 2010)
Pouzet, M.: Lucid Synchrone, version 3. Tutorial and reference manual. Université Paris-Sud, LRI (April 2006)
Thies, W., Karczmarek, M., Amarasinghe, S.P.: Streamit: A language for streaming applications. In: Horspool, R.N. (ed.) CC 2002. LNCS, vol. 2304, pp. 179–196. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mandel, L., Plateau, F., Pouzet, M. (2010). Lucy-n: a n-Synchronous Extension of Lustre. In: Bolduc, C., Desharnais, J., Ktari, B. (eds) Mathematics of Program Construction. MPC 2010. Lecture Notes in Computer Science, vol 6120. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13321-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-13321-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13320-6
Online ISBN: 978-3-642-13321-3
eBook Packages: Computer ScienceComputer Science (R0)