12.4 Implementing Pass-by-Reference in the Camille Interpreter

The Camille interpreter currently supports only pass-by-value because every time the interpreter encounters an operand, it creates a new reference. For instance, in the following Camille program, the assignment to passed argument x in the called function f does not affect the value of x in the outermost let expression:

The denoted value of a is a reference that initially contains a copy of the value with which the reference x is associated, but these references are distinct. Thus, the assignment to a in the body of the function f has no effect on the x in the outermost let expression; as a result, the value of the expression is 3.

Let us implement pass-by-reference in Camille. We want to mutate Camille so that literals (i.e., integers and functions/closures) are passed by value and variables are passed by reference. The difference between the purely pass-byvalue Camille interpreter and the new hybrid pass-by-value (for literals), pass-by-reference (for variables) Camille interpreter is summarized as follows:

• Pass-by-value involves creating a new reference for the evaluation of every operand.

• Pass-by-reference involves creating a new reference only for the evaluation of a literal operand.

In other words, unlike the prior implementation of Camille, now we only create a new reference for literal operands. In the prior implementation, we created a new reference for every operand. As a consequence, in Camille now, we use:

• pass-by-value for literals (i.e., numbers and functions/closures)

• pass-by-reference for all non-literals (i.e., variables)

12.4.1 Revised Implementation of References

We retain the following:

However, we need a revised implementation of references. A reference is still a location in a list. However, instead of only containing expressed values, the elements of that list can now contain either expressed values or denoted values— which are references to expressed values. We use the following terminology (Friedman, Wand, and Haynes 2001):

• A list element that contains an expressed value is called a direct target (i.e., pass-by-value).

• A list element that contains a denoted value is called an indirect target (i.e., pass-by-reference).

The following is an abstract-syntax implementation of a Target ADT as well as the revised abstract-syntax implementation of the Reference ADT:

12.4.2 Reimplementation of the evaluate_operand Function

The extend_environment and apply_environment_reference functions need not change. However, the function extend_environment now accepts a list of targets and returns a list containing those targets. The function apply_environment_reference looks up an identifier and creates a reference to the location containing the appropriate target.

We now have the support structures in place to implement the pass-byreference parameter-passing mechanism. Let us consider each context in which subexpressions are evaluated. For primitive applications, we simply pass the value. For instance:

where evaluate_prim_app_expr_operands is defined as

Therefore, the evaluation of primitive applications is unchanged and remains as pass-by-value. We will also retain pass-by-value for let-bound variables:

where the evaluate_let_expr_operand and localbindingDereference functions are defined, respectively, as

We define these functions because some expressions in the bindings or body of a let expression may not evaluate to references (e.g., let a=5 in 5). Therefore, we must inspect the value returned from evaluate_expr to determine if it is a reference that needs to be dereferenced before it is used. The evaluation of let expressions in Camille is also unchanged and remains as pass-byvalue. For function applications, we continue to evaluate each operand using evaluate_operand:

Let us unpack the three cases of operands handled in this function:

• If the operand is a literal [e.g., an integer (ntNumber) or function/closure (ntFuncDecl)], then return a direct target to it (lines 31–36).

• If the operand is a variable (i.e., ntIdentifier) that points to a direct target, then return an indirect target to it (lines 10–16).

• If the operand is a variable (i.e., ntIdentifier) that points to an indirect target, then return a copy of the same indirect target (lines 18–29).

• If the operand is a variable (i.e., ntIdentifier) that points to an indirect target (lines 18–29) that points to an indirect target, then return a copy of the same indirect target (line 27).

• If the operand is a variable (i.e., ntIdentifier) that points to an indirect target (lines 18–29) that points to a direct target, then return the direct target (line 29).

This definition of the evaluate_operand function maintains the invariant that a reference contains either an expressed value or a reference to an expressed value. It also means that Camille does not support double indirect references (e.g., int** x in C).

Consider the following illustrative Camille program modified from Friedman, Wand, and Haynes (2001):

Figure 12.10 presents the references associated with the arguments to the three literal functions in this program. Notice that both parameters b and y are indirect targets to parameter v, which is a direct target to the argument 7, rather than y being an indirect target to the indirect target b—double indirect pointers are not supported. Figure 12.11 depicts the relationship of the references b and y to each other and to the argument 7 in more detail. Since the Camille interpreter now supports pass-by-reference for variable arguments, a Camille function is now able to modify the value of an argument:

Now we can also define a swap function in Camille that successfully swaps its arguments in the calling expression/function:

Programming Exercise for Section 12.4

Exercise 12.4.1 (Friedman, Wand, and Haynes 2001, Exercise 3.55, p. 114) Implement the pass-by-value-result parameter-passing mechanism in the version of Camille in Section 12.2 (i.e., 3.0). To use pass-by-value-result, the argument must be a variable. When an argument is passed by value-result, the parameter is bound to a new reference initialized to the value of the argument, akin to pass-by-value. The body of the function is then evaluated as usual. However, when the function returns, the value in the new reference is copied back into the reference denoted by the argument. In addition to the modified Camille interpreter, provide a Camille program that produces different results using pass-by-reference and pass-by-value-result.