Predicates vs Functions

Appeared in Volume 9/2, May 1996

Keywords: functions.

dominic@aethos.demon.co.uk
Dominic Binks
5th March 1996

Writing one mapping predicate instead of two conversion functions for any non-trivial relation in Prolog almost always requires non-logical features. In Gödel, which is similar to Prolog, but does not have var, nonvar, assert, retract etc., you almost always need to write two conversion functions because you usually have to do two different things depending on what variables are bound, hence var and novar.

fjh@munta.cs.mu.oz.au
Fergus Henderson
6th March 1996

You are mostly right about Prolog, and mostly wrong about Gödel, but I can happily inform you that such conversion functions work just fine in other LP languages, including at least NU-Prolog and Mercury. You just need to use the right coding idiom.

There are two main problems with writing multi-mode predicates in Prolog. The first problem is that Prolog's left-to-right scheduling rule doesn't provide enough support for multi-moded predicates. The second problem is that the standard first-argument indexing is not sufficiently general to handle multi-moded predicates. In order to solve these problems in Prolog, you have to resort to using non-logical features. But in other languages, such as Mercury, there is no need to use non-logical features. Mercury's mode declarations allow the compiler to use a more flexible scheduling rule, and allow the Mercury compiler to do much better indexing.

If you need to do logically different things for conversion in one direction than for conversion in the other direction, then pass down an argument specifying the conversion direction. This idiom is very easy to use, and avoids the need to duplicate code for different modes.

:- module conversion_example.
:- interface.
:- import_module string, term.

:- type direction  ---> term_to_tree ; tree_to_term.

:- type tree  ---> empty ; tree(tree, string, tree).

:- pred convert(direction, tree, term).
:- mode convert(in(bound(tree_to_term)), in, out) is det.
:- mode convert(in(bound(term_to_tree)), out, in) is semidet.

:- implementation.
:- import_module list.

convert(Dir, empty, term__functor(term__atom("empty"), [], Context)) :-
   convert_context(Dir, Context).
convert(Dir, tree(L, Str, R), term__functor(term__atom("tree"),
                                [LT, S, RT], Context)) :-
    S = term__functor(term__string(Str), [], Context),
    convert_context(Dir, Context),
    convert(Dir, L, LT),
    convert(Dir, R, RT).

:- pred convert_context(direction, term__context).
:- mode convert_context(in(bound(tree_to_term)), out) is det.
:- mode convert_context(in(bound(term_to_tree)), in) is det.

convert_context(tree_to_term, Context) :- term__context_init(Context).
convert_context(term_to_tree, _).

Notice that the code in the main convert/3 predicate is shared between the two different modes. The Mercury compiler generates quite different C code for these two modes. Indeed, for convert_context/2, the Mercury compiler can tell from the mode declaration that the first clause is only applicable in the first mode, and that the second clause is only applicable in the second mode, and so the C code generated for the two modes is quite unrelated.

In this example, there is no problem with left-to-right scheduling in Prolog, and it could also easily be converted to Gödel (one particularly easy way is to use the '--convert-to-goedel' option of the Mercury compiler ;-). However, in Prolog and in Gödel, performance will be a problem, because of the lack of indexing. Every call to convert/3 will leave choice points lying around, which will, amongst other things, prevent effective garbage collection.