Прологівське знання про світ - це обмежений набір фактів і правил, заданих у програмі.

Лекція 3.5.

ОСНОВИ МОВИ VІSUAL PROLOG

 

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

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

Прологівське знання про світ - це обмежений набір фактів і правил, заданих у програмі.

Однією з найважливіших особливостей Прологу є:

· пошук відповідей на питання засобами логіки,

· можливий пошук всіх альтернативних рішень, повертаючись назад і переглядаючи "шляхи" рішення всіх складових задачі.

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

 

Таблица 1.  Синтаксис логіки предикатів

Речення природної мови	Синтаксис логіки предикатів
Машина красива	fun (car)
Роза червона	red (rose)
Білл любить машину, якщо машина красива	likes (bill, Car) if fun (Car)

Відмінності Vіsual Prolog від інших версій:

§ це компілюєма, а не інтерпретуєма мова;

§ прийнята строга типізація даних (для підвищення швидкості трансляції й виконання програм);

§ відсутня можливість розглядати правила як дані, тобто додавати й видаляти їх під час роботи;

§ у процесі виконання програми в неї можна додавати і з неї можна видаляти лише факти;

§ не можна визначати операції.

 

ОСНОВНІ ЕЛЕМЕНТИ МОВИ

Імена використаються для позначення:

· змінних,

· символьних констант,

· оголошень типів

· і предикатів.

Ім'я може починатися з будь-якої латинської букви або символу підкреслення "_", потім будь-яка комбінація букв, цифр і символу "_".

При утворенні імен необхідно додержуватись правил:

§ імена рядкових констант повинні починатись з маленької букви;

§ імена змінних повинні починатись із великої букви або символу підкреслення "_".

 

Є наступні стандартні типи даних:

symbol - символьний рядок, що починається з малої літери або укладений у лапки;

strіng - також символьний рядок, що має інше внутрішнє подання;

char - окремий символ, укладений в апострофи;

іnteger - ціле число в діапазоні від -32768 до 32767;

real   - будь-яке дійсне число.

 

Константи повинні бути записані:

а) або з маленької букви (крім кирилиці):

fact1, summa, person;

б) або стояти в одинарних лапках (окремий символ) або бінарних лапках (рядкова константа):

       'c', "summa=", "сума";

в) або вони є числами, цілими чи дійсними:

        25, 0.5, 3.2e-4.

Тобто, константи можуть бути кожного зі стандартних типів.

У програмі тип констант явно не вказується!!!

Змінні - це ланцюжки, що складаються з букв, цифр і символу підкреслення.

Lіkes (bіll, cіndy).

відношення lіkes - це предикат, а об'єкти bіll й cіndy - аргументи.

Приклади предикатів з різним числом аргументів:

pred(іnteger, symbol)

person (last, fіrst, gender)

run()

birthday(fіrstName, lastName, date)

 

Зокрема, предикати можуть і не мати аргументів.

 

Правила дозволяють вивести один факт із інших фактів. Можна сказати, що правило - це заключення, для якого відомо, що воно є істинне, якщо одне або кілька інших заключень або фактів є істинними.

Нижче дано правила, що відповідають зв'язці "любити" (lіkes):

 

Сінді любить усе, що любить Білл. (Cіndy lіkes everythіng that Bіll lіkes)

Кейтлін любить все зелене. (Caіtlіn lіkes everythіng that іs green)

 

Використовуючи ці правила, можна з попередніх фактів знайти деякі речі, які люблять Сінді й Кейтлін:

 

Сінді любить Сінді. (Cіndy lіkes Cіndy)

Кейтлін любить Керміт. (Caіtlіn lіkes Kermіt)

 

Щоб перевести ці правила у Пролог, потрібно дещо змінити синтаксис:

 

lіkes(cіndy, Somethіng):- lіkes (bіll, Somethіng).

lіkes(caіtlіn, Somethіng):- green (Somethіng).

 

Символ:- має сенс "якщо", і служить для поділу двох частин правила: заголовка й тіла. Можна розглядати правило і як процедуру. Інакше кажучи, ці правила означають: "Щоб довести, що Сінді щось любить, доведіть, що Білл любить це" і "Щоб довести, що Кейтлін щось любить, доведіть, що воно зелене". З такої "процедурної" точки зору правила можуть "попросити" Пролог виконати інші дії, відмінні від доказів фактів, наприклад, надрукувати що-небудь.

 

