Бэктрекинг   Рекурсия  

РАЗДЕЛЫ САЙТА


ГЛАВНАЯ

Когда я начинал свое знакомство с Прологом, то самое шокирующее впечатление состояло в осознании одного, казалось бы, незначительного факта: в системе Пролог почти полностью отсутствуют какие-либо встроенные команды (конструкции самого языка) или как принято говорить в логическом программировании - стандартные предикаты. Приступая к написанию программ на процедурных (императивных) языках (к примеру, 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 и программа будет работать с таким же результатом. Программист волен давать предикатам любые имена, ограничиваясь лишь удобством последующего чтения и понимания существа программы.
Почему стоит изучить логическое программирование?
Тезис первый (совсем не обязательный) - просто для расширения кругозора. Если вы считаете себя специалистом в информационных технологиях или собираетесь таковым стать, то такой серьезный пробел в области практического приложения математической логики как непонимание логических программ может сильно сказаться на вашей самооценке в дальнейшем.
Тезис второй - эстетическое наслаждение. Действительно, если вы не просто существуете в мире информационных технологий, а отчасти и разрабатываете их, то понимание основных механизмов порождения решений логическими программами может доставить вам истинное наслаждение, а конкретные реализации некоторых программ будут бросать вас от недоумения до восторженного восприятия.
Тезис третий (непременное условие) - интеллектуальное развитие. Мое субъективное мнение заключается в том, что человек, сумевший понять методологию написания логических программ, а, тем более, осиливший её настолько, что может на практике применять свои познания, имеет право считать себя интеллектуально продвинутым. Тут дело не в пустом бахвальстве, а в том, что "декларативный" программист имеет в своем багаже дополнительную модель представления мира и явно обладает факультативным инструментом, расширяющим возможности своего мыслительного аппарата.
Тезис четвертый (вполне вероятный) - повышение качества процедурных программ. Любой опыт развивает, а опыт деятельности в альтернативной парадигме позволяет взглянуть на обыденные вещи в несколько ином ракурсе. Возвращаясь из мира логических программ к традиционным языкам программирования, проявляется способность по-новому, четче и более структурировано конструировать код. Иногда порождаются решения, до которых ранее не удавалось дойти, докопаться.
Пролог освоить можно. Сложно, конечно, но "дорогу осилит идущий".






©Copyright 2007 - Беляков Андрей Юрьевич - Про Пролог / proprolog.narod.ru - All Rights Reserved
Hosted by uCoz