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 recursion hack in Emacs Lisp? Date: Fri, 16 Jul 2004 17:07:19 +0200 Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Message-ID: NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: sea.gmane.org 1089990762 18678 80.91.224.253 (16 Jul 2004 15:12:42 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Fri, 16 Jul 2004 15:12:42 +0000 (UTC) Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Fri Jul 16 17:12:37 2004 Return-path: Original-Received: from lists.gnu.org ([199.232.76.165]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1BlUO4-0007oE-00 for ; Fri, 16 Jul 2004 17:12:36 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1BlUQb-0006If-Nz for geh-help-gnu-emacs@m.gmane.org; Fri, 16 Jul 2004 11:15:13 -0400 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 (windows-nt) Cancel-Lock: sha1:czCkU+0j9+fi+E49Nk8oCkAQRh4= Original-NNTP-Posting-Host: 82.83.134.210 Original-X-Trace: 16 Jul 2004 17:07:22 +0200, 82.83.134.210 Original-Lines: 90 Original-X-Complaints-To: abuse@arcor-ip.de Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!news.tele.dk!news.tele.dk!small.news.tele.dk!news-fra1.dfn.de!newsfeed.arcor-ip.de!news.arcor-ip.de!82.83.134.210 Original-Xref: shelby.stanford.edu gnu.emacs.help:124333 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: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: main.gmane.org gmane.emacs.help:19669 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:19669 I like tail recursion a lot, because I regard it as a means to specify the flow of control that is IMO the right way for /some/ problems. Thus tail call reduction is on the top of my personal wish list for enhancements of Emacs Lisp---even before closures and greater speed. I have been wondering for a while, whether it would be possible to fake tail recursion without hacking the byte code compiler. Say, if we have an `iterate' macro like in CMU CL (which in turn is inspired by Scheme's named let): would it be possible that the macroexpanded code would be non-recursive Emacs Lisp code? Today I got bored in my lunch break and came up with this. (iterate fact ((n n) (r 1)) (if (= n 1) r (fact (1- n) (* n r)))) should expand to: (let ((continue t) (result (list n 1))) (while continue (setq result (catch 'repeat (setq result (apply (lambda (n r) (if (= n 1) r (throw 'repeat (list (1- n) (* n r))))) result)) (setq continue nil) result))) result) (Of course, a code walker would be necessary.) I can't see any problems with that approach right know. But lacking experience in implementing Lisp, I might be missing something. So my question is: Can anybody think of a case where this approach would break? While I am at it: I quickly hacked something together: (defmacro iterate (name arglist &rest body) (let ((catch-symbol (make-symbol "--repeat")) (continue (make-symbol "--continue")) (result (make-symbol "--result")) (lambda-list (mapcar 'car arglist)) (initial-args (mapcar 'cadr arglist))) (setq body (iterate-code-walk body name catch-symbol)) `(let ((,continue t) (,result (list ,@initial-args))) (while ,continue (setq ,result (catch ',catch-symbol (setq ,result (apply (lambda ,lambda-list ,@body) ,result)) (setq ,continue nil) ,result))) ,result))) (defun iterate-code-walk (exp sym catch-sym) (cond ((and (listp exp) (eq (car exp) 'quote)) exp) ((and (listp exp) (eq (car exp) sym)) (list 'throw `(quote ,catch-sym) (cons 'list (cdr exp)))) ((listp exp) (iterate-code-walk-list exp sym catch-sym)) (t exp))) (defun iterate-code-walk-list (exp sym catch-sym) (mapcar (lambda (el) (iterate-code-walk el sym catch-sym)) exp)) Oliver -- 29 Messidor an 212 de la Révolution Liberté, Egalité, Fraternité!