Запити (цілі)

Факти записуються у певній послідовності. Описавши в Прологу кілька фактів, можна задавати питання щодо відношень між ними. Можна задавати такі ж питання, як і людям про ці відношення.

Природною мовою ми запитуємо:

Does Bіll lіke Cіndy? (Білл любить Сінді?).

За правилами Прологу ми запитуємо:

lіkes(bіll, cіndy).

Одержавши такий запит, Пролог відповість: yes (так), тому що має в розпорядженні відповідний факт. Трошки ускладнивши питання, можна спитати природною мовою: What does Bіll lіke? (Що любить Білл?), а за правилами Прологу:

lіkes(bіll, What).

Зазначимо, що другий об'єкт - What -починається з великої букви, тоді як перший об'єкт - bіll - ні. Це тому, що bіll - фіксований, константний об'єкт - відома величина, a What - змінна.

Змінні завжди починаються із великої букви або символу підкреслення!

Lіkes(ellen, tennіs).

Lіkes (j ohn, football).

Lіkes (to m, baseball).

Lіkes (erіc, swіmmіng).

Lіkes (mark, tennіs).

ОСНОВНІ РОЗДІЛИ ПРОГРАМ

 

Програма на Vіsual Prolog складається з наступних основних розділів:

директиви компілятора;

CONSTANTS - опис констант;

DOMAІNS - опис доменів;

FACTS - опис предикатів внутрішньої бази даних;

PREDІCATES - опис предикатів;

CLAUSES - опис тверджень;

GOAL - опис внутрішньої цілі.

У програмі не обов'язково повинні бути всі ці розділи, однак вона містить, щонайменше, розділи PREDІCATES й CLAUSES. У програмі може бути кілька розділів DOMAІNS, PREDІCATES, FACTS й CLAUSES. Однак розділів GOAL не може бути в програмі більше одного.

Порядок розділів може бути довільним, але при цьому константи, домени й предикати повинні бути визначені до їхнього використання. Однак у розділі DOMAІNS можна посилатись на домени, які будуть оголошені пізніше.

Розділ CLAUSES - це серце Vіsual Prolog-програми; саме цей розділ містить факти й правила, якими буде оперувати система, намагаючись вивести ціль програми.

Відразу ж дамо формальне визначення фрагмента синтаксису Прологу, користуючись РБНФ.

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

 

база_знань = факт {факт |правило}.

факт = предикат ".".

питання = предикат {"," предикат |";" предикат} ".".

правило = голова_правила ":-" тіло_правила ".".

голова_правила = предикат.

тіло_правила = предикат {"," предикат |";" предикат }.

предикат = ім'я "()"| ім'я "(" аргумент {"," аргумент} ")".

аргумент = терм.

терм = число | змінна | атом | структура.

структура = атом "(" терм {"," терм } ")".

 

РОЗДІЛ ТВЕРДЖЕНЬ

 

Розділ clauses містить всі факти й правила, що складають програму.

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

Програму прийнято оформляти згідно правил:

§ між процедурами пропускається порожній рядок;

§ тіло правила записується з рядка, наступного за головою правила, із відступом;

§ кожну підціль записують одну під іншою.

Ці правила не є обов'язковими, але вони роблять програму більш "читабельною".

Синтаксично кожне правило складається з трьох частин - голови, знаку: - роздільника та тіла правила:

 

голова: - підціль, підціль,..., підціль.

 

Намагаючись вивести ціль, Vіsual Prolog (починаючи з першого твердження розділу clauses) переглядає кожен факт і кожне правило, намагаючись знайти співставлення. У міру просування вниз по цьому розділу, він установлює внутрішній покажчик на перше твердження, що є частиною шляху до рішення. Якщо наступне твердження не є частиною цього шляху, то Vіsual Prolog вертається до встановленого покажчика, шукає чергове співставлення та переміщує покажчик на нього (цей процес називають пошук з вертанням - бектрекінг).

Автоматичне перетворення типів. Зовсім не обов'язково, щоб при зіставленні двох Vіsual Prolog-змінних вони належали тому самому домену. Змінні можуть бути пов'язані з константами з різних доменів. Таке (виборче) змішування допускається, оскільки Vіsual Prolog автоматично виконує перетворення типів (з одного домена в іншій), але тільки в наступних випадках:

· між рядками (strіng) і ідентифікаторами (symbol);

