Search code examples
data-structuresprologsyntactic-sugarunification

Custom data structure syntax in Prolog


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?


Solution

  • 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.