skip to main content
10.1145/1159842.1159851acmconferencesArticle/Chapter ViewAbstractPublication PagesicfpConference Proceedingsconference-collections
Article

Strongly typed memory areas programming systems-level data structures in a functional language

Published: 17 September 2006 Publication History

Abstract

Modern functional languages offer several attractive features to support development of reliable and secure software. However, in our efforts to use Haskell for systems programming tasks-including device driver and operating system construction-we have also encountered some significant gaps in functionality. As a result, we have been forced, either to code some non-trivial components in more traditional but unsafe languages like C or assembler, or else to adopt aspects of the foreign function interface that compromise on strong typing and type safety.In this paper, we describe how we have filled one of these gaps by extending a Haskell-like language with facilities for working directly with low-level, memory-based data structures. Using this extension, we are able to program a wide range of examples, including hardware interfaces, kernel data structures, and operating system APIs. Our design allows us to address concerns about representation, alignment, and placement (in virtual or physical address spaces) that are critical in some systems applications, but clearly beyond the scope of most existing functional languages.Our approach leverages type system features that are wellknown and widely supported in existing Haskell implementations, including kinds, multiple parameter type classes, functional dependencies, and improvement. One interesting feature is the use of a syntactic abbreviation that makes it easy to define and work with functions at the type level.

References

[1]
Godmar Back. Datascript - a specification and scripting language for binary data. In Proceedings of the ACM Conference on Generative Programming and Component Engineering Proceedings (GPCE 2002), pages 66--77, October 2002.]]
[2]
Matthias Blume. No-Longer-Foreign: Teaching an ML compiler to speak C "natively". In BABEL 2001: 1st Workshop on Multi-Language Infrastructure and Interoperability, September 2001.]]
[3]
Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. Associated type synonyms. In ICFP 2005: ACM SIGPLAN International Conference on Functional Programming, pages 241--253, 2005.]]
[4]
Iavor S. Diatchki, Mark P. Jones, and Rebekah Leslie. High-level views on low-level representations. In ICFP 2005: ACM SIGPLAN International Conference on Functional Programming, pages 168--179, 2005.]]
[5]
Sigbjorn Finne, Daan Leijen, Erik Meijer, and Simon Peyton Jones. H/Direct: A binary foreign language interface for Haskell. In ICFP 1998: ACM SIGPLAN International Conference on Functional Programming, 1998.]]
[6]
Kathleen Fisher and Robert Gruber. PADS: a domain-specific language for processing ad hoc data. In PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, pages 295--304, 2005.]]
[7]
Kathleen Fisher, Ricardo Pucella, and John Reppy. A framework for interoperability. In BABEL 2001: 1st Workshop on Multi-Language Infrastructure and Interoperability, September 2001.]]
[8]
Daniel Joeseph Grossman. Safe Programming at the C Level of Abstraction. PhD thesis, Cornell University, 2003.]]
[9]
Thomas Hallgren, Mark P. Jones, Rebekah Leslie, and Andrew Tolmach. A principled approach to operating system construction in Haskell. In ICFP 2005: ACM SIGPLAN International Conference on Functional Programming, pages 116--128, 2005.]]
[10]
Robert Harper, Peter Lee, and Frank Pfenning. The fox project: Advanced language technology for extensible systems. Technical Report CMU-CS-98-107, School of Computer Science, Carnegie Mellon University, January 1998.]]
[11]
Intel Corporation. IA-32 Intel Architecture Software Developer's Manual, Volumes 1-3. Available online from http://www.intel.com/design/Pentium4/documentation.htm.]]
[12]
Trevor Jim, Greg Morrisett, Dan Grossman, Michael Hicks, James Cheney, and Yanling Wang. Cyclone: A safe dialect of C. In USENIX Annual Technical Conference, pages 275--288, June 2002.]]
[13]
Mark P. Jones. Simplifying and improving qualified types. Technical Report YALEU/DCS/RR-1040, Yale University, New Haven, Connecticut, USA, June 1994.]]
[14]
Mark P. Jones. Type classes with functional dependencies. In ESOP 2000: European Symposium on Programming, March 2000.]]
[15]
Mark P. Jones, Magnus Carlsson, and Johan Nordlander. Composed, and in Control: Programming the Timber Robot. Technical report, OGI School of Science & Engineering at OHSU, August 2002.]]
[16]
Simon Peyton Jones, editor. Haskell 98 Language and Libraries, The Revised Report. Cambridge University Press, 2003.]]
[17]
Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language. Prentice Hall, 1988.]]
[18]
Xavier Leroy. CamlIDL User's Manual (Version 1.05). INRIA Rocquencourt.]]
[19]
Xiaoming Liu, Christoph Kreitz, Robbert van Renesse, Jason Hickey, Mark Hayden, Ken Birman, and Robert Constable. Building reliable, high-performance communication systems from components. In Proceedings of the 17th ACM Symposium on Operating System Principles (SOSP '99), Kiawah Island Resort, SC, December 1999.]]
[20]
Matthias Neubauer, Peter Thiemann, Martin Gasbichler, and Michael Sperber. A functional notation for functional dependencies. In Proceedings of The 2001 ACM SIGPLAN Haskell Workshop, Firenze, Italy, September 2001.]]
[21]
Norman Ramsey and Mary F. Fernandez. Specifying representations of machine instructions. ACM Transactions on Programming Languages and Systems, 19(3):492--524, 1997.]]
[22]
Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, 1997.]]
[23]
Cyclone Team. Cyclone User's Manual (0.8.2), August 2004.]]
[24]
Haskell FFI Team. Haskell 98 Foreign Function Interface (1.0), 2003.]]
[25]
L4ka Team. L4 eXperimental Kernel Reference Manual, January 2005. Available online from http://l4ka.org/.]]
[26]
Andrew Tolmach and Dino P. Oliva. From ML to Ada: Stronglytyped language interoperability via source translation. Journal of Functional Programming, 8(4):367--412, July 1998.]]

