Higher-Order Definitions

# 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, `aggregate` is higher-order, because its parameter is intended to be a relation of arbitrary arity.

``````// read query

doc"""
Sum up all values in the last column of a relation.
For compound keys, use all but the last key element as the group-by variable.
"""
@outline
def aggregate[R](prefix..., agg) {
agg = sum[key, value : R(prefix..., key, value)]
}

def data = {
("A", "a", 1); ("A", "b", 10);
("B", "a", 2); ("B", "b", 20);
}
def output:data = data
def output:aggregate1 = aggregate[data]
def output:aggregate2 = aggregate[aggregate[data]]``````

As the example shows, higher-order relations can be stacked on top of each other. The keyword `prefix...` is a vararg and can refer to multiple elements in a tuple. See the Rel Primer for more information about varargs.

Higher-order relations can be even used in recursive logic. The example below 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
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 my_arguments = range[1, 6, 2]
def output:One = my_map[double, my_arguments]
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 my_arguments = range[1, 6, 2]
def output:One = double[my_arguments]

In both cases the example with `double` is equivalent to the following:

``````// read query

def double[x in Int] = x + x

def my_arguments = range[1, 6, 2]

def output = x: my_arguments(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 with two higher-order parameters: `F` and `R`.

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 my_arguments = range[1, 6, 2]

def output = my_map[double, my_arguments]``````

One way to think about it is that in the first case the iteration over `{1; 3; 5}` — defined by `my_arguments` — is carried out within the body of the definition of `my_map`, as seen in the `from x in R` expression.

The same logic can be expressed with first-order logic as follows:

``````// read query

def double[x in Int] = x + x, count[x]

def my_arguments = range[1, 6, 2]

def output = double[my_arguments]``````

You can write this as first-order logic thanks to scalar conversion. Scalar conversion means that even though the argument of a relation is a relation by itself (here `range[1, 6, 2]`), the underlying relation `double` applies its logic to each value in `my_arguments`.

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}]``````

## Higher-Order Keywords Shadowing Type Relations

Higher-order keywords in a declaration begin with a capital letter, similar to a type relation. This makes it possible to shadow the name of a type relation with a higher-order keyword.

🔎

Higher-order keywords in relational declarations may shadow the names of type relations.

The following example illustrates this point:

``````// read query

@outline
def all_negative(String) = forall(x in String: x < 0)

def output = all_negative({-1; -2})``````

Here, `String` is a higher-order keyword. It shadows the type relation `String` usually used to check whether a value is of data type String.

Next: Annotations