Участник:ESSch/Prolog

Пролог

Для Сравнение языков программирования

Prolog

• Пар.:
  • лог +

Тип.: Комп./Инт.: У.п.данных: У.п.вычислений: Типы: Логическое программирование в ограничениях, CLP (Constraint Logic Programming): Стандарты: ISO [1]

Раелизация

Стандартизация

ISO стандарт Пролога — ISO/IEC 13211-1 принятый в 1995 году, чья цель — нормализация многих, уже осуществлённых на практике, реализаций основного элемента Пролога.

Примеры программ на Прологе

Hello world

Транслятор пролога выводит сообщение «Hello world» на запрос вывести на экран — write() — строку 'Hello world' и перейти на следующую строку — nl. <source lang="prolog"> ?- write('Hello world!'), nl. Hello world! true.

?- </source>

Опртимизация

Любое вычисление может быть выраженно декларацией как последовательность конкретных переходов. Как пример, оптимизация компилятора с помощью трёх переходов может быть осуществленно как отношение начальной программы и этими оптимизированными формами: <source lang="prolog"> program_optimized(Prog0, Prog) :-

   optimization_pass_1(Prog0, Prog1),
   optimization_pass_2(Prog1, Prog2),
   optimization_pass_3(Prog2, Prog).

</source>

или эквиваелентоно в DCG нотации:

<source lang="prolog"> program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3. </source>

Быстрая сортировка

Реализация алгоритма быстрой сортировки: <source lang="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).

</source>

Динамическое программирование

Следующая программа на Прологе, используя динамическое программирование, находит самую длянную наиболее общую подпоследовательность из двух списков в течение полиномиального(англ.) времени. <source lang="prolog">

- dynamic(stored/1).

memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).

lcs([], _, []) :- !. lcs(_, [], []) :- !. lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)). lcs([X|Xs], [Y|Ys], Ls) :-

   memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
   length(Ls1, L1), length(Ls2, L2),
   (   L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

</source>

Пример запроса: <source lang="prolog"> ?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls). Ls = [m, j, a, u] </source>

ООП

