Call by Need and Standard C Output?

Question

The following code is here with keep the C Language Syntax:

#include <stdio.h>
int func(int a, int b){
if (b==0)
return 0;
else return func(a,b);
}

int main(){
printf("%d \n", func(func(1,1),func(0,0)));
return 0;
}

What is the output of this code at 1) run with standard C, 2) with any language that has call by need property, Then:

in (1) the programs loop into infinite call and in (2) we have ouptut zero !! this is an example solved by TA in programming language course, any idea to describe it for me? thanks

Answer 1

1) In C (which uses strict evaluation semantics) we get infinite recursion because in strict evaluation arguments are evaluated before a function is called. So in f(f(1,1), f(0,0)) f(1,1) and f(0,0) are evaluated before the outer f (which one of the two arguments is evaluated first is unspecified in C, but that does not matter). And since f(1,1) causes infinite recursion, we get infinite recursion.

2) In a language using non-strict evaluation (be it call-by-name or call-by-need) arguments are substituted into the function body unevaluated and are only evaluated when and if they're needed. So the outer call to f is evaluated first as such:

if (f(0, 0) == 0)
return 0;
else return f(f(1,1), f(0,0));

So when evaluating the if, we need to evaluate f(0,0), which simply evaluates to 0. So we go into the then-branch of the if and never execute the else-branch. Since all calls to f are only used in the else-branch, they're never needed and thus never evaluated. So there's no recursion, infinite or otherwise, and we just get 0.

Answer 2

To address the first part,

The C Draft, 6.5.2.2->10(Function calls) says

The order of evaluation of ... the actual arguments... is unspecified.

and for such reason, something such as

printf("%d%d",i++,++i); 

has undefined behaviour, because

• both ++i and i++ has side-effects, ie incrementing the value of i by one.
• The comma inside printf is just a separator and NOT a [ sequence point ].
• Even though function call itself is a sequence point, for the above reason, the order in which two modifications of i take place is not defined.

In your case

func(func(1,1),func(0,0))

though, the arguments for outer func ie func(1,1) or func(0,0) have no bearing on each other contrary to the case shown above. Any order of evaluation of these arguments eventually leads to infinite recursion and so the program crashes due to depleted memory.

Answer 3

With C, in general, it is not defined the order of arguments a and b evaluation with a function like int func(int a, int b)

Obviously evaluating func(1,1) is problematic and the code suffers from that regardless if func(1,1) is evaluated before/after/simultaneous with func(0,0)

---

Analysis of func(a,b) based on need may conclude that if b==0, no need to call func() and then replace with 0.

printf("%d \n", func(func(1,1),func(0,0)));
// functionally then becomes
printf("%d \n", func(func(1,1),0));

Applied again and

// functionally then becomes
printf("%d \n", 0);

Of course this conclusion is not certain as the analysis of b != 0 and else return func(a,b); leads to infinite recursion. Such code may have a useful desired side-effect (e.g. stack-overflow and system reset.) So the analysis may need to be conservative and not assume func(1,1) will ever return and not optimize out the call even if it optimized out the func(0,0) call.

---