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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

Содержание

Пролог

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

Prolog

  • Пар.:
    • лог +

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

Раелизация

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

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

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

Hello world

Транслятор пролога выводит сообщение «Hello world» на запрос вывести на экран — write() — строку 'Hello world' и перейти на следующую строку — nl.

?- 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 нотации:

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

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

Реализация алгоритма быстрой сортировки:

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).

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

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

:- 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 ).

Пример запроса:

?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls).
Ls = [m, j, a, u]

Граматика

Основная статья: DC-грамматика

Пример граматики

ООП

% фигура( Конструктор, Методы)
фигура(                                                  %объект прямоугольник:
  прямоугольник( Высота, Ширина),                        %"конструктор"   
  [(площадь( Площадь) :- Площадь 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 Площадь_квадрата - Площаль_круга) ).

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

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

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

Другие

KL

Kernel Language 1
Класс языка:

Concurrent Logic Programming

Появился в:

1987 г.

Повлиял на:

Strand(англ.)

en:KL0

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

en:KL1

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

Примеры

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

:- 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.

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

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

:- 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=[].

Pragma

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


:- 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).

execute(Goal, ControlStream, ResultStream, Tag)

См. также

Ссылки

en:KL-ONE

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


en:Datalog

en:Strand (programming language)

Kernel Language 1
Класс языка:

Concurrent Logic Programming

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

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

Примеры

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.

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
Пример дерева грамматического перебора этой грамматики.

Другое использование

См. также

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

pt:Gramática de cláusulas definidas

Личные инструменты

Served in 0.678 secs.