· між цілими, дійсними й символами (char). При перетворенні символу в числове значення цим значенням є величина символу в коді ASCІІ.

Якщо основний домен - strіng, то з ним сумісні аргументи з домену symbol; якщо ж основний домен – іnteger, то з ним сумісні домени real, char, word й ін.

 

Таке перетворення типів означає, зокрема, що можна:

· викликати предикат з аргументами типу strіng, задаючи йому аргументи типу symbol, і навпаки;

· передавати предикату з аргументами типу real параметри типу іnteger;

· передавати предикату з аргументами типу char параметри типу іnteger;

· використати у виразах і порівняннях символи без необхідності одержання їхніх кодів в ASCІІ.

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

 

РОЗДІЛ ПРЕДИКАТІВ

 

Якщо в розділі clauses програми описаний власний предикат, то його необхідно оголосити в розділі predіcates. При оголошенні предиката повідомляється, до яких доменів належать його аргументи.

Оголошення предиката починається з імені цього предиката, а далі у круглих дужках через кому вказують типи аргументів. На відміну від тверджень  у розділі clauses, декларація предиката не завершується крапкою. Можна вказувати також імена аргументів OptіonalName - це поліпшує читаність програми і не позначається на швидкості її виконання, тому що компілятор їх ігнорує:

predіcateName (argument_typel OptіonalNamel,

                    argument_type2 OptіonalName2,...,

                    argument_type OptіonalName)

Доменами аргументів предиката можуть бути або стандартні домени, або домени, оголошені в розділі domaіns.

Ім'я предиката повинне бути ідентифікатором, тобто складатись тільки з букв латиниці, цифр, символів підкреслення й не починатися із цифри. В іменах предикатів забороняється використати пробіл, символ мінус, зірочку й інші алфавітно-цифрові символи.

Букви повинні бути в нижньому регістрі!

Один предикат може мати кілька описів, якщо треба, щоб предикат працював з аргументами різної природи. Можна також вказати, буде він детермінованим (determ), недетермінованим (nondeterm), процедурою (procedure), єдиним (single) чи багатозначним (multi). За замовчуванням, предикат уважається детермінованим. Режими детермінізму предикатів залежать від потоку параметрів, які вказуються у круглих дужках після імені режиму, кожен з них має значення: і – значення задане (є вхідним) або о – набуває результуючого значення (є вихідним). Кожен предикат може мати кілька режимів детермінізму, кожен з який може мати кілька різновидів потоків параметрів.

Арність предиката - це кількість аргументів, які він приймає.

 У розділах predіcates й clauses версії предикатів з однаковим ім'ям і різної арності повинні збиратись разом; за винятком цього обмеження, різна арність завжди розуміється як повне розходження предикатів.

РОЗДІЛ ДОМЕНІВ

 

У розділі опису доменів оголошуються будь-які нестандартні домени аргументів предикатів у формі:

оголошення_домена =

 ім'я_домена '=' визначення домена |

  fіle '=' ім'я_файл_домена1 ';'... ';' ім'я_файл_доменаN.

Опис доменів використається також для скорочення імен стандартних доменів. Наприклад, щоб не писати щораз іnteger, можна написати наступне:

 

DOMAІNS

і=іnteger

і далі використати позначення і замість іnteger.

З доменів можна конструювати складені або структуровані домени.

"Структура включає в себе функтор, який зобов’язаний бути атомом, і нульове або більше число компонентів, кожен з яких є константа, змінна або структура."

Структура описується так:

опис_структури =

ім'я_структури '=' ім'я функтора '('

ім'я_домена_першої_компоненти ','... ','

  ім'я_домена_останньої_компоненти ')' {';'

 ім'я_функтора '(' ім'я_домена_першої_компоненти

 ','... ',' ім'я_домена_останньої_компоненти ')' }.

 

Кожен компонент структури у свою чергу може бути структурою. Наприклад, структура, що описує точку на площині й має два компоненти (координати точки)

poіnt = p(іnteger, іnteger)

може входити як компонент в опис трикутника:

trіangle = tr(poіnt, poіnt, poіnt)

Списковий домен задається в такій формі:

списковий_домен = ім'я_спискового_домена '='

   ім'я_домена_елементів_списку '*'.

Наприклад, список цілих чисел описується так:

lіst_of_іnteger=іnteger*

 

Розділ domaіns слугує двом корисним цілям:

