Процедурная семантика и декларативный смысл.

Предложения в языке Пролог.

Любое предложение заканчивается символом точки.

Виды предложений:

- факт;

Факт представляет собой некое утверждение, которое всегда истинно. Его не нужно выводить или доказывать, например, то, что Иван является родителем Петра, записано в виде факта – родит(иван, петр).

- правило;

Правило – более сложная конструкция, которую необходимо доказать, вывести из программы или согласовать с программой. Оно состоит из следующих основных частей: А: -В1, В2, В3, …, Вn,

где А – часть вывода, левая половина правила, голова правила;

: - - последовательность символов, читающаяся как «при условии, что»;

В1, В2, …, Вn – условная часть, правая часть, хвост правила. Правило в отличие от факта Пролог-программа обязана доказать.

Пример: бабушка(X, Y): -родит(X, Z), родит(Z, Y), жен(X).

- вопрос.

Вопрос является основным средством общения пользователя с Пролог-программой, т.е. своеобразным интерфейсом с программой. В общем виде вопрос записывается в следующей форме:

? -вопрос.

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

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

Термы Пролога.

Объекты данных – термы.

Атом – это любая последовательность букв, цифр, символов подчеркивания, начинающаяся со строчного символа.

Числа в Прологе бывают целыми и вещественными. Синтаксис целых чисел прост, как это видно из следующих примеров: 1, 1313, 0, -97. Вещественные числа можно представлять как в обычном формате, так и в экспоненциальном.

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

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

Структурные объекты (или просто структуры) — это объекты, которые состоят из нескольких компонент. Эти компоненты, в свою очередь, могут быть структурами. Например, дату можно рассматривать как структуру, состоящую из трех компонент: день, месяц, год. Хотя они и составлены из нескольких компонент, структуры в программе ведут себя как единые объекты. Для того, чтобы объединить компоненты в структуру, требуется выбрать функтор.

дата (14, сент, 2016). % дата-компонента(функтор), 14-число, сент – атом, 2016 –число

дата (день(14), сент, X).

Все структурные объекты можно изображать в виде деревьев

Если одно и то же имя появляется в программе в двух различных смыслах, то пролог-система будет различать их по числу аргументов и интерпретировать это имя как два функтора. Это возможно потому, что каждый функтор определяется двумя параметрами:

(1) именем, синтаксис которого совпадает с синтаксисом атомов;

(2) арностью — т.е. числом аргументов.

Процедурная семантика и декларативный смысл.

Рассмотрим предложение

P: - Q, R.

где P, Q и R имеют синтаксис термов. Приведем некоторые способы декларативной интерпретации этого предложения:

P — истинно, если Q и R истинны.

Из Q и R следует P.

Декларативный смысл программы определяет, является ли данная цель истинной (достижимой) и, если да, при каких значениях переменных она достигается.

Операция сопоставления.

Символ равенства (=) - операция сопоставления объектов и в случае, если она завершается успехом, переменные конкретизируются соответствующими значениями.

1) 2 терма сопоставимы в том случае, если они идентичны

? -а=а. %Yes

? -X=1. %Yes

? -X=Y. %Yes – наиболее общая конкретизация

? -10=X. %Yes

2) 2 терма сопоставимы в том случае, если их главные термы и их компоненты сопоставимы

? -X=дата(14, сент, 2016). %Yes

? -дата(14, Месяц, 2016) = дата(D, сент, Y),

% 1.? -дата=дата. Да

% 2.? -14=D. Да

%3.? Месяц=сент. Да

%4.? 2016=Y. Да

write(Месяц), write(D), write(Y). %сент142016

Общие правила выяснения, сопоставимы ли два терма S и T:

1) Если S и Т – простые объекты, то сопоставимы, если они идентичны.

2) S –переменная, Т – производный терм, то сопоставимы, если Т конкретизирует S.

3) S и Т – структурные объекты, то сопоставимы, если сопоставимы главные функторы и они покомпонентно сопоставимы.

Операторная запись.

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

: - op( 600, xfx, родитель).

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

Существуют три группы типов операторов, обозначаемые спецификаторами:

1) инфиксные операторы трех типов: xfx xfy yfx

