Prolog/Higher Order Programming
Introduction[edit | edit source]
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(0,null). digit_german(1,eins). digit_german(2,zwei). ...
To translate a phone number, use
phone_german(,). phone_german([Digit|Ds],[Word|Ws]) :- digit_german(Digit,Word), phone_german(Ds,Ws).
Note the common recursion pattern in
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/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(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 befenit is obvious: by using
map/3, we avoid repeating code fragments so our programs become shorter and easier to read and understand.
See also[edit | edit source]
The following research paper is about higher order programming in prolog and contains numerous examples: