2.21.10 References

All cited web pages visited during September 2007.

Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, Massachusetts. Second edition, 1996. The classic text on computer science. Section 3.5 includes extensive discussion of odd streams.

Anne L. Bewig. Golden Ratio (personal communication). Homework for the high school course Calculus. Teaching my daughter how to calculate the 200th element of a continued fraction was a moment of sheer joy in the development of the stream libraries.

Philip L. Bewig. Scheme Request for Implementation 40: A Library of Streams. August, 2004. Describes an implementation of the stream data type.

Richard Bird and Philip Wadler. Introduction to Functional Programming. Prentice Hall, 1988. The classic text on functional programming. Even streams are discussed in the context of purely functional programming.

William H. Burge. Recursive Programming Techniques. Addison–Wesley, 1975. An early text on functional programming, and still one of the best, though the terminology is dated. Discusses even streams in Section 3.10.

Jeremy Gibbons, David Lester and Richard Bird, Functional Pearl: Enumerating the Rationals, under consideration for publication in Journal of Functional Programming. Discusses a series of expressions that enumerate the rational numbers without duplicates.

Carl Hewitt. Viewing control structures as patterns of passing messages, in Journal of Artificial Intelligence, Volume 8, Number 3 (June, 1977), pp 323-364. Also published as Artificial Intelligence Memo 410 by the Massachusetts Institute of Technology. Describes the Actor message-passing system; one of the examples used is the same-fringe? problem.

Peter J. Landin. A correspondence between ALGOL 60 and Church’s lambda-notation: Part I, Communications of the ACM, Volume 8, Number 2, February 1965, pages 89-101. The seminal description of streams.

Joe Marshall. "Stream problem redux", from Usenet comp.lang.scheme, June 28, 2002. The original post on comp.lang.scheme that describes the times3 problem.

Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 2003. Revised version of Okasaki’s thesis Purely Functional Data Structures, Carnegie–Mellon University, 1996. Provides a strong defense of laziness, and describes several data structures that exploit laziness, including streams and queues.

Stephen K. Park and Keith W. Miller. Random number generators: good ones are hard to find, Communications of the ACM, Volume 31, Issue 10 (October 1988), pages 1192–1201. Describes a minimal standard random number generator.

Simon Peyton–Jones, et al, editors. Haskell 98: Haskell 98 Language and Libraries: The Revised Report. December 2002. Haskell is the prototypical purely functional language, and includes even streams, which it calls lists, as its fundamental structured data type.

Chris Reade. Elements of Functional Programming. Addison–Wesley, April 1989. A textbook on functional programming.

Antoine de Saint–Exupery. Chapter III "L’Avion" of Terre des Hommes. 1939. “Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.”

Dorai Sitaram. Teach Yourself Scheme in Fixnum Days. A useful introduction to Scheme; includes generator and co–routine solutions to the same-fringe? problem.

Michael Sperber, R. Kent Dybvig, Matthew Flatt, and Anton von Straaten, editors. Revised6 Report on the Algorithmic Language Scheme. September 26, 2007. www.r6rs.org. The standard definition of the Scheme programming language.

Andre van Tonder. Scheme Request for Implementation 45: Primitives for Expressing Iterative Lazy Algorithms. April, 2004. Describes the problems inherent in the promise data type of R5RS (also present in R6RS), and provides the alternate promise data type used in the stream primitives.

Philip Wadler. How to replace failure by a list of successes, in Proceedings of the conference on functional programming languages and computer architecture, Nancy, France, 1985, pages 113–128. Describes the “list of successes” technique for implementing backtracking algorithms using streams.

Philip Wadler, Walid Taha, and David MacQueen. How to add laziness to a strict language without even being odd. 1998 ACM SIGPLAN Workshop on ML, pp. 24ff. Describes odd and even styles of lazy evaluation, and shows how to add lazy evaluation to the strict functional language SML.