Article

E-FRP with priorities

Authors:

Roumen Kaiabachev,

Angela ZhuAuthors Info & Claims

EMSOFT '07: Proceedings of the 7th ACM & IEEE international conference on Embedded software

Pages 221 - 230

https://doi.org/10.1145/1289927.1289963

Published: 30 September 2007 Publication History

Abstract

E-FRP is declarative language for programming resource-bounded, event-driven systems. The original high-level semantics of E-FRP requires that each event handler execute atomically. This requirement facilitates reasoning about EFRP programs, and therefore it is a desirable feature of the language. But the original compilation strategy requires that each handler complete execution before another event can occur. This implementation choice treats all events equally, in that it forces the upper bound on the time needed to respond to any event to be the same. While this is acceptable for many applications, it is often the case that some events are more urgent than others.

In this paper, we show that we can improve the compilation strategy without altering the high-level semantics. With this new compilation strategy, we give the programmer more control over responsiveness without taking away the ability to reason about programs at a high level. The programmer controls responsiveness by declaring priorities for events, and the compilation strategy produces code that uses preemption to enforce these priorities. We show that the compilation strategy enjoys the same properties as the original strategy, with the only change being that the programmer reasons modulo permutations on the order of event arrivals.

References

[1]

G. Berry. The Constructive Semantics of Pure Esterel. Draft 3. ftp://ftpsop.inria.fr/esterel/pub/papers/constructiveness3.ps,July 1999.

[2]

G. Berry and L. Cosserat. The Esterel synchronous programming language and its mathematical semantics. In Seminar on Concurrency, Carnegie-Mellon University, pages 389--448, London, UK, 1985. Springer-Verlag.

Digital Library

[3]

D. D. Bovet and M. Cesati. Understanding the Linux kernel. O'Reilly & Associates, Inc., Sebastopol, CA, 2000.

Digital Library

[4]

P. Caspi, D. Pilaud, N. Halbwachs, and J. A. Plaice. Lustre: a declarative language for real-time programming. In POPL'87, pages 178--188, New York, NY, USA, 1987. ACM Press.

Digital Library

[5]

K. Donnelly and M. Fluet. Transactional events. In ICFP'06, pages 124--135. ACM Press, September 2006.

Digital Library

[6]

C. Elliott and P. Hudak. Functional reactive animation. In ICFP'97, volume 32(8), pages 263--273, 1997.

Digital Library

[7]

C. Flanagan and S. Qadeer. A type and effect system for atomicity. In PLDI'03, pages 338--349, New York, NY, USA, 2003. ACM Press.

Digital Library

[8]

C. Flanagan and S. Qadeer. Types for atomicity. In TLDI'03, pages 1--12, New York, NY, USA, 2003. ACM Press.

Digital Library

[9]

T. Gautier, P. L. Guernic, and L. Besnard. Signal: A declarative language for synchronous programming of real-time systems. In FPCA'87, pages 257--277, London, UK, 1987. Springer-Verlag.

Digital Library

[10]

D. Grossman. Software transactions are to concurrency as garbage collection is to memory management. Technical report, UW-CSE, Apr. 2006.

[11]

T. Harris and K. Fraser. Language support for lightweight transactions. In OOPSLA'03, pages 388--402, New York, NY, USA, 2003. ACM Press.

Digital Library

[12]

T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In PPoPP'05, pages 48--60, New York, NY, USA, 2005. ACM Press.

Digital Library

[13]

T. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing memory transactions. SIGPLAN, vol.41 (num. 6): p14--25, 2006.

Digital Library

[14]

P. Hudak. The Haskell School of Expression - Learning Functional Programming Through Multimedia. Cambridge University Press, 2000.

Digital Library

[15]

R. Kaiabachev, W. Taha, and A. Zhu. E-FRP with Priorities (extended version). http://www.cs.rice.edu/taha/publications/preprints,2007-08-15-TR.pdf.

Digital Library

[16]

J. Manson, J. Baker, A. Cunei, S. Jagannathan, M. Prochazka, B. Xin, and J. Vitek. Preemptible atomic regions for real-time java. In RTSS'05, pages 62--71, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[17]

J. Nordlander, M. Carlsson, M. P. Jones, and J. Jonsson. Programming with time-constrained reactions. In Submitted for publication, 2004.

[18]

J. Nordlander, M. P. Jones, M. Carlsson, R. B. Kieburtz, and A. Black. Reactive objects. In ISORC'02, page 155, Washington, DC, USA, 2002. IEEE Computer Society.

[19]

J. Palsberg and D. Ma. A typed interrupt calculus. In FTRTFT'02, LNCS 2469, pages 291--310. Springer-Verlag, 2002.

Digital Library

[20]

J. Peterson, G. Hager, and P. Hudak. A language for declarative robotic programming. In ICRA'99. IEEE, May 1999.

[21]

J. Peterson and K. Hammond. Haskell 1.4, a non-strict, purely functional language. Technical report, Haskell comittee, Apr. 1997.

[22]

A. Reid, J. Peterson, G. Hager, and P. Hudak. Prototyping real-time vision systems: An experiment in DSL design. In ICSE'99, pages 484--493, 1999.

Digital Library

[23]

M. F. Ringenburg and D. Grossman. AtomCaml: First-class atomicity via rollback. In ICFP'05. ACM, September 2005.

Digital Library

[24]

A. Rubini and J. Corbet. Linux Device Drivers. O'Reilly & Associates, Inc., Sebastopol, CA, second edition, 2001.

Digital Library

[25]

T. Shanley. Protected Mode Software Architecture. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1996.

Digital Library

[26]

N. Shavit and D. Touitou. Software transactional memory. In PODC'95, pages 204--213, August 20-23 1995. Ottawa, Ont. Canada.

