Парадигмы программирования

Отношение "потомок-предок" на классах принято называть наследованием.

Все эти свойства по отдельности встречаются и в других методологиях программирования. Так, локальные переменные инкапсулированы в процедуре. Объектно-ориентированное программирование достаточно гармонично их сочетает.

Синтаксис чистых объектно-ориентированных  языков описывает всего одну операцию: послать сообщение M объекту А с параметрами B₁..В_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.

2.) Понять, что множество  вычислимых функций X * Y -> Z очевидным образом взаимооднозначно отображается в множество вычислимых функций X -> (Y -> Z). Так, 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 являются переменными.

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

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

 

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

 

 

 

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

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

В логике теории задаются при  помощи аксиом и правил вывода. То же самое мы имеем и в Прологе. Аксиомы здесь принято называть фактами, а правила вывода ограничить по форме до так называемых "дизъюнктов Хорна" - утверждений вида A <= B₁& ...& B_n. В Прологе такие утверждения принято записывать так:

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).