Next: Object Centered Programming in Up: HiLog Programming Previous: HiLog Programming

# Generic Programs

Because one can use a complex term as a predicate in HiLog, one can program ``generic predicates.'' For example, consider a predicate function, i.e., a function that takes a predicate and returns another predicate. An interesting such predicate function might be `closure`. `closure` takes a binary predicate and returns a predicate for the transitive closure of the corresponding binary relation. So for example, `closure(parent)` would be the transitive closure of the `parent` relation, i.e., the ancestor relation, and `closure(child)` would be the descendent relation. We can define this `closure` predicate function in HiLog as follows:

```closure(R)(X,Y) :- R(X,Y).
closure(R)(X,Y) :- R(X,Z), closure(R)(Z,Y).
```
Now given any binary relation, one can use use this definition to compute its closure. For example, we can define a binary predicate, `parent` as follows:
```:- hilog parent.
parent(able,eve).
parent(cain,eve).
etc
```
and then we can use the generic definition of closure to find anscestors:
```| ?- closure(parent)(cain,X).
etc.
```

Notice that we must declare the symbol `parent` to be a hilog symbol using the directive:

```:- hilog parent.
```
This is necessary because the XSB system allows a mixture of HiLog programming and Prolog programming, and the system distinguishes between HiLog symbols and Prolog symbols in how it represents them. The HiLog term t0(t1,t2,...,tn) is represented as the Prolog term apply(t0,t1,t2,...,tn). Thus the system must know, for example, that `parent` is a hilog symbol so it knows to represent `parent(cain,adam) as the Prolog term \verb`apply(parent,cain,adam)|.

Another useful generic predicate is `map`. `map` takes a binary function and returns a function that when given a list, returns the list that results from applying that function to each element of the given list. Again, we can write a natural definition for it:

```map(F)([],[]).
map(F)([X|Xs],[Y|Ys]) :- F(X,Y), map(F)(Xs,Ys).
```

So, for example, we can use this generic function to add one to every element of a list, double every element of a list, or square every element of a list. Given the definitions:

```:- hilog successor,double,square.
successor(X,Y) :- Y is X+1.
double(X,Y) :- Y is X+X.
square(X,Y) :- Y is X*X.
```
we can do
```| ?- [(hilog)].
[Compiling ./hilog]
% Specialising partially instantiated calls to apply/3
[hilog compiled, cpu time used: 0.59 seconds]

yes
| ?- map(successor)([2,4,6,8,10],L).

L = [3,5,7,9,11];

no
| ?- map(double)([2,4,6,8,10],L).

L = [4,8,12,16,20];

no
| ?-
```

This definition of `map` is a bit more general than the one normally found in functional languages, which is not surprising since Prolog is a relational language and this is really a relational definition. For example, `map(successor)` is relation a relation over pairs of lists. If we give to `map` a nonfunctional relation, then the map of that relation is also nonfunctional.

(Think of an interesting example.)

Another interesting example is the generic function `twice`. `twice` takes an input function (or relation) and returns a function that applies the input function twice. (From DHDWarren and MVanEmden.) In standard mathematical notation: twice(f)(x) = f(f(x)). By turning `twice` into a relation and essentially writing down this definition, we get:

```twice(F)(X,R) :- F(X,U), F(U,R).
```
And we can run it:
```| ?- [twice].
[Compiling ./twice]
[twice compiled, cpu time used: 0.659 seconds]

yes
| ?- twice(successor)(1,X).

X = 3;

no
| ?- twice(twice(successor))(1,X).

X = 5;

no
| ?- twice(twice(square))(2,X).

X = 65536;

no
| ?- twice(twice(twice(double)))(1,X).

X = 256;

no
| ?-
```
This interesting thing here is that `twice(f)` for a function `f` produces a function similar to `f`, so we can apply `twice` to a result of `twice` and get a quadrupling (or octupling, ...) effect.

We can add another rule for `twice` (and make it a hilog symbol):

```:- hilog twice.
twice(X,twice(X)).
```
This rule says that applying `twice` itself to a function argument gives a term representing the resulting function. So now we can even apply twice to itself to produce a function that we can then apply to one of basic functions to produce a function to apply to a number (that lives in the house that Jack built), as follows:
```| ?- twice(twice)(double,Fun),Fun(1,X).

Fun = twice(twice(double))
X = 16;

no
| ?- twice(twice(twice))(double,Fun),Fun(1,X).

Fun = twice(twice(twice(twice(double))))
X = 65536;

no
| ?- twice(twice(twice))(successor,Fun),Fun(1,X).

Fun = twice(twice(twice(twice(successor))))
X = 17;

no
| ?-
```

DHDWarren (and a followup paper by Martin vanEmden et al.) explore issues around using Prolog to implement higher-order aspects of functional languages. This example is taken from there, but is expressed in HiLog's syntax, rather than Prolog's. HiLog's syntax makes the development more perspicuous.

(Do we(I) want to develop a bit more of lambda calculus, and show how to do more general higher-order programming?)

Next: Object Centered Programming in Up: HiLog Programming Previous: HiLog Programming
David S. Warren
1999-07-31