Higher-Order Definitions
Higher-order definitions are definitions of relations whose arguments can be relations that are not singletons. A parameter that represents such a relation must begin with an uppercase letter. Such a parameter is often called a higher-order parameter, or a higher-order variable.
You must annotate a higher-order definition with either @outline
or @inline
, but the former is preferable.
Note that you cannot use @inline
for definitions that are directly or indirectly recursive.
In the example below, rotate
is higher-order, because its parameter is intended to be a relation of arbitrary arity.
It can be used for a number of different relations:
// read query
// Move the last element of each tuple to the first position
@outline
def rotate[R] {y, x... : R(x..., y)}
def once = rotate[ {1, 10, 100; 2, 20} ]
def output:A = once
def output:B = rotate[once]
def output:C = rotate[rotate[once]]
See Varargs for an explanation of x...
.
In the example above you could have replaced @outline
with @inline
.
In the following example @outline
is necessary, because the higher-order relation is recursive.
The example computes the transitive closure of a binary relation.
If the binary relation R
contains edges between the nodes of a graph, then nodes A
and B
are in the transitive closure of R
if and only if B
is reachable from A
:
// read query
// Compute the transitive closure of a binary relation
@outline
def transitive_closure[R] = R
@outline
def transitive_closure[R] = x, y : R(x, z) and transitive_closure[R](z, y) from z
def edges = (1, 2); (2, 1); (3, 4); (4, 5)
def output = transitive_closure[edges]
Compare this version of transitive-closure
with the one shown in section @outline
.
There are many simple examples of higher-order definitions in the Standard Library, for instance, union
.
Here is a larger example, a Rel relation that emulates — though less efficiently — the Library relation sum
.
The relations last
, enumerate
, count
, and arity
can be found in the Standard Library:
// read query
@outline
def my_sum[R] = my_sum_aux[enumerate[last[R]], count[R]], arity[R] != 0
@outline
def my_sum_aux[Vector, index] = 0, index = 0
@outline
def my_sum_aux[Vector, index] = Vector[index] + my_sum_aux[Vector, index - 1], index > 0
def my_set = range[1, 10, 1]
def output:A = my_sum[my_set]
def output:B = my_sum[9]
def output:C = my_sum[{}]
def output:D = my_sum[{("a", 1); ("A", "B", 100); 50}]
def empty_arity_2(x, y) = {}
def output:E = arity[empty_arity_2]
def output:F = my_sum[empty_arity_2]
In many programming languages, a typical example of a higher-order function is one that maps a function over a list. Here is a relation that maps a binary relation over the elements of a unary relation:
// read query
// Map binary F over unary R
@outline
def my_map[F, R] = F[x] from x in R
def double[x in Int] = x + x
def emphasis[s in String] = concat[s, "!"]
def output:One = my_map[double, range[1, 6, 2]]
def output:Two = my_map[emphasis, {"Quietly"; "Please"}]
Note that in Rel a relation such as my_map
is unnecessary.
The following also works:
// read query
def double[x in Int] = x + x
def emphasis[s in String] = concat[s, "!"]
def output:One = double[range[1, 6, 2]]
def output:Two = emphasis[{"Quietly"; "Please"}]
In both cases the example with double
is equivalent to the following:
// read query
def double[x in Int] = x + x
def output = x: range[1, 6, 2](val) and double(val, x) from val
A higher-order relation is not required to perform such mapping.
Notice that my_map
is a true higher-order relation.
In particular, its second argument is not a singleton:
// read query
@outline
def my_map[F, R] = F[x], count[R] from x in R
def double[x in Int] = x + x
def output = my_map[double, range[1, 6, 2]]
In the simpler version, by contrast, the argument of double
is a singleton:
// read query
def double[x in Int] = x + x, count[x]
def output = double[range[1, 6, 2]]
One way to think about it is that in the first case the implicit iteration over the contents of {1, 3, 5}
is carried out within the body of the definition of my_rel
.
In the second case the implicit iteration is carried out within the body of the definition of output
.
In both cases the argument of double
is just a first-order variable, i.e., a singleton.
The fact that the name of the second parameter of my_map
begins with an uppercase letter makes a crucial difference.
If it were not so designated as a higher-order variable, then the implicit iteration would happen outside my_map
, and the second argument would be a singleton:
// read query
@outline
def my_map[F, r] = F[x], count[r] from x in r
def double[x in Int] = x + x
def output = my_map[double, range[1, 6, 2]]
The two examples below further illustrate the difference between a higher-order variable and a first-order variable in similar definitions:
// read query
@inline
def P[R] = max[R]
def output = P[{1; 2; 3}]
// read query
@inline
def P[r] = max[r]
def output = P[{1; 2; 3}]
In Rel, types are just relations, and their names are not keywords. If the name of a relation is used — perhaps inadvertently — as a parameter, it will shadow the relation, thus making it inaccessible in the scope of the parameter. In particular, a higher-order parameter may shadow the name of a type.
The following example illustrates the surprising effects of ill-advisedly shadowing the name of a type.
The definition is correct, and output
becomes true
.
// read query
@outline
def all_negative(String) = forall(x in String: x < 0)
def output = all_negative({-1; -2})
Next: Annotations