From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Ian Price Newsgroups: gmane.lisp.guile.devel,gmane.lisp.guile.user Subject: Re: Fun with guile, Erastones + goldbach conjecture Date: Wed, 10 Apr 2013 01:18:36 +0100 Message-ID: <87sj2z1bmr.fsf@Kagami.home> References: <1551498.g80VkUsTQo@warperdoze> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-2022-jp-2 X-Trace: ger.gmane.org 1365553128 19876 80.91.229.3 (10 Apr 2013 00:18:48 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 10 Apr 2013 00:18:48 +0000 (UTC) Cc: "guile-user@gnu.org" , guile-devel To: Panicz Maciej Godek Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Apr 10 02:18:51 2013 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UPikT-0002Mm-S4 for guile-devel@m.gmane.org; Wed, 10 Apr 2013 02:18:50 +0200 Original-Received: from localhost ([::1]:41009 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UPikT-0007Sf-6A for guile-devel@m.gmane.org; Tue, 09 Apr 2013 20:18:49 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:33997) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UPikN-0007SP-LY for guile-devel@gnu.org; Tue, 09 Apr 2013 20:18:44 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UPikM-0003ey-Bx for guile-devel@gnu.org; Tue, 09 Apr 2013 20:18:43 -0400 Original-Received: from mail-wg0-f50.google.com ([74.125.82.50]:45038) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UPikM-0003eo-4R; Tue, 09 Apr 2013 20:18:42 -0400 Original-Received: by mail-wg0-f50.google.com with SMTP id k13so7689927wgh.5 for ; Tue, 09 Apr 2013 17:18:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20120113; h=x-received:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version:content-type; bh=6Ki9PrVdT0ldWiK2SDkQvXs39H2rKRUKUWpRrIUoJoY=; b=PT2AWjWg4OIPM1J6kXMfkUI0aSeYwsNwupA4FX3UQ3sr/XkSgwq0V9BwgxLTjQyggw dHELon2nFqveDcC2xE2crjGZJuxJzySmqx3xZMmj4BK8Ow8zGdPXMr3pLAoDHNKsKkoP Er8vF3G3uhYx8wfKidCVw7HoI8x9y+sLfHP299pnwU0zi5bxfJbH7QVp6NebJ3ZfbTTc oP/2/8A8s8y3tALF8Eg5AVXLfJ0jyjMbCQVGI5YfjAUvRwTi+wjc07ghy4zyqDLy56Gf e8A+z5nt7BwaQ0tRKOFXUL5op64+QxOa9kbAPqorrKFNcriwmxDu+pinxpwrDU8EjJXm aWHw== X-Received: by 10.181.11.164 with SMTP id ej4mr23088578wid.29.1365553121365; Tue, 09 Apr 2013 17:18:41 -0700 (PDT) Original-Received: from Kagami.home (host86-184-183-126.range86-184.btcentralplus.com. [86.184.183.126]) by mx.google.com with ESMTPS id dm9sm28850397wib.3.2013.04.09.17.18.39 (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Tue, 09 Apr 2013 17:18:40 -0700 (PDT) In-Reply-To: (Panicz Maciej Godek's message of "Tue, 9 Apr 2013 21:35:04 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 74.125.82.50 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16211 gmane.lisp.guile.user:10256 Archived-At: Panicz Maciej Godek 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"