From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: for-each et al Date: Sun, 02 Mar 2014 16:55:26 +0100 Message-ID: <87txbgr3wx.fsf@pobox.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1393775735 15488 80.91.229.3 (2 Mar 2014 15:55:35 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 2 Mar 2014 15:55:35 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Mar 02 16:55:44 2014 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 1WK8jv-0002tJ-Mg for guile-devel@m.gmane.org; Sun, 02 Mar 2014 16:55:43 +0100 Original-Received: from localhost ([::1]:35849 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WK8jv-0002j1-Ag for guile-devel@m.gmane.org; Sun, 02 Mar 2014 10:55:43 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:44566) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WK8jp-0002il-0w for guile-devel@gnu.org; Sun, 02 Mar 2014 10:55:41 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WK8jk-0002mv-8i for guile-devel@gnu.org; Sun, 02 Mar 2014 10:55:36 -0500 Original-Received: from a-pb-sasl-quonix.pobox.com ([208.72.237.25]:60142 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WK8jj-0002mk-VU for guile-devel@gnu.org; Sun, 02 Mar 2014 10:55:32 -0500 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 547BBF5F5 for ; Sun, 2 Mar 2014 10:55:31 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to :subject:date:message-id:mime-version:content-type; s=sasl; bh=L l9MGDiIHI8AdGJlNhd+iCtXB9s=; b=JL33Dap212z00a5SX9Ys45cCDwqKYTby7 9OvuO5X1/cEEm8oeoyRCXN+tas4irOwJtIuJccQZIwdkADjBQ5onzzg/gHlcVFda yorrlTXWZiePfjWkAEM4A8q1fWBJWHkMybXXAfJkzfdflhJ+m/IyBKEzhkzymrj9 cYPchJiCgo= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:subject :date:message-id:mime-version:content-type; q=dns; s=sasl; b=q5J 4uK3woSYhwdqeXFGShrCfkLMocRjUJrlaHSuEqJK/gBqT7iL4AT+eCEhJ6HLWy4s 1jSTbXWPTlmYkrgDdCk0eRhW24dSAYyUIWpxvHlC9nD+tntADjo+ynGrZahgYCwf hVWgkDXUDo5lBHwyz37vB1wW6v3FoqRFeajU6ckE= Original-Received: from a-pb-sasl-quonix.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 4B213F5F4 for ; Sun, 2 Mar 2014 10:55:31 -0500 (EST) Original-Received: from badger (unknown [88.160.190.192]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTPSA id 8B61FF5F3 for ; Sun, 2 Mar 2014 10:55:29 -0500 (EST) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) X-Pobox-Relay-ID: 1427E958-A223-11E3-AA70-873F0E5B5709-02397024!a-pb-sasl-quonix.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 X-Received-From: 208.72.237.25 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:16941 Archived-At: Hi, I was looking at some profiles of the compiler in master, and surprisingly for-each was fairly high in the list. Probably for-each should be inlined; but be that as it may, I thought I should take a look inside for-each and see what the deal was. The current boot-9 for-each for one list argument is this nastiness: (define for-each (case-lambda ((f l) (let for-each1 ((hare l) (tortoise l)) (if (pair? hare) (begin (f (car hare)) (let ((hare (cdr hare))) (if (pair? hare) (begin (when (eq? tortoise hare) (scm-error 'wrong-type-arg "for-each" "Circular list: ~S" (list l) #f)) (f (car hare)) (for-each1 (cdr hare) (cdr tortoise))) (for-each1 hare tortoise)))) (if (not (null? hare)) (scm-error 'wrong-type-arg "for-each" "Not a list: ~S" (list l) #f))))) ...)) Terrible. And it's slower than this: (lambda (f l) (unless (list? l) (scm-error 'wrong-type-arg "for-each" "Not a list: ~S" (list l) #f)) (let for-each1 ((l l)) (unless (null? l) (f (car l)) (for-each1 (cdr l))))) So, pop quiz: what's the difference between the two? Yes, the first version would raise a "circular list" error instead of "not a list" on a circular list -- not that anyone cares, I think. Also, the boot-9 version calls the procedure on earlier elements of non-lists, something that perhaps it should avoid. But the real difference is in the handling of concurrent manipulation of the list being traversed. The boot-9 version is mostly tolerant of concurrent manipulation (either by f or by another thread), as it detects non-lists lazily. In contrast if a list is concurrently made circular, the check-then-iterate version will loop infinitely. (Incidentally the generic multi-list variant of for-each is vulnerable to this kind of bug.) I invite you to check out this Matthew Flatt article from November 2007: http://blog.racket-lang.org/2007/11/getting-rid-of-set-car-and-set-cdr.html Of course, there are different levels at which this problem can be solved. I think moving towards deprecation and removal of mutable pairs is probably a good idea, though it's really complicated and not really the point of this mail. OTOH I think it's reasonable to ask for a consensus opinion on this implementation of "for-each": (lambda (f l) (unless (list? l) (scm-error 'wrong-type-arg "for-each" "Not a list: ~S" (list l) #f)) (let for-each1 ((l l)) (unless (null? l) (f (car l)) (for-each1 (cdr l))))) Is this a reasonable implementation? Are we OK with the possibility for infinite-loops or exceptions accessing the car/cdr of what might not be a pair? Alternately if we change the test to pair? are we OK with the possibility of the loop possibly ending silently before its time? How do we deal with this kind of bug -- what's our perspective? My proposal would be that eventually, I don't know how, but Guile should remove all use of mutable pairs in its own code. There's not much set-car!/set-cdr! in Scheme so it's not that big of a deal. Therefore in light of that long-term goal, we should write library code as if pairs were immutable, and therefore the test-then-iterate example is fine code. WDYT? Cheers, Andy -- http://wingolog.org/