Evaluation in Magma

Evaluation is the process of computing (or constructing) a value from an expression. For example the value 3 can be computed from the expression 1+2. Computing a value from an expression is also known as evaluating an expression.

There are two aspects to evaluation, namely when and how it is performed. This section discusses these two aspects.

Call by Value Evaluation

Magma employs call by value evaluation. This means that the arguments to a function are evaluated before the function is applied to those arguments. Assume f is a function value. Say we type,

> r := f( 6+7, true or false );

While knowing the exact point at which arguments are evaluated is not usually very important, there are cases where such knowledge is crucial. Say we type,

> f := function( n, b )
> if b then return n else return 1;
> end function;

> r := f( 4/0, false );

By contrast some languages evaluate the arguments to a function only if those arguments are encountered when executing the function. This evaluation process is known as call by name evaluation. In the above example r would be set to the value 1 and the expression 4/0 would never be evaluated because b is false and hence the argument n would never be encountered.

Operators like + and * are treated as infix functions. So

> r := 6+7;

> r := '+'(6,7);

There are three operators, `select', `and' and `or' that are exceptions to this rule and are thus not treated as infix functions. These operators use call by name evaluation and only evaluate arguments as need be. For example if we type,

> false and (4/0 eq 6);

Magma's Evaluation Process

Let us examine more closely how Magma evaluates an expression as it will help later in understanding more complex examples, specifically those using functions and maps. To evaluate an expression Magma proceeds by a process of identifier substitution, followed by simplification to a canonical form. Specifically expression evaluation proceeds as follows,

(1)

replace each identifier in the expression by its value in the current context.

(2)

simplify the resultant value to its canonical form.

To clarify this process assume that we type,

> a := 6;
> b := 7;

> c := a+b;

(1)

replace a in the expression a+b by its value in the current context giving 6+b.

(2)

replace b in 6+b by its value in the current context giving 6+7.

(3)

simplify 6+7 to 13

Function Expressions

Magma's evaluation process might appear to be an overly formal way of stating the obvious about calculating expression values. This formality is useful, however when it comes to function (and map) expressions.

Functions in Magma are first class values, meaning that Magma treats function values just like it treats any other type of value (e.g., integer values). A function value may be passed as an argument to another function, may be returned as the result of a function, and may be assigned to an identifier in the same way that any other type of value is. Most importantly however function expressions are evaluated exactly as are all other expressions. The fact that Magma treats functions as first class values is why Magma is said to have an essentially functional subset.

Take the preceding example. It was,

> a := 6;
> b := 7;
> c := a+b;

> d := func< n | a+b+c+n >;

(1)

replace a in the expression func< n | a+b+c+n > by its value in the current context giving func< n | 6+b+c+n >.

(2)

replace b in func< n | 6+b+c+n > by its value in the current context giving func< n | 6+7+c+n >.

(3)

replace c in func< n | 6+7+c+n > by its value in the current context giving FUNC(n : 6+7+13+n)

(4)

simplify the resultant value FUNC(n : 6+7+13+n) to the value FUNC(n : 26+n).

The resultant function value is now assigned to d just like any other type of value would be assigned to an identifier yielding the context [ (a,6),(b,7), (c,8), (d,FUNC(n : 26+n)) ].

As a final point note that changing the value of any of a, b, and c, does not change the value of d!

Function Values Assigned to Identifiers

Say we type the following,

> a := 1;
> b := func< n | a >;
> c := func< n | b(6) >;

The third line is evaluated as follows,

(1)

replace the value of b in the expression func< n | b(6) > by its value in the current context giving FUNC(n : (FUNC(n : 1))(6)).

(2)

simplify this value to FUNC(n : 1) since applying the function value FUNC(n : 1) to the argument 6 always yields 1.

Now look back at the example at the end of the previous section. One step in the series of replacements was not mentioned. Remember that + is treated as a shorthand for an infix function. So a+b is equivalent to '+'(a,b). + is an identifier (assigned a function value), and so in the replacement part of the evaluation process there should have been an extra step, namely,

(4)

replace + in func< n : 6+7+13+n > by its value in the current context giving FUNC(n : A( A( A(6,7), 13 ), n )).

(5)

simplify the resultant value to FUNC(n : A( 26, n )). where A is the (function) value that is the addition function.

Recursion and Mutual Recursion

How do we write recursive functions? Function expressions have no names so how can a function expression apply itself to do recursion?

It is tempting to say that the function expression could recurse by using the identifier that the corresponding function value is to be assigned to. But the function value may not be being assigned at all: it may simply be being passed as an actual argument to some other function value. Moreover even if the function value were being assigned to an identifier the function expression cannot use that identifier because the assignment rules say that the identifiers on the left hand side of the := in an assignment statement are not considered declared on the right hand side, unless they were previously declared.

The solution to the problem is to use the $$ pseudo-identifier. $$ is a placeholder for the function value denoted by the function expression inside which the $$ occurs. An example serves to illustrate the use of $$. A recursive factorial function can be defined as follows,

> factorial := function(n) 
> if n eq 1 then
> return 1;
> else 
> return n * $$(n-1); 
> end if;
> end function;

A similar problem arises with mutual recursion where a function value f applies another function value g, and g likewise applies f. For example,

> f := function(...) ... a := g(...); ... end function;
> g := function(...) ... b := f(...); ... end function;

> forward f, g;
> f := function(...) ... a := g(...); ... end function;
> g := function(...) ... b := f(...); ... end function;

Function Application

It was previously stated that Magma employs call by value evaluation, meaning that the arguments to a function are evaluated before the function is applied. This subsection discusses how functions are applied once their arguments have been evaluated.

Say we type,

> f := func< a, b | a+b >;

Now say we apply f by typing,

> r := f( 1+2, 6+7 ).

\    ``simplify (FUNC(a, b : A(a,b)))(3,13) to its canonical form''

(1)

replace each formal argument in the function body by the corresponding actual argument.

(2)

simplify the function body to its canonical form.

The Initial Context

The only thing that remains to consider with the evaluation semantics, is how to get the ball rolling. Where do the initial values for things like the addition function come from? The answer is that when Magma starts up it does so with an initial context defined. This initial context has assignments of all the built-in Magma function values to the appropriate identifiers. The initial context contains for example the assignment of the addition function to the identifier +, the multiplication function to the identifier *, etc.

If, for example, we start Magma and immediately type,

> 1+2;

Users interact with this initial context by typing statements at the top level (i.e., statements not inside any function or procedure). A user can change the initial context through re-assignment or expand it through new assignments. [Next][Prev] [Right] [Left] [Up] [Index] [Root]