webber@porthos.rutgers.edu (Bob Webber) (06/25/88)
In article <3347@tekchips.TEK.COM>, stevev@tekchips.TEK.COM (Steve Vegdahl) writes: > In article <Jun.22.22.48.57.1988.7380@aramis.rutgers.edu>, webber@aramis.rutgers.edu (Bob Webber) writes: > > In article <3061@rpp386.UUCP>, jfh@rpp386.UUCP (John F. Haugh II) writes: > > > ... [collapsed to the following for reference] > > > strlen (s) char *s; { return (*s) ? strlen(s+1) + 1 : 0; } > > > ... > > > not such a smart move. always consider the cost of your algorithm. > > > > A perfectly fine algorithm. Any decent compiler would remove the tail > > recursion. > > Unfortunately, the above program is not tail-recursive. The result of the > recursive "strlen" call is incremented before its value is returned. It > would take a pretty sophisticated compiler to transform this into an > iteration. Among other things, it would probably have to use the > associativity of "+". Over 10 years ago this stuff was being done on lisp compilers. The first step is the generation of a ``helping variable'' creating strlen2(s,n) char *s; int n; { return (*s) ? strlen2(s,1+n) : n ; } which is then recognized to be tail recursive. And yes, you are right that this presumes associativity of "+". While in general, ``plus'' even for integers is not associative, since this situation is also monotone increasing, it all works out. Note the special case of monotone integer arithmetic is actually very common due to the number of things that can be thought of as sequences to be manipulated in order. > BTW, does a typical C compiler perform tail-call optimization. On your home micro? Not likely. A modern major production C compiler I would expect to. The technology has been in the literature for at least 10 years and this is definitely the way people are encouraged to analyze problems. Of course, the original C compilers did practically no optimization assuming that you would hand massage the critical parts and the others it wasn't worth the effort (10% of the code executing 90% of the time and such) -- also, they didn't have alot of space to waste on such nicities. Now-a-days, there seems to be more of a willingness to relieve the programmer of making such trivial algorithm refinements. Being commercial products, not alot is known about the optimizations actually done by the standard compilers. However, my understanding is that the GNU CC compiler is at least as good as what the commerical people are cranking out, so to the extent that statistics of 1 case are better than statistics of 0 cases, I am cross posting this message over to gnu.gcc to see if any of the experts over there know how it would handle such code. ------ BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber) p.s., The above code was being discussed in the context of a student compiler project and I still maintain that even if it wasn't optimized, that such an implementation of strlen is not ``unreasonable.'' Most of those projects spend far more time being compiled themselves rather than compiling other things and the only real usage for such a function in a reasonably written compiler would be enforcing restrictions on the targe language material. [Note: it has already been mentioned that on a VAX, strlen can be so cheaply implemented in assembler that it can be used in lots of places where one wouldn't normally contemplate using it.]