[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Fun with guile, Erastones + goldbach conjecture

From: Ian Price
Subject: Re: Fun with guile, Erastones + goldbach conjecture
Date: Wed, 10 Apr 2013 01:18:36 +0100
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)

Panicz Maciej Godek <address@hidden> 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,

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).

Ian Price --

"Programming is like pinball. The reward for doing it well is
the opportunity to do it again" - from "The Wizardy Compiled"

reply via email to

[Prev in Thread] Current Thread [Next in Thread]