Geum.ru

Опорный конспект Форма ф со пгу 18. 2/05 Министерство образования и науки Республики Казахстан

Вид материалаКонспект

Содержание


1.3 Программирование на основе объектно-ориентированного подхода
1.4 Функциональное программирование
1.5 Логическая парадигма программирования
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   15

1.3 Программирование на основе объектно-ориентированного подхода



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

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

Важно выделить следующие основные свойства объектов:

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.

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



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

В императивном программировании алгоритмы - это описания последовательно исполняемых   операций. Здесь существует понятие "текущего шага исполнения" (то есть, времени), и "текущего состояния", которое меняется с течением этого времени.

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

Императивное программирование основано на машине Тьюринга-Поста - абстрактном вычислительном устройстве, предложенном на заре алгоритмической эры для описания алгоритмов. Функциональное программирование основано на более естественном с математической точки зрения формализме - лямбда-исчислении Черча.

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

Выражение ::= Простое выражение | Составное выражение
Простое выражение ::= Константа | Имя
Составное выражение ::= Лямбда-абстракция | Применение | Квалифицирванное выражение | Ветвление
Лямбда-абстракция ::=  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 являются переменными.

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

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

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



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

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

В логике теории задаются при помощи аксиом и правил вывода. То же самое мы имеем и в Прологе. Аксиомы здесь принято называть фактами, а правила вывода ограничить по форме до так называемых "дизъюнктов Хорна" - утверждений вида 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 (версия чистого Пролога, предназначенная для промышленного использования и снабженная системой полиморфных типов, аналогичной используемой в современных функциональных языках).