Пролог и логическое программирование

с жесткими требованиями к рецепту комбикормов для птицы.

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

На небольших фермах необходимо

Поступила 30.12.9е)

иметь полный набор машин для заготовки кормов (тракторы типа МТЗ-80, косилки, грабли, тележки), навесы для хранения грубых кормов, склады для зерновых кормов, картофелехранилища. На фермах крупного рогатого скота для механизации доения надо использовать доильные установки АИД-01, УДИ-2 и др. На свинофермах целесообразно иметь небольшие кормо-приготовитсльные пункты, оборудованные измельчителями зерна, машинами для мойки и запаривания или варки картофеля, малогабаритными смесителями. Рационально их сблокировать с помещениями для содержания животных.

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

ПРОЛОГ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

И. П. САМОЙЛОВА, аспирант

Цель данной статьи — определить место языка Пролог в системе парадигм программирования. Краткий обзор истории создания логического программирования и описание особенностей программы на языке Пролог призваны обратить внимание на математические основания хорновского программирования — использование принципа резолюции для хорновских дизъюнктов.

Языки логического программирования — это класс языков программи-

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

Программа состоит из двух компонентов — логики и управления. Под логикой понимается полное непротиворечивое описание предметной обла-

© И. П. Самойлова, 2000

сти, а управление — это принципы, заложенные в организацию вычисления результата.

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

Классическим языком хорновского программирования является язык Пролог.

Из истории логического программирования

В 1879 г. Готтлоб Фреге разработал формальный язык логики. Далее формальная теория исчисления предикатов развивалась и совершенствовалась.

Около 1930 г. была доказана фундаментальная теорема исчисления предикатов — теорема о полноте. Фреге этот факт принимал на веру, а доказали его независимо друг от друга французский алгебраист и логик Жак Эрбран, норвежец Торальф Сколем и австрийский математик Курт Гедель.

Совершенствование вычислительной техники привело к идее использования ЭВМ для символьных вычислений. В 50-е гг. были осуществлены попытки реализации процедуры доказательства на вычислительных машинах. Датчанин Э. Бет, а за ним и Ст. Кан-гер и Д. Правиц из Швеции, П. Гил-мор, X. Ван, М. Девис и X. Патнем из США попробовали реализовать алгоритм на вычислительных машинах того времени. Опыт этих исследований показал, что алгоритм, сформулированный в 1930 г., был не очень хорош

с вычислительной точки зрения.

Важным шагом стали опубликованные Робинсоном в 1965 г. алгоритм унификации и принцип резолюции. Попытки использовать данный принцип в качестве вычислительной модели не увенчались успехом. С тех

пор предложено много усовершенствований принципа резолюции.

Р Ковальский, Д. Кюнер, Д. Лак-хем и Д. Лавленд упорно искали усовершенствование тривиального алгоритма резолюции. Ими была разработана идея ограничить правило резолюций так, чтобы структуры, порождаемые алгоритмом, были линейны. Ковальскому удалось впервые описать процедурную интерпретацию хорновских дизъюнктов.

В начале 70-х гг. группа специалистов Марсельского университета во главе с А. Колмероэ разработала специальную программу, предназначенную для доказательства теорем. Она была написана на языке Фортран и использовалась для обработки текстов на естественном языке. Программа доказательства теорем, названная Прологом, использовала линейную резолюцию; дизъюнкты, описывающие задачу, ограничивались хорновскими дизъюнктами. Использовалась и предложенная Колмероэ процедурная интерпретация, преобразующая процесс доказательства в более традиционный процесс вычисления, когда каждый шаг является вызовом процедуры.

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

В 1981 г. Пролог был принят в качестве базового языка в японской программе создания ЭВМ пятого поколения. И хотя он не стал базовым языком для ЭВМ, но японский проект привел к тому, что на Пролог обратили внимание. Появилось большое количество доступных его реализаций для различных компьютеров, установился стандарт, опубликованы многочисленные книги по программированию на этом языке. „Настало время признать, что хотя Пролог и не достиг высоких целей логического программирования, но тем не менее является мощным, продуктивным и практически пригодным формализмом программирования" [1 ].

Программа на языке Пролог

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

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

Совокупность правил, имеющих в заголовке один и тот же предикат, на-

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

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

* * *

1. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. М.: Мир, 1990. Поступила 16.02.2000.

РЕЦЕНЗИИ

В ПОМОЩЬ ВСЕМ ЛЮБИТЕЛЯМ ПРИРОДЫ

Растительный мир Мордовии достаточно богат и разнообразен. Он насчитывает свыше 1 ООО видов высших (сосудистых) растений и представлен древесными породами, кормовыми трава-

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