Matthias Felleisen gave a presentatation at ECOOP 2004 titled
"Functional Objects"
(http://www.ccs.neu.edu/home/matthias/Presentations/ecoop2004.pdf).
In it he points to what he sees as deficiencies in OO languages and
practice that could be addressed with ideas from functional programming.
In Part III (starting at slide 54) he presents an example that is
supposed to show that an OO language is deficient if it does not provide
tail call optimization.
A paraphrase of the example: It is a good idea to replace a
union with a hierarchy of classes. For example we can think
of lists as an abstract list --'alist', and two concrete
subclasses: 'empty' and 'cons-cell'. Felleisen gives his
implementation in Java (which seems to have a few errors
in the slides). I give a CLOS equivalent:
(defclass alist () ())
(defclass empty (alist) ())
(defclass cons-cell (alist)
((head :initarg :head :accessor the-head)
(tail :initarg :tail :accessor the-tail)))
(defgeneric how-many (o a))
(defgeneric cons-length (sequence))
(defmethod how-many ((o cons-cell) a)
(how-many (the-tail o) (+ 1 a)))
(defmethod how-many ((o empty) a)
a)
(defmethod cons-length ((sequence alist))
(how-many sequence 0))
(defun kons (kar kdr)
(let ((cell (make-instance 'cons-cell :head kar :tail kdr)))
cell))
;; just a util to make large lists
(defun make-alist (n cons)
(if (> n 0)
(make-alist (- n 1) (kons 1 cons))
cons))
(defvar naught (make-instance 'empty))
Of course the implementation of 'how-many' breaks on large list in
languages (and lisp implementations) with out tail call elimination.
(Felleisen makes the blanket claim that how-many breaks in CLOS!)
My question: is this a straw-man? Felleisen implements
a "fix" by implementing 'how-many' in 'alist' by using a for
loop (which terminates by explicitly testing for an
instance of 'empty'), and claims this violates principles of
good object oriented design.
Thanks,
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> Matthias Felleisen gave a presentatation at ECOOP 2004 titled
> "Functional Objects"
> (http://www.ccs.neu.edu/home/matthias/Presentations/ecoop2004.pdf).
Nice slides :)
> My question: is this a straw-man? Felleisen implements
> a "fix" by implementing 'how-many' in 'alist' by using a for
> loop (which terminates by explicitly testing for an
> instance of 'empty'), and claims this violates principles of
> good object oriented design.
Well, OO is about sending messages to objects. So if you want to
know the length of a list you call list.length().
Just using a loop instead is not really the right thing. Maybe in
this case it might work, because you know that you "stay" in the
same class.
However, for larger examples you would have possibly more complex
code in each method, and different methods might call each other
to perform things. Then putting everything into one method (with
loops and whatever) for the sake of efficiency makes for really
unreadable, unmaintainable code.
In general I think that tail call optimization directly follows
from the principle that you free memory you don't use:
Object foo = bar();
doSomethingWith(foo);
... other code, not using foo
return bigFunctionCall();
You want this code to free foo (or leave it to the GC by nulling
it) as soon as foo is not used anymore. The same goes for the
current function's stack frame and other local variables: when you
call the possibly stack-memory-intensive bigFunCall(), you don't
want anything left around. Maybe this bigFunCall() is even
recursion, then every call would heap a new stack frame which
isn't needed at all.
Lisp doesn't require tail call opt (TCO), but OTOH you could just
as well provide a flag for Scheme (which requires it) to turn it
off, when you want it for debugging. Not to mention that you can
also debug without heaping stuff on the stack, such as tracing
(i.e. letting functions set marks when they are called). I think
the Scheme way is right; nothing prevents an implementation from
still offering the debugging features. A runtime without TCO,
however, can suffer from space leaks.
> Lisp doesn't require tail call opt (TCO), but OTOH you could just
> as well provide a flag for Scheme (which requires it) to turn it
> off, when you want it for debugging.
Besides the fact that a Scheme with tail recursion turned off is not
Scheme,
the nature of tail recursion is such that if you program functionally,
then values
from an earlier stack frame are either do not affect the current state
(in a tail-recursive
call) and so are useless for debugging, or passed in as parameters.
And if you don't program functionally, then you don't need tail
recursion and
can use loops instead.
············@gmail.com wrote:
> Besides the fact that a Scheme with tail recursion turned off is not
> Scheme,
> the nature of tail recursion is such that if you program functionally,
> then values
> from an earlier stack frame are either do not affect the current state
> (in a tail-recursive
> call) and so are useless for debugging, or passed in as parameters.
I think tracing function invocation parameter lists can be very
useful, but for this you could have an extra data structure. The
stack can be kept in TCO compliance.
> And if you don't program functionally, then you don't need tail
> recursion and
> can use loops instead.
Not every program that would run in constant space with TCO can be
expressed with loops (or only *very* unnaturally). See Shriram
Krishnamurthi's "The Swine before Perl" Slides on that. Beautiful
example.
Ulrich Hobelmann wrote:
> ············@gmail.com wrote:
>
>> Besides the fact that a Scheme with tail recursion turned off is not
>> Scheme,
>> the nature of tail recursion is such that if you program functionally,
>> then values
>> from an earlier stack frame are either do not affect the current state
>> (in a tail-recursive
>> call) and so are useless for debugging, or passed in as parameters.
>
> I think tracing function invocation parameter lists can be very useful,
> but for this you could have an extra data structure. The stack can be
> kept in TCO compliance.
...but that wouldn't be space-safe anymore still. It doesn't matter
where you store your extra data, that's just an implementation detail.
Pascal
Pascal Costanza wrote:
>> I think tracing function invocation parameter lists can be very
>> useful, but for this you could have an extra data structure. The
>> stack can be kept in TCO compliance.
>
> ...but that wouldn't be space-safe anymore still. It doesn't matter
> where you store your extra data, that's just an implementation detail.
Suppose one just saves the, say, 1000 last stack frames. Then the
extra amount of space used is bounded (hmm... - at least I think it is).
--
Jens Axel Søgaard
············@gmail.com wrote:
> And if you don't program functionally, then you don't need tail
> recursion and can use loops instead.
Wasn't the point of the slide show, that you also need proper
TCO when you follow the object oriented paradigm?
--
Jens Axel Søgaard
In article <·······················@dread12.news.tele.dk>,
Jens Axel S�gaard <······@soegaard.net> wrote:
> ············@gmail.com wrote:
>
> > And if you don't program functionally, then you don't need tail
> > recursion and can use loops instead.
>
> Wasn't the point of the slide show, that you also need proper
> TCO when you follow the object oriented paradigm?
I'm not sure what OO has to do with his claim. Wouldn't you have the
same problem if you wrote a non-OO function that calculated the length
of normal Lisp lists recursively?
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin wrote:
>>Wasn't the point of the slide show, that you also need proper
>>TCO when you follow the object oriented paradigm?
>
>
> I'm not sure what OO has to do with his claim. Wouldn't you have the
> same problem if you wrote a non-OO function that calculated the length
> of normal Lisp lists recursively?
>
Yes. The OO thing is probably just to show why Java is a baaad
baad language ;)
Ulrich Hobelmann wrote:
> Barry Margolin wrote:
>
>>> Wasn't the point of the slide show, that you also need proper
>>> TCO when you follow the object oriented paradigm?
>>
>> I'm not sure what OO has to do with his claim. Wouldn't you have the
>> same problem if you wrote a non-OO function that calculated the length
>> of normal Lisp lists recursively?
>
> Yes. The OO thing is probably just to show why Java is a baaad baad
> language ;)
No, Matthias Felleisen addressed all OO languages in his talk. (I have
been there.)
My impression is that he was just trying to wake up the ECOOP audience.
Pascal
On Thu, 24 Mar 2005 21:42:43 -0500, Barry Margolin wrote:
> I'm not sure what OO has to do with his claim. Wouldn't you have the
> same problem if you wrote a non-OO function that calculated the length
> of normal Lisp lists recursively?
That is similar to my initial reaction. It seemed that that
the slides in question were highlighting a very scheme specific
point of view, using a contrived example of a common lisp task (recursing
through a list) to show that the rest of us were a bunch of losers.
However, this discussion has led me to believe that TCO is generally
applicable to the way composite data-structures decompose into classes in
OO languages. I don't consider my-self a functional (or OO -- whatever
that means this week) zealot but I no longer see urging
tail-call-optimization support in this context as simply grandstanding for
scheme.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> On Thu, 24 Mar 2005 21:42:43 -0500, Barry Margolin wrote:
>>I'm not sure what OO has to do with his claim. Wouldn't you have the
>>same problem if you wrote a non-OO function that calculated the length
>>of normal Lisp lists recursively?
> That is similar to my initial reaction. It seemed that that
> the slides in question were highlighting a very scheme specific
> point of view, using a contrived example of a common lisp task (recursing
> through a list) to show that the rest of us were a bunch of losers.
>
> However, this discussion has led me to believe that TCO is generally
> applicable to the way composite data-structures decompose into classes in
> OO languages. I don't consider my-self a functional (or OO -- whatever
> that means this week) zealot but I no longer see urging
> tail-call-optimization support in this context as simply grandstanding for
> scheme.
Felleisen and friends wrote "How To Design Programs" (HTDP) in which
all programming constructs are motivated. The pedagogical vehicle
is the design recipe. One design recipe describes in detail how to
write functions receiving a structure (aka records). The data definition
determines the structure of the code.
Now Felleisen and others are writing a new book called "How to Design
Class Hierarchies". The design recipe for structures thus needs to
be extended to objects. In simple cases the design recipes for
writing functions receiving objects and structures ought to be
equivalent.
In the counting example (which happens to be the first in a series of
examples illustrating how to use the design recipe) one discovers that
the resulting program is easy to understand and easy to write, but
have a chance of using up the stack on very long lists. In stead of
breaking the abstraction one ought to improve the underlying language
mechanisms. In this case the solution is old technology, proper tail
call optimization.
Some examples from the new book are available, the counting
problem is the first of a series:
<http://www.ccs.neu.edu/home/vkp/HtDCH/Workshops/Summer2004/program2004-Z-H-36.html>
In case you don't know the design recipes for structures, read the
material from the beginning in order to see the systematic approach.
--
Jens Axel Søgaard
Barry Margolin wrote:
> Jens Axel Søgaard <······@soegaard.net> wrote:
>>Wasn't the point of the slide show, that you also need proper
>>TCO when you follow the object oriented paradigm?
> I'm not sure what OO has to do with his claim. Wouldn't you have the
> same problem if you wrote a non-OO function that calculated the length
> of normal Lisp lists recursively?
It is my impression that is fairly established that functional
languages should require their implementations to be provide
proper tail call optimization.
Felleisen is arguing that proper tail call optimization is not
only a good idea for functional programming but also for
object oriented programming.
--
Jens Axel Søgaard
Ulrich Hobelmann wrote:
> Lisp doesn't require tail call opt (TCO), but OTOH you could just as
> well provide a flag for Scheme (which requires it) to turn it off, when
> you want it for debugging.
...which, in a strict sense, wouldn't be Scheme anymore.
Pascal
Pascal Costanza wrote:
> Ulrich Hobelmann wrote:
>
>> Lisp doesn't require tail call opt (TCO), but OTOH you could just as
>> well provide a flag for Scheme (which requires it) to turn it off,
>> when you want it for debugging.
>
>
> ...which, in a strict sense, wouldn't be Scheme anymore.
Well, the user could deactivate part of Scheme.
I think it's better to be able to turn on a debugging mode than
having no TCO all the way through.
OTOH, many Lispers enjoy debugging live systems, so maybe there it
helps.
Ulrich Hobelmann wrote:
> Pascal Costanza wrote:
>
>> Ulrich Hobelmann wrote:
>>
>>> Lisp doesn't require tail call opt (TCO), but OTOH you could just as
>>> well provide a flag for Scheme (which requires it) to turn it off,
>>> when you want it for debugging.
>>
>>
>> ...which, in a strict sense, wouldn't be Scheme anymore.
>
> Well, the user could deactivate part of Scheme.
>
> I think it's better to be able to turn on a debugging mode than having
> no TCO all the way through.
We are discussing a purely "academic" issue here, none that has any
"practical" relevance. In practice, most Common Lisp implementations
provide TCO, you just have to switch it on. Furthermore, some Scheme
implementations don't implement "proper" tail recursion, and some allow
you to switch it off. So for all practical matters, Common Lisp and
Scheme are on par in that regard.
The only way in which Common Lisp and Scheme differ here is with regard
to the question whether some form of tail recursion elimination should
be part of the specification, i.e., a required feature of any
implementation of a language, or whether it shoud not be part of such a
specification.
The Scheme R5RS specification requires it. This means that all Scheme
implementations that don't implement it, or allow you to switch it off,
are in violation with that specification.
The ANSI Common Lisp specification doesn't require it. This means that
no Common Lisp implementation violates that specification in that regard.
Note that this is not a discussion about the usefulness of tail
recursion elimination. That's definitely a useful feature to have. It is
a discussion about making it a required or an optional feature, and
whether a language specification should reflect what implementations
actually do or not.
Pascal
In article <···············@individual.net>, Pascal Costanza wrote:
>
> The only way in which Common Lisp and Scheme differ here is with
> regard to the question whether some form of tail recursion
> elimination should be part of the specification, i.e., a required
> feature of any implementation of a language, or whether it shoud not
> be part of such a specification.
Matthias Felleisen was talking specifically about CLOS, though, and I
think he might be right about that. CLOS has method combinations, and
I think that after methods make TCO impossible, because you must build
up a stack of after methods to execute after each recursive call
returns.
--
Neel Krishnaswami
·····@cs.cmu.edu
On Thu, 24 Mar 2005 23:37:59 +0000, Neelakantan Krishnaswami wrote:
> In article <···············@individual.net>, Pascal Costanza wrote:
>>
>> The only way in which Common Lisp and Scheme differ here is with
>> regard to the question whether some form of tail recursion
>> elimination should be part of the specification, i.e., a required
>> feature of any implementation of a language, or whether it shoud not
>> be part of such a specification.
>
> Matthias Felleisen was talking specifically about CLOS, though, and I
> think he might be right about that. CLOS has method combinations, and
> I think that after methods make TCO impossible, because you must build
> up a stack of after methods to execute after each recursive call
> returns.
Well I don't know about the general case, but 'how-many'
as written in my original post runs in constant space
on sbcl.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Neelakantan Krishnaswami wrote:
> In article <···············@individual.net>, Pascal Costanza wrote:
>
>>The only way in which Common Lisp and Scheme differ here is with
>>regard to the question whether some form of tail recursion
>>elimination should be part of the specification, i.e., a required
>>feature of any implementation of a language, or whether it shoud not
>>be part of such a specification.
>
> Matthias Felleisen was talking specifically about CLOS, though, and I
> think he might be right about that. CLOS has method combinations, and
> I think that after methods make TCO impossible, because you must build
> up a stack of after methods to execute after each recursive call
> returns.
CLOS is specifically designed so that such optimizations can be
performed when there are no :after methods. I think it should even be
possible when you have :after methods because a CLOS implementation
could inline the methods inside an effective method function. I don't
see why this shouldn't be possible. I haven't checked, though.
Pascal
In article <···············@individual.net>,
Pascal Costanza <··@p-cos.net> wrote:
> Neelakantan Krishnaswami wrote:
>
> > In article <···············@individual.net>, Pascal Costanza wrote:
> >
> >>The only way in which Common Lisp and Scheme differ here is with
> >>regard to the question whether some form of tail recursion
> >>elimination should be part of the specification, i.e., a required
> >>feature of any implementation of a language, or whether it shoud not
> >>be part of such a specification.
> >
> > Matthias Felleisen was talking specifically about CLOS, though, and I
> > think he might be right about that. CLOS has method combinations, and
> > I think that after methods make TCO impossible, because you must build
> > up a stack of after methods to execute after each recursive call
> > returns.
>
> CLOS is specifically designed so that such optimizations can be
> performed when there are no :after methods. I think it should even be
> possible when you have :after methods because a CLOS implementation
> could inline the methods inside an effective method function. I don't
> see why this shouldn't be possible. I haven't checked, though.
At compile time, when it must determine how to implement the call, it
dosn't know whether there will be any :after methods.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin wrote:
> In article <···············@individual.net>,
> Pascal Costanza <··@p-cos.net> wrote:
>
>
>>Neelakantan Krishnaswami wrote:
>>
>>
>>>In article <···············@individual.net>, Pascal Costanza wrote:
>>>
>>>
>>>>The only way in which Common Lisp and Scheme differ here is with
>>>>regard to the question whether some form of tail recursion
>>>>elimination should be part of the specification, i.e., a required
>>>>feature of any implementation of a language, or whether it shoud not
>>>>be part of such a specification.
>>>
>>>Matthias Felleisen was talking specifically about CLOS, though, and I
>>>think he might be right about that. CLOS has method combinations, and
>>>I think that after methods make TCO impossible, because you must build
>>>up a stack of after methods to execute after each recursive call
>>>returns.
>>
>>CLOS is specifically designed so that such optimizations can be
>>performed when there are no :after methods. I think it should even be
>>possible when you have :after methods because a CLOS implementation
>>could inline the methods inside an effective method function. I don't
>>see why this shouldn't be possible. I haven't checked, though.
>
> At compile time, when it must determine how to implement the call, it
> dosn't know whether there will be any :after methods.
OK, right. I have made the mistake to think only about recursive calls
of a generic function to itself. In that case, if the classes of the
required arguments stay the same, the effective method is fixed and so a
tail call to itself could be turned into a jump inside the effective
method function.
It would be at least very hard to achieve the same for mutually
recursive generic functions. Some form of recompilation of call sites
would be needed then, I guess.
Pascal
From: Pascal Costanza
Subject: TCO and CLOS, was Re: Tail call optimization and OO
Date:
Message-ID: <3al7p2F6drc93U1@individual.net>
Pascal Costanza wrote:
> Barry Margolin wrote:
>
>> In article <···············@individual.net>,
>> Pascal Costanza <··@p-cos.net> wrote:
>>
>>
>>> Neelakantan Krishnaswami wrote:
>>>
>>>
>>>> In article <···············@individual.net>, Pascal Costanza wrote:
>>>>
>>>>
>>>>> The only way in which Common Lisp and Scheme differ here is with
>>>>> regard to the question whether some form of tail recursion
>>>>> elimination should be part of the specification, i.e., a required
>>>>> feature of any implementation of a language, or whether it shoud not
>>>>> be part of such a specification.
>>>>
>>>>
>>>> Matthias Felleisen was talking specifically about CLOS, though, and I
>>>> think he might be right about that. CLOS has method combinations, and
>>>> I think that after methods make TCO impossible, because you must build
>>>> up a stack of after methods to execute after each recursive call
>>>> returns.
>>>
>>>
>>> CLOS is specifically designed so that such optimizations can be
>>> performed when there are no :after methods. I think it should even be
>>> possible when you have :after methods because a CLOS implementation
>>> could inline the methods inside an effective method function. I don't
>>> see why this shouldn't be possible. I haven't checked, though.
>>
>>
>> At compile time, when it must determine how to implement the call, it
>> dosn't know whether there will be any :after methods.
>
> OK, right. I have made the mistake to think only about recursive calls
> of a generic function to itself. In that case, if the classes of the
> required arguments stay the same, the effective method is fixed and so a
> tail call to itself could be turned into a jump inside the effective
> method function.
>
> It would be at least very hard to achieve the same for mutually
> recursive generic functions. Some form of recompilation of call sites
> would be needed then, I guess.
Forget the last two paragraphs, this was pure nonsense.
I think it should be possible to achieve TCO in CLOS.
- When a generic function is called, first its discriminating function
is executed. That's the part of the gf invocation protocol that calls
compute-applicable-methods and compute-effective-method, generates an
effective method function and finally calls it. (Effective method
functions are cached, so the first steps may be skipped.) The invocation
of the effective method function is in a tail position, so this can be
optimized.
- When an :after method is present, the effective method looks like this:
(multiple-value-prog1
(progn
(call-method #<first before method>)
(call-method #<second before method>)
...
(call-method
#<first primary method>
(list #<second primary method> ...)))
(call-method #<last after method>)
(call-method #<butlast after method>)
...)
- When no :after method is present, the effective method looks like that:
(multiple-value-prog1
(progn
(call-method #<first before method>)
(call-method #<second before method>)
...
(call-method
#<first primary method>
(list #<second primary method> ...))))
...which can be simplified to this:
(progn
(call-method #<first before method>)
(call-method #<second before method>)
...
(call-method
#<first primary method>
(list #<second primary method> ...))))
In the latter case, (call-method #<first primary method> ...) is in a
tail position, so all calls made in the first primary method that are in
a tail position can be optimized as well.
What is true is that the compiler cannot decide for a given defmethod
form whether that method will ultimately be called in a tail position or
not. However, the compiler could just compile two versions of such a
method and then defer the decision which method to use to that step in
the discriminating function that computes the effective method function.
Am I right, or am I missing something here?
Of course, I don't know whether any CLOS implementation does this...
Pascal
On Thu, 24 Mar 2005 22:11:57 +0100, Pascal Costanza wrote:
> Ulrich Hobelmann wrote:
>
>> Lisp doesn't require tail call opt (TCO), but OTOH you could just as
>> well provide a flag for Scheme (which requires it) to turn it off, when
>> you want it for debugging.
>
> ...which, in a strict sense, wouldn't be Scheme anymore.
>
>
> Pascal
But, in general, it seems Felleisen is right in so far as
tail call optimization supports arbitrarily long chains
of message delegation.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
On Thu, 24 Mar 2005 16:07:21 -0600, Matthew D Swank wrote:
> But, in general, it seems Felleisen is right in so far as
> tail call optimization supports arbitrarily long chains
> of message delegation.
Or maybe this is a horrible capability :)
Matt
--
"You do not really understand something unless you can explain
it to your grandmother." — Albert Einstein.
Ulrich Hobelmann <···········@web.de> writes:
> In general I think that tail call optimization directly follows
> from the principle that you free memory you don't use:
Hey, ever realized that UNIX has had TCO from day 1:
exec() and friends
So it must be a good thing, wouldn't you think?
exec() makes a deal of a difference. I remember on MS-DOS and AmigaOS,
where the calling process would unnecessarily sit around waiting for
the callee to terminate in a system()-like call to terminate
themselves, thus waisting resources!
Whenever I see a shell script which ends in
program $args
I change it to
exec program $args
since that time. The shell need not hang around.
> ... other code, not using foo
> return bigFunctionCall();
> A runtime without TCO, however, can suffer from space leaks.
AFAIK, TCO does not save you from the difference between reachable and
alive objects. So the GC may still not reclaim everything the
programmer would believe it could. Your argument seems moot to me.
The example you provide has nothing to do with TCO. It solely depends
on the the compiler to perform some lifetime analysis.
Regards,
Jorg Hohle
Telekom/T-Systems Technology Center
Joerg Hoehle wrote:
> Ulrich Hobelmann <···········@web.de> writes:
>
>>In general I think that tail call optimization directly follows
>>from the principle that you free memory you don't use:
>
>
> Hey, ever realized that UNIX has had TCO from day 1:
> exec() and friends
> So it must be a good thing, wouldn't you think?
Definitely. Exec rules! (both the syscall and the sh command)
> AFAIK, TCO does not save you from the difference between reachable and
> alive objects. So the GC may still not reclaim everything the
> programmer would believe it could. Your argument seems moot to me.
Why? When you don't needlessly keep the stack frame around, it
doesn't keep pointed-to objects alive. When a variable stops
being live, sometimes you might need to explicitly zero it to
allow the pointer to be collected I think. Maybe that's why often
Java never releases space?
> The example you provide has nothing to do with TCO. It solely depends
> on the the compiler to perform some lifetime analysis.
It was meant as a comparison. Lack of TCO is like keeping dead
variables around. I think Andrew Appel took this very seriously
for SML/NJ, but I didn't read too much about that.
Matthew D Swank wrote:
> Matthias Felleisen gave a presentatation at ECOOP 2004 titled
> "Functional Objects"
> (http://www.ccs.neu.edu/home/matthias/Presentations/ecoop2004.pdf).
>
> In it he points to what he sees as deficiencies in OO languages and
> practice that could be addressed with ideas from functional programming.
> In Part III (starting at slide 54) he presents an example that is
> supposed to show that an OO language is deficient if it does not provide
> tail call optimization.
>
> A paraphrase of the example: It is a good idea to replace a
> union with a hierarchy of classes. For example we can think
> of lists as an abstract list --'alist', and two concrete
> subclasses: 'empty' and 'cons-cell'. Felleisen gives his
> implementation in Java (which seems to have a few errors
> in the slides). I give a CLOS equivalent:
>
> (defclass alist () ())
>
> (defclass empty (alist) ())
>
> (defclass cons-cell (alist)
> ((head :initarg :head :accessor the-head)
> (tail :initarg :tail :accessor the-tail)))
>
> (defgeneric how-many (o a))
> (defgeneric cons-length (sequence))
>
> (defmethod how-many ((o cons-cell) a)
> (how-many (the-tail o) (+ 1 a)))
>
> (defmethod how-many ((o empty) a)
> a)
>
> (defmethod cons-length ((sequence alist))
> (how-many sequence 0))
>
> (defun kons (kar kdr)
> (let ((cell (make-instance 'cons-cell :head kar :tail kdr)))
> cell))
>
> ;; just a util to make large lists
> (defun make-alist (n cons)
> (if (> n 0)
> (make-alist (- n 1) (kons 1 cons))
> cons))
>
> (defvar naught (make-instance 'empty))
>
>
> Of course the implementation of 'how-many' breaks on large list in
> languages (and lisp implementations) with out tail call elimination.
> (Felleisen makes the blanket claim that how-many breaks in CLOS!)
This is wrong because Common Lisp is not a language "without tail call
elimination". Most CL implementations provide it. It's just that Scheme
(where he comes from) and Common Lisp have different ideas about what
should be part of a language specification and what not. Tail call
optimization (whatever version thereof) is just not a required feature
in Common Lisp.
This is different from Java: Java doesn't allow for tail call
elimination. (I don't remember the details anymore, but I vaguely recall
that it's a consequence of how exception handling is specified in Java.)
> My question: is this a straw-man? Felleisen implements
> a "fix" by implementing 'how-many' in 'alist' by using a for
> loop (which terminates by explicitly testing for an
> instance of 'empty'), and claims this violates principles of
> good object oriented design.
"Good" is a subjective statement. In pure OOP, only the objects should
decide how a message should be handled, not someone from the outside.
HOW-MANY recursively sends the "message" HOW-MANY to the tail of a list.
When you turn this into a for loop, you are not leaving it up to the
tail anymore to decide how to react to the HOW-MANY message, but you are
"forcing" a behavior on it - you are counting the tail without asking
it. In this way, you turn the tail and therefore all the elements of a
list into "passive" objects.
The Java API has many examples of such violations of "pure" OOP style.
Thankfully, Common Lisp is a multi-paradigm language, so we can choose
to use a "pure" OOP approach while making sure that the optional tail
call elimination is switched on, or use an imperative approach and just
count the damn suckers. ;)
Pascal
In article <······························@c.net>, Matthew D Swank wrote:
>
> Of course the implementation of 'how-many' breaks on large list in
> languages (and lisp implementations) with out tail call elimination.
> (Felleisen makes the blanket claim that how-many breaks in CLOS!)
>
> My question: is this a straw-man? Felleisen implements
> a "fix" by implementing 'how-many' in 'alist' by using a for
> loop (which terminates by explicitly testing for an
> instance of 'empty'), and claims this violates principles of
> good object oriented design.
It does violate OO-design principles, since HOW-MANY should be applied to
every object that participates in the operation. In principle, more
suclasses of alist could be created, and in that case the loop version of
the algorithm would need to be rewritten. But this example is a bit too
simple to demonstrate that.
However I disagree with this singling out of tail call elimination. Yes,
in some situation (where lost of tail calls are chained!) it will be
useful. In some other case not so. Think of a HOW-MANY method on trees for
example. I would give t.c.e. the same usefulness as function inlining,
which makes accessor functions and other one-liners much more efficient.
--
Eic Danie
Eric Daniel wrote:
> However I disagree with this singling out of tail call elimination. Yes,
> in some situation (where lost of tail calls are chained!) it will be
> useful. In some other case not so. Think of a HOW-MANY method on trees for
> example. I would give t.c.e. the same usefulness as function inlining,
> which makes accessor functions and other one-liners much more efficient.
>
TCO is the difference between constant space usage and maybe
running out of space. So it can influence the correctness of a
program.
Think of two functions calling each other, maybe forever in a web
server. Inlining is just a performance optimization, it doesn't
change a programs order of space usage.
Sure, in lots of cases it doesn't matter. And people don't write
those that do in languages without TCO. But it makes sense, if
you can live with the disadvantages (like to debugging).
In article <···············@individual.net>, Ulrich Hobelmann wrote:
>
> TCO is the difference between constant space usage and maybe
> running out of space. So it can influence the correctness of a
> program.
>
> Think of two functions calling each other, maybe forever in a web
> server. Inlining is just a performance optimization, it doesn't
> change a programs order of space usage.
Good point. But my main issue (which I should have spelled out) was with
the sweeping statement in Felleisen's presentation: "Object-Oriented
Programming in languages that don't require tail-call optimizations makes
no sense." His example seems too atypical to prove his point.
In a typical application where OO style is useful (i.e. lots of objects
talking to each other), it seems to me that most calls will be in non-tail
positions. I can't prove it of course... but this raised my interest
enough to study some of my recent code and count the tail calls :-)
--
Eric Daniel
Eric Daniel wrote:
> In article <···············@individual.net>, Ulrich Hobelmann wrote:
>
>>
>> TCO is the difference between constant space usage and maybe
>> running out of space. So it can influence the correctness of a
>> program.
>>
>> Think of two functions calling each other, maybe forever in a web
>> server. Inlining is just a performance optimization, it doesn't
>> change a programs order of space usage.
>
>
> Good point. But my main issue (which I should have spelled out) was with
> the sweeping statement in Felleisen's presentation: "Object-Oriented
> Programming in languages that don't require tail-call optimizations makes
> no sense." His example seems too atypical to prove his point.
It's contrived, and I got another one ;)
Imagine you have EvenNumber and OddNumber, subclassing Number.
This might be useful, since they have individual methods powering:
evenNumber.powering(n) means n to the power of evenNumber.
(kindof like
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4)
Of course you can always use if, but strict OO partitions classes
into subclasses with no if in their methods, everything else is
C-style coding.
Now give these objects the methods odd and even and the ability to
subtract one. An evenNumber would create an oddNumber, and vice
versa. Yes, it's inefficient, but I only want to prove the point.
Again, like in the list example, testing hugeNumber.even() would
run out of stack space. The (not anymore needed) numbers created
on the way would be garbage-collected (I hope), but why should an
implementation hold on to a function return it doesn't need
anymore (return new OddNumber(this.n - 1).even();)? The call to
even should be passed the current continuation, so it can deliver
its result directly to the caller, instead of executing a return
instruction 10000 times in the end and only then freeing memory.
> In a typical application where OO style is useful (i.e. lots of objects
> talking to each other), it seems to me that most calls will be in non-tail
> positions. I can't prove it of course... but this raised my interest
> enough to study some of my recent code and count the tail calls :-)
>
Maybe, maybe not. If you only push values to and fro, yes. If
you have complex webs of objects and want to calculate, say, the
value of a game (winning, losing), or the next move, or the
dimensions of a complex graphical widget with thousands of
subcomponents, then you will have LOTS of (recursive) method
invocations, I guess.
Ulrich Hobelmann wrote:
> Eric Daniel wrote:
>> Good point. But my main issue (which I should have spelled out) was with
>> the sweeping statement in Felleisen's presentation: "Object-Oriented
>> Programming in languages that don't require tail-call optimizations makes
>> no sense." His example seems too atypical to prove his point.
> It's contrived, and I got another one ;)
Why do you think it is contrived? It is the simplest example in which
the problem occurs.
An example showing that tail call optimization is needed, has to feature
a computation that uses bounded space in the presence of TCO and
and linear (or more) space usage otherwise.
The simplest data structure that can be arbitrarily long is a list;
and one of the simplest things to do with a list, is to calculate its
length.
--
Jens Axel Søgaard
In article <·······················@dread12.news.tele.dk>, Jens Axel S�gaard wrote:
> Ulrich Hobelmann wrote:
>
> > It's contrived, and I got another one ;)
>
> Why do you think it is contrived? It is the simplest example in which
> the problem occurs.
>
> An example showing that tail call optimization is needed, has to feature
> a computation that uses bounded space in the presence of TCO and
> and linear (or more) space usage otherwise.
>
> The simplest data structure that can be arbitrarily long is a list;
> and one of the simplest things to do with a list, is to calculate its
> length.
Maybe not contrived, but not a great example of object orientation!
The only concrete members of the class hierarchy are cons and empty and it
is not clear what possible other subclasses there would be, and whether
TCO would still apply on their length method.
Of course it illustrates TCO nicely, but I don't think it was the
point.
--
Eric Daniel
Eric Daniel wrote:
> Maybe not contrived, but not a great example of object orientation!
> The only concrete members of the class hierarchy are cons and empty and it
> is not clear what possible other subclasses there would be, and whether
> TCO would still apply on their length method.
Would an interpreter written in the object oriented style be a
better example?
--
Jens Axel Søgaard
In article <·······················@dread12.news.tele.dk>, Jens Axel S�gaard wrote:
> Eric Daniel wrote:
> > Maybe not contrived, but not a great example of object orientation!
> > The only concrete members of the class hierarchy are cons and empty and it
> > is not clear what possible other subclasses there would be, and whether
> > TCO would still apply on their length method.
>
> Would an interpreter written in the object oriented style be a
> better example?
>
This sounds intriguing... Do you know where I can find out more about
this? (Google only turned out interpreters for object-oriented languages).
--
Eric Daniel
>> Would an interpreter written in the object oriented style be a
>> better example?
> This sounds intriguing... Do you know where I can find out more about
> this? (Google only turned out interpreters for object-oriented languages).
Try the appended. Something like
(my-eval '((lambda (x) (+ x 1)) 5) '())
Note that MY-EVAL (LIST T) and MY-APPLY (CLOSURE T) make mutually
recursive tail calls. The resulting interpreter will be properly tail
recursive only if the Lisp compiler eliminates this recursion.
(I was a little sceptical of Jens's idea initially, but this turns out
to be rather nice code. You can add new constants to the interpreted
language just by adding new methods for MY-EVAL.
Pity you cannot specialise on (CONS (EQL 'LAMBDA)). I guess adding
another method dispatch for ``lambda macros'' would solve this
particular issue.
Soliloquy ends.)
Juliusz
(defstruct closure args body env)
(defgeneric my-eval (form env))
(defgeneric my-apply (function arguments))
(defmethod my-eval ((form symbol) env)
(cdr (or (assoc form env)
(error "Undefined variable ~S" form))))
(defmethod my-eval ((form number) env)
(declare (ignore env))
form)
(defmethod my-eval ((form (eql '+)) env)
(declare (ignore env))
#'+)
(defmethod my-eval ((form list) env)
(if (eq 'lambda (car form))
(make-closure :args (cadr form)
:body (caddr form)
:env env)
(my-apply (my-eval (car form) env)
(mapcar #'(lambda (e) (my-eval e env)) (cdr form)))))
(defmethod my-apply ((function function) args)
(apply function args))
(defmethod my-apply ((function closure) args)
(my-eval (closure-body function)
(append (mapcar #'cons (closure-args function) args)
(closure-env function))))
Jens Axel Søgaard wrote:
>>>> Would an interpreter written in the object oriented style be a
>>>> better example?
> Eric Daniel:
>
>>> This sounds intriguing... Do you know where I can find out more about
>>> this? (Google only turned out interpreters for object-oriented
>>> languages).
Here is one: HotScheme:
<http://stgtech.com/HotScheme/source/>
--
Jens Axel Søgaard
In article <···············@individual.net>, Ulrich Hobelmann wrote:
>
> It's contrived, and I got another one ;)
>
> Imagine you have EvenNumber and OddNumber, subclassing Number.
> This might be useful, since they have individual methods powering:
> evenNumber.powering(n) means n to the power of evenNumber.
> (kindof like
> http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4)
>
> Of course you can always use if, but strict OO partitions classes
> into subclasses with no if in their methods, everything else is
> C-style coding.
>
> Now give these objects the methods odd and even and the ability to
> subtract one. An evenNumber would create an oddNumber, and vice
>> versa. Yes, it's inefficient, but I only want to prove the point.
> Again, like in the list example, testing hugeNumber.even() would
> run out of stack space. The (not anymore needed) numbers created
> on the way would be garbage-collected (I hope), but why should an
> implementation hold on to a function return it doesn't need
> anymore (return new OddNumber(this.n - 1).even();)? The call to
> even should be passed the current continuation, so it can deliver
> its result directly to the caller, instead of executing a return
> instruction 10000 times in the end and only then freeing memory.
>
I'm not knocking TCO, every language should have it!
My point is that this sort of example isn't a good illustration of TCO. A
well-know algorithm (list length or power) that uses linear recursion is
translated it into OO style. But the OO encapsulation is only an illusion:
we must know everything about the methods in order to determine the
algorithm's efficiency (in your example there cannot be subclasses
other than OddNumber and evenNumber). A claim that doing X would break
encapsulation is therefore not valid because there isn't real
encapsulation in the first place.
The lack of control on the cost of methods is a general problem with OO's
encapsulation and is not limited to the TCO issue.
> Maybe, maybe not. If you only push values to and fro, yes. If
> you have complex webs of objects and want to calculate, say, the
> value of a game (winning, losing), or the next move, or the
> dimensions of a complex graphical widget with thousands of
> subcomponents, then you will have LOTS of (recursive) method
> invocations, I guess.
My point exactly :-) These two examples result in tree recursion,
where TCO doesn't help.
I'm racking my brain and I can't think of an example that would involve
- an extensible class hierarchy
- a generic function for which all methods make a single recursive call
(in tail position)
It would be interesting to find one though.
--
Eric Daniel
Eric Daniel <···········@barberic.org>:
> I'm racking my brain and I can't think of an example that would involve
> - an extensible class hierarchy
> - a generic function for which all methods make a single recursive call
> (in tail position)
> It would be interesting to find one though.
Automata. Used in parsers, in language interpreters, in graph theory.
Take the following Finite State Automaton:
a b
1 -----> 2 -----> accept
<-----
a
(It recognises the regular expression a(aa)*b.)
Suppose that you want to implement it in Lisp. Of course, you could
use gotos:
(defun fortran ()
(tagbody
one
(ecase (get-next-action)
((a) (go two)))
two
(ecase (get-next-action)
((a) (go one))
((b) (go accept)))
accept
(return-from fortran)))
Obviously, in a real-world example you do something interesting at
each state rather than simply dispatching to the next one. As your
automaton grows, the FORTRAN function becomes unwieldy. The solution
is to replace the GOTOs by tail calls:
(defun one ()
(ecase (get-next-action)
((a) (two))))
(defun two ()
(ecase (get-next-action)
((a) (one))
((b) (accept))))
(defun accept ()
nil)
At some point, you need to leave the area of finite state; in other
words, you want to encode supplementary data in your states. Well,
easy, instead of having your states be functions, you make them into
objects, and dispatch on the object instead of calling a function:
(defclass state () (...))
(defclass one (state) (...))
(defclass two (state) (...))
(defclass accept (state) ())
;;; state constructors make-one, make-two and make-accept omitted
(defmethod dispatch ((state one))
(ecase (get-next-action)
((a) (dispatch (make-one state)))))
(defmethod dispatch ((state two))
(ecase (get-next-action)
((a) (dispatch (make-one state)))
((b) (dispatch (make-accept state)))))
(defmethod dispatch ((state accept))
nil)
Obviously, both methods fail when you don't have tail call
elimination. So what can you do when you don't? The usual method --
used for example in ``indirect threading'' Forth implementations -- is
to have the dispatch function return the new state to its caller
rather than tail call into itself, and have a ``while(c) c = dispatch(c)''
loop to drive the dispatch. So you get something like
(defmethod dispatch ((state two))
(ecase (get-next-action)
((a) (make-one state))
((b) (make-one state))))
(defun run-automaton (state)
(loop
while state do (setq state (dispatch state))))
My measurements indicate that you pay a roughly 20% penalty for that
sort of transformation in C. (In Lisp, I tend to simply assume that
TCO works.)
Juliusz
Eric Daniel <···········@barberic.org> writes:
> In article <···············@individual.net>, Ulrich Hobelmann wrote:
> >
> > TCO is the difference between constant space usage and maybe
> > running out of space. So it can influence the correctness of a
> > program.
> >
> > Think of two functions calling each other, maybe forever in a web
> > server. Inlining is just a performance optimization, it doesn't
> > change a programs order of space usage.
>
> Good point. But my main issue (which I should have spelled out) was with
> the sweeping statement in Felleisen's presentation: "Object-Oriented
> Programming in languages that don't require tail-call optimizations makes
> no sense." His example seems too atypical to prove his point.
>
> In a typical application where OO style is useful (i.e. lots of objects
> talking to each other), it seems to me that most calls will be in non-tail
> positions. I can't prove it of course... but this raised my interest
> enough to study some of my recent code and count the tail calls :-)
Indeed, a good OO implementation of cons-length would be:
(defmethod cons-length ((o empty)) 0)
(defmethod cons-length ((o cons-cell)) (1+ (cons-length (the-tail o))))
;; no tail call here!
how-many is un-OO. In any case, it's quite weird to pass the
_results_ as arguments to internal functions...
--
__Pascal Bourguignon__ http://www.informatimago.com/
In article <··············@thalassa.informatimago.com>,
Pascal Bourguignon <····@mouse-potato.com> wrote:
> Eric Daniel <···········@barberic.org> writes:
>
> > In article <···············@individual.net>, Ulrich Hobelmann wrote:
> > >
> > > TCO is the difference between constant space usage and maybe
> > > running out of space. So it can influence the correctness of a
> > > program.
> > >
> > > Think of two functions calling each other, maybe forever in a web
> > > server. Inlining is just a performance optimization, it doesn't
> > > change a programs order of space usage.
> >
> > Good point. But my main issue (which I should have spelled out) was with
> > the sweeping statement in Felleisen's presentation: "Object-Oriented
> > Programming in languages that don't require tail-call optimizations makes
> > no sense." His example seems too atypical to prove his point.
> >
> > In a typical application where OO style is useful (i.e. lots of objects
> > talking to each other), it seems to me that most calls will be in non-tail
> > positions. I can't prove it of course... but this raised my interest
> > enough to study some of my recent code and count the tail calls :-)
>
> Indeed, a good OO implementation of cons-length would be:
>
> (defmethod cons-length ((o empty)) 0)
> (defmethod cons-length ((o cons-cell)) (1+ (cons-length (the-tail o))))
> ;; no tail call here!
>
>
> how-many is un-OO. In any case, it's quite weird to pass the
> _results_ as arguments to internal functions...
That style of recursive calling is frequently necessary to allow TCO to
be used. So if you're writing recursive code that's expected to become
deeply nested, you have to convert it to this style.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
In article <···············@individual.net>,
Ulrich Hobelmann <···········@web.de> wrote:
> Think of two functions calling each other, maybe forever in a web
> server. Inlining is just a performance optimization, it doesn't
> change a programs order of space usage.
>
> Sure, in lots of cases it doesn't matter. And people don't write
> those that do in languages without TCO. But it makes sense, if
> you can live with the disadvantages (like to debugging).
TCO has exactly the same properties with repect to debugging as its less
expressive alternative in other languages, the "goto", including things
built up from goto's such as while and for loops.
And if your compiler has a switch to turn off TCO then tail calls are
superior for debugging, at the cost of possibly running out of stack
space. But goto doesn't offer even the possibility of doing that.
--
Bruce | 41.1670S | \ spoken | -+-
Hoult | 174.8263E | /\ here. | ----------O----------
Bruce Hoult wrote:
> In article <···············@individual.net>,
> Ulrich Hobelmann <···········@web.de> wrote:
>
>>Think of two functions calling each other, maybe forever in a web
>>server. Inlining is just a performance optimization, it doesn't
>>change a programs order of space usage.
>>
>>Sure, in lots of cases it doesn't matter. And people don't write
>>those that do in languages without TCO. But it makes sense, if
>>you can live with the disadvantages (like to debugging).
>
> TCO has exactly the same properties with repect to debugging as its less
> expressive alternative in other languages, the "goto", including things
> built up from goto's such as while and for loops.
>
> And if your compiler has a switch to turn off TCO then tail calls are
> superior for debugging, at the cost of possibly running out of stack
> space. But goto doesn't offer even the possibility of doing that.
You get the same advantages in a language that allows you to switch TCO
on. It's just that it doesn't force you to use recursion, but it's the
programmer's decision whether to use it or not.
Scheme doesn't allow TCE to be switched off, in a strict reading of R5RS.
Pascal
Matthew D. Swank:
> [Matthias Felleisen at ECOOP 2004] presents an example that is
> supposed to show that an OO language is deficient if it does not
> provide tail call optimization.
I'd formulate that somewhat differently. A language is deficient if
it doesn't guarantee tail call optimisation. In particular, this
applies to OO languages.
It is important to understand what ``guarantee'' means in the above
context: that there is a (hopefully convenient) way for the programmer
to ensure that a given tail call gets eliminated; it does not
necessarily mean that all tail calls must be eliminated.
The example that you quote is a fairly classical one: iterating over a
complex data structure whose size is not known in advance. The only
way to fix the issue in a language without TCO would be to embed
complete knowledge of the structure in one function (or macro, in the
context of Lisp), as happens with things such as DOLIST. With some
data structures, for example complex automata, this breaks
encapsulation.
As other have pointed in this thread, this claim doesn't invalidate
particular Common Lisp implementations; OTOH, it does invalidate the
use of Common Lisp as a portable language.
(Most CL programmers agree that TCO is a good idea under some
circumstances; some CL programmers, including myself, choose to write
code that depends on TCO and deliberately ignore the problems it might
create under some implementations.)
Juliusz