Пользовательский синтаксис структуры данных в Прологе

Question

В Прологе [H|T] это список, который начинается с H и где остальные элементы находятся в списке T (внутренне представлен с '.'(H, '.'(…))).

Можно ли определить новый синтаксис подобным образом? Например, можно ли определить, что [T~H] это список, который заканчивается H и где остальные элементы находятся в списке T, а затем использовать его так же свободно, как [H|T] в головах и телах предикатов? Можно ли также определить, например, <H|T> быть другой структурой, чем списки?

Answer 1

Можно интерпретировать ваш вопрос буквально. Структура данных в виде списка, где доступ к хвосту может быть выражен без каких-либо вспомогательных предикатов. Ну, это те минус-списки, которые уже использовались в самой первой системе Пролога - той, которую иногда называют Прологом 0 и которая была написана на Алгол-W. Пример из исходного отчета, стр.32 транслитерированный в ISO Пролог:

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

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

По сути, вы берете любой левоассоциативный оператор.

Но я подозреваю, что это не то, что вы хотели. Вы, вероятно, хотите расширение для списков.

Было предпринято несколько попыток сделать это, одна из последних была Prolog III / Prolog IV. Однако, очень похоже на ограничения, вам придется столкнуться с тем, как определить равенство над этими операторами. Другими словами, вам нужно выйти за пределы синтаксического объединения в электронное объединение. Проблема звучит легко в начале, но она пугающе сложна. Простой пример в Прологе IV:

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

Очевидно, это несоответствие. То есть система должна отвечать false. Такого просто нет M, но Пролог IV не может вывести это. Вам бы пришлось решить хотя бы такие проблемы или как-то ужиться с ними.

Если вы действительно хотите в этом разобраться, рассмотрите исследование, начатое с новаторской работы Дж. Маканина:

^{Проблема разрешимости уравнений в свободной полугруппе, Акад. Наук СССР, т.233, №2, 1977.}

Тем не менее, это может быть тот случай, когда есть более простой способ получить то, что вы хотите. Возможно, полностью ассоциативный оператор списка не нужен.

Тем не менее, не ожидайте слишком много выразительности от такого расширения по сравнению с тем, что мы имеем в Прологе, то есть DCG. В частности, общая левая рекурсия все еще будет проблемой для завершения в грамматиках.

Answer 2

Можно расширить или переопределить синтаксис Prolog с помощью предиката iso

 :- op(Precedence, Type, Name).

Где Precedence - это число от 0 до 1200, введите type, если в операторе используется постфикс, префикс или инфикс:

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

и, наконец, имя это имя оператора.

Определения операторов не определяют значение оператора, а только описывают, как его можно использовать синтаксически. Это всего лишь определение, расширяющее синтаксис пролога. Он не дает никакой информации о том, когда предикат будет успешным. Поэтому вам также необходимо описать, когда ваш предикат будет успешным. Чтобы ответить на ваш вопрос, а также привести пример, вы можете определить:

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

где вы объявляете инфиксный оператор [ ~ ]. Это не значит, что это представление списка (пока). Вы можете определить предложение:

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

который соответствует [T~H] списку, который заканчивается на H, и где остальные элементы находятся в списке T.

Также обратите внимание, что не очень безопасно определять предопределенные операторы, такие как [ ] или же ~ потому что вы переписываете их существующий функционал Например, если вы хотите обратиться к файлу, как [файл]. это вернет false, потому что вы переопределили операторы.