Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Tail recursion elimination in methods

5 views
Skip to first unread message

Software Scavenger

unread,
Nov 11, 2001, 5:32:09 PM11/11/01
to
The following behavior in Lispworks 4.1.20 doesn't make sense, because
Lispworks eliminates tail recursion in ordinary functions when
compiled. Is it unable to do that in methods? And why does it say
the method is already compiled? I started Lispworks and entered the
code below, with nothing else before it.


CL-USER 1 > (defmethod testmethod ((n integer)) (if (< n 1) 123
(testmethod (1- n))))
#<STANDARD-METHOD TESTMETHOD NIL (INTEGER) 20FECB84>

CL-USER 2 > (compile 'testmethod)
;;;*** Warning in TESTMETHOD: The definition of TESTMETHOD is already
compiled.
TESTMETHOD
((TESTMETHOD #<STYLE-WARNING 20FE4054>))
NIL

CL-USER 3 > (testmethod 100)

Stack overflow (stack size 16000).
1 (abort) Return to level 0.
2 Return to top loop level 0.

Type :b for backtrace, :c <option number> to proceed, or :? for other
options

CL-USER 4 : 1 >

Thomas F. Burdick

unread,
Nov 11, 2001, 6:29:45 PM11/11/01
to
cubic...@mailandnews.com (Software Scavenger) writes:

> The following behavior in Lispworks 4.1.20 doesn't make sense, because
> Lispworks eliminates tail recursion in ordinary functions when
> compiled. Is it unable to do that in methods?

Tail call elimination in methods is hard. What if I added to your
example as below:

> CL-USER 1 > (defmethod testmethod ((n integer)) (if (< n 1) 123
> (testmethod (1- n))))
> #<STANDARD-METHOD TESTMETHOD NIL (INTEGER) 20FECB84>

(testmethod 50)
=> 123

(defmethod testmethod ((n (eql 10)))
"Eh, close enough to zero"
(format t "Approximating 10 =~~ 0~%")
(testmethod 0))

(testmethod 50)
Approximating 10 =~ 0
=> 123

You can (hopefully) see how this would get in the way of someone
trying to implement tail call elimination.

> And why does it say the method is already compiled? I started
> Lispworks and entered the code below, with nothing else before it.

I'm guessing that Lispworks always compiles methods? That would make
tail call elimination in methods, particularly methods typed into the
toplevel, quite a bit more difficult. If it has something like
CMUCL's concept of compilation blocks, then tail-calls elimination
might be feasible in generic functions in compiled files, but
otherwise, that's gonna be just way to much of a pain in the ass.

--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'

Erik Naggum

unread,
Nov 11, 2001, 10:39:19 PM11/11/01
to
* Software Scavenger

| The following behavior in Lispworks 4.1.20 doesn't make sense, because
| Lispworks eliminates tail recursion in ordinary functions when compiled.

If it allows advice to functions the same way it allows :around, :before,
and :after methods, it is hard to do it for functions, too. Predicting
what a programmer will do is hard. Disallowing certain things because of
a high optimization level is not a good idea, because it would mean that
dynamism and production quality would not be possible at the same time,
and that is sometimes precisely what you want.

| And why does it say the method is already compiled?

Well, it does not say that. You asked for the symbol to be compiled, and
the symbol's function value is the generic function, so it said that the
generic function is already compiled. That is because you did not define
your own generic function (with defgeneric); you let defmethod use one of
its already defined and compiled generic functions for you in the absence
of an existing generic function.

///
--
Norway is now run by a priest from the fundamentalist Christian People's
Party, the fifth largest party representing one eighth of the electorate.
--
Carrying a Swiss Army pocket knife in Oslo, Norway, is a criminal offense.

Tim Bradshaw

unread,
Nov 12, 2001, 5:15:38 AM11/12/01
to
cubic...@mailandnews.com (Software Scavenger) wrote in message news:<a6789134.0111...@posting.google.com>...

> The following behavior in Lispworks 4.1.20 doesn't make sense, because
> Lispworks eliminates tail recursion in ordinary functions when
> compiled. Is it unable to do that in methods? And why does it say
> the method is already compiled? I started Lispworks and entered the
> code below, with nothing else before it.
>
> [...]

I think that you underestimate how hard it is to eliminate tail-calls
in methods. It's only safe to do if you *know* at compile time that
what looks like a tail call actually is one, which probably means that
the call must either be with exactly the same arguments (`exactly the
same' meaning `the compiler can tell they are the same') as the call
its within (and its not clear to me that such a call can be useful if
its in a position where it could be a tail call) or you must be able
to make a closed-world assumption such that you know all the possible
methods on the GF at compile time. The latter case is more
interesting, obviously, and here's why it is a hard assumption to
make:

(defgeneric recurse (n))

(defmethod recurse ((n integer))
;; (1- n) is an INTEGER so this is a tail call, right?
(recurse (1- n))

(defmethod recurse ((n (eql 0)))
;; Ooops, no, its not.
0)

This may look like a silly example - for instance you could prevent it
by doing away with EQL methods (please, no one suggest this. I use
EQL methods *all the time*!), but you can see that the general problem
is fairly hard. Quite apart from the EQL method problem there's the
problem that in order to do TCE the compiler has to be able to do a
fair amount of type inference in the first place.

A better way of allowing optmisations like this (not just TCE, which a
compiler may not be interested in anyway, but other optimisations) is
a mechanism of declaring that the world is in fact closed as far as
this GF is concerned, so that it's possible to make all sorts of
assumptions about what methods exist. Dylan, I think, has this kind
of thing, which it calls `sealing'. CL doesn't (and, as far as I
know, no implementations have added it either). How interesting
sealing is depends largely on how much optimisation it allows in
practice - CL implementations seem to do a pretty good job of
optimising most of CLOS without it.

--tim

Thomas F. Burdick

unread,
Nov 12, 2001, 5:10:20 PM11/12/01
to
tfb+g...@tfeb.org (Tim Bradshaw) writes:

> A better way of allowing optmisations like this (not just TCE, which a
> compiler may not be interested in anyway, but other optimisations) is
> a mechanism of declaring that the world is in fact closed as far as
> this GF is concerned, so that it's possible to make all sorts of
> assumptions about what methods exist. Dylan, I think, has this kind
> of thing, which it calls `sealing'. CL doesn't (and, as far as I
> know, no implementations have added it either). How interesting
> sealing is depends largely on how much optimisation it allows in
> practice - CL implementations seem to do a pretty good job of
> optimising most of CLOS without it.

There are two things that make sealing more or less interesting: what
extra stuff the compiler can do with this guarantee; and how much
flexibility this takes away. Adding methods to a GF seems to be a
really good, clean way of modifying running code. The compiler I'm
working on (which uses a different object system) would benefit from
being able to seal classes, but that would seriously hamper our
ability to modify the running system, to the extent that the
efficiency gained isn't worth it.

CMUCL-style compilation blocks, on the other hand, are Very Good Things.

I suppose you could be careful and only seal GFs that you "won't" want
to modify, but how can you tell?

Bruce Hoult

unread,
Nov 12, 2001, 6:28:52 PM11/12/01
to
In article <xcvlmhb...@conquest.OCF.Berkeley.EDU>,
t...@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) wrote:

> tfb+g...@tfeb.org (Tim Bradshaw) writes:
>
> > A better way of allowing optmisations like this (not just TCE, which a
> > compiler may not be interested in anyway, but other optimisations) is
> > a mechanism of declaring that the world is in fact closed as far as
> > this GF is concerned, so that it's possible to make all sorts of
> > assumptions about what methods exist. Dylan, I think, has this kind
> > of thing, which it calls `sealing'. CL doesn't (and, as far as I
> > know, no implementations have added it either). How interesting
> > sealing is depends largely on how much optimisation it allows in
> > practice - CL implementations seem to do a pretty good job of
> > optimising most of CLOS without it.
>
> There are two things that make sealing more or less interesting: what
> extra stuff the compiler can do with this guarantee; and how much
> flexibility this takes away. Adding methods to a GF seems to be a
> really good, clean way of modifying running code. The compiler I'm
> working on (which uses a different object system) would benefit from
> being able to seal classes, but that would seriously hamper our
> ability to modify the running system, to the extent that the
> efficiency gained isn't worth it.

Sealing doesn't prevent you from modifying a running system, it just
increases the granuality of modification to include anything that made
use of the sealing declaration. It's little different to function
inlining or declaring the types of global variables in that respect.


>I suppose you could be careful and only seal GFs that you "won't"
>want to modify, but how can you tell?

As well as sealing entire GFs, Dylan also allows you to seal only *part*
of a GF, and in fact this is probably more common.

Take, for example, element() and element-setter(). Their sealing
declarations in Gydion Dylan are:

define sealed domain element (<builtin-collection>, <object>);

define sealed domain element-setter
(<object>, <builtin-mutable-collection>, <object>);

Of course this relies on the definitions of <builtin-collection> and
<builtin-mutable-collection>. I'll just list one of them :-)

define constant <builtin-mutable-collection>
= type-union(<builtin-mutable-sequence>,
<builtin-mutable-explicit-key-collection>);

define constant <builtin-mutable-sequence>
= type-union(<builtin-array>, <list>, <simple-object-deque>);

define constant <builtin-mutable-explicit-key-collection>
= type-union(<simple-object-table>, <equal-table>);

OK, you get the idea ... there are a couple more levels in some of the
branches.

What does this "define sealed domain" declaration mean? It means that
if the compiler knows that the second argument to element-setter()
belongs to any of the built-in mutable collections then it can assume
that it knows the entire applicable-methods list. If it knows the exact
class then it can call the appropriate method directly. If it doesn't
know the exact class but only that the class of the object is in some
subset of <builtin-mutable-collection> then it can use some dispatch
method that is possibly more efficient than full GF dispatch -- Gwydion
uses a tree of nested IFs.

Even if the class of the argument is totally unknown, the GF dispatch
mechanism for element-setter can be set up to special-case on calls
where the second argument is a built-in collection, while other cases go
through a more general mechanism.

The net effect of "define sealed domain" is that the GF itself can be
"open", and allow the user to add new methods specializing on their own
classes to the GF, but that dispatch can be optimized for the parts of
the GF that you don't expect to change.

As well as the collection classes, Dylan implementations typically use
define sealed domain extensively in the numeric tower, and users will
typically use it to seal make() and initialize() on their newly-declared
classes so that those operations can be inlined (or at least not
dispatched).

-- Bruce


-- Bruce

Francois-Rene Rideau

unread,
Nov 12, 2001, 8:47:02 PM11/12/01
to
tfb+g...@tfeb.org (Tim Bradshaw) writes:
> (defgeneric recurse (n))
>
> (defmethod recurse ((n integer))
> ;; (1- n) is an INTEGER so this is a tail call, right?
> (recurse (1- n))
>
> (defmethod recurse ((n (eql 0)))
> ;; Ooops, no, its not.
> 0)
WRONG! it's *STILL* a TAIL CALL.
What you have established is that it's not anymore a tail call to *self*.
But it's still a frigging *tail* call, and it *can* still be tail-merged,
with proper compiler support.
Whether the compiler *should* support such tail-call-merging or not
is of course a different question.
Certainly, tail-call to non-self, unlike the relatively trivial case
of tail-call to self, requires non-trivial munging of call frames,
which is a lot of trouble for the compiler writer,
for a result that might seem minor (or even negative!)
considering common CL coding style and/or C interfaceability.
But it is certainly possible to do, even without
heap-allocating call-frames like in hbaker's Cheney-on-the-MTA or SML/NJ.

Here are good reasons for not merging tail-calls in general
(as opposed to tail-calls to self in particular):
* keeping a track of the call history, for purposes
of debugging or of assessing security.
* complying (e.g. for immediate interoperability with C functions)
to some callee-saves calling conventions that prevent tail-call merging
because there remains cleanup to do by the would-be eliminated tail-caller.
* not spending time treating a special case that doesn't bring significant
gain considering expected coding styles.

These reasons might very well suffice in themselves.
No need to spread confusion about tail-calls.

As for tail-calls to self, and calls to self in general, note that,
due to the dynamic nature of LISP, you can *NEVER* be sure that
a (tail-)call to self is actually to self, when calling a function named by
a global symbol (and there's no standard declaration to ensure it, AFAIK):
The fdefinition might be changed by a subroutine, a concurrent thread
and/or the debugger. Only functions bound by labels or flet may be assumed
to be constant. Invalidation of code can help solve this relatively problem
while keeping the performance advantages of the common case, but it demands
quite some bit of coding from the implementors, who may choose other
optimizations first.

I think that the fact that you need a completely different
syntax for defining local and global functions (or worse, macros)
is a misdesign in CL.
Erlang does it right: you use the same syntax for all function definitions,
and distinguish local from non-local calls. You get better semantic control
without any overhead associated to moving a call from one category to another.
CMUCL, with its blocks, seems to allow one to do the same thing, too.

Yours freely,

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[ TUNES project for a Free Reflective Computing System | http://tunes.org ]
The trouble with opportunity is that it always comes disguised as hard work.
-- Herbert V. Prochnow

Tim Bradshaw

unread,
Nov 13, 2001, 5:16:14 AM11/13/01
to
tfb+g...@tfeb.org (Tim Bradshaw) wrote in message news:<fbc0f5d1.01111...@posting.google.com>...

> I think that you underestimate how hard it is to eliminate tail-calls
> in methods.

But maybe I was wrong. What I think it's hard to do is to remove the
whole generic dispatch for tail calls. But presumably it would be
possible to essentially replace the current frame with a new one while
still doing the whole dispatch thing? Whether this would be *worth*
it is another question...

--tim

Clive Tong

unread,
Nov 13, 2001, 5:47:59 AM11/13/01
to
cubic...@mailandnews.com (Software Scavenger) writes:

> The following behavior in Lispworks 4.1.20 doesn't make sense, because
> Lispworks eliminates tail recursion in ordinary functions when
> compiled. Is it unable to do that in methods? And why does it say
> the method is already compiled? I started Lispworks and entered the
> code below, with nothing else before it.
>
>
> CL-USER 1 > (defmethod testmethod ((n integer)) (if (< n 1) 123
> (testmethod (1- n))))
> #<STANDARD-METHOD TESTMETHOD NIL (INTEGER) 20FECB84>
>
> CL-USER 2 > (compile 'testmethod)
> ;;;*** Warning in TESTMETHOD: The definition of TESTMETHOD is already
> compiled.
> TESTMETHOD
> ((TESTMETHOD #<STYLE-WARNING 20FE4054>))
> NIL

The method isn't compiled at this point.

The 'already compiled' applies to the existing symbol-function which
is the generic function object.

CL-USER 2 > (symbol-function 'testmethod)
#<STANDARD-GENERIC-FUNCTION TESTMETHOD 20405E1C>

CL-USER 3 > (compiled-function-p *)
T

CL-USER 6 > (find-method #'TESTMETHOD nil (list (find-class 'integer)))
#<STANDARD-METHOD TESTMETHOD NIL (INTEGER) 20F5BFEC>

CL-USER 7 > (method-function *)
#'(LAMBDA (N) ...) <<<< Interpreted code

> CL-USER 3 > (testmethod 100)
>
> Stack overflow (stack size 16000).
> 1 (abort) Return to level 0.
> 2 Return to top loop level 0.
>
> Type :b for backtrace, :c <option number> to proceed, or :? for other
> options
>

Put the method into a buffer and compile it.
This does then reuse the stack frame.

CL-USER 16 > (method-function (find-method #'TESTMETHOD nil (list (find-class 'integer))))
#<function (METHOD TESTMETHOD (INTEGER)) 20FF32BA>

CL-USER 17 > (disassemble *)
20FF32BA:
0: 55 push ebp ;;; build stack
1: 89E5 move ebp, esp
.... blah blah blah .........
L4: 61: B501 moveb ch, 1
63: C9 leave ;;; unbuild stack
64: FF252091ED20 jmp [20ED9120] ; TESTMETHOD

CL-USER 19 > (testmethod 20000)
123

Tim Bradshaw

unread,
Nov 13, 2001, 6:37:42 AM11/13/01
to
Francois-Rene Rideau <fare+...@tunes.org> wrote in message news:<871yj3f...@Samaris.tunes.org>...

> WRONG! it's *STILL* a TAIL CALL.

No need to shout, I'm happy to be wrong. I noticed this last night
(and although google doesn't have it yet, you probably can see my
followup saying this).

As far as I can tell, LW does in fact eliminate tail calls in this
case.

--tim

Pierre R. Mai

unread,
Nov 13, 2001, 6:34:56 AM11/13/01
to
Francois-Rene Rideau <fare+...@tunes.org> writes:

> tfb+g...@tfeb.org (Tim Bradshaw) writes:
> > (defgeneric recurse (n))
> >
> > (defmethod recurse ((n integer))
> > ;; (1- n) is an INTEGER so this is a tail call, right?
> > (recurse (1- n))
> >
> > (defmethod recurse ((n (eql 0)))
> > ;; Ooops, no, its not.
> > 0)
> WRONG! it's *STILL* a TAIL CALL.
> What you have established is that it's not anymore a tail call to *self*.
> But it's still a frigging *tail* call, and it *can* still be tail-merged,
> with proper compiler support.
> Whether the compiler *should* support such tail-call-merging or not
> is of course a different question.

While one could imagine an implementation doing this when possible, I
don't think that it is a thing that meshes well with the whole idea of
generic functions, namely that you can extend them at will, without
having to worry about the implementation of other methods on the same
GF. Using tail-call optimization to do iteration will of course
invalidate that assumption:

(defmethod recurse ((n integer))
;; (1- n) is an INTEGER so this is a tail call, right?
(recurse (1- n))

TCO possible, but then (possibly, but not necessarily later):

(defmethod recurse :around ((n integer))
(if (zerop n)
0
(1+ (call-next-method))))

[ No comments about the usefulness please... ;) ]

This could suddenly turn a TCOed GF/method into one which isn't, and
that for reasons that aren't apparent either to the original or to the
new method author. Not a good idea.

> Certainly, tail-call to non-self, unlike the relatively trivial case
> of tail-call to self, requires non-trivial munging of call frames,
> which is a lot of trouble for the compiler writer,
> for a result that might seem minor (or even negative!)
> considering common CL coding style and/or C interfaceability.
> But it is certainly possible to do, even without
> heap-allocating call-frames like in hbaker's Cheney-on-the-MTA or SML/NJ.

I think the matter of method-TCO is sufficiently different from normal
function TCO in itself. E.g. I don't see problems with non-self TCO
for normal functions (in suitably constrained situations for some of
the reasons you cited), but TCO for _inherently_ extensible GFs seems
a very dangerous thing to me.

> I think that the fact that you need a completely different
> syntax for defining local and global functions (or worse, macros)
> is a misdesign in CL.

Why?

> Erlang does it right: you use the same syntax for all function
> definitions, and distinguish local from non-local calls. You get
> better semantic control without any overhead associated to moving a
> call from one category to another.

I don't see the huge advantage that this approach gives over the one
of CMUCL (that you noted below), or some suitably refined version of
same approach. It seems to me to force the caller to decide on each
call whether to do a local or non-local call, which I'd suggest he is
ill-equipped to do. The likely effect is that most users will prefer
the local call, for reasons of efficiency, if they don't think things
through (which most won't), thus making the life of any user of that
code much more complicated, if he wants to introduce dynamic updates
to a section.

This seems to me to be the C approach to coding, by forcing users to
decide questions which could have been delayed for quite a while, in
the name of very modest optimization gains. That produces a heavy
bias to non-dynamic "optimal" constructs, with all the corresponding
pitfalls that that entails.

> CMUCL, with its blocks, seems to allow one to do the same thing, too.

I think the CMU CL approach is quite different, in that it doesn't
force users to decide early, it leaves the decision to the
function/module writer, and not any and all callers, and in that the
default is the dynamic, flexible one, and further work is required to
switch to the static, limited scope one. So that this will only be
undertaken for functions where profiling has shown that calling
overhead matters. A much safer design IMHO, although I'm not sure it
is the right one.

Regs, Pierre.

--
Pierre R. Mai <pm...@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein

Francois-Rene Rideau

unread,
Nov 14, 2001, 1:14:33 PM11/14/01
to
"Pierre R. Mai" <pm...@acm.org> writes:
> I think the matter of method-TCO is sufficiently different from normal
> function TCO in itself. E.g. I don't see problems with non-self TCO
> for normal functions (in suitably constrained situations for some of
> the reasons you cited), but TCO for _inherently_ extensible GFs seems
> a very dangerous thing to me.
In a context where the tail-call optimization
was already available in the compiler, independently from the self- case,
I see no particular reason not to use it in a method.
Just how do you think it interferes with extensibility?

The continuation of the method might indeed be some handling by the gf
instead of the gf's caller; OR part of the gf handling (like
call-next-method) might be woven into the compiled method so as to
make tail-call merging more interesting. This looks like a "SMOP" problem
not a conceptual incompatibility.

Yours freely,

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[ TUNES project for a Free Reflective Computing System | http://tunes.org ]

The reason truth is stranger than fiction is that fiction has to make sense.

Francois-Rene Rideau

unread,
Nov 14, 2001, 1:42:11 PM11/14/01
to
In a thread about "Tail recursion elimination in methods",

"Pierre R. Mai" <pm...@acm.org> writes:
>> I think that the fact that you need a completely different
>> syntax for defining local and global functions (or worse, macros)
>> is a misdesign in CL.
>
> Why?
>
Because it makes moving from one to the other a global code modification,
instead of the matter of nesting/unnesting the code in proper block
constructs. Some (cumbersome but one-off) macrology could help both ways,
and I might end up writing it.

CMUCL blocks can help make global things local, though, if you don't need
to make things scope-dependent; or can they also help define scope?

An actually separate issue, that I can think about better now,
is that CL doesn't have a way to specify static calls, except in as much
as it doesn't provide a standard way to dynamically modify functions in
local scopes (apparently, ACL and LispWorks have such ways), thus making
a confusion between the usefully distinct notions of scoping and staticity.
[Actually, I suppose you could funcall a defconstant, and provide
code-walking macros that defun'ed globally re-defunable code for labels
- yuck].

>> Erlang does it right: you use the same syntax for all function
>> definitions, and distinguish local from non-local calls. You get
>> better semantic control without any overhead associated to moving a
>> call from one category to another.
>

> [...] [This approach] seems to me to force the caller to decide on each


> call whether to do a local or non-local call, which I'd suggest he is
> ill-equipped to do.

In presence of expected dynamic code update in a running system,
it's a matter of *semantics*, not just of optimization
(I think of optimizations as code transformations enabled by semantics
some of which should be reasonably expected to happen in proper
optimization settings, *where applicable* and not anywhere else).
You want to specify the atomicity of the code change,
with static calls in old active code remaining calls to the earlier version
whereas dynamic calls in old active code must call new versions.
I think that's something that requires programmer control.
Declaring functions inline in CL won't ensure a static call
in such circumstances; I don't know how CMUCL blocks work here.

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[ TUNES project for a Free Reflective Computing System | http://tunes.org ]

...so this guy walks into a bar.
"The usual, Mr. Descartes?" the barman asked.
"I think not," Rene replied, and promptly disappeared.

Tim Bradshaw

unread,
Nov 14, 2001, 1:46:35 PM11/14/01
to
"Pierre R. Mai" <pm...@acm.org> wrote in message news:<87adxq3...@orion.bln.pmsf.de>...

>
> While one could imagine an implementation doing this when possible, I
> don't think that it is a thing that meshes well with the whole idea of
> generic functions, namely that you can extend them at will, without
> having to worry about the implementation of other methods on the same
> GF. Using tail-call optimization to do iteration will of course
> invalidate that assumption:
>
> (defmethod recurse ((n integer))
> ;; (1- n) is an INTEGER so this is a tail call, right?
> (recurse (1- n))
>
> TCO possible, but then (possibly, but not necessarily later):
>
> (defmethod recurse :around ((n integer))
> (if (zerop n)
> 0
> (1+ (call-next-method))))
>
> [ No comments about the usefulness please... ;) ]
>
> This could suddenly turn a TCOed GF/method into one which isn't, and
> that for reasons that aren't apparent either to the original or to the
> new method author. Not a good idea.
>

No, I don't think this is right. AIt seems to me that a possible
implementation strategy for something like this case would be to have
each method correspond to some chunk of code, which we can consider as
a function for the sake of argument, and then to compose an effective
method as another chunk of code. In the case above this might look
something like this:

(let ((primary #'(lambda (n)
(recurse (1- n))))
(around #'(lambda (n next)
(if (zerop n) 0
(1+ (funcall next))))))
#'(lambda (n)
(funcall around n #'(lambda () (funcall primary n))))))

Now the point is that the thing called PRIMARY can happily optimise
the tail-call away, even though the overall thing is not
tail-recursive. And whether or not PRIMARY can do TCE doesn't depend
on the existence or not of AROUND - in fact PRIMARY's code isn't
affected at all by AROUND, what's affected is the `effective method'
which is what I'm trying to describe above. So although the whole
thing stops being tail-recursive, the individual methods can make
their own decisions (or rather, the compiler can make the decisions as
it compiles them), and the existence or not of TCE in a method does
not prevent redefinition.

--tim

Juliusz Chroboczek

unread,
Nov 17, 2001, 1:53:21 PM11/17/01
to
Tim Bradshaw:

TB> A better way of allowing optmisations like this (not just TCE, which a
TB> compiler may not be interested in anyway, but other optimisations) is
TB> a mechanism of declaring that the world is in fact closed as far as
TB> this GF is concerned, so that it's possible to make all sorts of
TB> assumptions about what methods exist. Dylan, I think, has this kind
TB> of thing, which it calls `sealing'.

An alternative which may (or may not) fit better in CL would be to
have a new method combination type, call it ``single,'' that is
similar to standard/daemon combination but doesn't allow :AFTER or
:AROUND (:BEFORE should be no problem, neither should CALL-NEXT-METHOD
I believe).

I am not particularly interested in this, as I try to be conscious of
relying on tail-call elimination, and pointedly avoid relying on it
within methods.

Juliusz

Juliusz Chroboczek

unread,
Nov 17, 2001, 2:14:38 PM11/17/01
to
Francois-Rene Rideau:

FR> [Actually, I suppose you could funcall a defconstant, and provide
FR> code-walking macros that defun'ed globally re-defunable code for labels
FR> - yuck].

You seem particularly keen on code-walking, lately ;-)

Try playing with MACROLET and LOAD-TIME-VALUE.

Juliusz

Juliusz Chroboczek

unread,
Nov 17, 2001, 1:46:56 PM11/17/01
to
Francois-Rene Rideau:

FR> Certainly, tail-call to non-self, unlike the relatively trivial case
FR> of tail-call to self, requires non-trivial munging of call frames,
FR> which is a lot of trouble for the compiler writer,

I just don't agree.

Eliminating a non-self tail call requires, in the general case,
building the complete stack frame of the new call, and then copying it
down over the current call frame. Assuming you update the stack
pointer at the right point, you don't even need to have an atomic
(w.r.t. GC) blt operation in your VM.

I do not think that this extra copy introduces too much complexity; at
any rate, optimising it away is no more trouble than optimising PSETQ.

FR> for a result that might seem minor (or even negative!)
FR> considering common CL coding style

What are you basing this assessment on? I've always been under the
impression that CL is the sort of language that doesn't impose a
particular coding style. (Hey, it even has PROG.)

There are some beautiful bits in the CMUCL sources that heavily rely
on tail-call elimination. I don't know if this is ``common'' CL
style, but it shows that I am not a lonely freak in my use of tail
calls.

FR> As for tail-calls to self, and calls to self in general, note
FR> that, due to the dynamic nature of LISP, you can *NEVER* be sure
FR> that a (tail-)call to self is actually to self, when calling a
FR> function named by a global symbol (and there's no standard
FR> declaration to ensure it, AFAIK):

What do you mean? Are you speaking of

(defun foo (...)
...
(foo ...))

or

(defun foo (...)
...
(funcall 'foo ...))

If the latter, then you're right. If the former, on the other hand, I
think that a conformant implementation is allowed to assume that the
call is to self, unless there is a NOTINLINE declaration in effect.

FR> CMUCL, with its blocks, seems to allow one to do the same thing, too.

Scope issues.

Juliusz

P.S. Any non-trivial code that I write seems to break LW with an
out-of-stack error. Does anyone know how to get tail-call elimination
out of LW?

Francois-Rene Rideau

unread,
Nov 20, 2001, 7:12:59 PM11/20/01
to
>>: Francois-Rene Rideau
>: Juliusz Chroboczek <j...@pps.jussieu.fr>

>
> FR> Certainly, tail-call to non-self, unlike the relatively trivial case
> FR> of tail-call to self, requires non-trivial munging of call frames,
> FR> which is a lot of trouble for the compiler writer,
>
> I just don't agree.
>
> Eliminating a non-self tail call requires, in the general case,
> building the complete stack frame of the new call, and then copying it
> down over the current call frame. Assuming you update the stack
> pointer at the right point, you don't even need to have an atomic
> (w.r.t. GC) blt operation in your VM.
>
> I do not think that this extra copy introduces too much complexity; at
> any rate, optimising it away is no more trouble than optimising PSETQ.
>
This extra complexity can indeed be relatively very small
if (as with CMUCL) you're targetting direct assembly on today's processors;
actually, if your compiler has an intermediate representation
that handles sharing of a memory location for multiple variables,
e.g. as a backend to some SSA representation, you can even do
much better than making a frame and copying it, and achieve
essentially no overhead in tail calls.
But it can be also be very big if you're targetting more or less portable C,
particularly if you try to compile code in a direct style
as opposed to using a control loop, a trampoline or a CPS transform.
I believe there are several such CL compilers.

Thus, the cost of implementing this optimization varies depending on
the general design of the compiler, and some choices of compiler design
are compatible with realizing the CL standard that make
the implementation of such feature very costly, or maybe even impossible
while preserving other features (like direct bidirectional interoperability
of LISP and C function calls).

Yours freely,

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[ TUNES project for a Free Reflective Computing System | http://tunes.org ]

Reality must take precedence over public relations,
for Mother Nature cannot be fooled.
-- R.P. Feynman

Francois-Rene Rideau

unread,
Nov 20, 2001, 8:44:22 PM11/20/01
to

Thanks for the tip! Indeed, no need for code-walking:
(macrolet ((foo (x) (funcall (load-time-value #'actual-foo t) x)))
...)
Ugly, but it should portably guarantee a statically bound call
within a set of functions compiled in the same file,
assuming no funky (eval-when ...) form introduces any discrepancy
between compile-time value and load-time-value.
[Actually, reading the standard, I'm unsure how load-time-value
interacts with defun; it could be that you cannot (load-time-value #'foo)
before foo's defun, which would prevents static calls in mutually
recursive functions. If this limitation indeed exists (or worse, if
you cannot use load-time-value on functions), it calls for a
compile-time-value special form instead.]
I wonder if CMUCL and/or other implementations actually take advantage
of such tricks to optimize function calls. Actually, in absence of a clever
check for eval-when, the load-time-value might even guarantee absence of any
optimization, since the load-time-value will be obtained after the compiler
has any chance to optimize -- ouch!

Now, reading section 3.2.2.3 more carefully, it seems that dynamic upgrade
can only happen for functions declared not-inline, and that other functions
might not be safely redefined, for the compiler might or not may the calls
static. To be portably on the safe side for dynamic redefinition
would then mean declaring all functions not-inline, and then using
the load-time-value trick in lots of places -- ouch again!
It looks like a cautious dynamic programmer would need to define his own
high-level API for static/dynamic calls and then map it to his LISP
dialect(s), with the fully ANSI standard way being almost a guarantee
of non-optimization in most implementations.

Anyway, it might allow to express the semantics of calls to statically bound
fdefinitions in code meant to be safely upgraded at runtime,
and that was the point.

Erlang defining the semantics of static vs dynamic calls seems much better.
This reminds me of very recent KMP comments on how language definitions
should privilege semantics rather than optimizations -
it looks like this is a case where CL falls short in this respect;
although this is probably due to historical compatibility with
existing implementations more than to a conspicuous design choice.

Thanks again for showing how to do things in CL that my insufficiant
knowledge of the standard led me to believe was impossible to do
(in a standard way), though the result seems somehow not fully satisfying.

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[ TUNES project for a Free Reflective Computing System | http://tunes.org ]

If you make people think they're thinking, they'll love you;
but if you really make them think, they'll hate you. -- Don Marquis

Pierre R. Mai

unread,
Nov 23, 2001, 6:06:36 PM11/23/01
to
Francois-Rene Rideau <fare+...@tunes.org> writes:

> Because it makes moving from one to the other a global code modification,
> instead of the matter of nesting/unnesting the code in proper block
> constructs. Some (cumbersome but one-off) macrology could help both ways,
> and I might end up writing it.

I think that while you still need to nest/unnest, doing the small
changes in syntax while you're at it is negligible.

That said, CL is designed for exploratory/interactive programming
(among other things), so it rather expects lots of small, independent
top-level functions.

> CMUCL blocks can help make global things local, though, if you don't need
> to make things scope-dependent; or can they also help define scope?

Defining scope in what way? This sounds interesting.

> An actually separate issue, that I can think about better now,
> is that CL doesn't have a way to specify static calls, except in as much
> as it doesn't provide a standard way to dynamically modify functions in
> local scopes (apparently, ACL and LispWorks have such ways), thus making
> a confusion between the usefully distinct notions of scoping and staticity.
> [Actually, I suppose you could funcall a defconstant, and provide
> code-walking macros that defun'ed globally re-defunable code for labels
> - yuck].

While CL doesn't define ways to specify static calls, it doesn't
prohibit implementations from defining extensions that allow more fine
grained control. E.g. implementations might have declarations that
allow you to specify "static-binding".

> >> Erlang does it right: you use the same syntax for all function
> >> definitions, and distinguish local from non-local calls. You get
> >> better semantic control without any overhead associated to moving a
> >> call from one category to another.
> >
> > [...] [This approach] seems to me to force the caller to decide on each
> > call whether to do a local or non-local call, which I'd suggest he is
> > ill-equipped to do.
>
> In presence of expected dynamic code update in a running system,
> it's a matter of *semantics*, not just of optimization
> (I think of optimizations as code transformations enabled by semantics
> some of which should be reasonably expected to happen in proper
> optimization settings, *where applicable* and not anywhere else).
> You want to specify the atomicity of the code change,
> with static calls in old active code remaining calls to the earlier version
> whereas dynamic calls in old active code must call new versions.
> I think that's something that requires programmer control.

I agree with all of this.

> Declaring functions inline in CL won't ensure a static call
> in such circumstances; I don't know how CMUCL blocks work here.

I agree that if you know a priori that your application is going to be
dynamically updated at runtime, you can make use of such a mechanism.

But CL isn't a language that is intended for only that kind of
setting. It must allow users who couldn't care less about such things
to not be bothered with it. As such it shouldn't force on users the
decision on whether to use static or dynamic calls all over the
place.

This is especially serious, if such code is going to be introduced
into a system that demands dynamic updates at a later time, which
should be possible with minimally invasive changes to the original
code. But if you forced people to decide this at every function call,
they will statistically decide wrong at least half of the time.

It seems to me that lexically scoped declarations are a much better
way of doing this, with dynamic calls being the default (for ease of
debugging and interactive redefinition). Then people with specific
needs can get complete control both for their own code, and with
minimal changes for foreign code (e.g. by declaring everything static,
except for well-known entry points).

Pierre R. Mai

unread,
Nov 23, 2001, 6:11:20 PM11/23/01
to
Francois-Rene Rideau <fare+...@tunes.org> writes:

> "Pierre R. Mai" <pm...@acm.org> writes:
> > I think the matter of method-TCO is sufficiently different from normal
> > function TCO in itself. E.g. I don't see problems with non-self TCO
> > for normal functions (in suitably constrained situations for some of
> > the reasons you cited), but TCO for _inherently_ extensible GFs seems
> > a very dangerous thing to me.
> In a context where the tail-call optimization
> was already available in the compiler, independently from the self- case,
> I see no particular reason not to use it in a method.
> Just how do you think it interferes with extensibility?
>
> The continuation of the method might indeed be some handling by the gf
> instead of the gf's caller; OR part of the gf handling (like
> call-next-method) might be woven into the compiled method so as to
> make tail-call merging more interesting. This looks like a "SMOP" problem
> not a conceptual incompatibility.

I didn't want to say that compilers shouldn't be able to use TCO/TCE
in in the implementation of GFs. That is not only permissible, but
actually a good idea, given the number of functions that might
interact for one call of a GF.

What I was arguing against (but what might not actually have been
proposed in this thread), was the reliance of people on any kind of
TCO/TCE in GFs, since foreign code might be interposed at any time in
the running of a method on a GF, and hence disable full TCE, thus
turning O(1) stack consumption into O(n) at any time.

0 new messages