Panicz Maciej Godek <godek.mac...@gmail.com> writes: > Section 3.5 (Streams), which introduces the notion > of streams, or lazy lists (that can be infinite), with the > most amazing example of Erastostenes' sieve,A (B > implementation, as well as sections,A (B4.1,A (Band,A (B4.3,A (Bof
My pedant sense is tingling :P Two concerns here. First, lazy lists as presented in SICP are subject to off-by-1 coding problems. You see it throughout the streams chapter, and in the non-deterministic evaluator chapter by occasional smatterings of 'force' and 'delay' about the place. In the next release of Guile, we will have an implementation of SRFI 41[0], which does not have these problems. Secondly, that is not actually the sieve of Eratosthenes, but Trial Division. Melissa E. O'Neill has a lovely paper about this[1], giving performances analyses of both. And before you object to me calling SICP's sieve $B!H(Bfake$B!I(B... $B!H(BSome readers may feel that despite all of these concerns, the earlier algorithm is somehow $B!H(Bmorally$B!I(B the Sieve of Eratosthenes. I would argue, however, that they are confusing a mathematical abstraction drawn from the Sieve of Eratosthenes with the actual algorithm. The algorithmic details, such as how you remove all the multiples of 17, matter.$B!I(B I have an implementation of the genuine sieve available[2], that you will be able to run when the next release comes out. (Needs pfds). Okay, pedant sense sufficiently exercised for now. SICP is a fine book IMO, but it isn't perfect. Section 3 is not fantastic, for a variety of reasons, and I feel people are better served learning recursion on recursive data structures (like lists or trees), rather than the way SICP does with numbers (yes, the naturals are recursive, but many of the algorithms, like fast-exponentiation, rely on recursion other than on the predecessor). 0. http://srfi.schemers.org/srfi-41/srfi-41.html 1. http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf 2. https://github.com/ijp/ijputils/blob/master/streams.sls#L73 -- Ian Price -- shift-reset.com "Programming is like pinball. The reward for doing it well is the opportunity to do it again" - from "The Wizardy Compiled"
