Лекция 1. Декларативные и процедурные способы представления знаний

Планирование на предприятии

Суполова Марина Калиновна

Учебное пособие

Компьютерный набор и верстка автора

Подготовка к печати М. М. Давыдов

Сдано в производство г. Подписано в печать г.

Уч.-изд. л. . Формат 84х108 ¹/₁₆ . Усл.-печ. л.

Изд. № . Заказ № .

Редакционно-издательский отдел Севмашвтуза

164500, г. Северодвинск, ул. Воронина, 6

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

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

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

Второй способ в общем случае менее универсален, так как для каждого класса задач нужен свой язык описания задачи и свой «решатель» для задач, написанных на этом языке. Например, при решении задачи линейного программирования для описания условий задачи (системы линейных неравенств и оптимизируемой линейной формы) нужен язык, на котором можно будет описать только эти условия и ничего больше. Решатель, или интерпретатор языка описания задачи, должен реализовывать какой‑либо из известных способов решения данного класса задач (например, симплекс метод). Очевидно, что если задача может быть формализована в терминах языка описания задач какого‑либо «решателя», то ее решение может быть получено с минимальными затратами. Однако справедлив тезис: чем шире класс задач, которые умеет решать «решатель», тем более универсальные и, следовательно, менее эффективные методы решения он должен использовать, и наоборот.

Закономерен вопрос: «Можно ли «придумать» декларативные языки, т. е. языки, описывающие «что», а не «как», которые были бы универсальными, т.е. пригодными для описания любой задачи, и какие математические понятия можно положить в их основу?». Одними из наиболее универсальных понятий в математике являются понятия функции и предиката, именно они легли в основу современных языков функционального и логического программирования.

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

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

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

Рассматривая декларативные и императивные парадигмы, нельзя не затронуть вопрос о месте в этом ряду объектно‑ориентированного программирования (ООП). Данные языки содержат значительную декларативную компоненту — описание классов (механизм классов, правда, в несколько ином понимании, присутствует в соответствующих версиях ФП и ЛП). Однако сама вычислительная модель, лежащая в основе этих языков (в виде множества статически или динамически определенных объектов, обменивающихся сообщениями), и методы, изменяющие значения атрибутов, имеют явный процедурный характер. Поэтому данные языки с точки зрения рассматриваемой классификации ближе к императивным языкам. Вообще деление языков на императивные, ФП, ЛП и ООП в определенной мере условно — можно разрабатывать вполне объектно‑ориентированные программы на ассемблере, хотя это и очень сложно. Можно следовать функциональной парадигме, используя язык С. Однако наиболее просто и естественно выглядят программы, написанные в соответствии с той парадигмой, для поддержки которой предназначен данный язык.

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

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

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

И с теоретической и тем более с практической точек зрения чрезвычайно важен вопрос: «Можно ли, используя ФП (ЛП), писать программы, не принимая во внимание процедурную семантику?». Ответ ожидаем: «Нет, нельзя». Природу обмануть нельзя: именно непонимание этого факта привело ко многим заблуждениям представителей искусственного интеллекта в 1980‑х гг. Полное игнорирование процедурной семантики может превратить программу в «исполняемую спецификацию», т. е. формально правильное определение задачи, но совершенно непригодное для практического использования из‑за крайней вычислительной неэффективности. Для превращения спецификации в реальную программу ее необходимо оптимизировать, используя какую‑либо эвристику (догадку), что с успехом делает опытный программист.