Re: Fun with guile, Erastones + goldbach conjecture

[Ian Price <ianprice90@googlemail.com>]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=iso-2022-jp-2, Size: 2229 bytes --]

Panicz Maciej Godek <godek.maciek@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"