More Web Proxy on the site http://driver.im/

article

Real-time FRP

Authors:

Paul HudakAuthors Info & Claims

ACM SIGPLAN Notices, Volume 36, Issue 10

Pages 146 - 156

https://doi.org/10.1145/507669.507654

Published: 01 October 2001 Publication History

Abstract

Functional reactive programming (FRP) is a declarative programming paradigm where the basic notions are continuous, time-varying behaviors and discrete, event-based reactivity. FRP has been used successfully in many reactive programming domains such as animation, robotics, and graphical user interfaces. The success of FRP in these domains encourages us to consider its use in real-time applications, where it is crucial that the cost of running a program be bounded and known before run-time. But previous work on the semantics and implementation of FRP was not explicitly concerned about the issues of cost. In fact, the resource consumption of FRP programs in the current implementation is often hard to predict. As a first step towards addressing these concerns, this paper presents real-time FRP (RT-FRP), a statically-typed language where the time and space cost of each execution step for a given program is statically bounded. To take advantage of existing work on languages with bounded resources, we split RT-FRP into two parts: a reactive part that captures the essential ingredients of FRP programs, and a base language part that can be instantiated to any generic programming language that has been shown to be terminating and resource-bounded. This allows us to focus on the issues specific to RT-FRP, namely, two forms of recursion. After presenting the operational explanation of what can go wrong due to the presence of recursion, we show how the typed version of the language is terminating and resource-bounded. Most of our FRP programs are expressible directly in RT. The rest are expressible via a simple mechanism that integrates RT-FRP with the base language.

References

[1]

G. Berry and L. Cosserat. The esterel synchronous programming language and its mathematical semantics. In AW. Roscoe S.D. Brookes and editors C. Winskel, editors, Seminar on Concurrency, volume 197 of Lect. Notes in Computer Science, pages 389--448. Springer Verlag, 1985.]]

Digital Library

[2]

Gerard Berry. The constructive semantics of pure esteral (draft version 3). Draft Version 3, Ecole des Mines de Paris and lNRIA. July 1999.]]

[3]

P. Caspi, N. Halbwachs, D. Pilaud, and J. A. Plaice. Lustre: A declarative language for programming synchronous systems. In 14th A CAI Symp. on Principles of Programming Languages. January I]]

Digital Library

[4]

Paul Caspi and Marc Pouzet. Synchronous Kaliii networks. ACM SIGPLAN Notices, 31(6):226-238. 1996.]]

Digital Library

[5]

Antony Courtney. Frappe: Functional reactive programming in Java. In Proceedings of Symposium on Practical Aspects of Declarative Languages. ACM 2001.]]

Digital Library

[6]

Anthony C. Daniels. A Semantics for Functions and Behaviours. PhD thesis, The University of Nottingham, December 1999.]]

[7]

Roberto Di Cosmo. isoniorphisms of Types: from A-calculus to information retrieval and language design. Progress in Theoretical Computer Science. Birkhauser, 1995.]]

Digital Library

[8]

Conal Elliott. Modeling interactive 3D and multimedia animation with an embedded language In Proceedings of the first conference on Domain-81)((41, Languages, pages 285-296. USENIX, October 1997.]]

Digital Library

[9]

Conal Elliott and Paul Hudak. Functional reactive animation. In International Conference on Functional Programming, pages 163--173. June 1997.]]

Digital Library

[10]

Thierry Gautier, Paul Le Guernic, and Loic Besnard. Signal: A declarative language for synchronous programming of real-time systems. In Gilles Kahn. editor. Functional Programming Languages a-nd Computer Architecture, volume 274 of Lect Not .5 iii Computer Science, edited by C. Coos and I. Hartmanis, pages 257-277. Springer-Verlag, 1987.]]

Digital Library

[11]

Thomas A. Henzinger. The theory of hybrid automata. Technical report, University of California. Berkeley, 1996.]]

[12]

Martin Hofmann. A type system for bounded space and functional in-place update. In European Symposium. on Programming (ESOP), Lecture Notes in Computer Science. Springer-Verlag, 2000.]]

Digital Library

[13]

P. Hudak, S. Peyton Jones, and P. Wadler (editors). Report on the Programming Language Haskell, A Non-strict Purely Functional Language (Version 1.2). ACM SIGPLAN Notices. 27(5), May 1992.]]

Digital Library

[14]

Paul Hudak. Building domain specific embedded languages. ACM Computing Surveys, 28A:(electronic). December 1996.]]

Digital Library

[15]

Paul Hudak. Modular domain specific languages and tools. In Proceedings of Fifth International Conference on Software Reuse, pages 134-142. IEEE Computer Society, June 1998.]]

Digital Library

[16]

Paul Hudak. The Haskell School of Expression -Learning Functional Programming through Multim.eil, a Cambridge University Press, New York, 2000.]]

Digital Library

[17]

John Hughes. Generalising monads to arrows. Scivone of Computer Programming, 37:67-111, May 2000.]]

Digital Library

[18]

