How to create bidirectional predicates in Prolog?

Question

In Prolog, there are predicates that are bidirectional (or even "multidirectional"), in the sense that one can split the set of variables into input and output variables in many different ways. For example, the predicate number_string acts like a bijection in both directions:

number_string(N, "42"). % finds solution N = 42
number_string(42, S).   % finds solution S = "42"

However, this wonderful property does not seem to be preserved by the conjunction of clauses. For example, consider the following two predicates, which simply translate strings like 3x^2 into pieces of an abstract syntax tree like term(3,2):

parse_stuff(String, term(Coeff, Pow)) :- 
  string_concat(CoeffStr, MonomialStr, String),
  string_concat("x^", PowStr, MonomialStr),
  number_string(Coeff, CoeffStr),
  number_string(Pow, PowStr).

write_stuff(String, term(Coeff, Pow)) :- 
  number_string(Pow, PowStr),
  number_string(Coeff, CoeffStr),
  string_concat("x^", PowStr, MonomialStr),
  string_concat(CoeffStr, MonomialStr, String).

Both predicates are exactly the same, except that the order of the defining clauses on the right hand side is reversed. All clauses on the right hand side are themselves bidirectional.

Here is an example session:

?- parse_stuff("3x^2", X).
X = term(3, 2).

?- parse_stuff(X, term(3, 2)).
ERROR: string_concat/3: Arguments are not sufficiently instantiated

?- write_stuff(X, term(3, 2)).
X = "3x^2".

?- write_stuff("3x^2", X).
ERROR: number_string/2: Arguments are not sufficiently instantiated

Both predicates work only in one way, although they both are obviously bijections, which is pretty sad.

The question consists of two parts (there are two requirements: easy to use, easy to maintain):

1. Is there any robust way to build bidirectional predicates in Prolog?
2. Is it possible to avoid code-duplication (that is, maintaining two versions: one normal, one reversed)?

Maybe there is some flag that tells "reverse the order of clauses if necessary"?

I'm currently using SWI-Prolog 7.1.x, if it's relevant.

---

↓ Jump to my own answer ↓

Answer 1

There are two ways to solve this: either you use an extra argument stating what the order should be and implement a top-predicate that chooses which of your predicates to use on the base of it, or you write a top-predicate that makes the choice by testing which arguments are free with no need for external information. In the latter you will probably use the var/1 or nonvar/1 extra-logical predefined predicates; I used extensively this in making Definite-Clause Grammars reversible, so that they could be used for parsing and for generating text, in that way avoiding a lot of work both in writing the programs and maintaining them.

UPDATE in answer to the additional requirement.

To avoid code duplication you should try to identify the common parts in both versions and define predicates for each part. You then call these predicates where needed instead of having their code in many places. But this is not really useful in your example that is too small: maybe you can try using difference lists and avoiding the concatenations to simplify your predicates.

Answer 2

Systematically chaining bijections [My own answer]

Advantages:

• Produces a bidirectional predicate from a chain of bijection-predicates.
• Avoids any code duplication.
• No explicit specification of the order is required.

Drawbacks:

• Suppresses warnings about unused free variables
• Uses "reflection" (might have impact on performance of compiled code)

Here is how we can chain multiple predicates that are obviously bijections:

% suppresses "Singleton variables" warning for
% a single variable
suppress_singleton_warning(_).

% calls all clauses in a list.
call_all([]).
call_all([F|G]) :- 
  call(F),call_all(G).

% If `X` is a closed term, calls all clauses `FS`
% in left-to-right order.
bijection(X, FS, Y) :-
  suppress_singleton_warning(Y),
  free_variables(X, XVars), 
  XVars == [],
  call_all(FS).

% If `Y` is a closed term, calls all clauses `FS`
% in right-to-left order
bijection(X, FS, Y) :-
  suppress_singleton_warning(X),
  free_variables(Y, YVars), 
  YVars == [],
  reverse(FS, RevFS),
  call_all(RevFS).

Example usage:

% Example: parser/printer that works in both
% directions.
parse_stuff(String, term(Coeff, Pow)) :-
  Clauses = [
    string_concat(CoeffStr, MonomialStr, String),
    string_concat("x^", PowStr, MonomialStr),
    number_string(Coeff, CoeffStr),
    number_string(Pow, PowStr)
  ],
  bijection(String, Clauses, term(Coeff, Pow)).

One can also just as well pass the Clauses directly, no extra variable is needed. This works as expected, in both directions:

 parse_stuff("3x^2", T), write(T), nl,
 parse_stuff(X, term(3,2)), write(X), nl

gives:

term(3,2)
3x^2