Пролог (мова програмування)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Цей термін має також інші значення. Докладніше — у статті Пролог.
Prolog
Парадигма: логічне програмування
Дата появи: 1972
Розробник: Алан Кольмерое (англ.)
Основні реалізації: BProlog (англ.), Ciao (англ.), ECLiPSe (англ.), GNU Prolog (англ.), Jekejeke Prolog, Logic Programming Associates (англ.), Пролог Poplog (англ.), P# (англ.), Quintus, SICStus (англ.), Strawberry (англ.), SWI-Prolog, tuProlog (англ.), XSB (англ.), YAP-Prolog (англ.)
Діалекти: Пролог ISO, Единбурзька Пролог
Вплинула на: Visual Prolog (англ.), Mercury (англ.), Oz (англ.), Erlang (англ.), Strand (англ.), KL0 (англ.), KL1 (англ.), Datalog (англ.)
Звичайні розширення файлів: .pl .pro .P

Проло́г — мова логічного програмування загального призначення, пов'язана зі штучним інтелектом та математичною лінгвістикою.[1][2][3]

Пролог має корені в логіці першого порядку, математичній логіці, та, на відміну від багатьох інших мов програмування, є декларативною: логіка програми виражається в термінах відношень, представлених як факти та правила (англ.). Обчислення ініціюється запуском запиту над цими відношеннями.[4]

Цю мову програмування спочатку було задумано групою навколо Алана Кольмерое (англ.) у Марселі на початку 1970-тих, а першу систему Пролог було розроблено у 1972-му Аланом Кольмерое та Філіпом Русселем (фр.).[5][6]

Пролог була однією з перших логічних мов програмування,[7] й залишається найпопулярнішою серед таких мов і на сьогодні, маючи багато безкоштовних та комерційних реалізацій. Хоча спочатку цю мову програмування і було націлено на обробку природної мови, вона з тих пір простяглася далеко в інші області, як-то доведення теорем (англ.),[8] експертні системи,[9] ігри, системи автоматичних відповідей, онтології та складні системи керування. Сучасні середовища Прологу підтримують як створення графічних інтерфейсів користувача, так і адміністративні або мережеві застосування.

Зміст

Синтаксис та семантика [ред.]

Докладніше: Синтаксис та семантика Прологу

Програмна логіка у Пролозі виражається в термінах відношень, а обчислення ініціюється запуском запиту над цими відношеннями. Відношення та запити створюються з використанням єдиного типу даних Прологу, терму.[4] Відношення виражаються реченнями. Отримавши запит, рушій Прологу намагається знайти спростування (англ.) резолюції заперечення запиту. Якщо заперечення запиту може бути спростовано, тобто, знайдено конкретизацію всіх вільних змінних, що робить об'єднання атомарних формул та множини-синґлетону, що складається із заперечення запиту, хибним, то з цього випливає, що початковий запит, із застосуванням знайденої конкретизації, є логічним висновком програми. Це робить Пролог (та інші логічні мови програмування) надзвичайно зручною для застосування у базах даних, символьній математиці та граматичному аналізі мов. Оскільки Пролог дозволяє нечисті предикати, перевірка істинності певних спеціальних предикатів може мати деякий навмисний побічний ефект, як-то виведення значення на екран. Через це програмістові дозволено певною мірою використовувати звичайне імперативне програмування, коли логічна парадигма є незручною. Пролог має як чисту логічну підмножину, що називається «чиста Пролог», так і ряд позалогічних властивостей.

Типи даних [ред.]

Єдиним типом даних Прологу є терм. Терми можуть бути атомами, числами, змінними або складеними термами.

  • Атом це загальна назва без притаманного значення. Прикладами атомів є x, синій, 'Бутерброд' та 'якийсь атом'.
  • Числа можуть бути з плаваючою комою (англ.), або цілими.
  • Змінні позначаються стрічками, що складаються з літер, цифр та символів підкреслення, і починаються з великої літери або символу підкреслення. Змінні дуже подібні до змінних в логіці в тім, що вони є позначками-заповнювачами для довільних термів.
  • Складений терм складається з атому, що зветься функтор, та певної кількості аргументів, що в свою чергу теж є термами. Складені терми зазвичай записуються у вигляді функтора, за яким у дужках слідує перелік термів-аргументів через кому. Кількість аргументів називається арністю терму. Атом може розглядатися як складений терм нульової арності. рік_машини('Таврія', 1988) та 'Друзі_Особи'(грай,[око,тур]) є прикладами складених термів.

Особливі випадки складених термів:

  • Список є впорядкованою колекцією термів. Він позначається квадратними дужками з термами, розділеними комами, або, у випадку порожнього списку, []. Наприклад, [1,2,3], або [червоний,зелений,синій].
  • Стрічки: послідовність символів у лапках, еквівалентна спискові (числових) кодів символів, зазвичай у місцевому кодуванні, або в Юнікоді, якщо система підтримує Юнікод. Наприклад, "бути чи не бути".

Правила та факти [ред.]

Прологові програми описують відношення, визначені реченнями. Чиста Пролог обмежена диз’юнктами Хорна (англ.). Є два типи речень: факти та правила. Правило має вигляд

Голова :- Тіло.