John Hughes and Lars Pareto. Recursion and dynamo data-structures in bounded space: Towards embedded NIL programming. In Proceedings of the Fourth AC-11 SIGPLAN International Conference on Functional Programming (ICPP-99), volume 34.9 of ACM Sigplan Notices, pages 7081, N.Y., September 27-29 1999. ACM Press.]]

Digital Library

[19]

John Hughes, Lars Pareto, and Amr Sabry. Proving the correctness of reactive systems using sized types. In Guy L. Steele Jr, editor, In proceedings of the ACM Symposium on Principles of Programming Languages (POPL), volume 23. St Petersburg, Florida, 1996. ACM Press.]]

Digital Library

[20]

Richard Kieburtz. Real-time reactive programming for embedded controllers. Available from author's home page, March 2001.]]

[21]

Richard B. Kieburtz. Implementing closed domain-specific languages. In /361. pages 1-2, 2000.]]

Digital Library

[22]

0. (Oded) Maler, editor. Hybrid and real-time systems: international workshop, HART '97, Grenoble, France, March 26-28. 1997: proceedings, volume 1201 of Lecture Notes in Computer Science, New York, NY, USA, 1997. Springer-Verlag.]]

Digital Library

[23]

Eugenio Moggi, Walid Taha, Zinc El-Abidine Benaissa, and Tim Sheard. An idealized MetaML: Simpler, and more expressive. In European Symposium on Programming (ESOP), volume 1576 of Lecture Notes in Computer Science, pages 193-207. Springer-Verlag, 1999.]]

Digital Library

[24]

A. S. Murawski and C.-H. L. Ong. Can safe recursion be interpreted in light logic? In Second International Workshop on Implicit Computational Complexity, Santa Barbara, June 200.]]

[25]

Alan Mycroft and Richard Sharp. A statically allocated parallel functional language. In Automata, Languages and Programming. pages 37-48, 2000.]]

[26]

Oregon Graduate Institute Technical Reports. P.O. Box 91000, Portland, OR 97291 1000.USA. Available online from ftp://cse.ogi.edu/pub/tech-reports/README,html. Last viewed August 1999.]]

[27]

John Peterson, Gregory Hager, and Paul Hudak. A language for declarative robotic programming. In International Conference on Robotics and Automation, 1999.]]

[28]

John Peterson, Paul Hudak, and Conal Elliott. Lambda in motion: Controlling robots with haskell. In First International Workshop on Practical Aspects of Declarative Languages. SIGPLAN, Jan 1999.]]

Digital Library

[29]

Gordon Plotkin. A structural approach to operational semantics. Technical report, Computer Science Department, Aarhns University, 1981.]]

[30]

J. Rees and W. Clinger (eds.). The revised" report on the algorithmic language Scheme. SIGPLAN Notices, 21(12):37- 79, December 1986.]]

Digital Library

[31]

Alastair Reid, John Peterson, Greg Hager, and Paul Hudak. Prototyping real-time vision systems: An experiment in DSL design. In Proc. Int'l Conference on Software Engineering, May 1999.]]

Digital Library

[32]

John H. Reppy. CML: A higher-order concurrent language. Proceedings of the ACM SICPLAN '91 Conference on Programming Language Design and Implementation, pages 293305, 1991.]]

Digital Library

[33]

Meurig Sage. FranTk - a declarative GUI language for Haskell. In Proceedings of Fifth ACM SIGPLAN International Conference on Functional Programming, pages 106-118, Montreal, Canada, September 2000. ACM.]]

Digital Library

[34]

David Sands. A nave time analysis and its theory of cost equivalence. Journal of Logic and Computation, 5(4):495-541, 1995.]]

[35]

Walid Taha. Multi-Stage Programming: Its Theory and Applications. PhD thesis, Oregon Graduate Institute of Science and Technology, 1999. Available from {26}.]]

Digital Library

[36]

Walid Taha, editor. Semantics, Applications, and Implementation of Program Generation, volume 1924 of Lecture Notes in Computer Science, Montral. 2000. Springer-Verlag.]]

Digital Library

[37]

Walid Taha, Zinc-El-Abidine Benaissa, and Tim Sheard. Multi-stage programming: Axiomatization and type-safety. In 25th International Colloquium on Automata, Languages, and Programming (ICALP), volume 1443 of Lecture Notes in Computer Science, pages 918 929, Aalborg. 1998.]]

Digital Library

[38]

W.W. Wadge and E.A. Ashcroft. Lucid, the Dataflow Programming Language. Academic Press U.K., 1985.]]

Digital Library

[39]

Zhanyong Wan and Paul Hudak. Functional reactive programming from first principles. In Proceedings of Symposium on Programming Language Design and Implementation. ACM, 2000.]]

Digital Library

Cited By

