tail call reduction

[Oliver Scholz]

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é!