і читається як «голова істинна, якщо тіло істинне». Тіло правила складається з викликів предикатів, що називаються цілями правила. Вбудований предикат ,/2 (що значить двоарний оператор з ім'ям ,) позначає кон'юнкцію цілей, а ;/2 — диз'юнкцію. Кон'юнкції та диз'юнкції можуть бути присутні лише в тілі, але не в голові правила.

Речення з порожніми тілами називаються фактами. Наприклад:

кіт(мурко).

що рівноцінне правилу:

кіт(мурко) :- true.

Вбудований предикат true/0 є завжди істинним.

Маючи наведений вище факт, можна спитати:

чи є мурко котом?

?- кіт(мурко).
Yes

що є котами?

?- кіт(X).
X = мурко

Речення з тілами називаються правилами. Наприклад:

тварина(X):- кіт(X).

Якщо ми додамо це правило та спитаємо, що є тваринами?

?- тварина(X).
X = мурко

Оскільки природа багатьох вбудованих предикатів є відносною, їх зазвичай можна використовувати в кількох напрямках. Наприклад, length/2 може використовуватися як для визначення довжини списку (length(List, L), коли задано список List), так і для створення кістяка списку заданої довжини (length(X, 5)), а також і для створення кістяків списків та їх довжин одночасно (length(X, L)). Так само, append/3 може використовуватися як для з'єднання двох списків (append(ListA, ListB, X) коли задано списки ListA та ListB), так і для розділення заданого списку на частини (append(X, Y, List), коли задано список List). Тому відносно невеликий набір бібліотечних предикатів є достатнім для великої кількості прологових програм.

Як мова загального призначення, Пролог також пропонує різноманітні вбудовані предикати для виконання всякої поточної діяльності, як-то введення/виведення (англ.), використання графіки, та іншої взаємодії з операційною системою. Ці предикати не мають значення відношень, і корисні лише для побічних ефектів, що вони спричиняють у системі. Наприклад, предикат write/1 відображає терм на екрані.

Виконання [ред.]

Виконання прологової програми починається задаванням користувачем єдиної цілі, що зветься запитом. З точки зору логіки, рушій Прологу намагається знайти спростування резолюції заперечення цього запиту. Метод резолюції, що використовується у Пролозі, називається SLD-резолюцією (англ.). Якщо заперечення запиту може бути спростовано, з цього випливає, що запит, з відповідними зв'язуваннями змінних, є логічним висновком програми. У такому разі всі створені зв'язування змінних повідомляються користувачеві, і про запит повідомляється, що він досяг успіху. З практичної точки зору, стратегію виконання Прологу можна уявити як узагальнення викликів функцій в інших мовах, з тією різницею, що заданому запитові можуть відповідати голови кількох речень. В такому випадку система створює точку вибору, об'єднує ціль з головою речення першої альтернативи, і продовжує цілями цієї першої альтернативи. Якщо у напрямку виконання програми будь-яка ціль зазнає невдачі, всі зв'язування змінних, що було зроблено від останньої на той момент точки вибору, скасовуються, і виконання продовжується з наступною альтернативою цієї точки вибору. Ця стратегія виконання називається хронологічним пошуком з вертанням. Наприклад:


мати_дитини(ірина, святослав).
 
батько_дитини(ярослав, святослав).
батько_дитини(ярослав, анна).
батько_дитини(володимир, ярослав).
 
брат_або_сестра(X, Y)        :- батько_або_мати_дитини(Z, X), батько_або_мати_дитини(Z, Y).
 
батько_або_мати_дитини(X, Y) :- батько_дитини(X, Y).
батько_або_мати_дитини(X, Y) :- мати_дитини(X, Y).


Виходячи з цього, наступний запит оцінюється як істинний:

?- брат_або_сестра(святослав, анна).
Yes

Це отримується наступним чином: Спочатку єдиною відповідною головою речення до запиту брат_або_сестра(святослав, анна) є перша, тому надавання запиту є рівноцінним надаванню тіла того речення з відповідними зв'язуваннями змінних, тобто, кон'юнкція (батько_або_мати_дитини(Z,святослав), батько_або_мати_дитини(Z,анна)). Наступною ціллю для доведення є крайня зліва з цієї кон'юнкції, тобто, батько_або_мати_дитини(Z,святослав). Цій цілі відповідають голови двох правил. Система створює точку вибору, і пробує перший вибір, чиїм тілом є батько_дитини(Z, святослав). Цю ціль може бути доведено з використанням факту батько_дитини(ярослав, святослав), тому створюється зв'язування Z = ярослав, і наступною ціллю для доведення стає друга частина наведеної вище кон'юнкції: батько_або_мати_дитини(ярослав, анна). І знову, це може бути доведено відповідним фактом. Оскільки всі цілі доведено, запит досягає успіху. Оскільки запит не містить жодних змінних, користувачеві не повідомляються жодні зв'язування. Запит зі змінними, як-то:

?- батько_дитини(Батько, Дитина).

перелічує всі дійсні відповіді пошуку з вертанням.

Зверніть увагу, що з наведеним вище кодом запит ?- брат_або_сестра(святослав, святослав). також досягає успіху. Якщо потрібно, можна додати додаткові цілі для опису відповідних обмежень.

Цикли та рекурсія [ред.]

Ітеративні алгоритми може бути реалізовано засобами рекурсивних предикатів.

Заперечення [ред.]

Вбудований предикат Прологу \+/1 забезпечує заперечення як невдачу (англ.), що уможливлює немонотонну (англ.) аргументацію. Ціль \+ легальне(X) у правилі

нелегальне(X) :- \+ легальне(X).

обчислюється наступним чином. Пролог намагається довести легальне(X). Якщо доведення цієї цілі знайдено, то початкова ціль (тобто, \+ легальне(X)) зазнає невдачі. Якщо доведення не може бути знайдено, то початкова ціль досягає успіху. Отже, префіксний оператор \+/1 називається оператором «недовідне», оскільки запит ?- \+ Ціль. досягає успіху, якщо Ціль не є довідною. Цей вид заперечення є правильним, якщо його аргумент є замкненим (англ.) (тобто, не містить змінних). Правильність втрачається, якщо аргумент містить змінні, та процедура доведення є повною. Зокрема, запит ?- нелегальне(X). тепер вже не може бути використано для перелічення усіх речей, що є нелегальними.

Приклади [ред.]

Далі слідують деякі приклади програм, написаних Прологом.

Вітання світові [ред.]

Приклад запиту:

?- write('Привіт, світе!'), nl.
Привіт, світе!
true.
 
?-

Оптимізація компілятора [ред.]

Будь-яке обчислення може бути виражено декларативно як послідовність переходу станів. Як приклад, оптимізуючий компілятор з трьома проходами оптимізації може бути реалізовано як відношення між початковою програмою та її оптимізованою формою:

програма_оптимізована(Прог0, Прог) :-
    оптимізація_прохід_1(Прог0, Прог1),
    оптимізація_прохід_2(Прог1, Прог2),
    оптимізація_прохід_3(Прог2, Прог).

або рівнозначно з використанням запису граматики визначених речень:

програма_оптимізована --> оптимізація_прохід_1, оптимізація_прохід_2, оптимізація_прохід_3.

Швидке сортування [ред.]

Алгоритм швидкого сортування, що ставить у відповідність спискові його відсортовану версію:

розділення([], _, [], []).
розділення([X|Xs], Опорне, Малі, Великі) :-
    (   X @< Опорне ->
        Малі = [X|Решта],
        розділення(Xs, Опорне, Решта, Великі)
    ;   Великі = [X|Решта],
        розділення(Xs, Опорне, Малі, Решта)
    ).
 
швидке_сортування([])     --> [].
швидке_сортування([X|Xs]) -->
    { розділення(Xs, X, Менші, Більші) },
    швидке_сортування(Менші), [X], швидке_сортування(Більші).

Шаблони проектування [ред.]

Шаблон проектування це загальне рішення багаторазового використання поширеної проблеми у проектуванні програмного забезпечення. У Пролозі шаблони проектування можуть носити різні назви: кістяки та техніки,[10][11] кліше,[12] програмні схеми[13] та схеми опису логіки.[14] Альтернативою до шаблонів проектування є програмування вищих порядків.[15]

Програмування вищих порядків [ред.]

Детальніші відомості з цієї теми Ви можете знайти в статті Логіка вищих порядків (англ.) та Програмування вищих порядків (англ.).

За визначенням, логіка першого порядку не дозволяє квантифікації предикатів. Предикат вищих порядків це предикат, що має один або більше інших предикатів у якості аргументів. Пролог вже має деякі вбудовані предикати вищих порядків, такі як call/1, call/2, call/3, findall/3, setof/3 та bagof/3.[16] Крім того, оскільки довільні цілі Прологу можуть створюватись та оцінюватись у реальному часі, нескладно писати предикати вищих порядків на кшталт maplist/2, що застосовує довільний предикат до кожного елемента наданого списку, та sublist/3, що відфільтровує елементи, що задовольняють наданому предикатові, беручи до уваги й карування (англ.).[15]

Для перетворення рішень з часового представлення (підстановки відповідей при зворотному пошуку) до просторового представлення (термів) Пролог має різноманітні предикати для всіх рішень, що збирають всі підстановки відповідей для заданого запиту до списку. Це може використовуватися у спискових виразах. Наприклад, досконалі числа дорівнюють сумі своїх дільників:

 perfect(N) :-
     between(1, inf, N), U is N // 2,
     findall(D, (between(1,U,D), N mod D =:= 0), Ds),
     sumlist(Ds, N).

Це може бути використано для перелічування досконалих чисел, а також для перевірки, чи є число досконалим.

Модулі [ред.]

Для великого програмування (англ.) Пролог пропонує систему модулів. Цю систему модулів стандартизовано ISO.[17] Проте, не всі компілятори Прологу підтримують модулі, а також існують проблеми сумісності між системами модулів основних компіляторів Прологу.[18] Отже, модулі, написані на одному компіляторі Прологу, не обов'язково працюватимуть на інших.

Граматичний розбір [ред.]

Докладніше: Синтаксис та семантика Прологу#Граматики визначених речень та Граматика визначених речень

Існує спеціальний запис, що називається граматики визначених речень. Правило, визначене через -->/2 замість :-/2, розкривається препроцесором (expand_term/2, засіб, аналогічний макросам в інших мовах) відповідно до кількох прямих правил переписування, маючи результатом звичайні речення Прологу. Найважливіше, що переписування споряджає предикат двома додатковими аргументами, що можуть використовуватися для неявного прокручування стану через них, аналогічно до монад в інших мовах. Граматики визначених речень часто використовуються для написання синтаксичних аналізаторів або генераторів списків, оскільки вони надають зручний інтерфейс до списків відмінностей.

Мета-інтерпретатори та рефлексія [ред.]

Пролог є гомоіконічною (англ.) мовою та забезпечує багато засобів для рефлексії (англ.). Її неявна стратегія виконання робить можливим написання стислого мета-циклічного інтерпретатора (англ.) (що також називають мета-інтерпретатором) коду чистої Пролог.[19] Оскільки прологові програми самі є послідовностями термів Прологу (:-/2 є інфіксним оператором), що легко читаються та аналізуються з використанням вбудованих механізмів (як-то read/1), нескладно писати спеціальні інтерпретатори, що розширюють Пролог предметно-орієнтованими властивостями.

Повнота за Тюрингом [ред.]

Чиста Пролог базується на підмножині логіки предикатів (англ.) першого порядку, диз’юнктах Хорна (англ.), що є повною за Тюрингом. Повноту за Тюрингом Прологу може бути показано шляхом використання її для імітації машини Тюрінга:

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).
 
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).
 
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
 
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
 
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

