Эффективная подготовка к государственным междисциплинарным экзаменам для студентов технических специальностей (стр. 41 )

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

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

Таким образом, для вычисления целей потребовалось 7 сопоставлений и один откат.

Формальное описание процедуры вычисления целей. Пусть список целей G1, G2, ...Gm.

1.Если список целей пуст, вычисление дает успех, если нет, то выполнятся пункт 2.

2.Берется первая цель G1 из списка. Пролог выбирает в базе данных, просматривая сначала первое предложение С,

С: H :- B1, B2, ..., Bn. голова, которого, сопоставляется с целью G1. Если такого предложения нет, то неудача. Если есть, то переменные конкретизируются и цель G1 заменяется на список целей В1’, В2’, ...Вn’, с конкретизированными значениями переменных.

3.Рассматривается рекурсивно через п.2 новый список целей. В1’, В2’, ...Вn’, G2, ...Gm. Если С - факт, то новый список короче на одну цель.(n=0) Если вычисление нового списка оканчивается успешно, то и исходный список целей выполняется успешно. Если нет, то новый список целей отбрасывается, снимается конкретизация переменных и происходит возврат к просмотру программы, но начиная с предложения следующего за предложением С. Описанный процесс возврата называется бэктрекинг. (backtracking).

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

Имея декларативно правильную программу, можно улучшить ее эффективность путем изменения порядка предложений и целей при сохранении ее декларативной правильности. Переупорядочивание - один из методов предотвращения за­цикливания.

4. Отсечение. Графическая иллюстрация действия cut. Формальное описание действия отсечения

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

CUT: <действия> - CUT

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

Однако для повышения эффективности выполнения программы, часто требуется вмешаться в перебор, ограничить его, исключить некоторые цели. Для этой цели в пролог введена специальная конструкция cut - "отсечение", обозначаемая как "!"( Читается "cut").

Cut подсказывает прологу "закрепить" все решения предшествующие появлению его в предложении. Это означает, что если требуется бэктрекинг, то он приведет к неудаче (fail) без попытки поиска альтернатив.

Графическая иллюстрация действия cut.

Графически действие cut можно показать с помощью box-представления логического вывода. В обычном случае бэктрекинг для правила G:-A, B,C. выглядит следующим образом:

Т. е. поиск альтернатив производится для всех целей: G, A,B, C. Заменим цель B на cut.

Действие cut заключается в отмене поиска альтернатив для целей A, G, стоящих после "!".

Формальное описание действия отсечения. Рассмотрим предложение Н:-B1, B2,..., Bm, !,..., Bn. Это предложение активизируется, когда некоторая цель G, будет сопоставляться с H. Тогда G называют целью-родителем. Если B1, B2,..., Bm, выполнены, а после!, например в Bi, i>m, произошла неудача и требуется выбрать альтернативные варианты, то для B1, B2,..., Bm такие альтернативы больше не рассматриваются и все выполнение окончится неудачей. Кроме этого G будет связана с головой H, и другие предложения процедуры во внимание не принимаются. Т. е. отсечение в теле предложения отбрасывает все предложения, расположенные после этого предложения. Формально действие отсечения описывается так: Пусть цель - родитель сопоставляется с головой предложения, в теле которого содержится отсечение. Когда при просмотре целей тела предложения встречается в качестве цели отсечение, то такая цель считается успешной и все альтернативы принятым решениям до отсечения отбрасываются и любая попытка найти новые альтернативы на промежутке между целью-родителем и сut оканчиваются неудачей. Процесс поиска возвращается к последнему выбору, сделанному перед сопоставлением цели родителя.

Т. е. отсечение в теле предложения отбрасывает все предложения, расположенные после этого предложения.

Формально действие отсечения можно описать еще так:

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

5. Сравнительная характеристика функционального, логического и процедурного подхода к программированию

Хар-ка	PASCAL	LISP	PROLOG
тип языка	процедурный	функциональный	логический
типы данных	скаляры, структуры	атомы, списки	атомы, структуры
обработка	присвоение	значение функции	связь переменных
данных	передача по значению	передача по значению	через унификацию
	передача по ссылке		по ссылке
управление	последовательное	вычисление функций	рекурсия
программой	ветвление	вычисления рекурсии
	циклы	условные	бэктрекинг
	рекурсия	циклы
структуры	блоки	функции	правила
программы	процедуры	LET-блоки	факты
действия	глобальные	локальные	область одно
переменных	локальные	свободные	предложение
транслятор	компилятор	интерпретатор	интерпретатор
		компилятор	компилятор
длина программы	5	3	1
скорость	1	2	5
Область	программы	символьная обработка	ЭС
	общего	ИИ	ИИ
	назначения		прототипы

  IX.  Объектно-ориентированное программирование

1. Определение класса в языке С++. Функции-члены класса в языке С++. Друзья класса в языке С++. Область видимости класса в языке С++. Инициализация класса в языке С++.

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

Определение типа, задаваемого пользователем (который в С++ называется class, т. е. класс), специфицирует данные, необходимые для представления объекта этого типа (свойства), и множество операций для работы с этими объектами (функции, методы). Определение имеет две части: закрытую (private) часть, содержащую информацию, которой может пользоваться только его разработчик, и открытую (public) часть, представляющую интерфейс типа с пользователем:

class ostream {

[private:]

streambuf* buf;

int state;

public:

void put(char*);

void put(long);

void put(double);

}

Описания после метки public: задают интерфейс: пользователь может обращаться только к трем функциям put(). Описания перед меткой public задают представление объекта класса ostream. Имена buf и state могут использоваться только функциями put(), описанными в открытой части.

class определяет тип, а не объект данных, поэтому чтобы использовать ostream, мы должны один такой объект описать (так же, как мы описываем переменные типа int): ostream my_out;

Считая, что my_out был соответствующим образом проинициализирован, его можно использовать, например, так: my_out. put("Hello, world\n");

Так же функция (метод) может определяться непосредственно при объявлении класса.

Для обращения к функции члену должен быть указан объект класса. В функции члене можно ссылаться на этот объект неявно, как это делалось выше в ostream::put(): в каждом вызове buf относится к члену buf объекта, для которого функция вызвана.