Семантика языка Prolog - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Семантика языка Prolog. Доклад-сообщение содержит 52 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Язык Prolog Семантика языка Prolog

Слайд 2

Описание слайда:

Декларативная семантика программ на языке Пролог. Язык Пролог является не алгоритмическим, а декларативным языком программирования. Прологпрограмма лишь декларирует утверждения, определяющие свойства объектов и отношения между ними, поэтому семантика Прологпрограмм является декларативной.

Слайд 3

Описание слайда:

Декларативная семантика программ на языке Пролог. Декларативная семантика программы определяет, что истинно и при каких значениях переменных. С точки зрения декларативной семантики, утверждения программы являются формулами исчисления предикатов 1-го порядка.

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Процедурная семантика программ на языке Пролог. Процедурная семантика  это процедура вычисления списка целей на основе заданной декларативной программы.

Слайд 6

Описание слайда:

Процедурная семантика программ на языке Пролог. Назовем эту процедуру именем «Вычислить».

Слайд 7

Описание слайда:

Процедурная семантика программ на языке Пролог. Процедурная семантика языка Пролог определяет встроенные в Прологсистему механизмы логического вывода. Рассмотрим простейшие механизмы логического вывода.

Слайд 8

Описание слайда:

Правило совпадения Факты в программе не содержат переменных, а вопрос  простой и основной. В этом случае используется правило совпадения: вопрос выводим из программы, если в программе имеется совпадающий с вопросом факт.

Слайд 9

Описание слайда:

Правило обобщения факта Факты в программе не содержат переменные, а вопрос  простой и неосновной. В этом случае для вывода можно применить правило обобщения факта: вопрос Q выводим из программы, если найдется подстановка, что вопрос Q выводим из программы. Процедура поиска ответа на простой, неосновной вопрос из программы, состоящей из фактов без переменных, сводится к поиску факта, являющегося примером вопроса.

Слайд 10

Описание слайда:

Правило обобщения факта (Конкретизация переменных) Побочным эффектом доказательства будет конкретизация переменных, входящих в вопрос. Конкретизацией называется присвоение переменной значения в процессе выполнения программы.

Слайд 11

Описание слайда:

Вычисление конъюнктивного запроса Процедура поиска ответа на конъюнктивный, неосновной вопрос из программы, состоящей из фактов без переменных, сводится к поиску факта, являющегося примером цели G1, а затем после подстановки значений общих переменных в цель G2 производится поиск факта, являющегося примером цели G2 данного вопроса. Если такой факт обнаруживается, то выполняется конкретизация переменных цели G2, которые не являются общими с целью G1, и вычисление конъюнктивного вопроса завершается успешно.

Слайд 12

Описание слайда:

SWI Prolog Вычислительная модель языка Prolog

Слайд 13

Описание слайда:

Алгоритм унификации – основа вычислительной модели языка Пролог Унификация (или сопоставление) — основной шаг процесса вычисления запроса, именно в результате унификации происходит конкретизация переменных и обеспечивается продвижение к успешному завершению логического вывода запроса. Операндами операции унификации являются логические термы.

Слайд 14

Описание слайда:

Правила унификации термов Правило 1. Если термы Т1 и Т2 — константы, то они унифицируются только в том случае, когда они одинаковы. Целые и вещественные числа сопоставимы только с равными им числам. Атомы сопоставимы только с идентичными атомами. Строки сопоставимы с одинаковыми строками.

Слайд 15

Описание слайда:

Правила унификации термов Правило 2. Если терм Т1—константа или составной терм, а Т2 — неконкретизированная переменная, не содержащаяся в Т1, то Т1 и Т2 унифицируются, причем в результате переменная Т2 конкретизируется значением Т1.

Слайд 16

Описание слайда:

Правила унификации термов Правило 3. Если термы Т1 и Т2 — неконкретизированные переменные, то их унификация успешна всегда, причем в результате унификации эти переменные становятся сцепленными, то есть при конкретизации одной из них, другая одновременно конкретизируется тем же значением.

Слайд 17

Описание слайда:

Правила унификации термов Правило 4. Если Т1 и Т2 составные термы, то Т1 и Т2 унифицируются успешно, когда они имеют одинаковые главные функторы и арности, и каждая пара соответствующих компонент составных термов успешно унифицируется.

Слайд 18