Простий приклад машини Тюринга визначається фактами:

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

Ця машина виконує збільшення на одиницю числа в унарному кодуванні: вона проходить будь-яке число комірок «1» та додає додаткову «1» у кінці. Приклад запиту та результату:

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

Це показує, як будь-яке обчислення може бути представлено декларативно як послідовність переходів станів, реалізована у Пролозі як відношення між послідовними станами, що нас цікавлять.

Реалізація [ред.]

Детальніші відомості з цієї теми Ви можете знайти в статті Порівняння реалізацій Прологу (англ.).

Пролог ISO [ред.]

Стандарт Прологу ISO складається з двох частин. ISO/IEC 13211-1,[16][20] опублікована у 1995 році, намагається стандартизувати наявні застосування багатьох реалізацій ключових елементів Прологу. Вона прояснила аспекти цієї мови, що раніше були неоднозначними, і веде до переносимості програм. Є дві еррати: Cor.1:2007[21] та Cor.2:2012.[22] ISO/IEC 13211-2,[16] опублікована у 2000 році, додає до стандарту підтримку модулів. Стандарт підтримується робочою групою ISO/IEC JTC1 (англ.)/SC22 (англ.)/WG17[23]. Технічною дорадчою групою США для цього стандарту є ANSI X3J17.[24]

