Лекция 16. Управление вычислениями логических программ. Оператор отсечения (1161908), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Уоррен предложил более эффективную схему реализацииинтерпретаторов логических программ (Warren AbstractMachine), в которой вместо единого стека используетсянесколько стеков, перераспределяющих данные вычислениянаиболее оптимальным способом. Эта схема положена в основувсех современных компиляторов логических программ.А как программист может управлять вычислением логическойпрограммы?Есть два основных способа управления:IВыбирать правильный порядок расположения атомов втелах процедур (по принципу: вначале решать простыезадачи, а потом сложные).IВыбирать правильный порядок расположенияпрограммных утверждений (по принципу: вначалепредлагать простые способы решения, а потом сложные).УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПримерРассмотрим две программы поиска маршрута вориентированном графе...

...P1 : Path((X Z nil) U, X , Y ) ← Path(U, Z , Y ), Arc(X Z nil);Path(nil, X , X ) ←;P2 : Path(nil, X , X ) ←;Path((X Z nil) U, X , Y ) ← Arc(X Z nil), Path(U, Z , Y );.. ...За счет правильного упорядочения атомов и программныхутверждений программа P2 проводит вычисление маршрутаболее эффективно чем программа P1 . На самом деле, обепрограммы несовершенны, поскольку обе могут зациклитьсядаже в случае простых графов.

