Next: Modules, Previous: User-defined equality and comparison, Up: Top [Contents]
Mercury supports higher-order functions and predicates with currying, closures, and lambda expressions. (To be pedantic, it would be more accurate to say that Mercury supports higher-order procedures. This is because in Mercury, when you construct a higher-order term, you only get one mode of a predicate or function. If you want multiple modes, you must pass multiple higher-order procedures.)
To create a higher-order predicate or function term, you can use a lambda expression, or, if the predicate or function has only one mode and it is not a zero-arity function, you can just use its name. For example, if you have declared a predicate
:- pred sum(list(int), int). :- mode sum(in, out) is det.
the following unifications have the same effect:
X = (pred(List::in, Length::out) is det :- sum(List, Length)) Y = sum
In the above example,
the type of X, and Y is ‘pred(list(int), int)’,
which means a predicate of two arguments
of types list(int) and int respectively.
Similarly, given
:- func scalar_product(int, list(int)) = list(int). :- mode scalar_product(in, in) = out is det.
the following three unifications have the same effect:
X = (func(Num, List) = NewList :- NewList = scalar_product(Num, List))
Y = (func(Num::in, List::in) = (NewList::out) is det
:- NewList = scalar_product(Num, List))
Z = scalar_product
In the above example,
the type of X, Y, and Z is
‘func(int, list(int)) = list(int)’,
which means a function of two arguments,
whose types are int and list(int),
with a return type of int.
As with ‘:- func’ declarations,
if the modes and determinism of the function
are omitted in a higher-order function term,
then the modes default to in for the arguments,
out for the function result,
and the determinism defaults to det.
The Melbourne Mercury implementation currently requires that you use an explicit lambda expression to specify which mode you want, if the predicate or function has more than one mode (but see below for an exception to this rule).
You can also create higher-order function terms of non-zero arity and higher-order predicate terms by “currying”, i.e. specifying the first few arguments to a predicate or function, but leaving the remaining arguments unspecified. For example, the unification
Sum123 = sum([1,2,3])
binds Sum123 to a higher-order predicate term of type ‘pred(int)’.
Similarly, the unification
Double = scalar_product(2)
binds Double to a higher-order function term of type
‘func(list(int)) = list(int)’.
As a special case, currying of a multi-moded predicate or function is allowed provided that the mode of the predicate or function can be determined from the insts of the higher-order curried arguments. For example, ‘P = list.foldl(io.write)’ is allowed because the inst of ‘io.write’ matches exactly one mode of ‘list.foldl’.
For higher-order predicate expressions that thread an accumulator pair, we have syntax that allows you to use DCG notation in the goal of the expression. For example,
Pred =
( pred(Strings::in, Num::out, di, uo) is det -->
io.write_string("The strings are: "),
{ list.length(Strings, Num) },
io.write_strings(Strings),
io.nl
)
is equivalent to
Pred =
( pred(Strings::in, Num::out, IO0::di, IO::uo) is det :-
io.write_string("The strings are: ", IO0, IO1),
list.length(Strings, Num),
io.write_strings(Strings, IO1, IO2),
io.nl(IO2, IO)
)
Higher-order function terms of zero arity can only be created using an explicit lambda expression; you have to use e.g. ‘(func) = foo’ rather than plain ‘foo’, because the latter denotes the result of evaluating the function, rather than the function itself.
Note that when constructing a higher-order term, you cannot just use the name of a builtin language construct such as ‘=’, ‘\=’, ‘call’, or ‘apply’, and nor can such constructs be curried. Instead, you must either use an explicit lambda expression, or you must write a forwarding predicate or function. For example, instead of
list.filter(\=(2), [1, 2, 3], List)
you must write either
list.filter((pred(X::in) is semidet :- X \= 2), [1, 2, 3], List)
or
list.filter(not_equal(2), [1, 2, 3], List)
where you have defined ‘not_equal’ using
:- pred not_equal(T::in, T::in) is semidet. not_equal(X, Y) :- X \= Y.
Another case when this arises is when want to curry a higher-order term. Suppose, for example, that you have a higher-order predicate term ‘OldPred’ of type ‘pred(int, char, float)’, and you want to construct a new higher-order predicate term ‘NewPred’ of type ‘pred(char, float)’ from ‘OldPred’ by supplying a value for just the first argument. The solution is the same: use an explicit lambda expression or a forwarding predicate. In either case, the body of the lambda expression or the forwarding predicate must contain a higher-order call with all the arguments supplied.
Once you have created a higher-order predicate term (sometimes known as a closure), the next thing you want to do is to call it. For predicates, you use the builtin goal call/N:
call(Closure)call(Closure1, Arg1)call(Closure2, Arg1, Arg2)A higher-order predicate call. ‘call(Closure)’ just calls the specified higher-order predicate term. The other forms append the specified arguments onto the argument list of the closure before calling it.
For example, the goal
call(Sum123, Result)
would bind Result to the sum of ‘[1, 2, 3]’, i.e. to 6.
For functions, you use the builtin expression apply/N:
apply(Closure)apply(Closure1, Arg1)apply(Closure2, Arg1, Arg2)A higher-order function application. Such a term denotes the result of invoking the specified higher-order function term with the specified arguments.
For example, given the definition of ‘Double’ above, the goal
List = apply(Double, [1, 2, 3])
would be equivalent to
List = scalar_product(2, [1, 2, 3])
and so for a suitable implementation of the function ‘scalar_product/2’
this would bind List to ‘[2, 4, 6]’.
One useful higher-order predicate in the Mercury standard library is ‘solutions/2’, which has the following declaration:
:- pred solutions(pred(T), list(T)). :- mode solutions(in(pred(out) is nondet), out) is det.
The term which you pass to ‘solutions/2’ is a higher-order predicate term. You can pass the name of a one-argument predicate, or you can pass a several-argument predicate with all but one of the arguments supplied (a closure). The declarative semantics of ‘solutions/2’ can be defined as follows:
solutions(Pred, List) is true iff
all [X] (call(Pred, X) <=> list.member(X, List))
and List is sorted without any duplicates.
where ‘call(Pred, X)’
invokes the higher-order predicate term Pred with argument X,
and where ‘list.member/2’
is the standard library predicate for list membership.
In other words, ‘solutions(Pred, List)’ finds all the values of X
for which ‘call(Pred, X)’ is true,
collects these solutions in a list,
sorts the list, and returns that list as its result.
Here is an example: the standard library defines a predicate
‘list.perm(List0, List)’
:- pred list.perm(list(T), list(T)). :- mode list.perm(in, out) is nondet.
which succeeds iff List is a permutation of List0. Hence the following call to solutions
solutions(list.perm([3,1,2]), L)
should return all the possible permutations of the list ‘[3,1,2]’ in sorted order:
L = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].
See also ‘unsorted_solutions/2’ and ‘solutions_set/2’, which are defined in the standard library module ‘solutions’ and documented in the Mercury Library Reference Manual.
In Mercury, it is an error to attempt to unify or to compare two higher-order terms. This is because the question of whether two higher-order terms are equivalent is undecidable in the general case.
Note that the compiler will catch only direct attempts at unifications or comparisons of higher-order terms. Indirect attempts, using for example polymorphic predicates such as ‘(list.append([], [P], [Q])’, will result in an error at run-time rather than at compile-time.
In Mercury, the mode and determinism of a higher-order predicate or function term are generally part of that term’s inst, not its type. This allows a single higher-order predicate to work on argument predicates that differ in their modes and in their determinisms, which is particularly useful for library predicates such as ‘list.map’ and ‘list.foldl’.
Consider ‘list.foldl’, one of the standard fold predicates on lists. The types of its arguments are given by this predicate declaration:
:- pred foldl(pred(L, A, A), list(L), A, A).
The first argument is a higher order value (a predicate in this case), whose types are the types bound by the caller to the type variables L, A and A respectively, where L is the type of the elements in the list in the second argument, and A is the type of the accumulator whose initial and final values are the third and fourth arguments. The job of the predicate passed in the first argument is to combine each element in the list with the current value of the accumulator to generate the next value of the accumulator, so in most calls to ‘list.foldl’, the argument modes and the determinism of that predicate will be
pred(in, in, out) is det
This is a higher order inst: an inst describing the modes of the arguments and the determinism of a higher order value, which in this case is a predicate. A higher order mode is a mode in which the initial and/or final inst is a higher order inst. These can be written like this:
pred(in, in, out) is det >> pred(in, in, out) is det
for a predicate being passed to another predicate or function, and like this
free >> pred(in, in, out) is det
for a predicate being returned from another predicate or function. In practice, it is far more convenient to use the builtin mode constructors ‘in/1’ and ‘out/1’ to write
in(pred(in, in, out) is det) out(pred(in, in, out) is det)
which are each equivalent to the corresponding example just above.
You can use higher order insts and modes in mode declarations like this:
:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.
The ‘in()’ wrapper around the higher order inst here declares the first argument of ‘list.foldl’ to be an input, but the higher order inst inside the wrapper goes further, by specifying the argument modes and the determinism of the predicate that ‘list.foldl’ takes in this mode.
That last qualification is important, because ‘list.foldl’ has several modes, each differing in the argument modes, in the determinism, or both. The set of mode declarations for ‘list.foldl’ includes
:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det. :- mode foldl(in(pred(in, di, uo) is det), in, di, uo) is det. :- mode foldl(in(pred(in, in, out) is semidet), in, in, out) is semidet. :- mode foldl(in(pred(in, in, out) is cc_multi), in, in, out) is cc_multi. :- mode foldl(in(pred(in, di, uo) is cc_multi), in, di, uo) is cc_multi.
That means you can pass predicates with several different argument mode/determinism combinations as the first argument. In the case of ‘list.foldl’, the modes of the accumulator arguments and the determinism of the whole predicate will follow the argument modes and the determinism of the higher-order argument, but one can create predicates (and functions) where this would not be true.
You can give names to such insts and modes using declarations such as
:- inst std_fold_pred == (pred(in, in, out) is det). :- mode std_fold_pred_in == in(pred(in, in, out) is det).
Note that the parentheses around the right hand side of the inst declaration are required, due to the relative precedences of the ‘==’ and ‘is’ operators.
Given these definitions, the declarations
:- mode foldl(in(std_fold_pred), in, in, out) is det. :- mode foldl(std_fold_pred_in, in, in, out) is det.
are both equivalent to
:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.
but they may be more convenient to write, especially in the presence of more arguments. 3
The general form of higher order insts follows one of two patterns, one for predicates, and one for functions.
The pattern for predicates is
(pred) is Determinism pred(Mode) is Determinism pred(Mode1, Mode2) is Determinism …
while the pattern for functions is
(func) = Mode is Determinism func(Mode1) = Mode is Determinism func(Mode1, Mode2) = Mode is Determinism …
In the case of zero-argument predicates and functions, the parentheses around ‘pred’ and ‘func’ are required to tell the compiler that these words are not being used as operators in this case. And, as explained above, one will usually need parentheses around any instances of these patterns in Mercury code.
As a convenience, the language allows you to write a higher order mode using the same syntax as a higher order inst. If HOInst has the form of a higher order inst, then writing HOInst where a mode is required is the same as writing ‘in(HOInst)’, which is in turn equivalent to ‘HOInst >> HOInst’. Therefore, you can omit ‘in()’ around the higher order inst of an input argument. For example,
:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.
can also be written as
:- mode foldl(pred(in, in, out) is det, in, in, out) is det.
though the former may be easier to understand.
As usual, if a predicate or function has only one mode, the ‘pred’ or ‘func’ declaration can be combined with the ‘mode’ declaration. Consider the declaration of a function that computes the intersection of two maps from keys to values:
:- func intersect(func(V, V) = V, map(K, V), map(K, V)) = map(K, V).
One could declare the mode of this function either using a separate mode declaration, like this:
:- mode intersect(in(func(in, in) = out is det), in, in) = (out) is det.
or by combining the mode declaration with the function declaration, like this:
:- func intersect((func(V, V) = V)::in(func(in, in) = out is det),
map(K, V)::in, map(K, V)::in) = (map(K, V)::out) is det.
In both cases, just as for the predicate examples above, the ‘in()’ wrapper around the higher order inst is optional, though in the combined declaration the parentheses must stay.
Mercury also provides builtin ‘inst’ values for use with solver types. These follow the patterns
any_pred is Determinism any_pred(Mode) is Determinism any_pred(Mode1, Mode2) is Determinism … any_func = Mode is Determinism any_func(Mode1) = Mode is Determinism any_func(Mode1, Mode2) = Mode is Determinism …
See Solver types for more details.
In order to call a higher-order term,
the compiler must know its higher-order inst.
This can cause problems when
higher-order terms are placed into a polymorphic collection type
and then extracted,
since the declared mode for the extraction will typically be out
and the higher-order inst information will be lost.
To partially alleviate this problem,
and to make higher-order functional programming easier,
if the term to be called has a function type,
but no higher-order inst information is explicitly provided,
we assume that it has the default higher-order function inst
‘func(in, …, in) = out is det’.
As a consequence of this, a higher-order function term can only be passed where a term with no higher-order inst information is expected if it can be passed where a term with the default higher-order function inst is expected. Higher-order predicate terms can always be passed to such a place, but there is little value in doing so, because there is no default higher-order inst for predicates, and therefore it will not be possible to call those terms.
A higher-order type may optionally specify an inst in the following manner:
(pred) is Determinism pred(Type::Mode) is Determinism pred(Type1::Mode1, Type2::Mode2) is Determinism … (func) = (Type::Mode) is Determinism func(Type1::Mode1) = (Type::Mode) is Determinism func(Type1::Mode1, Type2::Mode2) = (Type::Mode) is Determinism …
When used as argument types of functors in type declarations, types of this form have two effects. First, for any unification that constructs a term using such an argument, there is an additional mode constraint that the argument must be approximated by the inst. In other words, to be mode correct, a program must not construct any term where a functor has an argument that does not have the declared inst, if one is present.
The second effect is that when a unification deconstructs a ground term to extract an argument with such a declared inst, the extracted argument may then be used as if it had that inst.
For example, given this type declaration:
:- type job
---> job(pred(int::out, io::di, io::uo) is det).
the following goal is correct:
:- pred run(job::in, io::di, io::uo) is det.
run(Job, !IO) :-
Job = job(Pred),
Pred(Result, !IO), % Pred has the necessary inst
write_line(Result, !IO).
However, the following would be a mode error:
:- pred bad(job::out) is det. bad(job(p)). % Error: p does not have required mode :- pred p(int::in, io::di, io::out) is det. …
As a new feature, combined higher-order types and insts are only permitted as direct arguments of functors in discriminated unions. So the following examples currently result in errors.
% Error: use on the RHS of equivalence types.
:- type p == (pred(io::di, io::uo) is det).
:- type f == (func(int::in) = (int::out) is semidet).
% Error: use inside a type constructor.
:- type jobs
---> jobs(list(pred(int::out, io::di, io::uo) is det)).
% Error: use in a pred/func declaration.
:- pred p((pred(io::di, io::uo) is det)::in, io::di, io::uo) is det.
:- func f(func(int::in) = (int::out) is semidet, int) = int.
Future versions of the language may allow these forms.
If all instances of a given type are expected to use a single inst or a single mode, there is a convention where programmers will give that inst or mode the same name as the type. This works because types, insts and modes belong to separate namespaces, so the names do not conflict. Nonetheless, there is usually no need to define a named mode. It is clearer to write a mode using ‘in()’ or ‘out()’ around a named inst.
Previous: Default insts for functions, Up: Higher-order insts and modes [Contents]