Компіляція [ред.]

Для більшої ефективності код Прологу зазвичай компілюється в код абстрактної машини, що часто знаходиться під впливом набору інструкцій базованої на регістрах (англ.) абстрактної машини Уоррена (англ.).[25] Деякі реалізації вживають абстрактну інтерпретацію (англ.) для встановлення інформації про тип та напрямок предикатів під час компіляції, або, для вищої продуктивності, компілюють у код реальної машини.[26] У спільноті логічного програмування придумування ефективних методів реалізації коду Прологу є полем активних досліджень, і в деяких реалізаціях вживається багато інших методів виконання. Вони включають перетворення речень у двійкову форму та віртуальні машини, базовані на стеку (англ.).[Джерело?]

Хвостова рекурсія [ред.]

Для детермінованих предикатів, що демонструють хвостову рекурсію, або, загальніше, хвостові виклики, прологові системи зазвичай реалізують добре відомий метод оптимізації, що зветься оптимізацією хвостового виклику (англ. Tail Call Optimization, TCO): Перед виконанням виклику у хвостовій позиції кадр стеку речення скасовується. Отже, детерміновані предикати з хвостовою рекурсією виконуються з незмінним простором стеку, як цикли в інших мовах.

Індексування термів [ред.]

Детальніші відомості з цієї теми Ви можете знайти в статті Індексування термів (англ.).

Пошук речень, що є об'єднуваними із термом у запиті, є лінійним відносно кількості речень. Індексування термів (англ.) використовує структуру даних, що уможливлює суб-лінійний пошук.[27] Індексування впливає лише на продуктивність програми, семантики воно не зачіпає.

Табулювання [ред.]

Деякі прологові системи (BProlog (англ.), XSB (англ.) та Yap) реалізують метод мемоїзації (англ.), що зветься табулювання, що звільняє користувача від необхідності зберігати проміжні результати вручну.[28][29]

Апаратна реалізація [ред.]

Під час розробки проекту комп’ютерних систем п’ятої генерації (англ.) були спроби реалізувати Пролог в апаратному вигляді з метою отримання швидшого виконання спеціальними архітектурами.[30][31][32] До того ж, Пролог має ряд властивостей, що можуть дозволити прискорення шляхом паралельного виконання.[33] Новішими підходами було компілювати обмежені прологові програми у програмовані користувачем вентильні матриці.[34] Однак, швидкий розвиток апаратного забезпечення загального призначення послідовно випередив більш спеціалізовані архітектури.

Критика [ред.]

Хоча Пролог широко застосовується у дослідницькій роботі та освіті, вона та інші логічні мови програмування не справили істотного впливу на комп'ютерну промисловість у цілому.[35] Більшість застосунків є малими за промисловими стандартами, лише деякі з них мають понад 100,000 рядків коду.[35][36] Велике програмування (англ.) вважається складним, оскільки не всі компілятори Прологу підтримують модулі, а також існують проблеми сумісності між системами модулів основних прологових компіляторів.[18] Переносимість коду Прологу між реалізаціями також була проблемою, але розробка після 2007 року означала: «переносимість всередині сімейства реалізацій Прологу, що походять від Единбурзької Пролог або Quintus, достатньо гарна для підтримки реальних переносимих програм».[37]

Програмне забезпечення, розроблене на Пролозі, критикувалося за високі втрати продуктивності у порівнянні зі звичайними мовами програмування. Однак, вдосконалення методів реалізації зменшило втрати аж до 25%-50% для деяких застосунків.[38]

Пролог не є чисто декларативною: оскільки вона має оператор відсікання, для її розуміння потрібне також і процедурне прочитання написаних нею програм.[39] Порядок речень у прологовій програмі є суттєвим. Інші логічні мови програмування, такі як Datalog (англ.), є чисто декларативними: речення можуть надаватися у довільному порядку.

Розширення [ред.]

З Прологу було розвинуто різноманітні реалізації для розширення можливостей логічного програмування у численних напрямках. Вони включають типи, режими, логічне програмування з обмеженнями (англ.), об'єктно-орієнтоване логічне програмування (англ. object-oriented logic programming, OOLP), паралелізм, лінійну логіку (англ.), можливості функціонального програмування та програмування логіки вищих порядків (англ.), плюс функціональну сумісність з базами знань:

Типи [ред.]

Пролог є нетипізованою мовою. Спроби запровадити типи сходять до 1980-х років,[40][41] і станом на 2008 рік все ще існують спроби розширити Пролог типами.[42] Ця інформація корисна не лише для безпечної типізації (англ.), а й для розуміння прологових програм.[43]

Режими [ред.]

Синтаксис Прологу не визначає, які з аргументів предикату є вхідними, а які вихідними.[44] Проте ця інформація є істотною, і рекомендується включати її до коментарів.[45] Режими надають цінну інформацію для розуміння прологових програм,[43] а також можуть використовуватися для прискорення виконання.[46]

Обмеження [ред.]

Логічне програмування з обмеженнями (англ.) розширює Пролог включенням концепцій із задоволення обмежень (англ.).[47][48] Програма з логікою обмежень дозволяє обмеження в тілах речень, як, наприклад, A(X,Y) :- X+Y>0. Це підходить для великомасштабних задач комбінаторної оптимізації[49] й, отже, для застосувань у промислових умовах, таких як автоматизоване складання розкладів та планування виробництва (англ.). Більшість прологових систем постачаються із щонайменше одним розв'язувачем обмежень для зліченних областей визначення, а часто також і з розв'язувачами для інших областей визначення, таких як дійсні числа.

Програмування вищих порядків [ред.]

HiLog та λProlog (англ.) розширюють Пролог властивостями програмування вищих порядків (англ.). Пролог ISO зараз підтримує вбудовані предикати call/2, call/3, … що слугують програмуванню вищих порядків та лямбда-абстракціям.

maplist(_Cont, [], []).
maplist(Cont, [X1|X1s], [X2|X2s]) :-
   call(Cont, X1, X2),
   maplist(Cont, X1s, X2s).

Об'єктна орієнтація [ред.]

Logtalk (англ.) це об'єктно-орієнтована мова логічного програмування, що може використовувати більшість реалізацій Прологу в якості внутрішнього компілятора. Як мультипарадигмова мова, вона включає підтримку як прототипів, так і класів.

Oblog (англ.) це невелике переносне об'єктно-орієнтоване розширення Прологу від Маргарити Макдугалл (англ. Margaret McDougall) з EdCAAD Единбурзького університету.

Objlog (англ.) була фреймовою мовою, що поєднувала об'єкти та Пролог II від НЦНД Франції у Марселі.

Графіка [ред.]

Прологовими системами, що пропонують графічну бібліотеку (англ.), є SWI-prolog,[50] Visual-prolog, LPA Prolog для Windows та B-Prolog.

Паралелізм [ред.]

Prolog-MPI є розширенням SWI-Prolog з відкритим кодом для розподілених обчислень через інтерфейс передачі повідомлень (англ. Message Passing Interface).[51] Також існує декілька паралельних мов програмування Пролог.[52]

Веб-програмування [ред.]

Деякі реалізації Прологу, особливо SWI-Prolog та Ciao, підтримують веб-програмування на серверному боці (англ.) з підтримкою веб-протоколів, HTML та XML.[53] Існують також розширення для підтримки форматів семантичної павутини, таких як RDF та OWL.[54][55] Пролог також пропонувалася як мова клієнтського боку (англ.).[56]

Adobe Flash [ред.]

Cedar є безкоштовним та елементарним інтерпретатором Прологу. Від версії 4 та вище Cedar має підтримку FCA (Flash Cedar App). Це забезпечує нову платформу для програмуванні на Пролозі через ActionScript.

Інші [ред.]

Інтерфейси до інших мов [ред.]

