The interpreter we've built so far uses call-by-value parameter passing. You've probably heard this term before: it means that all parameters are passed by making a copy of their value. Call-by-value parameter passing is used by default in C++, Java, and Pascal. It's the only parameter passing method available in C and Scheme. (Yes, C has no call-by-reference parameter passing--you can pass pointer type by value, but that's not the same as passing a value by reference.)
Call-by-value parameter passing has the advantage of protecting values in the caller's environment from being changed by the called function. (Of course, it also has the disadvantage sometimes of being less efficient when passing really large structures.)
In call-by-reference parameter passing, we don't bind the formal parameter to a new reference containing a copy of the expressed value--we bind the formal parameter to a reference to the actual parameter. Any changes made to the formal parameter are made to the variable passed as the actual parameter as well.
For example, what would the value of the following expression be under call-by-value? Under call-by-reference?
let a = 3
p = proc (x) set x = 4
in begin
(p a);
a
end
(This example assumes we have a begin expression in ELL that works semantically like Scheme's begin expression. You'll be adding this in HW-23.)
This expression returns the value of the variable a after returning from the call to p.
What is it?
Sometimes this ability for the called function to propogate changes back to the caller through side effects is desirable. It makes it easier to write a swap function like this one:
let a = 3
b = 4
swap = proc (x, y)
let temp = x
in begin
set x = y;
set y = temp
end
in begin
(swap a b);
-(a,b)
end
The idea of passing parameters by reference applies only to variable expressions, not to the other types of expressions we've discussed. Why is this? Consider the following example using call-by-reference parameter passing:
let p = proc (x) set x = 5 in (p +(1,2))
So where does the value 5 go that is assigned to x?
Here's the same case in C++:
void p(int& x) {x = 5;}
main()
{
p(1+2);
}
When you try to compile this, you get the following warning:
% CC -o test test.C CC: "test.C", line 6: warning: temporary used for non-const int & argument; no changes will be propagated to actual argument (anachronism) (283)
What's the C++ compiler trying to tell you?
Call-by-reference parameter passing is one way that aliasing can be introduced. Aliasing is when multiple variables share a single value--changes to one mean all of the variables change. Of course, call-by-reference is not the only way that aliases can be introduced--pointers are another common source of aliases.
To see how aliasing is introduced through call-by-reference, consider the following code:
let a = 2
b = 3
p = proc(x, y)
begin
set x = 4;
y
end
in (p b b)
The result of executing this code is 4, not 3 because b gets two names in p, x and y.
This kind of behavior can make programs very difficult to reason about. Ensuring the programs behave correctly in the presence of aliasing is extremely difficult. For example, the following code appears to cleverly avoid the use of a temporarily variable by making use of the property that subtraction and addition are inverses for the integers:
let b = 3
c = 4
swap2 = proc (x, y)
begin
set x = +(x,y);
set y = -(x,y);
set x = -(x,y)
end
in begin
(swap2 b c);
(swap2 b b)
b
end
For non-aliased values, this code works as expected; but for aliased values, the procedure does the wrong thing.
Note that this is caused by aliasing, not because the procedure got the same value for x and y, so reasoning about swap2 using the standard rules for arithmetic leads to a mistaken assumption that the code works.
There are various ways to implement call-by-reference parameter passing. The one in your book relies on storing two different kinds of values in environments: direct values (expressed values) and indirect values (references). A new datatype (target) is introduced, and targets are stored as values in environments. Here's the implementation of target:
(define-datatype target target?
(direct-target
(expval expval?))
(indirect-target
(ref ref-to-direct-target?)))
(define expval?
(lambda (x)
(or (number? x) (procval? x))))
(define ref-to-direct-target?
(lambda (x)
(and
(reference? x)
(cases reference x
(a-ref (pos vec)
(cases target (vector-ref vec pos)
(direct-target (v) #t)
(indirect-target (v) #f)))))))
We also change our references to point into vectors of targets instead of just an arbitrary vector:
(define-datatype reference reference?
(a-ref
(position integer?)
(vec (vector-of target?))))
(define vector-of ; ignores argument -- doesn't really enforce, just for documentation
(lambda (pred) vector?)) ; could expand to really enforce contents of values vectors
We also need to change the functions that access references:
(define primitive-deref
(lambda (ref)
(cases reference ref
(a-ref (pos vec) (vector-ref vec pos)))))
(define primitive-setref!
(lambda (ref val)
(cases reference ref
(a-ref (pos vec) (vector-set! vec pos val)))))
(define deref
(lambda (ref)
(cases target (primitive-deref ref)
(direct-target (expval) expval)
(indirect-target (ref1)
(cases target (primitive-deref ref1)
(direct-target (expval) expval)
(indirect-target (p)
(eopl:error 'deref
"Illegal reference: ~s" ref1)))))))
(define setref!
(lambda (ref expval)
(let ((ref (cases target (primitive-deref ref)
(direct-target (expval1) ref)
(indirect-target (ref1) ref1))))
(primitive-setref! ref (direct-target expval)))))
The last set of changes involves the way we evaluate operands. (For variables, we don't want
to "evaluate" them to get expressed values--we just want to return a reference to them.) Let's look
at all of the places we currently use eval-rands and decide what we need to do.
There are currently three places where we use eval-rands:
For primitive expressions, we don't need to worry about passing references--just pass the expressed values we get back from evaluating each of the operands:
(define eval-primapp-exp-rands
(lambda (rands env)
(map (lambda (x) (eval-expression x env)) rands)))
For the expressions that initialize the local variables in let expressions, we also want to just evaluate the expressions, but we also want to build direct targets for binding to variables in the new local environment:
(define eval-let-exp-rands
(lambda (rands env)
(map (lambda (x) (eval-let-exp-rand x env)) rands)))
(define eval-let-exp-rand
(lambda (rand env)
(direct-target (eval-expression rand env))))
Finally, we're ready to set up the call-by-reference parameter passing itself.
We do this by changing the eval-rand function (which app-exp is the only one to use anymore):
(define eval-rands
(lambda (rands env)
(map (lambda (x) (eval-rand x env)) rands)))
(define eval-rand
(lambda (rand env)
(cases expression rand
(var-exp (id)
; call-by-reference and build an indirect target
(indirect-target
(let ((ref (apply-env-ref env id)))
(cases target (primitive-deref ref)
(direct-target (expval) ref)
(indirect-target (ref1) ref1)))))
(else
; just call-by-value and build a direct target
(direct-target (eval-expression rand env))))))
The implementation of eval-rands is pretty straightforward:
var-exp),
use apply-env-ref to get a reference to it, then return this reference as an indirect target.
There is one twist, though: if the expression is a variable and is already a reference to another variable, we don't want to build a reference to a reference--just use the reference that's already there.
The complete interpreter for Lecture 21.
Last updated at 4:03 pm on Tuesday, July 19, 2005.