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.
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 );Magma evaluates the two arguments to 13 and true respectively, before applying f.
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;and we apply f as follows
> r := f( 4/0, false );Magma treats this as an error since the 4/0 is evaluated, and an error produced, before the function f is applied.
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;is treated as the function application,
> r := '+'(6,7);Accordingly all arguments to an operator are evaluated before the operator is applied.
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 will reply with the answer false since Magma knows that false and X for all X is false.
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,
To clarify this process assume that we type,
> a := 6; > b := 7;producing the context [ (a,6), (b,7) ]. Now say we type,
> c := a+b;This produces the context [ (a,6), (b,7), (c,13) ]. By following the process outlined above we can see how this context is calculated. The steps are,
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;giving the context [ (a,6),(b,7),(c,13) ]. Now say I type,
> d := func< n | a+b+c+n >;Magma uses the same process to evaluate the function expression func< n | a+b+c+n > on the right hand side of the assignment d := ... as it does to evaluate expression a+b on the right hand side of the assignment c := .... So evaluation of this function expression proceeds as follows,
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!
Say we type the following,
> a := 1; > b := func< n | a >; > c := func< n | b(6) >;The first line leaves a context of the form [ (a,1) ]. The second line leaves a context of the form [ (a,1), (b,FUNC(n : 1)) ].
The third line is evaluated as follows,
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,
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;Here $$ is a placeholder for the function value that the function expression function(n) if n eq ... end function denotes (those worried that the denoted function value appears to be defined in terms of itself are referred to the fixed point semantics of recursive functions in any standard text on denotational semantics).
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;Again Magma's evaluation process appears to make this impossible, since to construct f Magma requires a value for g, but to construct g Magma requires a value for f. Again there is a solution. An identifier can be declared `forward' to inform Magma that a function expression for the forward identifier will be supplied later. The functions f and g above can therefore be declared as follows,
> forward f, g; > f := function(...) ... a := g(...); ... end function; > g := function(...) ... b := f(...); ... end function;(strictly speaking it is only necessary to declare g forward as the value of f will be known by the time the function expression function(...) ... b := f(...); ... end function is evaluated).
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 >;producing the context [ (f,FUNC(a,b : a+b)) ].
Now say we apply f by typing,
> r := f( 1+2, 6+7 ).How is the value to be assigned to r calculated? If we follow the evaluation process we will reach the final step which will say something like,
\ ``simplify (FUNC(a, b : A(a,b)))(3,13) to its canonical form''where as before A is the value that is the addition function. How is this simplification performed? How are function values applied to actual function arguments to yield result values? Not unsurprisingly the answer is via a process of substitution. The evaluation of a function application proceeds as follows,
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;then in evaluating the expression 1+2 Magma will replace + by its value in the initial context.
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.