Існують каркаси для сполучення між Прологом та іншими мовами:

  • LPA Intelligence Server дозволяє включення LPA Prolog до C, C#, C++, Java, VB, Delphi, .NET, Lua, Python та інших мов. Він використовує спеціальний стрічковий тип даних, до надає LPA Prolog
  • Logic Server API дозволяє як розширення Прологом, так і його включення до C, C++, Java, VB, Delphi, .NET та будь-яких інших мов/середовищ, що можуть викликати .dll або .so. Його реалізовано для Amzi! Prolog + Logic Server, але специфікацію API може бути зроблено доступною для будь-якої реалізації.
  • JPL це двоспрямований міст між Java та Прологом, що постачається з SWI-Prolog за замовчуванням, і що дозволяє Java та Прологові викликати одне одного (рекурсивно). Він відомий гарною підтримкою паралельності, та знаходиться в активній розробці.
  • InterProlog, програмна бібліотека мосту між Java та Прологом, що реалізує двоспрямовані виклики предикатів/методів між обома мовами. Об'єкти Java можуть відображатися у терми Прологу, і навпаки. Дозволяє розробку графічного інтерфейсу користувача та іншої функціональності в Java, залишаючи обробку логіки у шарі Прологу. Підтримує XSB (англ.), із запланованою на 2013 рік підтримкою SWI-Prolog та YAP.
  • Prova (англ.) надає інтеграцію рідного синтаксису з Java, обмін повідомленнями між програмними агентами та правила реакції. Prova позиціонує себе як скриптову систему на базі правил (англ. rule-based scripting, RBS) для підпрограмного забезпечення. Ця мова відкриває нові обрії у поєднанні імперативного та декларативного програмування.
  • PROL це вбудовуваний рушій Прологу для Java. Він включає невелике інтегроване середовище розробки та декілька бібліотек.
  • GNU Prolog для Java є реалізацією Прологу ISO як бібліотеки Java (gnu.prolog)
  • Ciao (англ.) надає інтерфейси до C, C++, Java та реляційних баз даних.
  • C#-Prolog є інтерпретатором Прологу, написаним (керованою) C#. Може легко інтегруватися у програми мовою C#. Характеристики: надійний та досить швидкий інтерпретатор, інтерфейс командного рядка, інтерфейс Windows, вбудована граматика визначених речень, XML-предикати, SQL-предикати, розширюваний. Доступний повний джерельний код, включно з генератором синтаксичного аналізатора, що може бути використано для додавання розширень особливого призначення.
  • Jekejeke Prolog API надає сильнозв'язані можливості паралельних вхідних та вихідних викликів між Прологом та Java або Android, з визначною можливістю створення індивідуальних об'єктів баз знань. Він може застосовуватися для вбудовування Прологу ISO до самостійних застосунків, аплетів, сервлетів, APK (англ.) тощо.
  • Абстрактна машина Уоррена для PHP, компілятор та інтерпретатор Прологу в PHP 5.3. Бібліотека, що може використовуватися самостійно, або з каркасом Symfony2.1.

Історія [ред.]

Назву Пролог (фр. Prolog) було обрано Філіпом Русселем (фр.) як абревіатуру від програмування в логіці (фр. programmation en logique). Пролог було створено у 1972 році Аланом Кольмерое (англ.) з Філіпом Русселем на основі процедурної інтерпретації диз’юнктів Хорна (англ.) Роберта Ковальського (англ.). Це було частково мотивоване бажанням примирити використання логіки як мови декларативного представлення знань з процедурним представленням знань, що було популярне в Північній Америці в кінці 1960-х і на початку 1970-х років. Згідно з Робертом Ковальським (англ.), першу прологову систему було розроблено у 1972 році Аланом Кольмерое та Філіпом Русселем.[5] Перші реалізації Прологу були інтерпретаторами, однак, Девід Уоррен (англ.) створив абстрактну машину Уоррена (англ.), ранній та впливовий компілятор Прологу, що прийшов, щоби визначити «Единбурзький» діалект Прологу, що послужив основою синтаксису більшості сучасних реалізацій.

Більшість сучасних розробок Прологу пішли від поштовху проекту комп’ютерних систем п’ятої генерації (англ.), в рамках якого було розроблено варіант Прологу під назвою Kernel Language (англ.) для його першої операційної системи.

Чисту Пролог було спочатку обмежено використанням системи доведення теорем з диз’юнктами Хорна (англ.) форми:

Г :- Т1, ..., Тn.

Застосунок системи доведення теорем обробляє такі речення як процедури:

щоби показати/розв’язати Г, покажи/розв’яжи Т1 та ... та Тn.

Однак, чисту Пролог незабаром було розширено включенням заперечення як невдачі (англ.), у якому заперечні умови форми not(Тi) показуються шляхом спроби і невдачі доведення відповідних позитивних умов Тi.

Подальші розширення Прологу оригінальною командою ввели до реалізацій можливості логічного програмування з обмеженнями (англ.).

Див. також [ред.]

Споріднені мови [ред.]

