in Compiler Design edited by
12,644 views
43 votes
43 votes

The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions.

global int i=100, j=5;
void P(x) {
	int i=10;
    print(x+10);
    i=200;
    j=20;
    print (x);
}
main() {P(i+j);}

If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are

  1. $115, 220$
  2. $25, 220$
  3. $25, 15$
  4. $115, 105$
in Compiler Design edited by
12.6k views

4 Comments

0
0
The programming language and its rules for global variables, nested function declarations, dynamic scoping, and call by name parameter passing must be known. Additionally, the program must be executed in order to determine the values printed, dynamic scoping and call by name parameter passing can lead to unpredictable behavior and are not commonly used in modern programming languages. It is generally recommended to use lexical scoping and call by value or call by reference parameter passing instead. Global variables can be accessed and modified by any function in the program, and the specific behavior of a function may depend on the values of global variables at the time the function is called. In a language that uses dynamic scoping and call by name parameter passing, the values of the local and global variables at the time of a function call may affect the behavior of the function. Additionally, the specific behavior of the parameter passing mechanism may affect how the values of the parameters are used in the function.
0
0

@samir757 here we will use rename concept so your answer is not correct but i am not able to understand best answer anyone please help me?

0
0

5 Answers

48 votes
48 votes
Best answer

Answer: No Option is correct.

The answer to this question can be found in Example $6$ below. 


The "Call by name" parameter passing technique is used by imperative languages like Algol $W,$ and is used by several functional languages like Haskell. 

We'll see how the "Call by name"  parameter passing technique works (theoretical idea for understanding its working), Not how it is actually implemented(practical implementation). 

How "Call by name" works (Idea of this technique):

In general, the effect of pass-by-name is to textually substitute the argument expressions(actual parameters) in a procedure call for the corresponding parameters(formal parameters) in the body of the called procedure.*

i.e. Direct Substitution of actual parameters in the place of the formal parameter in the called procedure.*

(* means that it is not a complete definition/statement and some technical details are missing and as we go on, we'll fill in these details.) 

Example 1: What will be the output if the "Call by name"  parameter passing technique is used. 

Given Program : 

void P(x) {
    print(x+10);
    print (x);
}
main()
{
    int j = 10; 
    P(j);
}

Answer: Since the "Call by name"  parameter passing technique is used, we can re-write the program as follows:

void P(x) {
    print(j+10);
    print (j);
}
main()
{
    int j = 10; 
    P(j);
}

Hence, output $: 20,10$

NOTE 1 (Technical Detail 1) : It does Not matter which Scoping is used(static or dynamic),
once we substitute actual arguments in the place of formal parameters in the called function,
for those variables in the actual arguments, environment of caller function will be applicable. 

Hence, in the above example $1,$ in function $P, j$ refers to the $j$ of the caller function i.e. main function. 

Example $2$ will illustrate Note $1.$ 

Example 2:  What will be the output if the "Call by name"  parameter passing technique is used in the case of static and dynamic scoping?

global int j=100;
void P(x) {
    print(x+10);
    print (x);
}
main()
{
    int j = 10; 
    P(j);
}

Answer: Since the "Call by name"  parameter passing technique is used, we can re-write the program as follows:

global int j=100;
void P(x) {
    print(j+10);
    print (j);
}
main()
{
    int j = 10; 
    P(j);
}
  • In case of Dynamic scoping $:  20,10 $
  • In case of Static scoping $:  20,10 $

Note that in the case of Static scoping, $j$ in function $P$ does not refer to the global variable But $j$ refers to the caller function, more precisely, Once we substitute Actual arguments in the place of formal parameters in the called function, for those variables in the actual arguments, Environment of caller function will be applicable. Hence, $j$ in $P$ will be accessed/updated according to caller function's environment, and since, caller function i.e. main function here, has a local variable $j$, so, this $j$ will be accessed/updated by the function $P.$ 

Example 3:  What will be the output if the "Call by name"  parameter passing technique is used in the case of static and dynamic scoping?

global int j=100;
void P(x) {
    print(x+10);
    print (x);
}
main()
{
    P(j);
}

Answer: Since the "Call by name"  parameter passing technique is used, we can re-write the program as follows:

global int j=100;
void P(x) {
    print(j+10);
    print (j);
}
main()
{
    P(j);
}
  • In case of Dynamic scoping $:  110,100 $
  • In case of Static scoping $:  110,100$

Again, once we substitute actual arguments in the place of formal parameters in the called function, for those variables in the actual arguments, environment of caller function will be applicable. Hence, $j$ in $P$ will be accessed/updated according to the caller function's environment and since, caller function i.e., main function here, does not have a local variable $j$, environment of function main for variable $j$ would depend on the scoping used, But this scoping will be seen from the perspective of caller function i.e. function main, not from the perspective of called function i.e. function P. So, it is like accessing variable $j$ in the main function, not in $P$ function. Hence, for this example $3,$ in both scoping, the main function will be using Global variable $j.$

Example 4:  What will be the output if "Call by name"  parameter passing technique is used in the case of static and dynamic scopings?

global int j = 100, i = 300;

void Q(x) { 
    print(x+10); 
    print (x); } 

void P(x) {
    print(x+10);
    Q(i);
    print (x);
}
main()
{
    int i = 500;
    int j = 10;
    P(j);
}

Answer: Since "Call by name"  parameter passing technique is used, we can re-write the program as follows:

global int j = 100, i = 300;

void Q(x) { 
    print(i+10);  // this i refers to i in the caller function i.e. P function's environment
    print (i); } // this i refers to i in the caller function i.e. P function's environment

void P(x) {
    print(j+10);  // this j refers to j in the caller function i.e. main function's environment
    Q(i);
    print (j);    // this j refers to j in the caller function i.e. main function's environment
}
main()
{
    int i = 500;  
    int j = 10;
    P(j);
}
  • In case of Dynamic scoping $:  20,510,500,10$
  • In case of Static scoping $:  20,310,300,10$

In Static scoping, variable $i$ in $P$ function's environment refers to the global variable $i$. In Dynamic scoping, variable $i$ in $P$ function's environment refers to the main function's $i.$  


NOTE 2 (Technical Detail 2) :
if any of the local variables in the called procedure clash with the caller's variables, they (called function's clashing variables) must be renamed uniquely before substitution. 

