Custom data structure syntax in Prolog

Question

In Prolog, [H|T] is the list that begins with H and where the remaining elements are in the list T (internally represented with '.'(H, '.'(…))).

Is it possible to define new syntax in a similar fashion? For example, is it possible to define that [T~H] is the list that ends with H and where the remaining elements are in the list T, and then use it as freely as [H|T] in heads and bodies of predicates? Is it also possible to define e.g. <H|T> to be a different structure than lists?

Answer 1

It is possible to extend or redefine syntax of Prolog with iso predicate

 :- op(Precedence, Type, Name).

Where Precedence is a number between 0 and 1200, Type describe if the operatot is used postfix,prefix or infix:

infix: xfx, xfy, yfx
prefix: fx, fy
suffix: xf, yf

and finally name is the operator's name.

Operator definitions do not specify the meaning of an operator, but only describe how it can be used syntactically. It is only a definition extending the syntax of Prolog. It doesn't gives any information about when a predicate will succeed. So you need also to describe when your predicate succeeds. To answer your question and also give an example you could define :

:- op( 42, xfy, [ ~ ]).

where you declare an infix operator [ ~ ]. This doesn't means that is a representation of a list (yet). You could define clause:

[T ~ H]:-is_list([H|T]).

which matches [T~H] with the list that ends with H and where the remaining elements are in the list T.

Note also that it is not very safe to define predefined operators like [ ] or ~ because you overwrite their existing functionality. For example if you want to consult a file like [file]. this will return false because you redefined operators.

Answer 2

One can interpret your question literally. A list-like data structure, where accessing the tail can be expressed without any auxiliary predicate. Well, these are the minus-lists which were already used in the very first Prolog system — the one which is sometimes called Prolog 0 and which was written in Algol-W. An example from the original report, p.32 transliterated into ISO Prolog:

t(X-a-l, X-a-u-x). 

?- t(nil-m-e-t-a-l, Pluriel).
Pluriel = nil-m-e-t-a-u-x.

So essentially you take any left-associative operator.

But, I suspect, that's not what you wanted. You probably want an extension to lists.

There have been several attempts to do this, one more recent was Prolog III/Prolog IV. However, quite similar to constraints, you will have to face how to define equality over these operators. In other words, you need to go beyond syntactic unification into E-unification. The problem sounds easy in the beginning but it is frightening complex. A simple example in Prolog IV:

>> L = [a] o M, L = M o [z].
M ~ list,
L ~ list.

Clearly this is an inconsistency. That is, the system should respond false. There is simply no such M, but Prolog IV is not able to deduce this. You would have to solve at least such problems or get along with them somehow.

In case you really want to dig into this, consider the research which started with J. Makanin's pioneering work:

^{The Problem of Solvability of Equations in a Free Semi-Group, Akad. Nauk SSSR, vol.233, no.2, 1977.}

That said, it might be the case that there is a simpler way to get what you want. Maybe a fully associative list operator is not needed.

Nevertheless, do not expect too much expressiveness from such an extension compared to what we have in Prolog, that is DCGs. In particular, general left-recursion would still be a problem for termination in grammars.