From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Geoff Gole Newsgroups: gmane.emacs.devel Subject: Re: O(N^2) behavior in LOOP Date: Sun, 30 May 2010 06:35:26 +0800 Message-ID: References: <4C018D79.7040409@censorshipresearch.org> <4C018FD3.1020305@censorshipresearch.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 X-Trace: dough.gmane.org 1275172538 29319 80.91.229.12 (29 May 2010 22:35:38 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sat, 29 May 2010 22:35:38 +0000 (UTC) Cc: Emacs development discussions To: Daniel Colascione Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun May 30 00:35:37 2010 connect(): No such file or directory Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1OIUcy-0003d9-8G for ged-emacs-devel@m.gmane.org; Sun, 30 May 2010 00:35:36 +0200 Original-Received: from localhost ([127.0.0.1]:54315 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OIUcx-0002hK-KL for ged-emacs-devel@m.gmane.org; Sat, 29 May 2010 18:35:35 -0400 Original-Received: from [140.186.70.92] (port=59432 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OIUcr-0002dz-J6 for emacs-devel@gnu.org; Sat, 29 May 2010 18:35:30 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OIUcq-0000aM-0a for emacs-devel@gnu.org; Sat, 29 May 2010 18:35:29 -0400 Original-Received: from mail-vw0-f41.google.com ([209.85.212.41]:47883) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OIUcp-0000aD-UD for emacs-devel@gnu.org; Sat, 29 May 2010 18:35:27 -0400 Original-Received: by vws13 with SMTP id 13so3080768vws.0 for ; Sat, 29 May 2010 15:35:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:cc:content-type; bh=FJmRG447yqk7RZYGiu0nd3QiANudyiO/HIDO79zKHgw=; b=TsJhYl3bZjuEig7xDDJY8T9WMNcOaP7zEcRuG/ZLefp8wQ3H0epIkoprG1B8A7WxDf zbNlmC6s3YbIz6/cvNy/wzMGx6Sm4IHDhl8AACX5XGv/JqJHhMhksPGxWuyQKGxSMTrd C7QNQQckASNzl0fLthdu/7hjluzDvDgFiWtms= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=eLbstaDSNriazNcVQYrsTSw7/4qkY7SEoSiN61k8U7X8FcB4WufBUo+RDJKe/DcKm2 wcHBr6aA0ja9TgTZbJLDn+mQuf34+VBKsneKoehfIGWGSRg4eblpExVzjpEqr1NOdzfr SQ3rpODV/JIaYWrA85altDFasqfiegGod+eWw= Original-Received: by 10.229.250.2 with SMTP id mm2mr390748qcb.108.1275172526770; Sat, 29 May 2010 15:35:26 -0700 (PDT) Original-Received: by 10.229.250.4 with HTTP; Sat, 29 May 2010 15:35:26 -0700 (PDT) In-Reply-To: <4C018FD3.1020305@censorshipresearch.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:125350 Archived-At: For what it's worth, the elisp and SBCL implementations of LOOP behave differently when the last cdr of the loop is assigned to. ; elisp (loop for i from 1 to 3 collecting i into x collecting (progn (setf (cdr (last x)) (list 'foo)) 1) into x finally (return x)) (1 foo 1 2 foo 1 3 foo 1) ; SBCL (loop for i from 1 to 3 collecting i into x collecting (progn (setf (cdr (last x)) (list 'foo)) 1) into x finally (return x)) (1 1 2 1 3 1) The SBCL macro emits much more efficient code, but I think it's wrong. Not that LOOP is a particuarly well defined thing to judge correctness against.