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

Книга от известен програмист (Югославия), съдържаща основите на езика Prolog и неговите приложения за решаване на проблеми с изкуствения интелект. Изложението се отличава с методически достойнства - книгата е написана в добър стил, на жив език. Книгата допълва наличната на български език литература за проложния език.

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

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

3.3. Нотация на оператора (нотация)

В математиката сме свикнали да пишем изрази като този:

където + и * са оператори и2,a,b,cса аргументи. По-специално + и * се наричат инфиксниоператори, защото се появяватмеждутехните аргументи. Такива изрази могат да бъдат представени като дървета, както е показано на фиг. 3.6 и написани като пролог термини с + и * като функтори:

Фиг. 3.6. Представяне на израза2*а+b*скато дърво.

Тъй като обикновено предпочитаме да пишем такива изрази в познатата инфиксна форма на изрази, Prolog предоставя това удобство. Следователно нашият израз, написан просто като

ще бъдат получени правилно. Това обаче е само външно представяне на обекта, което ще бъде автоматично преобразувано в обичайната форма на термините на Prologian. Такъв термин се показва на потребителя отново във външната си инфиксна форма.

Изразите се третират от Prolog просто като допълнителна нотация, която не въвежда никакви нови принципи за структуриране на обекти с данни. Ако напишем a + b, Prolog ще разбере тази нотация, сякаш сме написали +(a, b) .За да може Prolog правилно да анализира изрази като a + b*c, той трябва да знае, че * се свързва по-силно от +. Ще кажем, че + има по-нисък приоритет от *. Следователно правилното тълкуване на изразите зависи от приоритета на оператора. Например, изразът a + b * c по принцип може да се разбира като

Общото правило е, че операторът с най-нисък приоритет се счита за основен функтор на термина. Ако искаме изрази, съдържащи + и *, да се разбират според обичайните конвенции, тогава + трябва да има по-нисък приоритет от *. Тогава изразът a + b*c означава същото като a + (b*c) . Ако се има предвид друго тълкуване, това трябва да бъде посочено изрично с помощта на скоби, например (a+b)*c.

Програмистът може да въвежда свои собствени отчети. Така, например, можете да дефинирате has и supports atoms като инфикс оператори и след това да напишете факти като:

Петър има информация. Подът поддържа масата.

Тези факти са точно еквивалентни на следното:

има (петър, информация). опори (под, маса).

Програмистът дефинира нови оператори чрез въвеждане на специален вид клауза в програмата, понякога наричанадирективи. Такива изречения играят ролята на дефиниции на нови оператори. Дефиницията на оператор трябва да се появи в програмата преди всеки израз, използващ този оператор. Например операторът has може да бъде дефиниран с директивата

:- op( 600, xfx, има).

Тази нотация казва на Prolog, че искаме да използваме "has" като оператор с приоритет 600 и тип 'xfx', обозначаващ един от вариантите на инфикс оператора. Формата на спецификатора ' xfx ' показва, че изразът, обозначен с ' f ', е междуаргументи, обозначени с 'x'.

Обърнете внимание, че дефинициите на оператори не съдържат описания на никакви операции или действия. В съответствие с принципите на езикаnorникакви операции върху данни не са свързани седин оператор (освен в специални, редки случаи). Операторите обикновено се използват по същия начин като функторите, само за групиране на обекти в структури и не причиняват действия върху данни, въпреки че самата дума "оператор" изглежда предполага някакъв вид действие.

Имената на операторите са атоми и техните приоритети - по-точно техните приоритетни номера - трябва да бъдат в някакъв диапазон, зависим от изпълнението. Ще приемем, че този диапазон е в диапазона от 1 до 1200.[1]

Има три групи типове оператори, обозначени със спецификатори, подобни на xfx:

(1) три типа инфикс оператори:

(2) два типа префиксни оператори:

(3) постфикс оператори от два типа:

Спецификаторите са избрани така, че да отразяват по-добре структурата на израза, където „f“ съответства на оператор, а „x“ и „y“ представляват неговите аргументи. Местоположението на 'f' между аргументите показва, че операторът е инфикс. Спецификаторите за префикс и постфикс съдържат само един аргумент, който съответно следва или предхожда оператора.

Фиг. op3.7. Две интерпретации на израза a-b-c, като се приема, че '-' има приоритет 500. Ако типът на '-' е yfx, тогава интерпретация 2 е неправилна, тъй като приоритетът на b-c не е по-висок от приоритета на '-'.

Има разлика между 'x' и 'y'. За да го обясним, трябва да въведем концепцията запредимство на аргументи. Ако аргументът е в скоби или няма структура (епрост обект), тогава неговият приоритет е 0; ако е структура, тогава нейният приоритет е равен на приоритета на нейния главен функтор. 'x' обозначава аргумент, чийто приоритет трябва да бъде строго по-висок от приоритета на оператора (т.е. неговият номер е строго по-малък от приоритета на оператора); 'y' обозначава аргумент, чийто приоритет е по-голям или равен на този на оператора.

