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, 21 Jun 2016 17:31:32 +0200 Message-ID: <87h9cmftij.fsf@fencepost.gnu.org> References: <87y4y6t0or.fsf@fencepost.gnu.org> <87poray55o.fsf@pobox.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1466523199 28849 80.91.229.3 (21 Jun 2016 15:33:19 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 21 Jun 2016 15:33:19 +0000 (UTC) Cc: 17485@debbugs.gnu.org To: Andy Wingo Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue Jun 21 17:33:11 2016 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 1bFNfq-0001US-H6 for guile-bugs@m.gmane.org; Tue, 21 Jun 2016 17:33:10 +0200 Original-Received: from localhost ([::1]:52573 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bFNfp-0006AC-IG for guile-bugs@m.gmane.org; Tue, 21 Jun 2016 11:33:09 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:57132) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bFNfj-00060X-F8 for bug-guile@gnu.org; Tue, 21 Jun 2016 11:33:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bFNfi-0000R0-6o for bug-guile@gnu.org; Tue, 21 Jun 2016 11:33:03 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:37606) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bFNfi-0000Qv-3l for bug-guile@gnu.org; Tue, 21 Jun 2016 11:33:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1bFNfh-0006un-Up for bug-guile@gnu.org; Tue, 21 Jun 2016 11:33:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Tue, 21 Jun 2016 15:33:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17485 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 17485-submit@debbugs.gnu.org id=B17485.146652312226512 (code B ref 17485); Tue, 21 Jun 2016 15:33:01 +0000 Original-Received: (at 17485) by debbugs.gnu.org; 21 Jun 2016 15:32:02 +0000 Original-Received: from localhost ([127.0.0.1]:49943 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bFNej-0006tQ-Tk for submit@debbugs.gnu.org; Tue, 21 Jun 2016 11:32:02 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:37537) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bFNei-0006t2-55 for 17485@debbugs.gnu.org; Tue, 21 Jun 2016 11:32:00 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bFNeb-0000DC-VV for 17485@debbugs.gnu.org; Tue, 21 Jun 2016 11:31:55 -0400 Original-Received: from fencepost.gnu.org ([2001:4830:134:3::e]:46720 helo=lola.localdomain) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bFNeb-0000Cg-Ml; Tue, 21 Jun 2016 11:31:53 -0400 Original-Received: by lola.localdomain (Postfix, from userid 1000) id 888B9DF5F4; Tue, 21 Jun 2016 17:31:32 +0200 (CEST) In-Reply-To: <87poray55o.fsf@pobox.com> (Andy Wingo's message of "Tue, 21 Jun 2016 16:42:43 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.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" Xref: news.gmane.org gmane.lisp.guile.bugs:8108 Archived-At: Andy Wingo writes: > Hi, > > On Tue 13 May 2014 12:47, David Kastrup writes: > >> 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" ())'. > > On the 2.2 series this problem does not occur because there is no stack > limit. Mark if you would like to fix this on 2.0 in a different way, go > ahead. Otherwise we can close. > > I think on 2.0 that this might be an OK workaround: > > (define (reduce-right f ridentity lst) > (reduce f ridentity (reverse lst))) > > Thoughts? Traversing lst in reverse without additional O(n) storage would require working on (reverse! lst), fixing up the list afterwards. Using reverse! also has the advantage that the list? predicate check does not require the turtle/hare traversal. The downside, of course, is that for something like reduce-right, temporary reversal of lst would be an unexpected side effect not working well with multithreading or read-only memory. So if we don't store the inverse list in-space, it needs to be either a copy in heap (reverse) or stack (recursion). Stack allocation is likely cheaper in execution time (though the total memory cost depends on the stack frame size taken per call). The limited stack size on 2.0 does not seem like a good fit, however. Which makes your workaround seem like the best option. I don't like that then both reduce and reverse check for listness. But that's a different topic. -- David Kastrup