From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Chris Gray Newsgroups: gmane.emacs.devel Subject: Re: tail-call elimination Date: Mon, 10 Dec 2012 22:45:38 -0800 Message-ID: <87fw3dw0h9.fsf@stuffy.starviewtechnology.com> References: <50C6CF11.2000706@dancol.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1355208348 28479 80.91.229.3 (11 Dec 2012 06:45:48 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 11 Dec 2012 06:45:48 +0000 (UTC) Cc: emacs-devel@gnu.org To: Daniel Colascione Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Dec 11 07:46:02 2012 Return-path: Envelope-to: ged-emacs-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 1TiJbL-0007EY-I8 for ged-emacs-devel@m.gmane.org; Tue, 11 Dec 2012 07:45:59 +0100 Original-Received: from localhost ([::1]:58022 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TiJb9-0002NI-1c for ged-emacs-devel@m.gmane.org; Tue, 11 Dec 2012 01:45:47 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:35011) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TiJb5-0002N2-5h for emacs-devel@gnu.org; Tue, 11 Dec 2012 01:45:44 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TiJb4-00041J-0M for emacs-devel@gnu.org; Tue, 11 Dec 2012 01:45:43 -0500 Original-Received: from mail-pa0-f41.google.com ([209.85.220.41]:42854) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TiJb3-00041C-Pa for emacs-devel@gnu.org; Tue, 11 Dec 2012 01:45:41 -0500 Original-Received: by mail-pa0-f41.google.com with SMTP id bj3so2599440pad.0 for ; Mon, 10 Dec 2012 22:45:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:in-reply-to:references:user-agent:date :message-id:mime-version:content-type; bh=Gm2ej3M1pJ2G1FQK9d/GzepNSbA+XPRBKnQButSsOOo=; b=M3LfiqgQMUlz8h4pqwqx9OsOKNGS0+7JHxpxjsbnL1+89g12zNWqCQme3IfIea9Mh9 kAHtMA8mdZPyAMblaiW49ltstKbl5dtOH9z0UG3T8fhsS86vn1WrcMIO0j/Xvpy8F2x9 kBL1zMgxMOtsU/g5eWNBXmjCPi9fkY3TmTMqxWA+Gw5I3EnmnoQDbT6siiKOcRfAX2B6 PeqXMJ0iQ8H4YS4zEOnvnkbLT2UyhBCrrxLG0whdjzWv4PLneA9/TgApTBHrq7MAQH5j cHYfFSEPmsAljtVOu015Gxaxb7MGPXY9HpSiDw/UNqy6fFfy7TgoSGecGt5R4AV3GOOL kXqQ== Original-Received: by 10.66.87.167 with SMTP id az7mr42287290pab.69.1355208340912; Mon, 10 Dec 2012 22:45:40 -0800 (PST) Original-Received: from stuffy.starviewtechnology.com (c-24-130-14-100.hsd1.ca.comcast.net. [24.130.14.100]) by mx.google.com with ESMTPS id i3sm13334370pav.18.2012.12.10.22.45.39 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 10 Dec 2012 22:45:40 -0800 (PST) In-Reply-To: <50C6CF11.2000706@dancol.org> User-Agent: Notmuch/0.13.2+83~gfa1d99b (http://notmuchmail.org) Emacs/24.1.50.1 (x86_64-unknown-linux-gnu) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 209.85.220.41 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:155446 Archived-At: Daniel Colascione writes: > On 12/10/2012 6:57 PM, Chris Gray wrote: >> Hello, >> >> I have attached a patch that implements tail-call elimination for a subset of >> emacs lisp. This will be helpful in allowing coding styles which emphasize tail >> recursion, such as is usual in languages like Scheme. > > Your patch eliminates tail calls only in byte compiled code. Until the > interpreter also supports guaranteed tail call elimination or we byte-compile > all forms before evaluating them, elisp developers cannot rely on the > optimization and cannot write idiomatic tail recursive code. As a purely > opportunistic optimization, not as a guaranteed language feature, I doubt tail > call elimination is worth the complexity. I agree that the fact that the code must be byte-compiled makes it harder to do interactive programming. In many cases, however, small tests can be done interactively to verify that the function is correct before compiling it. These would likely not blow up the stack, and thus tail-call elimination would not be needed. When the function has been shown to work, it can be byte-compiled fairly simply. I do, however, think that it's a bit inaccurate to say that this is a purely opportunistic optimization. It is guaranteed in the case that your code is byte-compiled and lexically bound. I would love to widen that subset of the language to include things that aren't byte-compiled (or to byte-compile automatically), but I've gotta start somewhere. Cheers, Chris