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

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

 

Программирование  в ограничениях

 

 

 

Программирование в ограничениях - достаточно новое направление в  декларативном программировании. Появилось  оно во многом в результате развития систем символьных вычислений, искусственного интеллекта и исследования операций. Программирование в ограничениях - это программирование в терминах "постановок задач". Постановка задачи - это конечный набор переменных 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.

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

assume X>0. 
when X+1<10 ?

выдавать ответ:

X in (0..9).

Как правило, такие системы  могут доказывать достаточно нетривиальные  матичематические утверждения, выводя "минимальными необходимыми ограничениями", и проверяя эти ограничения на совместность. В задачах исследования операций и реализации искусственного интеллекта часто используется некоторое "пространство решений", сужением которого достигается необходимый результат. Такие "сужения" естественным образом представляются как ограничения. Кроме этого, программирование в ограничениях естественным образом приложимо к задаче автоматического вывода типов: выведенные ограничения на переменные, соответствующие типам подвыражений, будут задавать "минимальный набор требований на типы". Так, удовлетворение ограничения type_correct("lambda x -> x+1") потребует выполнения набора ограничений{number(x.type_of)}, что, буквально, обозначает, что для того, чтобы прибавить к х единицу, х должно быть числом.

Как и логическое программирование, программирование в ограничениях предполагает совершенно аналогичную "естественную" реализацию на параллельных платформах.

 

Заключение

 

 

 

Можно заметить, что парадигмы программирования можно сочетать. Так, о всех парадигмах выше было отмечено, что они допускают естественную параллельную реализацию. Аналогично, объекты как сущности, взаимодействующие между собой при помощи посылки сообщений, можно рассматривать как в контексте императивного, так и, например, логического программирования: вызов обработчика сообщения будет сводиться к доказательству некоторого утверждения; или функционального программирования: вызов обработчика сообщения - вычисление некоторого выражения. Каждая из рассмотренных парадигм интересна и сама по себе. Но наиболее "полезно" для практики использовать их в совокупности, что позволяют современные языки программирования (как например, Си++ по сути, позволяет использовать императивное, фунциональное (хотя бы на уровне аппликативности) и объектно-ориентированное программирование, а с расширением, обеспечивающим параллелизм - и параллельное).

 

Список использованных источников

 

 

 

1.Мельник В.П. Информационные технологии. – М.: Академия, 2008. – 432c.

2.Хубавев Г.Н.. , Патрушина С.М. и др. Информатика: Учебное пособие для вузов. – Ростов н/Дону: Март, 2010. – 288с.

3. Черепашков А.А., Носов Н.В. Компьютерные технологии, моделирование и автоматизированные системы в машиностронии: Учебник для вузов.– Волгоград.: ИД”Ин-фолио”, 2009.– 640c/.

4.http://ru.wikipedia.org/