Wu QNeuroth TIgouchkine OAditya KChen JMa K(2020)DIVA: A Declarative and Reactive Language for in situ Visualization2020 IEEE 10th Symposium on Large Data Analysis and Visualization (LDAV)10.1109/LDAV51489.2020.00007(1-11)Online publication date: Oct-2020
https://doi.org/10.1109/LDAV51489.2020.00007
Shivkumar BMurphy JZiarek L(2020)RTMLton: An SML Runtime for Real-Time SystemsPractical Aspects of Declarative Languages10.1007/978-3-030-39197-3_8(113-130)Online publication date: 14-Jan-2020
https://doi.org/10.1007/978-3-030-39197-3_8
Cardoso DVizzotto JPiveta ECamarão CSulzmann M(2018)AsyncRFJProceedings of the XXII Brazilian Symposium on Programming Languages10.1145/3264637.3264642(35-42)Online publication date: 20-Sep-2018
https://dl.acm.org/doi/10.1145/3264637.3264642
Show More Cited By

Index Terms

Real-time FRP
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
      2. Language types
        Functional languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics

Recommendations

Real-time FRP
ICFP '01: Proceedings of the sixth ACM SIGPLAN international conference on Functional programming

Functional reactive programming (FRP) is a declarative programming paradigm where the basic notions are continuous, time-varying behaviors and discrete, event-based reactivity. FRP has been used successfully in many reactive programming domains such as ...
Event-Driven FRP
PADL '02: Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages

Functional Reactive Programming (FRP) is a high-level declarative language for programming reactive systems. Previous work on FRP has demonstrated its utility in a wide range of application domains, including animation, graphical user interfaces, and ...
Rhine: FRP with type-level clocks
Haskell 2018: Proceedings of the 11th ACM SIGPLAN International Symposium on Haskell

Processing data at different rates is generally a hard problem in reactive programming. Buffering problems, lags, and concurrency issues often occur. Many of these problems are clock errors, where data at different rates is combined incorrectly. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 36, Issue 10

October 2001

276 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/507669

Issue’s Table of Contents

ICFP '01: Proceedings of the sixth ACM SIGPLAN international conference on Functional programming
October 2001
277 pages
ISBN:1581134150
DOI:10.1145/507635
General Chair:
Benjamin Pierce
Univ. of Pennsylvania

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2001

Published in SIGPLAN Volume 36, Issue 10

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

75
Total Citations
View Citations
700
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)4

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu QNeuroth TIgouchkine OAditya KChen JMa K(2020)DIVA: A Declarative and Reactive Language for in situ Visualization2020 IEEE 10th Symposium on Large Data Analysis and Visualization (LDAV)10.1109/LDAV51489.2020.00007(1-11)Online publication date: Oct-2020
https://doi.org/10.1109/LDAV51489.2020.00007
Shivkumar BMurphy JZiarek L(2020)RTMLton: An SML Runtime for Real-Time SystemsPractical Aspects of Declarative Languages10.1007/978-3-030-39197-3_8(113-130)Online publication date: 14-Jan-2020
https://doi.org/10.1007/978-3-030-39197-3_8
Cardoso DVizzotto JPiveta ECamarão CSulzmann M(2018)AsyncRFJProceedings of the XXII Brazilian Symposium on Programming Languages10.1145/3264637.3264642(35-42)Online publication date: 20-Sep-2018
https://dl.acm.org/doi/10.1145/3264637.3264642
Murphy TJanin DSperber M(2016)A livecoding semantics for functional reactive programmingProceedings of the 4th International Workshop on Functional Art, Music, Modelling, and Design10.1145/2975980.2975986(48-53)Online publication date: 10-Sep-2016
https://dl.acm.org/doi/10.1145/2975980.2975986
Helbling CGuyer SJanin DSperber M(2016)Juniper: a functional reactive programming language for the ArduinoProceedings of the 4th International Workshop on Functional Art, Music, Modelling, and Design10.1145/2975980.2975982(8-16)Online publication date: 10-Sep-2016
https://dl.acm.org/doi/10.1145/2975980.2975982
Kazemi ZCheng A(2016)A Scratchpad Memory-Based Execution Platform for Functional Reactive Systems and Its Static Timing Analysis2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA.2016.43(176-181)Online publication date: Aug-2016
https://doi.org/10.1109/RTCSA.2016.43
Chen YAcar UTangwongsan K(2014)Functional programming for dynamic and large data with self-adjusting computationACM SIGPLAN Notices10.1145/2692915.262815049:9(227-240)Online publication date: 19-Aug-2014
https://dl.acm.org/doi/10.1145/2692915.2628150
Chen YAcar UTangwongsan KJeuring JChakravarty M(2014)Functional programming for dynamic and large data with self-adjusting computationProceedings of the 19th ACM SIGPLAN international conference on Functional programming10.1145/2628136.2628150(227-240)Online publication date: 19-Aug-2014
https://dl.acm.org/doi/10.1145/2628136.2628150
Bainomugisha ECarreton ACutsem TMostinckx SMeuter W(2013)A survey on reactive programmingACM Computing Surveys10.1145/2501654.250166645:4(1-34)Online publication date: 30-Aug-2013
https://dl.acm.org/doi/10.1145/2501654.2501666
ACAR UBLUME MDONHAM J(2013)A consistent semantics of self-adjusting computationJournal of Functional Programming10.1017/S095679681300009923:3(249-292)Online publication date: 22-Oct-2013
https://doi.org/10.1017/S0956796813000099
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents