Пролог (програмски јазик)

Пролог () — логички програмски јазик со општа намена кој се асоцира со вештачка интелигенција и компјутерска лингвистика.

Основите на Пролог се засноваат на логиката од прв ред и формалната логика. За разлика од многу други програмски јазици, Пролог е декларативен јазик, што значи дека програмската логика се изразува преку релации, прикажани преку факти и правила на заклучување. Пресметувањата се иницираат со поставување на прашања.

Овој програмски јазик е создаден од групата Alain Colmerauer во почетокот на седумдесеттите години, додека првиот систем е создаден во 1972 година од Colmerauer со помош на Philippe Roussel.

Prolog е еден од првите логички програмски јазици, и денес сè уште претставува еден од најпопуларните логички јазици достапен во многу комерцијални и бесплатни имплементации. Првично наменет за обработка на природните јазиции, неговата употреба се проширува во многу други области како докази на теореми, експертни системи, игри, автоматизирани системи за одговарање на прашања, онтологии и софистицирани контролни системи. Модерните развојни околини за Пролог, поддржуваат создавање на графички кориснички интерфејси, како и административни и мрежни апликации.

Синтакса и семантика Во Пролог, програмската логика е изразена преку релации, додека пресметките се засноваат на прашања упатени до релациите. Релациите и прашањата се конструираат со единствениот податочен тип term. Релациите се дефинирани со клаузи. За дадено прашање, механизмот во Prolog се обидува да најде одбивање за негираното прашање. Попрецизно ова значи дека прашањето се негира, и во случај да се најде инстанца од базата на знаење која го побива негираното прашање, следува дека оваа инстанца е логичка последица на програмата. Ова го прави Пролог погоден за работа со бази на податоци, симболичка математика и апликации за манупилација со јазици. Во случаи кога логичката парадигма не може да реши одреден проблем, програмерот има можност да употреби одредена доза на конвенционалното императивно програмирање.

Податочни типови

OОсновен податочен тип во Prolog е term. Term може да биде атом, број, променлива или сложен term.

Атом е име со општа употреба со неоделиво значење. Пример за атом: x, blue, 'Taco', and 'some atom'. Број може да биде децимален број или цел број. Променлива е низа од карактери која почнува со голема почетна буква или долна црта. Променливите имаат блиско значење со променливите со логиката. Сложен term претставува атом, со одреден број на аргументи, кои исто така се атоми. Пример truck_year('Mazda', 1986) и 'Person_Friends'(zelda,[tom,jim]).

Специјални случаи на сложен term:

Листа - подредена колекција на terms. На пример [1,2,3] или [red,green,blue]. Стринг - низа од карактери во наводници. На пример "to be, or not to be".

Правила и факти Prolog програмите опишуваат релации, кои се дефинирани преку клаузули. Постојат два типа на клаузули: факти и правила. Правилото ја има следната форма

Head :- Body.

и истото се чита на следниот начин "Head е вистина ако Body е вистина". Телото на едно правило се состои од повици до предикати. Исто така во телото се користат и конјункција и дисјункција.

Клаузула со празно тело се нарекува факт. На пример

cat(tom).

што исто така може да се запише преку правилото

cat(tom) :- true.

Предикатот true/0 е секогаш вистинит.

Ако е дадено горното правило, тогаш моше да се постават прашањата:

is tom a cat?

?- cat(tom). Yes

what things are cats?

?- cat(X). X = tom

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

animal(X):- cat(X).

Доколку го додадеме ова правило и потоа прашаме what things are animals?

?- animal(X). X = tom

Поради релационите одлики на предикатите, тие можат да се користат во различни насоки. На пример length/2 може да се употреби за одредување на големината на листа (length(List, L), за дадената листа List), но исто така и за да се генерира листа со дадена големина (length(X, 5)). Слично, append/3 може да се користи за да се спојат две листи (append(ListA, ListB, X) или пак истите да се раздвојат (append(X, Y, List)). Поради ова во множеството на библиотеките има мал број на предикати кои често се употребуваат.

Како јазик со општа намена, Пролог нуди и одредени рутини како input/output, употреба на графика или различни повици за комуникација со оперативниот систем.

Евалуација Извршувањето на програма напишана во Prolog, се иницира со поставување на прашање од страна на корисникот. Логички, механизмот на Prolog се обидува да пронајде одбивање на негацијата на прашањето. Овој метод на пролог се нарекува 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).

This results in the following query being evaluated as true:

?- sibling(sally, erica). Yes

За дадениот пример треба да се забележи дека програмата како вистинит одговор ќе даде и за следниот случај, ?- sibling(sally, sally).. За да се одбегне ваков случај потребни се додатни ограничувања.

Циклуси и рекурзија Итеративните алгоритми во Пролог можат да се имплементираат со употреба на рекурзивни предикати.

Примери

Следуваат пример програми напишани во Prolog.

Hello world Пример за прашање: ?- write('Hello world!'), nl. Hello world! true.

?-

Оптимизација на компајлер Било која пресметка може да се изрази декларативно како низа од состојби кои минуваат една во друга. На пример, оптимизиран комапјлер со три премини може да се имплементира како релација помеѓу првичната програма и нејзината оптимална форма:

program_optimized(Prog0, Prog) :- optimization_pass_1(Prog0, Prog1), optimization_pass_2(Prog1, Prog2), optimization_pass_3(Prog2, Prog).

или евивалентно со употреба на DCG (definite clause grammar) нотација:

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

Брзо сортирање Следува алгоритмот за брзо сортирање (Quicksort) имплементиран во Prolog: partition([], _, [], []). partition([X|Xs], Pivot, Smalls, Bigs) :- ( X @< Pivot -> Smalls = [X|Rest], partition(Xs, Pivot, Rest, Bigs) ; Bigs = [X|Rest], partition(Xs, Pivot, Smalls, Rest) ).

