Применение языка ПРОЛОГ в области искусственного интеллекта.

Язык и система Пролог

Пролог (англ. Prolog) — я зык и система логического программирования, основанные на языке предикатов математической логики исчисления предикатов, представляющей собой подмножество логики предикатов первого порядка.

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

Факты в языке Пролог описываются логическими предикатами с конкретными значениями. Правила в Прологе записываются в форме правил логического вывода с логическими заключениями и списком логических условий.

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

Факты в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщенными сведениями.

 

Когда я начинал свое знакомство с Прологом, то самое шокирующее впечатление состояло в осознании одного, казалось бы, незначительного факта: в системе Пролог почти полностью отсутствуют какие-либо встроенные команды (конструкции самого языка) или как принято говорить в логическом программировании - стандартные предикаты. Приступая к написанию программ на процедурных (императивных) языках (к примеру, BASIC или Pascal) всегда опираешься на какой-то базис из огромного количества команд, заготовленных разработчиками "на все случаи жизни". Откройте, к примеру, какую-нибудь книжицу, типа "Delphi в подлиннике" или "VBA для профессионалов"… Их не то что открывать страшно, но и в закрытом состоянии для непосвященного они производят тяжелое впечатление, как в прямом, так и в переносном смысле. Проблема первоначального освоения процедурных языков заключается скорее в изучении значительного по объему синтаксиса языка и правил применения конкретных команд. Совсем иная проблема возникает при изучении Пролога...

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

Итак, основная концепция традиционных и повсеместно используемых императивных языков программирования напрямую связана с "фон-неймановской" моделью архитектуры компьютера. Согласно идее американского математика Джона фон Неймана все данные и программы компьютера хранятся в одной памяти. Процессор получает из памяти очередную команду, декодирует её, выбирает из памяти указанные в качестве операндов данные, выполняет команду и размещает результат снова в памяти. Программа на императивном языке представляет собой последовательность команд. Команды программы выполняются последовательно: сверху - вниз и слева - направо. Встречаются команды, которые могут изменять последовательность выполнения команд. Вообще, императив (происходит от лат. imperativus - повелительный, лат. imperator - повелитель) - приказ, требование. К наиболее известным и распространенным императивным языкам программирования относятся: ALGOL, FORTRAN, PL/1, BASIC, Pascal, C, C++, Java.

Декларативные (declaration - объявление, заявление) языки - это языки программирования, в которых операторы представляют собой высказывания об отношениях между объектами некоторого предметного поля. Высказывания могут быть двух видов: 1) факт - задает отношение между конкретными объектами; 2) правило - опосредованно задает отношение между объектами, заменяя их переменными и требуя выполнения некоторых условий. Таким образом, программа на декларативном языке, по сути, представляет собой совокупность фактов и правил, а работа с программой заключается в формулировке вопроса, ответ на который ищется самой системой программирования в процессе перебора с подстановками значений на множестве фактов и правил. Программисту нет необходимости разрабатывать алгоритм перебора этим занимается сама система программирования. Последовательность выполнения операторов программы детерминирована совокупностью фактов, правил и вопросов, сформулированных программистом.

Наиболее известным языком декларативного программирования является Пролог. Язык программирования Пролог базируется на ограниченном наборе механизмов, включающих в себя сопоставление образцов (унификация), автоматический перебор (поиск) с возвратами (бэктрекинг), рекурсия. Этот небольшой набор в руках опытного программиста образует удивительно мощный и гибкий инструмент логического программирования. Пролог находит свое воплощение при решении задач искусственного интеллекта, а также любых задач, требующих нечислового программирования. Само название Пролог есть сокращение, означающее программирование в терминах логики (Prolog - programming in logic). Идея использовать логику предикатов в качестве языка программирования возникла впервые в начале 70-х годов. Первыми исследователями, разрабатывавшими эту идею, были Роберт Ковальский из Эдинбурга (теоретические аспекты), Маартен ван Эмден из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ из Марселя (реализация). Сегодняшней своей популярности Пролог во многом обязан эффективной реализации этого языка, полученной в Эдинбурге Дэвидом Уорреном в середине 70-х годов.

Мы остановимся на наиболее известной у нас в стране и довольно эффективной версии Пролога - Турбо Прологе. Его начинала разрабатывать фирма Borland International в содружестве с датской компанией Prolog Development Center (PDC). Первая версия вышла в 1986 году. Последняя совместная версия имела номер 2.0 и была выпущена в 1988 году. В 1990 году PDC получила монопольное право на Турбо Пролог и дальше продвигала его под названием PDC Prolog. С 1996 года компания Prolog Development Center стала выпускать Visual Prolog версии 4.0 и выше. Основы логического программирования мы будем изучать с использованием PDC Prolog 3.21.

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

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

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

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

Min = Cells(1, 1)

For i = 2 To 10

If Cells(i, 1) < Min Then Min = Cells(i, 1)

Next

Cells(11, 1) = Min

В данном случае вы видите VBA код, выполненный в Excel`е. Все значения располагаются в первом столбце в диапазоне строк от 1 до 10, ответ заносится в ячейку Cells(11, 1). Суть размышлений такова: возьмем первое значение из списка и назначим его текущим минимальным; далее будем сравнивать текущее минимальное значение последовательно со всеми значениями из списка и если какое-то из них будет меньше текущего минимального, то назначим уже его текущим минимальным; так будем продолжать до тех пор, пока список не кончится; когда список кончится, то текущее минимальное назовем просто минимальным значением списка и зафиксируем его.

Мы последовательно и в деталях объяснили машине как решать задачу.

Давайте сравним этот подход с реализацией на Прологе:

min([H|T],MT):-min(T,MT),MT<=H,!.

min([H|_],H).

В переводе на русско-алгоритмический это будет звучать примерно так: если минимум в конце списка меньше первого элемента списка, то результатом будет минимум из конца списка, иначе, первый элемент и есть искомый результат.

По существу мы не рассказали машине как решать задачу, мы лишь передали как мы понимаем что есть минимум списка. Иначе говоря, мы описали отношение между объектами предметного поля. В этом описании (декларации) указаны признаки минимума, отличающие его от других значений (максимум, среднее арифметическое и т.п.). Кроме того, обратите внимание на то, что в лексике Пролога нет команды min. Вместо min можно написать всё, что угодно. К примеру, nim или mother и программа будет работать с таким же результатом. Программист волен давать предикатам любые имена, ограничиваясь лишь удобством последующего чтения и понимания существа программы.

Почему стоит изучить логическое программирование?

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

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

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

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

Пролог освоить можно. Сложно, конечно, но "дорогу осилит идущий".

Метод опорных векторов

Метод опорных векторов относится к группе граничных методов. Он определяет классы при помощи границ областей.

При помощи данного метода решаются задачи бинарной классификации.

В основе метода лежит понятие плоскостей решений.

Цель метода опорных векторов - найти плоскость, разделяющую два множества объектов;

 

Метод "ближайшего соседа" или системы рассуждений на основе аналогичных случаев

Следует сразу отметить, что метод "ближайшего соседа" ("nearest neighbour") относится к классу методов, работа которых основывается на хранении данных в памяти для сравнения с новыми элементами. При появлении новой записи для прогнозирования находятся отклонения между этой записью и подобными наборами данных, и наиболее подобная (или ближний сосед) идентифицируется.

При таком подходе используется термин "k-ближайший сосед" -

выбирается k "верхних" (ближайших) соседей для их рассмотрения в качестве множества "ближайших соседей".

 

Байесовская классификация

Так называемая наивная классификация или наивно-байесовский подход

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

"Наивная" классификация - достаточно прозрачный и понятный метод классификации. "Наивной" она называется потому, что исходит из предположения о взаимной независимости признаков.

Свойства наивной классификации:

1. Использование всех переменных и определение всех зависимостей между ними.

2. Наличие двух предположений относительно переменных:

o все переменные являются одинаково важными;

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

Нейронные сети (+ кластеризация)

Нейронные сети (Neural Networks) - это модели биологических нейронных сетей мозга, в которых нейроны имитируются относительно простыми, часто однотипными, элементами (искусственными нейронами).

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

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

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

Перед использованием нейронной сети ее необходимо обучить.

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

Нейронные сети бывают с обратными связями и без обратных связей.

Сети без обратных связей

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

- Другие сети (когнитрон, неокогнитрон, другие сложные модели).

Сети с обратными связями

- Сети Хопфилда (задачи ассоциативной памяти).

- Сети Кохонена (задачи кластерного анализа).

 

 

Методы кластерного анализа.

Иерархические методы.

Методы кластерного анализа можно разделить на две группы:

 иерархические (иерархические методы кластерного анализа используются при небольших объемах наборов данных, результат – древовидная диаграмма);

 неиерархические.

Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.

Итеративные методы.

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

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

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

Итеративные методы показывают более высокую устойчивость по отношению к шумам и выбросам, некорректному выбору метрики, включению незначимых переменных в набор, участвующий в кластеризации.

 

Факторный анализ

Факторный анализ - это метод, применяемый для изучения взаимосвязей между значениями переменных.

Вообще, факторный анализ преследует две цели:

сокращение числа переменных;

классификацию переменных - определение структуры взаимосвязей между переменными.

Соответственно, факторный анализ может использоваться для решения задач сокращения размерности данных или для решения задач классификации.

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

 

Методы визуализации

Традиционные методы визуализации могут находить следующее применение:

· представлять пользователю информацию в наглядном виде;

· компактно описывать закономерности, присущие исходному набору данных;

· снижать размерность или сжимать информацию;

· восстанавливать пробелы в наборе данных;

· находить шумы и выбросы в наборе данных.

Методы визуализации, в зависимости от количества используемых измерений, принято классифицировать на две группы [22]:

· представление данных в одном, двух и трех измерениях - к этой группе методов относятся хорошо известные способы отображения информации, которые доступны для восприятия человеческим воображением. Практически любой современный инструмент Data Mining включает способы визуального представления из этой группы. Среди двухмерных и трехмерных средств наиболее широко известны линейные графики, линейные, столбиковые, круговые секторные и векторные диаграммы.;

· представление данных в четырех и более измерениях - представления информации в четырехмерном и более измерениях недоступны для человеческого восприятия. Однако разработаны специальные методы для возможности отображения и восприятия человеком такой информации.

Наиболее известные способы многомерного представления информации:

· параллельные координаты;

· "лица Чернова" - основная идея представления информации состоит в кодировании

значений различных переменных в характеристиках или чертах человеческого лица;

· лепестковые диаграммы.

8. Этапы процесса Data Mining: анализ предметной области; · постановка задачи; · подготовка данных; построение моделей;· проверка и оценка моделей;· выбор модели;· применение модели;· коррекция и обновление модели.

 

Этап 2. Постановка задачи

Постановка задачи Data Mining включает следующие шаги:

· формулировка задачи;

· формализация задачи.

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

 

Этап 3. Подготовка данных

Цель этапа: разработка базы данных для Data Mining.

На этап подготовки данных, по некоторым оценкам, может быть потрачено до 80% всего времени, отведенного на проект.

1. Определение и анализ требований к данным

На этом этапе осуществляется моделирование данных, т.е. определение и анализ требований к данным, которые необходимы для осуществления Data Mining. При

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

Сбор данных

Если нет ХД. В этом случае источником для исходных данных являются

оперативные, справочные и архивные БД, т.е. данные из существующих информационных систем.

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

 

Предварительная обработка данных

Анализировать можно как качественные, так и некачественные данные. Результат будет достигнут и в том, и в другом случае. Для обеспечения качественного анализа необходимо проведение предварительной обработки данных, которая является необходимым этапом процесса Data Mining.

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

Данные высокого качества - это полные, точные, своевременные данные, которые

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

Рассмотрим наиболее распространенные виды грязных данных:

Пропущенные значения (Missing Values).

Некоторые значения данных могут быть пропущены в связи с тем, что:

· данные вообще не были собраны (например, при анкетировании скрыт возраст);

· некоторые атрибуты могут быть неприменимы для некоторых объектов (например,

атрибут "годовой доход" неприменим к ребенку).

Шумы и выбросы.

Выбросы - резко отличающиеся объекты или наблюдения в наборе данных.

Задача аналитика - не только их обнаружить, но и оценить степень их влияния на

результаты дальнейшего анализа - информативной часть либо ошибки.

 

4. построение моделей;·

 

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

Аналитик создает модель как подобие изучаемого объекта. Модели могут быть записаны в виде различных изображений, схем, математических формул и т.д.

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

 

Для построения моделей используются различные методы и алгоритмы Data Mining.

Некоторые задачи могут быть решены при помощи моделей, построенных на основе различных методов. Многие разработчики включают в инструменты Data

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

 

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

Постановка задачи формализует суть задачи, так, наличие входных и выходных

переменных при решении задачи классификации определяет выбор одного из методов "обучение с учителем"(при наличии лишь вх. переменных - "обучение без учителя").

 

Этапы подготовки данных, построения модели, оценки модели и выбора лучшей

представляют собой цикл. Если по каким-либо причинам построенная модель оказалось неприемлемой, цикл повторяется и следует один из следующих этапов:

· подготовка данных (если причина некорректности модели - в данных);

· построение модели (если причина некорректности - во внутренних параметрах самой

модели).

 

Этап 6. Выбор модели

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

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

 

Этап 7. Применение модели

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

 

Стандарт PMML

PMML - язык описания предикторных (или прогнозных) моделей или языке

разметки для прогнозного моделирования.

PMML относится к группе стандартов по хранению и передаче моделей Data Mining.

 

Основа этого стандарта - язык XML. Примером другого стандарта, также основанного на языке XML, является стандарт обмена статистическими данными и метаданными. Стандарт PMML используется для описания моделей Data Mining и статистических моделей.

Основная цель стандарта PMML - обеспечение возможности обмена моделями данных между программным обеспечением разных разработчиков (с другими PMML-инструментами).

Таким образом, модель, созданная в одном программном продукте, может использоваться для прогнозного моделирования в другом.

 

Стандарт PMML включает:

описание анализируемых данных (структура и типы данных);

описание схемы анализа (используемые поля данных);

описание трансформаций данных (например, преобразования типов данных);

описание статистик, прогнозируемых полей и самих прогнозных моделей.

 

 

Язык и система Пролог

Пролог (англ. Prolog) — я зык и система логического программирования, основанные на языке предикатов математической логики исчисления предикатов, представляющей собой подмножество логики предикатов первого порядка.

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

Факты в языке Пролог описываются логическими предикатами с конкретными значениями. Правила в Прологе записываются в форме правил логического вывода с логическими заключениями и списком логических условий.

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

Факты в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщенными сведениями.

 

Когда я начинал свое знакомство с Прологом, то самое шокирующее впечатление состояло в осознании одного, казалось бы, незначительного факта: в системе Пролог почти полностью отсутствуют какие-либо встроенные команды (конструкции самого языка) или как принято говорить в логическом программировании - стандартные предикаты. Приступая к написанию программ на процедурных (императивных) языках (к примеру, BASIC или Pascal) всегда опираешься на какой-то базис из огромного количества команд, заготовленных разработчиками "на все случаи жизни". Откройте, к примеру, какую-нибудь книжицу, типа "Delphi в подлиннике" или "VBA для профессионалов"… Их не то что открывать страшно, но и в закрытом состоянии для непосвященного они производят тяжелое впечатление, как в прямом, так и в переносном смысле. Проблема первоначального освоения процедурных языков заключается скорее в изучении значительного по объему синтаксиса языка и правил применения конкретных команд. Совсем иная проблема возникает при изучении Пролога...

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

Итак, основная концепция традиционных и повсеместно используемых императивных языков программирования напрямую связана с "фон-неймановской" моделью архитектуры компьютера. Согласно идее американского математика Джона фон Неймана все данные и программы компьютера хранятся в одной памяти. Процессор получает из памяти очередную команду, декодирует её, выбирает из памяти указанные в качестве операндов данные, выполняет команду и размещает результат снова в памяти. Программа на императивном языке представляет собой последовательность команд. Команды программы выполняются последовательно: сверху - вниз и слева - направо. Встречаются команды, которые могут изменять последовательность выполнения команд. Вообще, императив (происходит от лат. imperativus - повелительный, лат. imperator - повелитель) - приказ, требование. К наиболее известным и распространенным императивным языкам программирования относятся: ALGOL, FORTRAN, PL/1, BASIC, Pascal, C, C++, Java.

Декларативные (declaration - объявление, заявление) языки - это языки программирования, в которых операторы представляют собой высказывания об отношениях между объектами некоторого предметного поля. Высказывания могут быть двух видов: 1) факт - задает отношение между конкретными объектами; 2) правило - опосредованно задает отношение между объектами, заменяя их переменными и требуя выполнения некоторых условий. Таким образом, программа на декларативном языке, по сути, представляет собой совокупность фактов и правил, а работа с программой заключается в формулировке вопроса, ответ на который ищется самой системой программирования в процессе перебора с подстановками значений на множестве фактов и правил. Программисту нет необходимости разрабатывать алгоритм перебора этим занимается сама система программирования. Последовательность выполнения операторов программы детерминирована совокупностью фактов, правил и вопросов, сформулированных программистом.

Наиболее известным языком декларативного программирования является Пролог. Язык программирования Пролог базируется на ограниченном наборе механизмов, включающих в себя сопоставление образцов (унификация), автоматический перебор (поиск) с возвратами (бэктрекинг), рекурсия. Этот небольшой набор в руках опытного программиста образует удивительно мощный и гибкий инструмент логического программирования. Пролог находит свое воплощение при решении задач искусственного интеллекта, а также любых задач, требующих нечислового программирования. Само название Пролог есть сокращение, означающее программирование в терминах логики (Prolog - programming in logic). Идея использовать логику предикатов в качестве языка программирования возникла впервые в начале 70-х годов. Первыми исследователями, разрабатывавшими эту идею, были Роберт Ковальский из Эдинбурга (теоретические аспекты), Маартен ван Эмден из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ из Марселя (реализация). Сегодняшней своей популярности Пролог во многом обязан эффективной реализации этого языка, полученной в Эдинбурге Дэвидом Уорреном в середине 70-х годов.

Мы остановимся на наиболее известной у нас в стране и довольно эффективной версии Пролога - Турбо Прологе. Его начинала разрабатывать фирма Borland International в содружестве с датской компанией Prolog Development Center (PDC). Первая версия вышла в 1986 году. Последняя совместная версия имела номер 2.0 и была выпущена в 1988 году. В 1990 году PDC получила монопольное право на Турбо Пролог и дальше продвигала его под названием PDC Prolog. С 1996 года компания Prolog Development Center стала выпускать Visual Prolog версии 4.0 и выше. Основы логического программирования мы будем изучать с использованием PDC Prolog 3.21.

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

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

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

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

Min = Cells(1, 1)

For i = 2 To 10

If Cells(i, 1) < Min Then Min = Cells(i, 1)

Next

Cells(11, 1) = Min

В данном случае вы видите VBA код, выполненный в Excel`е. Все значения располагаются в первом столбце в диапазоне строк от 1 до 10, ответ заносится в ячейку Cells(11, 1). Суть размышлений такова: возьмем первое значение из списка и назначим его текущим минимальным; далее будем сравнивать текущее минимальное значение последовательно со всеми значениями из списка и если какое-то из них будет меньше текущего минимального, то назначим уже его текущим минимальным; так будем продолжать до тех пор, пока список не кончится; когда список кончится, то текущее минимальное назовем просто минимальным значением списка и зафиксируем его.

Мы последовательно и в деталях объяснили машине как решать задачу.

Давайте сравним этот подход с реализацией на Прологе:

min([H|T],MT):-min(T,MT),MT<=H,!.

min([H|_],H).

В переводе на русско-алгоритмический это будет звучать примерно так: если минимум в конце списка меньше первого элемента списка, то результатом будет минимум из конца списка, иначе, первый элемент и есть искомый результат.

По существу мы не рассказали машине как решать задачу, мы лишь передали как мы понимаем что есть минимум списка. Иначе говоря, мы описали отношение между объектами предметного поля. В этом описании (декларации) указаны признаки минимума, отличающие его от других значений (максимум, среднее арифметическое и т.п.). Кроме того, обратите внимание на то, что в лексике Пролога нет команды min. Вместо min можно написать всё, что угодно. К примеру, nim или mother и программа будет работать с таким же результатом. Программист волен давать предикатам любые имена, ограничиваясь лишь удобством последующего чтения и понимания существа программы.

Почему стоит изучить логическое программирование?