Введение Императивное программирование Параллелизм. Параллельное и событийно-управляемое программирование Объектно-ориентированное программирование Функциональное программирование Логическое программирование Программирование в ограничениях Заключение
Эта статья должна показать, что "парадигмы разные нужны, парадигмы разные важны". Все они - всего лишь различные инструменты, которые можно использовать при программировании. Каждый из этих инструментов по-своему хорош. Все описанные в статье модели вычислений эквивалентны. Но это не значит, что они "эффективно универсальны". То есть, на самом деле, различные методики программирования дают разный выигрыш для решения задач разных классов. Этот выигрыш можно мерять по двум параметрам:
Так как современные компьютеры (персональные, как наиболее широко распространенные и, как ни странно, наиболее востребованные широким пользователем) практически все построены по принципам, заложенным еще Фон Нейманом в середине нашего века. То есть, есть процессор, есть память, есть внешние устройства, и все это работает под управлением последовательной выборки команд из памяти.
Читатель, сведущий в архитектурах ЭВМ, знает, что компьютеры, на самом деле, не далеко ушли по своему внутреннему устройству от гипотетических последовательных вычислительных моделей, использовавшихся в начале века пионерами исследования алгоритмов для доказательств базовых утверждений современной теории вычислимости. В самом деле, процессор - это система (да, очень большая) логических элементов. То есть, процессор - схема булевых элементов, реализующая функцию переходов некоторого автомата (почему некоторого? сам компьютер и есть этот автомат) на множестве состояний (вся память какая есть и будет этим самым состоянием). Поэтому современные компьютеры практически все ориентированы на последовательные вычисления. Со всеми замечаниями относительно разных уровней параллелизма согласен, но об этом будет отдельный разговор дальше. Следовательно, парадигмой, имеющей наиболее "естественную" реализацию семантики на нынешних компьютерах, является императивное программирование. Оно заведомо выигрывает любой другой методологии в эффективности реализации. Хорошие трансляторы, например, с чистых объектно-ориентированных языков - вещь достаточно редкая. По изложенным выше причинам не стоит осуждать отдельные парадигмы исключительно руководствуясь аргументом: "мала эффективность готовой программы", забывая о том, что практически все сложные программы работают не так быстро и требуют больших объемов памяти.
В следующих частях будут подробно рассмотрены отдельные методологии программирования. Это потребует описания традиционного синтаксиса некоторого языка программирования, поддерживающего эту методологию (да, между Паскалем и Си очень много разницы; в одном надо писать begin...end, а в другом {...}, и так далее). Будут описаны традиционные средства структурирования программ, принятые в этих языках. Естественно, будет рассказано о типичной семантике таких языков. И, что наиболее важно, будет рассмотрен класс задач, для которого эти методологии дают достаточно эффективные решения.
Практически любой язык программирования в наши дни - это язык определений. Программы представляют из себя множество определений программных объектов (типов данных, функций, ...), которые как-то взаимосвязаны. Методологии программирования, как правило, фокусируются на описании алгоритмической части определений, входящих в программу. Методология для работы с описательной частью всего одна: программа должна быть максимально структурирована. Это помогает переиспользовать единожды написанный код, да и просто облегчает понимание текста программы. Это знали и в середине ХХ века (когда уже по-программировали всласть), это знают и сейчас. Структурированность программы позволяет повысить уровень декларативности (то есть, еще сильнее оторваться от деталей архитектуры конкретного компьютера и программировать практически в терминах предметной области задачи) даже для программирования на языке ассемблера процессора Intel. В алгоритмической же части многие современные языки на самом деле поддерживают в явном виде несколько парадигм программирования.
Для описания синтаксиса будут использованы грамматики в расширенной форме Бекуса-Науэра. В правой части таких грамматик допускается использование следующих "регулярных операций":
A B - последовательно А, за тем В. A | B - альтернатива. Читается: "A или B". A* - произвольное количество повторений (в том числе - 0 раз) А. Читается: "последовательность А". A # B - эквивалентно A ( B A )*. Читается: "последовательность А через В".
Терминальные символы выделяются подчеркиванием.
Про императивное программирование мы уже практически все сказали. Автомат, последовательно изменяющий свои состояния под управлением некоторой схемы, наиболее просто реализуется технически. Поэтому первые компьютеры были императивными. И остались такими и в наши дни, несмотря на все эксперименты с оригинальными вычислительными устройствами. Даже типичное определение алгоритма, вдалбливаемое еще со школы (описание последовательности действий для решения какой-либо задачи), несет на себе сильнейший отпечаток императивного подхода. Стоит ли говорить о том, почему императивное программирование - практически наиболее "популярное"?
Одна из характерных черт императивного программирования - наличие переменных с операцией "разрушающего присвоения". То есть, была переменная А, было у нее значение Х. Алгоритм предписывает на очередном шаге присвоить переменной А значение Y. То значение, которое было у А, будет "навсегда забыто". Вот что на практике означает "переход между состояниями под управлением функции переходов".
Синтаксис описания алгоритмов в простейшем языке, поддерживающем императивную модель программирования, мог бы быть таким:
Оператор ::= Простой оператор | Структурный оператор Простой оператор ::= Оператор присваивания | Оператор вызова | Оператор возврата Структурный оператор ::= Оператор последовательного исполнения | Оператор ветвления | Оператор цикла Оператор присванивания ::= Переменная := Выражение ; Оператор вызова ::= Имя подпрограммы ( Список параметров ) ; Оператор возврата ::= return [ Выражение ] ; Оператор последовательного исполнения ::= begin Оператор* end Оператор ветвления ::= if Выражение then Оператор* (elseif Выражение then Оператор*)* [ else Оператор* ] end Оператор цикла ::= while Выражение do Оператор* end
Семантика такого языка описывается достаточно легко. Состоянием вычислительного устройства будут указатель текущей инструкции, значения всех используемых программой ячеек памяти, и состояние стека возвратов из подпрограмм. Исполнение каждого оператора тривиальным образом записывается как изменение этого "состояния вычислителя" (если считать, что алгоритм представлен в виде дерева вывода в указанной грамматике, то с описанием переходов не должно возникнуть никаких проблем).
Про наш мир можно сказать, что он локально императивен. То есть, если взять достаточно узкую задачу, то ее можно вполне легко описать методами последовательного программирования. Практика показывает, что более сложные императивные программы (компиляторы, например) пишутся и отлаживаются долго (годами). Переиспользование кода и создание предметно-ориентированных библиотек упрощает программирование, но ошибки в реализации сложных алгоритмов проявляются очень часто.
Императивное программирование наиболее пригодно для реализации небольших подзадач, где очень важна скорость исполнения на современных компьютерах. Кроме этого, работа с внешними устройствами, как правило, описывается в терминах последоательного исполнения операций ("открыть кран, набрать воды"), что делает такие задачи идеальными кандидатами на императивную реализацию.
Исторически сложилась такая ситуация, что компьютеры изначально использовались для решения больших вычислительных задач, которые были просто "неподъемны" для человека. Для таких задач характерно, что приходится проделывать практически те же вычисления для каждого элемента очень большого массива данных. Постепенно многие крупные организации осознали пользу компьютеров как средств централизованного хранения и обработки своих "картотек" (из которых и выросли современные базы данных). Оказалось, что и в задачах, связанных с систематизацией такой информации, оказывается много общего с численными методами математической физики, в терминах алгоритмической реализации.
Достаточно быстро были разработаны супер-ЭВМ, имеющие "векторную" или "матричную" архитектуру. Такие ЭВМ представляют, на самом деле, несколько процессоров, достаточно автономных, но способных обмениваться между собой информацией о результатах своих вычислений. Достаточно хорошим приближением к таким архитектурам являются сети компьютеров с возможностью распределенных вычислений. Кроме этого, практически все современные микропроцессоры максимально используют в своей архитектуре возможности параллельного исполнения отдельных операций. Таким образом, параллелизм можно мысленно разбить на два уровня: параллелизм уровня микроопераций и параллелизм уровня процессов.
Процессы - это абстракция достаточно высокого уровня. В какой вычислительной модели работает каждый отдельный процесс - не принципиально. Важно, что они могут работать параллельно, и могут обмениваться между собой результатами своих вычислений через "каналы связи". Примерно такую модель взаимодействия процессов реализует язык параллельного программирвоания Occam. Вот некотороая грамматика описания процессов, достаточно близкая к принятой в Occam-е:
Процесс ::= Простой процесс | Структурный процесс Простой процесс ::= Послать значение | Принять значение | Процесс вычислительной модели Структурный процесс ::= Последовательный процесс | Параллельный процесс Послать значение ::= Канал связи << Выражение ; Принять значение ::= Канал связи >> Выражение ; Процесс вычислительной модели ::= нечто, определяемое конкретным вычислителем Последовательный процесс ::= seq Процесс* end Параллельный поцесс ::= par Процесс* end
Семантически взаимодействие параллельных процессов лучше всего представлять как работу сети неких устройств, соединенных "проводками", по которым текут данные. Спроектировав в таких терминах, например, систему параллельных процессов для быстрого суммирования большого количества чисел, можно легко описать эту систему в приведенном синтаксисе.
Каждый вычислитель производит типичные для его вычислительной модели операции (например, императивный вычислитель будет переходить из состояния в состояние). Когда процесс встречает инструкцию "Принять значение (из канала)", он входит в состояние ожидания, пока канал пуст. Как только в канале появляется значение, процесс его считывает и продолжает работу.
Достаточно распространенной является так же и следующее понимание параллелизма: в системе параллельных процессов каждый отдельный процесс обрабатывает события. События могут быть как общими для всей системы, так и индивидуальными для одного или нескольких процессов. В таких терминах достаточно удобно описывать, например, элементы графического интерфейса пользователя, или моделирование каких-либо реальных процессов (например, управление уличным движением) - так как понятие события является для таких задач естественным. Такое программирование принято называть событийно-управляемым. В событийно-управляемом программировании отдельные процессы максимально автономны, единственное средство общения между ними - посылка сообщений (порождение новых событий). Событийно-управляемое программирование очень близко к объектно-ориентированному прграммированию, которое будет подробно разобрано в дальнейшем.
Параллелизм является не только надстройкой над другими вычислительными моделями; некоторые методологии программирования имеют естественную реализацию на платформах, поддерживающих параллелизм. Об этом будет упомянуто отдельно в каждом таком случае.
Объектно-ориентированное программирование появилось на свет божий из недр событийно-управляемого программирования и практически затмило его своим светом, так как оказалось значительно более мощным и универсальным средством программирования и проектирования.
В чистом объектно-ориентированном программировании все, что можно - процессы, данные, события - являются объектами. Все объекты располагают некоторыми "собственными" данными, представленными как ссылки на другие объекты. Объекты могут обмениваться между собой сообщениями. При получении объектом сообщения запускается соответствующий ему обработчик, иначе называемый методом. У объекта есть ассоциативный контейнер, который позволяет получить по сообщению его метод для его обработки. Кроме этого, у объекта есть объект-предок. Если метод для обработки сообщения не найден, сообщение будет перенаправлено объекту-предку. Эту структуру в целом (таблица обработчиков + предки) из соображений эффективности выделяют в отдельный объект, называемый классом данного объекта. У самого объекта будет ссылка на объект, представляющий его класс. Объект по отношению к сковему классу является экземляром. Так как классы тоже представлены, как объекты, существует класс, определяющий поведение, общее для всех классов. Такой класс принято называть метаклассом.
Важно выделить следующие основные свойства объектов:
1.) Так как один объект может воздействовать на другой исключительно при помощи посылки последнему сообщений, он не может как-либо непосредственно работать с собственными данными "собеседника", и, следовательно, не может нарушить их внутреннюю согласованность. Это свойство (сокрытие данных) принято называть инкапсуляцией.
2.) Так как объекты взаимодействуют исключительно засчет обмена сообщениями, объекты-собеседники могут ничего не знать о реализации обработчиков сообщений у своего визави. Взаимодействие происходит исключительно в терминах сообщений/событий, которые достаточно легко привязать к предметной области. Это свойство (описание взаимодействия исключительно в терминах предметной области) называют абстракцией.
3.) Объекты взаимодействуют исключительно через посылку сообщений друг другу. Поэтому если в каком-либо сценарии взаимодействия объектов заменить произвольный объект другим, способным обрабатывать те же сообщения, сценарий так же будет реализуем. Это свойство (возможность подмены объекта другим объектом со сходной структурой класса) называется полиморфизмом.
Отношение "потомок-предок" на классах принято называть наследованием.
Все эти свойства по-отдельности встречаются и в других методологиях программирования. Так, локальные переменные инкапсулированы в процедуре. Объектно-ориентированное программирование достаточно гармонично их сочетает.
Синтаксис чистых объектно-ориентированных языков описывает всего одну операцию: послать сообщение M объекту А с параметрами B1..Вn. Параметры сообщения - это объекты, которые сами могут быть результатами обработки других сообщений. Часто операцию "вернуть объект-результат" так же вводят в явном виде, хотя ее достаточно легко реализовать как посылку сообщения системному объекту "стек возвращаемых значений".
Если в чистом объектно-ориентированном языке нужно создать новый класс - требуется послать классу-предку сообщение: "породить наследника" ( sublcass ). Существует класс, являющийся вершиной всей иерархии наследования (как правило, наываемый Object), так что предок будет у всех классов, даже явно его не имеющих. Для описания обработки сообщения нужно послать классу, в котором задается обработчик, сообщение: "установить новый обработчик сообщения" ( answer ).
Пример описания класса "точка" в некотором абстрактном объектно-ориентированном языке (напоминающем SmallTalk или Common LISP Object System = CLOS):
Object <- subclass(Point, (X, Y)), Point <- answer( isnew, (Init_X, Init_Y), ( Integer <- new(X, Init_X), Integer <- new(Y, Init_Y) )), Point <- answer( move, (Delta_X, Delta_Y), ( X <- add(Delta_X), Y <- add(Delta_Y) )) ...
Если мы в дальнейшем хотим использовать класс Point, например, порождая его объекты и как-то с ними работая, мы можем написать нечто вроде:
Point <- new(A, (0, 0)), A <- move(+2, -2) ...
В наши дни объектно-ориентированное программирование активно используется как средство поректирования сложных систем и моделирования, например, в языке UML.
До сих пор рассматриваемые нами парадигмы программирования воспринимались нами как некоторые "полезные надстройки над императивным программированием". Уже отмечалось, например, что параллельное программирование - это программирование в терминах взаимодействия некоторых одновременно работающих абстрактных вычислителей, и почти ничего не говорили о вычислительной модели, на которой основаны отдельные элементы этой системы. Мы ничего не сказали о том, на каком языке описаны обработчики сообщений у объектов (кроме того, что в этих языках основной операцией является посылка сообщения). Функциональное программирование представляет из себя одну из альтернатив императивному подходу.
В императивном программировании алгоритмы - это описания последовательно исполняемых операций. Здесь существует понятие "текущего шага исполнения" (то есть, времени), и "текущего состояния", которое меняется с течением этого времени.
В функциональном программировании понятие времени отсутствует. Программы являются выражениями, исполнение программ заключается в вычислении этих выражений. Практически все математики, сами того не замечая, занимаются функциональным программированием, описывая, например, чему равно абсолютное значение произвольного вещественного числа.
Императивное программирование основано на машине Тьюринга-Поста - абстрактном вычислительном устройстве, предложенном на заре алгоритмической эры для описания алгоритмов. Функциональное программирование основано на более естественном с математической точки зрения формализме - лямбда-исчислении Черча.
Как правило, рассматривают так называемое "расширенное лямбда-исчисление". Его грамматику можно описать следующим образом (жаль, что не в любой локализации есть символ "лямбда"):
Выражение ::= Простое выражение | Составное выражение Простое выражение ::= Константа | Имя Составное выражение ::= Лямбда-абстракция | Применение | Квалифицирванное выражение | Ветвление Лямбда-абстракция ::= lambda Имя -> Выражение end Применение ::= ( Выражение Выражение ) Квалифицированное выражение ::= let ( Имя = Выражение ; )* in Выражение end Ветвление ::= if Выражение then Выражение (elseif Выражение then Выражение)* else Выражение end
Константами в расширенном лямбда-исчислении могут быть числа, кортежи, списки, имена предопределенных функций, и так далее.
Результатом вычисление применения предопределенной функции к аргументам будет значение предопределенной функции в этой "точке". Результатом применения лямбда-абстракции к аргументу будет подстановка аргумента в выражение - "тело" лямбда-абстракции. Сами лямбда-абстракции так же являются выражениями, и, следовательно, могут быть аргументами.
Вы уже заметили, что лямбда-абстракции имеют всего один аргумент. В то же время, функции в традиционном понимании не обязаны быть одноместными. Представления функций от нескольких аргументов можно достичь двумя способами:
1.) Считать, что аргумент является кортежем. Например, apply = lambda (f, x) -> ( f x ) end можно понимать как apply = lambda y -> ( ( first y ) ( second y ) ) end.
apply = lambda (f, x) -> ( f x ) end
apply = lambda y -> ( ( first y ) ( second y ) ) end
2.) Понять, что множество вычислимых функций X * Y -> Z очевидным образом взаимнооднозначно отображается в множество вычислимых функций X -> (Y -> Z). Так, apply = lambda f -> lambda x -> (f x) end end.
apply = lambda f -> lambda x -> (f x) end end
Когда нам надоест ставить скобки вокруг применения функций к аргументам, мы можем объявить операцию применения функции (которую мы при записи опускаем, так же, как в математике принято не писать явно символ умножения) левоассоциативной, то есть, понимать запись вида f x y как ((f x) y). Это - традиционное соглашение, поэтому никаких "стандартов" мы при этом не нарушаем.
Чистое лямбда-исчисление Черча позволяет обходится исключительно именами, лямбда-абстракциями от одного аргумента и применениями выражений к выражениям. Оказывается, в этих терминах можно описать и "предопределенные" константы (числа и т.п.), структуры данных (списки, кортежи...), логические значения и ветвление. Более того, в чистом лямбда-исчислении можно обойтись без квалифицированных выражений, и, следовательно, выразить рекурсию, не используя для этого употребления имени функции в теле функции. Некоторые экспериментальные модели функционального программирования позволяют обходится без каких-либо имен вообще. Подробнее об этом можно почитать в специальной литературе, например, в книге Филда и Харрисона "Функциональное программирование".
Функциональное программирование обладает следующими двумя примечательными свойствами:
1.) Аппликативность: программа есть выражение, составленное из применения функций к аргументам.
2.) Настраиваемость: так как не только программа, но и любой программный объект (в идеале) является выражением, можно легко порождать новые программные объекты по образцу, как значения соответствующих выражений (применение порождающей функции к параметрам образца).
Настраиваемость активно используется в таком направлении программирования, как generic programming. Основная задача, решаемая в рамках это направления - создание максимально универсальных библиотек, ориентированных на решение часто встречающихся подзадач (обработка агрегатных данных; потоковый ввод-вывод; взаимодействие между программами, написанными на разных языках и различающихся в деталях семантики; универсальные оконные библиотеки). Эти направления наиболее ярко представлены в STL - стандартной библиотеке шаблонов (контейнеров) языка Си++, а так же - в реализации платформы .NET фирмы MicroSoft. Нередко в разговорах о пользе функционального программирования можно услышать следующее утверждение: "самые крупные специалисты по функциональному языку Haskell в настоящее время находятся в MicroSoft Research".
Для обеспечения видовой корректности программ в функциональные языки вводят специальные системы типов, ориентированные на поддержку настраиваемости. Как правило, трансляторы функциональных языков могут самостоятельно определять типы выражений, без каких-либо описаний типов вообще. Так, функция add = lambda x -> lambda y -> x+y end end будет иметь тип number -> number -> number, а уже рассматриваемая нами функция apply - тип any(X).any(Y).(X->Y)->X->Y, где any обозначает "квантор всеобщности" для типов, а X и Y являются переменными.
add = lambda x -> lambda y -> x+y end end
number -> number -> number
any(X).any(Y).(X->Y)->X->Y
Можно заметить, что так как порядок вычисления подвыражений не имеет значения (благо "состояния" у функциональной программы нет), функциональное программирвание может быть естественным образом реализовано на платформах, поддерживающих параллелизм. "Потоковая модель" функционального программирования, о которой так же можно почитать у Филда и Харрисона, является естественным представлением функиональных программ в терминах систем взаимодействующих процессов.
Функциональное программирование, как и другие модели "неимперативного" программирования, обычно применяется для решения задач, которые трудно сформулировать в терминах последовательных операций. Практически все задачи, связанные с искусственным интеллектом, попадают в эту категорию. Среди них следует отметить задачи распознавания образов, общение с пользователем на естественном языке, реализацию экспертных систем, автоматизированное доказательство теорем, символьные вычисления. Эти задачи далеки от традиционного прикладного программирования, поэтому им уделяется не так много внимания в учебных программах по информатике.
В функциональном программировании программы - это выражения, и их исполнение заключается в вычислении их значения. В логическом программировании программа представляет из себя некоторую теорию (описанную на достаточно ограниченном языке), и утверждение, которое нужно доказать. В доказательстве этого утверждения и будет заключаться исполнение программы.
Логическое программирование и язык Пролог появились в результате исследования группы французских ученых под руководством Колмерье в области анализа естественных языков. В последствии было обнаружено, что логическое программирование столь же эффективно в реализации других задач искусственного интеллекта, для чего оно в настоящий момент, главным образом, и используется. Но логическое программирование оказывается удобным и для реализации других сложных задач; например, диспетчерская система лондонского аэропорта Хитроу в настоящий момент переписывается на Прологе. Оказывается, логическое программирование является достаточно выразительным средством для описания сложных систем.
В логике теории задаются при помощи аксиом и правил вывода. То же самое мы имеем и в Прологе. Аксиомы здесь принято называть фактами, а правила вывода ограничить по форме до так называемых "дизъюнктов Хорна" - утверждений вида A <= B1& ...& Bn. В Прологе такие утверждения принято записывать так:
a :- b1, ..., bn.
а факты, они же аксиомы, представлять как правила с пустой "посылкой":
a.
Переменные в утверждениях Пролога принято обозначать идентификаторами, начинающимися с заглавной буквы.
Пример простейшей программы на Прологе:
member(X, [X|_]). member(X, [_|T]) :- member(X, T).
Эту программу можно прочитать так: "Х является членом списка, если он совпадает с головой списка, или является членом хвоста списка". В этой программе объявлен один предикат - member.
Как вы заметили, это - только набор аксиом и правил. Обычно Пролог-система работает в форме диалога с пользователем. Утверждение, которое требуется доказать, вводится с клавиатуры. Компилирующие версии трансляторов Пролога могут располагать специальными синтаксическими средствами для задания утверждений, которые требуется доказать. Такие утверждения в Прологе принято называть целями.
Зададим Пролог-системе простейший вопрос: является ли 2 членом списка [1,2,3]? Для этого введем:
?- member(2, [1,2,3]).
Пролог-система сначала попытается применить первое правило для предиката member, сравнивая 2 с головой списка [1,2,3]. Это сравнение даст неуспех, в результате чего система продолжит вывод по второму правилу, рекурсивно вызывающему предикат member, с аргументами 2 и [2,3]. В этом рекурсивном вызове сработает первое правило (так как 2 совпадает с головой списка [2,3]), и Пролог-система выдаст нечто вроде:
yes ->
Так как произвольная цель может быть доказана не единственным образом, система предлагает нам решить, пытаться ли доказать это утверждение по-другому. Ответим "да" (тем способом, как это предусмотрено в используемой Пролог-системе). Осталось незадействованным второе правило для предиката member для аргументов 2, [2,3], по которому следует пытаться доказать, что 2 есть член списка [3]. Так как 2 =/= 3, первое правило для этой цели не сработает, и доказательство пойдет дальше по второму правилу, которое предписывает доказывать утверждение member(2, []). Так у для пустых списков нет головы и хвоста, ни одно из правил для предиката member не применимо, и Пролог-система выдаст ответ:
no.
Мы могли бы задать Пролог-системе и более "интересные" вопросы - например, "для какого Х верно, что он является членом списка [1,2,3]?":
?- member(X, [1,2,3]).
Пролог-система последовательно выдаст нам варианты:
X=1 -> X=2 -> X=3 -> no.
Можно задать и еще более "интересный" вопрос: "для какого Х верно, что 1 является членом списка Х?":
?- member(1, X). X = [1|_] -> X = [_, 1|_] -> X = [_, _, 1|_] -> ...
Таких списков, очевидно, бесконечно много. Рано или поздно нам надоест созерцать порождаемые Пролог-системой списки, содержащие 1, и мы скажем "нет" на очередной запрос о продолжении доказательства. Пролог-система выдаст нам долгожданное "no." и закончит доказательство утверждения member(1, X).
Сведущие в автоматизированном доказательстве теорем люди скажут, что Пролог-система использует для доказательства утверждений "унификацию и метод резолюций". Унификация - это сопоставление двух произвольных термов, содержащих переменные, с целью определения того, можно ли присвоить этим переменным такие значения, чтобы получились два одинаковых терма. Например, унификация термов f(X, 2) и f(1, Y), где X, Y - переменные, выдаст подстановку: X=1, Y=2. Унификация термов f(X) и Х пройдет безуспешно. Метод резолюций заключается в последовательном доказательстве отдельных утверждений, входящих в посылку дизъюнкта Хорна, для доказательства его следствия. То есть, применение метода резолюций к правилу a :- b, c. и утверждению a приведет к последовательному доказательству утверждений b и c. Метод резолюций имеет прямой аналог в обычной логике высказываний - правило modus ponens, по которому (A & A=>B) => B.
Логическое программирование допускает естественную параллельную реализацию. В примере a :- b, c. порядок согласования целей b и c не имеет значения, поэтому их можно доказывать параллельно. Говорят, что процессы доказательства b и с образуют И-систему процессов: И-система успешно доказывается, если каждый процесс, входящий в систему, успешен. В примере с предикатом member два правила для него могли применяться параллельно, образуя ИЛИ-систему процессов. ИЛИ-система успешно доказывается, если хотя бы 1 процесс в системе успешен. Переменные, общие для системы процессов(например, в случае a(X) :- b(X), c(Х).) преобразуются в каналы связи между процессами в системе. Связывание переменной (присвоение ей значения) аналогично посылке значения в канал.
В настоящее время существует несколько "промышленных" реализаций языка Пролог (наряду с большим количеством "исследовательских" версий). "Промышленный" транслятор Пролога, как правило, порождает исполняемый код, сопоставимый по эффективности с кодом аналогичной программы на императивных языках; компилируемое им подмножество "чистого Пролога" наделено строгой системой типов и возможностью вызывать процедуры, написанные на других языках (Си, Паскаль, Ассемблер...).
Среди экспериментальных расширений Пролога следует упомянуть такие языки, как лямбда-Пролог (Пролог с элементами функционального программирования), Goedel (язык, в котором семантический анализ может быть описан алгоритмически средствами самого языка), Mercury (версия чистого Пролога, предназначенная для промышленного использования и снабженная системой полиморфных типов, аналогичной используемой в современных функциональных языках).
Программирование в ограничениях (constraint programming)- достаточно новое направление в декларативном программировании. Появилось оно во многом в результате развития систем символьных вычислений, искусственного интеллекта и исследования операций.
Программирвание в ограничениях - это программирование в терминах "постановок задач".
Постановка задачи - это конечный набор переменных V = {v[1], ..., v[n]}, соответствующих им конечных (перечислимых) множеств значений D = {D[1], ...,D[n]}, и набор ограничений С = {C[1],...,C[m]}. Ограничения представлены как утверждения, в которые входят в качетсве "параметров" переменные из некоторого подмножества V[j],j=1..m набора V. Решение такой задачи - набор значений переменных, удовлетворяющий всем ограничениям C[j].
Синтаксически такую постановку задачи пожно записать как "правило" для "типизированного" Пролога:
problem(V1:D1, ..., Vn:Dn) :- С1, ... Cm.
Семантически, однако, программирование в ограничениях отличается от традиционного логического программирования в первую очередь тем, что исполнение программы рассматривается не как доказательство утверждения, а нахождение значений переменных. При этом порядок "удовлетворения" отдельных ограничений не имеет значения, и система программирования в ограничениях, как правило, стремится оптимизировать порядок "доказательства" утверждений с целью минимизации отката в случае неуспеха.С этой целью набор ограничений может быть соответствующим образом преобразован - по правилам, аналогичным правилам Пролога. Любую задачу можно рассматривать как ограничение: "значения переменных должны быть решением этой задачи". Часто о программировании в ограничениях говорят исключительно как о "дополнительной" ветви логического программирования.
В качестве примера, мы можем задать системе программирования в ограничениях следующий запрос:
? (X : integer) X>1, member(X, [1,2,3]).
Типичная Пролог-система на таком запросе выдаст ошибку: Х является неинициализированной переменной, и его нельзя сравнивать с числом 1. Система, поддерживающая программирование в ограничениях, воспримет эти "утверждения" как ограничения (а не как цели, которые требуется доказать), и выдаст нам требуемые решения: Х=2 и Х=3.
Это может быть реализовано, например, следующим образом: при "прологовском" доказательстве утверждения Х>1 будет выведено ограничение на переменную Х (естественно, Х>1). Результаты доказательства следующей подцели (member(...)) будут проверяться на удовлетворение этому ограничению (фактически, будет передоказываться утверждение X>1 для конкретных значений Х). Первый вариант (Х=1) не пройдет эту проверку, остальные будут приняты как удовлетворяющие выведенному ограничению.
Задачу в ограничениях можно рассматривать и как задачу о минимальном необходимом наборе ограничений, что позволяет в некоторых случаях описать в явном виде бесконечные множества решений. Так, минимальным необходимым набором ограничений для задачи X:integer, X>2, X<4 будет Х=3; для задачи X,Y:integer, X*2=Y таким набором будет X:integer, Y mod 2 = 0.
X:integer, X>2, X<4
X,Y:integer, X*2=Y
Системы символьных вычислений нередко позволяют использовать "допущения" - по сути, те же ограничения. И на следующий (простой) запрос:
assume X>0. when X+1<10 ?
выдавать ответ:
X in (0..9).
Как правило, такие системы могут доказывать достаточно нетривиальные матичематические утверждения, выводя "минимальными необходимыми ограничениями", и проверяя эти ограничения на совместность.
В задачах исследования операций и реализации искусственного интеллекта часто используется некоторое "пространство решений", сужением которого достигается необходимый результат. Такие "сужения" естественным образом представляются как ограничения.
Кроме этого, программирование в ограничениях естественным образом приложимо к задаче автоматического вывода типов: выведенные ограничения на переменные, соответствующие типам подвыражений, будут задавать "минимальный набор требований на типы". Так, удовлетворение ограничения type_correct("lambda x -> x+1") потребует выполнения набора ограничений {number(x.type_of)}, что, буквально, обозначает, что для того, чтобы прибавить к х единицу, х должно быть числом.
type_correct("lambda x -> x+1")
{number(x.type_of)}
Как и логическое программирование, программирование в ограничениях предполагает совершенно аналогичную "естественную" реализацию на параллельных платформах.
Читатель уже заметил, что парадигмы программирования можно сочетать. Так, о всех парадигмах "без состояния" было отмечено, что они допускают естественную параллельную реализацию. Аналогично, объекты как сущности, взаимодействующие между собой при помощи посылки сообщений, можно рассматривать как в контексте императивного, так и, например, логического программирования: вызов обработчика сообщения будет сводится к доказательству некоторого утверждения; или функционального программирования: вызов обработчика сообщения - вычисление некоторого выражения.
Каждая из рассмотренных парадигм интересна и сама по себе. Но наиболее "полезно" для практики использовать их в совокупности, что позволяют современные языки программирования (как например, Си++ по сути, позволяет использовать императивное, фунциональное (хотя бы на уровне аппликативности) и объектно-ориентированное программирование, а с расширением, обеспечивающим параллелизм - и параллельное).
На страницу автора