Синтаксис и семантика Пролога

Синтаксис соответственно и семантика Пролога . , языка программирования , представляют собой наборы правил, которые определяют, как пишется программа на Прологе и как она интерпретируется Правила изложены в стандарте ISO/IEC 13211. ^[1] хотя существуют различия в реализациях Пролога .

Типы данных

Пролог является динамически типизированным . Он имеет единственный тип данных — term , который имеет несколько подтипов: атомы , числа , переменные и составные термины .

Атом . — это имя общего назначения, не имеющее внутреннего значения Он состоит из последовательности символов, которая анализируется программой чтения Пролога как единое целое. Атомы обычно представляют собой простые слова в коде Пролога, написанные без специального синтаксиса. Однако атомы, содержащие пробелы или некоторые другие специальные символы, должны быть заключены в одинарные кавычки. Атомы, начинающиеся с заглавной буквы, также необходимо заключать в кавычки, чтобы отличать их от переменных. Пустой список, написанный [], тоже атом. Другие примеры атомов включают x, blue, 'Taco', и 'some atom'.

Числа могут быть числами с плавающей запятой или целыми числами . Многие реализации Пролога также предоставляют неограниченные целые и рациональные числа .

Переменные обозначаются строкой, состоящей из букв, цифр и символов подчеркивания и начинающейся с заглавной буквы или подчеркивания. Переменные очень похожи на переменные в логике, поскольку они являются заполнителями для произвольных терминов. Переменная может быть создана (привязана к определенному термину) посредством унификации . Одно подчеркивание ( _) обозначает анонимную переменную и означает «любой термин». В отличие от других переменных, подчеркивание не представляет одно и то же значение везде, где оно встречается в определении предиката.

Составной терм состоит из атома, называемого «функтором», и ряда «аргументов», которые также являются термами. Составные термины обычно записываются в виде функтора, за которым следует список терминов-аргументов, разделенных запятыми, который содержится в круглых скобках. Количество аргументов называется арностью терма . Атом можно рассматривать как составной термин с нулевой арностью .

Примеры сложных терминов: truck_year('Mazda', 1986) и 'Person_Friends'(zelda,[tom,jim]). Составные термины с функторами, объявленными как операторы, могут быть записаны в префиксной или инфиксной записи. Например, условия -(z), +(a,b) и =(X,Y) также можно записать как -z, a+b и X=Y, соответственно. Пользователи могут объявлять произвольные функторы как операторы с различным приоритетом, чтобы обеспечить нотации, специфичные для предметной области. Обозначение f/n обычно используется для обозначения термина с функтором f и арностью n .

Особые случаи сложных терминов:

Списки определяются индуктивно: атом [] это список. Составной термин с функтором . (точка) и арность 2, второй аргумент которой является списком, сам является списком. Для обозначения списков существует специальный синтаксис: .(A, B) эквивалентно [A|B]. Например, список .(1, .(2, .(3, []))) также можно записать как [1 | [2 | [3 | []]]]или даже более компактно, как [1,2,3].
Строки : последовательность символов, заключенная в кавычки, эквивалентна списку (числовых) кодов символов, обычно в локальной кодировке символов или Unicode , если система поддерживает Unicode.

Пролог-программы

Программы на Прологе описывают отношения, определяемые посредством предложений. Чистый Пролог ограничен предложениями Хорна , полным по Тьюрингу первого порядка подмножеством логики предикатов . Существует два типа предложений: факты и правила. Правило имеет вид

Head :- Body.

и читается как «Голова верна, если Тело истинно». правила Тело правила состоит из вызовов предикатов, которые называются целями . Встроенный предикат ,/2 (имеется в виду 2-арный оператор с именем ,) обозначает соединение целей, а ;/2 обозначает дизъюнкцию . Союзы и дизъюнкции могут появляться только в теле, а не в начале правила.

Предложения с пустым телом называются фактами . Пример факта:

cat(tom).

что эквивалентно правилу:

cat(tom) :- true.

другой пример:

X is 3+2.

