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

Функциональное программирование

Применение ЭВМ для решения задач искусственного интеллекта и обработки текстов привело к созданию функциональных языков. Эти языки имеют хорошо проработанное математическое основание - l-исчисление. Функция в математике - отображение объектов из множества величин (области определения функции или домена) в объекты другого множества (область значений функции). Переменные в функциональной программе рассматриваются как переменные в математике: если они существуют, то имеют какую-то величину, и эта величина не может измениться. Функциональная программа описывает, что должно быть вычислено, то есть является просто выражением, определенным в терминах заранее заданных функций и функций, определенных пользователем. Величина этого выражения является результатом программы. Таким образом, здесь отсутствует состояние программы и предыстория вычислений. Первым языком функционального программирования является созданный в начале 1960-х годов язык ЛИСП (LISP - LISt Processing). В отличие от процедурных языков, в которых действия в основном выражаются в виде итерации - повтора какого-либо фрагмента программы несколько раз, в ЛИСП вычисления производятся с помощью рекурсии - вызова функцией самой себя, а основная структура данных - это список.

Математическая логика использует отточенный формальный язык для представления знаний об объектах той или иной предметной области, включая явные средства выражения гипотез и суждений. Подобные качества роднят логику и искусство программирования. Идея непосредственного применения логики в качестве средства программирования возникла практически одновременно с первыми процедурными языками. Главная особенность такого подхода состоит в том, что программа (логическая) состоит из набора утверждений (аксиом), а вычисление, выполняемое под управлением такой программы, представляет собой логический вывод некоторого целевого утверждения - искомого результата. Вывод производится из аксиом программы по правилам математической логики, причем эти правила применяются автоматически, программист не должен их специально указывать.

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

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

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