quicksort([]) --> []. quicksort([X|Xs]) --> { partition(Xs, X, Smaller, Bigger) }, quicksort(Smaller), [X], quicksort(Bigger).

Шеми Шема претставува решение кое се користи повеќепати за проблеми кои се чести во софтверскиот дизајн. Во пролог шемите се јавуваат под две имиња, скелети и техники, клишеа,D. Barker-Plummer. Cliche programming in Prolog. In M. Bruynooghe, editor, Proc. Second Workshop on Meta-Programming in Logic, pages 247--256. Dept. of Comp. Sci., Katholieke Univ. Leuven, 1990. program schemata, и логичка описна шема. An alternative to design patterns is higher order programming.

Логика од повисок ред По дефиниција, логиката од прв ред не дозволува квантификација на предикатите. Предикат со логика од повисок ред е предикат кој како аргументи прима еден или повеќе други предикати. Пролог има предефинирани предикати со логика од повисок ред, на пример call/1, findall/3, setof/3, и bagof/3.

Модули За големи програмски решенија, Пролог нуди систем на модули. Овој систем е стандардазиран од ISO.ISO/IEC 13211-2: Modules. Но, не сите компајлери подршуваат модулирање, па постојат проблеми во компатибилност на различни компајлери.Paulo Moura, Logtalk in Association of Logic Programming Newsletter. Vol 17 n. 3, August 2004.

Имплементација ISO Prolog Стандардниот ISO Prolog се состои од два дела. ISO/IEC 13211-1,ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva. објавен во 1995, цели кон стандардизација на постоечките имплементации на јадрените елементи на Пролог. ISO/IEC 13211-2, објавен во 2000, ги стандардизира модулите на стандардот. Стандардот се одржува од SC22 работната група. ANSI X3J17 е надгледувачка група за овој стандард. Критички осврт Иако Пролог е широко употребуван во истражувањата и едукацијата, тој и останатите логички програмски јазици немаат начително влијание врз компјутерската индустрија генерално.Logic programming for the real world. Zoltan Somogyi, Fergus Henderson, Thomas Conway, Richard O'Keefe. Proceedings of the ILPS'95 Postconference Workshop on Visions for the Future of Logic Programming. Повеќето апликации се мали за индустриските стандарди, со ретки прекорочувања од 100,000 линии на код.The Prolog 1000 database http://www.faqs.org/faqs/prolog/resource-guide/part1/section-9.html Програмирање на големи апликации е комплицирано поради фактот дека не сите компајлери поддржуваат работа со модули. Портабилноста исто се јавува како проблем.

Слични програмски јазици Gödel е јазик кој се заснова на SICStus Prolog. Visual Prolog, на почетокот познат како PDC Prolog и Turbo Prolog, е објектно ориентиран дијалект на Пролог, кој е многу различен од стандартниот Пролог. Datalog е подмножество на Prolog. Лимитиран е во релациите кои може да имаат слоевита архитектура и не дозволува употреба на сложени terms. GraphTalk е имплементација на Warren's Abstract Machine, со објектно-ориентирани одлики. AgentSpeak е варијанта на Пролог за програмирање на агенти во системи со повеќе агенти.

Наводи

Дополнителна литература

Patrick Blackburn, Johan Bos, Kristina Striegnitz, Learn Prolog Now!, 2006, ISBN 1-904987-17-6. Ivan Bratko, PROLOG Programming for Artificial Intelligence, 2000, ISBN 0-201-40375-7. William F. Clocksin, Christopher S. Mellish: Programming in Prolog: Using the ISO Standard. Springer, 5th ed., 2003, ISBN 978-3540006787. (This edition is updated for ISO Prolog. Previous editions described Edinburgh Prolog.) William F. Clocksin: Clause and Effect. Prolog Programming for the Working Programmer. Springer, 2003, ISBN 978-3540629719. Alain Colmerauer and Philippe Roussel, The birth of Prolog , in The second ACM SIGPLAN conference on History of programming languages, p. 37-52, 1992. Michael A. Covington, Donald Nute, Andre Vellino, Prolog Programming in Depth, 1996, ISBN 0-13-138645-X. Michael A. Covington, Natural Language Processing for Prolog Programmers, 1994, ISBN 0-13-62921 Robert Smith, John Gibson, Aaron Sloman: 'POPLOG's two-level virtual machine support for interactive languages', in Research Directions in Cognitive Science Volume 5: Artificial Intelligence, Eds D. Sleeman and N. Bernsen, Lawrence Erlbaum Associates, pp 203–231, 1992. Leon Sterling and Ehud Shapiro, The Art of Prolog: Advanced Programming Techniques, 1994, ISBN 0-262-19338-8. Robert Kowalski, The Early Years of Logic Programming, CACM January 1988. ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva. Richard O'Keefe, The Craft of Prolog, ISBN 0-262-15039-5. David H D Warren, Luis M. Pereira and Fernando Pereira, Prolog - the language and its implementation compared with Lisp. ACM SIGART Bulletin archive, Issue 64. Proceedings of the 1977 symposium on Artificial intelligence and programming languages, pp 109 – 115.

Дополнителни врски

comp.lang.prolog FAQ Prolog: The ISO standard DECsystem-10 Prolog User’s Manual (plain text) describes a typical Edinburgh Prolog Prolog Tutorial by J.R.Fisher Runnable examples by Lloyd Allison On-line guide to Prolog Programming by Roman Bartak Learn Prolog Now! by Patrick Blackburn, Johan Bos and Kristina Striegnitz Prolog and Logic Programming by Dr Peter Hancox Adventure in Prolog, online tutorial by Dennis Merritt