Логическо програмиране: как работи, езици (Prolog) и примери

Логическото програмиране е използване на математическа логика за писане на компютърни програми. Съществуват специализирани езици за програмиране, в които потребителят може директно да въвежда логически оператори. Вероятно най-известният от тези езици се нарича Prolog. Алонзо Чърч е използвал форма на логическо програмиране в това, което днес е известно като ламбда калкулус. Логическо програмиране е използвано и в LISP.

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

Как работи логическото програмиране

Логическите програми се формулират като множества от факти и правила, обикновено представени като Хорнови клаузи (Horn clauses). Основни понятия:

• Факти — атомарни изказвания, които се приемат за верни (например parent(alice, bob)).
• Правила — импликации, които описват как едно изказване може да бъде изведено от други (например grandparent(X,Y) :- parent(X,Z), parent(Z,Y)).
• Запитвания (queries) — въпроси към базата от факти и правила; изпълнението търси доказателство за запитването.

Оперативно изпълнение в езици като Prolog използва механизми като унификация (unification) за съвпадение на термини и резолюция или SLD-резолюция за търсене на доказателства. За да намери решения, системата често използва backtracking — ако даден път за доказване се провали, тя се връща назад и пробва алтернативи.

Пример в Prolog

Ето прост пример с родителски отношения и правило за дядо/баба:

% факти parent(ivan, maria). parent(maria, petar). parent(anna, ivan).  % правило grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

Запитване: grandparent(ivan, Who). — системата ще върне Who = petar. Запитване: grandparent(Who, petar). — ще върне Who = ivan, а при допълнителни факти може да върне и други решения чрез backtracking.

Отрицание като неуспех (negation as failure)

Както беше споменато по-горе, много системи използват т.нар. negation as failure. На практиката това означава, че ако Prolog не може да докаже изказване p, той приема, че "не p" е вярно. Например:

bird(tweety). penguin(polly).  fly(X) :- bird(X), \+ penguin(X).

Запитване fly(tweety). ще е успешно (Tweety лети), а fly(polly). ще бъде неуспешно, защото Polly е пингвин. Важно е да се разбере, че това не е класическо логическо отрицание — то зависи от това, какво е известно в момента (от базата от факти и правила).

Други особености и терминология

• Декларативен vs оперативен изглед: Логическата програма описва какво е вярно, а не как да се изчисли. Все пак изпълнението (напр. редът на правилата, употребата на cut (!), и др.) влияе на поведението и може да направи програмата импурна.
• Cut (!): специфичен оператор в Prolog, който контролира backtracking и променя оперативната семантика.
• Деклариран език: освен Prolog съществуват и езици/парадигми като Datalog (фокусиран върху заявки и бази данни), Answer Set Programming (ASP) за сложни нелинейни задачи, Mercury (статично типизиран логически език) и miniKanren (вграден в Scheme/OCaml).

Приложения

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

• изкуствен интелект и експертни системи;
• репрезентация на знания и семантични мрежи;
• естествен език и синтактичен/семантичен анализ (напр. чрез DCG — Definite Clause Grammars в Prolog);
• системи за планиране, проверка на логически зависимости и декларативни заявки към бази данни.

Предимства и ограничения

Предимства:

• яснота и декларативност — програмата описва логика и взаимоотношения;
• подходящо за проблеми с интензивно използване на правила и търсене (логически задачи, дедукция);
• богати средства за изразяване на рекурсивни зависимости.

Ограничения:

• не всички проблеми са удобно представими като логически правила;
• оперативната семантика (ред на правила, cut, negation as failure) може да затрудни формалната прецизност и да доведе до неинтуитивно поведение;
• производителността при големи бази от факти и сложни търсения може да бъде предизвикателство без оптимизации.

Имплементации и ресурси

Популярни реализации на Prolog: SWI-Prolog, GNU Prolog, SICStus Prolog. За да учите, потърсете уводи в Prolog, книги за логическо програмиране и онлайн туториали. Практиката с малки примери (факти, правила, запитвания) е най-удобният начин да се разбере парадигмата.

Въпроси и отговори

В: Какво е логическо програмиране?

В: Кои са някои езици за програмиране, които използват логическо програмиране?

В: Каква е ролята на правилата и фактите в логическото програмиране?

В: Какво представлява отрицанието като неуспех в логическото програмиране?

В: Какво е слабо отрицание в логическото програмиране?

Въпрос: Кой е използвал форма на логическо програмиране в ламбда калкулуса?

Въпрос: Кой е най-известният език за програмиране, който позволява на потребителите директно да въвеждат логически твърдения?

Търсене по буква