<source lang="prolog"> % фигура( Конструктор, Методы) фигура( %объект прямоугольник:

 прямоугольник( Высота, Ширина),                        %"конструктор"   
 [(площадь( Площадь) :- Площадь is Высота * Ширина),                 %методы        
  (вывести :- write( 'Площадь прямоугольника равна '),   
              write( Площадь)
  )]

). фигура( %объект квадрат

 квадрат( Сторона),                                     %"конструктор"
 [(вывести :- write( 'Площадь квадрата равна '),        %методы
              write( Сторона)
  )]

). фигура(

 круг( Диаметр),
 [(вывести :- write( 'Площадь круга равна '),
              write( Площадь)
  )]

). фигура(

 квадрат_вырезанный_круг( Сторона),
 [(вывести :- write( 'Площадь фигуры: квадрата без вписанного крука равна '),
              write( Площадь)
  )]

). % наследования методов от объекта родителя к объекту наследнику, то есть соответсвенно Площадь() от Прямоугольник к Квадрат наследование( квадрат( Сторона), прямоугольник( Сторона, Сторона)). наследование( круг( Диаметр), (Сторона is Диаметр * Sqrt(0.25 * pi)), квадрат(Сторона)). % S(кр)=pi*R*R=0.25pi*D*D=L*L -> L=D*Sqrt(0.25pi) наследование( круг( Радиус), (Высота is Диаметр * Sqrt(0.25 * pi)), прямоугольник( Высота, Высота)). вызов_методов(

 квадрат_вырезанный_круг(Сторона), 
 send( квадрат( Сторона), площадь( Площадь_квадрата)), 
 send( круг( Сторона), площадь( Площадь_круга), 
 (площадь( Площадь) :- Площадь is Площадь_квадрата - Площаль_круга) ).

</source> На данном примере выдны применение трёх парадигм ООП:

• Наследование:
  • Простое наследование видно в передачи метода площадь( Порщадь) от объекта фигура( прямоугольник(_), _) к объекту фигура( квадрат(_), _):
    • Запрос: ?- send( квадрат(5), площадь( Площадь)).
    • Конструктор квадрат(5) найден в объекте фигура(). Поиск метода площадь( Площадь) в этоме объекте завершилось неудачей.
    • Конструктор квадрат(5) найден в методе наследование(). Поиск конструктора прямоугольник(5, 5).
    • Конструктор прямоугольник(5, 5) найден в методе фигура(). Поиск метода площадь( Площадь) в прямоугольник(5) завершилось инициализацией площадь(25).
    • Результат: Площадь = 25
  • Множественное наследование объектом фигура( круг(_), _) осуществляется аналогично простому, за исключением препроцессора, в котором осуществляется выбор основной ветви наследования.
• Инкапсуляцию видна в сокрытии реализации методов (например, Метод1) в фигура( Конструктор, [ Метод1|_]), хотя результат его работы доступен и через наследование и через прямое обращение (например, в вызов_методов() ).
• Полиморфизм виден в перегрузке объекта фигура( Объект, Методы).

Расширения(англ.)

Другие

• F-logic(англ.) расширения языка Пролог с помощью фреймов/объектов представлений знаний, язык описания онтологий. Язык обладает свойсвами, среди прочих, равные и сложне объекты, наследование, полиморфизм, инкапсуляция, запрос методов. Язык устанавливает то же отношение с объектно-ориентированным программированием, что и язык реляционных быз данных — с классическим исчислением предикатов. F-logic основывается на языках:
  • FLORA-2 — расширение F-logic с помощью HiLog и добалением логики.
  • FLORID — язык, основанный на C++.
  • Web Services Modeling Language (WSML).
  • Semantic Web Services Language (SWSL).
  • Ссыки: Михаил Кифер, Георг Лясен, Джеймс Ву Логические основы объектно-ориентированных и основанных на ферймах языков. (англ.) = Logical Foundations of Object-Oriented and Frame-Based Languages. — 1995. — С. 104.
• OW Prolog(англ.) расширение языка Пролог, создан для того, чтобы предоставить графику и интерфейс, отсутсвующий в Прологе. Реализован в стандарте Prolog(англ.). OW Пролог создан Or Weis в 2003 году, он предоставляет графический интерфейс для Пролога, а также динамические переменные; и полная поддержка Английского, Еврейского и других языков.

KL

Kernel Language 1

Класс языка:	Concurrent Logic Programming
Появился в:	1987 г.
Повлиял на:	Strand(англ.)

en:KL0

Kernel Language 0 (KL0) — последовательный язык логического программирования, основанный на языке Пролог, использовавшийся в проеткте компьютеров пятого поколения.

en:KL1

Не следует путать с KL-ONE — система представления знаний.

Kernel Language 1 (KL1) — эксперементальный И-распараллелиной версия языка KL0, разработанная для проекта компьютеров пятого поколения. KL1 — вариант распараллелиной версии языка языка Пролог.

Примеры

Логическое отрицание

<source lang="prolog">

- module main.

main :- not(1, X), io:outstream([print(X), nl]). not(In, Out):- In = 0 | Out = 1. not(In, Out):- In = 1 | Out = 0. </source>

Быстрая сортировка

Быстрая сортировка <source lang="prolog">

- module quicksort.

qsort([Pivot|Xs], Ys0, Ys2) :- part(Xs,Pivot, Small, Large),

                              qsort(Small, Ys0, [Pivot|Ys1]),
                              qsort(Large, Ys1, Ys2).

qsort([], Ys0, Ys1) :- Ys0 = Ys1.

part([X|Xs],Pivot,Small,Large) :- Pivot< X | Large=[X|L1], part(Xs,Pivot,Small,L1). part([X|Xs],Pivot,Small,Large) :- Pivot>=X | Small=[X|S1], part(Xs,Pivot,S1,Large). part([], _, Small,Large) :- Small=[], Large=[]. </source>

Pragma

Распределение цели Pragma 　　　　　          Goal@node(Node)
Указание преоритета цели Pragma            Goal@priority(Priority)
Указание преоритета цели в раздели Pragma  alternatively.

<source lang="prolog">

- module cyclic.

- public distribute/1.

distribute(N):- true |

               current_node(_,PEs),  %Возращает номер узла
               fork(N,PEs,0).          %Запуск узла n процесса

fork(0,PEs,PE):- true | true. otherwise. fork(N,PEs,PE):- PeNo:=PE mod PEs |

               spawn@node(PeNo),     %Начало узла для поддержания процесса
               NextPE:=PE+1,
               N1:=N-1,
               fork(N1,PEs,NextPE).

</source>

execute(Goal, ControlStream, ResultStream, Tag)

См. также

• Дизъюнкт Хорна

Ссылки

• ассациация: последние изменения 1999 году.(англ.)

en:KL-ONE

Не следует путать с KL1 — язык программирования.

KL-ONE — хорошо известное представление знаний

en:Strand (programming language)

Kernel Language 1

Класс языка:	Concurrent Logic Programming

Strand — язык распараллеленного программирования высокого уровня, использующий синтаксис, схдный с языком Пролог.

Искуственный интелект

Примеры

<source lang="Prolog"> merge([A|Xs],Ys,Zs0) :- true | Zs0:=[A|Zs], merge(Xs,Ys,Zs). merge(Xs,[A|Ys],Zs0) :- true | Zs0:=[A|Zs], merge(Xs,Ys,Zs). merge([],Ys,Zs) :- true | Zs:=Ys. merge(Xs,[],Zs) :- true | Zs:=Xs. </source>

DC-грамматика

Грамматика, построенная на определенных предложениях или сокр. DC-грамматика (англ. Definite clause grammar или DCG) — способ выражения грамматических взаимосвязей, а также естественных или формальных языков, в логическом программировании используется в таких языках, как Пролог. DC-грамматики обычно ассациируются с Прологом, но такие подобные ему языки, как Меркурий, тоже ключают их. Они называются грамматикой определённого предложения, поскольку, они представляют грамматику определённую как представление определённые предикаты в логике первого порядка.

Термин DC-грамматика отмечает специфику типа, выраженного в Прологе и в других подобных ему языках; но не все способы определения грамматик, используемые в определённых предложениях, считаются DC-грамматиками. Тем не менее, все возможности или свойства DC-грамматик бедут теми же для любого грамматического представление, которые представленны с помощью определённых предложений, по сущетсву, это те же способы, что в Прологе.

Определённые предложения DC-грамматик могут считаться набором аксиомами, где достоверность такова, что предложений могут считаться теоремами следующими от этих актсиом. Эти приемущества получают для того, чтобы опознавательный и синтаксический анализ выражений в языке был общим материалом проверки утверждений, таким как утверждения в языке логического программирования.

История

Роберт Кавальски

Роберт Антони Ковальски (англ. Robert Anthony Kowalski) -- американский логик Был студентом Чикагского университета, Бриджпортского университета (бакалавр математики, 1963 год), Стэнфордский университет(магистр по математики, 1966 год), Варшавский университет и Эдинбургский университет(докторская степень по компьютерным наукам, 1970 год) Аспирант в Единбургском университете (1970-1975) и заместитель ? руководителя по Компьютерной логике в Имперском колледже ? 1982. С 1999 года -- заслуженный преподаватель по компьютерной логике депортамента по компьютерным исчислениям в Имперском колледже. ?Имперском колледже. bg:Робърт Ковалски cs:Robert Kowalski en:Robert Kowalski ru:Роберт Ковальки

Пример

sentence --> noun_phrase, verb_phrase.
noun_phrase --> det, noun.
verb_phrase --> verb, noun_phrase.
det --> [the].
det --> [a].
noun --> [cat].
noun --> [bat].
verb --> [eats].

Граматический анализ с помощью DC-граматики

Файл:The bat eats a cat tree.png

Пример дерева грамматического перебора этой грамматики.

См. также

• Контекстно-свободная грамматика
• Контекстная грамматика
• Пролог
• Иерархия Хомского
• en:Phrase structure grammar
• Обработка естественного языка

Дополнительные источники

• Definite Clause Grammars