Википедија

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

програмски јазик

Пролог (англиски: Prolog) — логички програмски јазик со општа намена кој се асоцира со вештачка интелигенција и компјутерска лингвистика.[1][2][3]

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

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

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

Синтакса и семантика

уреди

Во Пролог, програмската логика е изразена преку релации, додека пресметките се засноваат на прашања упатени до релациите. Релациите и прашањата се конструираат со единствениот податочен тип term.[4] Релациите се дефинирани со клаузи. За дадено прашање, механизмот во 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).

Шеми

уреди

Шема претставува решение кое се користи повеќепати за проблеми кои се чести во софтверскиот дизајн. Во пролог шемите се јавуваат под две имиња, скелети и техники,[9][10] клишеа,[11] program schemata,[12] и логичка описна шема.[13] An alternative to design patterns is higher order programming.[14]

Логика од повисок ред

уреди

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

Модули

уреди

За големи програмски решенија, Пролог нуди систем на модули. Овој систем е стандардазиран од ISO.[16] Но, не сите компајлери подршуваат модулирање, па постојат проблеми во компатибилност на различни компајлери.[17]

Имплементација

уреди

ISO Prolog

уреди

Стандардниот ISO Prolog се состои од два дела. ISO/IEC 13211-1,[15][18] објавен во 1995, цели кон стандардизација на постоечките имплементации на јадрените елементи на Пролог. ISO/IEC 13211-2,[15] објавен во 2000, ги стандардизира модулите на стандардот. Стандардот се одржува од SC22 работната група.[19] ANSI X3J17 е надгледувачка група за овој стандард.[20]

Критички осврт

уреди

Иако Пролог е широко употребуван во истражувањата и едукацијата, тој и останатите логички програмски јазици немаат начително влијание врз компјутерската индустрија генерално.[21] Повеќето апликации се мали за индустриските стандарди, со ретки прекорочувања од 100,000 линии на код.[21][22] Програмирање на големи апликации е комплицирано поради фактот дека не сите компајлери поддржуваат работа со модули.[17] Портабилноста исто се јавува како проблем.

Слични програмски јазици

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

Наводи

уреди
  1. ↑ Clocksin, William F.; Mellish, Christopher S. (2003). Programming in Prolog. Berlin ; New York: Springer-Verlag. ISBN 978-3-540-00678-7.
  2. ↑ Bratko, Ivan (2001). Prolog programming for artificial intelligence. Harlow, England ; New York: Addison Wesley. ISBN 0-201-40375-7.
  3. ↑ Covington, Michael A. (1994). Natural language processing for Prolog programmers. Englewood Cliffs, N.J.: Prentice Hall. ISBN 978-0-13-629213-5.
  4. ↑ 4,0 4,1 Lloyd, J. W. (1984). Foundations of logic programming. Berlin: Springer-Verlag. ISBN 3-540-13299-6.
  5. ↑ doi:10.1145/35043.35046
    Овој навод ќе се дополни автоматски во текот на следните неколку минути. Можете да го прескокнете редот или да го проширите рачно
  6. ↑ doi:10.1145/155360.155362
    Овој навод ќе се дополни автоматски во текот на следните неколку минути. Можете да го прескокнете редот или да го проширите рачно
  7. ↑ doi:10.1007/BF00297245
    Овој навод ќе се дополни автоматски во текот на следните неколку минути. Можете да го прескокнете редот или да го проширите рачно
  8. ↑ Merritt, Dennis (1989). Building expert systems in Prolog. Berlin: Springer-Verlag. ISBN 0-387-97016-9.
  9. ↑ Kirschenbaum, M.; Sterling, L.S. (1993). „Applying Techniques to Skeletons“. Constructing Logic Programs, (ed. J.M.J. Jacquet): 27–140.
  10. ↑ Sterling, Leon (2002). „Computational Logic: Logic Programming and Beyond“. Patterns for Prolog Programming. Lecture Notes in Computer Science. Lecture Notes in Computer Science. 2407: 17–26. doi:10.1007/3-540-45628-7_15. ISBN 978-3-540-43959-2.
  11. ↑ 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.
  12. ↑ Gegg-harrison, T. S. (1995). „Representing Logic Program Schemata in Prolog“. Procs. Twelfth International Conference on Logic Programming: 467–481.
  13. ↑ Deville, Yves (1990). Logic programming: systematic program development. Wokingham, England: Addison-Wesley. ISBN 0-201-17576-2.
  14. ↑ Naish, Lee (1996). „Higher-order logic programming in Prolog“. Higher-order logic programming in Prolog. Посетено на 2010-11-02.
  15. ↑ 15,0 15,1 15,2 ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva.
  16. ↑ ISO/IEC 13211-2: Modules.
  17. ↑ 17,0 17,1 Paulo Moura, Logtalk in Association of Logic Programming Newsletter. Vol 17 n. 3, August 2004. [1] Архивирано на 12 април 2010 г.
  18. ↑ A. Ed-Dbali; Deransart, Pierre; L. Cervoni (1996). Prolog: the standard: reference manual. Berlin: Springer. ISBN 3-540-59304-7.CS1-одржување: повеќе имиња: список на автори (link)
  19. ↑ „WG17 Working Group“. Архивирано од изворникот на 2009-10-24. Посетено на 2011-10-24.
  20. ↑ „X3J17 Committee“. Архивирано од изворникот на 2009-08-23. Посетено на 2011-10-24.
  21. ↑ 21,0 21,1 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.
  22. ↑ The Prolog 1000 database http://www.faqs.org/faqs/prolog/resource-guide/part1/section-9.html

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

уреди
  • 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 Архивирано на 27 јули 2003 г., 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.

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

уреди
 
Wikibooks
Англиските Викикниги нудат повеќе материјал на тема:
Преземено од „https://mk.wikipedia.org/w/index.php?title=Пролог_(програмски_јазик)&oldid=5117767“