research-article

Flask: staged functional programming for sensor networks

Authors:

Geoffrey Mainland,

Greg Morrisett,

Matt WelshAuthors Info & Claims

ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programming

Pages 335 - 346

https://doi.org/10.1145/1411204.1411251

Published: 20 September 2008 Publication History

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.

Supplementary Material

JPG File (1411251.jpg)

Download
21.48 KB

index.html (index.html)

Slides from the presentation

Download
.93 KB

ZIP File (p335-slides.zip)

Supplemental material for: Flask: staged functional programming for sensor networks

Download
15.99 MB

Audio only (1411251.mp3)

Download
9.22 MB

Video (1411251.mp4)

Download
127.33 MB

References

[1]

Andreas M. Ali, Kung Yao, Travis C. Collier, Charles E. Taylor, Daniel T. Blumstein, and Lewis Girod. An empirical study of collaborative acoustic source localization. In IPSN '07, pages 41--50, 2007.

Digital Library

[2]

Amol Bakshi, Viktor K. Prasanna, Jim Reich, and Daniel Larner. The abstract task graph: A methodology for architecture-independent programming of networked sensor systems. In Proc. Workshop on End-to-End, Sense-and-Respond Systems, Applications, and Services, pages 19--24, 2005a.

Digital Library

[3]

Amol Bakshi, Viktor K. Prasanna, Jim Reich, and Daniel Larner. The abstract task graph: a methodology for architecture-independent programming of networked sensor systems. In EESR '05: Proceedings of the 2005 workshop on End-to-end, sense-and-respond systems, applications and services, pages 19--24, Berkeley, CA, USA, 2005b. USENIX Association.

Digital Library

[4]

Elaine Cheong, Judith Liebman, Jie Liu, and Feng Zhao. TinyGALS: A programming model for event-driven embedded systems. In SAC, pages 698--704, 2003.

Digital Library

[5]

Koen Claessen and John Hughes. Quickcheck: a lightweight tool for random testing of haskell programs. In ICFP '00: Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, pages 268--279, New York, NY, USA, 2000. ACM.

Digital Library

[6]

Antony Courtney and Conal Elliott. Genuinely functional user interfaces. In 2001 Haskell Workshop, September 2001.

[7]

Conal Elliott and Paul Hudak. Functional reactive animation. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP '97), volume 32(8), pages 263--273. ACM, August 1997.

Digital Library

[8]