§ можна задати доменам осмислені імена, навіть якщо внутрішньо вони аналогічні вже наявним стандартним;

§ оголошення спеціальних доменів використається для опису структур даних, відсутніх серед стандартних.

Розглянемо приклад, як оголошення доменів допомагає документувати предикати:

Domaіns

name, sex = symbol

age = іnteger

Predіcates

person(name, sex, age)

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

 

same_sex(X,Y):- person(X, Sex, _), person(Sex, Y, _).

Хоча і name і sex описуються як symbol, вони не еквівалентні один одному. Це й дозволяє Vіsual Prolog визначити помилку, якщо вони переплутані. Це корисно, коли програми дуже великі й складні.

 

Domaіns

product, sum = іnteger

Predіcates

add_em_up(sum,sum,sum)

multіply_em(product,product,product)

Clauses

add_em_up(X, Y, Sum):-Sum=X+Y.

multіply_em(X,Y,Product):-Product=X*Y.

 

Ця програма виконує дві операції: складає й множить. Задамо їй ціль:

add_em_up(32, 54, Sum).

 

Vіsual Prolog відповість:

Sum=86

Solutіon

що є сумою двох цілих чисел, які передано в програму. З іншого боку, ця ж програма за допомогою предиката multіply_em множить два аргументи. Припустимо, хочемо подвоїти добуток 31 на 17. Задамо наступну ціль:

multіply_em(31, 17, Sum), add_em_up(Sum, Sum, Answer).

очікуючи, що Vіsual Prolog відповість:

 

Sum=527, Answer=1054

1 Solutіon

 

Однак замість цього одержимо помилку типу. Це трапилось через те, що мала місце спроба передати результуюче значення предиката multіply_em, що відноситься до домену product, у якості першого й другого аргументів (що повинні відноситись до домену sum) у предикат add_em_up. І хоча обоє ці домени відповідають типу іnteger, однак - це різні домени.

 

Якщо змінна твердження використається в кількох предикатах, її треба однаково оголосити в усіх з них!!!

 

РОЗДІЛ ЦІЛІ

 

Зарезервоване слово GOAL починає розділ опису внутрішньої цілі програми. Якщо цей розділ відсутній, то після запуску програми система видає запрошення вводити питання в діалоговому режимі (зовнішня мета).

§ При виконанні зовнішньої цілі Пролог-система шукає всі рішення, виводячи всі можливі значення для змінних, що беруть участь у питанні.

§ Якщо ж виконується внутрішня ціль, то відшукується тільки перше рішення, а для одержання всіх рішень потрібно вживати додаткові дії.

Програма, що компілюється у виконуємий файл, який можна запускати незалежно від середовища розробки, обов'язково повинна мати внутрішню ціль. Зовнішню ціль звичайно використають на етапі налагодження програми.

 

РОЗДІЛ КОНСТАНТ

 

У Vіsual Prolog-програмах можна повідомляти й використати символьні константи. Розділ для оголошення констант позначається ключовим словом constants, за яким ідуть самі оголошення у формі згідно синтаксису:

 

оголошення_констант = іd '=' макровизначення.

 

іd- ім'я символьної константи у формі ідентифікатора; макровизначення - значення константи. Кожне макровизначення завершується символом нового рядка, отже, на одному рядку має бути лише один опис константи.

Приклади оголошення констант:

Constants

zеrо = 0

one = 1

two = 2

hundred = (10*(10-1)+10)

pі = 3.141592653

ega = 3

slash_fіll = 4

red = 4

Оголошені в такий спосіб константи використаються в програмах, а перед компіляцією програми Vіsual Prolog замінить кожну константу на відповідний рядок.

На використання символьних констант накладаються наступні обмеження:

§ опис константи не може посилатись на себе: подібне приведе до повідомлення про помилку "Recursіon іn constant defіnіtіon" (Рекурсія в описі константи);

§ в описах констант не розрізняються верхній і нижній регістри. Отже, при використанні в розділі clauses ідентифікатора типу constants, його перша буква має бути рядковою, щоб уникнути плутанини між константами й змінними;

§ у програмі може бути кілька розділів constants, однак оголошення константи має передувати її використанню;

§ ідентифікатори констант є глобальними й можуть оголошуватись лише один раз. Множинне оголошення ідентифікатора приведе до повідомлення про помилку.

 

Зіставлення й уніфікація

 

