17 HIGHER-ORDER
DEFINITIONS
17.1 References
17.2 Refdef function
17.3 Evaldef function
17.4 Definition-references
17.5 Function Definitions
17.6 Operation Definitions
17.7 Result Specifications
A higher-order definition is a definition that takes references to
other definitions as input and/or returns references to other definitions as
result.
The major use of higher-order definitions is to abstract common behaviour
into one place. For example, a common kind of a higher-order definition is found
in sorting functions which take a comparison function as a parameter, allowing
the programmer to separate the sorting algorithm from the comparisons of the
items being sorted. Other examples are numerical integration of an external
function, and external operations on the elements of a list.
17.1 References
A reference to a definition consists of a pointer to a definition and its
associated type. The type of the reference is derived from the signature of the
referenced definition. There are two builtin functions: the refdef
function to obtain a reference to a definition and the evaldef to
evaluate a referenced definition.
17.2 Refdef function
The refdef function is a built-in function. It refers to an
existing definition and returns a reference to the selected definition.
refdef(definition) -> definition-reference;
The refdef function has
only one argument which is used to identify a definition. The argument
must be
the signature of an existing definition, without the result-specification. The
selection of the definition is based on definition-name, number of parameters and the type
specifications of those parameters.
The result of the refdef function is a reference to the selected
definition. A reference to a definition consists of a reference value
and a reference type. The reference value is a pointer to the selected
definition. The reference type is derived from the signature of the
selected definition. It describes the number and types of the
parameters and the result-specification. A reference type has always the
reserved name def.
Let us use as an example a definition of the sum of two integers:
sum (integer, integer) -> integer;
sum (i1, i2) = i1 + i2;
Let us assume that we want to obtain a reference to this definition. We use
the refdef function:
Ref = refdef (sum(integer, integer)); In this example the argument of the
refdef function identifies our
sum definition, based on the name sum and the two integer
parameters. In this example, the value of Ref is a pointer to the
sum definition.
The
type of Ref is
def(integer, integer) -> integer This type is derived from the
signature of the selected definition. The only
difference is that the name of the definition is replaced by the reserved name def
. This is because the type of a definition covers a broader range then the
specific definition.
17.3 Evaldef
function
The evaldef function is also a built-in function. It calls and
evaluates a selected definition and returns the value of the evaluated definition.
evaldef (definition-reference, argument1, argument2, ...) -> value; The
evaldef
function has a variable numbers of arguments. The
first argument must always be a reference to a first or higher-order
definition. All other arguments must correspond to the parameters as specified
by the type of the reference. The result-specification in the reference
type specifies the number and result-type of the returning value(s).
Using our previous example, we may use the evaldef function to call
the sum definition:
evaldef(Ref, 2, 5) ?
The result will be 7.
evaldef(Ref, 3, 5) * evaldef(Ref, 7,3) ?
will return 80.
But
evaldef(Ref, 3, 4.5) ?
will return the error-message:
evaldef((def(integer, integer) -> integer), integer, real) is not defined
17.4
Definition-references
A definition-reference may be used in name-definitions,
assigment-statements, arrays, lists, arguments and in all other places
where expressions are allowed. In that sense definition-references are
ordinary values. Each definition-reference has a type as explained
earlier. The normal rules for type assignment and type matching also
apply to the types of definition-references.
Definition-reference types may be declared in type specifications,
such as:
type IntegerDeftype = def(integer, integer) -> integer;
17.5 Function
Definitions
Let us use some additional examples of function definitions. Suppose, we want to write a definition to double all the elements of an
integer list and store the result into a new list:
double(list(integer)) -> list(integer);
double(L) = { 2 * items(L) };
We may use this in an expression like
double({1 .. 7})?
The result will be:
{ 2, 4, 6, 8, 10, 12, 14}
The next step is to generalize this example. We want to make a definition
which is not restricted to a multiplication of 2. We will use an external
definition which will double all odd numbers of the input
list.
DoubleOdd(integer) -> integer; DoubleOdd(I) = if mod(I, 2) == 1 then I + I else I;
We now make a higher-order definition which creates a new modified list:
NewList(list(integer), def(integer) -> integer) -> list(integer); NewList(L ,D) = { evaldef(D, items(L)) };
We may use this in an expression like
NewList({1 .. 7}, refdef(DoubleOdd(integer)))?
The result will be:
{ 2, 2, 6, 4, 10, 6, 14}
We will discuss this example in more detail:
The DoubleOdd definition is a normal, first-order definition. It doubles the
odd input numbers.
The NewList definition is a second-order definition. It has two
parameters. The first one is a list of integers, the second is the type
of a first-order definition.
In the definition rule of the NewList definition the first-order
definition will be executed by calling the evaldef function. The
first argument of the evaldef function is the reference to the supplied
definition, the second argument are the items of the input list.
In the following expression the NewList is called. The first argument is a
list of integers. The second argument is a reference to the DoubleOdd
definition.
17.6 Operation
Definitions
Operation definitions may also be used as first-order definitions.
Let us assume that we want to define the adding of two text strings:
text + text -> text;
T1 + T2 = T1 & T2;
We may now use the refdef function to obtain a reference to
the text adding operation:
AddTextRef = refdef(text + text);
The type of AddTextRef is in this case:
def(text, text) -> text;
To evaluate this operation reference we may use:
evaldef(AddTextRef, "pq", "rstu")?
will return:
"pqrstu"
17.7 Result
Specifications
Part of a reference type is a result specification. It specifies one
of the quantifiers (nothing, optional, single, multi) and the
resulting type, if any. The result specification must match with the
result-specification of the evaluated definition.
Let us assume that we want to define a multi-value definition:
f(integer) -> multi(integer);
f(N) = 1 .. N;
We may now use the refdef function to obtain a reference to
the multi-value definition.
MultiRef = refdef(f(integer));
The type of MultiRef is in this case:
def(integer) -> multi(integer);
To evaluate this operation reference we may use:
evaldef(MultiRef, 5)?
will return the values of 1, 2, 3, 4, 5.
|
|
Part 1: Language Description |
|
Chapter 17: Higher-order
Definitions |
|