Такива правила помагат да се избегне неяснотата при обработката на изрази, които съдържат оператори със същия приоритет. Например изразът

обикновено се разбира като (a-b)-c, а не като a-(b-c) . За да осигури тази обща интерпретация, операторът „-“ трябва да бъде дефиниран като yfx. На фиг. 3.7 показва как се изключва втората интерпретация.

Като друг пример, разгледайте оператора not (логическото отрицание на "not"). Ако not е дефинирано като fy, тогава изразът

написано правилно; обаче, ако not е дефинирано като fx, то е невалидно, защото аргументът към първия not е not p структура, която има същия приоритет като not. В този случай изразът трябва да бъде написан със скоби:

не (не p) :- op( 1200, xfx, ':-'). :- op( 1200, fx, [:-, ?-] ). :- op( 1100, xfy, ';'). :- op( 1000, xfy, ','). :- op( 700, xfx, [=, е, , = =, ==, ==, ==, =:=]). :- op( 500, yfx, [+, -]). :- op( 500, fx, [+, -, не]). :- op( 400, yfx, [*, /, div]). :- op( 300, xfx, mod).

Фиг. 3.8. Набор от предварително дефинирани оператори.

За удобство някои оператори в системите Prolog са предварително дефинирани, така че да могат да се използват незабавно, без никаква дефиниция за тях в програмата. Наборът от такива оператори и техният приоритет зависят от изпълнението. Ще приемем, че наборът от тези "стандартни" операторисе държи така, сякаш е дефинирано с помощта на изреченията, показани на фиг. 3.8. Както можете да видите от същата фигура, множество оператори могат да бъдат дефинирани в една и съща клауза, стига всички да имат еднакъв приоритет и тип. В този случай имената на операторите се записват като списък. Използването на оператори може значително да увеличи видимостта, "четимостта" на програмата. Като пример, да предположим, че пишем програма за обработка на булеви изрази. В такава програма може да искаме да напишем твърдението на една от теоремите на Де Морган, която в математическа нотация е записана по следния начин:

Ето един начин да напишете това твърдение под формата на прологово изречение:

еквивалентно на ( не ( и ( A, B)), или ( не ( A, не ( B))).

Въпреки това, добрият стил на програмиране би бил да се опитате да запазите възможно най-голяма прилика между формата на оригиналния проблем и формата, използвана в програмата за решаването му. В нашия пример това може да се постигне почти напълно с помощта на оператори. Подходящ набор от оператори за нашите цели може да бъде дефиниран, както следва:

:- op( 800, xfx, ). :- op( 700, xfy, v). :- op( 600, xfy, &). :- op( 500, fy,

Сега правилото на де Морган може да се напише като следния факт:

В съответствие с нашите дефиниции на операторите, този термин се разбира, както е показано на фиг. 3.9.

Фиг. 3.9. Тълкуване на термина

• Четимостта на една програма често може да бъде подобрена чрез използване на операторна нотация. Операторите са инфикс, префикс и постфикс.

• По принцип никакви действия с данни не са свързани с оператор, освен в специални случаи. Дефиницията на оператора не съдържа описание на действие, а само въвежда нов начинзаписи. Операторите, подобно на функторите, само свързват компоненти в една структура.

• Програмистът може да въвежда свои собствени отчети. Всеки оператор се определя от своето име, приоритет и тип.

• Номерът на приоритет е цяло число в някакъв диапазон, да речем, между 1 и 1200. Операторът с най-висок номер на приоритет съответства на главния функтор на израза, в който се среща този оператор. Операторите с по-нисък приоритет обвързват своите аргументи по-силно от другите оператори.

• Типът на оператора зависи от две условия: (1) неговата позиция спрямо аргументите му, (2) приоритета на неговите аргументи пред неговите собствени. В спецификатори като xfy, x обозначава аргумент, чийто приоритетен номер е строго по-малък от приоритетния номер на оператора; y е аргумент с номер на приоритет по-малък или равен на номера на приоритет на оператора.

Упражнения

3.12. Ако такива определения са приети

:- op( 300, xfy, plays_in). :- op( 200, xfy и).

тогава следните два термина са синтактично правилни обекти:

Term1 = Jimmy играе_футбол и скуош Term1 = Susan играе_tennis и баскетбол и волейбол

Как се тълкуват тези термини от системата Prolog? Кои са основните им функтори и каква е тяхната структура?

3.13. Предложете подходяща дефиниция на оператори ("работи", "във", "наши"), така че да можем да пишем изречения като:

Диана работи като секретар в нашия отдел.

и след това попитайте:

? - Кой работи като секретар в нашия отдел. Кой = Даяна ? - Даяна работи като кой. От = секретар в нашия отдел

3.14. Помислете за програмата:

Как тази програма ще отговори на следните въпроси, ако ' + ' е (катообикновено) инфиксен оператор като yfx?