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: Re: for-each et al Date: Tue, 04 Mar 2014 21:30:25 +0100 Message-ID: <87wqg9ogf2.fsf@pobox.com> References: <87txbgr3wx.fsf@pobox.com> <87r46ks33b.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1393965062 12773 80.91.229.3 (4 Mar 2014 20:31:02 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 4 Mar 2014 20:31:02 +0000 (UTC) Cc: guile-devel@gnu.org To: ludo@gnu.org (Ludovic =?utf-8?Q?Court=C3=A8s?=) Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Mar 04 21:31:12 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 1WKvza-0000Hy-Db for guile-devel@m.gmane.org; Tue, 04 Mar 2014 21:31:10 +0100 Original-Received: from localhost ([::1]:48425 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WKvza-0007LO-0B for guile-devel@m.gmane.org; Tue, 04 Mar 2014 15:31:10 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:55586) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WKvzR-0007HB-JU for guile-devel@gnu.org; Tue, 04 Mar 2014 15:31:06 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WKvzM-0000tz-Rn for guile-devel@gnu.org; Tue, 04 Mar 2014 15:31:01 -0500 Original-Received: from a-pb-sasl-quonix.pobox.com ([208.72.237.25]:38198 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WKvzM-0000jF-LK; Tue, 04 Mar 2014 15:30:56 -0500 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 2B14A10EFA; Tue, 4 Mar 2014 15:30:29 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; s=sasl; bh=kfkz0n/lFYRB n9lp2/Z2tGmQEJo=; b=UV9p90JlkCy0Gk0AffeozH/Xc+fXqgM8Qnb+C6HeHmQO wj6pm1F8C8QX7zNSse0+Bbb4l2sPQ/2XxDZkHg+I63yUgx6O49KJwMuV8zsdEZq4 AvBE/aKWbhGxi0RO8+6OL3OaGQHjE/rK4CzSd9gaF7h+M03O4Mc5tg91cFv8x3E= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; q=dns; s=sasl; b=Ub87M8 Bp1sVhZKeXigNiiUCZf1h6wcKJ0e5JbyF40EzZQLSpOdexY8bWb4HqMhprvYM8dH ubRItFrltpQ81X6T24qoJeDoO3LPfOdIujy9m10N4ilYVaM1nXwP3n0FjoQAUwlY Phg/n/H0xAW/tkUdmgbY2giuVmcBUr0kfe45w= 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 20F7010EF8; Tue, 4 Mar 2014 15:30:29 -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 2ED0E10EF6; Tue, 4 Mar 2014 15:30:28 -0500 (EST) In-Reply-To: <87r46ks33b.fsf@gnu.org> ("Ludovic =?utf-8?Q?Court=C3=A8s=22'?= =?utf-8?Q?s?= message of "Sun, 02 Mar 2014 22:27:52 +0100") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) X-Pobox-Relay-ID: D2EEDC02-A3DB-11E3-B438-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:16945 Archived-At: On Sun 02 Mar 2014 22:27, ludo@gnu.org (Ludovic Court=C3=A8s) writes: > Welcome back to email. ;-) Thank you :) This makes my first round-trip ;) >> (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? > > I think an important difference you didn=E2=80=99t mention is that =E2=80= =98list?=E2=80=99 does > its list traversal in C. That's true. Let's call the above version for-each*. Then we have for-each**, which is the same except it calls list*, which is: (define (list*? l) (let lp ((hare l) (tortoise l)) (or (null? hare) (and (pair? hare) (let ((hare (cdr hare))) (or (null? hare) (and (pair? hare) (not (eq? tortoise hare)) (lp (cdr hare) (cdr tortoise))))))))) Then we have: scheme@(guile-user)> (define l (iota 100000000)) scheme@(guile-user)> ,time (for-each** (lambda (x) x) l) ;; 3.228201s real time, 3.223919s run time. 0.000000s spent in GC. scheme@(guile-user)> ,time (for-each* (lambda (x) x) l) ;; 2.356612s real time, 2.353496s run time. 0.000000s spent in GC. scheme@(guile-user)> ,time (for-each (lambda (x) x) l) ;; 3.142366s real time, 3.126806s run time. 0.000000s spent in GC. So the overhead of traversing the list twice is negligible in the worst case, and probably we still gain once the compiler gets better. >> (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))))) > I=E2=80=99m OK with this implementation. I=E2=80=99ve never found myself= iterating over > a list and modifying it concurrently. Yeah it's something that no one in their right mind does. But still we should have some kind of statement about what we guarantee -- currently the code is resilient to concurrent mutation, and we'd be relaxing that. > I=E2=80=99m all in favor of immutable pairs. However, I expect that a lo= t of > code out there relies on it. > > Moving set-car! and set-cdr! to a different module like in R6 may be a > good first (or second) step. Brainstorming possibilities: * Deprecate set-car!/set-cdr! (replacement would be mutable cells in the car/cdr; currently called variables, but could be called boxes) * Introducing a #!lang facility, and having programs with #!lang make immutable pairs * ? It's completely possible to remove mutable pair usage in Guile, but what's not clear is how to migrate our users. I assume that we would want to make Guile's core operations only operate on immutable pairs; how big would the mutable pair libraries have to be? Could we forsake R6RS/R7RS and only do immutable pairs? (I would be OK with that. In that case R5RS would run in its own environment.) Dunno, just some thoughts. Deprecating set-car!/set-cdr! would be an easy first step, if we planned to make further steps. Andy --=20 http://wingolog.org/