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

do loops and idioms

13 views
Skip to first unread message

mi...@orsi.com

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

consider the code fragment below, which you are free to use if you find it
useful.

;; the main routine

(defun filtered-input (predicate prompt)
"Obtain input that passes the predicate"
(labels ((local-input ()
(format t prompt)
(read)))
(do ((j (local-input) (local-input)))
((funcall predicate j) j))))

;; here are some applications
(defun get-pos-num ()
(filtered-input #'(lambda (x) (and (numberp x) (plusp x)))
"~&Enter a positive number:"))

(defun input-integer () (filtered-input #'integerp "~&Enter an integer.
Numbers like 4.0 count as floats, not integers:"))

;; here are my questions

It bothers me that I have to repeat myself in my do loop in the
definition of j. Is there another idiom in common usage in common LISP?
Of course in scheme I would have written it as a tail recursive function:

(define (filtered-input predicate prompt)
(let ((local-input (sequence (display prompt) (read))))
(if (predicate local-input)
local-input
(filtered-input predicate prompt))))

for that matter is there a more idiomatic way of writing this in scheme?

-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet

Christopher N. Vogt

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to mft...@rocketmail.com

You can certainly do this in Lisp:

(defun filtered-input (predicate prompt)


(labels ((local-input ()
(format t prompt)
(read)))

(let ((result (local-input)))
(if (funcall predicate result)
result
(filtered-input predicate prompt)))))

For discussion sake, I'd have written this in the following manner:

(defun filtered-input (predicate prompt)
(format t prompt)
(let ((result (read)))
(if (funcall predicate result)
result
(filtered-input predicate prompt))))

As an aside, is it only us Lisp people who are "bothered" when we "repeat
ourselves"? This is a familiar refrain, that I only hear from Lisp'ers
(myself included). I don't recall hearing this from someone who has not
written in Lisp before.

Kent M Pitman

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

[Replying only to comp.lang.lisp, and ONLY because I had written
the reply before noticing the cross-posting. I consider
cross-posting anti-social and would not normally have replied
at all. (Gotta install those good cross-post filters people
mailed me...)]

"Christopher N. Vogt" <vo...@home.com> writes:

> You can certainly do this in Lisp:
>
> (defun filtered-input (predicate prompt)

> (labels ((local-input () ...))
> (let (...)
> (if (...)
> result
> (filtered-input predicate prompt)))))

Uh, I wouldn't advise this. If you go a very long time without
getting a true value in your IF's test, you'll run out of stack.
Lisp, unlike Scheme, is not constrained to turn tail recursion
into iteration. Many implementations do under some circumstances
optimize this, but there are debugging trade-offs, and it is
generally unwise to build code--especially portable code--around
this plan.

I might prefer

(defun filtered-input (predicate prompt)
(flet ((local-input () (format t prompt) (read)))
(loop (let ((result (local-input)))
(when (funcall predicate result)
(return result))))))

In effect, this forces the tail recursion optimization explicitly.

Christopher N. Vogt

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to Kent M Pitman

Kent M Pitman wrote:
>
> [Replying only to comp.lang.lisp, and ONLY because I had written
> the reply before noticing the cross-posting. I consider
> cross-posting anti-social and would not normally have replied
> at all. (Gotta install those good cross-post filters people
> mailed me...)]
>
> "Christopher N. Vogt" <vo...@home.com> writes:
>
> > You can certainly do this in Lisp:
> >
> > (defun filtered-input (predicate prompt)
> > (labels ((local-input () ...))
> > (let (...)
> > (if (...)
> > result
> > (filtered-input predicate prompt)))))
>
> Uh, I wouldn't advise this. If you go a very long time without
> getting a true value in your IF's test, you'll run out of stack.
> Lisp, unlike Scheme, is not constrained to turn tail recursion
> into iteration. Many implementations do under some circumstances
> optimize this, but there are debugging trade-offs, and it is
> generally unwise to build code--especially portable code--around
> this plan.

[me standing on soapbox]
With appropriate compiler switches set, any compiler that does not optimize
this is has a bug IMHO.

Marco Antoniotti

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

Kent M Pitman <pit...@world.std.com> writes:

>
...


>
> Uh, I wouldn't advise this. If you go a very long time without
> getting a true value in your IF's test, you'll run out of stack.
> Lisp, unlike Scheme, is not constrained to turn tail recursion
> into iteration. Many implementations do under some circumstances
> optimize this, but there are debugging trade-offs, and it is
> generally unwise to build code--especially portable code--around
> this plan.

Which of the major CL implementations do not optimize tail-recursion?

>
> I might prefer
>
> (defun filtered-input (predicate prompt)
> (flet ((local-input () (format t prompt) (read)))
> (loop (let ((result (local-input)))
> (when (funcall predicate result)
> (return result))))))
>
> In effect, this forces the tail recursion optimization explicitly.

Admit it! You are really "the Peaceman" :) There is no explicit
recursion in the above code. :)

