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

Зачем нужны определяющие методологии в программировании?
В чем заключается поддержка методологии методами и концепциями?
Каковы вычислительные модели методологий?
На какой класс практических задач ориентирована каждая из методологий?
Какова языковая поддержка методологий?
Каково происхождение методологий?

2.1. Основные методологии

Собрались однажды звери в лесу, чтобы строить мост через реку.
Когда все обсудили, медведь спрашивает: "Вопросы есть?"
Осел: "А как будем строить - вдоль или поперек реки?"
Анекдот о необходимости определяющих подходов

Хотя все племена нтернети исповедуют, в общем, единый культ, между ними идут
постоянные религиозные войны. Одна из самых затяжных связана с тем, какие палочки
использовать для добывания дыма. Одно племя пользуется мсайе, палочками
из древесины кокосовой пальмы, а другое - нтскейпами, из древесины банановой
пальмы. Что интересно - те и другие одинаково кривые, однако каждое племя
замечает лишь кривизну палочек противника.
Юрий Нестеренко

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

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

2.1.1. Атрибуты методологий

С каждой методологией можно связать некоторые характерные для нее атрибуты.

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

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

О парадигмах программирования
Когда методология применяется во время стадии программирования (реализации), очень часто ее называют парадигмой программирования- способом мышления и программирования, не связанным с конкретным языком программирования. Термин "парадигма" был впервые предложен Томасом Куном [Кун 1977]. Он определял парадигму как свод норм научного мышления. Парадигма - это правило (modus operand!) развития научного знания. Оно в течение определенного времени дает научному сообществу модель постановки проблем и их решений.

2.1.2. Ядра методологий

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

Ядра методологий определяются способом описания алгоритмов. Перечислим основные ядра методологии и посвятим следующие разделы их анализу:

методология императивного программирования (см. разд. 2.2.1);
методология объектно-ориентированного программирования (см. разд. 2.2.2);
методология функционального программирования (см. разд. 2.2.3);
методология логического программирования (см. разд. 2.2.4);
методология программирования в ограничениях (см. разд. 2.2.5).

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

2.1.3. Топологическая специфика методологий

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

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

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

2.1.4. Реализационная специфика методологий

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

Ядра методологий изначально продумывались для централизованных архитектур. Позже появились параллельные аппаратные реализации, к которым стали адаптировать уже существовавшие методологии. Приведем примеры параллельных методологий:

методология императивного параллельного программирования (см. разд. 2.4.1). Эту методологию обычно называют кратко- методология параллельного программирования;
методология логического параллельного программирования (см. разд. 2.4.2).

2.1.5. Смешанные методологии

