From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Oliver Scholz Newsgroups: gmane.emacs.help Subject: tail call reduction Date: Thu, 10 Feb 2005 10:39:17 +0100 Message-ID: <87k6pgwy7u.fsf@ID-87814.user.uni-berlin.de> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: sea.gmane.org 1108028936 12907 80.91.229.2 (10 Feb 2005 09:48:56 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Thu, 10 Feb 2005 09:48:56 +0000 (UTC) Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Thu Feb 10 10:48:55 2005 Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1CzAvc-0006rC-8m for geh-help-gnu-emacs@m.gmane.org; Thu, 10 Feb 2005 10:48:04 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1CzBAJ-0000of-Vp for geh-help-gnu-emacs@m.gmane.org; Thu, 10 Feb 2005 05:03:16 -0500 Original-Newsgroups: gnu.emacs.help X-Attribution: os X-Face: "HgH2sgK|bfH$; PiOJI6|qUCf.ve<51_Od(%ynHr?=>znn#~#oS>",F%B8&\vus),2AsPYb -n>PgddtGEn}s7kH?7kH{P_~vu?]OvVN^qD(L)>G^gDCl(U9n{:d>'DkilN!_K"eNzjrtI4Ya6; Td% IZGMbJ{lawG+'J>QXPZD&TwWU@^~A}f^zAb[Ru;CT(UA]c& User-Agent: Gnus/5.1006 (Gnus v5.10.6) Emacs/21.3.50 (gnu/linux) Cancel-Lock: sha1:q75VfNH7wI5btIeDrGEYxUvxR/8= Original-NNTP-Posting-Host: 84.58.40.202 Original-X-Trace: 10 Feb 2005 10:39:57 +0100, 84.58.40.202 Original-Lines: 112 Original-X-Complaints-To: abuse@arcor-ip.de Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!logbridge.uoregon.edu!news-FFM2.ecrc.net!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!newsfeed.arcor-ip.de!news.arcor-ip.de!84.58.40.202 Original-Xref: shelby.stanford.edu gnu.emacs.help:128470 Original-To: help-gnu-emacs@gnu.org X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org X-MailScanner-To: geh-help-gnu-emacs@m.gmane.org Xref: main.gmane.org gmane.emacs.help:24000 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:24000 My main pet Emacs Lisp programming project involves both a lot of parsing and recursively descending of tree-like data structures. Elisp's lack of tail call reduction has become a major nuisance to me. This is of course partly due to my personal style, yet I believe that it is also due to the nature of the task. It is comparatively easy to make a recursive function written for a recursive task tail recursive, but turning it into a loop involves major rethinking, restructuring and the introduction of a lot of temporary variables. Similarly, my parsing functions have the unfortunate tendency to become very large. It would be easy and straightforward to break them up into a bunch of mutually (tail) recursive smaller functions, but without tail call reduction such refactoring could only be achieved by relying on dynamic scoping. Both decreases local readability. When it comes to the point that I find it difficult to read my own code, something has to be done. Therefore I decided to take a save-excursion and look into the possibility of introducing tail call reduction at the very least as an optimisation to the byte code compiler. But, alas, unless I am much mistaken, proper tail recursion is simply impossible in a dynamically scoped environment. I could reduce byte opcodes like: "call N, unbind M, return" to something like "tail-call N M", whereas `tail-call' would be a new opcode that takes the number of active variable bindings as additional argument and delays their unbinding until the final return. I don't know whether this idea is silly, because I have not looked too deeply into this: it would not be proper tail recursion anyways, because the variable environment would still grow with each call. It would have to be something like "call N, unbind M, return" --> "unbind M, tail-call N". This would introduce the semantical madness of lexical scoping only for the function called in the tail. So tail call reduction is impossible, right? Another idea would be to optimise function calls away for certain functions declared with `defsubst' or with a (newly introduced) `labels'. For instance, the canonical `fact' example: (defun fact (n) (labels ((fact-iter (n r) (if (zerop n) r (fact-iter (1- n) (* n r))))) (fact-iter n 1))) could be compiled to: byte code for fact: args: (n) 0 goto 3 ;; *** the following used to be `fact-iter' *** 1:1 varbind r 2 dub 3 varbind n 4 constant zerop 2 call 1 3 goto-if-nil 2 4 reg-pop 6 varref r 7 reg-push 8 unbind 2 9 goto-stack 10:2 varref n 11 sub1 12 varref n 13 varref r 14 mult 15 unbind 2 16 goto 1 ;; *** the main body of `fact' *** 17:3 constant 4 ; return point 18 varref n 19 constant 1 20 goto 2 21:4 return With three new opcodes: `reg-pop', `reg-push': popping/pushing a value to/from the stack to/from a single (new) register and `goto-stack': pop an integer from the stack and jump to that position. Alternatively the same could be achieved with two new opcodes `subroutine-goto' and `subroutine-return', whereas `subroutine-goto' stores the value of the program counter in a linked list in a new slot in struct byte_stack before the goto and `subroutine-return' returns to that point. Something like (labels ((some-func (arg) (do-something arg))) (eval (list 'some-func arg))) would not work, but I checked with implementations of `labels' in two other lisps and it does not work there either, so that seems to be o.k.. However, it seems to me after glancing over byte-.*.el that it would be rather difficult to do as an _optimisation_ with the current bytecompiler. And implementing a `byte-compile-labels' that does something like this unconditionally makes me rather feel uneasy. Besides it would be real fun only if something similar could be done for `defsubst'. Any thoughts? Oliver -- 22 Pluviôse an 213 de la Révolution Liberté, Egalité, Fraternité!