tail call reduction

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

Re: tail call reduction

[Oliver Scholz]

My keyboard is haunted by evil spirits. Lots of mistyping in my
previous post. I am not going to offer corrections for the bad
English. But one typo is especially problematic if actually somebody
would take the pain to read my made-up lapcode:

Oliver Scholz <alkibiades@gmx.de> writes:

[...]
> 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

This should be "20 goto 1".

> 21:4    return    

    Oliver
-- 
22 Pluviôse an 213 de la Révolution
Liberté, Egalité, Fraternité!

Re: tail call reduction

[Stefan Monnier]

> My main pet Emacs Lisp programming project involves both a lot of
> parsing and recursively descending of tree-like data structures.

Can you give a short description of one such case where you've bumped
into problems.  After all, the lack of tail-recursion should only be
a problem when you implement loops by recursive calls, but unless your tree
data-structures are very deep, normal recursion should fine.

> But, alas, unless I am much mistaken, proper tail recursion is simply
> impossible in a dynamically scoped environment.  I could reduce byte

I recommend you check out the lexbind branch which introduces static scoping
(it still provides dynamic scoping as well, but it should allow tail-call
elimination in most simple cases).


        Stefan

Re: tail call reduction

[Oliver Scholz]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> My main pet Emacs Lisp programming project involves both a lot of
>> parsing and recursively descending of tree-like data structures.
>
> Can you give a short description of one such case where you've bumped
> into problems.  After all, the lack of tail-recursion should only be
> a problem when you implement loops by recursive calls, but unless your tree
> data-structures are very deep, normal recursion should fine.

I don't recall the actual cases where I bumped into problems. IIRC I
got beyond `max-lisp-eval-depth' once or twice with recursive
functions on a depth-first traversal of medium-sized trees. Since the
default of said variable is 300, this should be o.k.. Hm, well, I
guess it was with a loop implemented by recursive calls.

>> But, alas, unless I am much mistaken, proper tail recursion is simply
>> impossible in a dynamically scoped environment.  I could reduce byte
>
> I recommend you check out the lexbind branch which introduces static scoping
> (it still provides dynamic scoping as well, but it should allow tail-call
> elimination in most simple cases).

Ah, of course! Thanks a lot! Wow, it seems, this Emacs manages lexical
variables on the stack ... I am impressed.

    Oliver
-- 
22 Pluviôse an 213 de la Révolution
Liberté, Egalité, Fraternité!

Re: tail call reduction

[Stefan Monnier]

> I don't recall the actual cases where I bumped into problems. IIRC I
> got beyond `max-lisp-eval-depth' once or twice with recursive
> functions on a depth-first traversal of medium-sized trees. Since the
> default of said variable is 300, this should be o.k.. Hm, well, I
> guess it was with a loop implemented by recursive calls.

The depth used by Emacs might be significantly smaller if the code is
byte-compiled.  And you can bump up the max-lisp-eval-depth (you can even
bump it locally inside your code with a let-binding).

Or you can change your algorithm to use trees that are better balanced and
will thus not be so deep (though not always if you're using something like
splay trees).


        Stefan

Re: tail call reduction

[David Combs]

>Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>   ...
>> I recommend you check out the lexbind branch which introduces static scoping

For those who aren't users of the cvs and other such programs,
where do you get this lexbind emacs-version?

Thanks,

David

Re: tail call reduction

[Oliver Scholz]

dkcombs@panix.com (David Combs) writes:

>>Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>>   ...
>>> I recommend you check out the lexbind branch which introduces static scoping
>
> For those who aren't users of the cvs and other such programs,
> where do you get this lexbind emacs-version?

Unless I am mistaken (and somebody packaged it and put it on the web
somewhere) you can get it only with cvs or "other such programs" (such
as GNU arch). With cvs you can use the option "-r lexbind" to check
out the lexbind branch.

    Oliver
-- 
12 Ventôse an 213 de la Révolution
Liberté, Egalité, Fraternité!

Re: tail call reduction

[Miles Bader]

Oliver Scholz <alkibiades@gmx.de> writes:
>>> I recommend you check out the lexbind branch which introduces
>>> static scoping
>>
>> For those who aren't users of the cvs and other such programs,
>> where do you get this lexbind emacs-version?
>
> Unless I am mistaken (and somebody packaged it and put it on the web
> somewhere) you can get it only with cvs or "other such programs" (such
> as GNU arch). With cvs you can use the option "-r lexbind" to check
> out the lexbind branch.

Yes as far as I know it's only available via CVS (as you say, the
"lexbind" tag, using something like "cvs co -r lexbind emacs") or GNU
arch (my `miles@gnu.org--gnu-2005/emacs--lexbind--0' branch).

BTW, it's quite usable as your normal emacs (I use it), i.e., it doesn't
crash a lot or anything.  However, it's really no different in behavior
from stock Emacs unless you explicitly mark certain source files as
"lexically bound" -- and then it's more for someone interested in
hacking on the byte compiler than for production use.

Basically, the status of the lexbind branch is this:

 * Lexical binding should work properly in interpreted lisp code.

 * The runtime support for lexically-bound compiled code should work
   fine (it's not particularly complicated).

 * HOWEVER, the byte-compiler fails to compile certain types of code
   properly when using "lexically-bound" mode.

   It should compile straight-forward code properly (e.g. normal
   variables just used within a function), but incorrectly handles many
   cases where it must pass explicit lexical environments around (e.g.,
   where a lambda expression uses a lexically bound variable from the
   surrounding environment).  [Much of the compiler support for this is
   written, just not debugged and made to work.]

If you are interested in the issue, however, I'd certainly appreciate
some help... :-)  I haven't actively worked on it for a while, but
I keep the branch up-to-date, and make sure the code doesn't bit-rot.

-Miles
-- 
If you can't beat them, arrange to have them beaten.  [George Carlin]

Re: tail call reduction

[Johan Bockgård]

Miles Bader <miles@gnu.org> writes:

>  * Lexical binding should work properly in interpreted lisp code.

(let* ((x 0) (y x))) => Debugger entered--Lisp error: (void-variable x)

-- 
Johan Bockgård

Re: tail call reduction

[Miles Bader]

bojohan+news@dd.chalmers.se (Johan Bockgård) writes:
>>  * Lexical binding should work properly in interpreted lisp code.
>
> (let* ((x 0) (y x))) => Debugger entered--Lisp error: (void-variable x)

Thanks, fixed.

-Miles
-- 
"Whatever you do will be insignificant, but it is very important that
 you do it."  Mahatma Ghandi