и когда вы запустите его, результат будет

 X=5
 Yes.

Встроенный предикат true/0 всегда верно.

Оценка

Выполнение программы на Прологе инициируется сообщением пользователем единственной цели, называемой запросом. Логично, что механизм Пролога пытается найти решение, опровергающее отрицательный запрос. Метод разрешения, используемый Прологом, называется разрешением SLD . Если отрицательный запрос можно опровергнуть, из этого следует, что запрос с соответствующими привязками переменных является логическим следствием программы. В этом случае пользователю сообщается обо всех сгенерированных привязках переменных, и считается, что запрос выполнен успешно. С функциональной точки зрения стратегию выполнения Пролога можно рассматривать как обобщение вызовов функций в других языках, единственное отличие состоит в том, что одному вызову может соответствовать несколько заголовков предложений. В этом случае система создает точку выбора, объединяет цель с заголовком предложения первой альтернативы и продолжает работу над целями этой первой альтернативы. Если какая-либо цель не удалась в ходе выполнения программы, все привязки переменных, которые были сделаны с момента создания самой последней точки выбора, отменяются, и выполнение продолжается со следующей альтернативой этой точки выбора. Такая стратегия выполнения называется хронологической. обратный путь .

mother_child(trude, sally).
 
father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).
 
sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).
 
parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

Это приводит к тому, что следующий запрос оценивается как истинный:

?- sibling(sally, erica).
Yes

Это достигается следующим образом: изначально единственный совпадающий заголовок предложения для запроса sibling(sally, erica) является первым, поэтому доказательство запроса эквивалентно доказательству тела этого предложения с соответствующими привязками переменных, т. е. соединением (parent_child(Z,sally), parent_child(Z,erica)). Следующая цель, которую необходимо доказать, — это крайняя левая цель этого соединения, т. е. parent_child(Z, sally). Этой цели соответствуют два заголовка статей. Система создает точку выбора и пробует первую альтернативу, тело которой father_child(Z, sally). Эту цель можно доказать, используя тот факт father_child(tom, sally), поэтому привязка Z = tom генерируется, и следующей целью, которую необходимо доказать, является вторая часть приведенного выше союза: parent_child(tom, erica). Опять же, это можно доказать соответствующим фактом. Поскольку все цели могут быть доказаны, запрос завершается успешно. Поскольку запрос не содержал переменных, пользователю не сообщается ни о каких привязках. Запрос с переменными, например:

?- father_child(Father, Child).

перечисляет все действительные ответы при возврате.

Обратите внимание, что в приведенном выше коде запрос ?- sibling(sally, sally). также преуспевает. При желании можно было бы добавить дополнительные цели для описания соответствующих ограничений.

Циклы и рекурсия

Итерационные алгоритмы могут быть реализованы с помощью рекурсивных предикатов. Системы Пролога обычно реализуют хорошо известную технику оптимизации, называемую оптимизацией хвостового вызова (TCO), для детерминированных предикатов, демонстрирующих хвостовую рекурсию или, в более общем плане, хвостовые вызовы: кадр стека предложения отбрасывается перед выполнением вызова в хвостовой позиции. Таким образом, детерминированные предикаты хвостовой рекурсии выполняются с постоянным пространством стека, как циклы в других языках.

Порезы

Разрез ( !) внутри правила не позволит Прологу выполнить возврат любых предикатов за вырезом:

predicate(X) :- one(X), !, two(X).

потерпит неудачу, если первое найденное значение X для чего one(X) правда, приводит к two(X) будучи ложным.

Анонимные переменные

Анонимные переменные _ никогда не привязаны к значению и могут использоваться в предикате несколько раз.

Например, поиск в списке по заданному значению:

contains(V, [V|_]).
contains(V, [_|T]) :- contains(V, T).

Отрицание

Встроенный предикат Пролога \+/1 предоставляет отрицание как отказ , что позволяет проводить немонотонные рассуждения. Цель \+ illegal(X) в правиле

legal(X) :- \+ illegal(X).

