From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.lisp.guile.bugs Subject: bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9 Date: Tue, 13 May 2014 12:47:32 +0200 Message-ID: <87y4y6t0or.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1399978159 13477 80.91.229.3 (13 May 2014 10:49:19 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 13 May 2014 10:49:19 +0000 (UTC) To: 17485@debbugs.gnu.org Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue May 13 12:49:12 2014 Return-path: Envelope-to: guile-bugs@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 1WkAGi-0005aG-L0 for guile-bugs@m.gmane.org; Tue, 13 May 2014 12:49:08 +0200 Original-Received: from localhost ([::1]:43295 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkAGi-0007md-65 for guile-bugs@m.gmane.org; Tue, 13 May 2014 06:49:08 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:41586) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkAGe-0007mP-If for bug-guile@gnu.org; Tue, 13 May 2014 06:49:05 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WkAGc-0006JP-JR for bug-guile@gnu.org; Tue, 13 May 2014 06:49:04 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:44250) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkAGc-0006JL-GZ for bug-guile@gnu.org; Tue, 13 May 2014 06:49:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WkAGb-0005wW-Ua for bug-guile@gnu.org; Tue, 13 May 2014 06:49:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Tue, 13 May 2014 10:49:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 17485 X-GNU-PR-Package: guile X-GNU-PR-Keywords: X-Debbugs-Original-To: bug-guile@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.139997808822761 (code B ref -1); Tue, 13 May 2014 10:49:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 13 May 2014 10:48:08 +0000 Original-Received: from localhost ([127.0.0.1]:33368 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WkAFj-0005v2-25 for submit@debbugs.gnu.org; Tue, 13 May 2014 06:48:07 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:39716) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WkAFf-0005uV-T2 for submit@debbugs.gnu.org; Tue, 13 May 2014 06:48:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WkAFZ-00068P-Hy for submit@debbugs.gnu.org; Tue, 13 May 2014 06:47:58 -0400 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:58557) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkAFZ-00068L-G4 for submit@debbugs.gnu.org; Tue, 13 May 2014 06:47:57 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:41432) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkAFY-0007Qm-F8 for bug-guile@gnu.org; Tue, 13 May 2014 06:47:57 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WkAFX-00067q-HP for bug-guile@gnu.org; Tue, 13 May 2014 06:47:56 -0400 Original-Received: from fencepost.gnu.org ([2001:4830:134:3::e]:33888) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkAFX-00067m-ES for bug-guile@gnu.org; Tue, 13 May 2014 06:47:55 -0400 Original-Received: from localhost ([127.0.0.1]:41063 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WkAFX-0005kt-0X for bug-guile@gnu.org; Tue, 13 May 2014 06:47:55 -0400 Original-Received: by lola (Postfix, from userid 1000) id 916BCE11D7; Tue, 13 May 2014 12:47:32 +0200 (CEST) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:7458 Archived-At: The following code results in an error: (use-modules (srfi srfi-1)) (reduce-right + 0 (make-list 10000 1)) Backtrace: In srfi/srfi-1.scm: 379: 19 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 18 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 17 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 16 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 15 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 14 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 13 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 12 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 11 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 10 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 9 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 8 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 7 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 6 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 5 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 4 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 3 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 2 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 1 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] 379: 0 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)] srfi/srfi-1.scm:379:31: In procedure recur: srfi/srfi-1.scm:379:31: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'. This is for Guile version 2.0.9 as distributed by Ubuntu 14.04. Somewhat surprisingly, fold-right does not suffer from the same error. Surprisingly because the definition of reduce-right is (define (reduce-right f ridentity lst) "`reduce-right' is a variant of `fold-right', where the first call to F is on two elements from LST, rather than one element and a given initial value. If LST is empty, RIDENTITY is returned. If LST has just one element then that's the return value." (check-arg procedure? f reduce) (if (null? lst) ridentity (fold-right f (last lst) (drop-right lst 1)))) It turns out that the call of drop-right is responsible here: (define (drop-right lis k) (let recur ((lag lis) (lead (drop lis k))) (if (pair? lead) (cons (car lag) (recur (cdr lag) (cdr lead))) '()))) For all the cleverness involved here, one has to run through the whole list anyway. It makes no real sense to do this in this manner. The motivation may be to have a warm cache when k is small, but the result is self-defeating because of VM stack buildup. (define (drop-right lis k) (drop lis (- (length lis) k))) should be all that is needed. -- David Kastrup