--
Marco Antoniotti
==============================================================================
California Path Program - UC Berkeley
Richmond Field Station
tel. +1 - 510 - 231 9472

Erik Naggum

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

* mi...@orsi.com

| (defun filtered-input (predicate prompt)
| "Obtain input that passes the predicate"
| (labels ((local-input ()
| (format t prompt)
| (read)))

| (do ((j (local-input) (local-input)))
| ((funcall predicate j) j))))
:

| It bothers me that I have to repeat myself in my do loop in the
| definition of j.
| Is there another idiom in common usage in common LISP?

well, I would do one of these:

(loop initially (format t prompt)
for local-input = (read)
until (funcall predicate local-input)
finally (return local-input))

(do () () ;or `loop'
(format t prompt)
(let ((local-input (read)))
(when (funcall predicate local-input)
(return local-input))))

or you could use the Lisp reader for a short-hand way of repeating a form.
I used this for a while, but then I confused myself, so I stopped. what do
others think?

(do ((local-input #1=(progn (format t prompt) (read)) #1#))
((funcall predicate local-input)
local-input))

| Of course in scheme I would have written it as a tail recursive function:
|
| (define (filtered-input predicate prompt)
| (let ((local-input (sequence (display prompt) (read))))
| (if (predicate local-input)
| local-input
| (filtered-input predicate prompt))))

you could do the same in Common Lisp:

(defun filtered-input (predicate prompt)
(format *query-io* prompt)
(let ((local-input (read *query-io*)))
(if (funcall predicate local-input)
local-input
(filtered-input predicate prompt))))

as a matter of user interface design, I think it would make sense to
indicate that a value was rejected and to use another prompt for repeats:

(defun filtered-input (predicate prompt repeat-prompt)
(loop initially (format *query-io* prompt)
for local-input = (read *query-io*)
until (funcall predicate local-input)
do (format *query-io* repeat-prompt)
finally (return local-input)))

#\Erik
--
if you think this year is "97", _you_ are not "year 2000 compliant".

see http://sourcery.naggum.no/emacs/ for GNU Emacs 20-related material.

Rainer Joswig

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

Marco Antoniotti wrote:

> Which of the major CL implementations do not optimize tail-recursion?
>

Symbolics CL.


Kent M Pitman

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

"Christopher N. Vogt" <vo...@home.com> writes:

> With appropriate compiler switches set, any compiler that does not

> optimize [tail recursion] is has a bug IMHO.

I understand that you are just trying to say that you wish this were
so, but really it is not. You are mixing several issues in a forum
full of people with varying levels of knowledge and experience and
it is important not to conflate them in the same casual way you might
feel comfortable doing in a group of people you know personally.

First, there is the question of what a bug is. A bug is when something
doesn't behave according to documentation. The documentation does not
guarantee you what you want, and so you have no reason to say there is
a bug.

One reason for this is that we wanted to allow low-cost cheapy
implementations for those who are not able to fund full work. Opining
that an implementation is buggy when it conforms to a standard is, I
am told by the people who make standards, a risk of lawsuit and
something you should not do. Low-cost implementations may trade cost
for efficiency or other features, but the market NEEDS to accomodate a
variety of cost/feature trade-offs and you should separate the notion
of what you personally would buy from what others should be permitted
to offer.

Personally, I absolutely abhor the tail recursion elimination and
don't want it done for me ever. If I want a loop, I will write one.
But when stack is pushed, I want to find it when debugging, and I try
never to crank debugging down so low that I lose this feature, and
moreover, I'd be happy to buy an implementation which didn't waste
cycles trying to infer loops where I never wrote them. But that's
just a personal preference and my real point is that it's an
implementation choice and that implementation choices are made by each
vendor based on who they seek as customers. Most vendors with enough
money to do so try to accomodate both, since it is possible, but in
cases where they do not, they are entitled not to be ridiculed.

Also, it is permissible for there to be interpeted-only
implementations and it may be especially hard (or not, again depending
on implementation) for them to recognize certain kinds of tail
recursion efficiently.

And, finally, even in implementations offering this setting, since it
is not a semantic part of the language, deliberately blowing out by
doing a recursion because you insist on writing it that way even
knowing it won't always work when there is a better way to write it is
not acceptable engineering practice to me. If someone were working
for me and kept doing that, he'd be reprimanded for risking program
correctness to satisfy personal style. Done enough, it could mean
someone's job. So while you're on your high horse here telling people
what's a bug and what's not, keep in mind that you're also perhaps
teaching styles that may get a person into job trouble.

IMO, people should not adopt any particular style without knowing the
pluses and minuses of that style--and the more nonstandard the style,
the more care is due by the person advocating it. There are DEFINITE
and MAJOR minuses for trying to use recursion as an expressive style
for a loop in Lisp. Enough so that I think you really should just not
recommend it unless you run the group yourself and are talking to
people who you will defend personally when it goes awry. When
recommending it to others, it's important to keep the caveats attached
and let them make the value judgment since they will suffer the
consequences when something goes wrong.

Then again, that's all just -my- opinion.

Christopher N. Vogt

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to Kent M Pitman

Kent M Pitman wrote:

Gosh, you can be prolific! :-)

>
> "Christopher N. Vogt" <vo...@home.com> writes:
>
> > With appropriate compiler switches set, any compiler that does not
> > optimize [tail recursion] is has a bug IMHO.
>

> [...]


>
> First, there is the question of what a bug is. A bug is when something
> doesn't behave according to documentation. The documentation does not
> guarantee you what you want, and so you have no reason to say there is
> a bug.

Isn't there an implicit gaurantee that things will generally "work"? For
example, if I had a lisp environment that blew out the stack, or ran out
of memory, or gc'd so much that no useful work could be accomplished, whenever
I added 1 to a value e.g. (1+ foo), even though I had the required amount
of memory that the vendor recommended, wouldn't you call that a bug? I would.
This is how I see the issue of tail-recursion elimination.

>
> [...]
>

>
> Also, it is permissible for there to be interpeted-only
> implementations and it may be especially hard (or not, again depending
> on implementation) for them to recognize certain kinds of tail
> recursion efficiently.

I did say "appropriate compiler switches set", the implication (and my
intention) being that I'm talking about compiled code, not interpreted.

>
> [...]
>

Marco Antoniotti

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

Given what Kent Pitman says regarding allowances for "cheapo"
implementations of Common Lisp, let me ask quite a different question.

Which implementations of Scheme (or whatever name is used) are not
properly tail-recursive?

Michael Rot13 Klein

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

Christopher N. Vogt wrote:

> As an aside, is it only us Lisp people who are "bothered" when we "repeat
> ourselves"? This is a familiar refrain, that I only hear from Lisp'ers
> (myself included). I don't recall hearing this from someone who has not
> written in Lisp before.

It bothers me. I usually program in Smalltalk. For what it's worth,Scheme is
the only post-Smalltalk language i've used that I can stomache.
But Haskell sound interesting...
-- Mike Klein

--
To programatically despam my email address, see:
http://www.alumni.caltech.edu/~mklein/rot13ed.st
GO SMALLTALK -- GO VW2.5.2c beta


Chuck Fry

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to

In article <scflny3...@moskvitch.PATH.Berkeley.EDU>,

Marco Antoniotti <mar...@moskvitch.path.berkeley.edu> wrote:
>Given what Kent Pitman says regarding allowances for "cheapo"
>implementations of Common Lisp, let me ask quite a different question.
>
>Which implementations of Scheme (or whatever name is used) are not
>properly tail-recursive?

If I remember correctly, at least R4RS specifies that tail recursion
support is mandatory, a fundamental property of Scheme.
-- Chuck
--
Chuck Fry -- Jack of all trades, master of none
chu...@chucko.com (text only please), chuc...@home.com (MIME enabled)
This space for rent... NOT.

Christopher N. Vogt

unread,
Dec 2, 1997, 3:00:00 AM12/2/97
to Kent M Pitman

>Kent M Pitman wrote:
>
> > "Christopher N. Vogt" <vo...@home.com> writes:
>
> > > Kent M Pitman wrote:
>
> > Isn't there an implicit gaurantee that things will generally "work"?
>
> Heh. Strictly, no. I've previously claimed copyright on the smallest
> Common Lisp implementation. (Sorry, Harlequin, I did this long before
> I arrived to work for you so it's mine, mine, mine--if you want to
> license it, you can stand in line with all the other interested
> parties :-) ...
>
> (defun conforming-common-lisp ()
> (write-string "Memory exhausted."))

Well, as the consumer of a product, e.g. somebody's implementation of Common
Lisp, I couldn't disagree more strongly.

>
> > For example, if I had a lisp environment that blew out the stack, or ran out
> > of memory, or gc'd so much that no useful work could be accomplished, whenever
> > I added 1 to a value e.g. (1+ foo), even though I had the required amount
> > of memory that the vendor recommended, wouldn't you call that a bug?
>

> No, actually. But I might not buy the product. It is conforming, and
> explicitly so. It is a resource limitation. Indeed, it is entirely
> the reason that SERIOUS-CONDITION and ERROR are distinct conditions.
> Resource errors like STORAGE-EXHAUSTED are not errors in that they
> violate no requirement on either programs or implementations; they
> ARE, however, serious and so they enter the debugger EVEN IF errors
> are being ignored. You can make something stronger than IGNORE-ERRORS
> by using HANDLER-CASE with SERIOUS-CONDITION (or even CONDITION)
> rather than ERROR, but the point is that the language itself contains
> support acknowledging this complex philosophical line between "a bug"
> and a "resource limitation".

If you didn't buy the product, how could you know it had this
mis-behavior? You couldn't. You'd have to buy it and try, and upon
finding out, you'd complain.

>
> > I would.
> > This is how I see the issue of tail-recursion elimination.
>

> I'd rather you define it as a bug in the design of the language. I'd
> disagree with you, but you'd be entitled to disagree at that level.
> Once we're down into what the language requires and what
> implementations and programs do, it's plain that any reasonable system
> of logic demands that you not consider this a bug unless the term
> "bug" becomes a meaningless term you can apply anywhere. Sometimes
> people call these "design misfeatures", and I can live with that, too
> ... well, except I'll perhaps argue it's a "design feature". But one
> person's feature is another's..etc.

You and I seem to be talking past each other, I suspect because you are a
language specifyer, and I am a product consumer. As a consumer of any product,
I expect it to work. If it doesn't work, it has a bug. I use the word "bug"
specifically because it is stronger than "mis-feature", and that is how
I feel about TRE.

I don't believe this to be a language issue, it is an implementation issue.
I don't think requireing, or not requiring TRE belongs in the specification
of a language, however I do believe that any self-respecting
implementation of any language in this day and age, ought to support the
option of doing TRE.

>
> > > Also, it is permissible for there to be interpeted-only
> > > implementations and it may be especially hard (or not, again depending
> > > on implementation) for them to recognize certain kinds of tail
> > > recursion efficiently.
> >
> > I did say "appropriate compiler switches set", the implication (and my
> > intention) being that I'm talking about compiled code, not interpreted.
>

> Right. The point I was trying to get at is that one doesn't rewrite
> one's code as one uses it for different purposes (debugging vs
> production). At least I don't. I debug code SO THAT I can send it
> out once debugged; to me it is pointless to debug one set of code and
> then rewrite it differently to send out. So if in debug mode it won't
> work, it's not very interesting that there's another mode it could
> have worked in. At least to me. Your mileage may vary.

My delivered code always includes performance enhancement. I have found that
I can often gain a factor of 2 or more in performance by tweaking the way
the code is compiled in a *very* small fraction of the entire program. By
having the compiler optimize maybe 1% of my functions, I loose very little
in debugability, and gain an awful lot in performance. This of course
assumes that the compiler supports such tweaking, and not all CL
implementations do as much as I'd like.

>
> Further, I have found that programs in which you are sure you can say
> what implementations they will run in are often not worth worrying
> about--if your program doesn't have enough longevity that you can't
> predict whose implementation it may ultimately have to run in, then
> sometimes I might say you are working on things with planned
> obsolescence in them. Not that that's a crime. But life is short and
> one would like one's efforts to last. I have worked on more than one
> multi-decade software effort and have seen a lot of unexpected
> portings. I've done the porting in some cases. And I've found that
> some extralinguistic strategies have longer lifetimes than others.
> And one of them is that this battle between tail recursion and
> iteration has been going a long time, but languages pretty much always
> have a way to loop that is both perspicuous and likely to have a
> direct mapping in a new dialect or implementation; the same is just
> not true of tail recursion. It's a nice teaching device, but it's
> available some places and not in others, and though the rewrite to
> iterative form is not rocket science, I find it slows down porting
> efforts and leads to needless bugs. Again, your mileage may vary.

While I agree with you philosophically, from a practical standpoint I disagree,
although I suppose it depends on exactly what work you are involved in.

If I'm bidding on a project, I have two choices: 1. I can do as you describe
in which case it is going to take me longer up front to develop the code, but
down the road, if I have to port, or make other changes I can do it faster
and cleaner; or 2. I can program specifically for the task at hand, and not
think
about the future. Now your way is going to take longer, and cost more money
up front, and reduce the chance that I am successful in winning the contract.
Similarly if I'm developing an application to sell on my own, I'm probably not
going to be thinking about porting. I just want the product developed as fast
as possible to maybe get to market before the other guy, and to reduce my costs
so I can price my product less than the other guy, and hopefully be more
successful.

Kent M Pitman

unread,
Dec 3, 1997, 3:00:00 AM12/3/97
to

"Christopher N. Vogt" <vo...@home.com> writes:

> Kent M Pitman wrote:
>
> Gosh, you can be prolific! :-)

Oops. Sorry about that. I was in a hurry and didn't probably edit my
remarks as carefully as I might have. I send private followup to
Christopher on this. In brief, though, I'm sorry to the extent he may
have felt jumped on about this--it touches a hot-button about Lisp vs
Scheme and I probably read a lot more into his remarks than he
intended.

> Isn't there an implicit gaurantee that things will generally "work"?

Heh. Strictly, no. I've previously claimed copyright on the smallest
Common Lisp implementation. (Sorry, Harlequin, I did this long before
I arrived to work for you so it's mine, mine, mine--if you want to
license it, you can stand in line with all the other interested
parties :-) ...

(defun conforming-common-lisp ()
(write-string "Memory exhausted."))

> For example, if I had a lisp environment that blew out the stack, or ran out


> of memory, or gc'd so much that no useful work could be accomplished, whenever
> I added 1 to a value e.g. (1+ foo), even though I had the required amount
> of memory that the vendor recommended, wouldn't you call that a bug?

No, actually. But I might not buy the product. It is conforming, and
explicitly so. It is a resource limitation. Indeed, it is entirely
the reason that SERIOUS-CONDITION and ERROR are distinct conditions.
Resource errors like STORAGE-EXHAUSTED are not errors in that they
violate no requirement on either programs or implementations; they
ARE, however, serious and so they enter the debugger EVEN IF errors
are being ignored. You can make something stronger than IGNORE-ERRORS
by using HANDLER-CASE with SERIOUS-CONDITION (or even CONDITION)
rather than ERROR, but the point is that the language itself contains
support acknowledging this complex philosophical line between "a bug"
and a "resource limitation".

> I would.


> This is how I see the issue of tail-recursion elimination.

I'd rather you define it as a bug in the design of the language. I'd
disagree with you, but you'd be entitled to disagree at that level.
Once we're down into what the language requires and what
implementations and programs do, it's plain that any reasonable system
of logic demands that you not consider this a bug unless the term
"bug" becomes a meaningless term you can apply anywhere. Sometimes
people call these "design misfeatures", and I can live with that, too
... well, except I'll perhaps argue it's a "design feature". But one
person's feature is another's..etc.

> > Also, it is permissible for there to be interpeted-only


> > implementations and it may be especially hard (or not, again depending
> > on implementation) for them to recognize certain kinds of tail
> > recursion efficiently.
>
> I did say "appropriate compiler switches set", the implication (and my
> intention) being that I'm talking about compiled code, not interpreted.

Right. The point I was trying to get at is that one doesn't rewrite
one's code as one uses it for different purposes (debugging vs
production). At least I don't. I debug code SO THAT I can send it
out once debugged; to me it is pointless to debug one set of code and
then rewrite it differently to send out. So if in debug mode it won't
work, it's not very interesting that there's another mode it could
have worked in. At least to me. Your mileage may vary.

Further, I have found that programs in which you are sure you can say


what implementations they will run in are often not worth worrying
about--if your program doesn't have enough longevity that you can't
predict whose implementation it may ultimately have to run in, then
sometimes I might say you are working on things with planned
obsolescence in them. Not that that's a crime. But life is short and
one would like one's efforts to last. I have worked on more than one
multi-decade software effort and have seen a lot of unexpected
portings. I've done the porting in some cases. And I've found that
some extralinguistic strategies have longer lifetimes than others.
And one of them is that this battle between tail recursion and
iteration has been going a long time, but languages pretty much always
have a way to loop that is both perspicuous and likely to have a
direct mapping in a new dialect or implementation; the same is just
not true of tail recursion. It's a nice teaching device, but it's
available some places and not in others, and though the rewrite to
iterative form is not rocket science, I find it slows down porting
efforts and leads to needless bugs. Again, your mileage may vary.

As I mentioned in private mail, these remarks are mostly aimed not at
Christopher but at those others watching us haggle who might not have
thought so hard about these matters as either he or I has. I didn't
want the remarks to go unchallenged, but it isn't he who I'm
challenging -- just the concepts. That doesn't make my position
right--it just establishes that this is not a settled issue.

Hope that makes things somewhat clearer than I did before.

Rob Warnock

unread,
Dec 3, 1997, 3:00:00 AM12/3/97
to

Chuck Fry <chu...@best.com> wrote:
+---------------

| >Which implementations of Scheme (or whatever name is used) are not
| >properly tail-recursive?
|
| If I remember correctly, at least R4RS specifies that tail recursion
| support is mandatory, a fundamental property of Scheme.
+---------------

While that is quite true, there are still several useful implementations
that violate it, at least in its most general form (that is, other than
immediate self-recursion), primarily compilers which chose intermediate
target languages (e.g., C, Java) which don't conveniently support generalized
tail-call optimization, e.g.:

- Scheme->C
- Bigloo
- Stalin
- Kawa (Scheme in Java)

...and probably others.


-Rob

p.s. AFAIK, all of the above *will* properly handle tail-recursion within
a single "DEFINE" or "LETREC" group, just not the full generality.

-----
Rob Warnock, 7L-551 rp...@sgi.com http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673 [New area code!]
2011 N. Shoreline Blvd. FAX: 650-933-4392
Mountain View, CA 94043 PP-ASEL-IA

Bruno Haible

unread,
Dec 3, 1997, 3:00:00 AM12/3/97
to

Christopher N. Vogt <vo...@computer.org> wrote about tail recursion elimination
(TRE):

>
> I don't believe this to be a language issue, it is an implementation issue.
> I don't think requireing, or not requiring TRE belongs in the specification
> of a language, however I do believe that any self-respecting
> implementation of any language in this day and age, ought to support the
> option of doing TRE.

*Any* language? I invite you to go out and implement tail recursion
elimination for GNU C. Not that it would be unfeasible, but you wouldn't
be done with it in a year.

Yes, it is an implementation issue. Take those Lisp implementations, for
example, which compile to C, like GCL and Scheme->C. The mere fact of
supporting tail recursion elimination in general would force on them a
function call convention which is slower than the current one.

Bruno


Christopher Browne

unread,
Dec 3, 1997, 3:00:00 AM12/3/97
to

On 3 Dec 1997 19:30:03 GMT, Bruno Haible <hai...@ilog.fr> wrote:
>*Any* language? I invite you to go out and implement tail recursion
>elimination for GNU C. Not that it would be unfeasible, but you wouldn't
>be done with it in a year.

I thought that GCC knew about tail recursion elimination. At least,
the last time the "recursion is evil, complex, and stupid" came up,
someone posted code generated by GCC that at least *appeared* to
indicate that:

a) Using a tail recursive algorithm makes some algorithms read better,
whether in LISP, Scheme, or even C, and

b) Some C compilers are intelligent enough to recognize and optimize
out tail recursion.

I could be wrong about the latter...
--
cbbr...@hex.net, <http://www.hex.net/~cbbrowne/>
Windows95, Word97, Excel95: With all the criticisms of Microsoft, at
least they provide "best-before" dating on many of their products...

Jrm

unread,
Dec 3, 1997, 3:00:00 AM12/3/97
to

Christopher N. Vogt <vo...@computer.org> wrote about tail recursion
elimination
(TRE):

> I don't believe this to be a language issue, it is an implementation


issue.
> I don't think requireing, or not requiring TRE belongs in the
specification
> of a language, however I do believe that any self-respecting
> implementation of any language in this day and age, ought to support the
> option of doing TRE.


I'm pretty fanatical about TRE, but when a language specifies that
the lifetime (extent) of an object is precisely the extent of the function
that creates it, the language itself specifies that it is not in general
tail
recursive. Take C++ for example. You could do a little TRE some of time,
but not in general.

Rolf-Thomas Happe

unread,
Dec 4, 1997, 3:00:00 AM12/4/97
to

In article <664eob$m...@george.sabre.com> cbbr...@news.amrcorp.com
(Christopher Browne) writes:
I thought that GCC knew about tail recursion elimination. At least,

What gcc does is (I believe) tail *self* call merging, not general
tail call merging resp. full blown tail recursion optimisation.

rthappe

--
Getretener Quark wird weich und breit. (Tucholsky)
http://www.cauce.org/ Coalition Against Unsolicited Commercial Email

Jon Buller

unread,
Dec 4, 1997, 3:00:00 AM12/4/97
to

Bruno Haible wrote:
>
> *Any* language? I invite you to go out and implement tail recursion
> elimination for GNU C. Not that it would be unfeasible, but you wouldn't
> be done with it in a year.

Um... The simple cases have been done in GCC for a long time. The
simple tail recursive factorial, and it's for loop companion have
produced nearly identical code for at least two or three years.
(Version 2.4.5 I think is when I first tried it out.)

Of course the GCC version produces much different results for large
inputs since Lisp has different ideas about what ints are than C does...

> Yes, it is an implementation issue. Take those Lisp implementations, for
> example, which compile to C, like GCL and Scheme->C. The mere fact of
> supporting tail recursion elimination in general would force on them a
> function call convention which is slower than the current one.

I think this has more to do with the way C's semantics deal with
local variables, (lack of) garbage collection, and the like, than
with tail recursion optimization itself.

Jon Buller

Bruno Haible

unread,
Dec 4, 1997, 3:00:00 AM12/4/97
to

<emer...@cape.com> wrote:
>
> but when a language specifies that
> the lifetime (extent) of an object is precisely the extent of the function
> that creates it, the language itself specifies that it is not in general
> tail recursive.

... which is a plus for performance: In a language which specifies that
it is in general tail recursive, fewer variables can be stack allocated.
By requiring tail recursion elimination, many function-local variables
are forced onto the heap. And we all know that heap allocation is normally
more expensive than stack allocation (because it usually involves a
function call to the allocation routine, and because it causes more cache
misses).

Bruno

Bruno Haible

unread,
Dec 4, 1997, 3:00:00 AM12/4/97
to

Jon Buller <bul...@nortel.com> wrote about tail recursion elimination:

>
> Um... The simple cases have been done in GCC for a long time. The
> simple tail recursive factorial, and it's for loop companion have
> produced nearly identical code for at least two or three years.

The simple cases, yes. The simple tail recursive factorial with return
type `int' is transformed into a loop, but as soon as you change the
return type into a `struct' of three ints, GCC can't perform the
optimization any more.

This shows why it is bad to _rely_ on tail recursion elimination in
a system which implements it only partially: Subtle differences in the
code, the compiler or the compilation options make the recursion pop up
again. You won't notice that during testing, but in production use the
program will abort due to stack overflow. (Because testing data is always
smaller than real-world data.)

Bruno

Jon Buller

unread,
Dec 4, 1997, 3:00:00 AM12/4/97
to

Rolf-Thomas Happe wrote:
>
> In article <664eob$m...@george.sabre.com> cbbr...@news.amrcorp.com
> (Christopher Browne) writes:
> I thought that GCC knew about tail recursion elimination. At least,
>
> What gcc does is (I believe) tail *self* call merging, not general
> tail call merging resp. full blown tail recursion optimisation.

Well, that appears to be correct. Using the simple definitions of

int isodd (int x) {
if (x == 0) return 0;
return !iseven (x - 1);
}
int iseven (int x) {
if (x == 0) return 1;
return !isodd (x - 1);
}

GCC spits out:

.globl _isodd
.type _isodd,@function
_isodd:
enter [],0
movd 8(fp),r0
cmpqd 0,r0
beq L2
addr -1(r0),tos
bsr _iseven
cmpqd 0,tos
cmpqd 0,r0
seqd r0
br L3
.align 2,0xa2
L2:
movqd 0,r0
L3:
exit []
ret 0

And correspondingly similar code for iseven. In particular, GCC could
have done something like the following:

_isodd:
enter
moved
_oddtail:
cmpqd
beq
addr
bsr _eventail
...

However, that would require it to basically compile both functions as
halves of a single function, so it could get the registers and
everything
else right. It would be nice if it could do it, but I doubt C code does
that very often. (Unless it's Scheme->C output 8-) For a language like
C,
it pretty much requires global interprocedural analysis and
optomization.
You'd get other wins from doing that, but it's a lot of work, and GCC is
already pretty slow sometimes.

Too bad C doesn't have semantics more like Scheme's so it could be more
intelligent in matters like this without so much effort.

Jon Buller

Juergen Nickelsen

unread,
Dec 6, 1997, 3:00:00 AM12/6/97
to

Rainer Joswig <jos...@lavielle.com> wrote:

> > Which of the major CL implementations do not optimize tail-recursion?
>
> Symbolics CL.

Which else? I'd like to see some kind of representative number (assuming
Symbolics CL ist not the only one).

--
Juergen Nickelsen

Georg Bauer

unread,
Dec 6, 1997, 3:00:00 AM12/6/97
to

Juergen Nickelsen <jnick...@acm.org> wrote:

> Which else? I'd like to see some kind of representative number (assuming
> Symbolics CL ist not the only one).

Since tail-recursion-elimination is nowadays so common that even some
C-compilers do optimize it, I wouldn't think you will find many Common
Lisp implementations that don't support it. At least not the modern and
supported one.

bye, Georg

mi...@orsi.com

unread,
Dec 8, 1997, 3:00:00 AM12/8/97
to

In article <30900811...@naggum.no> wrote:
> as a matter of user interface design, I think it would make sense to
> indicate that a value was rejected and to use another prompt for repeats:
>
> (defun filtered-input (predicate prompt repeat-prompt)
> (loop initially (format *query-io* prompt)
> for local-input = (read *query-io*)
> until (funcall predicate local-input)
> do (format *query-io* repeat-prompt)
> finally (return local-input)))
>
> #\Erik

I thought this was a nice touch and included it in my code:

(defun filtered-input (predicate &key (prompt "Enter your data:") (rpp
"Try again:") (stream

*query-io*)) "Obtains input from user repeatedly until user enters
input that passes predicate. Note Strings MUST be enclosed in quotes -
thus this is not the best way to obtain a string from a user" (labels
((local-input (prompt) (format t prompt) (read))) (do ((j (local-input
prompt) (local-input rpp))) ((funcall predicate j) j))))

1. I thought your example was more direct than mine - I wonder if the
labels command makes this code undesireable in any way? The code feels
nicer to me since the do loop no longer has that repetition.

2. If the initialization of a variable and the update use the same body
of code, (do ((j #1=<whatever> #1#)...) can be used to run the loop. Is
there a nicer way to write this?

Barry Margolin

unread,
Dec 9, 1997, 3:00:00 AM12/9/97
to

In article <881615341....@dejanews.com>, <mi...@orsi.com> wrote:
>(defun filtered-input (predicate &key (prompt "Enter your data:") (rpp
>"Try again:") (stream
>
> *query-io*)) "Obtains input from user repeatedly until user enters
>input that passes predicate. Note Strings MUST be enclosed in quotes -
>thus this is not the best way to obtain a string from a user" (labels
>((local-input (prompt) (format t prompt) (read))) (do ((j (local-input
>prompt) (local-input rpp))) ((funcall predicate j) j))))

I assume filling the code was inadvertent, and you don't normally write
Lisp this way....

>1. I thought your example was more direct than mine - I wonder if the
>labels command makes this code undesireable in any way? The code feels
>nicer to me since the do loop no longer has that repetition.

The local function seems fine to me, although I would use FLET rather than
LABELS because the function isn't recursive.

>2. If the initialization of a variable and the update use the same body
>of code, (do ((j #1=<whatever> #1#)...) can be used to run the loop. Is
>there a nicer way to write this?

Unfortunately, no. That's one of the things that often got me to use LOOP
rather than DO.

However, if the end-test doesn't use J, you can move the assignment into
the body, e.g.

(do (j <other var-specs>)
(<end test> <result forms>)
(setq j <whatever>)
...)

--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.

Michael Tuchman

unread,
Dec 9, 1997, 3:00:00 AM12/9/97
to

Barry Margolin <bar...@bbnplanet.com> wrote:

>In article <881615341....@dejanews.com>, <mi...@orsi.com> wrote:
>>(defun filtered-input (predicate &key (prompt "Enter your data:") (rpp
>>"Try again:") (stream
>>
>> *query-io*)) "Obtains input from user repeatedly until user enters
>>input that passes predicate. Note Strings MUST be enclosed in quotes -
>>thus this is not the best way to obtain a string from a user" (labels
>>((local-input (prompt) (format t prompt) (read))) (do ((j (local-input
>>prompt) (local-input rpp))) ((funcall predicate j) j))))
>
>I assume filling the code was inadvertent, and you don't normally write
>Lisp this way....

I wonder how that happened - you are correct - I do not usually write
LISP that way. From now on, I'll make sure to write from my usual
newsreader.


>
>>1. I thought your example was more direct than mine - I wonder if the
>>labels command makes this code undesireable in any way? The code feels
>>nicer to me since the do loop no longer has that repetition.
>
>The local function seems fine to me, although I would use FLET rather than
>LABELS because the function isn't recursive.
>
>>2. If the initialization of a variable and the update use the same body
>>of code, (do ((j #1=<whatever> #1#)...) can be used to run the loop. Is
>>there a nicer way to write this?
>
>Unfortunately, no. That's one of the things that often got me to use LOOP
>rather than DO.
>

I will do my best to avoid getting into a loop vs. do flamewar :-)

>However, if the end-test doesn't use J, you can move the assignment into
>the body, e.g.
>
>(do (j <other var-specs>)
> (<end test> <result forms>)
> (setq j <whatever>)
> ...)
>
>--

Thanks for the hints! I think I like this form a little better.

Ingvar Mattsson

unread,
Dec 10, 1997, 3:00:00 AM12/10/97
to

cbbr...@news.amrcorp.com (Christopher Browne) writes:

>
> On 3 Dec 1997 19:30:03 GMT, Bruno Haible <hai...@ilog.fr> wrote:
> >*Any* language? I invite you to go out and implement tail recursion
> >elimination for GNU C. Not that it would be unfeasible, but you wouldn't
> >be done with it in a year.
>

> I thought that GCC knew about tail recursion elimination. At least,

> the last time the "recursion is evil, complex, and stupid" came up,
> someone posted code generated by GCC that at least *appeared* to
> indicate that:
>
> a) Using a tail recursive algorithm makes some algorithms read better,
> whether in LISP, Scheme, or even C, and
>
> b) Some C compilers are intelligent enough to recognize and optimize
> out tail recursion.

A quick test of a factorial function, compiled with gcc v2.7.2.1,
indicates *very* clearly that it does, indeed, perform something very
similar to tail recursion. C code and assembler can be posted on request.

> I could be wrong about the latter...

//Ingvar
--
Sysadmin, disgruntled, unpolite.
I don't speak for my employer nor do they speak for me.
Accept this and life will be easier. ing...@idasys.se

0 new messages