оценивается следующим образом: Пролог пытается доказать illegal(X). Если доказательство этой цели может быть найдено, первоначальная цель (т. е. \+ illegal(X)) терпит неудачу. Если доказательств не найдено, первоначальная цель достигнута. Таким образом, \+/1 префиксный оператор называется «недоказуемым» оператором, поскольку запрос ?- \+ Goal. успешна, если цель недоказуема. Этот вид отрицания является правильным , если его аргумент «основной» (т. е. не содержит переменных). Разумность теряется, если аргумент содержит переменные. В частности, запрос ?- legal(X). теперь нельзя использовать для перечисления всего, что является законным.

Семантика

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

predicate1(X) :-
  predicate2(X,X).
predicate2(X,Y) :-
  predicate1(X),
  X \= Y.

Учитывая этот порядок, любой запрос формы

?- predicate1(atom).

будет повторяться до тех пор, пока стек не будет исчерпан. Однако если последние 3 строки были изменены на:

predicate2(X,Y) :-
  X \= Y,
  predicate1(X).

тот же запрос приведет к результату «Нет» за очень короткое время.

Определенные грамматики предложений

Существует специальная нотация, называемая грамматиками определенного предложения ( DCG ). Правило, определенное через -->/2 вместо :-/2 расширяется препроцессором ( expand_term/2, средство, аналогичное макросам в других языках) в соответствии с несколькими простыми правилами переписывания, в результате чего получаются обычные предложения Пролога. В частности, переписывание снабжает предикат двумя дополнительными аргументами, которые можно использовать для неявного связывания состояния, аналогично монадам в других языках. DCG часто используются для написания анализаторов или генераторов списков, поскольку они также предоставляют удобный интерфейс для перечисления различий.

Пример парсера

Более крупный пример покажет потенциал использования Пролога при синтаксическом анализе .

Учитывая предложение, выраженное в форме Бэкуса-Наура :

<sentence>    ::=  <stat_part>
<stat_part>   ::=  <statement> | <stat_part> <statement>
<statement>   ::=  <id> = <expression> ;
<expression>  ::=  <operand> | <expression> <operator> <operand>
<operand>     ::=  <id> | <digit>
<id>          ::=  a | b
<digit>       ::=  0..9
<operator>    ::=  + | - | *

Это можно написать на Прологе с использованием DCG, что соответствует прогнозирующему анализатору с упреждающим просмотром одного токена:

sentence(S)                --> statement(S0), sentence_r(S0, S).
sentence_r(S, S)           --> [].
sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S).
 
statement(assign(Id,E)) --> id(Id), [=], expression(E), [;].
 
expression(E) --> term(T), expression_r(T, E).
expression_r(E, E)  --> [].
expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E).
expression_r(E0, E) --> [-], term(T), expression_r(minus(E0, T), E).
 
term(T)       --> factor(F), term_r(F, T).
term_r(T, T)  --> [].
term_r(T0, T) --> [*], factor(F), term_r(times(T0, F), T).
 
factor(id(ID))   --> id(ID).
factor(digit(D)) --> [D], { (number(D) ; var(D)), between(0, 9, D)}.
 
id(a) --> [a].
id(b) --> [b].

Этот код определяет связь между предложением (представленным в виде списка токенов) и его абстрактным синтаксическим деревом (AST). Пример запроса:

?- phrase(sentence(AST), [a,=,1,+,3,*,b,;,b,=,0,;]).
AST = seq(assign(a, plus(digit(1), times(digit(3), id(b)))), assign(b, digit(0))) ;

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

?- length(Tokens, _), phrase(sentence(AST), Tokens).
 Tokens = [a, =, a, (;)], AST = assign(a, id(a)) ;
 Tokens = [a, =, b, (;)], AST = assign(a, id(b))
 etc.

См. также

Сравнение реализаций Пролога

Ссылки

^ ISO/IEC 13211: Информационные технологии. Языки программирования. Пролог . Международная организация по стандартизации , Женева.

[1] ISO/IEC 13211: Информационные технологии. Языки программирования. Пролог . Международная организация по стандартизации , Женева.

[1]