Prolog/Higher Order Programming

Introduction

Higher-order programming means writing programs that take other programs as input and/or return still other programs as output. Higher-order programming is common in functional programming, but can be in done in Prolog as well.

As an example, suppose you are writing a speech synthesis application that reads out phone numbers aloud. We might have a predicate digit_english/2 that relates Prolog integers 0 through 9 to English words (as symbols):

digit_english(0,zero).
digit_english(1,one).
digit_english(2,two).
...

Now, to translate a phone number, define:

phone_english([],[]).
phone_english([Digit|Ds],[Word|Ws]) :-
    digit_english(Digit,Word),
    phone_english(Ds,Ws).

Now, suppose we want to add support for another language, say, German. You define digit_german:

digit_german(0,null).
digit_german(1,eins).
digit_german(2,zwei).
...

To translate a phone number, use phone_german:

phone_german([],[]).
phone_german([Digit|Ds],[Word|Ws]) :-
    digit_german(Digit,Word),
    phone_german(Ds,Ws).

Note the common recursion pattern in phone_english/2 and phone_german. You've probably seen that many times before, even written it several times. It can be summed up as:

Base case: relate the empty list to itself.
Recursive case: relate the first element of the first list to the first element of the second via some predicate, then recur on the tails of both lists.

This pattern can be captured by a higher-order predicate generally known as map/3 (but not defined by standard Prolog):

map([],P,[]).
map([X|Xs],P,[Y|Ys]) :-
    Goal =.. [P,X,Y],
    call(Goal),
    map(Xs,P,Ys).

In Prolog, we cannot write P(X,Y) since the head of a functor must be a symbol. Therefore, we use the infix operator =.. that unifies its first argument with a term built from its right argument, which must be a list. The first element, which must be a symbol, becomes the functor, the rest its arguments. We then apply call/1 to the term we constructed to invoke it as a Prolog goal. Note that many Prolog implementations also define call/2, call/3, ... built-in predicates which construct a callable term out of the given arguments (with the first argument being the principal functor), so that the above code example can be also written as

map([],P,[]).
map([X|Xs],P,[Y|Ys]) :-
    call(P,X,Y),
    map(Xs,P,Ys).

We can now redefine phone_english/2 and phone_german/2 as:

phone_english(P,E) :- map(P,digit_english,E).
phone_german(P,G) :- map(P,digit_german,G).

Both predicates still work in both directions and non-determinism is preserved.

The benefit is obvious: by using map/3, we avoid repeating code fragments so our programs become shorter and easier to read and understand.

Introduction

See also