Prolog - unusual cons syntax for lists

问题:

I have come across an unfamiliar bit of Prolog syntax in Lee Naish's paper Higher-order logic programming in Prolog. Here is the first code sample from the paper:

% insertion sort (simple version)
isort([], []).
isort(A.As, Bs) :-
    isort(As, Bs1),
    isort(A, Bs1, Bs).

% insert number into sorted list
insert(N, [], [N]).
insert(N, H.L, N.H.L) :-
    N =< H.
insert(N, H.LO, H.L) :-
    N > H,
    insert(N, LO, L).

My confusion is with A.As in isort(A.As, Bs) :-. From the context, it appears to be an alternate cons syntax for lists, the equivalent of isort([A|As], Bs) :-.

As well N.H.L appears to be a more convenient way to say [N|[H|L]].

But SWI Prolog won't accept this unusual syntax (unless I'm doing something wrong).

Does anyone recognize it? is my hypothesis correct? Which Prolog interpreter accepts that as valid syntax?

回答1:

The dot operator was used for lists in the very first Prolog system of 1972, written in Algol-W, sometimes called Prolog 0. It is inspired by similar notation in LISP systems. The following exemple is from the paper The birth of Prolog by Alain Colmerauer and Philippe Roussel – the very creators of Prolog.

+ELEMENT(*X, *X.*Y).
+ELEMENT(*X, *Y.*Z) -ELEMENT(*X, *Z).

At that time, [] used to be NIL.

The next Prolog version, written in Fortran by Battani & Meloni, used cases to distinguish atoms and variables. Then DECsystem 10 Prolog introduced the square bracket notation replacing nil and X.Xs with [] and [X,..Xs] which in later versions of DECsystem 10 received [X|Xs] as an alternative. In ISO Prolog, there is only [X|Xs], .(X,Xs), and as canonical syntax '.'(X,Xs).

Please note that the dot has many different rôles in ISO Prolog. It serves already as

• end token when followed by a % or a layout character like SPACE, NEWLINE, TAB.

• decimal point in a floating point number, like 3.14159

• graphic token char forming graphic tokens as =..

So if you are now declaring . as an infix operator, you have to be very careful. Both with what you write and what Prolog systems will read. A single additional space can change the meaning of a term. Consider two lists of numbers in both notations:

[1,2.3,4]. [5].
1 .2.3.4.[]. 5.[].

Please note that you have to add a space after 1. In this context, an additional white space in front of a number may change the meaning of your terms. Like so:

[1|2.3]. [4]. 5. [].
1 .2.3. 4.[]. 5. [].

Here is another example which might be even more convincing:

[1,-2].
1.(-2).[].

Negative numbers require round brackets within dot-lists.

Today, there is only YAP and XSB left that still offer infix . by default – and they do it differently. And XSB does not even recognize above dot syntax: you need round brackets around some of the nonnegative numbers.

You wrote that N.H.L appears to be a more convenient way to say [N|[H|L]]. There is a simple rule-of-thumb to simplify such expressions in ISO Prolog: Whenever you see within a list the tokens | and [ immediately after each other, you can replace them by , (and remove the corresponding ] on the right side). So you can now write: [N,H|L] which does not look that bad.

You can use that rule also in the other direction. If we have a list [1,2,3,4,5] we can use | as a "razor blade" like so: [1,2,3|[4,5]].

---

Another remark, since you are reading Naish's paper: In the meantime, it is well understood that only call/N is needed! And ISO Prolog supports call/1, call/2 up to call/8.

回答2:

Yes, you are right, the dot it's the list cons infix operator. It's actually required by ISO Prolog standard, but usually hidden. I found (and used) that syntax some time ago:

:- module(eog, []).
:- op(103, xfy, (.)).

% where $ARGS appears as argument, replace the call ($ARGS) with a VAR
% the calle goes before caller, binding the VAR (added as last ARG)
funcs(X, (V, Y)) :-
    nonvar(X),
    X =.. W.As,

    % identify meta arguments
    (   predicate_property(X, meta_predicate M)
        % explicitly exclude to handle test(dcg)
        % I'd like to handle this case in general way...
    ,   M \= phrase(2, ?, ?)
    ->  M =.. W.Ms
    ;   true
    ),

    seek_call(As, Ms, Bs, V),
    Y =.. W.Bs.

% look for first $ usage
seek_call([], [], _Bs, _V) :-
    !, fail.
seek_call(A.As, M.Ms, A.Bs, V) :-
    M @>= 0, M @=< 9, % skip meta arguments
    !, seek_call(As, Ms, Bs, V).
seek_call(A.As, _, B.As, V) :-
    nonvar(A),
    A = $(F),
    F =.. Fp.FAs,
    (   current_arithmetic_function(F) % inline arith
    ->  V = (PH is F)
    ;   append(FAs, [PH], FBs),
        V =.. Fp.FBs
    ),
    !, B = PH.
seek_call(A.As, _.Ms, B.As, V) :-
    nonvar(A),
    A =.. F.FAs,
    seek_call(FAs, Ms, FBs, V),
    !, B =.. F.FBs.
seek_call(A.As, _.Ms, A.Bs, V) :-
    !, seek_call(As, Ms, Bs, V).

:- multifile user:goal_expansion/2.
user:goal_expansion(X, Y) :-
    ( X = (_ , _) ; X = (_ ; _) ; X = (_ -> _) )
    -> !, fail % leave control flow unchanged (useless after the meta... handling?)
    ;  funcs(X, Y).

/* end eog.pl */

I was advised against it. Effectively, the [A|B] syntax it's an evolution of the . operator, introduced for readability.

OT: what's that code?

the code above it's my attempt to sweeten Prolog with functions. Namely, introduces on request, by means of $, the temporary variables required (for instance) by arithmetic expressions

fact(N, F) :-
     N > 1 -> F is N * $fact($(N - 1)) ; F is 1.

each $ introduce a variable. After expansion, we have a more traditional fact/2

?- listing(fact).
plunit_eog:fact(A, C) :-
    (   A>1
    ->  B is A+ -1,
        fact(B, D),
        C is A*D
    ;   C is 1
    ).

Where we have many expressions, that could be useful...

回答3:

This syntax comes from NU-Prolog. See here. It's probably just the normal list functor '.'/2 redefined as an infix operator, without the need for a trailing empty list:

?- L= .(a,.(b,[])).
L = [a,b]
Yes (0.00s cpu)
?- op(500, xfy, '.').
Yes (0.00s cpu)
?- L = a.b.[].
L = [a,b]
Yes (0.00s cpu)