firth@sei.cmu.edu (Robert Firth) (02/03/88)
[NOTE: please forgive me if you get multiple copies of this: the mailer here is behaving in a most bizarre fashion ] In article <3995@hoptoad.uucp> gnu@hoptoad.uucp (John Gilmore) writes: [Ackermann's Function] >A(x,y) >int x,y; >{ > if(x==0) return(++y); > if(y==0) return(A(--x,1)); > return(A(--x,A(x,--y))); > } If tests are to be of any use, they surely should be programmed correctly. Brian Wichmann has collected over a thousand examples of Ackermann's function, and they are all based on his original paper [Wichmann: How to Call procedures..., Software, vol 7 pp 317-329 (1977)]. The original Algol code is: integer procedure Ackermann(m,n); value m,n; integer m,n; Ackermann := if m=0 then n+1 else if n=0 then Ackermann(m-1,1) else Ackermann(m-1, Ackermann(m,n-1)); The proper C translation is: A(m,n) int m,n; { return m==0 ? n+1 : n==0 ? A(m-1,n) : A(m-1,A(m,n-1)); } This is a better form since it preserves the conditional expression of the original. Note also that there is absolutely NO warrant whatever for changing the code so that the formal parameters are modified: this feature of the quoted C code is simply wrong - presumably an error perpetrated by a programmer who thought "++x" meant "x+1". Arguing about a side effect that shouldn't even be there is a pretty pointless exercise, so I won't.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/08/88)
In article <4034@aw.sei.cmu.edu> firth@sei.cmu.edu (Robert Firth) writes: >The proper C translation is: ... Actually, I liked John Gilmore's better! >Arguing about a side effect that shouldn't even be there is a pretty >pointless exercise, so I won't. The issue is not tied to Ackermann's function, but is a more general question about order of evaluation. (My guess, since I don't have the draft proposed standard at hand, is that Stallman is right -- it is not until the inner A() is evaluated that issues of interleaving of ITS arguments are relevant; whether or not the outer A()'s other argument is evaluated before or after this is implementation-dependent. I do recall that the wording about sequence points changed somewhat since the old draft, so it may be clearer in the current one.)