Примітки [ред.]

  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. ↑ а б Lloyd, J. W. (1984), Foundations of logic programming, Berlin: Springer-Verlag, ISBN 3-540-13299-6 
  5. ↑ а б Kowalski, R. A. (1988), «The early years of logic programming», Communications of the ACM 31: 38, doi:10.1145/35043.35046 
  6. ↑ Colmerauer, A.; Roussel, P. (1993), «The birth of Prolog», ACM SIGPLAN Notices 28 (3): 37, doi:10.1145/155360.155362 
  7. ↑ Див. Логічне програмування#Історія.
  8. ↑ Stickel, M. E. (1988), «A prolog technology theorem prover: Implementation by an extended prolog compiler», Journal of Automated Reasoning 4 (4): 353–380, doi:10.1007/BF00297245 
  9. ↑ Merritt, Dennis (1989), Building expert systems in Prolog, Berlin: Springer-Verlag, ISBN 0-387-97016-9 
  10. ↑ Kirschenbaum, M.; Sterling, L.S. (1993), «Applying Techniques to Skeletons», Constructing Logic Programs, (ed. J.M.J. Jacquet): 27–140 
  11. ↑ Sterling, Leon (2002), Patterns for Prolog Programming, «Computational Logic: Logic Programming and Beyond», 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 
  12. ↑ 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.
  13. ↑ Gegg-harrison, T. S. (1995), «Representing Logic Program Schemata in Prolog», Procs. Twelfth International Conference on Logic Programming: 467–481 
  14. ↑ Deville, Yves (1990), Logic programming: systematic program development, Wokingham, England: Addison-Wesley, ISBN 0-201-17576-2 
  15. ↑ а б Naish, Lee (1996), «Higher-order logic programming in Prolog», Higher-order logic programming in Prolog, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.4505, процитовано 2010-11-02 
  16. ↑ а б в ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva.
  17. ↑ ISO/IEC 13211-2: Modules.
  18. ↑ а б Paulo Moura, Logtalk in Association of Logic Programming Newsletter. Vol 17 n. 3, August 2004. [1]
  19. ↑ Shapiro; Ehud, Y.; Sterling, Leon (1994), The art of Prolog: advanced programming techniques, Cambridge, Mass: MIT Press, ISBN 0-262-19338-8 
  20. ↑ Ed-Dbali, A.; Deransart, Pierre; Cervoni, L. (1996), Prolog: the standard: reference manual, Berlin: Springer, ISBN 3-540-59304-7 
  21. ↑ ISO/IEC 13211-1:1995/Cor.1:2007
  22. ↑ ISO/IEC 13211-1:1995/Cor 2:2012
  23. ↑ WG17 Working Group
  24. ↑ X3J17 Committee
  25. ↑ David H. D. Warren. «An abstract Prolog instruction set». Technical Note 309, SRI International (англ.), Menlo Park, CA, October 1983.
  26. ↑ Van Roy, P.; Despain, A. M. (1992), «High-performance logic programming with the Aquarius Prolog compiler», Computer 25: 54, doi:10.1109/2.108055 
  27. ↑ Graf, Peter (1995), Term indexing, Berlin ; New York: Springer, ISBN 978-3-540-61040-3 
  28. ↑ Swift, T. (1999), Annals of Mathematics and Artificial Intelligence 25 (3/4): 201–200, doi:10.1023/A:1018990308362 
  29. ↑ Neng-Fa Zhou and Taisuke Sato (2003): Efficient Fixpoint Computation in Linear Tabling, In Proceedings of the 5th ACM SIGPLAN Conference on Principles and practice of declaritive programming, pp. 275–283.
  30. ↑ Abe, S.; Bandoh, T.; Yamaguchi, S.; Kurosawa, K.; Kiriyama, K. (1987), High performance integrated Prolog processor IPP, pp. 100, doi:10.1145/30350.30362 
  31. ↑ «A Prolog processor based on a pattern matching memory device - Third International Conference on Logic Programming - Lecture Notes in Computer Science». Springer Berlin / Heidelberg. 1986. doi:10.1007/3-540-16492-8_73. 
  32. ↑ Taki, K.; Nakajima, K.; Nakashima, H.; Ikeda, M. (1987), «Performance and architectural evaluation of the PSI machine», ACM SIGPLAN Notices 22 (10): 128, doi:10.1145/36205.36195 
  33. ↑ Gupta, G.; Pontelli, E.; Ali, K. A. M.; Carlsson, M.; Hermenegildo, M. V. (2001), «Parallel execution of prolog programs: a survey», ACM Transactions on Programming Languages and Systems 23 (4): 472, doi:10.1145/504083.504085 
  34. ↑ http://www.cl.cam.ac.uk/~am21/research/sa/byrdbox.ps.gz
  35. ↑ а б 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.
  36. ↑ The Prolog 1000 database http://www.faqs.org/faqs/prolog/resource-guide/part1/section-9.html
  37. ↑ Jan Wielemaker and Vıtor Santos Costa: Portability of Prolog programs: theory and case-studies. CICLOPS-WLPE Workshop 2010.
  38. ↑ Sterling, Leon (1990), The Practice of Prolog, MIT Press (англ.), p. 32, ISBN 0-262-19301-9, «Although some CAD algorithms run between 2 to 4 times slower than their counterparts in C, the interactive response of the editor is comparable to a similar program written in C.» 
  39. ↑ Declarative vs procedural
  40. ↑ Mycroft, A.; O'Keefe, R. A. (1984), «A polymorphic type system for prolog☆», Artificial Intelligence 23 (3): 295, doi:10.1016/0004-3702(84)90017-1 
  41. ↑ Pfenning, Frank (1992), Types in logic programming, Cambridge, Mass: MIT Press, ISBN 0-262-16131-1 
  42. ↑ Schrijvers, Tom; Santos Costa, Vitor; Wielemaker, Jan; Demoen, Bart (2008), «Towards Typed Prolog», у Maria Garcia de la Banda; Enrico Pontelli, Logic programming : 24th international conference, ICLP 2008, Udine, Italy, December 9-13, 2008 : proceedings, Lecture Notes in Computer Science, 5366, pp. 693–697, doi:10.1007/978-3-540-89982-2_59, ISBN 9783540899822 
  43. ↑ а б Apt, K. R.; Marchiori, E. (1994), «Reasoning about Prolog programs: From modes through types to assertions», Formal Aspects of Computing 6 (6): 743, doi:10.1007/BF01213601 
  44. ↑ O'Keefe, Richard A. (1990), The craft of Prolog, Cambridge, Mass: MIT Press, ISBN 0-262-15039-5 
  45. ↑ Covington et al; Roberto Bagnara; O'Keefe; Jan Wielemaker; Simon Price (2010). «Coding guidelines for Prolog». arXiv:0911.2899 [cs.PL]. 
  46. ↑ Roy, P.; Demoen, B.; Willems, Y. D. (1987), «Improving the execution speed of compiled Prolog with modes, clause selection, and determinism», Tapsoft '87, Lecture Notes in Computer Science, 250, pp. 111, doi:10.1007/BFb0014976, ISBN 3-540-17611-X 
  47. ↑ Jaffar, J. (1994), «Constraint logic programming: a survey», The Journal of Logic Programming 19-20: 503–581, doi:10.1016/0743-1066(94)90033-7 
  48. ↑ Colmerauer, Alain (1987), «Opening the Prolog III Universe», Byte August 
  49. ↑ Wallace, M. (20022002), «Constraint Logic Programming», Computational Logic: Logic Programming and Beyond, Lecture Notes in Computer Science, 2407, pp. 512, doi:10.1007/3-540-45628-7_19, ISBN 3540456287 
  50. ↑ «XPCE graphics library». 
  51. ↑ «prolog-mpi». Apps.lumii.lv. Процитовано 2010-09-16. 
  52. ↑ Ehud Shapiro. The family of concurrent logic programming languages ACM Computing Surveys (англ.). September 1989.
  53. ↑ Wielemaker, J.; Huang, Z.; Van Der Meij, L. (2008), «SWI-Prolog and the web», Theory and Practice of Logic Programming 8 (03), doi:10.1017/S1471068407003237 
  54. ↑ Jan Wielemaker and Michiel Hildebrand and Jacco van Ossenbruggen (2007), S.Heymans, A. Polleres, E. Ruckhaus, D. Pearse, and G. Gupta, ред., «Using {Prolog} as the fundament for applications on the semantic web», Proceedings of the 2nd Workshop on Applicatiions of Logic Programming and to the web, Semantic Web and Semantic Web Services, CEUR Workshop Proceedings (Porto, Portugal: CEUR-WS.org) 287: 84–98, http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-287/paper_1.pdf 
  55. ↑ Processing OWL2 Ontologies using Thea: An Application of Logic Programming. Vangelis Vassiliadis, Jan Wielemaker and Chris Mungall. Proceedings of the 5th International Workshop on OWL: Experiences and Directions (OWLED 2009), Chantilly, VA, United States, October 23-24, 2009
  56. ↑ Loke, S. W.; Davison, A. (2001), «Secure Prolog-based mobile code», Theory and Practice of Logic Programming 1, doi:10.1017/S1471068401001211 

