previous  next  contents  top

Incremental multi-level input processing and collection enumeration

 


 

Towards the best collection traversal interface

Most programming languages support collections, represented by an in-memory data structure, a file, a database, or a generating function. A programming language system gives us typically one of the two interfaces to systematically access elements of a collection. One traversal API is based on enumerators -- e.g., for-each, map, filter higher-order procedures -- of which the most general is fold. The second approach relies on streams, a.k.a. cursors, lazy lists. Generators such as the ones in Icon, Ruby and Python are a hybrid approach.

It is well-known that given a cursor interface to a collection, we can implement an enumerator. It is less appreciated that given an enumerator interface, we can always derive a cursor -- in an automatic way. We demonstrate that generic procedure for languages with and without first-class continuations.

Now that cursors and enumerators are inter-convertible, an implementor of a collection has a choice: which of the two interfaces to implement natively? We argue that he should offer the enumerator interface as the native one. The paper elaborates that enumerators are superior: in efficiency; in ease of programming; in more predictable resource utilization and avoidance of resource leaks. We present a design of the overall optimal collection traversal interface, which is based on a left-fold-like combinator with premature termination. The design has been implemented and tested in practice.

Version
The current version is 1.5, Nov 6, 2003.
References
LL3-collections-enumerators.txt [23K]
Towards the best collection API: an extended abstract
LL3-collections-talk.pdf [55K]
An extended abstract and a poster presentation at the Lightweight Languages 2003 (LL3) workshop. November 8, 2003, MIT, Cambridge MA.

Enumerating collections: searching for the best iterator

From enumerators to cursors: turning the left fold inside out, in Haskell

enumerators-callcc-code.scm [4K]
The general enumerator-inversion code in Scheme.

Relationship between iterations and continuations

Zipper in Scheme

 

Incremental multi-level input processing with left-fold enumerator: predictable, high-performance, safe, and elegant

We introduce input processing with left-fold enumerator -- Iteratee IO -- as a safe, declarative and practical alternative to Handle and Lazy IO for input processing. The approach is general and applies to processing data from various collections, from in-memory data structures to databases, files, sockets, etc. The input data may come from a file or from an embedded (e.g., chunk-encoded or encrypted) stream; the depth of embedding is arbitrary. The approach is naturally incremental. It permits IO interleaving without any unsafe operations. The approach is algebraic and declarative. The left-fold enumerator as a general concept has been used in other functional languages.

Our running example is HTTP request processing in Haskell, specifically, reading lines (terminated by CR, LF or CRLF) from a file descriptor and then from the chunk-encoded body. The main example illustrates multiplexing across two file descriptors and the full IO interleaving. The same line parser is used to process data from the file descriptor stream and from the embedded chunk-encoded stream, which is incrementally decoded.

We focus on:

We achieve both high performance and encapsulation of input processing layers that can be freely composed. The technique has been validated in a production web-application server written in Haskell and database access library Takusen.

Version
The current version is 1.1, September 2008.
References
DEFUN08-talk.pdf [146K]
DEFUN08-talk-notes.pdf [185K]
Talk presented at DEFUN08, ACM SIGPLAN 2008 Developer Tracks on Functional Programming. September 27, 2008. Victoria, Canada.
The talk is aimed at practitioners not afraid of Haskell, in particular, server programmers. That is, programmers who program long-running distributed applications and are painfully aware of the issues of reading from sockets, latency, buffering, many layers of decoding, proper resource disposal and sustaining high load.

README.dr [3K]
Description of the Iteratee IO library and the code accompanying the talk.

Lazy-vs-correct.txt [5K]
Lazy vs correct IO: A message on composability and performance of Iteratee IO, posted on the Haskell-Cafe mailing list on Thu, 18 Sep 2008 23:51:59 -0700 (PDT).
We show that although the Iteratee IO library is not optimized at all, it already outperforms Lazy IO. The final benchmark, counting words in all GHC documentation, demonstrates the differences between Lazy and Iteratee IO: Iteratee IO finishes the test whereas Lazy IO runs out of file descriptors.

 

