call by name : how are clashing variables handled?

In call by name : In general, the effect of pass-by-name is to textually substitute the argument expressions in a procedure call for the corresponding parameters in the body of the procedure.

Technically, if any of the variables in the called procedure clash with the caller's variables, they must be renamed uniquely before substitution.

Now consider the following code :

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);
}


Will the variable i declared in function P get renamed before execution ? Which i ( global or local ) is accessed by x in print(x + 10) ? Which i ( global or local ) will get updated by (i = 200) ? What will be the output of the second print statement (220 or 120 ) ?

• Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. – Discrete lizard Jan 28 '18 at 16:36
• @Discretelizard, the question is OK, what are you complaining about? – Andrej Bauer Jan 28 '18 at 22:29
• @AndrejBauer It looked like a 'problem dump' to me, as questions are asked for which no attempt at interpretation or solution is given, but I may be mistaken. – Discrete lizard Jan 28 '18 at 22:43

Programming languages do not "textually substitute" anything, that would be horribly inefficient. The "textual substitution" definition may be offered sometimes as a sort of textbook explanation, but it usually fails to capture all the details.

There are many techniques for dealing with the problem you describe. By the way, the problem is known as "variable capture" beacuse a binder "captures" a variable.

One possiblity is to eliminate all variable names and use de Bruijn indices instead. Substitution still requires a bit of work, namely shifting of indices, but at least one does not have to generate new names.

Another possibility is to create closures. These are used for evaluation of functions (I did not say "application"!), but in a call-by-name language we could use them for any expression. Briefly, when we evaluate P(i + j) in your code, we create a closure (η, i + j) where η tells us what the values of variables are at that point in the execution (so concretely, η would be something like i ↦ 100, j ↦ 50, P ↦ ..., main ↦ ....). When P actually needs the value of its argument, we evaluate i + j in the environment η (and not in the environment of P), so that i + j gets evaluated in the "old" environment.

There are still many other techniques for avoiding variable capture. Haskell compiles to a spineless tagless G-machine, or at least it used to.

As far as I know, call-by-name generally assumes hygienic calls, where no name leaks out of its scope. The simple way of implementing that is to α-convert the program: rename each bound variable to a newly-created unique name at compile time. Once all names are made unique, hygiene is automatic. A theoretical approach which abstracts away implementation details is de Bruijn indexing; a common pragmatic approach is to "rename" variables to their stack frame offsets (bearing in mind that the appropriate stack frame must also be identified).

Macro processors like the C preprocessor do unhygienic substitution, since they work by strict textual substitution. That is sometimes called call-by-name but most terms for it are less polite. I don't believe there is any theoretical model which avoids α-conversion in this way.

Assuming hygienic substitution (α-conversion), then:

Will the variable i declared in function P get renamed before execution?

Yes, at compile time.

Which i ( global or local ) is accessed by x in print(x + 10) ?

The global one.

Which i ( global or local ) will get updated by (i = 200) ?

The local one.

What will be the output of the second print statement (220 or 120 ) ?

120

Call by name has widely gone out of fashion. I have seen it in Algol 60, can't remember if it was in Algol 68, and I thought I hadn't seen it since, although the technology needed is in common use now again with closures etc. , and auto closures in Swift are actually the same as call by value parameters.

You wouldn't do this by name substitution. You would do this in your example by creating a chunk of code that adds the global int i and the global int j, and passing that code to P, where it can be executed whenever needed.