[comp.lang.c] Ackermann's Function

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.)