Justifying layered streams for input processing

Handling many internet protocols and file formats -- describing structured, multiply encoded data -- emphasizes layered stream processing. For example, the lowest-level stream reads data in blocks or ethernet frames. An overlay stream provides abstractions of characters or bytes. Higher streams take care of Base64, UTF and other decoding, assembling data into words, data structures, or Unicode characters. It is often useful to layer a stream that reads at most N units (octets, bits, etc) from a lower-level stream. A layered stream may transparently accumulate the SHA-1 digest of the read data and check the signature afterwards. It is important to be able to push and peel off the layers at run time. The latter is indispensable when dealing with HTTP streams carrying multi-part messages.
Version
The current version is 1.1, 2002.
References
layered-io.txt [6K]
Advocating layered IO on the example of HTTP multi-part processing. A message Layered I/O posted on the Haskell-Cafe mailing list on Tue, 14 Sep 2004 23:55:25 -0700 (PDT).

io.txt [26K]
An early draft of an ambitious layered IO proposal, cast in the context of Scheme. More polished drafts exist, and even a prototype Scheme implementation. Unfortunately, once it became clear that the ideas are working out, the motivation fizzled.

 

Streams in Linear Algebra

The linear matrix library LinAlg is built upon matrix streams, which provide sequential view/access to a matrix or its parts. Many of Linear Algebra algorithms turn out to require only sequential access to a matrix or its rows/columns, which is simpler and faster than random access. All streams in LinAlg are light-weight: they use no heap storage and leave no garbage.

A stream-wise access to a collection is an important access method, which may even be supported by hardware. For example, Pentium III floating-point extension (Internet Streaming SIMD Extension) lets programmers designate arrays as streams and provides instructions to handle such data efficiently (Internet Streaming SIMD Extensions, Shreekant (Ticky) Thakkar and Tom Huff, Computer, Vol. 32, No. 12, December 1999, pp. 26-34). Streaming is a typical memory access model of DSPs: that's why DSP almost never incorporate a data cache (See "DSP Processors Hit the Mainstream," Jennifer Eyre and Jeff Bier, Computer, Vol. 31, No. 8, August 1998, pp. 51-59). A memory architecture designed in an article "Smarter Memory: Improving Bandwidth for Streamed References" (IEEE Computer, July 1998, pp.54-63) achieves low overall latencies because the CPU is told by a compiler that a stream operation is to follow. LinAlg offers this streaming access model to an application programmer.

Matrix streams may stride a matrix by an arbitrary amount. This lets us traverse a matrix along the diagonal, by columns, by rows, etc. Streams can be constructed of a Matrix itself, or from other matrix views (MatrixColumn, MatrixRow, MatrixDiag). In the latter case, the streams are confined only to specific portions of the matrix.

Many functions of LinAlg are written in terms of streams, for example, the computation of vector norms, the addition of a vector to the diagonal or the anti-diagonal of a matrix, Aitken-Lagrange interpolation. Singular value decomposition SVD demonstrates many applications of streams: e.g., multiplying a matrix by a rotation matrix avoids random access to matrix elements and the corresponding range checks and offset calculations. The stream code is also more lucid. One may create a stream that spans over a part of another stream. We use substreams, for example, to efficiently reflect the upper triangle of a square matrix onto the lower one, yielding a symmetric matrix. The SVD computation uses subranging extensively, e.g., for left Householder transformations.

LinAlg's streams may span an arbitrary rectangular block of a matrix, including the whole matrix, a single matrix element, a matrix row or a column, or a part thereof. Assigning a block of one matrix to a block of another takes only one line -- which, due to inlining, is just as efficient as the direct loop with pointer manipulation.

References
LinAlg: Basic Linear Algebra and Optimization classlib


Last updated October 5, 2008

This site's top page is http://okmij.org/ftp/

oleg-at-pobox.com or oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!

Converted from HSXML by HSXML->HTML