The bits between the lambdas: binary data in a lazy functional language

ABSTRACT

For the programmer, storage media are usually assumed to have a minimum atomic unit of transfer of one byte. However, sometimes it is useful to have an even finer storage granularity of one bit, for instance in order to compress data.This paper describes an API in the lazy functional language Haskell for treating storage media as arbitrary-length streams of bits without byte-alignment constraints. So far as possible, storage media are treated uniformly. In particular, bit-stream memory and binary files share the same API -- a new and useful abstraction over memory management and file management. This uniformity of access leads to a novel technique for lazy random-access to files in a purely functional manner. We also describe a technique for automatically deriving compressed binary representations of user-defined data structures, whose operations provide both in-heap data compression and convenient high-level binary I/O.Of many possible applications, we illustrate the processing of Huffman-encoded image data, and a bibliographic information system which uses lazy B-trees for efficient storage management.

REFERENCES

• 1: Richard Bird , Philip Wadler, An introduction to functional programming, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
• 2: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 3: N. RSjemo et al. nhcl3 Haskell compiler, York release, http://www, cs. york. ac. uk/fp/nhc13//, Dept. of Computer Science, University of York, UK, May 1998.
• 4: Jeroen Fokker. Functional specification of JPEG decompression and an implementation for free. In Veltkamp and Blake, editors, Programming Paradigms in Graphics, Proceedings of Eurographics Workshop, pages 102-120, Maastricht, NL, September 1995. Springer.
• 5: D. A. Hurl:man. A method for the construction of minimum-redundancy codes. Proc. IRE, 40:1098-1101, 1952.
• 6: Patrik Jansson , Johan Jeuring, PolyP—a polytypic programming language extension, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.470-482, January 15-17, 1997, Paris, France [doi>10.1145/263699.263763]
• 7: J. Jeuring. Polytypic data compression. Unpublished, 1997.
• 8: M. P. Jones. The implementation of the Gofer functional programming system. Technical Report YALEU/DCS/RR-1030, Department of Computer Science, Yale University, May 1994.
• 9: Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987 [doi>10.1145/45072.45074]
• 10: Simon L. Peyton Jones , John Launchbury, Unboxed values as first class citizens in a non-strict functional language, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.636-666, June 1991, Cambridge, Massachusetts, United States
• 11: Simon Peyton Jones, Thomas Nordm, and Alastair Reid. GreenCard: a foreign-language interface for Haskell. In J. Launchbury, editor, 2nd Haskell Workshop, Amsterdam, NL, June 1997.
• 12: Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
• 13: Marco Pil, First Class File I/O, Selected Papers from the 8th International Workshop on Implementation of Functional Languages, p.233-246, September 16-18, 1996
• 14: Alastair Reid. Malloc pointers and stable pointers: improving Haskell's foreign language interface. In Glasgow Functional Programming Workshop Draft Proceedings, Ayr, Scotland, September 1994.
• 15: Niklas Röjemo, Highlights from nhc—a space-efficient Haskell compiler, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.282-292, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224217]
• 16: Colin Runciman , Niklas Röjemo, Heap Profiling for Space Efficiency, Advanced Functional Programming, Second International School-Tutorial Text, p.159-183, August 26-30, 1996
• 17: Olin Shivers, Automatic management of operating-system resources, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.274-279, June 09-11, 1997, Amsterdam, The Netherlands
• 18: Jan Sparud , Colin Runciman, Tracing Lazy Functional Computations Using Redex Trails, Proceedings of the9th International Symposium on Programming Languages: Implementations, Logics, and Programs: Including a Special Trach on Declarative Programming Languages in Education, p.291-308, September 03-05, 1997
• 19: Simon Thompson, Haskell: the craft of functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 20: David Wakeling, The dynamic compilation of lazy functional programs, Journal of Functional Programming, v.8 n.1, p.61-81, January 1998 [doi>10.1017/S0956796897002955]
• 21: M. Wallace and C. Runciman. Heap compression and binary I/O in Haskell. In J. Launchbury, editor, 2nd Haskell Workshop, Amsterdam, NL, June 1997.
• 22: D.A. Ziff, S.P. Spackman, and K. Waclena. Funser: a functional server for textual information retrieval. Journal of Functional Programming, 5(3):317-343, July 1995.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Haskell

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Languages, Measurement, Performance, Theory