Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Название ПРОЛОГ есть сокращение, означающее ПРОграммирование в терминах ЛОГики. Идея использовать логику в качестве языка программирования возникла впервые в начале 70-х годов. Первыми исследователями, разрабатывавшими эту идею, были Роберт Ковальский из Эдинбурга (теоретические аспекты), Маартен ван Эмден из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ из Марселя (реализация). Сегодняшней своей популярности Пролог во многом обязан эффективной реализации этого языка, полученной в Эдинбурге Дэвидом Уорреном в середине 70-х годов (см. [3]).

3.2. Синтаксис языка ПРОЛОГ

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

Опишем синтаксис языка посредством регуляризованных формул Бэкуса-Наура. Фигурные скобки в формуле означают, что конструкция внутри них может повторяться многократно. Квадратные скобки означают, что конструкция внутри них может отсутствовать.

<программа>::={<предложение>.}

Пролог-программа состоит из предложений. Каждое предложение заканчивается точкой.

<предложение>::=<голова>[:-<тело>]

<тело>::=< предикат>{,<предикат>}

<голова>::=<предикат>

Предложения Пролога состоят из головы и тела, которые разделяются знаком «:-» (вместо «:-» может использоваться «if»). Тело - это список предикатов, разделенных запятыми. Тело может быть пустым. В этом случае знак «:-» опускается.

Предложения бывают трех типов: факты, правила и вопросы.

<факт>::=<предикат>

<правило>::=<голова>:-<тело>

<вопрос>::=?-<тело>

Факты - это предложения, имеющие пустое тело. Вопросы имеют только тело. Правила имеют голову и непустое тело.

<предикат>::=<имя>[(<список_параметров>)]

<список_параметров>::=<параметр>{,<параметр>}

<параметр>::=<число> | <текстовая константа> | <переменная> | <структура>

<текстовая константа>::=”<строка_символов>” | <атом>

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

Параметрами предиката могут быть конкретные имена объектов (текстовые константы), числовые константы, переменные, а также структуры. Текстовые константы бывают двух видов: строка произвольных символов в кавычках и строка, начинающаяся со строчной буквы без кавычек. Такая константа называется атомом. переменными в Прологе являются идентификаторы, начинающиеся с заглавной буквы, например, X, Y.

Пример 3.2.1.Конструкции языка Пролог

Предикаты:

родитель(X, анна)

родитель(иван, анна)

родитель(“Иван”, “Анна”)

родитель(X, Y)

сосед(X, Y)

Факты:

родитель(иван, анна).

сосед(иван, федор).

Вопросы:

?- сосед(иван, федор).

?- родитель(иван, анна).

?- родитель(X, Y).

Правила:

отец(X, Y):- родитель(X, Y), мужчина(X).

дед(X, Y):- отец(X, Z), отец(Z, Y).

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

<структура>::=<функтор>(<список_компонент>)

<список_компонент >::=< компонента>{,< компонента>}

<компонента>::=<параметр>

< функтор >::=<имя>

Функторы различается двумя параметрами: именем и арностью - т.е. числом компонент. Например, point(X, Y, Z) и point(X, Y) - это разные термы.

3.3. Семантика языка ПРОЛОГ

Декларативная семантика. Словесная интерпретация языка Пролог.

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

Пример 3.3.1.Программа «Родственные отношения». Отношение родитель(X, Y) означает, что X является родителем Y. Отношение мужчина(X) означает, что X является мужчиной (унарные отношения называют свойствами). Отношение отец(X, Y) означает, что X является отцом Y. Программа представляет собой набор фактов и правил.

родитель(пам, боб). (Памела является родителем Боба)

родитель(том, боб). (Том является родителем Боба)

родитель(том, лиз). (Том является родителем Лиз)

родитель(боб, энн). (Боб является родителем Энн)

родитель(боб, пат). (Боб является родителем Патриции)

родитель(пам, джим). (Памела является родителем Джима)

мужчина(боб). (Боб является мужчиной)

мужчина(том). (Том является мужчиной)

мужчина(джим). (Джим является мужчиной)

отец(X, Y):- родитель(X, Y),мужчина(X). (Некто является отцом кого-либо, если он его родитель и мужчина)

Вопросы Пролога интерпретируются как вопросительные предложения в естественном языке.

Пример 3.3.2.Вопросы к программе «Родственные отношения».

Является ли Боб родителем Пат?

?- родитель(боб, пат).

yes

Является ли Лиз родителем Пат?

?- родитель(лиз, пат).