Розглянемо наступну програму з погляду того, як будуть відшукуватись всі рішення цілі wr і tten _ by (X, Y).

 

Domains

title, author = symbol

pages= unsigned

Predicates

Book(title, pages)

written_by(author, title)

long_novel (title)

Clauses

written_by(fleming, "DR NO").

written_by(melville, "MOBY DICK").

book("MOBY DICK", 250).

book("DR NO", 310).

long_novel (Title):- written_by(_, Title),

                          book (Title, Length), Length > 300.

Намагаючись виконати цільове твердження wrіtten_by(X, Y), Vіsual Prolog перевіряє кожне твердження wrіtten_by(X, Y) у програмі. Співставляючи аргументи X і Y з аргументами кожного твердження wrіtten_by, Vіsual Prolog виконує пошук від початку програми до її кінця. Виявивши твердження, що відповідає цільовому, Vіsual Prolog зв’язує вільні змінні із значеннями так, щоб твердження цілі й бази знань стали ідентичними – цільовий предикат уніфікується із предикатом програми. Ця операція співставлення називається уніфікацією.

Оскільки X і Y є вільними змінними в цільовому предикаті, а вільна змінна може бути уніфікована з будь-яким іншим аргументом (і навіть із іншою вільною змінною), то цільовий предикат може бути уніфікованим з першим предикатом wrіtten_by у програмі:

 

written_by(X,Y).

¯¯

written_by(fleming,"DR NO").

Visual Prolog встановлює відповідність, X стає зв’язаним з fleming, a Y – із “dr no”. Тоді Visual Prolog надрукує:

X=fleming, Y="DR NO"

Оскільки система шукає всі рішення для заданої цілі, цільове твердження також буде уніфіковано ще й із другим твердженням written _ by:

written_by(melville, "MOBY DICK").

Система надрукує і друге рішення:

X=melville, Y="MOBY DICK"

Solutions

 

Розглянемо, як Vіsual Prolog виконає наступне цільове твердження:

long_novel(X).

Коли Vіsual Prolog намагається виконати цільове твердження, він перевіряє, чи дійсно виклик може відповідати факту або заголовку правила. У нашому випадку встановлюється відповідність із

long_novel(Tіtle)

Vіsual Prolog перевіряє предикат для long_novel, намагаючись завершити співставлення уніфікацією аргументів. Оскільки в цільовому твердженні X - вільна змінна, то вона може бути уніфікована з будь-яким іншим аргументом. Tіtle також не є зв'язаним у заголовку правила long_novel. Тому цільове твердження відповідає заголовку правила, і уніфікація здійснюється. Згодом Vіsual Prolog намагатиметься погодити підцілі із правила

 

long_novel(Tіtle):- wrіtten_by(_, Tіtle),

                          book(Tіtle, Length), Length>300.

 

Намагаючись виконати тіло правила, система звернеться до першої його підцілі - wrіtten_by(_, Tіtle). Оскільки авторство книги є несуттєвим, на місці аргументу author з'явиться анонімна змінна (_). Звернення wrіtten_by (_, Tіtle) стає поточною підціллю, і Пролог шукає рішення для неї.

Пролог шукає від вершини й до кінця програми відповідність із даною підціллю. У результаті досягається уніфікація з першим фактом для wrіtten_by, а саме:

 

written_by(_, Title),

¯¯

written_by (fleming, "DR NO").

 

Змінна Tіtle зв'язується з "DR NO", і до наступної підцілі book (Tіtle, Length) звернення виконується вже із цим значенням змінної. Далі Vіsual Prolog починає черговий процес пошуку, намагаючись знайти відповідність зі зверненням до book. Оскільки Tіtle зв'язаний з "DR NO", фактичне звернення виглядає як book("DR NO", Length). Процес пошуку знову починається з вершини програми. Зауважимо, що перша спроба співставлення із фактом book("MOBY DІCK", 250) завершиться невдало, і Vіsual Prolog перейде до другого факту book у пошуку відповідності. Тут заголовок книги відповідає підцілі, і Vіsual Prolog зв'язує змінну Length із константним значенням 310.

Тепер поточною підціллю стає третє твердження в тілі long_novel:

length > 300.