Cited By

View all
  • (2023)Haskell Library for Safer Virtual Machine Introspection (Experience Report)Proceedings of the 16th ACM SIGPLAN International Haskell Symposium10.1145/3609026.3609732(89-96)Online publication date: 30-Aug-2023
  • (2023)Dargent: A Silver Bullet for Verified Data Layout RefinementProceedings of the ACM on Programming Languages10.1145/35712407:POPL(1369-1395)Online publication date: 11-Jan-2023
  • (2017)A compiler and verifier for page access oblivious computationProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106248(649-660)Online publication date: 21-Aug-2017
  • Show More Cited By

Index Terms

  1. Strongly typed memory areas programming systems-level data structures in a functional language

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      Haskell '06: Proceedings of the 2006 ACM SIGPLAN workshop on Haskell
      September 2006
      131 pages
      ISBN:1595934898
      DOI:10.1145/1159842
      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: 17 September 2006

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. data representation
      2. improvement
      3. memory areas
      4. memory manipulation
      5. qualified types
      6. systems programming

      Qualifiers

      • Article

      Conference

      ICFP06
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 57 of 143 submissions, 40%

      Upcoming Conference

      ICFP '25
      ACM SIGPLAN International Conference on Functional Programming
      October 12 - 18, 2025
      Singapore , Singapore

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)30
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 19 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2023)Haskell Library for Safer Virtual Machine Introspection (Experience Report)Proceedings of the 16th ACM SIGPLAN International Haskell Symposium10.1145/3609026.3609732(89-96)Online publication date: 30-Aug-2023
      • (2023)Dargent: A Silver Bullet for Verified Data Layout RefinementProceedings of the ACM on Programming Languages10.1145/35712407:POPL(1369-1395)Online publication date: 11-Jan-2023
      • (2017)A compiler and verifier for page access oblivious computationProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106248(649-660)Online publication date: 21-Aug-2017
      • (2015)Guilt free ivoryACM SIGPLAN Notices10.1145/2887747.280431850:12(189-200)Online publication date: 30-Aug-2015
      • (2015)Guilt free ivoryProceedings of the 2015 ACM SIGPLAN Symposium on Haskell10.1145/2804302.2804318(189-200)Online publication date: 30-Aug-2015
      • (2014)Building embedded systems with embedded DSLsACM SIGPLAN Notices10.1145/2692915.262814649:9(3-9)Online publication date: 19-Aug-2014
      • (2014)Building embedded systems with embedded DSLsProceedings of the 19th ACM SIGPLAN international conference on Functional programming10.1145/2628136.2628146(3-9)Online publication date: 19-Aug-2014
      • (2014)Programming languages for high-assurance autonomous vehiclesProceedings of the ACM SIGPLAN 2014 Workshop on Programming Languages meets Program Verification10.1145/2541568.2541570(1-2)Online publication date: 11-Jan-2014
      • (2010)Instance chainsACM SIGPLAN Notices10.1145/1932681.186359645:9(375-386)Online publication date: 27-Sep-2010
      • (2010)Instance chainsProceedings of the 15th ACM SIGPLAN international conference on Functional programming10.1145/1863543.1863596(375-386)Online publication date: 27-Sep-2010
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media