Пролог - необычный синтаксис для списков

Я встретил незнакомый бит синтаксиса Prolog в статье Ли Наиша Логическое программирование более высокого порядка в Prolog. Вот первый пример кода из статьи:

% 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).

Моя путаница с A.As в isort(A.As, Bs) :-. Из контекста он выглядит как альтернативный синтаксис для списков, эквивалент isort([A|As], Bs) :-.

Также N.H.L представляется более удобным способом сказать [N|[H|L]].

Но SWI Prolog не примет этот необычный синтаксис (если я не ошибаюсь).

Кто-нибудь узнает об этом? моя гипотеза правильная? Какой интерпретатор Prolog принимает это как действительный синтаксис?

Ответы

Ответ 1

Точечный оператор использовался для списков в самой первой системе Пролога 1972 года, написанной в Algol-W, иногда называемой Prolog 0. Она вдохновлена ​​аналогичными обозначениями в системах LISP. Следующий пример - из статьи Рождение Пролога Алена Колмерауера и Филиппа Русселя; сами создатели Пролога.

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

В то время [] использовалось NIL.

Следующая версия Prolog, написанная в Fortran by Battani и Meloni, использовала случаи, чтобы отличать атомы и переменные. Затем DECsystem 10 Prolog ввел замену квадратной скобки, заменяя NIL и X.Xs на [] и [X,..Xs], которые в более поздних версиях DECsystem 10 получили [X|Xs] в качестве альтернативы. В ISO Prolog существует только [X|Xs], .(X,Xs) и как канонический синтаксис '.'(X,Xs).

Обратите внимание, что точка имеет много разных параметров в ISO Prolog. Он служит уже как

  • конец токена, за которым следует % или макет, такой как SPACE, NEWLINE, TAB.

  • десятичная точка в номере с плавающей запятой, например 3.14159

  • графический токен char формирование графических токенов как =..

Итак, если вы теперь объявляете . как инфиксный оператор, вы должны быть очень осторожны. Как с тем, что вы пишете, так и с системами Prolog. Одно дополнительное пространство может изменить значение термина. Рассмотрим два списка чисел в обеих обозначениях:

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

Обратите внимание, что после 1 необходимо добавить пробел. В этом контексте дополнительное пространство перед номером может изменить смысл ваших условий. Например:

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

Вот еще один пример, который может быть еще более убедительным:

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

Отрицательные числа требуют круглых скобок внутри точечных списков.

Сегодня осталось только YAP и XSB, которые по-прежнему предлагают infix . по умолчанию – и они делают это по-другому. И XSB даже не распознает синтаксис выше точки: вам нужны круглые скобки вокруг некоторых неотрицательных чисел.

Вы написали, что N.H.L представляется более удобным способом сказать [N|[H|L]]. Существует простое правило для упрощения таких выражений в ISO Prolog: всякий раз, когда вы видите внутри списка токены | и [ сразу после друг друга, вы можете заменить их на , (и удалить соответствующие ] с правой стороны). Итак, теперь вы можете написать: [N,H|L], который не выглядит , который плох.

Вы можете использовать это правило также в другом направлении. Если у нас есть список [1,2,3,4,5], мы можем использовать | как "лезвие бритвы" так: [1,2,3|[4,5]].

Еще одно замечание, так как вы читаете статью Наиша: тем не менее, хорошо понят, что нужен только call/N! И ISO Prolog поддерживает call/1, call/2 до call/8.

Ответ 2

Да, вы правы, это точка, которую он перечисляет оператору infix. Это действительно требуется по стандарту ISO Prolog, но обычно скрыто. Я нашел (и использовал) этот синтаксис некоторое время назад:

:- 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 */

Мне посоветовали против этого. Эффективно синтаксис [A | B] - это эволюция. оператора, введенного для удобочитаемости.

OT: какой именно код?

код выше его моя попытка подсластить Prolog с функциями. А именно, вводит по запросу с помощью $ временные переменные, требуемые (например) арифметическими выражениями

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

каждый $вводит переменную. После расширения мы имеем более традиционный факт /2

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

Если у нас есть много выражений, это может быть полезно...

Ответ 3

Этот синтаксис происходит от NU-Prolog. См. здесь. Вероятно, это просто нормальный функтор списка. '/2 переопределяется как инфиксный оператор, без необходимости иметь пустой пустой список:

?- 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)