The primary reason for using call-by-reference parameter passing is when a function's primary means of communicating with its caller is through side effects to the parameters. This is a very desirable property for certain situations (e.g., a "swap" function), but it comes with a price: aliasing. Call-by-value-result parameter passing attempts to provide the benefits of call-by-reference (side effects to passed parameters) without the drawbacks (aliasing).
The strategy is essentially a copy-in, copy-out one. When a parameter is passed, it is evaluated to get its expressed value, and a new reference (denoted value) is created to store that value--that part is just like call-by-value parameter passing. In addition, if the actual parameter is a variable, a reference to it is obtained and also stored (just like call-by-reference). During the execution of the procedure, the copy is used and any changes to the formal parameter do not change the variable passed to it. In other words, there is no aliasing. When the procedure finishes execution, just before returning control to the caller, the values in the formal parameter is copied back to the variable passed as the actual parameter. At this point, the side-effects of the procedure have effect.
So, why not always use call-by-value result if it can do what call-by-reference can do without the problems of aliasing? Well, all that coping in and out does have a price when it comes to the efficiency of the resulting program. This overhead is probably the most significant factor limiting its use.
Let's look again at one of the examples we used for call-by-reference:
let a = 3
p = proc (x)
set x = 4
in begin
(p a);
a
Notice: Uninitialized string offset: 3 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 333
end
Under call-by-value-result, a copy of the value of a (3) is created for x.
The assignment to x changes this copy, but does not change a. When the function
returns, the value of x is copied back to a. Thus, a has the value of
4 after the procedure returns--just like call-by-reference. So, in the absence of aliasing, the two techniques
produce the same results.
Suppose that we have a case where aliasing causes one value to change when another value changes:
let a = 3
in let p = proc(x)
begin
set x = +(x,1);
+(a,x)
end
in (p a)
The initial impression of this procedure is that it increments the variable passed and returns
that value plus the value of a. So, if x is 3 and a is 3,
the result should be 7, right? Under call-by-reference, x and a are aliased,
so the result is actually 8. Notice also that the variable a is incremented as a side effect.
Under call-by-value result, x and a aren't aliased during the procedure.
The assignment to x doesn't change a, so the result is 7. Upon return, the value
of x is copied back to a, so the (presumably desired) side effect still happens.
Call-by-value result does have one quirk when copying back: what if the same variable is passed to two different formal parameters?
let a = 3
p = proc (x,y)
begin
set x = 4
set y = 5
end
in begin
(p a a);
a
Notice: Uninitialized string offset: 3 in /users/home2/ta/cs330ta/public_html/cs330/inc/codeformat.php on line 333
end
What's the value of a after returning from the procedure p?
It depends, of course, on the order in which the values are copied back.
Of course, call-by-reference has similar uncertainties. Suppose the specification for
the procedure p didn't specify the exact order in which the assignments were to
take place, merely that the two parameters should be changed to 4 and 5 respectively.
Without knowing the order
in which the procedure changes the parameters, you don't know what the value of a
will be after passing it for both parameters.
As long as we’re careful about not changing scoping, we can model functions calls by a method called substitution. Calling a function is the same as executing the body of the function with all the formal parameters replaced by the actual parameters--just like in-lining a function in C++. Here's how this would work in Scheme:
(define f (lambda (x y) (+ (* x x) y))) (f 3 4)
is equivalent to
(+ (* 3 3) 4)
which simplifies further to 13.
What if we called the same function but passed expressions instead of just literals for the values:
(f (+ 1 2) (* 3 4))
We can simplify this by simplifying the operands first, then substituting:
(f 3 12)
Which substitutes to be
(+ (* 3 3) 12)
and simplifies to 21.
As an alternative, we could just replace the formal parameters with the actual parameters before simplifying them:
(+ (* (+ 1 2) (+ 1 2)) (* 3 4))
which also simplifies to 21.
Two different strategies, same answer. Is this always the case?
Can our choice of evaluation strategy lead to different results? The answer is no. This was proven by two people named Church and Rosser and is thus called the Church-Rosser Theorem. Another name for this property is confluence. The picture below shows the main idea of the Church-Rosser Theorem:
The theorem state that if we can reduce an expression E to two different expressions E1 and E2, then there is another expression N that is the reduction of both of these.
The Church-Rosser theorem does not:
The reason for both of these is that there are some expressions that never terminate. (You've probably written a few yourself.) For an example of the first consider the expression:
((lambda (x) (x x)) (lambda (x) (x x)))
This reduces to itself! Thus, applying any evaluation strategy to this expression will result in an infinite computation. That is, it will not terminate.
For an example of an expression with a different answer depending on the evaluation strategy, consider the following:
((lambda (y) 3) ((lambda (x) (x x)) (lambda (x) (x x))))
If we substitute first, the answer is 3, but if we attempt to evaluate the operand first, we get lost in an infinite computation.
Clearly, we must choose our reduction strategy carefully in spite of the Church-Rosser theorem.
Let's give these two evaluation strategies names. Evaluating the actual parameters before passing them is called applicative order evaluation. Passing the unevaluated actual parameters and evaluating them as needed as called normal order evaluation. Again, the two methods produce the same answer in the absence of side effects and if both terminate.
If it's possible at all to terminate and produce an answer, normal order will do so. Applicative order may not terminate, though, if evaluating one of the parmeters (even if not needed!) fails to terminate.
Applicative order is generally more efficient, since actual parameters are evaluated once instead of every time they are used as in normal order. However, this is not always the case: applicative order may spend two hours evaluating an actual parameter that is never used.
Because of this "evaluating things only when needed" strategy, normal order evaluation is sometimes called lazy evaluation.
Last updated at 9:54 am on Friday, August 27, 2004.