Synchronous Kahn networks

ABSTRACT

Synchronous data-flow is a programming paradigm which has been successfully applied in reactive systems. In this context, it can be characterized as some class of static bounded memory data-flow networks. In particular, these networks are not recursively defined, and obey some kind of "synchronous" constraints (clock calculus). Based on Kahn's relationship between data-flow and stream functions, the synchronous constraints can be related to Wadler's listlessness, and can be seen as sufficient conditions ensuring listless evaluation. As a by-product, those networks enjoy efficient compiling techniques. In this paper, we show that it is possible to extend the class of static synchronous data-flow to higher order and dynamical networks, thus giving sense to a larger class of synchronous data-flow networks.This is done by extending both the synchronous operational semantics, the clock calculus and the compiling technique of static data-flow networks, to these more general networks.

REFERENCES

• 1: IEEE standard VHDL reference manual. Technical report, 1988.
• 2: Albert Benveniste , Paul Le Guernic , Christian Jacquemot, Synchronous programming with events and relations: the SIGNAL language and its semantics, Science of Computer Programming, v.16 n.2, p.103-149, Sept. 1991 [doi>10.1016/0167-6423(91)90001-E]
• 3: Andrew Gill , John Launchbury , Simon L. Peyton Jones, A short cut to deforestation, Proceedings of the conference on Functional programming languages and computer architecture, p.223-232, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165214]
• 4: William W. Wadge , Edward A. Ashcroft, LUCID, the dataflow programming language, Academic Press Professional, Inc., San Diego, CA, 1985
• 5: E. A. Ashcroft , W. W. Wadge, Lucid, a nonprocedural language with iteration, Communications of the ACM, v.20 n.7, p.519-526, July 1977 [doi>10.1145/359636.359715]
• 6: L. Augustsson and T. Johnsson. Lazyml user's manual version 0.999.4. Technical report, Chalmers University of Technology, Goteborg, Sweden, 1993.
• 7: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V]
• 8: F. Boussinot. R~seaux de processus r~actifs. Technical Report 1588, INRIA Sophia-Antipolis, janvier 1992.
• 9: Paul Caspi, Clocks in dataflow languages, Theoretical Computer Science, v.94 n.1, p.125-140, March 1992 [doi>10.1016/0304-3975(92)90326-B]
• 10: P. Caspi. Towards recursive block diagrams. In 19th IFA U/IFIP Workshop on real-time programming, Isle of Reichenau, Germany, June 1994. iFAC.
• 11: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• 12: D.P. Friedman and D.S. Wise. CONS should not evaluate its arguments. In Proceding of the ICALP'76 Conference, pages 257-284, 1976.
• 13: J.L. Giavitto. A synchronous data-flow language for massively parallel computers. In Parallel Computzng'91, London, 1991.
• 14: John T. Feo , David C. Cann , Rodney R. Oldehoeft, A report on the Sisal language project, Journal of Parallel and Distributed Computing, v.10 n.4, p.349-366, Dec. 1990 [doi>10.1016/0743-7315(90)90035-N]
• 15: G. Kahn. The semantics of a simple language for parallel programming. In IFIP 7~ Congress. North Holland, Amsterdam, 1974.
• 16: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987 [doi>10.1109/TC.1987.5009446]
• 17: Xavier Leroy. The carol light system : release 0.7 : documentation and user's manual. Technical report, INRIA, INRIA, Domaine de Voluceau-Rocquencourt, 78153 Le Chesnay Cedex, France, July 1995.
• 18: C. Maurras. Alpha, un langage iquationnel pour la conception d'architectures parall~les synchrone. PhD thesis, Universit~ de Rennes 1, France, 1989.
• 19: Alan Mycroft, Polymorphic Type Schemes and Recursive Definitions, Proceedings of the 6th Colloquium on International Symposium on Programming, p.217-228, April 17-19, 1984
• 20: P. Raymond N. Halbwachs, P. Caspi and D. Pilaud. The synchronous datafiow programming language LUSTRE. Proceedings of the IEEE, 79(9):1305-1320, 1991.
• 21: P. Caspi , D. Pilaud , N. Halbwachs , J. A. Plaice, LUSTRE: a declarative language for real-time programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.178-188, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41641]
• 22: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 23: D.A. Turner. A new implementation technique for applicative languages. Software Practice and Experience, 9:31-49, 1979.
• 24: W.G. Vree and P.H. Hartel. Communication lifting: fixed point computation for parallelism. Journal of Functional Programming, 1(1):1-33, 1993.
• 25: Philip Wadler, Listlessness is better than laziness: Lazy evaluation and garbage collection at compile-time, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.45-52, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802020]
• 26: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Design, Languages, Measurement, Theory, Verification