Chapter VIII.  Technical Programming Concepts

21. Function Calls

Last revision:  April 15 1998

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, call-by-name and call-by-reference, and we describe how these methods are simulated in Mathematica.  Our examples are derived from list and matrix operations.

Mathematica operations/structures introduced: 
     call-by-value
     call-by-name
     call-by-reference
     SetAttributes[name, attribute]
     ClearAttributes[name, attribute]
     Attributes[name]
     HoldAll, HoldFirst, HoldRest
     AppendTo[]
     PrependTo[]

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.

To illustrate this, consider the following version of an absolute value function.

Clear[absValue];
absValue[x_] := If[x < 0, -x, x];

Tracing an evaluation of this function reveals something about how Mathematica deals with parameters when evaluating functions.

n = 5; 
Trace[absValue[2n]]

The steps revealed by the Trace are: 
  •  Compute the value of the argument, 2n, by finding n's value, then doubling (to get 10);
  •  Substitute 10 for every instance of n in the body of the function absValue;
  •  Proceed to evaluate the body of the function.
The second step is the reason Mathematica doesn't allow you to Set parameters to new values within the body of a function.  Here, for example, a statement like x = -x (or, in FullForm,  Set[x, -x]) would be converted to  10 = -10 (or, Set[10, -10]).  Clearly this is ridiculous.

Example: matrixTrace

There are times, however, when evaluation of the argument to a function involves more work than is necessary.  One such situation is when the argument is an object of very large size, such as an 1000x1000 array of integers.  The mere act of copying the value of this argument into one place in the body of the function involves copying one million integers!  But suppose our function doesn't need to look at all the entries, but only at a relatively small fraction of them.  

Here's an example.  The trace of a square matrix is the sum of the entries on it's diagonal.  Here's a function which computes the sum of the entries on the main diagonal of a square matrix.  (In linear algebra, this is known as the "trace" of a matrix.  First, we write a boolean function which tests for a square matrix.)

squareMatrixQ...

Clear[squareMatrixQ];
squareMatrixQ::usage="squareMatrixQ[m] returns True if m has dimensions {n,n} for some n, otherwise squareMatrixQ[m] returns false.";

squareMatrixQ[m_] :=
  MatrixQ[m] &&
  Switch[Dimensions[m],
    {n_Integer,n_Integer, ___}, True,
    _, False
  ];

Clear[matrixTrace];
matrixTrace::usage="matrixTrace[m] returns sum of the entries on the
main diagonal of the square matrix m.";

matrixTrace[mtrx_?squareMatrixQ] := 
  Module[
    { diagSum = 0, i
    },
    Do[ 
      diagSum = diagSum + mtrx[[i,i]],
      {i, Length[mtrx]}
    ];
    diagSum
  ];

matrixTrace[{{10,2,3},{4,50,6},{7,8,90}}]

A call like matrixTrace[{{10,2,3},{4,50,6},{7,8,90}}] isn't too bad (try tracing it), but suppose we wanted to calculate the trace of a large matrix. The variable largeMtrx below holds a 400x400 matrix whose entries are randomly selected from 1, 2, 3, .., 10.

largeMtrx = 
  Table[Random[Integer, {1, 10}], {400}, {400}];

A call like matrixTrace[largeMtrx] now requires copying 160,000 integers, but we only need to look at the 400 (or 0.25%) of these.  Let's see how long it takes to do this.

Timing[matrixTrace[largeMtrx]]

If our task involved taking a lot of matrixTrace's for large matrices, the time could really add up.   One way to get around this is to delay the evaluation of the argument sent to matrixTrace until it is actually needed.  Mathematica accomplishes this by allowing us to set an "attribute" for our function indicating that arguments are to be "held" unevaluated until it is necessary to do so.

Clear[matrixTraceH];
matrixTraceH::usage="matrixTraceH[m] returns sum of the entries on the
main diagonal of the square matrix m.";

SetAttributes[matrixTraceH, HoldAll];

matrixTraceH[mtrx_Symbol] := 
  Module[
    { diagSum = 0, i
    },
    If[squareMatrixQ[mtrx],
      Do[ 
        diagSum = diagSum + mtrx[[i,i]],
        {i, Length[mtrx]}
      ];
      diagSum
    ]
  ];

Timing[matrixTraceH[largeMtrx]]

Timing[squareMatrixQ[largeMtrx]]

Attributes are properties of functions which affect how they are evaluated.  They are turned on or off via the commands SetAttributes and ClearAttributes, respectively.  You can learn the attributes associated with a function using the Attributes command.

?SetAttributes

?ClearAttributes

?Attributes

Attributes[Plus]

Attributes[matrixTrace]

Attributes[matrixTraceH]

There are many attributes available to the Mathematica programmer; our concern here is with those which "hold" arguments: HoldAll, HoldFirst, HoldRest.  (See the statement SetAttributes[matrixTraceH, HoldAll] above.)  We take advantage of "holding" when we ask for a Trace of an expression's evaluation.  See, for example, the FullForm of the trace in the absolute value example.

n = 5; 
Trace[absValue[2n]]

Trace[absValue[2n]]//FullForm

The method of function evaluation that we establish via SetAttributes[matrixTraceH, HoldAll] is known as call-by-name.  This leaves the actual parameters unevaluated until they are needed, but evaluates them anew with each reference.

Warning: the conveniences of call-by-name must be balanced against the potential abuse by harmful side-effects.  More on this later.

Call-by-reference

Most commonly used languages (for example, Pascal, C, or C++) do not directly support call-by-name function evaluation.  There, the alternative mechanism to call-by-value evaluation is call-by-reference evaluation.  A reference to a variable is the information the computer needs to determine the precise storage location of the actual parameter.  You could think of it as the location (or address) of the container for this variable---where the computer looks to find the value of the variable.  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.  This behavior may or may not be one we wish the function to have.

If matrixTrace were implemented using call-by-reference, then a call like matrixTrace[largeMtrx] would make the address of the parameter mtrx (in the definition of the matrixTrace) agree with the address of largeMtrx.  Then the computations referencing parts of mtrx would be going to the actual source, largeMtrx, to get the needed values, as opposed to retrieving these values from a copy of largeMtrx. Since it's only necessary to copy the address of largeMtrx, and not the entire value of largeMtrx, considerable time savings are involved.

An inconvenience of call-by-reference evaluation is that calls to a function must provide an actual parameter which has a "real" address.  For example, matrixTrace[2 * largeMtrx] wouldn't be permitted, since the expression 2*largeMtrx doesn't belong to a "name"---we haven't specifically asked for an address to store this value.  We imposed a similar restriction on matrixTraceH, when the formal parameter was typed as a Symbol.

Call-by-reference is an important and common tool.  Our discussion of call-by-name evaluation is prompted by a desire to simulate the benefits (and pitfalls) of call-by-reference evaluation.

Example: saveRotateLeft

Here we implement a rotate function using call-by-name, 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 = Range[10]

saveRotateLeft[test]

Now test has actually been changed!

test

If we were able to use call-by-reference, function calls to saveRotateLeft[] would run faster.  (This isn't really the case with call-by-name in this instance, since we need to reference the entire parameter, anyway.)

However, 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[]" sank 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-name; one sets the attribute "HoldFirst" instead of "HoldAll".

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