2) префиксные операторы двух типов: fx fy

3) постфиксные операторы двух типов: хf yf

Спецификаторы выбраны с таким расчетом, чтобы нагляднее отразить структуру выражения, в котором 'f' соответствует оператору, а 'x' и 'y' представляют его аргументы.

Между 'x' и 'y' есть разница. Если аргумент заключен в скобки или не имеет структуры (является простым объектом), тогда его приоритет равен 0; если же он структурный, тогда его приоритет равен приоритету его главного функтора. С помощью 'x' обозначается аргумент, чей приоритет должен быть строго выше приоритета оператора (т e. его номер строго меньше номера приоритета оператора); с помощью 'y' обозначается аргумент, чей приоритет выше или равен приоритету оператора.

Типовые предикаты Пролога.

Типовые предикаты - позволяющие определить к какому типу относится объект.

1) var( X) - Эта цель успешна, если X в текущий момент — не конкретизированная переменная.

2) nonvar( X) - Эта цель успешна, если X — терм, отличный от переменной, или если X — уже конкретизированная переменная.

3) atom( X) - Эта цель истинна, если X обозначает атом.

4) integer( X)- Цель истинна, если X обозначает целое.

5) atomic( X) - Цель истинна, если X обозначает целое или атом.

Работа с базами данных.

Пролог программа представляется реляционной БД, то есть как описание некоторого множества отношений. Описание отношений в ней присутствует в явном виде (факты) или в неявном виде (правила). Более того, встроенные предикаты дают возможность корректировать эту БД в процессе выполнения программы. Предикаты для работы с БД таковы: assert, asserta, assertz, assert_in, asserta_in, retract, retractall.

Предикат assert(< the fact> ) – всегда успешен, а в качестве своего побочного эффекта добавляет факт к текущей базе данных. Предикат retract(< the fact> ) – приводит к противоположному эффекту: удаляет сопоставимый c < the fact> факт из базы данных.

Следует отметить, что добавленный факт будет присутствовать в текущей БД до конца текущего сеанса работы. Однако он будет «не видимым» для пользователя, т. е. не будет отображаться в рабочем окне. Для того чтобы факт появился в рабочем окне, необходимо использовать предикат assert_in.

К этой же группе предикатов относятся родственные предикаты asserta и assertz (последний в SP отсутствует). Предикат asserta добавляет предложение в начало БД, а assertz – в конец (аналогия assert).

Следует отметить, что из рабочего окна удаляемый факт не исчезнет. Для его «видимого» исчезновения необходимо использовать предикат retract_in.

Для удаления всех вхождений данного факта в БД необходимо использовать предикат retractall(< the fact> ).

Польза от таких предикатов очевидна, пользователь может динамически изменять БД в момент выполнения программы. Очевиден и тот факт, что неумелое, неграмотное их использование приведет к полному изменению исходной БД и как результат – непредсказуемые результаты. В отдельных случаях следует вовсе отказаться от использования предикатов этой группы.

Интерфейс с программой осуществляется посредством предиката read(Term) или read(Term, String), первый аргумент которого – вводимый терм, т. е. переводимое слово, а второй (если он имеется) – надпись на заголовке диалогового окна.

Экспертные системы.

Пример применения Пролога в области искусственного интеллекта - экспертная система.

Функции ЭС:

1) Диалог с пользователем, интерфейс

2) Выбор из базы знаний

Экспертными системами обычно называют программы, которые могут заменить эксперта в какой-то предметной области. Мы построим классификационную экспертную систему, которая будет пытаться угадать загаданное человеком животное. Если загаданное человеком животное окажется неизвестно нашей программе, у нее будет возможность пополнить свою базу знаний новой информацией.

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

Один из них предназначен для хранения характеристик животных и будет иметь два аргумента: первый — номер свойства, второй — его словесное описание.

Небольшой базовый набор свойств может выглядеть, например, так:

cond(1, " кормит детенышей молоком" ).

cond(2, " имеет перья" ).

cond(3, " плавает" ).

cond(4, " ест мясо" ).

cond(5, " имеет копыта" ).

cond(6, " летает" ).

cond(7, " откладывает яйца" ).

