Prolog Language
Различия
Поиск…
Вступление
Разностные списки в Прологе означают концепцию, чтобы знать структуру списка до точки . Оставшийся список можно оставить без привязки до полной оценки предиката. Список, где его конец неизвестен, называется открытым списком , заканчивающимся отверстием . Этот метод особенно полезен для проверки сложных синтаксисов или грамматик.
Известные грамотные грамматики (DCG) используют разностные списки для работы под капотом.
Основное использование
Рассмотрим предикат sumDif/2 , проверенный, если структура списка соответствует нескольким ограничениям. Первый термин представляет собой список для анализа, а второй термин - другой список, который содержит часть первого списка, который неизвестен нашим ограничениям.
Для демонстрации sumDif/2 распознает арифметическое выражение для суммирования n целых чисел.
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
Мы знаем, что первым элементом списка для проверки является целое число, здесь иллюстрируется X , за которым следует символ сложения ( + ). Оставшийся список, который еще предстоит обработать позже ( OpenList ), остается неизменным на этом уровне. Hole представляет собой часть списка, которую нам не нужно проверять.
Давайте дадим другое определение предиката sumDif/2 для завершения проверки арифметического выражения:
sumDif([X|Hole], Hole) :-
integer(X).
Мы ожидаем, что целое число называется X непосредственно в начале открытого списка. Интересно, что оставшаяся часть списка Hole остается неизвестной, и это целая цель Разностных списков: структура списка известна до определенной точки.
Наконец, недостающая часть появляется, когда оценивается список:
?- sumDif([1,+,2,+,3], []).
true
Это когда предикат используется, когда упоминается конец списка, здесь [] указывает, что список не содержит дополнительных элементов.
Оценить арифметическое выражение
Давайте определим грамматику, позволяющую нам выполнять дополнения, умножения с использованием скобок. Чтобы добавить больше значения в этот пример, мы собираемся вычислить результат арифметического выражения. Резюме грамматики:
выражение → раз
выражение → times '+' выражение
раз → элемент
раз → элемент '*' раз
элемент → "целое число"
элемент → '(' выражение ')'
Все предикаты имеют arity of 3, потому что им нужно открыть список, отверстие и значение арифметического выражения.
expression(Value, OpenList, FinalHole) :-
times(Value, OpenList, FinalHole).
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
times(Value, OpenList, FinalHole) :-
element(Value, OpenList, FinalHole).
times(TimesValue, OpenList, FinalHole) :-
element(Value1, OpenList, ['*'|Hole1]),
times(Value2, Hole1, FinalHole),
TimesValue is Value1 * Value2.
element(Value, [Value|FinalHole], FinalHole) :-
integer(Value).
element(Value, ['('|OpenList], FinalHole) :-
expression(Value, OpenList, [')'|FinalHole]).
Чтобы правильно объяснить принцип дыр и как вычисляется значение, давайте возьмем expression второго предложения:
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
Открытый список обозначается предикатом OpenList . Первым элементом для проверки является то, что предшествует символу добавления ( + ) . Когда первый элемент проверяется, за ним сразу следует символ добавления и продолжением списка, называемого Hole1 . Мы знаем, что Hole1 является следующим элементом для проверки и может быть другим expression , поэтому Hole1 тогда является термином, заданным для expression предиката.
Значение всегда представляется в первом члене. В этом разделе он определяется суммой Value1 (все перед символом добавления) и Value2 (все после символа добавления).
Наконец, выражение можно оценить.
?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31