Математика, логика и программирование. Часть четвертая, логическое программирование

Предыдущая запись в этой серии была посвящена вопросам, традиционно объединяемым под вывеской “искусственный интеллект”. Конечно, вся упомянутая там деятельность может быть довольно полезна в чисто теоретическом плане, но на практике обычно интересны другие вопросы. Я упоминал о программе Eurisko, применявшейся в самых разных областях знаний – это можно было делать, так как Eurisko работала с представленными в некоторой формализованной форме произвольными утверждениями. Система этих утверждений называется “базой знаний”, а процесс построения базы знаний и создания запросов к ней – “логическим программированием”.

Обычно логическое программирование связывают с языком Prolog – но только потому, что он якобы “специально” для него предназначен. На самом деле тут применяется и Lisp, и “потомки” ML, и “самописные” движки типа Inform 7.

Математическая основа логического программирования – это исчисление предикатов. Предикат – это выражение с параметрами, которое, в зависимости от этих параметров, может быть истинно или ложно. Правила их преобразования – то есть исчисление – возникло, как попытка обоснования математики Фреге и Расселом. Число этих правил, как я говорил в предыдущей части, относительно невелико. Фактически, для построения базы знаний надо представить способ записи предикатов и систему, с этими предикатами работающую. На Lisp ядро такой системы записывается в виде нескольких тысяч строчек, но “стандартом” для построения “коммерческих” баз знаний стал язык Prolog – из-за того, что в него включены некоторые “процедурные” дополнения.

Например, довольно легко записать условие типа “список отсортирован” – но неизвестен (для системы логического вывода) способ, который позволит по этому условию эффективно отсортировать список. “Обычная” система логического вывода для того, чтобы отсортировать список, “имеет право” только перебрать все перестановки его элементов – а это ну очень медленно. В разработанном в начале 70-х Prolog предусматривается возможность задать некоторые действия в “явном” процедурном стиле, что несколько упрощает процедуру вывода (то есть получения ответа на “вопрос” с использованием заданной базы знаний).

Разумеется, при построении системы “простейших” предикатов, то есть базы знаний, программист не может определить, как будут “выводиться” те или иные утверждения. Это свойство “логических” языков программирования называется декларативностью – описывается не последовательность действий для достижения результата, описывается лишь “онтология” и требования к результату. Онтология – это умное слово, обозначающее базу знаний, оно позаимствовано из философии, где означает “всего лишь” систему представлений об окружающем мире. Возвращаясь к “Логико-философскому трактату” – “окружающий мир” есть совокупность утверждений о нем. Экспертная система – еще одно названия для логического “движка” с базой знаний – не может “прыгнуть выше головы”, то есть сформулировать утверждение, выходящее за рамки ее онтологии. Считается, что область применения логического программирования этим и ограничена, и сводится фактически к перебору вариантов – а с другой стороны, компьютеры все равно “перебирают варианты” быстрее человека, а главное – не стеснены “лишними знаниями”. Игроки в Traveller пытались играть, “отыгрывая роли” великих адмиралов – но все их знания о военно-морской тактике оказались перечеркнуты тем, что программа перебрала все варианты стратегии, включая и самые идиотские.

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

Правда, там, где от декларативных языков требуется производительность, и за эту производительность готовы платить – там все обстоит несколько лучше. Например, язык SQL является чисто декларативным – он описывает не процесс поиска данных, а то, какие данные удовлетворяют результату. Но в производительности СУБД заинтересованы люди с большими деньгами – и поэтому ведется постоянная работа по улучшению алгоритмов оптимизации запросов к БД.

Кстати, SQL построен на основе реляционной алгебры – предложенных Коддом в 1970 году операций для работы с “отношениями”, то есть таблицами с записями. Тоже математическая теория, только про нее в популярных самоучителях типа “PHP и SQL за два дня” не пишут.

5 комментариев

  1. rt_tr пишет:

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

  2. rt_tr пишет:

    .. которая использовалась при обучении. основы программирования/глубже – интересно все.

  3. marshallab пишет:

    Интересно и легко читается! Эдакий исторический отчерк. Вообщем интересно, спасибо :)
    PS предуматривается (а то мало ли – студенты будут печатать).

  4. cheryoleg пишет:

    как говорил председатель колхоза в фильме “Целина” – как знать чего не знаешь

  5. cheryoleg пишет:

    хлеба и зрелищ!!! ну ещто есть че