Смешанные методологии включают объединение методов нескольких методологий. Наиболее часто объединяются методологии функционального и логического программирования. Существуют исследовательские работы в области объединения объектно-ориентированного и логического программирования (http://www.math.spbu.ru/user/tseytin/papers.html). Ряд исследований посвящен вопросам унификации методологий программирования [Hoare, Jifeng 1998].

2.1.6. Классы задач, поддерживаемых методологиями

Различные методологии программирования дают разный выигрыш для решения задач различных классов. Этот выигрыш можно оценивать по двум параметрам.

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

2.2. Ядра методологий

2.2.1. Методология императивного программирования

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

2.2.1.1. Происхождение, история и эволюция

Императивное программирование - это исторически первая поддерживаемая аппаратно методология программирования. Она ориентирована на классическую фон Неймановскую модель (см. разд. 6.2.1.1), остававшуюся долгое время единственной аппаратной архитектурой, получившей широкое практическое применение.

2.2.1.2. Методы и концепции

Метод изменения состояний - заключается в последовательном изменении состояний. Метод поддерживается концепцией алгоритма (см. разд. 1.7.3). Метод управления потоком исполнения - заключается в пошаговом контроле управления. Метод поддерживается концепцией потока исполнения.

2.2.1.3. Вычислительная модель

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

Языки, поддерживающие данную вычислительную модель, являются компактным средством описания функции переходов между состояниями вычислителя.

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

2.2.1.4. Синтаксис и семантика

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

О формальной системе обозначений
Для описания синтаксиса далее будет использована расширенная формальная система обозначений Бэкуса-Наура. В ней одни синтаксические категории определяются через другие последовательно. Метапеременные представляют собой слова или группы русских слов, заключенных в угловые скобки. Под значением метапеременной понимается некоторая конечная последовательность основных символов языка, из которых, в конечном счете, состоят программы. Символ : := означает "определяется как", символ | означает "или", символ * - "произвольное количество повторений (в том числе ноль раз) того символа, за которым он указан". Символы, указанные в квадратных скобках, являются необязательными.

Синтаксис описания алгоритмов в простейшем языке, поддерживающем императивную модель программирования, мог бы быть таким:

<оператор> ::= <простой оператор> | <структурный оператор>
<простой оператор> ::= <оператор присваивания> | <оператор вызова> | <оператор возврата>
<структурный оператор> ::= <оператор последовательного исполнения> | <оператор ветвления> | <оператор цикла>
<оператор присваивания> ::= <переменная> := <выражение>;
<оператор вызова> ::= <имя подпрограмма ( <список параметров>);
<оператор возврата> ::= return [ <выражение> ];
<оператор последовательного исполнения> ::= begin <оператор>* end
<оператор выбора> ::= if <выражение> then <оператор>* ( elseif
<выражение> then <оператор>*)* [ else <оператор>* ] end
<оператор цикла> ::= while <выражение> do <оператор>* end

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

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

Если в данной методологии требуется решить некоторую задачу для того, чтобы использовать ее результаты при решении следующей задачи, то типичный подход будет таким. Сначала исполняется алгоритм, решающий первую задачу. Результаты его работы сохраняются в специальном месте памяти, которое известно следующему алгоритму, и используются им.

2.2.1.5. Императивные языки программирования

Императивные языки программирования манипулируют данными в пошаговом режиме, используя последовательные инструкции и применяя их к разнообразным данным. Считается, что первым алгоритмическим языком программирования был язык Plankalkuel (от plan calculus), разработанный в 1945-1946 годах Конрадом Цузе (Konrad Zuse).

Наиболее известные и распространенные императивные языки программирования, большинство из которых было создано в конце 50-х - середине 70-х годов XX века, представлены на рис. 2.1. Обратим внимание на пустое место на рисунке, соответствующее 80-м и 90-м годам прошлого века. Это период увлечения новыми парадигмами, и императивных языков в это время практически не появлялось.

2.2.1.6. Класс задач

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

Вспомним, что первые задачи для компьютеров были рутинными вычислениями и представляли собой расчеты, связанные с созданием атомной бомбы.

2.2.1.7. Рекомендации по литературе

Особенности императивного программирования изложены в огромном количестве книг. Наиболее систематично они приведены в работе "Универсальные языки программирования. Семантический подход" [Калинин, Мацкевич 1991].

2.2.2. Методология объектно-ориентированного программирования

Странный неопознанный объект летает над Стокгольмом.
Астрид Линдгрен. "Малыш и Карлсон"

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

2.2.2.1. Происхождение, история и эволюция

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

2.2.2.2. Методы и концепции

Метод объектно-ориентированной декомпозиции - заключается в выделении объектов и связей между ними. Метод поддерживается концепциями инкапсуляции, наследования и полиморфизма.

Метод абстрактных типов данных - метод, лежащий в основе инкапсуляции. Метод поддерживается концепцией абстрагирования (см. разд. 4.3.2.3).

Метод пересылки сообщений - заключается в описании поведения системы в терминах обмена сообщениями между объектами. Метод поддерживается концепцией сообщения.

2.2.2.3. Вычислительная модель

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

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

2.2.2.4. Синтаксис и семантика

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

В объектно-ориентированном программировании определяют три основных свойства, перечисленные ниже.

Инкапсуляция. Это сокрытие информации и комбинирование данных и функций, которые аналогичны абстрактным типам данных.

О новом и старом
Итак, новое - это хорошо забытое старое. Абстрактный тип данных появился вновь через 25 лет после своего создания под названием объектно-ориентированный.

Наследование. Построение иерархии порожденных объектов с возможностью для каждого такого объекта, относящегося к иерархии, доступа к коду и данным всех порождающих объектов.

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

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

У каждого объекта есть ссылка на класс, к которому он относится. При приеме сообщения объект обращается к классу для обработки данного сообщения. Сообщение может быть передано вверх по иерархии наследования, если сам класс не располагает методом для его обработки. Если обработчик событий для сообщения выбирается динамически, то методы, реализующие обработчиков событий, принято называть виртуальными.

Пример описания класса "точка" в некотором абстрактном объектно- ориентированном языке выглядит так:

Object :subclass Point :fields { x, у };

Point :answer isnew :args { init_x, init_y } :body {

Integer :new x :value { init_x };

Integer :new у :value { init_y )

Point :answer getx :args {} :body { ^х };

Point :answer gety :args {} :body { ^у };

Point :answer setx :args {new_x} :body { x :set new_x };

Point :answer sety :args {new_y} :body ( у :set new_y };

Point :answer move :args {delta_x, delta_y} :body {

x :add delta_x

у :add delta_y

};

Если мы в дальнейшем хотим использовать класс Point, например, порождая его объекты и работая с ними, то мы можем написать следующий фрагмент:

Point :new A :value (0, 0};

A :move [+2, -2};

...

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

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

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

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

2.2.2.5. Объектно-ориентированные языки программирования

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

Чистые языки, в наиболее классическом виде поддерживающие объектно-ориентированную методологию. Такие языки содержат небольшую языковую часть и существенную библиотеку, а также набор средств поддержки времени исполнения.
Гибридные языки, которые появились в результате внедрения объектно-ориентированных конструкций в популярный императивный язык программирования .
Урезанные языки, которые появились в результате удаления из гибридных языков наиболее опасных и ненужных с объектно-ориентированной точки зрения конструкций.

2.2.2.6. Класс задач

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

2.2.2.7. Рекомендации по литературе

Одна из лучших книг по данной методологии - "Объектно-ориентированный анализ и проектирование с примерами приложений на C++" [Буч 1998]. Решения типичных задач объектно-ориентированного программирования удачно изложены в работе "Приемы объектно-ориентированного программирования. Паттерны проектирования" [Гамма, Хелм, Джонсон, Влиссидес 2001].

2.2.3. Методология функционального программирования

Нужно быть терпеливым, чтобы научиться терпению.
Ежи Леи.

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

2.2.3.1. Происхождение, история и эволюция

Функциональная методология является одной из старейших. По происхождению она тесно связана с лямбда-исчислением, изобретенным еще в начале 30-х годов XX века логиком Алонзо Черчем (Alonzo Church). Для многих функциональная методология стала ассоциироваться с языком Lisp, созданным Джоном Маккарти (John McCarthy) в конце 50-х годов XX века [Хювенен, Сеппянен 1986]. В то же время эта методология в основном используется теоретиками программирования и является средством лабораторных исследований искусственного интеллекта.

2.2.3.2. Методы и концепции

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

Метод рекурсивного поведения - заключается в самоповторяющемся поведении, возвращающемся к самому себе. Метод поддерживается концепцией рекурсии.

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

2.2.3.3. Вычислительная модель

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

В качестве математической модели функциональное программирование использует лямбда-исчисление Черча.

2.2.3.4. Синтаксис и семантика

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

Его грамматика может выглядеть следующим образом:

<выражение> ::= <простое выражение> | <составное выражение>
<простое выражение> ::= <константа> | <имя>
<составное выражение> ::= <лямбда-абстракция> | <применение> | <квалифицированное выражение> | <ветвление>
<лямбда-абстракция> ::= lambda <имя> -> <выражение> end
<применение> ::= (<выражение> <выражение>)
<квалифицированное выражение> ::= let (<имя> = <выражение>;)* in
<выражение> end
<ветвление> ::= if <выражение> then <выражение> (elseif <выражение> then
<выражение>)* else <выражение> end

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

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

В первом способе будем считать, что аргумент является кортежем. Например, apply = lambda (f, x) -> ( f x) end МОЖНО Понимать как apply = lambda у -> ( ( first у) ( second у)) end.
Второй способ исходит из того, что множество вычислимых функций х * у -> z очевидным образом взаимно однозначно отображается в множество ВЫЧИСЛИМЫХ функций X -> (У -> Z). Так, apply = lambda f -> lambda x -> (f x) end end.

О расстановке скобок
Вместо расстановки скобок вокруг применения функций к аргументам, можно объявить операцию применения функции (которую мы при записи опускаем, так же, как в математике принято не писать явно символ умножения) левоассоциативной. Будем понимать запись вида f x у как ((f х) у).

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

Для обеспечения видовой корректности программ в функциональные языки вводят специальные системы типов, ориентированные на поддержку настраиваемости. Как правило, трансляторы функциональных языков могут самостоятельно определять типы выражений, без каких-либо описаний типов вообще. Так, функция add = lambda x -> lambda у -> х+у end end будет иметь тип number -> number -> number, а уже рассматриваемая нами функция apply- тип any(X) .any(Y). (X->Y)->X->Y, где any обозначает "квантор всеобщности" для типов, а х и Y являются переменными.

Нередко существует возможность в качестве "списка параметров" для функции указать "образец", успешное сопоставление с которым определяет выражение, которое будет вычисляться (листинг 2.1).

Листинг 2.1. Пример программы на функциональном языке

let

map = fun

(f, [ ]) -> [];

(f, [head | tail]) -> [f(head) |map(f,tail)]

end fun;

square = fun

x -> multiply (x, x)

end fun

map(square, [1,2,3])

end let

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

2.2.3.5. Функциональные языки программирования

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

На рис. 2.3 представлены основные функциональные языки. Первый пик интереса к ним приходится на конец 70-х - начало 80-х годов XX века. Второй пик приходится на настоящее время, и он связан в первую очередь со стандартизацией наиболее мощного чистого функционального языка - Haskell.

Особенность ранних функциональных языков - в их динамической типизации. Типы формируются вместе с их значениями в ходе вычислений. За последние 15 лет функциональное программирование перестало быть исключительно исследовательским. Современные языки функционального программирования (ML, Haskell) - строго типизированные, компилирующиеся, предназначенные как для индивидуальной работы над программами, так и Для коллективной разработки.

2.2.3.6. Класс задач

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

2.2.3.7. Рекомендации по литературе

Методология функционального программирования подробно изложена в работах "Функциональное программирование" [Филд, Харрисон 1993] и "Функциональное программирование. Применение и реализация" [Хендерсон 1983]. В сети Интернет существует хорошее введение в функциональные языки Филиппа Уэдлера (Philip Wadler) (http://cm.bell-labs.com/cm/cs/who/wadler/guide.html).

2.2.4. Методология логического программирования

Я мыслю, следовательно, я существую.
Декарт (и Роденовский мыслитель)

Я не мыслю, следовательно, я не существую.
Г. Лихтенберг

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

2.2.4.1. Происхождение, история и эволюция

Логическое программирование начинает свой отсчет времени с конца 60-х годов XX века, когда Корделл Грин (Cordell Green) предложил использовать резолюцию как основу логического программирования. Алан Колмероэ (Alain Colmerauer) создал язык логического программирования Пролог в 1971 году. В основе логических языков лежит теория хорновских дизъюнктов. Логическое программирование пережило пик популярности в середине 80-х годов XX века, когда оно было положено в основу проекта разработки программного и аппаратного обеспечения вычислительных систем пятого поколения [Язык 1988].

2.2.4.2. Методы и концепции

Метод единообразного применения механизма логического доказательства ко всей программе.

Метод унификации - механизм сопоставления с образцом для создания и декомпозиции структур данных.

2.2.4.3. Вычислительная модель

Логическое программирование - это программирование в терминах фактов и правил вывода.

2.2.4.4. Синтаксис и семантика

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

а :- b1, ..., bn.

Факты (они же аксиомы) представляются как правила с пустой "посылкой":

а.

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

member(X, [Х|_]).

member(X, [_|T]) :-member(X, Т).

Эту программу можно прочитать так: "х является членом списка, если он совпадает с головой списка, или является членом хвоста списка". В этой программе объявлен один предикат - member.

Обычно Prolog-система работает в форме диалога с пользователем. Утверждение, которое требуется доказать, вводится с клавиатуры. Компилирующие версии трансляторов Пролог могут располагать специальными синтаксическими средствами для задания утверждений, которые требуется доказать. Такие утверждения в Прологе принято называть целями.

Зададим системе простейший вопрос: "Является ли 2 членом списка [1,2,3]?" Для этого введем:

?- member(2, [1,2,3]).

Prolog-система сначала попытается применить первое правило для предиката member, сравнивая 2 с головой списка [1,2,3]. Это сравнение не является Успешным. Система продолжит вывод по второму правилу, рекурсивно вызывающему предикат member, с аргументами 2 и [2,3]. В этом рекурсивном вызове можно применить первое правило (т. к. 2 совпадает с головой списка t2,3]), и тогда Prolog-система выдаст ответ:

yes ->

Так как произвольная цель может быть доказана не единственным образом, система предлагает нам решить, пытаться ли доказать это утверждение подругому. Ответим "да" тем способом, как это предусмотрено в используемой

Prolog-системе. Осталось незадействованным второе правило для предиката member для аргументов 2, [2,3], по которому следует пытаться доказать, что 2 есть член списка [3]. Так как 2 != 3, первое правило для этой цели не сработает, и доказательство пойдет дальше по второму правилу, которое предписывает доказывать утверждение member(2, []). Так как у пустых списков нет головы и хвоста, ни одно из правил для предиката member не применимо, и Prolog-система выдаст ответ:

no.

Мы могли бы задать Prolog-системе и более "интересные" вопросы - на-< пример, "для какого х верно, что он является членом списка [1,2,3]?": J

?- member(X, [1,2,3]).

Система последовательно выдаст нам варианты:

X=1 ->

Х=2 ->

Х=3 ->

по.

Можно задать и еще один "интересный" вопрос: "Для какого х верно, что 1 является членом списка х?":

?- member(1, X).

X = [1|_] ->

X = [_, 1|_] ->

X = [_, _, 1|_] ->

...

Таких списков, очевидно, бесконечно много. Рано или поздно нам надоест наблюдать порождаемые Prolog-системой списки, содержащие 1, и мы скажем "нет" на очередной запрос о продолжении доказательства. Система выдаст нам долгожданное "по." и закончит доказательство утверждения member(1, X).

Prolog-система использует метод унификации и метод резолюций для доказательства утверждений. Унификация - это сопоставление двух произвольных термов, содержащих переменные, с целью определения того, можно ли присвоить этим переменным такие значения, чтобы получились два одинаковых терма. Например, унификация термов f(x, 2) и f(i, У), где х, Y - переменные, выдаст подстановку: X=1, Y=2. Унификация термов f (X) их пройдет безуспешно. Метод резолюций заключается в последовательном доказательстве отдельных утверждений, входящих в посылку дизъюнкта Хорна, для доказательства его следствия. То есть, применение метода резолюций к правилу а :- b, c. и утверждению а приведет к последовательному доказательству утверждений b и с. Метод резолюций имеет прямой аналог в обычной логике высказываний - правило modus ponens, по которому

(А & А=>В) => В.

2.2.4.5. Логические языки программирования

Логические языки программирования содержат конструкции, позволяющие выполнить описание проблемы в терминах фактов и логических формул, а собственно решение проблемы выполняет система с помощью механизмов логического вывода. От языка программирования неотъемлем механизм конструктивного вывода целевого утверждения, основанный на строгих математических моделях. Язык Prolog является родоначальником семейства ему подобных языков (рис. 2.4), в котором можно выделить три ветви.

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

2.2.4.6. Класс задач

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

2.2.4.7. Рекомендации по литературе

Основные идеи методологии логического программирования изложены в сборнике статей "Логическое программирование" [Логическое 1988]. Элементы практического программирования на языке Prolog можно найти в книге [Бабаев, Герасимов, Косовский, Соловьев 1992].

2.2.5. Методология программирования в ограничениях

Чем дальше мы продвигались по Южным штатам, тем чаще сталкивались
со всякого рода ограничениями, устроенными для негров.
Илья Ильф, Евгений Петров. "Одноэтажная Америка"

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

2.2.5.1. Происхождение, история и эволюция

Методология возникла в начале 80-х годов XX века как перспективная область исследований на пересечении символьных вычислений, искусственного интеллекта, исследования операций и интервальной арифметики.

2.2.5.2. Методы и концепции

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

2.2.5.3. Вычислительная модель

Программирование в ограничениях - это программирование в терминах постановок задач.

2.2.5.4. Синтаксис и семантика

Постановка задачи - это конечный набор переменных V = {v[1], ..., v[n]}, соответствующих им конечных (перечислимых) множеств значений D = {D[1], ..., D[n]}, и набор ограничений C = {С[1], ..., C[m]}. Ограничения представлены как утверждения, в которые в качестве "параметров" входят переменные из некоторого подмножества v[j], j=l..m набора v. Решение такой задачи - набор значений переменных, удовлетворяющий всем ограничениям C[j].

Семантически исполнение программы рассматривается как нахождение значений переменных. При этом порядок удовлетворения отдельных ограничений не имеет значения, и система обычно стремится оптимизировать порядок нахождения значений с целью минимизировать откат в случае неуспеха. С этой целью набор ограничений может быть соответствующим образом преобразован - по правилам, аналогичным правилам языка Prolog. Любую задачу можно рассматривать как ограничение: "значения переменных должны быть решением этой задачи". В качестве примера, мы можем задать системе программирования в ограничениях следующий запрос:

? (X : integer) X>1, member(X, [1,2,3]).

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

Х=2 И Х=3.

Задачу в ограничениях можно рассматривать и как задачу о минимальном необходимом наборе ограничений, что позволяет в некоторых случаях описать в явном виде бесконечные множества решений. Так, минимальным необходимым набором ограничений для задачи х: integer, x>2, х<4 будет х=з. Для задачи X, У: integer, X*2=Y таким набором будет X: integer, Y mod 2 = 0.

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

assume X>0.

when X+K10 ?

системы могут выдать такой ответ:

х in (0..9).

Как правило, такие системы могут доказывать достаточно нетривиальные математические утверждения.

2.2.5.5. Языки программирования в ограничениях

Языки программирования в ограничениях позволяют в программе определить тип данных решения, предметную область решения и ограничения на значение искомого решения. Решение находится системой. Данные языки получили наибольшую известность в 80-х годах XX века (рис. 2.5).

Заметим, что зачаточным языком программирования в ограничениях может служить язык описания условий для утилиты "make".

Язык программирования УТОПИСТ (Универсальные Текстовые ОПИСания Терминов) предназначен для описания понятий и задач. Язык является базовым для инструментальной системы программирования ПРИЗ [Кахро, Калья, Тыугу 1988]. Язык имеет процедурную часть (поскольку при описании задачи иногда приходится описывать действия), но основная его выразительность достигается за счет описаний.

Приведем пример модели и постановки задачи на языке УТОПИСТ для вычисления некоторых значений на основе закона Ома (листинг 2.2).

Листинг 2.2. Пример программы на языке программирования в ограничениях

ПУСТЬ'

СХЕМА: (I1, I2, I3, U1, U2, U3, R1, R2, R3: ВЕЩ';

УРАВ' U1 = I1 * R1;

УРАВ' U2 = I2 * R2;

УРАВ' U3 = I3 * R3;

УРАВ' I1 + I2 + I3 = 0);

СХЕМА1: СХЕМА

R1 = 16, R2 = 32, R3 = 5,

U1 = 50, U2 = -28;

ДЕЙСТВИЯ'

НА' СХЕМА1 ВЫЧИСЛИТЬ' U3;

2.2.5.6. Класс задач

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

2.2.5.7. Рекомендации по литературе

Представление о ранних работах в этой области можно получить из книги "Инструментальная система программирования ЕС ЭВМ (ПРИЗ)" [Кахро, Калья, Тыугу 1988]. Современное видение программирования в ограничениях изложено у Романа Бартака (Roman Bartak) (http://kti.mff.cuni.cz/~bartak/constraints/).

2.3. Топологическая специфика методологий

2.3.1. Методология структурного императивного программирования

Методология структурного императивного программирования - подход, заключающийся в задании хорошей топологии императивных программ, в том числе отказе от использования глобальных данных и оператора безусловного перехода, разработке модулей с сильной связностью и обеспечении их независимости от других модулей. Подход базируется на двух основных принципах построения.

Последовательная декомпозиция алгоритма решения задачи сверху вниз.
Использование структурного кодирования.

Напомним, что данная методология является важнейшим развитием императивной методологии.

2.3.1.1. Происхождение, история и эволюция

Создателем структурного подхода считается Эдсгер Дейкстра. Ему также принадлежит попытка (к сожалению, совершенно неприменимая для массового программирования) соединить структурное программирование с методами доказательства программ [Дейкстра 1978].

2.3.1.2. Методы и концепции

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

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

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

2.3.1.3. Структурные языки программирования

Основное отличие от классической методологии императивного программирования заключается в отказе (точнее, той или иной степени отказа) от оператора безусловного перехода.

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

Таблица 2.1. Четыре основных мнения по поводу оператора goto

Точка зрения	Заменители goto	Использование goto	Примеры языков
Ортодоксальная (Дейкстра)	Нет	Нет	BLISS, PDL
Только заменители goto	Да	Нет	Java, Modula-2
Критики Дейкстры (только goto)	Нет	Да	BASIC
И заменители, и goto	Да	Да	C, Ada

2.3.1.4. Класс задач

Класс задач для данной методологии соответствует классу задач для императивной методологии. Заметим, что при этом удается разрабатывать более сложные программы, поскольку их легко воспринимать и анализировать.

2.3.1.5. Рекомендации по литературе

Одной из наиболее известных работ в этой области является статья "Заметки| по структурному программированию" [Дейкстра 1975]. Методы структурного программирования подробно рассмотрены в книге "Теория и практика структурного программирования" [Лингер, Миллс, Уитт 1982]. Практику структурного программирования можно изучать по книге "Алгоритмы + структуры данных = программы" [Вирт 1985]. Философия визуального структурного программирования подробно изложена в работе [Паронджанов 1999].

2.4. Реализационная специфика методологий

2.4.1. Методология императивного параллельного программирования

Методология императивного параллельного программирования - подход, в котором предлагается использование явных конструкций для параллельного исполнения выбранных фрагментов программ.

2.4.1.1. Происхождение, история и эволюция

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

2.4.1.2. Методы и концепции

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

2.4.1.3. Вычислительная модель

Модель вычислений параллельного программирования рассмотрим в контексте модели императивного программирования. Имеется несколько вычислителей, которые характеризуются наличием общих элементов состояния. Одно из возможных описаний вычислительной модели выглядит следующим образом. Если на шаге вычислений с некоторым номером элемент состояния одного вычислителя принимал данное значение, то и для любого Другого вычислителя на шаге вычисления с тем же номером соответствующий элемент состояния также должен принимать данное значение.

2.4.1.4. Синтаксис и семантика

Прямым аналогом оператора в данной методологии является процесс. Основное отличие этой методологии от императивной в том, что процессы могут исполняться параллельно.

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

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

параллелизм на уровне микрокоманд;
параллелизм на уровне операторов (кроме циклов);
параллелизм на уровне циклов и итераций;
параллелизм на уровне подпрограмм (процедур и функций);
параллелизм на уровне потоков управления;
параллелизм на уровне процессов;
параллелизм на уровне приложений.

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

<процесс> ::= <простой процесс> | <структурный процесс
<простой процесс> ::= <послать значение> | <принять значение> | <процесс вычислительной модели>
<структурный процесс> ::= <последовательный процесс> | <параллельный процесс>
<послать значение> ::= <канал связи> << <выражение>;
<принять значение> ::= <канал связи> >> <выражение>;
<процесс вычислительной модели> ::= <нечто, определяемое конкретным вычислителем>
<последовательный процесс> ::= seq <процесс>* end
<параллельный процесс> ::= par <процесс>* end

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

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

2.4.1.5. Параллельные языки программирования

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

Программирование на параллельном языке программирования. Причем такие языки могут быть:

универсальными (например, Ada);
для конкретных типов компьютеров, позволяющих эффективно транслировать программы на параллельном языке именно в эту архитектуру (например, язык Occam изначально разрабатывался для транспьютеров).

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

На рис. 2.6 приведены наиболее распространенные языки программирования, содержащие явные конструкции параллельного исполнения.

2.4.1.6. Класс задач

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

2.4.1.7. Рекомендации по литературе

Две книги являются хорошим введением в методологию параллельного программирования: "Программное обеспечение параллельных процессов" [Трахтенгерц 1987] и "Параллельные вычислительные системы" [Корнеев 1999].

2.4.2. Методология логического параллельного программирования
В моих рассуждениях была все-таки некоторая логика, ускользавшая от Бертрана. Я сказала ему об этом, мы стали спорить. В заключение он привел меня к себе без обеда, в виде наказания.
Франсуаза Саган. "Смутная улыбка"

Логическое программирование допускает естественную параллельную реализацию. В примере а :- b, с. порядок согласования целей b и с не имеет значения, поэтому их можно доказывать параллельно. Говорят, что процессы доказательства b и с образуют И-систему процессов. И-система успешно доказывается, если каждый процесс, входящий в систему, успешен. В примере с предикатом member (см. разд. 2.2.4.4) два правила для него могли применяться параллельно, образуя ИЛИ-систему процессов. ИЛИ-система успешно доказывается, если хотя бы один процесс в системе успешен. Переменные, общие для системы процессов (например, в случае а(Х) :- Ь(Х), с(Х).), преобразуются в каналы связи между процессами в системе. Связывание переменной (присвоение ей значения) аналогично посылке значения в канал.

2.4.2.1. Язык программирования Concurrent Prolog

Языку Concurrent Prolog, предложенному Э. Шапиро (Ehud Shapiro), посвящен ряд статей в сборнике [Язык 1988]. Язык развивает логический подход к абстрактным спецификациям и включает несколько идей Дейкстры (в том числе, идею охраняемого предложения). При этом подходе предметная область описывается как формальная теория в некотором логико-математическом языке. Когда мы используем абстрактную модель вычисления логических программ, то предполагаем, что они легко поддаются параллельному выполнению. Вычисление логической программы - это доказательство целевого утверждения с использованием аксиом из программы. Пространство поиска вывода может быть описано И/ИЛИ деревом, где И-узлы соответствуют конъюнкции целей, ИЛИ-узлы соответствуют различным путям выбора единичных целей из программы.

В языке Concurrent Prolog применяется особое прочтение логических программ - поведенческое. В поведенческом прочтении единичная цель есть аналог процесса, конъюнкция целей - аналог системы процессов, а общие переменные целевых функций - просто каналы связи. Предложение читается поведенчески: процесс А может заменить себя системой процессов B1 и В2 и ... и Bn. Процесс оканчивается заменой себя пустой системой.

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

Вообще, общие переменные возникают, когда процесс создает новую систему процессов, как в следующем случае: р(х) :- q(x, Y), г(Y?). Y создается и используется как канал связи от q к r. Общие переменные могут создаваться динамически при посылке переменной как части сообщения. Это означает, что канал связи может быть создан динамически и отправлен другому объекту. Сообщение, содержащее переменную, называется незавершенным (частично определенным) сообщением. Оно делает новую переменную общей между отправителем и получателем сообщения, что означает создание нового канала связи.

Введем понятие системы процессов.

И-система процессов - это совокупность процессов, которая:

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

ИЛИ-система процессов - это совокупность процессов, которая:

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

Переменные языка Concurrent Prolog обладают рядом свойств, отличающих их от обычных логических переменных.

Унификация защищенной переменной с непеременным термом приостанавливается и приостанавливает тем самым некоторый процесс.
Если переменную, которую ждет какой-либо процесс, установить равной непеременному терму, то это должно привести к возобновлению этого процесса.
Семантика Concurrent Prolog такова, что одна и та же переменная может быть с точки зрения одного процесса защищенной (только для чтения), а с точки зрения другого - просто переменной (общей с первым процессом).

2.5. Другие методологии

Перечислим ряд других, менее исследованных и менее популярных методологий:

методология программирования, управляемого потоками, данных, - подход, заключающийся в том, что операции срабатывают не последовательно, а в зависимости от готовности данных [Чудаева 1992];
методология доступ-ориентированного программирования - подход, в котором функции с переменными связываются таким образом, что при доступе к переменной процедура будет вызываться автоматически [Bal, Grune 1994];
методология нейросетевого программирования - подход, заключающими в том, что на основе знаний, полученных от экспертов, создается программа на нейронном языке программирования, которая затем компилируется в эквивалентную нейронную сеть из аналоговых нейронов (http://iew.technion.ac.il:8080/~iehava/publications/nilletter.ps).

2.6. Происхождение методологий

Достоверная информация о происхождении методологий может быть полезной для их более точной классификации и предсказания появления и развития новых методологий.

2.6.1. Методологии как концентрация практического опыта

Первый и самый очевидный ответ на вопрос происхождения методологий заключается в их независимом происхождении на основе практического опыта программистов. Заметим, что очень многие методологии имеют автора или основателя научной школы, исследующей данную методологию.

2.6.2. Алгоритмическое происхождение некоторых методологий

Это объяснение происходит из утверждения - "теория алгоритмов и логика - родители программирования". Четыре главные модели алгоритма, рассмотренные ниже, математически эквивалентны, но на практике они породили разные направления в программировании, в том числе некоторые основные методологии [Логика 1990].

Первая модель - абстрактные вычислительные машины Тьюринга и Поста. Они определяют методологию императивного программирования.
Вторая модель - рекурсивные функции Гильберта и Аккермана. От них унаследовала свои идеи и конструкции методология структурного программирования.
Третья модель - лямбда-исчисление Черча, Шейнфинкеля и Карри. Эти идеи активно развиваются в методологии функционального программирования.
Четвертая модель - нормальные алгорифмы Маркова. Модель послужила основой логического программирования и обработки символьной информации.

2.6.3. Методологии как результат отображений структур

Еще одно объяснение берет за основу понятие отображения структур языка [Тузов 1990]. Согласно ему, сущность языка определяют три его составные части.

Структура данных.
Структура управления.
Логика.

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

Данные -> Данные. Отображение представляет процесс укрупнения данных и операций над ними и приводит к методам модульности и абстрактных типов данных.
Управление -> Управление. Отображение, связанное с понижением уровня структуры управления языка моделирования, ведет к идее методологии структурного программирования.
Логика -> Логика. Отображение лежит в основе методологии логического программирования.
Данные -> Управление. Отображение активизирует пассивные данные, преобразуя их в активные процессы. Лежит в основе методологии функционального программирования. В значительной степени определяет методологию объектно-ориентированного программирования.
Данные -> Логика. Отображение дает возможность по совокупности операций построить логическую структуру и определяет методологию программирования в ограничениях.
Управление -> Данные. Отображение лежит в основе методов интерпретации. Определяет методологию доступ-ориентированного программирования.
Управление -> Логика. Отображение лежит в основе методов расшифровки смысла задачи.
Логика -> Данные. Отображение может быть связано с типизацией данных и определяет метод развитой системы типов и приведений. Также отображение может быть связано с интерпретаторами, реализующими языки с развитой логической структурой.
Логика -> Управление. Отображение может быть использовано в системах структурного синтеза.

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

ЛИТЕРАТУРА
Правду сказать, мы знаем жизнь только по литературе.
Разумеется, за исключением тех, кто не знает литературы.
Станислав Ежи Лец

1. Бабаев, Герасимов, Косовский, Соловьев 1992- Бабаев И. О., Герасимов М. А., Косовский Н. К., Соловьев И. П. Интеллектуальное программирование. Турбо Пролог и Рефал-5 на персональных компьютерах. - СПб.: Изд-во С-Петербургского университета, 1992.

2. Буч 1998 - Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на C++, 2-е изд. - М.: Бином, СПб.: Невский диалект 1998.

3. Вирт 1985 - Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985.

4. Гамма, Хелм, Джонсон, Влиссидес 2001 - Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного программирования. Паттерны проектирования. - СПб.: Питер, 2001.

5. Дейкстра 1975 - Дейкстра Э. Заметки по структурному программированию // Дал У., Дейкстра Э., Хоор К. Структурное программирование. - М.: Мир, 1975, с. 7-97.

6. Дейкстра 1978 - Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978.

7. Калинин, Мацкевич 1991 - Калинин А. Г., Мацкевич И. В. Универсальные языки программирования. Семантический подход. - М.: Радио и связь, 1991.

8. Кахро, Колья, Тыугу 1988 - Кахро М. И., Калья А. П., Тыугу Э. X. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). - М.: Финансы и статистика, 1988.

9. Корнеев 1999 - Корнеев В. В. Параллельные вычислительные системы. - М.: Нолидж, 1999.

10. Кун 1977 - Томас Кун. Структура научных революций. - М.: Прогресс, 1977.

11. Лингер, Миллс, Уитт 1982 - Лингер Р., Миллс X., Уитт Б. Теория и практика структурного программирования. - М.: Мир, 1982.

12. Логика 1990 - Логика и компьютер. Моделирование рассуждений и проверка правильности программ. - М.: Наука, 1990.

13. Логическое 1988 - Логическое программирование. - М.: Мир, 1988.

14. Паронджанов 1999 - Паронджанов В. Д. Как улучшить работу ума. - М.: Радио и связь, 1999.

15. Тузов 1990 - Тузов В. А. Языки представления знаний. - Л.: Изд-во ЛГУ, 1990.

16. Трахтенгерц 1987 - Трахтенгерц Э. А. Программное обеспечение параллельных процессов. - М.: Наука, 1987.

17. Филд, Харрисон 1993- Филд А., Харрисон П. Функциональное программирование. - М.: Мир, 1993.

18. Хендерсон 1983 - Хендерсон П. Функциональное программирование. Применение и реализация. - М.: Мир, 1983.

19. Хювенен, Сеппянен 1986 - Хювенен Э., Сеппянен И. Мир Лиспа. В 2-х т. - М.: Мир, 1990.

20. Чудаева 1992 - Чудаева О. В. Вычисления, управляемые потоками данных: модели, машины, языки (проблемы и перспективы развития). - Новосибирск: Изд-во ВЦ СО РАН, 1992.

21. Язык 1988 - Язык Пролог в пятом поколении ЭВМ: Сб. статей 1983-1986 гг. / Сост. Н. И. Ильинский. - М.: Мир, 1988.

22. Bal, Grune 1994 - Henri E. Bal, Dick Grune. Programming Language Essentials. Addison-Wesley Publishing Company, 1994.

23. Шаге, Jifeng 1998 - C. A.R. Hoare, He Jifeng. Unifying Theories of Programming. Prentice Hall International, 1998.

технологии программирования к оглавлению к высокоуровн. языкам - 3GL к визуальным средам - 4GL

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

НОВОСТИ ФОРУМА

Рыцари теории эфира