13.4 Логическое и функциональное программирование Логическое программирование

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

Логическое программирование - программирование, основанное на  логике. Часто его определяют как использование языка логики в качестве языка программирования, вместе с использованием логического вывода в качестве вычислительного механизма. Это очень хорошее определение, но оно очень широкое. Логическое программирование, определенное таким образом, включает в себя то же функциональное программирование, как и многие другие стили программирования.

Исторически сложилось так, что термином "логическое программирование" обозначают использование в качестве языка программирования некоторого подмножества чистой  логики первого порядка. Это означает, что для выражения концепции действия применяется математическое понятие отношения или предиката.

Пролог остается наиболее распространенным языком логического программирования. Логическое программирование хорошо подходит для некоторых применений, таких как дедуктивные базы данных, синтаксический анализ (особенно неоднозначных грамматик) и сложные комбинаторные задачи.

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

 

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

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

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

Это же понятие функции как мы увидим в дальнейшем, используется и для выражения концепции данных. Вообще, изучение функционального программирования - хороший повод убедиться, что разница между «данными» и «операциями» не столь уж принципиальна. Функции в функциональных языках являются объектами «первого класса».

Языки программирования налагают различные ограничения на методы использования элементов языка. Элементы первого класса - это элементы с наименьшим количеством ограничений. Важные свойства таких первоклассных элементов:

                     На них можно ссылаться посредством переменных.

                     Их можно включать в структуры данных.

                     Их можно передавать как параметры.

                     Они могут быть возвращены в качестве результата.

За небольшими исключениями (например, Алгол-68) императивные языки ограничивают «права и свободы» функций и процедур. В отличие от них, функциональные языки предоставляет функциям статус первого класса. Это создаёт трудности для их эффективной реализации, но приводит к значительному увеличению выразительной силы этих языков. Диалект языка Лисп Scheme позволяет прозрачно выразить основные идеи функционального программирования.

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

С точки зрения функционального программирования программа - функция, применяемая к вводу и возвращающая вывод.

            output = program(input)

Логическая программа - отношение между вводом и выводом.

    program(input, output)

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

Имеется, однако, более серьёзные отличия. Функции в функциональных языках "однонаправлены". Они получают аргументы и возвращают результат. В логических языках разница между вводом и выводом условна. Мы можем указать желаемый вывод и получить ввод, который его обеспечит. Другое важное отличие - индетерминизм логических языков. Результат в них не обязательно определяется однозначно.

Проиллюстрировать эти различия можно простым примером. Рассмотрим две программы, определяющие площади материков.

Функциональная программа	Логическая программа
area(Eurasia) = 55 area(Africa) = 29 area(NorthAmerica) = 20 area(SouthAmerica) = 18 area(Australia) = 7 area(Antarctica) =14	area(Eurasia,55) area(Africa,29) area(NorthAmerica,20) area(SouthAmerica,18) area(Australia,7) area(Antarctica,14)

 

Теперь к функциональной программе можно обратиться, например, с запросом area(Eurasia) и получить ответ 55.

Запросы к логической программе разнообразнее: area(Eurasia,a) выдаст ответ {a = 55}, а area(m,29) - {m=Africa}. Запрос area(m,a) выдаст любую из шести возможных пар, но, добавляя ограничения, мы можем сузить область допустимых результатов. Возможные ответы на area(m,a),a>20 - {m=Eurasia,a=55}и {m=Africa, a=29}, а на area(m,a),a>20,a<40 получим единственно возможный ответ: {m=Africa, a=29}. Этот по выражению Хоара "ангельский индетерминизм" и составляет главную силу логического программирования.

Предпринимаются попытки объединить эти два стиля. Один из подходов - "функционально-логическое программирование", в котором отношения задаются функциями, но запросы выполняются как в логических языках. То есть допускаются обращения вида area(m) = 20 --> {m = NorthAmerica}.

Более тонкие различия проявляются в стратегии управления вычислениями. Так функциональные языки обычно делят на "ленивые" (откладывающие вычисление значения выражения, до тех пор, пока оно реально потребуется) и "энергичные". Для логических и особенно функционально-логических языков разнообразие шире. Еще больше вариантов возникает в случае параллельных вычислений.

Другая характеристика языка - используемая в нём система типов данных. Вообще, для декларативных языков характерен "декларативный" подход и к организации данных. То есть понятие структуры данных никак не связано с её представлением в памяти компьютера. Напрочь отсутствует такое понятие как указатель. Редко встречаются и массивы. Наиболее распространенные структуры - списки и деревья.

Некоторые языки полностью игнорируют понятие типа данных. Имена переменных в них не связываются по умолчанию с каким-либо типом - все объекты образуют единое универсальное пространство. Такие языки называют бестиповыми, а также "языками с динамической типизацией" или "языками со скрытыми типами". Наиболее радикальны в этом плане Лисп и Пролог. Формы представления программ и данных в них одинаковы - символьные выражения. Это позволяет программе обрабатывать и преобразовывать другие программы и даже саму себя.

Так или иначе, типы возникают естественно, даже в бестиповых языках, когда объекты классифицируются согласно их использованию. Но вот что лучше - считать типы существующими априори или организовывать подмножества объектов из единой области? Этот вопрос остаётся нерешённым, так как отражает (возможно, неразрешимое) противоречие между надежностью и гибкостью языка. Споры о необходимости контроля типов ведутся и сегодня, но практический успех языка часто определяет более или менее успешная попытка найти компромисс. В этом отношении система типов Хиндли-Милнера - один из наиболее интересных примеров. Её разновидности используются во многих функциональных языках.

Еще одно важное свойство языков - поддержка модульности. Ранние языки слабо развиты в этом отношении. Они имеют "плоское" пространство имён в духе Си. Наиболее развита система модулей у SML и OCAML, но многие считают её чересчур сложной. Возможно "золотую середину" представляют Haskell, Mercury и т.п., использующие простой модульный механизм в стиле Модулы-2. Для практических нужд этого вполне достаточно.