cond(8, " имеет шерсть" ).

cond(9, " имеет полосы" ).

cond(10, " имеет пятна" ).

cond(11, " имеет черно-белую окраску" ).

cond(12, " имеет длинную шею" ).

cond(13, " имеет длинные ноги" ).

cond(14, " имеет щупальца" ).

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

Выглядеть эта база знаний может примерно следующим образом:

rule(" гепард", [1, 4, 8, 10]).

rule(" тигр", [1, 4, 8, 9]).

rule(" жираф", [1, 5, 8, 10, 12, 13]).

rule(" зебра", [1, 5, 8, 9, 11]).

rule(" страус", [2, 14]).

rule(" пингвин", [2, 3, 11]).

rule(" орел", [2, 6]).

rule(" кит", [1, 3, 11]).

cond_is(N, '1') /* если загаданное животное имеет свойство с номером N */

cond_is(N, '2') /* если загаданное животное не имеет свойства с номером N */

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

animals: –

rule(X, L),

check(L),

nl, write(" Я думаю это ", X),

nl, write(" Я прав? (1 — да, 2 — нет)" ),

read_true_char(C), C='1',!.

animals: –

nl, write(" Я не знаю, что это за животное" ), nl,

nl, write(" Давайте добавим его в мою базу

знаний." ), nl,

update.

update: –

nl, write(" Введите название животного: " ),

readln(S),

add_cond(L), /* указываем свойства животного */

assert(rule(S, L), knowledge),

/* добавляем информацию в базу

знаний*/

save(" animals.ddb", knowledge).

S-выражения Лиспа. Примеры.

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

(name_function arg_1 arg_2 … arg_n), где

name_function – имя функции;

arg_I – аргументы.

Такая форма записи называется S-выражением.

Таким же образом записываются арифметические выражения, например, (+ 2 3), (- 4 3), (* x (+ y z)), etc.

Характерной особенностью S-выражения является наличие скобок. Действительно, их количество и местоположение влияет на смысл и результат S-выражения. Кроме скобок в любом S-выражении имеются элементы, называемые атомами. Различают два типа атомов: символьные и числовые. Символьный атом состоит обычно из букв, но может содержать и другие символы (числа, символ подчеркивания), но обязательно должен содержать хотя бы один символ, отличающий его от числа. Символьный атом нельзя расчленять на составляющие символы. Единственная операция, допустимая над символами – операция сравнения. Числовой атом является последовательностью цифр, возможно следующих за знаком.

S-выражение может состоять из произвольной смеси символьных и числовых атомов. Простейшая форма S-выражения – атом.

Формы S-выражений:

· один атом

· список атомов

· список с подсписками

QUOTE или ' - блокирует вычисление значения S-выражения.

Виды рекурсий в Лиспе.

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

Различают следующие формы рекурсии:

– простая рекурсия, если рекурсивный вызов встречается в некоторой ветви не более одного раза;

– параллельная рекурсия, если рекурсия встречается одновременно в нескольких аргументах функции;

– взаимная рекурсия, если при определении одной функции, вызывается другая, которая в свою очередь вызывает первую;

– рекурсия более высокого порядка, если в качестве аргумента рекурсивного вызова выступает рекурсивный вызов.

Замыкания.

Замыкание - это связь свободных переменных в некотором контексте.

Замыкание - это функция и контекст его применения. Сформированный на время вычисления контекст после окончания ее вычисления пропадает, и на него невозможно позже сослаться или вернуться к нему. Часто бывает полезным и необходимым, чтобы функция для продолжения вычислений могла запомнить связи и состояние более раннего контекста. Это достигается с помощью таких функциональных объектов, в которых вместе с самим описанием вычислений сохраняется контекст момента определения функционального объекта, защищённый от более позднего контекста вызова. Пару, состоящую из функции (лямбда-выражения) и контекста, называют замыканием или лексическим замыканием. Замыкание, как и имя функции или лямбда-выражение, можно использовать в качестве функционального аргумента

> (defun generate-even (*evenum*)

(function

(lambda()

(setq *evenum* (+ *evenum* 2)))))

> (setq gen-even-1 (generate-even 0))

> (funcall gen-even-1)