Пролог (език за програмиране)

Вижте пояснителната страница за други значения на Пролог.

Пролог (Prolog) е компютърен език за логическо програмиране. Името пролог е акроним от PROgramming in LOGic. Създаден е от Ален Колмерое, Филип Ръсел и Робърт Ковалски през 1972 г. като алтернатива на американско-доминираните Lisp програмни езици. Това е опит да се направи програмен език, който дава възможност да се използват логически изрази, вместо специални инструкции към компютъра. До някаква степен пролог е помощен на Planner (виж историята на Ковалски за ранното логическо програмиране). Пролог е богата колекция от структури от данни и мощна система за писане на потребителски приложения. Той притежава свои логически аспекти, възможности за интерпретиране, компактност и присъща модуларност.

За разлика от процедурните езици за програмиране като Pascal, PL/I и т.н., програмата, написана на пролог, дава на компютъра описание на проблема, като използва редица факти и правила, а след това го кара да намери всички възможни решения. Когато бива използван Pascal например, програмистът трябва да каже на компютъра как точно да изпълни задачата, докато ако се програмира на пролог, щом се опише какво трябва да се направи, системата на пролог сама организира начина на реализиране. Поради декларативния (а не процедурния) подход, добре известните източници на грешки в Pascal, Basic и т.н. – като напр. цикли, които изпълняват повече или по-малко от необходимите операции – са елиминирани от самото начало. Нещо повече, пролог учи програмиста как да направи добре структурирано описание на даден проблем. Освен това той може да се използва и като инструмент за писане на спецификации.

История

Пролог е резултат от дългогодишна изследователска работа. Първата официална версия на пролог е създадена в Университета на Марсилия от Ален Колмерое (Alain Colmerauer) в началото на 1970-те. Това е опит да се разработи език за програмиране, който да даде възможност да се описва логиката, вместо подробно да се описват инструкциите към компютъра.

Пролог се развива в областта на изкуствения интелект. Първоначално става популярен сред изследователите, занимаващи се с изкуствен интелект. Философията на това се крие в логическите и декларативни аспекти на пролог, който представлява фундаментално нов подход в компютърното програмиране, ставайки сериозен конкурент на LISP.

Области на приложение

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

Пролог се използва в много компютърни програми за изкуствен интелект и в компютърната лингвистика (особено при обработка на естествени езици). Неговите синтаксис и семантика се считат за много прости и ясни (първоначалното му предназначение е било да служи като инструмент за компютърно грамотни лингвисти). В проекта „Операционни системи от пето поколение“ (FGCS, System V) се използва вариант на пролог, наричан език-ядро (kernel language). Други важни приложения на пролог са експертните системи, които възпроизвеждат вземане на решение на ниво човек-експерт, и системите за управление на релационни бази данни.

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

Типове данни

Пролог не използва типове данни по начин, обичаен в класическите езици за програмиране. По-скоро може да се говори за лексикални елементи в пролог, а не за типове данни:

Атоми

Текстовите константи се въвеждат чрез т.нар. атоми. Атомът е низ от букви, цифри и долни тирета (_), който започва с малка буква. Ако е необходимо да се въведе атом, който не съдържа букви и цифри, той се загражда с апострофи (напр. '+' е атом, а + е оператор).

Числа

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

Променливи

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

Така наречената анонимна променлива се обозначава като едно долно тире (_).

Термини

Термините са единственият начин, чрез който пролог може да представи сложни данни. Терминът се състои от заглавие, наричано също функтор (което трябва да бъде атом), и параметри (неограничени типове). Броят на параметрите, наричан arity е много важен. Даден термин се идентифицира по неговото заглавие и arity, писано обикновено като functor/arity.

Списъци

Списъкът не е самостоятелен тип данни, защото се дефинира чрез рекурсивна конструкция (с използване на термина '.'/2):

атомът [] е празен списък
ако L е списък и X е елемент, то терминът '.'(X, L) е списък. Първият елемент е X, след който следва съдържанието на L. Синтактичното съкращение е [X | L].

За удобство на програмистите, списъците могат да се изграждат и разрушават по различни начини:

изреждане на елементи: [abc, 1, f(x), Y, g(A,rst)]
начално задаване на един елемент: [abc | L1]
начално задаване на множество елементи: [abc, 1, f(x) | L2]
разширяване на термин: '.'(abc, '.'(1, '.'(f(x), '.'(Y, '.'(g(A,rst), [])))))

Низове

Низовете обикновено се пишат като последователност от символи, заградени с кавички. Вътрешно те често са представяни като списъци от ASCII-кодове.

Факти

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

cat(tom).

Тук 'cat' е заглавието, а 'tom' е аргументът. Ето няколко примера за заявки, които можете да направите към интерпретатора на пролог въз основа на този факт:

?- cat(tom).
     yes.

?- cat(X).
     X = tom;
     no.

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

father(sally,pat).
father(pat,sally).

който би означавал, че Пат (Pat) е баща на Сали (Sally)? И в двата случая 'father' е заглавието, а 'sally' и 'pat' са аргументи. Обаче в първия случай Сали е първи аргумент, а във втория случай – Пат е първи аргумент (редът на аргументите има значение). Първият случай е пример за дефиниция, чийто ред е: сказуемо, допълнение, подлог, а вторият: сказуемо, подлог, допълнение. Понеже пролог не разбира английски, то за него и двата варианта са правилни. Обаче добрият стил на програмиране изисква в отделна програма да се спазва една и съща конвенция, така че да се избягва писане като:

father(pat,sally).
father(jessica,james).

Някои предикати са вградени в езика и позволяват на програмите на пролог да изпълняват рутинни действия (като входни/изходни операции, използване на графики и други начини на комуникация с операционната система). Предикатът write може да се използва за извеждане на екрана. Така например

 write('Hello')

ще изведе думата 'Hello' на екрана.

Правила

Вторият тип команди в пролог са правилата. Ето пример за правило:

light(on) :- switch(on).

    където „:-“ означава „ако“

Това правило означава, че light(on) е истина, ако switch(on) е истина. Правилата могат да използват също и променливи. Променливите започват с главна буква, докато константите започват с малка буква, напр.:

father(X,Y) :- parent(X,Y),male(Y).

Това означава: „ако някой е родител на някого и е мъж, той е баща“. Причината и следствието са в обратна последователност на тази, която обикновено се среща в логиката. В причината може да се поставят множество предикати, свързани със съюз и, напр.:

a,b,c :- d.

което е равно просто на три отделни правила:

a :- d.
b :- d.
c :- d.

Не са позволени правила като:

a;b :- c.

което означава „ако c, то a или b“. Това е поради ограничение за хорновите клаузи.

Примери

Ето и някои практически примера.

Операции със списъци

Проверка дали даден елемент е в списък:

in(X, [X|R]).
in(X, [Y,R]) :- in(X,R).

или

in(X, [X|_]).
in(X, [_,R]) :- in(X,R).

Намиране на последния елемент от списък:

last_element([X],X).
last_element([K|R],X) :- last_element(R,X).

Конкатенация на два списъка:

con([],L,L).
con([X|L1],L2, [X|L3]) :- con(L1,L2,L3).

Брой на елементите в списък:

list_length([],0).
list_length([K|R],N) :- list_length(R,M),
                        N is M + 1.

Изчисление на факториел

fak(0,1).
fak(N,X) :- M is N-1,
            fak(M,Y),
            X is N*Y.

Реализации

Strawberry Prolog, създаден е в България и се преподава в СУ, НБУ и в други университети в България и в чужбина.
Open Prolog
Ciao Prolog
GNU Prolog Архив на оригинала от 2011-08-14 в Wayback Machine.
YAP Prolog Архив на оригинала от 2004-07-06 в Wayback Machine.
SWI Prolog
Visual Prolog
SICStus Prolog
Amzi! Prolog
Turbo Prolog на Borland, вече не се поддържа
Jekejeke Prolog Архив на оригинала от 2012-08-07 в Wayback Machine.

Външни препратки

Реални примери
Интерпретатор на Prolog, който се пуска от браузър
Prolog: стандарт ISO
Visual Prolog: еволюция на Turbo Prolog, разработена от Prolog Development Center в Дания.