David Gay, ilip Levis, J. Robert von Behren, Matt Welsh, Eric A. Brewer, and David E. Culler. The nesC language: A holistic approach to networked embedded systems. In Proc. Programming Language Design and Implementation (PLDI '03), pages 1--11. ACM, 2003.

Digital Library

[9]

Omprakash Gnawali, Ki-Young Jang, Jeongyeup Paek, Marcos Vieira, Ramesh Govindan, Ben Greenstein, August Joki, Deborah Estrin, and Eddie Kohler. The Tenet architecture for tiered sensor networks. In SenSys '06: Proceedings of the 4th international conference on Embedded networked sensor systems, pages 153--166, New York, NY, USA, 2006. ACM Press.

Digital Library

[10]

Michael Gordon, William Thies, Michal Karczmarek, Jasper Lin, Ali S. Meli, Christopher Leger, Andrew A. Lamb, Jeremy Wong, Henry Hoffman, David Z. Maze, and Saman Amarasinghe. A stream compiler for communication-exposed architectures. In ASPLOS '02, 2002.

Digital Library

[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, Omprakash Gnawali, and Ramesh Govindan. Macro-programming wireless sensor networks using Kairos. In Proc. DCOSS'05, 2005.

Digital Library

[13]

Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David E. Culler, and Kristofer S. J. Pister. System architecture directions for networked sensors. In ASPLOS '00, pages 93--104, 2000.

Digital Library

[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. Sci. Comput. Program, 37 (1-3): 67--111, 2000.

Digital Library

[16]

John Hughes. Programming with arrows. In Advanced Functional Programming, volume 3622 of Lecture Notes in Computer Science, pages 73--129. Springer, 2004.

Digital Library

[17]

Graham Hutton. Higher-order functions for parsing. Journal of Functional Programming, 2 (3): 323--343, July 1992.

[18]

Simon L. Peyton Jones and Simon Marlow. Secrets of the glasgow haskell compiler inliner. J. Funct. Program, 12 (4&5): 393--433, 2002.

Digital Library

[19]

Simon L. Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Geoffrey Washburn. Simple unification-based type inference for GADTs. In Proceedings of the 11th ACM SIGPLAN International Conference on Functional Programming, ICFP '06, pages 50--61. ACM, 2006.

Digital Library

[20]

Simon Peyton Jones, Jean-Marc Eber, and Julian Seward. Composing contracts: an adventure in financial engineering (functional pearl). ACM SIGPLAN Notices, 35 (9): 280--292, 2000.

Digital Library

[21]

Nupur Kothari, Ramakrishna Gummadi, Todd Millstein, and Ramesh Govindan. Reliable and efficient programming abstractions for wireless sensor networks. In Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation (PLDI '07), pages 200--210, 2007.

Digital Library

[22]

Philip Levis, David Gay, and David Culler. Active sensor networks. In NSDI '05: Proceedings of the Second USENIX/ACM Symposium on Networked System Design and Implementation, 2005.

Digital Library

[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.

Digital Library

[24]

Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. TinyDB: an acquisitional query processing system for sensor networks. ACM Transactions on Database Systems, 30 (1): 122--173, 2005.

Digital Library

[25]

Geoffrey Mainland. Why it's nice to be quoted: quasiquoting for haskell. In Haskell '07: Proceedings of the ACM SIGPLAN workshop on Haskell workshop, pages 73--82, New York, NY, USA, 2007. ACM.

Digital Library

[26]

Ryan Newton, Greg Morrisett, and Matt Welsh. The regiment macroprogramming system. In Proc. IPSN '07, 2007.

Digital Library

[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, and John Peterson. Functional reactive programming, continued. In Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell'02), pages 51--64, Pittsburgh, Pennsylvania, USA, October 2002. ACM Press.

Digital Library

[29]

Izzet Pembeci, Henrik Nilsson, and Greogory Hager. Functional reactive robotics: An exercise in principled integration of domain-specific languages. In PPDP '02, October 2002.

Digital Library

[30]

John Peterson, Paul Hudak, and Conal Elliott. Lambda in motion: Controlling robots with Haskell. Lecture Notes in Computer Science, 1551: 91--105, 1999.

Digital Library

[31]

Tim Sheard and Simon Peyton Jones. Template metaprogramming for Haskell. In Manuel M. T. Chakravarty, editor, ACM SIGPLAN Haskell Workshop 02, pages 1--16. ACM Press, October 2002.

Digital Library

[32]

Jacob Sorber, Alexander Kostadinov, Matthew Garber, Matthew Brennan, Mark D. Corner, and Emery D. Berger. Eon: a language and runtime system for perpetual systems. In Proc. SenSys '07, pages 161--174, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-763-6.

Digital Library

[33]

Martin Sulzmann, Manuel M. T. Chakravarty, Simon Peyton Jones, and Kevin Donnelly. System F with type equality coercions. In TLDI '07: Proceedings of the 2007 ACM SIGPLAN international workshop on Types in languages design and implementation, pages 53--66, 2007.

Digital Library

[34]

Walid Taha. Multi-stage programming: Its theory and applications. Technical Report CSE-99-TH-002, Oregon Graduate Institute of Science and Technology, 1999.

Digital Library

[35]

Walid Taha and Tim Sheard. MetaML and multi-stage programming with explicit annotations. Theoretical Computer Science, 248 (1--2): 211--242, 2000.

Digital Library

[36]

Ben Titzer, Daniel K. Lee, and Jens Palsberg. Avrora: scalable sensor network simulation with precise timing. In Fourth International Symposium on Information Processing in Sensor Networks (IPSN '05), pages 477--482, 2005.

Digital Library

[37]

Z. Wan, W. Taha, and P. Hudak. Real-time FRP. In International Conference on Functional Programming (ICFP '01), Florence, Italy, September 2001a.

Digital Library

[38]

Zhanyong Wan. Functional Reactive Programming for Real-Time Reactive Systems. .d. dissertation, Computer Science Department, Yale University, October 2002.

Digital Library

[39]

Zhanyong Wan, Walid Taha, and Paul Hudak. Event-driven FRP. Lecture Notes in Computer Science, 2257: 155+, 2001b.

Digital Library

[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]

Geoff Werner-Allen, Pat Swieskowski, and Matt Welsh. Motelab: A wireless sensor network testbed. In Proc. Fourth International Conference on Information Processing in Sensor Networks (IPSN'05), Special Track on Platform Tools and Design Methods for Network Embedded Sensors (SPOTS), April 2005b.

Digital Library

[43]

Geoff Werner-Allen, Konrad Lorincz, Jeff Johnson, Jonathan Lees, and Matt Welsh. Fidelity and yield in a volcano monitoring sensor network. In Proc. 7th USENIX OSDI, Seattle, WA, Nov 2006.

Digital Library

[44]

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.

[45]

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.

Digital Library

[46]

Hongwei Xi, Chiyan Chen, and Gang Chen. Guarded recursive datatype constructors. POPL '03, 2003.

Digital Library

[47]

Ning Xu, Sumit Rangwala, Krishna Kant Chintalapudi, Deepak Ganesan, Alan Broad, Ramesh Govindan, and Deborah Estrin. A wireless sensor network for structural monitoring. In SenSys '04, pages 13--24, 2004.

Digital Library

Cited By

Casadei R(2023)Macroprogramming: Concepts, State of the Art, and Opportunities of Macroscopic Behaviour ModellingACM Computing Surveys10.1145/357935355:13s(1-37)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3579353
Jaigirdar FTan BRudolph CBain C(2023)Security-Aware Provenance for Transparency in IoT Data PropagationIEEE Access10.1109/ACCESS.2023.328092811(55677-55691)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3280928
Oeyen BVan den Vonder SDe Meuter WMandel L(2021)Trampoline variables: a general method for state accumulation in reactive programmingProceedings of the 8th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems10.1145/3486605.3486787(27-40)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3486605.3486787
Show More Cited By

Index Terms

Flask: staged functional programming for sensor networks
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

Flask: staged functional programming for sensor networks
ICFP '08

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 ...
Flask: Building Python Web Services
Mastering Flask Web Development: Build enterprise-grade, scalable Python web applications, 2nd Edition

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programming

September 2008

422 pages

ISBN:9781595939197

DOI:10.1145/1411204

General Chair:
James Hook
Portland State University, USA
,
Program Chair:
Peter Thiemann
Universität Freiburg, Germany

ACM SIGPLAN Notices Volume 43, Issue 9
ICFP '08
September 2008
399 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1411203
Issue’s Table of Contents

Copyright © 2008 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: 20 September 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

meta programming

Qualifiers

Research-article

Conference

ICFP08

Sponsor:

ICFP08: ACM SIGPLAN International Conference on Functional Programming

September 20 - 28, 2008

BC, Victoria, Canada

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
589
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)2

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Casadei R(2023)Macroprogramming: Concepts, State of the Art, and Opportunities of Macroscopic Behaviour ModellingACM Computing Surveys10.1145/357935355:13s(1-37)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3579353
Jaigirdar FTan BRudolph CBain C(2023)Security-Aware Provenance for Transparency in IoT Data PropagationIEEE Access10.1109/ACCESS.2023.328092811(55677-55691)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3280928
Oeyen BVan den Vonder SDe Meuter WMandel L(2021)Trampoline variables: a general method for state accumulation in reactive programmingProceedings of the 8th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems10.1145/3486605.3486787(27-40)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3486605.3486787
Sarkar ASheeran MGabbrielli MAbel ACheney J(2020)Hailstorm: A Statically-Typed, Purely Functional Language for IoT ApplicationsProceedings of the 22nd International Symposium on Principles and Practice of Declarative Programming10.1145/3414080.3414092(1-16)Online publication date: 8-Sep-2020
https://dl.acm.org/doi/10.1145/3414080.3414092
Saputra YHua JWendt NJulien CRoman GTilevich E(2019)WarbleProceedings of the 6th International Conference on Mobile Software Engineering and Systems10.5555/3340730.3340755(128-139)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.5555/3340730.3340755
Mizzi AEllul JPace G(2019)Porthos: Macroprogramming Blockchain Systems2019 10th IFIP International Conference on New Technologies, Mobility and Security (NTMS)10.1109/NTMS.2019.8763784(1-5)Online publication date: Jun-2019
https://doi.org/10.1109/NTMS.2019.8763784
Saputra YHua JWendt NJulien CRoman G(2019)WARBLE: Programming Abstractions for Personalizing Interactions in the Internet of Things2019 IEEE/ACM 6th International Conference on Mobile Software Engineering and Systems (MOBILESoft)10.1109/MOBILESoft.2019.00026(128-139)Online publication date: May-2019
https://doi.org/10.1109/MOBILESoft.2019.00026
Wang SWatanabe T(2019)Functional Reactive EDSL with Asynchronous Execution for Resource-Constrained Embedded SystemsSoftware Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing10.1007/978-3-030-26428-4_12(171-190)Online publication date: 23-Aug-2019
https://doi.org/10.1007/978-3-030-26428-4_12
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
Mizzi AEllul JPace G(2018)D'ArtagnanProceedings of the Real World Domain Specific Languages Workshop 201810.1145/3183895.3183899(1-9)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3183895.3183899
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