2016-10-26 17 views
2

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

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

ответ

2

Можно толковать свой вопрос буквально. Структура данных в виде списка, в которой доступ к хвосту может быть выражен без какого-либо вспомогательного предиката. Ну, это минусовые списки, которые уже использовались в самой первой системе Prolog — той, которую иногда называют Prolog 0 и которая была написана в Algol-W. Пример из the original report, p.32 транслитерации в 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. 

Так по существу вы принимаете какой-либо левоассоциативный оператор.

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

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

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

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

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

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

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

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

1

Можно расширить или переопределить синтаксис Пролога с ИСО предикатом

:- op(Precedence, Type, Name). 

Где Старшинство представляет собой число от 0 до 1200, типа описывает, если operatot используется постфиксным, префикс или инфикс:

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

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

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

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

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

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

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

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

+1

Я не вижу, как '[T ~ H]' будет соответствовать списку, который заканчивается символом 'H', а остальные элементы находятся в списке' T'. Фактически, он даже не соответствует списку: '? - X = [1,2,3], X = [T ~ H]. false.'. – Fatalize

+0

Да, потому что они разные синтаксически, но одинаково семантически. Как я уже говорил выше, [T ~ H] является просто определением синтаксиса, он не говорит, что это список. Семантика исходит из правила [T ~ H]: - is_list ([H | T]). который говорит, что [T ~ H] - это список с головкой H и хвостом T тогда и только тогда, когда is_list [H | T], поэтому синтаксис [T ~ H] истинен, когда [H | T] является списком. – coder

+0

Я до сих пор не вижу, как это отвечает на вопрос. Я хочу что-то такое, что '? - X = [1,2,3], X = [T ~ H] .' возвращает' H = 3, T = [1,2] ', и ваш ответ не предусматривает этого. Как я уже сказал, я даже не знаю, возможно ли это, не касаясь компилятора. – Fatalize