(Привести пример. )УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИНо иногда и этих средств управления вычислением программнедостаточно для эффективного решения задачи.Предположим, что нам нужно написать программу, котораяпроверяет, верно ли, что заданная буква содержится взаданном слове (например, буква a в слове abaa).Можно предложить вот такую программу:....Elem(X , X .Y ) ←;Elem(X , Z .Y ) ← Elem(X , Y );G : ?Elem(a, a b a a nil)P:Тогда вычисления будут развиваться так.УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ..P : Elem(X , X Y ) ←;Elem(X , Z Y ) ← Elem(X , Y );....?Elem(a,a b a a nil)tУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ..P : Elem(X , X Y ) ←;Elem(X , Z Y ) ← Elem(X , Y );t....?Elem(a,a b a a nil)tУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ..P : Elem(X , X Y ) ←;Elem(X , Z Y ) ← Elem(X , Y );tОтвет: YES....?Elem(a,a b a a nil)tУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); tУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); t...?t?Elem(a, b a a nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); t...?t?Elem(a, b a a nil)..?t?Elem(a, a a nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); t...?t?Elem(a, b a a nil)..?t?Elem(a, a a nil)tУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); t...?t?Elem(a, b a a nil)..?t?Elem(a, a a nil)tОтвет: YESУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t..?t?Elem(a, a a nil)tУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t..?t?Elem(a, a a nil)t.?t?Elem(a, a nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t..?t?Elem(a, a a nil)tt.?t?Elem(a, a nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t..?t?Elem(a, a a nil)ttОтвет: YES.?t?Elem(a, a nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t..?t?Elem(a, a a nil).?t?Elem(a, a nil)ttУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t..?t?Elem(a, a a nil).?t?Elem(a, a nil)tt?t?Elem(a, nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t..?t?Elem(a, a a nil).?t?Elem(a, a nil)t6t?t?Elem(a, nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t..?t?Elem(a, a a nil)6.?t?Elem(a, a nil)t6t?t?Elem(a, nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); ...?t?Elem(a, b a a nil)t6..?t?Elem(a, a a nil)6.?t?Elem(a, a nil)t6t?t?Elem(a, nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ......P : Elem(X , X Y ) ←;?Elem(a,a b a a nil)tElem(X , Z Y ) ← Elem(X , Y ); 6...?t?Elem(a, b a a nil)t6..?t?Elem(a, a a nil)6.?t?Elem(a, a nil)t6t?t?Elem(a, nil)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ..P : Elem(X , X Y ) ←;Elem(X , Z Y ) ← Elem(X , Y );tНо зачем нам обходить все дерево,если для ответа YES достаточнопройти по одной ветви?....?Elem(a,a b a a nil)tУПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИ..P : Elem(X , X Y ) ←;Elem(X , Z Y ) ← Elem(X , Y );t....?Elem(a,a b a a nil)t@@?t?Elem(a, b a a nil).....Хотелось бы иметь способобрезать в дереве вычисленийненужные ветви.?t?Elem(a, a a nil)t.?t?Elem(a, a nil)t?t?Elem(a, nil)ОПЕРАТОР ОТСЕЧЕНИЯДля этого в языках логического программирования вводитсяоператор отсечения (cut ).Этот оператор предсталяет собой 0-местный предикат !,оказывающий специальный побочный эффект.С точки зрения декларативной семантики, предикат ! имеетпостоянное значение true.

Для его описания не требуетсяникаких программных утверждений (! — встроенныйпредикат). Поэтому оператор отсечения может использоватьсяв запросах и в телах программных утверждений, не оказываяпри этом никакого влияния на их логический смысл.Однако операционная семантика оператора ! определяется внерамок SLD-резолютивного вывода. Оператор отсеченияпредназначен для выделения тех ветвей в деревеSLD-резолютивных вычислений, которые не должныпроходиться по ходу вычисления запроса.ОПЕРАТОР ОТСЕЧЕНИЯОперационная семантика оператора отсечения ! задаетсяследующими правилами:I Если запрос G и программное утверждениеD : A0 ← A1 , . .

. , !, . . . , An порождают SLD-резольвентуG 0 , то в стеке вычислений программы запрос G получаетспециальную служебную пометку (∗, индивидуальную длякаждого вхождения оператора !;I Если в запросе G оператор ! активен, т. е.G =?!, C1 , . . . , Ck , то в стеке вычислений программызапрос G получает специальную служебную пометку ∗),индивидуальную для каждого вхождения оператора !, ипри этом порождается новый запрос G 0 =?C1 , . . . , Ck ;I Если по ходу вычисления при откате достигается элементстека вычислений программы, помеченный ∗), то из стекаудаляются все элементы, расположенные междуэлементами, помеченными (∗ и ∗) (включая и сами этиэлементы).УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:(1)(2)(3)(4)(5)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсечения?P(U, V ), R(U)η = ε; count = 1Запрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Унификация(1)(2)(3)(4)(5)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:SLD-резолюцияПоявление оператора!(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 1(*УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 1(*УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 2(*УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Унификация(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:SLD-резолюция(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3?!, Q(V ), R(b)η = {U/b};(*УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Активизация оператора!(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 1*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 1*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 2*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 3*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Унификация(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:SLD-резолюция(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 1*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 1*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 2*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Унификация(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 3*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:SLD-резолюция(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 3η = {U/b, V /c};*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Успех: η = {U/b, V /c}(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 3η = {U/b, V /c};*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Откат(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 3*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 4*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 3(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4?R(b)η = {U/b, V /c}; count = 5*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Откат(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 4*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Унификация(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:SLD-резолюция(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 1*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 1*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 2*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Унификация(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 3*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:SLD-резолюция(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 3η = {U/b, V /b};*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Успех: η = {U/b, V /b}(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 3η = {U/b, V /b};*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Откат(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 3*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 4*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Нет унификатора(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5?R(b)η = {U/b, V /b}; count = 5*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Откат(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};?Q(V ), R(b)η = {U/b}; count = 5*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Откат(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*?!, Q(V ), R(b)η = {U/b};*)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Срабатывание оператора!(1)(2)(3)(4)(5)?P(U, V ), R(U)η = ε; count = 1?R(U), !, Q(V ), R(U)η = ε; count = 4(*УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсечения?P(U, V ), R(U)η = ε; count = 1Запрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Срабатывание оператора!(1)(2)(3)(4)(5)(*УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Срабатывание оператора!(1)(2)(3)(4)(5)УПРАВЛЕНИЕ ВЫЧИСЛЕНИЯМИПример вычисления логических программ соператором отсеченияЗапрос: ?P(U, V ), R(U)Программа P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;Протокол:Конец вычислений(1)(2)(3)(4)(5)Дерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;?P(U,V ), R(U)t(1)(2)(3)(4)(5)Дерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)Дерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)!?t? , Q(V ), R(b)Дерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??t?Q(V ), R(b)Дерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??t?Q(V ), R(b)?R(b) tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??t?Q(V ), R(b)?R(b) t?tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??t?Q(V ), R(b)?R(b) t6?tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??t?Q(V ), R(b)?R(b) t6?tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??R(b) t6?t?t?Q(V ), R(b)@@@R t?R(b)@Дерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??R(b) t?t?Q(V ), R(b)@@@R t?R(b)@6?t?tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??R(b) t6?t?t?Q(V ), R(b)@@@R t?R(b)@6?tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗??R(b) t6?t?t?Q(V ), R(b)@I@@@@@@R t?R(b)@6?tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←;V ), R(U)t∗ ?P(U,(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗?6?R(b) t6?t?t?Q(V ), R(b)@I@@@@@@R t?R(b)@6?tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←; ?P(U, V ), R(U)t∗(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗?6Сработал оператор отсечения.Построение деревавычислений завершено.

Характеристики

Список файлов лекций