E-FRP with priorities

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érard Berry , Laurent Cosserat, The ESTEREL Synchronous Programming Language and its Mathematical Semantics, Seminar on Concurrency, Carnegie-Mellon University, p.389-448, July 09-11, 1984
• 3: Daniel Pierre Bovet , Marco Cassetti , Andy Oram, Understanding the Linux Kernel, O'Reilly & Associates, Inc., Sebastopol, CA, 2000
• 4: 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]
• 5: Kevin Donnelly , Matthew Fluet, Transactional events, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 6: Conal Elliott , Paul Hudak, Functional reactive animation, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.263-273, June 09-11, 1997, Amsterdam, The Netherlands
• 7: Cormac Flanagan , Shaz Qadeer, A type and effect system for atomicity, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 8: Cormac Flanagan , Shaz Qadeer, Types for atomicity, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 9: Thierry Gautier , Paul Le Guernic , Löic Besnard, SIGNAL: A declarative language for synchronous programming of real-time systems, Proc. of a conference on Functional programming languages and computer architecture, p.257-277, October 1987, Portland, Oregon, United States
• 10: D. Grossman. Software transactions are to concurrency as garbage collection is to memory management. Technical report, UW-CSE, Apr. 2006.
• 11: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 12: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 13: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, ACM SIGPLAN Notices, v.41 n.6, June 2006
• 14: Paul Hudak, The Haskell school of expression: learning functional programming through multimedia, Cambridge University Press, New York, NY, 2000
• 15: Roumen Kaiabachev , Walid Taha , Angela Zhu, E-FRP with priorities, Proceedings of the 7th ACM & IEEE international conference on Embedded software, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289927.1289963]
• 16: Jeremy Manson , Jason Baker , Antonio Cunei , Suresh Jagannathan , Marek Prochazka , Bin Xin , Jan Vitek, Preemptible Atomic Regions for Real-Time Java, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.62-71, December 05-08, 2005 [doi>10.1109/RTSS.2005.34]
• 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: Jens Palsberg , Di Ma, A Typed Interrupt Calculus, Proceedings of the 7th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems: Co-sponsored by IFIP WG 2.2, p.291-310, September 09-12, 2002
• 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: Alastair Reid , John Peterson , Greg Hager , Paul Hudak, Prototyping real-time vision systems: an experiment in DSL design, Proceedings of the 21st international conference on Software engineering, p.484-493, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302681]
• 23: Michael F. Ringenburg , Dan Grossman, AtomCaml: first-class atomicity via rollback, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 24: Jonathan Corbet , Alessandro Rubini , Greg Kroah-Hartman, Linux Device Drivers, 3rd Edition, O'Reilly Media, Inc., 2005
• 25: Tom Shanley, Protected Mode Software Architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 26: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 27: David A. Solomon , Mark Russinovich, Inside Microsoft Windows 2000, Microsoft Press, Redmond, WA, 2000
• 28: John A. Stankovic, Misconceptions About Real-Time Computing: A Serious Problem for Next-Generation Systems, Computer, v.21 n.10, p.10-19, October 1988 [doi>10.1109/2.7053]
• 29: Zhanyong Wan , Paul Hudak, Functional reactive programming from first principles, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.242-252, June 18-21, 2000, Vancouver, British Columbia, Canada
• 30: Zhanyong Wan , Walid Taha , Paul Hudak, Real-time FRP, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 31: Zhanyong Wan , Walid Taha , Paul Hudak, Event-Driven FRP, Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages, p.155-172, January 19-20, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Design, Languages, Reliability

Keywords:
event-driven programming, resource-aware programming