no

Является ли Том родителем Бен?

?- родитель(том, бен).

no

Кто является родителем Лиз?

?- родитель(X, лиз).

X = том

Кто дети Боба?

?- родитель( боб, X).

X = энн

X = пат

Кто чей родитель? Найти X и Y такие, что X - родитель Y.

?- родитель(X, Y).

X = пам Y = боб;

X = том Y = боб;

X = том Y = лиз;

Кто является отцом Лиз?

?- отец(X, лиз).

X = том

Процедурная семантика

Пролог-система рассматривает вопросы как цели, к достижению которых нужно стремиться. Ответ на вопрос может оказаться или положительным, если цель достижима или отрицательным в противном случае.

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

Алгоритм 6. Пролог-интерпретатор основных конструкций.

Вход: P– программа - упорядоченное множество фактов и правил, вопрос к пролог-системе в виде списка целевых предикатов G=G₁,…,G_n.

1) берется первое предложение C из программы P. Пусть C имеет вид H:-B₁, B₂,..., B_m

2) пока G₁, и H не сопоставимы и программа P не исчерпана выбирать в качестве C следующее по порядку предложение

3) если программа P исчерпана, то ВЫХОД(неудача)

4) если для некоторого предложения C (H:-B₁, B₂,..., B_m) G₁, и H сопоставимы и d-подстановка, полученная при сопоставлении, то сформировать новый список целей G=d(B₁, B₂,..., B_m, G₂,…,G_n.)

5) если список целей G – пуст, то КОНЕЦ РАБОТЫ(успех).

6) если список целей G – не пуст, то применить описываемый алгоритм рекурсивно к списку целей G

7) в случае выхода алгоритма с неудачей выбирать в качестве C следующее по порядку предложение программы P и перейти к п. 2).

Пример 3.3.3.Исполнение пролог-программы.

Вход: P– программа примера 3.2.2., G=отец(X, боб)

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

1) 1) C=родитель(пам, боб)

2) 2) выбираются в качестве C предложения программы P до C=отец(X₁, Y₁):- родитель(X₁, Y₁),мужчина(X₁), H= отец(X₁, Y₁), B₁=родитель(X₁, Y₁), B₂=мужчина(X₁)

3) 3)

4) 4) d={X=X₁, Y₁=боб}, G=родитель(X₁, боб),мужчина(X₁)

5) 5)

6) 6) применить описываемый алгоритм рекурсивно к списку целей G (уровень 1)

7) 1) C=родитель(пам, боб)

8) 2)

9) 3)

10) 4) d={X₁= пам}, G=мужчина(пам)

11) 5)

12) 6) применить описываемый алгоритм рекурсивно к списку целей G (уровень 2)

13) 1) C=родитель(пам, боб)

14) 2) выбираются в качестве C предложения программы P до конца

8) 3) ВЫХОД(неудача) (возврат на уровень 1 к шагу 7))

15) 7) C=родитель(том, боб) перейти к п 2)

16) 2)

17) 3)

18) 4) d={X₁= том}, G=мужчина(том)

19) 5)

20) 6) применить описываемый алгоритм рекурсивно к списку целей G (уровень 2)

21) 1) C=родитель(пам, боб)

22) 2) выбираются в качестве C предложения программы P до C=мужчина(том)

23) 3)

24) 4) d={ }, G=пусто

25) 5) КОНЕЦ РАБОТЫ(успех)

В ходе решения переменные получили значения X=X₁, X₁= том, т. е. X= том. Это значение выдается в качестве ответа.

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

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

Пример 3.3.4.Отношение «предок».

Вариант 1

предок1(X, Z):-родитель(X, Z).

предок1(X, Z):-родитель(X, Y), предок1(Y, Z).

Вариант 2

предок2(X, Z):- родитель(X, Y), предок2(Y, Z).

предок2(X, Z):- родитель(X, Z).

Вариант 3

предок3(X, Z):- родитель(X, Z).

предок3(X, Z):- предок3(X, Y), родитель(Y, Z).

Вариант 4

предок4(X, Z):- предок4(X, Y), родитель(Y, Z).

предок4(X, Z):- родитель(X, Z).

В последнем варианте пролог-система не сможет найти ответа, т. е. цель предок4(X, Z) прежде всего порождает аналогичную цель предок4(X, Y) и т.д. до бесконечности.

Упражнения 3.3.1.

Рассмотреть работу алгоритма пролог-интерпретатора с различными вариантами программы «предок» при различных вопросах к системе.

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