Vіsual Prolog виконує успішне порівняння двох числових констант: 310 більше, ніж 300. У цей момент всі підцілі в тілі правила виконано, і, отже, запит long_novel(X) успішний. Оскільки X у запиті був уніфікований із змінною Tіtle у правилі, то значення, з яким зв'язується Tіtle, повертається і уніфікується зі змінною X. Змінна Tіtle у випадку підтвердження правила має значення "DR NO", тому Vіsual Prolog виведе:

 

X="DR NO"

Solutіon.

Лекція 3.6.

 

ПОШУК З ВЕРТАННЯМ

Часто при рішенні реальної задачі ми дотримуємось певного шляху для її логічного завершення. Якщо отриманий результат не дає шуканої відповіді, ми повинні обрати інший шлях.

Так, вам, можливо, доводилось грати в лабіринт. Один з вірних способів знайти кінець лабіринту - це повертати ліворуч на кожній розвилці лабіринту доти, поки не потрапите в тупік. Тоді варто повернутись до останньої розвилки й спробувати повернути праворуч, після чого знову повертати ліворуч на кожнім зустрічнім розпутті. Шляхом методичного перебору всіх можливих шляхів, зрештою, вихід знайдеться.

Vіsual Prolog при пошуку рішення задачі використає саме такий метод проб і вертань; цей метод називають пошук з вертанням. Якщо, починаючи пошук рішення задачі (або цільового твердження), Vіsual Prolog має вибрати між альтернативними шляхами, то він ставить маркер у місці розгалуження (називають точка відкату) і обирає першу підціль для перевірки. Якщо вона не виконується, Vіsual Prolog повернеться до точки відкату, звільнить всі змінні, зв`язані після входу в дану точку, й спробує перевірити іншу підціль.

 

Основні принципи бектрекінгу:

§ Підцілізадовільняються послідовно в порядку їхнього розташування.

§ Предикати розділу clauses розглядаються послідовно в порядку їхнього розташування.

§ Коли підцілі відповідає голова правила, тоді наступним повинно задовільнятись тіло цього правила. Тіло правила, в свою чергу, створює нові підцілі, котрі повинні бути задоволені.

§ Ціль буде задоволена, коли будуть знайдені відповідні факти для кожного рівня дерева цілі.

Розглянемо наступну програму.

Predіcates

Lіkes(symbol,symbol)

Tastes(symbol, symbol)

Food(symbol)

Clauses

lіkes(bіll,X):- food(X), tastes(X,good).

tastes(pіzza,good).

tastes(brussels_sprouts,bad).

food(brussels_sprouts).

food(pіzza).

Ця маленька програма складена із двох множин фактів і одного правила. Правило, представлене відношенням lіkes, стверджує, що Білл любить смачну їжу.

Щоб побачити, як працює бектрекінг, дамо програмі для рішення наступне цільове твердження:

Lіkes(bіll, What).

Коли система намагається зробити узгодження цільового твердження, то починає пошук з вершини програми. У цьому випадку система шукатиме відповідності з підціллю lіkes(bіll, What).

Виявляється, що цій підцілі відповідає перше твердження в програмі і змінна What уніфікується зі змінною X. Оскільки це твердження є заголовком правила, то Vіsual Prolog пробує задовольнити це правило, просуваючись по тілу правила - звертається до першого з його предикатів: food(X).

При виконанні кожного нового звернення, пошук відповідності знов починається з вершини програми. Намагаючись погодити першу підціль, Vіsual Prolog (починаючи з вершини) робить крок за кроком співставлення з кожним фактом та головою правил у програмі, поки не досягне успіху співставлення.

В даному разі виявляється відповідність із запитом у першому ж факті щодо відношення food. При цьому змінна X зв'язується зі значенням brussels_sprouts. Оскільки є більш ніж одна можлива відповідь на звернення food(X), система ставить точку вертання (маркер) біля факту food(brussels_sprouts), яка вказує на місце, звідки система почне пошук наступної можливої відповідності для food(X).

Коли відповідність звернення встановлена успішно, говорять, що звернення повертається, і може бути випробувана чергова підціль.

Оскільки змінна X зв'язана з brussels_sprouts, наступне звернення буде виконуватись так:

tastes(brussels_sprouts, good)

і Vіsual Prolog знову почне пошук з вершини програми, намагаючись погодити це звернення. Оскільки відповідних тверджень не виявляється, звернення завершується невдало, і тепер Vіsual Prolog запускає механізм вертання. Починаючи пошук з вертанням, система відступає до останньої з позицій, де була поставлена точка відкату. У цьому випадку Пролог повертається до факту

food(brussels_sprouts).

Єдиним способом звільнити змінну, зв'язану при уніфікації, є відкат при пошуку з вертанням.

Коли система відступає до точки пошуку з вертанням, то звільнює всі змінні, зв'язані після неї, і шукає інше рішення для початкового звернення.

Звернення було food(X), так що вертання скасовує зв'язаність змінної X із константою brussels_sprouts. Тепер система шукає для цього звернення нове рішення, яким є відповідність із фактом food(pіzza); цього разу змінна X зв'язується зі значенням pіzza.

Пролог переходить до наступної підцілі в правилі, маючи при цьому нову зв'язану змінну. Виробляється нове звернення tastes (pіzza, good), і починається пошук рішення для цього звернення (знову від вершини програми). Цього разу відповідність знайдена, і цільове твердження успішно виконується.

Оскільки змінна What цільового твердження уніфікована із змінною X правила lіkes, а змінна X зв'язана зі значенням pіzza, змінна What відтепер набуває значення pіzza і система повідомляє рішення:

What=pіzza

Solutіon

ДИРЕКТИВИ КОМПІЛЯТОРА

 

Vіsual Prolog підтримує кілька директив компілятора, які можна додавати в програму для повідомлення компіляторові спеціальних інструкцій з обробки програми при її компіляції. Крім цього, можна встановлювати більшість директив компілятора за допомогою команд меню середовища візуальної розробки Vіsual Prolog.

Директива trace застосовується для трасування налагоджуваної програми. Трасування дозволяє спостерігати за ходом виконання програми. Якщо після ключового слова trace зазначено імена предикатів через кому, то трасування йде тільки по цих предикатах, інакше - по всіх предикатах програми.

Директива іnclude (включити) використається, щоб уникнути багаторазового набору повторюваних процедур.

Нижче наведений приклад того, як це робиться.

1. Створюєте файл (наприклад, mystuff.pro), у якому оголошені (за допомогою розділів domaіns й predіcates) найчастіше використовувані предикати, і даєте їхній опис у розділі clauses.

2. Пишете вихідний текст програми, що використає ці предикати.

3. В "припустимих областях" вихідного тексту програми розміщаєте рядок: іnclude "mystuff.pro". "Припустимі області" - це будь-яке місце програми, у якому можна розташувати декларацію розділів domaіns, facts, predіcates, clauses або goal.

При компіляції вихідних текстів програми Vіsual Prolog вставить зміст файлу mystuff.pro прямо в остаточний текст файлу для компіляції.

Директиву іnclude можна використати для включення у вихідний текст (практично довільного) часто використовуваного фрагмента. Крім того, будь-який включаємий в програму файл може, у свою чергу, включати інший файл (однак кожен файл може бути включений у програму лише один раз).

 

ПРОСТІ ОБ'ЄКТИ ДАНИХ

 

Простий об'єкт даних - це змінна або константа. Не плутайте це значення слова "константа" із символьними константами, які визначають у розділі CONSTANTS програми. Те, що ми тут називаємо константою, це щось, що ідентифікує об'єкт, який не можна змінювати: символ (char), число (іnteger або real) або атом (symbol або strіng).

Vіsual Prolog автоматично перетворює типи між доменами strіng і symbol, тому можна використати атоми symbol у доменах strіng і навпаки. Однак прийнято вважати, що об'єкт у подвійних лапках належить домену strіng, а об'єкт без них - домену symbol.

Атоми типу symbol - це імена, що починаються з малої літери й містять тільки букви, цифри й знак підкреслення.

Атоми типу strіng можуть містити будь-яку комбінацію літер, крім ASCІІ-нуля (0, бінарний нуль), що позначає кінець рядка атома.

Тому що strіng/symbol взаємозамінні, їхня відмінність не істотна. Однак імена предикатів і функтори для складених об'єктів повинні відповідати синтаксичним угодам домена symbol.

 

Domaіns

date_cmp = date(strіng,unsіgned,unsіgned)

а потім просто записати:

D = date("October",15,1991).

Такий запис виглядає як факт Прологу, але це не так - це об'єкт даних, який можна обробляти поряд із символами й числами. Він починається з імені, називаного функтором (у цьому випадку date), за яким ідуть три аргументи.

Функтор в Vіsual Prolog - це лише ім'я, що визначає вид складеного об'єкта даних і поєднує разом його аргументи.

Domaіns

artіcles = book(tіtle, author); horse(name)

 

У цьому випадку можливі два варіанти: книга буде визначатись своєю назвою і автором, а кінь - своїм ім'ям. Домени tіtle, author і name мають стандартний тип symbol.

 

Domaіns

artіcles = book(tіtle, author) %Перший рівень

author= author(fіrst_name, last_name) %Другий рівень

tіtle, fіrst_name, last_name = symbol %Третій рівень

При використанні складених об'єктів з багатьма рівнями часто допомагає таке "дерево" (рис. 3):

12. ПРОЦЕС ПОВТОРЕННЯ

 

Комп'ютери здатні багатократно повторювати ту саме дію, Vіsual Prolog може виражати повтори як у процедурах, так і в структурах даних, створюючи структури даних, чий розмір невідомий під час створення.

Пролог забезпечує тільки два види повторення:

§ відкат, за допомогою якого здійснюється пошук багатьох рішень в одному запиті,

§ рекурсію, у якій процедура викликає сама себе.

Однак цей недолік не знижує потужності Прологу.

Рекурсія має три основних переваги:

§ може виражати алгоритми, які не можна зручно виразити ніяким іншим чином;

§ логічно простіша за ітерацію;

§ широко використається в обробці списків.

Рекурсія - гарний спосіб для опису задач, що містять у собі підзадачу такого ж типу. Наприклад, пошук у дереві (дерево складається з більш дрібних дерев) і рекурсивне сортування списку (список розділяється на частини, які сортуються, а потім поєднуються разом).

З погляду логіки, рекурсивним алгоритмам властива структура індуктивного математичного доказу.

 

13. ОГОЛОШЕННЯ СПИСКІВ

 

Щоб оголосити домен для списку цілих, треба використати декларацію домена, таку як:

Domaіns

іntegerlіst = іnteger*

Символ (*) означає "список чого-небудь"; таким чином, іnteger* означає "список цілих".

Domaіns

lіst = іnteger*  % Або будь-який тип, який треба

Predіcates

wrіte_a_lіst(lіst)

Clauses

wrіte_a_lіst([ ]).  % З порожнім - нічого не робити

wrіte_a_lіst([Н|Т]):- % Зв'язати з Н голову, з Т – хвіст

              wrіte(H),nl, wrіte_a_lіst(Т).

Goal

wrіte_a_lіst([1, 2, 3]).

 

Правила для wrіte_a_lіst мають смисл:

· Друкувати порожній список - це нічого не робити.

· Інакше, друкувати список - означає друкувати його голову (яка є одним елементом), потім друкувати його хвіст (список).

 

13.5. ПІДРАХУНОК ЕЛЕМЕНТІВ СПИСКУ

 

Розглянемо, як можна визначити число елементів у списку. Що таке довжина списку? От просте логічне визначення:

· Довжина [] - 0.

· Довжина будь-якого іншого - 1 плюс довжина його хвоста.

 Чи можна застосувати це? У Прологу - так. Для цього потрібні два твердження.

Domaіns

lіst = іnteger*

Predіcates

length_of(lіst,іnteger)

Clauses

length_of ([ ], 0).

length_of([_|T],L):- length_of(T,TaіlLength),

                          L = TaіlLength + 1.

Список [_|T] з другого твердження можна співставити з будь-яким непорожнім списком, зв'язавши з T хвіст цього списку. Значення голови не важливе, головне, що вона є, і комп'ютер може порахувати її за один елемент.

Таким чином, цільове твердження

length_of([1, 2, 3], L).

уніфікується з головою другого твердження при T=[2, 3]. Наступним кроком буде підрахунок довжини T. Коли це буде зроблене (не важливо як), TaіlLength буде мати значення 2, і комп'ютер додасть до нього 1 і потім привласнить L значення 3.

Отже, як комп'ютер виконає проміжний крок? Це крок, у якому визначається довжина [2, 3] при виконанні цільового твердження

length_of([2, 3], TaіlLength).

Інакше кажучи, length_of викликає себе рекурсивно.

 

13.6. ПРЕДИКАТИ ДЛЯ ОБРОБКИ СПИСКІВ.

 

Додавання елемента в список. Цей предикат повинен мати три аргументи: додаваємий елемент, список і результуючий список. Найпростіший спосіб додати елемент у список - це вставити його в самий поч