Flask: staged functional programming for sensor networks

ABSTRACT

Severely resource-constrained devices present a confounding challenge to the functional programmer: we are used to having powerful abstraction facilities at our fingertips, but how can we make use of these tools on a device with an 8- or 16-bit CPU and at most tens of kilobytes of RAM? Motivated by this challenge, we have developed Flask, a domain specific language embedded in Haskell that brings the power of functional programming to sensor networks, collections of highly resource-constrained devices. Flask consists of a staging mechanism that cleanly separates node-level code from the meta-language used to generate node-level code fragments; syntactic support for embedding standard sensor network code; a restricted subset of Haskell that runs on sensor networks and constrains program space and time consumption; a higher-level "data stream" combinator library for quickly constructing sensor network programs; and an extensible runtime that provides commonly-used services.

We demonstrate Flask through several small code examples as well as a compiler that generates node-level code to execute a network-wide query specified in a SQL-like language. We show how using Flask ensures constraints on space and time behavior. Through microbenchmarks and measurements on physical hardware, we demonstrate that Flask produces programs that are efficient in terms of CPU and memory usage and that can run effectively on existing sensor network hardware.

REFERENCES

• 1: Andreas M. Ali , Kung Yao , Travis C. Collier , Charles E. Taylor , Daniel T. Blumstein , Lewis Girod, An empirical study of collaborative acoustic source localization, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236367]
• 2: Amol Bakshi , Viktor K. Prasanna , Jim Reich , Daniel Larner, The Abstract Task Graph: a methodology for architecture-independent programming of networked sensor systems, Proceedings of the 2005 workshop on End-to-end, sense-and-respond systems, applications and services, June 05-05, 2005, Seattle, Washington
• 3: Amol Bakshi , Viktor K. Prasanna , Jim Reich , Daniel Larner, The Abstract Task Graph: a methodology for architecture-independent programming of networked sensor systems, Proceedings of the 2005 workshop on End-to-end, sense-and-respond systems, applications and services, June 05-05, 2005, Seattle, Washington
• 4: Elaine Cheong , Judy Liebman , Jie Liu , Feng Zhao, TinyGALS: a programming model for event-driven embedded systems, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952668]
• 5: Koen Claessen , John Hughes, QuickCheck: a lightweight tool for random testing of Haskell programs, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.268-279, September 2000
• 6: Antony Courtney and Conal Elliott. Genuinely functional user interfaces. In 2001 Haskell Workshop, September 2001.
• 7: 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
• 8: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 9: Omprakash Gnawali , Ki-Young Jang , Jeongyeup Paek , Marcos Vieira , Ramesh Govindan , Ben Greenstein , August Joki , Deborah Estrin , Eddie Kohler, The Tenet architecture for tiered sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182823]
• 10: Michael I. Gordon , William Thies , Michal Karczmarek , Jasper Lin , Ali S. Meli , Andrew A. Lamb , Chris Leger , Jeremy Wong , Henry Hoffmann , David Maze , Saman Amarasinghe, A stream compiler for communication-exposed architectures, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 11: E. Goto. Monocopy and associative algorithms in an extended LISP. Technical Report 74-03, Univ. of Tokyo, Information Science Lab., May 1974.
• 12: Ramakrishna Gummadi , Nupur Kothari , Ramesh Govindan , Todd Millstein, Kairos: a macro-programming system for wireless sensor networks, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom [doi>10.1145/1095810.1118600]
• 13: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 14: Paul Hudak, Antony Courtney, Henrik Nilsson, and John Peterson. Arrows, robots, and functional reactive programming. In Summer School on Advanced Functional Programming 2002, Oxford University, volume 2638 of Lecture Notes in Computer Science, pages 159--187. Springer-Verlag, 2003.
• 15: John Hughes, Generalising monads to arrows, Science of Computer Programming, v.37 n.1-3, p.67-111, May 2000 [doi>10.1016/S0167-6423(99)00023-4]
• 16: John Hughes. Programming with arrows. In Advanced Functional Programming, volume 3622 of Lecture Notes in Computer Science, pages 73--129. Springer, 2004.
• 17: Graham Hutton. Higher-order functions for parsing. Journal of Functional Programming, 2 (3): 323--343, July 1992.
• 18: Simon Peyton Jones , Simon Marlow, Secrets of the Glasgow Haskell Compiler inliner, Journal of Functional Programming, v.12 n.5, p.393-434, July 2002 [doi>10.1017/S0956796802004331]
• 19: Simon Peyton Jones , Dimitrios Vytiniotis , Stephanie Weirich , Geoffrey Washburn, Simple unification-based type inference for GADTs, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 20: Simon Peyton Jones , Jean-Marc Eber , Julian Seward, Composing contracts: an adventure in financial engineering (functional pearl), ACM SIGPLAN Notices, v.35 n.9, p.280-292, Sept. 2000
• 21: Nupur Kothari , Ramakrishna Gummadi , Todd Millstein , Ramesh Govindan, Reliable and efficient programming abstractions for wireless sensor networks, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 22: Philip Levis , David Gay , David Culler, Active sensor networks, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.343-356, May 02-04, 2005
• 23: Liqian Lu, Tian He, Tarek Abdelzaher, and John Stankovic. Design and comparison of lightweight group management strategies in EnviroSuite. In Proc. International Conference on Distributed Computing in Sensor Networks (DCOSS), Marina Del Rey, CA, June 2005.
• 24: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 25: Geoffrey Mainland, Why it's nice to be quoted: quasiquoting for haskell, Proceedings of the ACM SIGPLAN workshop on Haskell workshop, September 30-30, 2007, Freiburg, Germany [doi>10.1145/1291201.1291211]
• 26: Ryan Newton , Greg Morrisett , Matt Welsh, The regiment macroprogramming system, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236422]
• 27: Ryan Newton, Lewis Girod, Michael Craig, Sam Madden, and Greg Morrisett. Wavescript: A case-study in applying a distributed stream-processing language. Technical Report MIT-CSAIL-TR-2008-005, MIT CSAIL, 2008.
• 28: Henrik Nilsson , Antony Courtney , John Peterson, Functional reactive programming, continued, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.51-64, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581695]
• 29: Izzet Pembeci , Henrik Nilsson , Gregory Hager, Functional reactive robotics: an exercise in principled integration of domain-specific languages, Proceedings of the 4th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.168-179, October 06-08, 2002, Pittsburgh, PA, USA [doi>10.1145/571157.571174]
• 30: John Peterson , Paul Hudak , Conal Elliott, Lambda in Motion: Controlling Robots with Haskell, Proceedings of the First International Workshop on Practical Aspects of Declarative Languages, p.91-105, January 18-19, 1999
• 31: Tim Sheard , Simon Peyton Jones, Template meta-programming for Haskell, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.1-16, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581691]
• 32: Jacob Sorber , Alexander Kostadinov , Matthew Garber , Matthew Brennan , Mark D. Corner , Emery D. Berger, Eon: a language and runtime system for perpetual systems, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322279]
• 33: Martin Sulzmann , Manuel M. T. Chakravarty , Simon Peyton Jones , Kevin Donnelly, System F with type equality coercions, Proceedings of the 2007 ACM SIGPLAN international workshop on Types in languages design and implementation, January 16-16, 2007, Nice, Nice, France [doi>10.1145/1190315.1190324]
• 34: Taha Walid, Multi-Stage Programming: Its Theory and Applications, Oregon Graduate Institute School of Science & Engineering, 1999
• 35: Walid Taha , Tim Sheard, MetaML and multi-stage programming with explicit annotations, Theoretical Computer Science, v.248 n.1-2, p.211-242, October 2000 [doi>10.1016/S0304-3975(00)00053-0]
• 36: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 37: 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
• 38: Zhanyong Wan , Paul Hudak, Functional reactive programming for real-time reactive systems, Yale University, New Haven, CT, 2002
• 39: 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
• 40: Stephen Weeks, Matthew Fluet, Henry Cejtin, and Suresh Jagannathan. http://www.mlton.org/.
• 41: Geoff Werner-Allen, Jeff Johnson, Mario Ruiz, Jonathan Lees, and Matt Welsh. Monitoring volcanic eruptions with a wireless sensor network. In Proc. Second European Workshop on Wireless Sensor Networks (EWSN '05), January 2005a.
• 42: Geoffrey Werner-Allen , Patrick Swieskowski , Matt Welsh, MoteLab: a wireless sensor network testbed, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 44: Geoff Werner-Allen , Konrad Lorincz , Jeff Johnson , Jonathan Lees , Matt Welsh, Fidelity and yield in a volcano monitoring sensor network, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.27-27, November 06-08, 2006, Seattle, WA
• 45: Kamin Whitehouse, Feng Zhao, and Jie Liu. Semantic Streams: a framework for declarative queries and automatic data interpretation. Technical Report MSR-TR-2005-45, Microsoft Research, One Microsoft Way, Redmond, WA 98052, April 2005.
• 46: Kamin Whitehouse, Jie Liu, and Feng Zhao. Semantic Streams: a framework for composable inference over sensor data. In Proc. Third European Workshop on Wireless Sensor Networks (EWSN), Zurich, Switzerland, February 2006.
• 47: Hongwei Xi , Chiyan Chen , Gang Chen, Guarded recursive datatype constructors, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.224-235, January 15-17, 2003, New Orleans, Louisiana, USA
• 48: Ning Xu , Sumit Rangwala , Krishna Kant Chintalapudi , Deepak Ganesan , Alan Broad , Ramesh Govindan , Deborah Estrin, A wireless sensor network For structural monitoring, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031498]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Design, Languages

Keywords:
meta programming