$Явная операция унификации При выполнении логического вывода скрыто от пользователя выполняется большое число операций унификации, обусловленных встроенным в Прологсистему алгоритмом логического вывода. Однако, у программиста имеется возможность задать в качестве одной из целей явное выполнение унификации двух термов с помощью операции сопоставления ‘=’. Знак ‘\=’ является знаком отрицания сопоставления.$

Описание слайда:

Явная операция унификации При выполнении логического вывода скрыто от пользователя выполняется большое число операций унификации, обусловленных встроенным в Прологсистему алгоритмом логического вывода. Однако, у программиста имеется возможность задать в качестве одной из целей явное выполнение унификации двух термов с помощью операции сопоставления ‘=’. Знак ‘\=’ является знаком отрицания сопоставления.

Слайд 19

Описание слайда:

Примеры унификации термов Пример 1. ?2+1=1+2. no Составные термы 2+1 и 1+2 не сопоставимы, и операция сопоставления этих термов неуспешна.

Слайд 20

$Примеры унификации термов Пример 2. ?2+1\=1+2. yes Операция отрицания сопоставления термов 2+1 и 1+2 успешна.$

Описание слайда:

Примеры унификации термов Пример 2. ?2+1\=1+2. yes Операция отрицания сопоставления термов 2+1 и 1+2 успешна.

Слайд 21

Описание слайда:

Примеры унификации термов Пример 2. ?2+X=2+1. X=1 yes Операция сопоставления термов 2+X и 2+1 успешна.

Слайд 22

Описание слайда:

Общая схема согласования целевых утверждений. Самым общим случаем Прологпрограммы является программа, включающая как факты, так и правила. Рассмотрим процесс вычисления запроса на основе такой логической программы.

Слайд 23

Описание слайда:

Общая схема согласования целевых утверждений. Процесс вычисления начинается с некоторого исходного вопроса Q, который в общем случае может быть конъюнктивным, и завершается получением одного из двух результатов: успешного согласования целей вопроса; неуспеха (или неудачи).

Слайд 24

Описание слайда:

Общая схема согласования целевых утверждений (продолжение) Допустим, что логическая программа P состоит из фактов и правил, а вопрос Q  конъюнктивный и содержит цели G1,G2,…Gn. Интерпретатор языка Пролог будет вычислять ответ на вопрос согласно следующим принципам, на которых он реализован.

Слайд 25

Описание слайда:

Общая схема согласования целевых утверждений (продолжение) 1) Цели запроса обрабатываются слева направо, G1 будет согласовываться первой, а Gn последней.

Слайд 26

Описание слайда:

Общая схема согласования целевых утверждений (продолжение) 2) Предложения программы просматриваются интерпретатором сверху вниз.

Слайд 27

Описание слайда:

Общая схема согласования целевых утверждений (продолжение) 3) Если цель Gi сопоставима с заголовком правила Hj, то она должна быть сопоставима с предикатами в правой части правила. Интерпретатор заменяет цель Gi на правую часть правила Hj. Это действие называется редукцией.

Слайд 28

Описание слайда:

Общая схема согласования целевых утверждений (продолжение) Редукцией цели Gi с помощью программы P называется замена цели Gi на тело правила Cj, заголовок которого Hj унифицируется с целью Gi. Вычисление вопроса выполняется в виде последовательности редукций, цепочки преобразований исходного вопроса.

Слайд 29

Описание слайда:

Общая схема согласования целевых утверждений (продолжение) На каждом этапе вычисления существует некоторая конъюнкция целей (или одна цель), называемая резольвентой. Цели, которые добавляются в запрос в результате редукции, называются производными целями от цели Gi и правила Cj. Если цель Gi сопоставима с заголовком правила Hj, то список целей в запросе увеличивается.

Слайд 30

Описание слайда:

Общая схема согласования целевых утверждений (продолжение) 4) Если цель Gi сопоставима с фактом, то конкретизируются переменные этой цели, и общие переменные цели Gi и других целей, входящих в вопрос, затем осуществляется переход к сопоставлению следующей цели Gi+1 , и, таким образом, список целей, подлежащих согласованию уменьшается.

Слайд 31

Описание слайда:

Общая схема согласования целевых утверждений (продолжение) 5) Когда мы таким образом достигнем последней цели в запросе, и она успешно будет согласована с каким-либо фактом программы, то текущая резольвента окажется пустой, и вычисление запроса будет успешным.

Слайд 32

Описание слайда:

Пример вычисления запроса на основе программы, включающей и факты, и правила. Пусть программа содержит утверждения, приведенные ниже: big(‘медведь’). %предложение 1 big(‘слон’). %предложение 2 little(‘кот’). %предложение 3 little(‘мышь’). %предложение 4 black(‘кот’). %предложение 5 grey(‘слон’). %предложение 6 grey(‘мышь’). %предложение 7 brown(‘медведь’). %предложение 8 dark(Z):black(Z). %предложение 9 dark(Z):brown(Z). %предложение 10

Слайд 33

Описание слайда:

Шаг 1 вычисления запроса Для вычисления запроса “?  dark(X),big(X). “ интерпретатор выполняется следующие действия: Текущая резольвента Q1 есть исходный запрос  dark(X),big(X). Шаг 1. Текущая резольвента Q2 является конъюнкцией целей dark(X),big(X). Выбираем первую цель G21dark(X) и, просматривая программу с первого предложения, находим предложение 9, сопоставимое с целью G21, является правилом dark(Z):black(Z). переименовываем переменную Z на Х и вместо цели G21 подставляем правую часть правила 9. Получаем текущую резольвенту Q2black(X),big(X)

Слайд 34

Описание слайда:

Шаг 2 вычисления запроса Шаг 2. Текущая резольвента Q2 является конъюнкцией целей black(X),big(X). Выбираем первую цель G21black(X) и, просматривая программу с первого предложения, находим предложение 5, сопоставимое с целью G21, black(‘кот’). при подстановке {X=’кот’}. Предложение 5 является фактом, поэтому список целей в резольвенте сократится, так как цель G21 удаляется , а в цель G22 при подстановке {X=’кот’} примет вид big(‘кот’). Получаем текущую резольвенту Q3: big(‘кот’).

Слайд 35

Описание слайда:

Шаг 3 вычисления запроса Шаг 3. Текущая резольвента Q3 включает одну цель G31 big(‘кот’). Просматривая программу с первого предложения, не находим ни одного предложения, сопоставимого с целью G31, поэтому выполняется возврат на шаг 2.

Слайд 36

Описание слайда:

Шаг 4 вычисления запроса Шаг 4. Текущая резольвента Q4=Q2 является конъюнкцией целей black(X),big(X). Выбираем первую цель G41black(X) и, просматривая программу с предложения 6 до конца программы, и не находим ни одного предложения, сопоставимого с целью G41, поэтому выполняется возврат на шаг 1.

Слайд 37

Описание слайда:

Шаг 5 вычисления запроса Шаг 5. Текущая резольвента Q5=Q1 является конъюнкцией целей dark(X),big(X). Выбираем первую цель G51dark(X) и, просматривая программу с предложения 10, находим предложение 10, сопоставимое с целью G21, является правилом dark(Z):brown(Z). переименовываем переменную Z на Х и вместо цели G21 подставляем правую часть правила 9. Получаем текущую резольвенту Q5  brown (X),big(X).

Слайд 38

Описание слайда:

Шаг 6 вычисления запроса Шаг 6. Текущая резольвента Q5 является конъюнкцией целей brown(X),big(X). Выбираем первую цель G51 brown(X) и, просматривая программу с первого предложения, находим предложение 8, сопоставимое с целью G51, brown(‘медведь’). при подстановке {X=’медведь’}. Предложение 8 является фактом, поэтому список целей в резольвенте сократится, так как цель G51 удаляется , а в цель G52 при подстановке {X=’медведь’} примет вид big(‘медведь’). Получаем текущую резольвенту Q6: big(‘медведь’).

Слайд 39

Описание слайда:

Шаг 7 вычисления запроса Шаг 7. Текущая резольвента Q6 включает одну цель G61 big(‘медведь’). Просматривая программу с первого предложения, находим предложение 1, сопоставимое с целью G61, которое является фактом, поэтому цель G61 удаляется из текущей резольвенты, и она становится пустой, Q7=. Текущая резольвента Q7 есть пустой дизъюнкт, это указывает на успешное завершение вычисления запроса Q1. Интерпретатор выдает конкретизацию переменной {X=’медведь’} как результат вычисления запроса.

Слайд 40

Описание слайда:

Дерево поиска Процесс вычисления запроса удобно представить в виде дерева поиска. Дерево поиска ответа на любой запрос строится следующим образом. Корнем дерева является исходный вопрос Q. Вершины дерева соответствуют целям (резольвентам), которые в общем случае являются конъюнктивными. В каждой выделяется одна цель.

Слайд 41

Описание слайда:

Дерево поиска Для каждого утверждения программы, заголовок которого унифицируется с выделенной в вершине целью имеется ребро, выходящее из этой вершины. На ребрах дерева записываются подстановки, которые образуются в результате унификации выделенной в вершине цели и утверждения.

Слайд 42

Описание слайда:

Дерево поиска Лист дерева называется успешной вершиной, если существует подстановка, удовлетворяющая последнюю цель в списке целей. Лист дерева называется безуспешной вершиной, если нет в программе утверждений, которые сопоставимы с выделенной в вершине целью.

Слайд 43

Описание слайда:

Дерево поиска

Слайд 44

Описание слайда:

Механизм автоматического возврата (backtracing) Когда выполнение программы достигает тупиковой вершины отмеченной словом "неуспех", автоматически происходит возврат на предыдущий уровень дерева поиска, так как в Прологсистему встроен механизм возврата (backtracing).

Слайд 45

Описание слайда:

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

Слайд 46

Описание слайда:

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

Слайд 47

Описание слайда:

Механизм автоматического возврата (backtracing). Понятие маркера. Для каждой цели в запросе Прологсистема создает свой собственный маркер, который будем обозначать значком “”. Маркеры могут передвигаться только вперед. Однако, когда цель начинает согласовываться сначала, соответствующий маркер устанавливается на первое утверждение, заголовок которого совпадает с именем предиката  цели.

Слайд 48

$Пример поиска решений с возвратом. Пусть программа «Однокурсники» содержит следующие утверждения: student_course(X,Y):student(X,K1), student(Y,K2),X\=Y,K1=K2. student(‘Иванов’,1). student(‘Петров’,4). student(‘Сидоров’,2). student(‘Кузнецов’,4). Пусть требуется согласовать запрос: ? student_course(X,Y).$

Описание слайда:

Пример поиска решений с возвратом. Пусть программа «Однокурсники» содержит следующие утверждения: student_course(X,Y):student(X,K1), student(Y,K2),X\=Y,K1=K2. student(‘Иванов’,1). student(‘Петров’,4). student(‘Сидоров’,2). student(‘Кузнецов’,4). Пусть требуется согласовать запрос: ? student_course(X,Y).

Слайд 49

$Пример поиска решений с возвратом. Пусть требуется согласовать запрос: ? student_course(X,Y). Этот запрос сопоставим с первым утверждением, которое является правилом, поэтому производится редукция цели, и текущая резольвента примет вид: ТР: student(X,K1), student(Y,K2),X\=Y,K1=K2. Создадим маркер 1 для первой цели в резольвенте student(X,K1) и маркер 2 для второй цели в резольвенте student(Y,K2).$

Описание слайда:

Пример поиска решений с возвратом. Пусть требуется согласовать запрос: ? student_course(X,Y). Этот запрос сопоставим с первым утверждением, которое является правилом, поэтому производится редукция цели, и текущая резольвента примет вид: ТР: student(X,K1), student(Y,K2),X\=Y,K1=K2. Создадим маркер 1 для первой цели в резольвенте student(X,K1) и маркер 2 для второй цели в резольвенте student(Y,K2).

Слайд 50

$Поиск первого решения При просмотре фактов student в программе маркеры будут передвигаться следующим образом: (2) student(‘Иванов’,1). 1 2 (no) 2 (no) (3) student(‘Петров’,4). 2 (no) 1 2 (no) (4) student(‘Сидоров’,2). 2 (no) 2 (no) (5) student(‘Кузнецов’,4). 2 (no) 2 (yes) возврат 1-й цели успешный вывод при подстановке {X=‘Петров’; Y=‘Кузнецов’}. Таким образом, ответ на запрос будет выдан в следующем виде: ? student_course(X,Y). X=‘Петров’ Y=‘Кузнецов’ >$

Описание слайда:

Поиск первого решения При просмотре фактов student в программе маркеры будут передвигаться следующим образом: (2) student(‘Иванов’,1). 1 2 (no) 2 (no) (3) student(‘Петров’,4). 2 (no) 1 2 (no) (4) student(‘Сидоров’,2). 2 (no) 2 (no) (5) student(‘Кузнецов’,4). 2 (no) 2 (yes) возврат 1-й цели успешный вывод при подстановке {X=‘Петров’; Y=‘Кузнецов’}. Таким образом, ответ на запрос будет выдан в следующем виде: ? student_course(X,Y). X=‘Петров’ Y=‘Кузнецов’ >