Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will.  Free for
distribution to college and university instructors for personal,
non-commercial use.  If these notebooks are used in a course, the authors
request $20 per student.

Chapter VIII.  Technical Programming Concepts

21. Function Calls

Last revision: October 27 1996

In this section we consider in detail the procedure a compiled program uses
in executing a function call, especially the trade-offs of call-by-value
and call-by-reference, and we describe how these methods are simulated in
Mathematica.  Our examples are derived from list and matrix operations.

Function Calls

Recall how standard function calls in compiled programs operate.  The
computer copies the values of the actual parameters into the space
allocated for the formal parameters; the computer runs the function, which
is typically stored in a separate place from the list of instructions being
executed; and finally the computer optionally provides a return value back
to the original program.  This method of implementing function calls is
termed call-by-value, emphasizing the fact that only the value of each
parameter is passed to the function, not the names or locations of the
actual parameters themselves. This method is best in most situations, but
the method poses problems when the data to be passed to the function is of
a very large size.  For instance, if the parameters are 1000x1000 arrays of
integers, the very operation of copying may take an inordinately long time,
and if the function is only going to consider a few of the array elements,
the operation of copying so many elements is terribly inefficient. An
alternate plan for implementing function calls is to pass what is called a
reference to the parameter, which is the information the computer needs to
determine the precise storage location of the actual parameter.  This
method circumvents the need to copy the parameter into a formal parameter,
and so speeds up the function call process.  One possible trade-off is that
the function now has the information, and therefore the ability, to change
the value of the original actual parameter, so that if the function changes
the value of the formal parameter, it will then change the value of the
original actual parameter.  Now this behavior may or may not be one we wish
the function to have.  In what follows we'll consider how to implement
call-by-reference in Mathematica (call-by-value being the default) and
examine situations in which call-by-reference is desirable and situations
in which it is not.

Example 1: Adding Elements on the Diagonal of a Matrix

Suppose we wish to sum all of the elements of a two-dimensional array which
have identical array indices, e.g. the element at "1,1", the element at
"2,2", and so forth.  We could do so using "Sum[ ]", executing
"Sum[array[i,i],{i,1,n}]", where "array" is the name of the array and "n"
is the number of rows and columns.  However, we would like to define a
function.  We might try the following.

Clear[myTrace]
myTrace[a_] := Module[{i},
          i=Dimensions[a];
        If[Length[i]==2&&i[[1]]==i[[2]]
                                (* checking square *),
                For[sum=0;j=1, j<=i[[1]], j++,
                        sum+=a[[j,j]] ];
                    sum,
             "Bad matrix"]
        ]

myM = {{1,2},{3,4}};
myTrace[myM]

"myTrace[ ]" is a perfectly fine definition for our function, unless "a" is
a huge matrix, in which case Mathematica is forced to waste lots of time
copying the entire actual parameter to the formal variable when the
function in fact needs only a small fraction of the data.  Hence we'll use
call-by-reference.

We can instruct Mathematica to implement function calls to particular
functions as call-by-reference operations by setting a particular
attribute, "HoldAll", of the function.   To do so we execute
"SetAttributes[name,HoldAll]", where "name" is the name of our function.
Then all  parameters to the function will be passed as references, not as
copied values.

Clear[myTrace2]
myTrace2[a_] := Module[{i},
        i=Dimensions[a];
        If[Length[i]==2&&i[[1]]==i[[2]] (* checking square *),
                For[sum=0;j=1, j<=i[[1]], j++,
                        sum+=a[[j,j]] ];
                sum,
           "Bad matrix"]
        ];
SetAttributes[myTrace2,HoldAll]

myTrace2[myM]

Let's check out the relative timings on a huge matrix.  Recall that
"Timing[ ]" returns a list, the first element of which is the amount of
time the expression took to evaluate and the second element of which is the
result.  We'll find the average execution time over 100 separate runs of
each functions.

myMatrix=Table[i+2*j,{i,1,150},{j,1,150}];

Sum[Timing[myTrace2[myMatrix]],{100}]/100.0
  (* call-by-reference *)

Sum[Timing[myTrace[myMatrix]],{100}]/100.0
  (* call-by-value *)

Which took longer?

Example 2: saveRotateLeft

Here we implement a rotate function using call-by-reference, and the
function will have a property that no other function we have written so far
has had: the capability to save the result back in the variable whose name
was passed to the function.  We must be careful, then, since if the
parameter is not a name (but an explicit expression, such as "2"), we do
not want to allow the function to attempt to change that value.  Actually,
Mathematica won't allow it, but will complain with an error message, which
we'd like to avoid.  Hence we check for a name (a Symbol) in the formal
parameter.

Clear[saveRotateLeft];
SetAttributes[saveRotateLeft, HoldAll];
saveRotateLeft[v_Symbol] := Module[{firstEntry},
   firstEntry = v[[1]];
   Do[
      v[[i]] = v[[i+1]]
   ,{i,1,Length[v]-1}];
   v[[ Length[v] ]] = firstEntry;
   v
]

test = {1,2,3,4,5}

saveRotateLeft[test]

Now "test" has actually been changed!

test

Note that since we have used call-by-reference, any function calls to
"saveRotateLeft[ ]" will occur faster, but it may not be true that we wish
our functions to have the power to change the arguments which they are
given.  We have, then, a time versus protection trade-off.
"saveRotateLeft[ ]" is a substitute for "RotateLeft[ ]", but not a
substitute without disadvantages:  if we want to rotate a list and save the
result elsewhere, we would have to say "list = listold;
saveRotateLeft[list]", thereby saving the list before "saveRotateLeft[ ]"
got its claws into the old list!

Notes

When a function is defined with the attribute "HoldAll", the parameter type
checking of the function is basically disabled; Mathematica will only be
able to tell if the parameter is a Symbol or not.  Hence, do not check for
a List or some other type when specifying arguments; do not use expressions
such as "a_List".

It is possible in Mathematica to permit only the first argument in a list
to be passed under "call-by-reference"; one sets the attribute "HoldFirst"
instead of "HoldAll".

Mathematica itself actually contains some "call-by-reference" functions:
two are "AppendTo[]" and "PrependTo[]".