From: Oliver Scholz <alkibiades@gmx.de>
Subject: tail call reduction
Date: Thu, 10 Feb 2005 10:39:17 +0100 [thread overview]
Message-ID: <87k6pgwy7u.fsf@ID-87814.user.uni-berlin.de> (raw)
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é!
next reply other threads:[~2005-02-10 9:39 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-02-10 9:39 Oliver Scholz [this message]
2005-02-10 10:21 ` tail call reduction Oliver Scholz
2005-02-10 14:56 ` Stefan Monnier
2005-02-10 22:45 ` Oliver Scholz
2005-02-11 4:50 ` Stefan Monnier
2005-03-02 16:20 ` David Combs
2005-03-02 18:06 ` Oliver Scholz
2005-03-04 0:15 ` Miles Bader
[not found] ` <mailman.2542.1109897787.32256.help-gnu-emacs@gnu.org>
2005-03-04 0:56 ` Johan Bockgård
2005-03-04 14:01 ` Miles Bader
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87k6pgwy7u.fsf@ID-87814.user.uni-berlin.de \
--to=alkibiades@gmx.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).