Digital Library

[27]

D. Solomon and M. Russinovich. Inside Microsoft Windows 2000. Microsoft Press, 3rd edition, 2000.

Digital Library

[28]

J. A. Stankovic. Misconceptions about real-time computing: A serious problem for next-generation systems. Computer, Vol. 21 (Num. 10): p10--19, 1988.

Digital Library

[29]

Z. Wan and P. Hudak. Functional reactive programming from first principles. In PLDI'00. ACM, 2000.

Digital Library

[30]

Z. Wan, W. Taha, and P. Hudak. Real-time FRP. In ICFP'01, pages 146--156, New York, NY, USA, 2001. ACM Press.

Digital Library

[31]

Z. Wan, W. Taha, and P. Hudak. Event-driven FRP. In PADL'02, Lecture Notes in Computer Science. Springer, January 19-20 2002.

Digital Library

Cited By

Cheng A(2023)Work in Progress: Response Time Analysis of Real-Time Quantum Computing Systems2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00033(329-332)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00033
Lin JCheng A(2018)P-FRP task scheduling with preemption thresholdACM SIGBED Review10.1145/3269482.326948515:4(15-19)Online publication date: 20-Aug-2018
https://dl.acm.org/doi/10.1145/3269482.3269485
Watanabe T(2018)A Simple Context-Oriented Programming Extension to an FRP Language for Small-Scale Embedded SystemsProceedings of the 10th ACM International Workshop on Context-Oriented Programming: Advanced Modularity for Run-time Composition10.1145/3242921.3242925(23-30)Online publication date: 16-Jul-2018
https://dl.acm.org/doi/10.1145/3242921.3242925
Show More Cited By

Index Terms

E-FRP with priorities
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Event-driven programming with EScala
AOSD '11: Proceedings of the tenth international conference on Aspect-oriented software development companion

EScala is an extension of Scala with support for declarative event-driven programming. It provides mechanisms for declarative definition of events and employs aspect-oriented techniques for exposing implicitly existing events, which reduces the need for ...
EScala: modular event-driven object interactions in scala
AOSD '11: Proceedings of the tenth international conference on Aspect-oriented software development

Event-driven programming style in OO languages based on imperatively triggered events does not support separate and more declarative event definitions by composition or transformation of other events. AO language mechanisms for defining events as ...
P: safe asynchronous event-driven programming
PLDI '13

We describe the design and implementation of P, a domain-specific language to write asynchronous event driven code. P allows the programmer to specify the system as a collection of interacting state machines, which communicate with each other using ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EMSOFT '07: Proceedings of the 7th ACM & IEEE international conference on Embedded software

September 2007

304 pages

ISBN:9781595938251

DOI:10.1145/1289927

Program Chairs:
Christoph M. Kirsch
University of Salzburg
,
Reinhard Wilhelm
Saarland University

Copyright © 2007 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 September 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ESWEEK07

Sponsor:

ESWEEK07: Third Embedded Systems Week

September 30 - October 3, 2007

Salzburg, Austria

Acceptance Rates

Overall Acceptance Rate 60 of 203 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
233
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cheng A(2023)Work in Progress: Response Time Analysis of Real-Time Quantum Computing Systems2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00033(329-332)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00033
Lin JCheng A(2018)P-FRP task scheduling with preemption thresholdACM SIGBED Review10.1145/3269482.326948515:4(15-19)Online publication date: 20-Aug-2018
https://dl.acm.org/doi/10.1145/3269482.3269485
Watanabe T(2018)A Simple Context-Oriented Programming Extension to an FRP Language for Small-Scale Embedded SystemsProceedings of the 10th ACM International Workshop on Context-Oriented Programming: Advanced Modularity for Run-time Composition10.1145/3242921.3242925(23-30)Online publication date: 16-Jul-2018
https://dl.acm.org/doi/10.1145/3242921.3242925
Murphy JShivkumar BPritchard AIraci GKumar DKim SZiarek L(2018)A survey of real‐time capabilities in functional languages and compilersConcurrency and Computation: Practice and Experience10.1002/cpe.490231:4Online publication date: 23-Oct-2018
https://doi.org/10.1002/cpe.4902
Batalla JVasilakos AGajewski M(2017)Secure Smart HomesACM Computing Surveys10.1145/312281650:5(1-32)Online publication date: 26-Sep-2017
https://dl.acm.org/doi/10.1145/3122816
Brandtzaeg PFølstad A(2017)Trust and distrust in online fact-checking servicesCommunications of the ACM10.1145/312280360:9(65-71)Online publication date: 23-Aug-2017
https://dl.acm.org/doi/10.1145/3122803
Pulido-Prieto OJuárez-Martínez U(2017)A Survey of Naturalistic Programming TechnologiesACM Computing Surveys10.1145/310948150:5(1-35)Online publication date: 26-Sep-2017
https://dl.acm.org/doi/10.1145/3109481
Peisert S(2017)Security in high-performance computing environmentsCommunications of the ACM10.1145/309674260:9(72-80)Online publication date: 23-Aug-2017
https://dl.acm.org/doi/10.1145/3096742
Watanabe TSawada K(2017)Towards Reflection in an FRP Language for Small-Scale Embedded SystemsCompanion Proceedings of the 1st International Conference on the Art, Science, and Engineering of Programming10.1145/3079368.3079387(1-6)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1145/3079368.3079387
Zou XCheng ARincon CJiang Y(2017)Multi-mode P-FRP Task Scheduling2017 IEEE 20th International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC.2017.19(150-157)Online publication date: May-2017
https://doi.org/10.1109/ISORC.2017.19
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.

Figures

Tables

Media

View Table of Conten