Example 5: What will be the output if the "Call by name"  parameter passing technique is used?

Given Program : 

void P(x) {
    int j=100;
    print(x+10);
    print(j);
    print (x);
}
main()
{
    int j = 10; 
    P(j);
}

Answer: Since "Call by name"  parameter passing technique is used, we can re-write the program as follows:

Caller function's actual argument contains variable $j$ which clashes with called function $P$'s local variable $j,$ hence, we rename called function $P$'s local variable $j$ and change it to $j'.$

void P(x) {
    int j'=100;
    print(j+10);   // this j refers to j in the caller function i.e. main function's environment
    print(j');    // this j' refers to the local variable j' in P.
    print (j);    // this j refers to j in the caller function i.e. main function's environment
}
main()
{
    int j = 10; 
    P(j);
}

Hence, output $: 20,100, 10.$


Coming to the actual GATE question, we'll call it to example $6.$

Example 6: What will be the output if the "Call by name"  parameter passing technique is used, in the case of static and dynamic scopings?

global int i=100, j=5;
void P(x) {
	int i=10;
    print(x+10);
    i=200;
    j=20;
    print (x);
}
main() {P(i+j);}

Answer: Since the "Call by name"  parameter passing technique is used, we can re-write the program as follows:

Caller function's Actual argument contains variable $i$ which clashes with called function $P$'s local variable $i,$ hence, we rename called function $P$'s local variable $i$ and change it to $i'.$

global int i=100, j=5;
void P(x) {
	int i'=10;   // this i' refers to the local variable i' in function P.
    print(i+j+10);  // this i,j refers to i,j in the caller function i.e. main function's environment
    i'=200;    // this i' refers to the local variable i' in function P.
    j=20;      // this j refers to j in the caller function i.e. main function's environment
    print (i+j);   // this i,j refers to i,j in the caller function i.e. main function's environment
}
main() {P(i+j);}
  • In case of Static scoping $: 115, 120$
  • In case of Dynamic scoping$: 115, 120$

Note that there are no local variable $i,j$ in the main function, so, when we say that $i,j$ refer to the $i,j$ in the main's environment, we mean that If $i,j$ were accessed/updated in the main function then depending on the scoping, which $i,j$ would they refer.

Here, in this question, in both static and dynamic scoping cases, $i,j$ will refer to the Global variables. 

And in function $P$, in the $4$th statement $(\text{i.e.}\; j = 20)$, the Global variable $j$ will be updated.

Hence, No Option is correct for the actual above GATE question. 


Example 7: What will be the output if the "Call by name"  parameter passing technique is used in the case of static and dynamic scopings?

global int j = 100, i = 300;

void Q(x) { 
    print(x+10); 
    print (x); } 

void P(x) {
    int i = 400;
    int j = 600;
    print(x+10);
    Q(i);
    Q(j);
    print (x);
}
main()
{
    int i =500;
    Q(i);
    int j =10;
    P(j);
}

Answer : 

in both scoping, for this question, output $: 510,500,20,410,400,610,600,10.$

Note that When main calls $P(j)$, then Caller function main's Actual argument contains variable $j$ which clashes with called function $P$'s local variable $j,$ hence, we rename called function $P$'s local variable $j$ and change it to $j'.$ So, in function P, the 5th statement becomes $Q(j').$

Also note that when main calls $Q(i)$, then $x$ in $Q$ is replaced with $i.$ When $P$ calls $Q(i),$ then $x$ in $Q$ is replaced with $i.$ When $P$ calls $Q(j')$, then $x$ in $Q$ is replaced with $j'.$ 


Note that "Direct Substitution of actual parameters in the place of the formal parameter in the called procedure" is only the Idea of Call-by-name, Not the actual practical implementation. The compiler does Not do Direct Substitution blindly. Pass-by-name is difficult to implement. Argument expressions must be compiled to special parameter-less procedures called thunks. These thunks are passed into the called procedure and used whenever necessary to evaluate or re-evaluate the argument.

But we do not need to go into practical implementation details because the Idea remains the same. Hence, we can solve all the questions using the above idea of call-by-name. 


NOTE 3 (Technical Detail 3) :
if any of the variables in the called procedure clash with the caller's variables, they(called function's clashing variables) must be renamed uniquely before substitution. 

Clashing variables need not be local variables of the called function. 

But remember that when we rename a variable, we don't really rename it. We rename it just to eliminate the possibility of confusion. So, when we rename $j $ to $j'$, we must not forget that $j'$ is actually $j$ only in the first place. 

The following example will illustrate this point : 

Example 8: What will be the output if the "Call by name"  parameter passing technique is used in the case of static and dynamic scoping?

global int j=100, i = 300;

void Q(x) { 
    print(i);   
    print(j);
    print(x+10); 
    print (x); } 

void P(x) {
    int i = 400;
    int j = 600;
    print(x+10);
    Q(i);
    Q(j);
    print (x);
}
main()
{
    int i =500;
    int j =10;
    Q(i);
    P(j);
}

Answer : 

  • In case of Static scoping $: 300, 100, 510, 500, 20, 300, 100, 410, 400, 300, 100, 610, 600, 10$
  • In case of Dynamic scoping $: 500, 10, 510, 500, 20, 400, 600, 410, 400, 400, 600, 610, 600, 10$
global int j = 100, i = 300;

void Q(x) { 
    print(i); // this i refers to the Global i in case of static scoping and in case of dynamic scoping, according to the calling function in the stack.
    print(j); // this j refers to the Global j in case of static scoping and in case of dynamic scoping, according to the calling function in the stack.
    print(x+10);  // variables that are substituted here, refer to the corresponding variables in the caller function's environment
    print (x); } // variables that are substituted here, refer to the corresponding variables in the caller function's environment

void P(x) {
    int i = 400;
    int j = 600;
    print(x+10); // variables that are substituted here, refer to the corresponding variables in the caller function's environment
    Q(i);
    Q(j);
    print (x); // variables that are substituted here, refer to the corresponding variables in the caller function's environment
}
main()
{
    int i =500;
    int j =10;
    Q(i);
    P(j);
}

When main calls $Q(i) ,$ we substitute $i$ in place of $x$ and it(Q) becomes:

void Q(x) {
    print(i′);  // This is renamed as i′ and it refers to 
                //global variable i in case of static scoping and 
                //in case of dynamic scoping it refers to 
                //variable i in main function.
    print(j);  
    print(i+10);  
    print (i);  
}

Hence, the two different $i's$ should be distinguished properly. 


edited by

4 Comments

Mindblowing,Superb explantion..

@Deepak Poonia Sir..

1
1
Sir why we rename the identifiers as i and i’ when we implemented the call by name parameter passing technique in example 6?? Shouldn’t they be the same??
0
0

@Deepak Poonia Sir, based on NOTE 3 (Technical Detail 3), along with renaming local variable \(i\) in the procedure \(P(x)\) of example 6 (the actual GATE question), shouldn’t variable \(j\) in \(P(x)\) also be renamed to \(j’\), as it clashes with the caller’s/main’s argument variable \(j\)? In case static scoping is used, \(j’\) refers to the global variable \(j\), and in case dynamic scoping is used, \(j’\) refers to the definition of \(j\) in the main’s environment. But, since main doesn’t have a definition of \(j\), we search for \(j\) in the next higher enclosing scope, i.e., the global scope. Thus, ultimately the answer remains the same, bar the technical nuance, right?

0
0
46 votes
46 votes
global int i=100, j=5; // memory created 
//for i and j variable and 100 and 5 store in them respectively (1)

void P(x) { // p(i+j) (3)
//dynamic scoping means when a variable is not found locally, 
//it refers to the caller function for it 

    int i=10; // new variable created i with value 10 store in it. (4)

    print(x+10); // print(x+10); = print(i+j +10);= 10 +5 +10 = 25 (5)

    i=200; // local i and global j value changed to 200 and 20 respectively  (6)

    j=20;
    print (x); // print (x);= print (i +j); = 200 +20 = 220 (7)
}
main() {P(i+j);}  // 1st function call 
//since it is call by name dont calculate value just send i+j  
//Since there are no local i and j, they refer to the global variables (2) 

Answer is (B).

Refer: http://stackoverflow.com/questions/838079/what-is-pass-by-name-and-how-does-it-work-exactly

edited by

4 Comments

@Arjun sir

the function will use local variable i sure?

0
0
Such a nice explanation all at one place. Thank you sir.
0
0
nice one prashant. well expalined
0
0
4 votes
4 votes

Answer will be B dynamic scope and call by name is used so first print will be evaluated as

            print(10+5+10)

and 2nd print will be evaluated as

           print(200+20)

by

1 comment

Can you please explain the same with static scoping and call by name
0
0
4 votes
4 votes

In Gate official keys the answer for this question is given as the option (A) and for the previous one it is (D) and that is the correct solution.

Call-by-Name: Here the expression is evaluated every time it is requested, no cache is stored.  

Call-by-Need: Here the expression is evaluated only once and it is stored for further reference, no cache is stored.  

In static scoping, the local variables have more preference than global variables if the name of both the variables is same. In dynamic scoping, the global variables are preferred over local variables. 

Now let us look at the program.

Static scoping and Call-by-need

global int i=100, j=5;
void P(x) {
	int i=10; // Local variable declared and initialized to value 10
    print(x+10); //Requested the evaluation of the expression, but the expression uses global i not local i so x + 10 = i + j +10 = 105 +10 =115 
    i=200; // Local i assigned to 200 as static scoping prefers local variable
    j=20; // No confusion here, the global value is changed to 20
    print (x); // Here again as it is Call-by-Need and is only evaluated once so this will print 105 as x is 105
}
main() {P(i+j);} // Here the expression i+j is passed but it is not evaluated yet.

Here in static scoping the local variable is preferred over global but that does not mean that in print(x) line, i is local variable but it is the global one as the expression is evaluated from the scope of the main() function from which it was called.
So the answer is (D)


Dynamic scoping and Call-by-name

global int i=100, j=5;
void P(x) {
	int i=10; // Local variable declared and initialized to value 10
    print(x+10); //Requested the evaluation of the expression, but the expression uses global i not local i so x + 10 = i + j +10 = 105 +10 =115 
    i=200; // Here is the difference where assignment of is done on the global one not the local one
    j=20;// Here global value is changed.
    print (x); // Now again expression is requested as it is call by name and now as the global values have changed so the answer is 200 + 20 = 220 
}
main() {P(i+j);} // Here the expression i+j is passed but it is not evaluated yet.

(A) is the answer

1 comment

FYI: There were no official keys before GATE 2011. And the explanation given is wrong --  The terms global and local alone are not enough while explaining static/dynamic scoping.
7
7
Answer:

Related questions