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

Докладніше: Пролог (мова програмування)

Синтаксис та семантика мови програмування Пролог є множиною правил, що визначає, як пишеться програма мовою Пролог, і як вона інтерпретується. Ці правила викладено у стандарті ISO/IEC (13211), хоча в ^[en] є відмінності.

Типи даних

Пролог є динамічно типізованою мовою. Вона має єдиний тип даних, терм, що має декілька підтипів: атоми, числа, змінні та складені терми.

Атом це загальна назва без притаманного значення. Він складається з послідовності символів, що аналізується читачем Прологу як єдине ціле. Як правило, атоми є простими словами у коді Прологу, написаними без спеціального синтаксису. Однак, атоми, що містять пропуски, або певні інші спеціальні символи, мають братися в одинарні лапки. Атоми, що починаються з великої літери, також повинні братися в лапки, щоби їх можна було відрізнити від змінних. Порожній список, що пишеться як [], також є атомом. Інші приклади атомів: x, синій, 'Пиріжок', 'якийсь атом'.

Числа можуть бути з рухомою комою, або цілими. Багато реалізацій Прологу пропонують також необмежені цілі та дійсні числа.

Змінні позначаються стрічками, що складаються з літер, цифр та символів підкреслення, і починаються з великої літери або символу підкреслення. Змінні дуже подібні до змінних в логіці в тім, що вони є позначками-заповнювачами для довільних термів. Змінну може бути конкретизовано (зв'язано дорівнюванням певному термові) через уніфікацію. Поодиноке підкреслення (_) позначає анонімну змінну і значить «будь-який терм». На відміну від інших змінних, підкреслення не представляє однакове значення всюди, де воно зустрічається у визначенні предикату.

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

Прикладами складених термів є рік_машини('Таврія', 1988) та 'Друзі_Особи'(грай,[око,тур]). Складені терми із функторами, що оголошено як оператори, можуть записуватися префіксним або інфіксним записом. Наприклад, теми -(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].
• Стрічки: послідовність символів у лапках, еквівалентна спискові (числових) кодів символів, зазвичай у місцевому кодуванні, або в Юнікоді, якщо система підтримує Юнікод. Наприклад, "бути чи не бути".

Прологові програми

Прологові програми описують відношення, визначені твердженнями. Чиста Пролог обмежена диз'юнктами Горна, повною за Тюрингом підмножиною логіки предикатів першого порядку. Є два типи тверджень: факти та правила. Правило має вигляд

Голова :- Тіло. 

і читається як «голова істинна, якщо тіло істинне». Тіло правила складається з викликів предикатів, що називаються цілями правила. Вбудований предикат ,/2 (що значить двоарний оператор з ім’ям ,) позначає кон’юнкцію цілей, а ;/2 — диз’юнкцію. Кон’юнкції та диз’юнкції можуть бути присутні лише в тілі, але не в голові правила.

Твердження з порожніми тілами називаються фактами. Наприклад:

кіт(базиліо). 

що рівноцінне правилу:

кіт(базиліо) :- true. 

інший приклад:

X is 3+2. 

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

 X=5 Yes. 

Вбудований предикат true/0 є завжди істинним.

Виконання

Виконання прологової програми починається задаванням користувачем єдиної цілі, що зветься запитом. З точки зору логіки, рушій Прологу намагається знайти спростування резолюції заперечення цього запиту. Метод резолюції, що використовується у Пролозі, називається ВЛВ-резолюцією. Якщо заперечення запиту може бути спростовано, з цього випливає, що запит, з відповідними зв’язуваннями змінних, є логічним висновком програми. У такому разі всі створені зв’язування змінних повідомляються користувачеві, і про запит повідомляється, що він досяг успіху. З практичної точки зору, стратегію виконання Прологу можна уявити як узагальнення викликів функцій в інших мовах, з тією різницею, що заданому запитові можуть відповідати голови кількох тверджень. В такому випадку система створює точку вибору, об’єднує ціль з головою твердження першої альтернативи, і продовжує цілями цієї першої альтернативи. Якщо у напрямку виконання програми будь-яка ціль зазнає невдачі, всі зв’язування змінних, що було зроблено від останньої на той момент точки вибору, скасовуються, і виконання продовжується з наступною альтернативою цієї точки вибору. Ця стратегія виконання називається хронологічним пошуком з вертанням. Наприклад:

мати_дитини(ірина, святослав). батько_дитини(ярослав, святослав). батько_дитини(ярослав, анна). батько_дитини(володимир, ярослав). брат_або_сестра(X, Y) :- батько_або_мати_дитини(Z, X), батько_або_мати_дитини(Z, Y). батько_або_мати_дитини(X, Y) :- батько_дитини(X, Y). батько_або_мати_дитини(X, Y) :- мати_дитини(X, Y). 

Виходячи з цього, наступний запит оцінюється як істинний:

?- брат_або_сестра(святослав, анна). Yes 

Це отримується наступним чином: Спочатку єдиною відповідною головою твердження до запиту брат_або_сестра(святослав, анна) є перша, тому надавання запиту є рівноцінним надаванню тіла того твердження з відповідними зв’язуваннями змінних, тобто, кон’юнкція (батько_або_мати_дитини(Z,святослав), батько_або_мати_дитини(Z,анна)). Наступною ціллю для доведення є крайня зліва з цієї кон’юнкції, тобто, батько_або_мати_дитини(Z,святослав). Цій цілі відповідають голови двох правил. Система створює точку вибору, і пробує перший вибір, чиїм тілом є батько_дитини(Z, святослав). Цю ціль може бути доведено з використанням факту батько_дитини(ярослав, святослав), тому створюється зв’язування Z = ярослав, і наступною ціллю для доведення стає друга частина наведеної вище кон’юнкції: батько_або_мати_дитини(ярослав, анна). І знову, це може бути доведено відповідним фактом. Оскільки всі цілі доведено, запит досягає успіху. Оскільки запит не містить жодних змінних, користувачеві не повідомляються жодні зв’язування. Запит зі змінними, як-то:

?- батько_дитини(Батько, Дитина). 

перелічує всі дійсні відповіді пошуку з вертанням.

Зверніть увагу, що з наведеним вище кодом запит ?- брат_або_сестра(святослав, святослав). також досягає успіху. Якщо потрібно, можна додати додаткові цілі для опису відповідних обмежень.

Цикли та рекурсія

Ітеративні алгоритми може бути реалізовано засобами рекурсивних предикатів. Для детермінованих предикатів, що демонструють хвостову рекурсію, або, загальніше, хвостові виклики, прологові системи зазвичай реалізують добре відомий метод оптимізації, що зветься оптимізацією хвостового виклику (англ. Tail Call Optimization, TCO): Перед виконанням виклику у хвостовій позиції кадр стеку твердження скасовується. Отже, детерміновані предикати з хвостовою рекурсією виконуються з незмінним простором стеку, як цикли в інших мовах.

Відсікання

Відсікання ! всередині правила втримає Пролог від пошуку з вертанням далі нього:

предикат(X) :- один(X), !, два(X). 

зазнає невдачі, якщо перше знайдене значення X, для якого один(X) є істинним, веде до того, що два(X) є хибним.

Анонімні змінні

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

Приклад пошуку заданого значення у списках:

містить(Ш, []) :- false. містить(Ш, [Ш|_]) :- true. містить(Ш, [_|Т]) :- містить(Ш, Т). 

Заперечення

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

нелегальне(X) :- \+ легальне(X). 

обчислюється наступним чином. Пролог намагається довести легальне(X). Якщо доведення цієї цілі знайдено, то початкова ціль (тобто, \+ легальне(X)) зазнає невдачі. Якщо доведення не може бути знайдено, то початкова ціль досягає успіху. Отже, префіксний оператор \+/1 називається оператором «недовідне», оскільки запит ?- \+ Ціль. досягає успіху, якщо Ціль не є довідною. Цей вид заперечення є правильним, якщо його аргумент є замкненим (тобто, не містить змінних). Правильність втрачається, якщо аргумент містить змінні. Зокрема, запит ?- нелегальне(X). тепер вже не може бути використано для перелічення усіх речей, що є нелегальними.

Семантики

При декларативному прочитанні, порядок правил, та цілей в межах правил, не має значення, оскільки логічна кон’юнкція та диз’юнкція є комутативними. Процедурно, однак, часто важливо враховувати стратегію виконання Прологу, чи то з міркувань ефективності, чи то з причини семантик нечистих вбудованих предикатів, для яких порядок виконання має значення. Також, оскільки інтерпретатори Прологу намагаються уніфікувати твердження в порядку їх представлення, неспроможність надати правильного порядку може призводити до нескінченної рекурсії, як у:

предикат1(X) :- предикат2(X,X). предикат2(X,Y) :- предикат1(X), X \= Y. 

За цього порядку будь-який запит вигляду

?- предикат1(атом). 

рекуруватиме до вичерпання стеку. Проте, якщо хоча б останні три рядки було змінено на:

предикат2(X,Y) :- X \= Y, предикат1(X). 

той самий запит призводив би до результату No. за дуже короткий час.

Граматики визначених тверджень

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

Приклад синтаксичного аналізатора

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

Дано твердження, представлене у нотації Бекуса — Наура:

<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> ::= + | - | * 

Це можна записати Прологом з використанням граматик визначених тверджень, що відповідають синтаксичному аналізаторові з передбаченням, що зазирає на одну лексему вперед:

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]. 

Цей код визначає відношення між виразом (заданим як перелік лексем) та його абстрактним синтаксичним деревом (АСД). Приклад запиту:

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

Це АСД представлено з використанням термів Прологу, і може бути використано для застосування оптимізацій, для компіляції таких виразів до машинного коду, або для інтерпретації їх напряму. Як є типовим для відносної природи предикатів, ці визначення можуть використовуватися як для синтаксичного розбору, так і для генерації виразів, а також для перевірки, чи відповідає задане дерево заданому перелікові лексем. Використовуючи ітеративне заглиблення для послідовного переліку, буде зрештою згенеровано кожен довільний, але фіксований вираз, та його АСД:

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

Див. також

• ^[en]

Примітки

1. ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva.