Tuesday, April 30, 2013

Parameter Passing I

Parameter passing is a remarkably complex subject for something that appears so simple on the surface. First there is the terminology. When you call a function as in f(x+1,5), you pass arguments or actual parameters. When you define a function, as in

function f(x,y) return x+y; end

the names x and y are called formal parameters or sometimes just parameters when ambiguity is not a problem. So

argument = actual parameter = expressions you see at the function call
parameter = formal parameter = names you see at the function definition

Usually I will use “argument” and “parameter” unless it is especially important to avoid ambiguity and then I will use “actual parameter” and “formal parameter”.

So with that terminology under our belt, let’s see what’s so hard about parameter passing. Suppose you have a definition of a function

function f(x,y)
 var i;
 i := x+x;
 return i+y;

and you have a call of that function f(3,4). What could be more simple than to substitute 3 in place of each x and 4 in place of the y to get

i := 3+3
return i+4;

which returns 10. How can that be complicated?

Well, let’s start with that 3. What if instead of 3, we declare another variable i and the function call is

i := 3;

The ++ operation is from C. It first increments i and then returns its value. Now if we follow the proposed substitution, we get the first line of the function as

i := ++i+++i;

The intention is that this should be parsed as (++i) + (++i) but if we are using pass-by-text (which is the method used by the C preprocessor) then we might instead parse it as ((++i)++)+i because ++ can be a suffix operator as well as a prefix operator.

But let’s assume that we don’t have pass-by-text, instead we have pass-by-phrase. A phrase is a parsed syntactic unit. You can think of it as an abstract syntax tree. With prhases the parsing is done before the call so we don’t have to worry about weird parsing interactions. This is similar to the parameter-passing method used in the macros of Common Lisp. With this mechanism, the parsing would be correct and the function body, after substituting parameters is

var i;
i := (++i) + (++i);
return i+4;

But this bit of code is declaring i as a new variable then calling ++i before assigning to the variable. That’s a reference to an undefined variable. What happened to the 3 that was assigned to i before the call? That assignment doesn’t count in the function body because i in the function body is a different variable than it was at the point of the call.

OK, what we need is something like a phrase but where the names have already been bound so they can’t be captured by the declarations in the function body. What we need is a thunk. A thunk can be thought of as a bit of compiled code along with some sort of namespace, but in abstract it is a phrase where the variables are already bound and cannot be captured in another context.

Several languages starting with Algol 68 have had a pass-by-thunk parameter passing mechanism, although most of them called it pass-by-name. I prefer “pass-by-thunk” because “pass-by-name” doesn’t make any sense.

So let’s take a look at what would happen with pass-by-thunk. The arguments would be converted into thunks which means into something like a function call with no arguments:

function thunk1() return ++i; end
function thunk2() return 4; end

except that i in thunk1 is an alias for the i at the calling point. Now the body of the function would be something like

var i;
i := thunk1() + thunk1()
return i+thunk2();.

This body evaluates thunk1() twice, which increments i twice so the result is 4+5+4=13. But surely what we really expected f(++i,4) to do is increment i once and return 4+4+4=12, so we aren’t done yet.

The problem seems to be that the thunk evaluated ++i twice. What if we defined the thunk to only evaluated it once? This is pass-by-lazy-thunk because the thunk is only evaluated when it’s need and then only once. We define it like this:

function lazythunk1()
 static var tmp := ++i;
 return i;

What this function does is execute ++i the first time it is called, but after that it just keeps returning i. This solution gives us the answer we want. It increments i once and returns 4+4+4=12.

But we aren’t done yet. Let’s try out another function

function g(x,y)
 if y < 0 then return x;
 else return y;

and lets call this function with the same arguments g(++i,4). Using the lazy thunk, this will produce the following body

if y < 0 then return lazythunk1();
else return lazythunk2();

In this code y is greater than 0 so lazythunk1() never gets evaluated and i is never incremented. But surely when the user wrote g(++i,4) he expected that after this call i would be greater by one.

So here’s another try. Let’s avoid all of this confusion by just saying that we will evaluate the arguments at the point of the call and pass to the function the results of that evaluation. The formal parameters of the function, then would not become names for the argument expressions of the function; they would become names for whatever those expressions evaluate to. This seems to handle both of the problem cases above. In both cases, the ++i gets evaluated once at the point of the function call and x gets bound to 4, the value returned by the expression. But now consider

function h(x,y)
 x := x+1;
 return x+y;

When the function is called as h(i,4), what will happen? Well, if x becomes a name for the result of the expression i, this is ambiguous. Since i is a variable it denotes a location rather than a value. So we could say either that i evaluates to a location or that it evaluates to the contents of the location. The issue is whether the evaluation that we do on the parameter stops before or after dereferenicng. If the evaluation stops before dereferencing, then the formal parameter x becomes an alias for the location denoted by the actual parameter i. This is called pass-by-reference or pass-by-var.

If we use pass-by-reference, we have a problem again. When the user calls h(i,4) the formal parameter x becomes an alias for the actual parameter i so when x is incremented by 1, so is i. But the user is not going to expect i to be modified when he calls f(i,4).

The final alternative is to say that the evaluation of the arguments goes all the way through to dereferencing any reference results so that the formal parameters get bound to value only. This is called pass-by-value and it turns out to give the expected semantics.

Since Unobtainabol wants to give users the expected results, should it just use pass-by-value? The problem with that is that pass-by-value is not powerful enough. Pass-by-value is great for calling a function that takes a set of argument values and manipulates them in some way, but sometimes you want something more powerful.

I'll discuss that in a future post.

No comments:

Post a Comment