Література [ред.]

  • Blackburn P. Learn Prolog Now! / Bos J., Striegnitz K. — Kings College Publications, 2006–265 с. — ISBN 1-904987-17-6. (англ.)
  • Братко И. (англ.) Алгоритмы искусственного интеллекта на языке PROLOG. — М, СПб, К: Вильямс, 2004–640 с. — ISBN 5-8459-0664-4. (рос.)
  • Clocksin W. F. Programming in Prolog: Using the ISO Standard / Mellish C. S. — Вид. 5 — Springer, 2003–299 с. — ISBN 978-3-540-00678-7. (Це видання оновлено для Прологу ISO. Попередні видання описували Единбурзьку Пролог.) (англ.)
  • Clocksin W. F. Clause and Effect. Prolog Programming for the Working Programmer. — Springer, 2003–152 с. — ISBN 978-3-540-62971-9. (англ.)
  • Colmerauer A. The birth of Prolog / Roussel P. // The second ACM SIGPLAN conference on History of programming languages. — 1992 — с. 37-52. (англ.)
  • Covington M. A. Prolog Programming in Depth / Nute D., Vellino A. — 1996–516 с. — ISBN 0-13-138645-X. (англ.)
  • Covington M. A. Natural Language Processing for Prolog Programmers. — 1994–348 с. — ISBN 0-13-62921. (англ.)
  • Smith R. POPLOG's two-level virtual machine support for interactive languages / Gibson J., Sloman A. (англ.) // Research Directions in Cognitive Science Volume 5: Artificial Intelligence. — Eds D. Sleeman and N. Bernsen, Lawrence Erlbaum Associates — 1992 — с. 203–231. (англ.)
  • Стерлинг Л. (англ.) Искусство программирования на языке Пролог / Шапиро Э. (англ.) — М: Мир, 1990–333 с. — ISBN 5-03-000406-8. (рос.)
  • Kowalski R. The Early Years of Logic Programming // CACM. — січень 1988. (англ.)
  • ISO/IEC 13211: Information technology — Programming languages — Prolog. — Geneva: International Organization for Standardization. (англ.)
  • O'Keefe R. (англ.) The Craft of Prolog. — 387 с. — ISBN 0-262-15039-5. (англ.)
  • Warren D. H. D. Prolog — the language and its implementation compared with Lisp / Pereira L. M., Pereira F. // ACM SIGART Bulletin archive, Issue 64. Proceedings of the 1977 symposium on Artificial intelligence and programming languages. — с. 109–115. (англ.)
  • Трушевський В. М. Технології та мови програмування для штучного інтелекту. Частина 1: Основи програмування мовою Prolog. — Львів: 2006–120 с.

Посилання [ред.]

Вікіпідручник має книгу на тему

Отримано з http://uk.wikipedia.org/w/index.php?title=Пролог_(мова_програмування)&oldid=12174682