List var y, z: list;
| function rev (x: list) : List var y, z: list; begin A: if null (x) Then rev := y; Z := cdr (x); if atom (z) then goto B; z := rev (z); B: y := cons (z, y); x := cdr (x); goto A end; |
| Пример 8.1. Функция REV, обращающая список и все подсписки, столь же естественно пишется с помощью рекурсивного Prog-выражения. |
| Закрыть окно |
| (setq x 'y) (set x 'NEW) ( print x) (print y) ; Напечатается Y и NEW. |
| Пример 8.2. |
| Закрыть окно |
Стандартное (системное) программирование
Рассматривается наиболее известная парадигма программирования. Предлагается анализ ограничений на структуры управления и информационные потоки при обработке данных. Приведено обоснование дисциплины программирования на стандартных императивно-процедурных языках. Отмечена проблема сопряжения программ, подготовленных на разных языках. Методы расширения функциональных построений применены для моделирования привычного операторно-процедурного стиля программирования и техники работы с глобальными определениями. Обсуждены достоинства структурного программирования, повышающего сходимость процесса отладки программ [[11],[70]].
Существует большое число чисто теоретических работ, исследовавших соотношения между потенциалом функционального и императивно-процедурного подхода к записи программ, пришедших к заключению о формальной сводимости в обе стороны при непринципиальных ограничениях на средства программирования. На практике переложить функциональные программы в императивные проще, чем наоборот - может не хватать широты понятий.
Любые конструкции стандартных языков программирования могут быть введены как функции, дополняющие исходную систему функционального программирования, что делает их вполне легальными средствами в рамках функционального подхода. Надо лишь четко уяснить цену такого дополнения и его преимущества, обычно связанные с наследованием решений и привлечением пользователей. В первых реализациях Лиспа были сразу предложены специальные формы и структуры данных, служащие мостом между разными стилями программирования, а заодно смягчающие недостатки исходной, слишком идеализированной, схемы интерпретации, выстроенной для учебных и исследовательских целей. Важнейшее такого рода средство, выдержавшее испытание временем - prog-форма, списки свойств атома и деструктивные операции, расширяющие язык программирования так, что становятся возможными оптимизирующие преобразования структур данных, программ и процессов, а главное - раскрутка систем программирования [[75]].
Применение prog-выражений позволяет писать "паскалеподобные" программы, состоящие из операторов, предназначенных для исполнения. (Точнее "алголоподобные", т.к.
появились лет за десять до паскаля. Но теперь более известен паскаль.)
Для примера prog-выражения приводится императивное определение функции Length *), сканирующей список и вычисляющей число элементов на верхнем уровне списка. Значение функции Length - целое число. Программу можно примерно описать следующими словами1):
"Это функция одного аргумента L. Она реализуется программой с двумя рабочими переменными u и v. Записать число 0 в v. Записать аргумент L в u. A: Если u содержит NIL, то программа выполнена и значением является то, что сейчас записано в v. Записать в u cdr от того, что сейчас в u. Записать в v на единицу больше того, что сейчас записано в v. Перейти к A"
Эту программу можно записать в виде Паскаль-программы с несколькими подходящими типами данных и функциями. Строкам описанной выше программы в предположении, что существует на Паскале библиотека функций над списками, соответствуют строки определения функции:
function LENGTH (L: list) : integer; var U: list; V: integer; begin V := 0; U := l; A: if null (U) then LENGTH := V; U := cdr (U); V := V+1; goto A; end;
Переписывая на Лисп, получаем программу:
(defun
LENGTH (lambda (L) (prog (U V) (setq V 0) (setq U L) A (cond ((null U)(return V))) (setq U (cdr U)) (setq V (+ 1 V)) (go A) ))) ))
Prog-форма имеет структуру, подобную определениям функций и процедур в Паскале: (PROG, список рабочих переменных, последовательность операторов и атомов ... ) Атом в списке является меткой, локализующей оператор, расположенный вслед за ним. В приведенном примере метка A локализует оператор, начинающийся с "COND".
Первый список после символа PROG называется списком рабочих переменных. При отсутствии таковых должно быть написано NIL или (). С рабочими переменными обращаются примерно как со связанными переменными, но они не могут быть связаны ни с какими значениями через lambda. Значение каждой рабочей переменной есть NIL, до тех пор, пока ей не будет присвоено что-нибудь другое.
Для присваивания рабочей переменной применяется форма SET.
Чтобы присвоить переменной pi значение 3.14 пишется (SET (QUOTE PI)3.14). SETQ подобна SET, но она еще и блокирует вычисление первого аргумента. Поэтому (SETQ PI 3.14) - запись того же присваивания. SETQ обычно удобнее. SET и SETQ могут изменять значения любых переменных из сиска параметров более внешних функций. Значением SET и SETQ является значение их второго аргумента.
Обычно операторы выполняются последовательно. Выполнение оператора понимается как его вычисление и отбрасывание его значения. Операторы программы часто выполняются в большей степени ради действия, чем ради значения.
GO-форма, используемая для указания перехода (GO A) указывает, что программа продолжается оператором, помеченным атомом A, причем это A может быть и из более внешнего prog.
RETURN - нормальный конец программы. Аргумент return вычисляется, что и является значением программы. Никакие последующие операторы не вычисляются.
function rev (x: list) :List var y, z: list; begin A: if null (x) Then rev := y; Z := cdr (x); if atom (z) then goto B; z := rev (z); B: y := cons (z, y); x := cdr (x); goto A end;
Пример 8.1. Функция REV, обращающая список и все подсписки, столь же естественно пишется с помощью рекурсивного Prog-выражения.
Функция rev обращает все уровни списка, так что rev от (A ((B C) D)) даст ((D (C B))A).
(DEFUN rev (x) (prog (y z)
A (COND ((null x)(return y))) (setq z (CDR x)) (COND ((ATOM z)(goto B))) (setq z (rev z))
B (setq y (CONS z y)) (setq x (CDR x)) (goto A) ))
Атомы, играющие роль меток, работают как указатели помеченного блока.
В принципе, SET и SETQ могут быть реализованы примерно так же, как и поиск значения переменной, только с копированием связей, расположенных ранее изменяемой переменной.
(DEFUN set (x y) (assign x y Alist))
Здесь ASSIGN - модель присваивания переменным, хранящим значения в ассоциативном списке Alist (см. лекцию 2). Работает как замена связанного с данной переменной значения на новое заданное значение. Если пары не было вообще, то новая пара из переменной и ее значения помещается в конце списка Alist, чтобы она могла работать как глобальная.
Обратите внимание, что введенное таким образом присваивание работает разнообразнее, чем традиционное: обеспечена вычисляемость левой части присваивания, т.е. можно в программе вычислять имена переменных, значение которых предстоит поменять.
(setq x 'y) (set x 'NEW) (print x) (print y) ; Напечатается Y и NEW.
Пример 8.2.
Для стандартного программирования характерно четкое разделение понятий "программа" и "данное" и учет в процессе обработки данных средств контроля типов данных. Кроме того идеи структурного программирования налагают на стиль программирования ряд ограничений, способствующих удобству отладки программ:
Дисциплина логики управления с исключением переходов по меткам.Минимизация использования глобальных переменных в пользу параметров процедур.Полнота условий в ветвлениях, отказ от отсутствия "else".Однотипность результатов, полученных при прохождении через разные ветви.
Общий механизма интерпретации стандартной программы естественно представить как автомат с отдельными таблицами имен для переменных, значения которых подвержены изменениям, и для меток и процедур, определения которых неизменны. Наиболее распространенные языки программирования, такие как Фортран, Паскаль, Си, Бейсик, придерживаются примерно такой семантики при слегка варьируемой строгости контроля типов данных [[83],[85],[28],[29],[17],[47]]. Семантика стандартных императивных языков допускает применение общей абстрактной машины, что объясняет существование многоязыковых систем программирования, поддерживающих общие библиотеки процедур, компонентов и модулей, а также интеграцию с ассемблером [[42],[86],[22]].
Примечание. Стилизация примера от МакКарти [[75]].
Декларативное программирование
Есть мнение, что однозначное решение задачи в виде четкого алгоритма над хорошо организованными структурами и упорядоченными данными - результат аккуратной, тщательной работы, пытливого и вдумчивого изучения класса задач и требований к их решению. Эффективные и надежные программы в таких случаях - естественное вознаграждение. Но в ряде случаев природа задач требует свободного выбора одного из вариантов - выбор произвольного элемента множества, вероятности события при отсутствии известных закономерностей, псевдо-случайные изменения в игровых обстановках и сценариях, поиск первого подходящего адреса для размещения блока данных в памяти, лингвистический анализ при переводе документации и художественных текстов и т.д. При отсутствии предпочтений все допустимые варианты равноправны, и технология их отладки и обработки должна обеспечивать формально равные шансы вычисления таких вариантов. (Похожая проблема характерна для организации обслуживания в сетях и выполнения заданий операционными системами. Все узлы и задания сети должны быть потенциально достижимы, если нет формального запрета на оперирование ими.)
Представление вариантов подобно определению ветвлений, но без предикатов, управляющих выбором ветви. В некоторых языках, например, учебно-игрового характера, можно указать вероятность выбора варианта. В языках логического и генетического программирования считают возможным прямой перебор вариантов, сопоставляемых с образцами, и организацию возвратов при неудачном варианте.
В отличие от множества элементов, набор вариантов не требует одновременного существования всех составляющих. Поэтому и программирование вариантов можно освободить от необходимости формулировать все варианты сразу. В логическом программировании можно продумывать варианты отношений между образцами формул постепенно, накапливая реально встречающиеся сочетания. Содержательно такой процесс похож и на уточнение набора обработчиков прерываний на уровне оборудования. Кроме основной программы, выполняющей целевую обработку данных, отлаживается коллекция диагностических реакций и процедур продолжения счета для разного рода неожиданных событий, препятствующих получению результата программы.
Обычно понятие алгоритма и программы связывают с детерминированными процессами. Но эти понятия не очень усложняются, если допустить недетерминизм, ограниченный конечным числом вариантов, так что в каждый момент времени из них существует только один вариант. По смыслу выбор варианта похож на выбор произвольного элемента множества.
{ a | b | c } = э{ a, b, c }
Чтобы такое понятие промоделировать, нужны дополнительные примитивы. Например, чтобы определить обычными функциональными средствами выбор произвольного элемента из списка L, можно представить рекурсивное выражение вида:
(любой L) = {( car L) | (любой (cdr L)) }
Если варианты в таком выражении рассматривать как равноправные компоненты, то не ясно, как предотвратить преждевременный выбор пустого списка при непустом перечне вариантов.
Чтобы решить эту задачу, вводится специальная форма ESC (ТУПИК), действие которой заключается в том, что она как бы "старается" по возможности не исполняться. Иными словами, при выборе вариантов предпочитаются варианты, не приводящие к исполнению формы ESC. (Такая же проблема возникает при обработке пустых цепочек в грамматиках. Аналогичная проблема решена при моделировании процессов интерпретированными сетями Петри [[15]] - соглашением о приоритете раскрашенных переходов в сравнении с пустыми.)
Уточненное таким образом определение выбора произвольного элемента списка можно представить формулой вида:
(любой L) = { (car L) | (любой (cdr L)) | (if (nl L) ESC) }
В какой-то момент L становится пустым списком, и его разбор оказывается невозможным. Тогда действует ESC.
Следует иметь в виду, что варианты не образуют иерархии. Их аксиоматика подобна так называемой упрощенной теории множеств. Принципиальная особенность - совпадение предикатов принадлежности и включения.
Другие построения, характерные для теории множеств:
{ x | P(X) } - множество элементов, обладающих свойством P.
Определение вида
(F x) = {(if (P ( car L )) (cons ( car L) (F ( cdr L))) ) | (if (nl L) esc) }
недостаточно, т.к. порождаемые варианты элементов, удовлетворяющих заданому свойству, существуют в разные моменты времени и могут не существовать одновременно. Чтобы получить все варианты одновременно, требуется еще один примитив ALL, обеспечивающий накопление всех реально осуществимых вариантов.
(F x) = (ALL {(if (P ( car L )) (cons ( car L) (F ( cdr L))) ) | (if (nl L) esc) } )
Пересечение множеств A и B:
( all ( lambda (x y) {(if (= x y) x) | esc }) (любой A) (любой B) )
Логические связки:
Логическую связку "a & b" часто реализуют как "(if (not a) Nil b)", так что "b" вычисляется лишь при истинном "a", что не всегда соответствует интуитивным ожиданиям. Более надежны варианты, исключающие зависимость от порядка вычислений параметров:
(( lambda x { (if (not x) Nil ) | esc }) {a | b} )
Аналогичная проблема возникает при реализации ветвлений.
(cond (p1 e1) (p2 e2 ) …)
( ( lambda L {(cond (( eval ( caar L) AL) ( eval ( cadr L) AL ) )) | ESC }) ( любой ((p1 e1) (p2 e2) ...)))
Поддержка вариантов, каждый из которых может понадобиться при построении окончательного результата, находит практическое применение при организации высокопроизводительных вычислений. Например, мультиоперации можно организовать с исключением зависимости от порядка отдельных операций в равносильных формулах:
a+b+c = (a+b)+c = a+(b+c) = (a+c)+b
((lambda (x y z) {(if (< (+ x y) K) (+(+ x y) z)) | esc}) {(a b c) | (b c a) | (c a b)})
В книге Хендерсона приведено обобщение абстрактной машины, поддерживающее на базовом уровне работу с вариантами с использованием дополнительного дампа, гарантирующего идентичность состояния машины при переборе вариантов [[23]].
Необходимая для такого стиля работы инструментальная поддержка обеспечивается в GNU Clisp механизмом обработки событий throw-catch, для которого следует задать примерно такое взаимодействие:
(defun vars (xl)(catch 'esc ; перебор вариантов до первого тупика (cond ; vars not Nil ((null xl)(escape)) ((car xl) (cons (car xl)(vars (cdr xl)))) )))
(defun escape () (throw 'esc Nil)) ; сигнал о попадании в тупик
В этой схеме THROW играет роль прерывания процесса, а CATCH - обработчика прерываний. Их взаимодействие синхронизировано с помощью тега, идентифицирующего уровень, на котором расположена ловушка для соответствующего прерывания. При этом есть возможность указать передаваемое "наверх" значение. Содержательно такая схема взаимодействия похожа на PROG-RETURN, с той разницей, что отсутствует зависимость от расположения в тексте программы.
Получается, что в любом выражении можно выполнить разметку ветвей на нормальные и тупиковые. Тупики можно связать с различными тегам и выставить ловушки на заданные теги. При попадании в тупик формируется значение всей структуры, размещенной внутри ловушки.
Используя тупики и ловушки, можно собрать все беступиковые варианты или организовать перебор вариантов до первого беступикового. Первое можно сделать с помощью отображений (map), а второе - первый подходящий - слегка модифицированным evcon с добавочной ловушкой на прерывание при достижении успеха. Модификация заключается в использовании другой версии eval. Ловушка нужна для приостановки вычисления независимых вариантов, когда уже найден один подходящий, т.е. не заводящий в тупик.
Более сложно обеспечить равновероятность выбора вариантов. Наиболее серьезно возможность такой реализации рассматривалась Дж. Шварцем в проекте языка SETL. Похожие механизмы используются в языках, ориентированных на конструирование игр, таких как Grow, в которых можно в качестве условия срабатывания команды указать вероятность.
В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств. Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле.
Следует отметить открытый ряд классов задач, при решении которых результативно используются недетерминированные модели:
Обоснование упорядочений в традиционных алгоритмах - выделяется доалгоритмический уровень, на котором просто анализируются таблицы возможных решений и постепенно вырабатываются комплекты упорядочивающих условий и предикатов.Переформулировка задач и переопределение алгоритмов с целью исключения необоснованных упорядочений - одна из типовых задач оптимизации, особенно при переходе от обычных программ к параллельным. Приходится выяснять допустимость независимого исполнения всех ветвей и управляющих их выбором предикатов.Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах (многопроцессорная машина Тьюринга и т.п.).Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность.Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskel и др.Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками.Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т.п.Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т.п.
Используемые при исследовании и решении таких задач модели дают богатый материал для развития нового поколения информационных систем, концептуальную основу которых можно изучать с помощью небольших функциональных программ.
Принятая при решении таких задач техника сопоставления с образцом в значительной мере может быть осуществлена как работа с необязательными параметрами, что иллюстрирует эффективная версия определения сцепления списков [[73]]:
(defun append (&optional first &rest others ) (if (null others) first (nconc (copy-list first) (apply #'append others)) ) )
В этой версии исключено копирование первого списка, когда других списков нет, и копии сцепляемых списков производятся лишь однократно.
Интерпретирующий автомат для выполнения недетерминированных процессов можно представить как цикл продолжения вычислений при попадании в диагностическую ситуацию. Продолжение заключается в выборе другого варианта из набора определений функционального объекта. Вычисление признается неудачным лишь если не удалось подобрать комплект вариантов, позволяющий вычислить значение формулы.
Более подробно с идеями декларативного программирования можно ознакомиться на примере языка логического программирования Пролог [[52]].
Классы и экземпляры объектов
(defclass ob () (f1 f2 ...))
Это означает, что каждое вхождение объекта будет иметь поля-слоты f1 f2 ... (Слот - это поле записи или списка свойств.)
Чтобы сделать представителя класса, мы вызываем общую функцию:
(setf с (make-instance 'ob))
Чтобы задать значение поля, используем специальную функцию:
(setf (slot-value c) 1223)
До этого значения полей были не определены.
Объектно-ориентированное программирование
Рассмотрены основные принципы ОО-программирования и проанализированы схемы их реализации на базе ряда структур данных на примере простой модели ОО-языка, встраиваемого в Лисп. Отмечены особенности CLOS, поддерживающей ООП на GNU Clsip. Реализация методов обработки объектов заданного класса сводится к отдельной категории функций, вызов которых управляется анализом принадлежности аргумента классу.
Сборка программы из автономно развивающихся компонентов опирается на формулировку достигаемой ими цели, понимание которой гарантирует не только корректность полученного результата, но и рациональность его использования. Формулировать цели частей программы - процесс нетривиальный. В его основе лежат весьма различные подходы к классификации понятий.
ООП объединяет в рамках единой методики организации программ классификацию на базе таких понятий как класс объектов, структура данных и тип значений. Тип значений обычно отражает спектр низкоуровневых реализационных средств, учет которых обеспечивает эффективность кода программы, получаемого при компиляции. Структура данных обеспечивает конструктивность построений, гарантирует доступ к частям, из которых выстроено данное любой сложности. Класс объектов характеризуется понятным контекстом, в котором предполагается их корректная обработка. Обычно контекст содержит определения, структуру объектов и их свойства [[41]].
Текст программы одновременно представляет и динамику управления процессами, и схему информационных потоков, порождаемых при исполнении программы. Кроме того, последовательность написания программы и ее модификации по мере уточнения решаемой задачи могут соответствовать логике, существенно отличающейся от процесса выбора системных и реализационных решений. Обычно программирование скрывает сложность таких деталей управления процессами путем сведения его к общим функциям, преобразующим любые аргументы в определенные результаты. Модификации программы при развитии решаемой задачи осуществляются непосредственно переработкой текста программы и определений входящих в нее функций.
ООП структурирует множество частных методов, используемых в программе, в соответствии с иерархией классов объектов, обрабатываемых этими методами, реализуемыми с помощью функций и процедур, в предположении, что определяемые в программе построения могут локально видоизменяться при сохранении основных общих схем информационной обработки. Это позволяет выполнять модификации объявлением новых подклассов и дописыванием методов обработки объектов отдельных классов без радикальных изменений в ранее отлаженном тексте программы.
При анализе задач, решаемых в терминах объектов, некоторая деятельность описывается так, что постепенно продумывается все, что можно делать с объектом данного класса. Потом в программе достаточно лишь упоминать методы обработки объекта. Если методов много, то они структурированы по иерархии классов, что позволяет автоматизировать выбор конкретного метода. На каждом уровне иерархии можно немного варьировать набор методов и структуру объектов. Таким образом, описание программы декомпозируется на интерфейс и реализацию, причем интерфейс скрывает сложность реализации так, что можно обозревать лишь необходимый для использования минимум средств работы с объектом.
Типичная гипотеза при программировании работы с объектами:
Объект не изменен, если на него не было воздействий из программы.
Но реальность зачастую требует понимания и учета более сложных обстоятельств, что может существенно продлить время жизни программы или ее компонентов. В таком случае удобно предоставлять объектам большую свободу, сближающую их с понятием субъекта, описание которого содержит все, что он может делать. Программа может давать ему команды-сообщения и получать ответы-результаты.
Связь методов с классами объектов позволяет вводить одноименные методы над разными классами объектов (полиморфизм), что упрощает представление логики управления: на уровне текста программы можно не выражать распознавание принадлежности объекта классу, это сделает система программирования. Таким образом обычно реализовано сложение, одинаково изображаемое для чисел, строк, векторов, множеств и т.п.
Фактически субъектом является суперкласс, объединяющий классы объектов, обрабатываемые одноименными методами, т.е. функциями одного семейства. Так, при организации сложения можно считать, что существует суперкласс "слагаемые", которое умеют складываться с другими слагаемыми. При этом они используют семейство функций, реализующих сложение. В зависимости от полноты семейства результат может быть получен или не получен. Семейство легко пополняется добавлением одноименных функций с новыми комбинациями типов параметров.
Дальнейшее развитие подходов к декомпозиции программ связано с выделением отдельных аспектов и шагов при решении сложных задач. Понятие аспекта связано с различием точек зрения, позволяющим описывать решение всей задачи, но отражать в описании только видимые детали [[33]]. По мере изменения точек зрения могут проступать новые детали, до тех пор, пока дальнейшая детализация не утрачивает смысл, т.е. улучшение трудно заметить или цена его слишком высока. Так, представление символьной информации в Лиспе выделено в отдельный аспект, независимый от распределения памяти, вычисление значений четко отделено от компиляции программ, понятие связывания имен с их определениями и свойствами не зависит от выбора механизмов реализации контекстов исполнения конструкций программы.
Понятие шага обычно связывается с процессом раскрутки программ, оправданным в тех случаях, когда целостное решение задачи не может гарантировать получение приемлемого результата в нужный срок - это влечет за собой непредсказуемо большие трудозатраты.
Удобный подход к организации программ "отдельная работа отдельно программируется и отдельно выполняется" успешно показал себя при развитии операционной системы UNIX как работоспособный принцип декомпозиции программ. Но существуют задачи, например реализация систем программирования, в которых прямое следование такому принципу может противоречить требованиям к производительности. Возможен компромисс "отдельная работа программируется отдельно, а выполняется взаимосвязано с другими работами" [[67]], что требует совмещения декомпозиции программ с методами сборки - комплексации или интеграции программ из компонентов.
Рассматривая комплексацию как еще одну "отдельную" работу, описываемую, например, в терминах управления процессами, можно констатировать, что эта работа больше сказывается на требованиях к уровню квалификации программиста, чем на объеме программирования. При достаточно объективной типизации данных и процессов, возникающих при декомпозиции и сборке программ определенного класса, строят библиотеки типовых компонентов и разрабатывают компонентные технологии разработки программных продуктов - Corba, COM/DCOM, UML и т.п.. Одна из проблем применения таких компонентов - их обширность [[76],[86]].
Таким образом, ООП отражает эволюцию подходов к организации структур данных на уровне задач и программ их решения, исходя из парадигмы императивно-процедурного программирования. От попыток реализации математически корректных абстрактных типов данных произошел практичный переход к технически простому статическому контролю типов данных при разработке и применении расширяемых программ. Расширение программы выполняется декларативно, а выбор нужного варианта при исполнении функций, обладающих неединственным определением, - в зависимости от типа данных. Введены дополнительные механизмы - инкапсуляция, уточнение типов данных при компиляции и выбор обработчиков данных, управляемый типами данных.
Механизмы ООП обеспечивают наследование свойств по иерархии классов объектов и так называемый "дружественный" доступ к произвольным классам. Расширение программ при объектно-ориентированном подходе к программированию выглядит как простое дописывание новых определений. Библиотеки типов данных и методов их обработки легко вписываются в более общие системы. Спецификация интерфейсов в принципе может быть сопровождена верификацией реализации компонент. Возможна факторизация программ на компоненты и рефакторизация программных компонент в стиле экстремального программирования [[12],[46]].
При реализации экспериментальных языков и систем программирования часто применяется методика раскрутки - минимизация трудозатрат, основанная на учете формальной избыточности средств языков программирования.
Выделяется небольшое ядро, на основе которого методично программируется все остальное. Каждый шаг реализации по схеме раскрутки должен обеспечивать:
уменьшение трудоемкости последующих шагов,отладку прототипов сложных компонентов,подготовку демонстрационного материала.
Выбор конретных шагов можно соотнести с декомпозицией определения языка программирования на синтаксические и семантические, функциональные и машинно-ориентированные, языково-ориентированные и системные аспекты. При такой декомпозиции можно на первых шагах как бы "снять" синтаксическое и семантическое разнообразие языка, как имеющее чисто технический характер. Именно в этом смысл выделения элементарного Лиспа (см. лекцию 2). Такая методика может быть успешна при освоении любого класса, информацию о котором можно представить в виде частично формализуемых текстовых и графовых форм.
Дальнейшие шаги раскрутки можно упорядочить по актуальности реализации компонентов, обеспечивающих положительную оценку системы пользователем. Это позволяет развить представление о принципах декомпозиции программ более созвучно ООП: "отдельная работа обнаруживается независимо от остальных работ". Наиболее устойчивая и значимая классификация работ по реализации системы программирования может быть установлена как обеспечение механизмов надежного функционирования информационных систем - "отдельная работа - это отдельное средство повышения надежности программирования". Ряд таких средств можно выделить в любом языке программирования: вычисления, статическое и динамическое управление процессами, логика выбора хода обработки информации, дисциплина именования памяти и доступа к расположенным в ней данным, правила укрупненных воздействий на блоки данных и иерархию процессов, диагностика и обработка событий - перечень открытый [[33]].
При переходе от обычного стандартного программирования с ООП связывают радикальное изменение способа организации программ. Это изменение произошло под давлением роста мощности оборудования.
ООП взламывает традиционное программирование по многим направлениям. Вместо создания отдельной программы, оперирующей массой данных, приходится разбираться с данными, которые сами обладают поведением, а программа сводится к простому взаимодействию новой категории данных - "объекты".
Прозрачная модель ООП получается на базе обычных списков свойств, заодно иллюстрирующая глубинное родство ФП и ООП.
(defun classes (cl) (cond (cl (cons (cdar cl) (classes (cdr cl)))) ))
; вывод формулы классов аргументов из определения параметров метода ; Nil - произвольный класс
(defun argum (cl) (cond (cl (cons (caar cl) (argum (cdr cl)))) ))
; вывод списка имен аргументов из определения параметров метода
(defun defmet (FMN c-as expr) (setf (get FMN 'category) 'METHOD) (setq ML (cons(cons(cons FMN (classes c-as)) (list 'lambda (argum c-as) expr) ) ML)) FMN )
; объявление метода и расслоение его определения ; для удобства сопоставления с классами аргументов
(defun defcl (NCL SCL FCL ) ; имя, суперкласс и поля/слоты класса (setq ALLCL (cons NCL ALLCL)) (set NCL (append FCL SCL)) )
; значением класса является список его полей, возможно, со значениями
(defun ev-cl (vargs) (cond
; вывод формата фактических аргументов для поиска метода их обработки
(vargs (cons (cond ((member (caar vargs) ALLCL) (caar vargs)) ) (ev-cl (cdr vargs)))) )) ; Nil если не класс
(defun m-assoc (pm meli) (cond (meli (cond ((equal (caar meli) pm)(cdar meli)) (T(m-assoc pm (cdr meli)))))))
; поиск подходящего метода, соответствующего формату классов данных
(defun method (MN args &optional c) (apply (m-assoc (cons mn (ev-cl args)) ML) args c))
; если метода не нашлось, в программе следует выполнить приведение ; параметров к нужному классу
(defun instance (class &optional cp) (cond
; подобно Let безымянная копия контекста
(class (cond ((atom (car class))(instance (cdr class) cp)) ((assoc (caar class) cp) (instance (cdr class) cp)) (T(instance (cdr class) (cons (car class) cp))) )) ) cp)
(defun slot (obj fld) (assoc fld obj))
; значение поля объекта
Пример 10.1. Модель интерпретатора объектно-ориентированных программ
Остается лишь слегка подкорректировать определение Лисп-интерпретатора, заодно используя необязательные параметры, осовобождающие от простейших вспомогательных определений, например от обязательного вхождения накопителей типа ассоциативного списка, примерно как в курсе "Основы функционального программирования" [[8]].
Показанный в [[72]] аналогичный пример работает по первому аргументу (выбор подходящего метода рассчитан на то, что достаточно разобраться с одним аргументом). Система CLOS (GNU Clisp) делает это на всех аргументах, причем с рядом вспомогательных средств, обеспечивающих гибкий перебор методов и анализ классов объектов [[82]].
Рассмотрим отличия в базовых понятиях и методах работы с ними:
вывод формулы классов аргументов из
|
(defun classes (cl) (cond (cl (cons (cdar cl) (classes (cdr cl)))) )) ; вывод формулы классов аргументов из определения параметров метода ; Nil - произвольный класс (defun argum (cl) (cond (cl (cons (caar cl) (argum (cdr cl)))) )) ; вывод списка имен аргументов из определения параметров метода (defun defmet (FMN c-as expr) (setf (get FMN 'category) 'METHOD) (setq ML (cons(cons(cons FMN (classes c-as)) (list 'lambda (argum c-as) expr) ) ML)) FMN ) ; объявление метода и расслоение его определения ; для удобства сопоставления с классами аргументов (defun defcl (NCL SCL FCL ) ; имя, суперкласс и поля/слоты класса (setq ALLCL (cons NCL ALLCL)) (set NCL (append FCL SCL)) ) ; значением класса является список его полей, возможно, со значениями (defun ev-cl (vargs) (cond ; вывод формата фактических аргументов для поиска метода их обработки (vargs (cons (cond ((member (caar vargs) ALLCL) (caar vargs)) ) (ev-cl (cdr vargs)))) )) ; Nil если не класс (defun m-assoc (pm meli) (cond (meli (cond ((equal (caar meli) pm)(cdar meli)) (T(m-assoc pm (cdr meli))))))) ; поиск подходящего метода, соответствующего формату классов данных (defun method (MN args &optional c) (apply (m-assoc (cons mn (ev-cl args)) ML) args c)) ; если метода не нашлось, в программе следует выполнить приведение ; параметров к нужному классу (defun instance (class &optional cp) (cond ; подобно Let безымянная копия контекста (class (cond ((atom (car class))(instance (cdr class) cp)) ((assoc (caar class) cp) (instance (cdr class) cp)) (T(instance (cdr class) (cons (car class) cp))) )) ) cp) (defun slot (obj fld) (assoc fld obj)) ; значение поля объекта |
| Пример 10.1. Модель интерпретатора объектно-ориентированных программ |
| Закрыть окно |
|
;oop-compile (defclass expr () ((type :accessor td) (sd :accessor ft)) (:documentation "C-expression")) (defclass un (expr) ; \ _____суперкласс для унарных форм ((type :accessor td) ;; можно убрать ??? (sd :accessor ft)) ;; можно убрать ??? (:documentation "quote car *other *adr")) (defclass bin (expr) ((type :accessor td) (sd :accessor ft) (sdd :accessor sd) ) (:documentation "cons + lambda let")) (defclass trio (expr) ((type :accessor td) (sd :accessor ft) ; (bin) ;; не объявлять sdd ??? (sdd :accessor sd) (sddd :accessor td) ) (:documentation "if label")) (defmethod texrp ((x expr) (nt atom)) (setf (slot-value x 'type) nt) (setf (td x) nt) ;;--;; variant (:documentation "объявляем тип выражения")) (defmethod spread ((hd (eql 'QUOTE)) (tl expr)) (let ( (x (make-instance 'un)) ) (setf (ft x) (car tl)) (setf (td x) hd) ) (:documentation "распаковка выражения")) (defmethod compl ((hd (eql 'QUOTE)) (tl expr)) (list 'LDC tl) ) (:documentation "сборка кода")) (defmethod compl ((hd (eql 'CAR)) (tl expr)) (append (compl(ft tl) N) '(CAR)) ) (:documentation "сборка кода")) (defmethod spread ((hd (eql 'CONS)) (tl expr)) (let ( (x (make-instance 'bin)) ) (setf (ft x) ( car tl)) (setf (sd x) ( cadr tl)) (setf (td x) hd) ) (:documentation "распаковка выражения")) (defmethod compl ((hd (eql 'CONS)) (tl bin) N ) (append (compl(sd tl) N) (compl(ft tl) N) '(CONS)) ) (:documentation "сборка кода")) (defmethod compl ((hd (eql '+)) (tl bin) N ) (append (compl(ft tl) N) (compl(sd tl) N) '(ADD)) ) (:documentation "сборка кода")) (defmethod spread ((hd (eql 'IF)) (tl expr)) (let ( (x (make-instance 'trio)) ) (setf (ft x) ( car tl)) (setf (sd x) ( cadr tl)) (setf (td x) ( caddr tl)) (setf (td x) hd) ) (:documentation "распаковка выражения")) (defmethod compl ((hd (eql 'IF)) (tl expr) N ) (let ( (then (list (compl(sd tl) N) '(JOIN))) (else (list (compl(td tl) N) '(JOIN))) ) (append (compl(ft tl) N) (list 'SEL then else) ) )(:documentation "сборка кода")) (defmethod parh ((x expt)) (let (ftx (ft x)) (cond ((atom ftx) (spread 'ADR ftx)) ((member (car ftx) '(QUOTE CAR CONS + IF LAMBDA LABEL LET)) (spread (car ftx) (cdr ftx)) (T (spread 'OTHER ftx) )) )(:documentation "шаг разбора")) |
| Пример 10.2. Модель компилятора объектно-ориентированных программ |
| Закрыть окно |
Суперкласс
Нет необходимости все новые слоты создавать в каждом классе
;oop-compile
(defclass expr () ((type :accessor td) (sd :accessor ft)) (:documentation "C-expression"))
(defclass un (expr) ; \_____суперкласс для унарных форм
((type :accessor td) ;; можно убрать ??? (sd :accessor ft)) ;; можно убрать ??? (:documentation "quote car *other *adr"))
(defclass bin (expr) ((type :accessor td) (sd :accessor ft) (sdd :accessor sd) ) (:documentation "cons + lambda let"))
(defclass trio (expr) ((type :accessor td) (sd :accessor ft) ; (bin) ;; не объявлять sdd ??? (sdd :accessor sd) (sddd :accessor td) ) (:documentation "if label"))
(defmethod texrp ((x expr) (nt atom)) (setf (slot-value x 'type) nt) (setf (td x) nt) ;;--;; variant (:documentation "объявляем тип выражения"))
(defmethod spread ((hd (eql 'QUOTE)) (tl expr)) (let ( (x (make-instance 'un)) ) (setf (ft x) (car tl)) (setf (td x) hd) ) (:documentation "распаковка выражения"))
(defmethod compl ((hd (eql 'QUOTE)) (tl expr)) (list 'LDC tl) ) (:documentation "сборка кода"))
(defmethod compl ((hd (eql 'CAR)) (tl expr)) (append (compl(ft tl) N) '(CAR)) ) (:documentation "сборка кода"))
(defmethod spread ((hd (eql 'CONS)) (tl expr)) (let ( (x (make-instance 'bin)) ) (setf (ft x) ( car tl)) (setf (sd x) ( cadr tl)) (setf (td x) hd) ) (:documentation "распаковка выражения"))
(defmethod compl ((hd (eql 'CONS)) (tl bin) N ) (append (compl(sd tl) N) (compl(ft tl) N) '(CONS)) ) (:documentation "сборка кода"))
(defmethod compl ((hd (eql '+)) (tl bin) N ) (append (compl(ft tl) N) (compl(sd tl) N) '(ADD)) ) (:documentation "сборка кода"))
(defmethod spread ((hd (eql 'IF)) (tl expr)) (let ( (x (make-instance 'trio)) ) (setf (ft x) ( car tl)) (setf (sd x) ( cadr tl)) (setf (td x) ( caddr tl)) (setf (td x) hd) ) (:documentation "распаковка выражения"))
(defmethod compl ((hd (eql 'IF)) (tl expr) N ) (let ( (then (list (compl(sd tl) N) '(JOIN))) (else (list (compl(td tl) N) '(JOIN))) ) (append (compl(ft tl) N) (list 'SEL then else) ) )(:documentation "сборка кода"))
(defmethod parh ((x expt)) (let (ftx (ft x)) (cond ((atom ftx) (spread 'ADR ftx)) ((member (car ftx) '(QUOTE CAR CONS + IF LAMBDA LABEL LET)) (spread (car ftx) (cdr ftx)) (T (spread 'OTHER ftx) )) )(:documentation "шаг разбора"))
Пример 10.2. Модель компилятора объектно-ориентированных программ
Тесты к этому определению имеются в курсе Основы функционального программирования [[8]]
Система CLOS (Common Lisp Object System) использует похожую модель обобщенных функций, но мы написали независимую модель, используя более старые представления, тем самым показав, что концептуально ООР - не более чем перефразировка идей функционального программирования с привкусом декларативного стиля. ООП - это одна из вещей, к которой Лисп изначально приспособлен. Для функционального стиля программирования в переходе к ООП нет ничего неожиданного. Это просто небольшая конкретизация механизмов представления и перебора ветвей функциональных объектов.
Свойства слотов
Простейшее определение слота - это его имя. Но в общем случае слот может содержать список свойств. Внешне свойства слота специфицируются как ключевые параметры функции. Это позволяет задавать начальные значения.
Можно объявить слот совместно используемым.
:allocation :class
Изменение такого слота будет доступно всем экземплярам объектов класса.
:documentation - свойство слота
Можно задать тип элементов, заполняющих слот.
Языки параллельного программирования
Применение параллельных архитектур повышает производительность при решении задач, явно сводимых к обработке векторов. Автоматическое распараллеливание последовательных программ дает теоретически ограниченный выигрыш по ускорению вычислений. Более успешным может быть выражение языковыми средствами естественного параллелизма на уровне постановки задачи, с тем чтобы при оптимизирующей компиляции был выполнен аккуратный выбор наиболее эффективной схемы параллелизма для программы решения задачи.
Существование проблемы второго языка объясняет, что достаточно распространены методы представления параллельных программ, через добавление средств параллелизма в обычные языки программирования, такие как Fortran, Pascal, Ada и др. Существуют версии ряда стандартных языков императивного программирования, приспособленные к выражению взаимодействия последовательных процессов в предположении, что в каждый момент времени существует лишь один процесс. При таком подходе в программе выделяются критические интервалы, учет которых полезен при распараллеливании программ.
Независимая разработка специализированных языков параллельного программирования и языков управления процессами дала ряд интересных идей по представлению и масштабированию параллельных вычислений, с которыми можно ознакомиться по материалам о языках APL, Symula-67, Sisal, БАРС, Occam, Поляр и др. [[16],[35],[51],[59],[84],[87]]
Весьма перспективно применение универсальных языков сверх высокого уровня, таких как SETL, Planner, Eiffel, Haskel, Python, Cw и т.п., абстрагирование данных и процессов в которых нацеливает на активное использование математических и функциональных моделей, приспособленных к гибкому и строгому структурированию, удобному для доказательных построений [[35],[49],[50],[57],[78]].
Языки спецификаций и проектирования также заслуживают внимания как средства, определяющие качество программных решений, надежность программирования, возможность верификации программ и длительность их жизненного цикла [[14],[25],[65],[86]].
Техника программирования в достаточно сложных областях науки и техники иллюстрируется на не теряющих актуальности задачах организации параллельных вычислений. Этот класс задач решается как функциональный подход к определению преобразований регулярных множеств. В рамках такого подхода сложные построения факторизуются с учетом особенностей структуры данных так, что выделяются несложные отображающие функции, "просачиваемые" по структуре данных с помощью функций более высокого порядка - функционалов. В результате при организации сложной информационной обработки можно независимо варьировать структуры данных, функционалы, отображающие функции, методы сборки полного результата отображения и набор отображаемых множеств.
Развитие суперкомпьютеров обусловлено существованием особо важных задач, главным требованием к решению которых является скорость вычислений в реальном времени. Нужная скорость достигается ценой весьма сложной организации связей между синхронизованными на уровне аппаратуры процессорами. Активно используется локальная память процессоров, приспособленная к быстрым матричным вычислениям и вообще однородной обработке информации. При программировании целенаправленно выделяются конвейерные процессы, приспособленные к минимизации хранения промежуточных результатов. Разработаны специальные архитектуры сверхдлинных команд с внутренним совмещением микроопераций. Исследованы асинхронные конфигурации и модели управления на метауровне организации параллельных процессов. Специфику языков параллельного программирования для высокопроизводительных вычислений на базе суперкомпьютеров и многоядерных архитектур рассмотрим на примере языков APL, Sisal и БАРС [[16],[84],[87]].
Исторически первое предложение по организации языка высокого уровня для параллельных вычислений было сделано в 1962 году Айверсоном в проекте языка APL [[16]]. В этом весьма оригинальном языке был предложен интересный механизм реализации многомерных векторов, приспособленный к расширению и распараллеливанию обработки. Сложные данные представляются как пара из последовательности скаляров и паспорта, согласно которому эта последовательность структурируется. В результате любое определение функции над скалярами может быть стандартно распространено на произвольные структуры данных из скаляров. APL обладает богатым, тщательно подобранным набором базовых средств обработки векторов и манипулирования паспортами структур данных как данными.
Заметное место среди языков функционального программирования занимают языки параллельного программирования. Довольно известен язык функционального программирования Sisal.
Название языка расшифровывется как "Streams and Iterations in a Single Assignment Language", сам он представляет собой дальнейшее развития языка VAL, известного в середине 70-х годов. Среди целей разработки языка Sisal следует отметить наиболее характерные, связанные с функциональным стилем программирования [[84]].
Создание универсального функционального языка.Разработка техники оптимизации для высокоэффективных параллельных программ.Достижение эффективности исполнения, сравнимой с императивными языками типа Fortran и C.Внедрение функционального стиля программирования для больших научных программ.
Эти цели создателей языка Sisal подтверждают, что функциональные языки способствуют разработке корректных параллельных программ. Одна из причин заключается в том, что функциональные программы свободны от побочных эффектов и ошибок, зависящих от реального времени. Это существенно снижает сложность отладки. Результаты переносимы на разные архитектуры, операционные системы или инструментальные окружения. В отличие от императивных языков, функциональные языки уменьшают нагрузку на кодирование, в них проще анализировать информационные потоки и схемы управления.
Легко создать функциональную программу, которая является безусловно параллельной, если ее можно писать, освободившись от большинства сложностей параллельного программирования, связанных с выражением частичных отношений порядка между отдельными операциями уровня аппаратуры. Пользователь Sisal-а получает возможность сконцентрироваться на конструировании алгоритмов и разработке программ в терминах крупноблочных и регулярно организованных построений, опираясь на естественный параллелизм уровня постановки задачи.
Начнем с примера программы:
For % инициирование цикла Approx := 1.0; Sign := 1.0; Denom := 1.0; i := 1
while i <= Cycles do % предусловие завершения цикла
Sign := -Sign; % однократные Denom := Denom + 2.0; % присваивания Approx := Approx + Sign / Denom; % образуют i := i + 1 % тело цикла
returns Approx * 4.0 % выбор и вычисление результата цикла end for
Пример 11.1. Вычисление числа пи
for i in [1..Cycles/2] do % пространство параллельно исполнимых итераций
val := 1.0/real(4*i-3) - 1.0/real(4*i-1); % тело цикла, для каждого i исполняемое независимо
returns sum( val ) % выбор и свертка результатов всех итераций цикла
end for * 4.0 % вычисление результата выражения
Пример 11.2. Это выражение также вычисляет число пи
Это выражение вычисляет сумму всех вычисленных значений val и умножает результат на 4.0.
for i in [1..2] dot j in [3..4] do % для пар индексов [1,3] и [2,4]
returns product (i+j) % произведение сумм
end for % = 24
Пример 11.3. В for-выражениях операция dot может порождать пары индексов при формировании пространства итерирования
for i in [1..2] cross j in [3..4] do % для пар [1,3], [1,4], [2,3] и [2,4]
returns product (i+j) % произведение сумм
end for % = 600
Пример 11.4. В for-выражениях операция cross может порождать пары индексов при формировании пространства итерирования
for I := 1 while I < S do K := I; I := old I + 2; % значение из предыдущей итерации
J := K + I; returns product(I+J) end for
Пример 11.5. Итеративное for-выражение с обменом данными между итерациями
Как это свойственно языкам функционального программирования, и язык SISAL математически правильный - функции отображают аргументы в результаты без побочных эффектов, и программа строится как выражение, вырабатывающее значение. Наиболее интересна форма параллельного цикла. Она включает в себя три части: генератор пространства итераций, тело цикла и формирователь возвращаемых значений.
SISAL-программа представляет собой набор функций, допускающих частичное применение, т.е. вычисление при неполном наборе аргументов. В таком случае по исходному определению функции строятся его проекции, зависящие от остальных аргументов, что позволяет оперативно использовать эффекты смешанных вычислений и определять специальные оптимизации программ, связанные с разнообразием используемых конструкций и реализационных вариантов параллельных вычислений.
function Sum (N); % Сумма квадратов result (+ ( sqw (1 .. N)));
Пример 11.6.
Обычно рассматривают оптимизации, обеспечивающие устранение неиспользуемого кода, чистку циклов, слияние общих подвыражений, перенос участков повторяемости для обеспечения однородности распараллеливаемых ветвей, раскрутку или разбиение цикла, втягивание константных вычислений, уменьшение силы операций, удаление копий агрегатных конструкций и др.
Основные идеи языков параллельного программирования APL и VAL, предшественника языка Sisal, были интересно обогащены в языке БАРС [[87]] в трех направлениях:
в качестве базовой структуры данных были выбраны комплексы, представляющие собой нечто вроде размеченных множеств с возможностью обозначить кратность вхождения элементов,описание элементов памяти могло сопровождаться предписанием дисциплины доступа к памяти,средства управления асинхронными процессами включали механизм синхросетей, позволяющий согласовывать функционирование узлов из независимо представленных фрагментов.
Синхросети позволяют независимые описания процессов синхронизовать в терминах разметки. Узлы с одинаковой разметкой срабатывают одновременно. Полное представление об асинхронных процессах, их эффективности и проблемах организации дают работы по сетям Петри [[15]].
Современное параллельное программирование не ограничено проблемами применения многоядерных архитектур. Параллельные процессы возникают при функционировании информационных сетей и применении распределенных информационных систем во многих сферах деятельности, связанных с автоматизацией бизнеса, транспорта, образования и др.
и вычисление результата цикла end
|
For % инициирование цикла Approx := 1.0; Sign := 1.0; Denom := 1.0; i := 1 while i <= Cycles do % предусловие завершения цикла Sign := -Sign; % однократные Denom := Denom + 2.0; % присваивания Approx := Approx + Sign / Denom; % образуют i := i + 1 % тело цикла returns Approx * 4.0 % выбор и вычисление результата цикла end for |
| Пример 11.1. Вычисление числа пи |
| Закрыть окно |
|
for i in [1..Cycles/2] do % пространство параллельно исполнимых итераций val := 1.0/real(4*i-3) - 1.0/real(4*i-1); % тело цикла, для каждого i исполняемое независимо returns sum( val ) % выбор и свертка результатов всех итераций цикла end for * 4.0 % вычисление результата выражения |
| Пример 11.2. Это выражение также вычисляет число пи |
| Закрыть окно |
|
for i in [1..2] dot j in [3..4] do % для пар индексов [1,3] и [2,4] returns product (i+j) % произведение сумм end for % = 24 |
| Пример 11.3. В for- выражениях операция dot может порождать пары индексов при формировании пространства итерирования |
| Закрыть окно |
|
for i in [1..2] cross j in [3..4] do % для пар [1,3], [1,4], [2,3] и [2,4] returns product (i+j) % произведение сумм end for % = 600 |
| Пример 11.4. В for- выражениях операция cross может порождать пары индексов при формировании пространства итерирования |
| Закрыть окно |
|
for I := 1 while I < S do K := I; I := old I + 2; % значение из предыдущей итерации J := K + I; returns product(I+J) end for |
| Пример 11.5. Итеративное for-выражение с обменом данными между итерациями |
| Закрыть окно |
| function Sum (N); % Сумма квадратов result (+ ( sqw (1 .. N))); |
| Пример 11.6. |
| Закрыть окно |
Функции высших порядков
Рассматривается аппарат функций высших порядков при организации высококвалифицированных процессов информационной обработки, использующей формализацию и спецификацию данных, таких как синтаксический анализ, кодогенерация, конструирование интерпретаторов и компиляторов по формальному определению реализуемого языка - так называемые синтаксически управлямые методы информационной обработки [[19],[31],[49],[53],[66],[74]].
Конструирование распознавателей
Результативность функций высших порядков Хендерсон показывает на модельной задаче построения распознавателя контекстно-свободного языка, подробно описанной в курсе [[8],[23]]. В качестве примера такого языка рассмотрен синтаксис понятия "слог", образованный из гласных и согласных букв [[23]].
В результате достигнуто синтаксическое подобие определения грамматики и программы построенного распознавателя. Это значит, что определение можно автоматически отобразить в такой распознаватель. Отображение - функция высокого порядка, вырабатывающая в качестве результата распознаватель языка, порождаемого исходной грамматикой.
| Грамматика |
<слог> ::= <в-гр> <а-гр> | <а-гр> <в-гр> | <в-гр> <а-гр> <в-гр> |
| Распознаватель |
(defun is-syllable (x ) (funcall (is-alt (is-chain #'is-b-gr #'is-a-gr) (is-alt (is-chain #'is-a-gr #'is-b-gr) (is-chain #'is-b-gr (is-chain #'is-a-gr #'is-gr)) ) ) x )) |
| Вспомогательные функции |
(defun is-alt (p q) #'(lambda (x) (cond ((funcall p x )T) ((funcall q x) T) (T Nil)))) (defun both (x y) (cond ( x y)(T Nil)) ) (defun is-chain (p q) #'(lambda (x ) (cond ((null x) nil) ((both(funcall p x) (funcall q nil)) T) ((both(funcall p Nil) (funcall q x)) T) ((both(funcall p (cons (car x)Nil)) (funcall q (cdr x)) ) T) (T(funcall (is-chain (lambda(y) (funcall p(cons(car x)y))) (lambda(y)(funcall q y)) ) (cdr x) )) ))) |
Преобразование определений
Конечно, построенное выше определение не отличается эффективностью. Обычно синтаксические формулы приводят к нормализованной форме, гарантирующей полезные свойства распознавателей и удобство их построения. Выбор нормализованной формы и процесс нормализации обосновывается доказательными построениями, на практике воспринимаемыми как эквивалентные преобразования. Преобразования формул - еще один интересный класс задач символьной обработки. Для демонстрации рассмотрим модель реализации функций свертки текстов. При подходящем выборе обозначений такие функции можно применять для преобразования синтаксических формул с целью приведения к нормализованной форме [[8]].
Пусть свертки системы текстов представлены в стиле самоописания подобно формам Бекуса-Наура списком вида:
( (Тексты (Имя Вариант ...)...) ; первое имя - обозначение системы текстов ; за ним следуют варианты поименованных текстов
(Вариант Элемент ...) ; Вариант представляет собой последовательность Элементов
(Элемент Имя Лексема (Варианты)) ; Элемент - это или Имя, или Лексема, или Варианты в скобках )
Построение свертки системы текстов выполняется функциями unic, ass-all, swin, gram, bnf:
(defun unic (vac) (remove-duplicates (mapcar 'car vac) )) ;; список уникальных начал
(defun ass-all (Key Vac) ;; список всех вариантов продолжения, ;; что может идти за ключом (cond ((Null Vac) Nil) ((eq (caar Vac) Key) (cons (cdar Vac) (ass-all Key (cdr Vac)) )) (T (ass-all Key (cdr Vac)) ) ) )
(defun swin (key varl) (cond ;; очередной шаг свертки ;; снять скобки при отсутствии вариантов ((null (cdr varl))(cons key (car varl))) (T (list key (gram varl)) ) ))
(defun gram (ltext) ;; левая свертка, если нашлись общие начала ( (lambda (lt) (cond ((eq (length lt)(length ltext)) ltext) (T (mapcar #'(lambda (k) (swin k (ass-all k ltext ) )) lt ) ) ) ) (unic ltext) ) )
(defun bnf (main ltext binds) (cons (cons main (gram ltext)) binds))
В результате синтаксические формулы можно приводить к нормализованному виду, пригодному для конструирования эффективного распознавателя с грамматикой текста. Организованные таким образом свернутые формы текстов могут играть роль словарей, грамматик языка, макетов программ и других древообразных структур данных, приспособленных к обработке рекурсивными функциями.
Обратные преобразования представляют не меньший интерес. Их можно использовать как генераторы тестов для синтаксических анализаторов или перечисления маршрутов в графе и других задач, решение которых сводится к обходу деревьев.
Построение развертки, т.е. системы текстов по их свернутому представлению, выполняется функциями names, words, lexs, d-lex, d-names, h-all, all-t, pred, sb-nm, chain, level1, lang.
Функции names, words и lexs задают алфавит и разбивают его на терминальные и нетерминальные символы на основе анализа их позиций в определении.
(defun names (vac) (mapcar 'car vac)) ;; определяемые символы
(defun words (vac) (cond ;; используемые символы ((null vac) NIL) ((atom vac) (cons vac NIL )) (T (union (words(car vac)) (words (cdr vac)))) ))
(defun lexs (vac) (set-difference (words vac) (names vac))) ;; неопределяемые лексемы
Функции d-lex и d-names формируют нечто вроде встроенной базы данных, хранящей определения символов для удобства дальнейшей работы.
(defun d-lex ( llex) ;; самоопределение терминалов (mapcar #'(lambda (x) (set x x) ) llex) )
(defun d-names ( llex) ;; определение нетерминалов (mapcar #'(lambda (x) (set (car x )(cdr x )) ) llex) )
Функции h-all, all-t и pred раскрывают слияния общих фрагментов системы текстов.
(defun h-all (h lt) ;; подстановка голов (mapcar #'(lambda (a) (cond ((atom h) (cons h a)) (T (append h a)) ) ) lt) )
(defun all-t (lt tl) ;; подстановка хвостов (mapcar #'(lambda (d) (cond ((atom d) (cons d tl)) (T(append d tl)) ) ) lt) )
(defun pred (bnf tl) ;; присоединение предшественников (level1 (mapcar #'(lambda (z) (chain z tl )) bnf) ))
Функции sb-nm, chain и LeveL1 строят развернутые, линейные тексты из частей, выполняя подстановку определений, сборку и выравнивание.
(defun sb-nm (elm tl) ;; подстановка определений имен (cond ((atom (eval elm)) (h-all (eval elm) tl)) (T (chain (eval elm) tl)) ) )
(defun chain (chl tl) ;; сборка цепочек (cond ((null chl) tl) ((atom chl) (sb-nm chl tl))
((atom (car chl)) (sb-nm (car chl) (chain (cdr chl) tl) ))
(T (pred (all-t (car chl) (cdr chl)) tl)) ))
(defun level1 (ll) ;; выравниваие (cond ((null ll)NIL) (T (append (car ll) (level1 (cdr ll)) )) ))
На основе приведенных вспомогательных функций общая схема развертки языка по заданному его определению (свертке) может быть выполнена функцией lang:
(defun lang ( frm ) ;; вывод заданной системы текстов (d-lex (lexs frm)) (d-names frm) (pred (eval (caar frm)) '(()) ) )
Цель преобразования синтаксических формул при определении анализаторов и компиляторов можно проиллюстрировать на схеме рекурсивного определения понятия "Идентификатор":
Ид ::= БУКВА | Ид БУКВА | Ид ЦИФРА
Удобное для эффективного синтаксического разбора определение имеет вид:
Ид ::= БУКВА | БУКВА КонецИд
КонецИд ::= БУКВА КонецИд | ЦИФРА КонецИд | ПУСТО
Синтаксическая диаграмма анализатора
Ид----БУКВА-----КонецИд-----------.------ ПУСТО -------> | | |--<--БУКВА--<--| | | \--<--ЦИФРА--<-'
Этот пример показывает, что удобные для анализа формулы приведены к виду, когда каждую альтернативу можно выбрать по одному текущему символу. Система CLOS поддерживает ООП с выделением методов для одноэлементных классов, распознаваемых простым сравнением. Тем самым обеспечено удобное построение программ над структурами, подобными нормализованным формам.
Например, определение:
<а-гр> ::= А | А <а-гр>
<в-гр> ::= В | В <в-гр>
<слог> ::= <а-гр> <в-гр> | <в-гр> <а-гр> | <в-гр> <а-гр> <в-гр>
можно привести к виду, не требующему возвратов при анализе (в фигурных скобках - внутренние альтернативы):
<а-гр> ::= А <а-кон> <а-кон> ::= <пусто> | A <а-кон>
<в-гр> ::= B <в-кон> <в-кон> ::= <пусто> | B <в-кон>
<слог> ::= A <а-кон> B <в-кон> | B <в-кон> A <а-кон> <в-кон>
Если программирование сводит алгоритм решения задачи к программе из определенной последовательности шагов, то конструирование строит программу решения задачи из решений типовых вспомогательных задач. Для задачи реализации языка программирования ключевой (но не единственной) типовой задачей является определение реализуемого языка. Ее решение открывает возможности автоматизированного конструирования анализаторов и компиляторов. Автоматизацию конструирования системы программирования обеспечивают методы синтаксического управления обработкой информации и методы смешанных/частичных вычислений, позволяющие выводить определение компилятора программ из определения интерпретатора.
Все это хорошо изученные задачи, имеющие надежные решения, знания которых достаточно для создания своих языков программирования и проведения экспериментов с программами на своих языках. Существует ряд программных инструментов, поддерживающих автоматизацию процесса создания и реализации языков программирования и более общих информационных систем обработки формализованной информации, например YACC, LEX, Bison, Flex, основные идеи применения которых достаточно близки изложенным выше методам обработки формул и текстов.
Интересны предложения по новым синтаксическим формам в языке SETL и новом PYTHON с активным использованием двумерной геометрии текстов для выделения блоков и других конструкций [[49],[50]].
Ранжирование функций
Применение функций высших порядков (ФВП) характерно при решении задач регулярной обработки формализованной информации. Подобные задачи возникают при реализации и настройке сложных информационных систем, таких как операционные системы, системы программирования, текстовые и графические процессоры, системы управления базами данных, поддержки проектов и т.п. Рассмотрим технику применения ФВП на примере функционалов языка Лисп.
Функции высших порядков используют другие функции в качестве аргументов или вырабатывают в качестве результатов.
(defun mul-N (N) #'(lambda (x) (* x N))) ; конструктор семейства функций, множащих аргумент на N
(funcall (mul-N 25) 7) ; применение частной функции, умножающей на 25
Правильность выражений с такими функциями требует корректной подстановки параметров и учета ранга функции, определяющего возможность манипулирования функциональными значениями. Функции можно ранжировать на основе так называемых типовых выражений, представляющих области определения и значения функций. Задание типов данных может требоваться языком программирования или быть представимо в виде комментария. Методы таких представлений рассмотрены в курсе [[23],[8]].
Например, можно ввести обозначения:
Atom - атомы, Number - число, List (X) - NIL или списки из элементов типа X, Bool - NIL или T,' Some - любой объект.
Типовые выражения для элементарных функций:
cons : (X List (X)) -> List (X) car : List (X) -> X cdr : List (X) -> List (X) eq : (Atom Atom) -> Bool at : Some -> Bool : (Atom -> T) & (List (X) -> NIL) nl : Some -> Bool : (NIL -> T) & (Atom \=NIL -> NIL) & (List (X)\=NIL -> NIL)
Таким же образом можно специфицировать интерпретатор:
eval : (Some List( (Atom . Some ) )) -> Some |__ могут попасть неправильные выражения
apply : (List(Some ) -> Some List(Some ) List((Atom . Some)) ) -> Some
Отображающий функционал также может характеризоваться типовым выражением:
map- : ( List(X) (X->Y) ) -> List(Y)
(defun map- (x f) (cond (x (cons (funcall f (car x)) (map- (cdr x) f ))))) (map- '((1) (2) (3)) #'car )
Можно построить функцию, непосредственно преобразующую свой функциональный аргумент в новую функцию.
mapf : List(X->Y) ->( List(X) -> List(Y))
(defun mapf (f) #'(lambda (x) (cond (x (cons (funcall f (car x)) (funcall (mapf f ) (cdr x)) ))) )) (funcall (mapf #'car ) '((1) (2) (3)) )
Аргумент может быть списком функций, результаты которых следует собрать в общий список.
manyfun : List(X->Y) -> (X -> List(Y))
(defun manyfun (lf) #'(lambda (x) (cond (lf (cons (funcall (car lf) x) (funcall (manyfun (cdr lf)) x) ))) )) (funcall (manyfun '(car cdr length)) '(1 f (2 T) (3 D e)) )
Таким образом можно как бы "просачивать" определения функций над простыми данными по структурам данных и тем самым распространять простые функции на сложные данные подобно матричной арифметике. Такой стиль работы характерен для теории комбинаторов и языка FORTH [[3]]. Похожие построения предлагаются Бэкусом в его программной статье о функциональном стиле программирования и в языке APL, ориентированном на обработку матриц [[16]].
Существует ряд языков функционального программирования, требующих или допускающих спецификацию объектов, что, кроме дисциплины программирования, дает средства для корректной работы с пакетами, сопряжения с модулями на других языках, оптимизирующих преобразований, распараллеливания и верификации программ (Sisal, ML и др.) [[84]].
Компиляция. Венский метод. Операционная семантика
Функциональный подход к программированию наиболее убедительно выражен в Венской методике определения языков программирования. Эта методика разработана в конце 60-х годов [[74]]. Основная идея - использование абстрактного синтаксиса и абстрактной машины при определении семантики языка программирования. Конкретный синтаксис языка отображается в абстрактный - анализ, а абстрактная машина может быть реализована с помощью конкретной машины - кодогенерация, причем и то, и другое может иметь небольшой объем и невысокую сложность. Сущность определения языка концентрируется в виде так называемой семантической функции языка, выполняющей переход от абстрактного синтаксиса к абстрактной машине - трансляцию.
При такой архитектуре компилятор можно рассматривать как три комплекта функций, обеспечивающих анализ программы, ее трансляцию и кодогенерацию. Главная задача анализа - обнаружить основные понятия и выделить, вывести или вычислить по тексту программы значения компонентов структуры, представляющей собой абстрактный синтаксис программы. Эта работа сводится к набору распознавателей и селекторов, названия которых могут быть выбраны в зависимости от смысла понятий, составляющих программу, а реализация варьируется в зависимости от конкретного синтаксиса языка. Тогда при любом конкретном синтаксисе разбор программы выполняется тем же самым определением, что и анализ ее абстрактного представления, которое играет роль спецификации. Любое определение анализа выглядит как перебор распознавателей, передающих управление композициям из селекторов, выбирающих существенные компоненты из анализируемой программы и заполняющих поля определенной структуры или значениями, или программами их вычисления. Содержимое полей предназначено для генерации кода программы, эквивалентной исходному тексту программы, а заодно и ее абстрактной структуре.
Например, если лисповскую форму PROG рассматривать как представление абстрактного синтаксиса для подмножества языка Паскаль, содержащего переменные, константы, арифметические операции и сравнения, пустой оператор, присваивание, последовательное исполнение операторов, условный оператор и безусловный переход goto, то необходим набор распознавателей, выявляющих эти понятия, и селекторов, выделяющих их характеристики.
Селекторы имеют смысл лишь при истинности соответствующего распознавателя.
Использование списочных форм в качестве абстрактного синтаксиса позволяет все распознаватели свести к анализу головы списка
| (перем X) | X |
| (конст C) | C |
| (плюс А1 А2) | (A1 + A2) |
| (равно А1 А2) | (A1 = A2) |
| (пусто) | |
| (присвоить X A) | x := a; |
| (шаги S1 S2) | S1; S2; |
| (если P ST SF) | if p then ST else SF; |
| (пока P S) | while p do S; |
Определение семантической функции, обеспечивающей корректную трансляцию абстрактного синтаксиса программы в ее абстрактный код, требует реализации соответствия между именами и их значениями в зависимости от контекста и предшествующих определений.
При интерпретации такое соответствие представлялось ассоциативным списком, в котором хранятся связи вида Имя-Смысл, преобразуемые по принципу стека, естественно отражающего динамику вызова функций. При компиляции не принято сохранять имена на время исполнения программы: их роль выполняют сопоставленные именам адреса. Поэтому вместо а-списка вида ((а . 1)(в . 2)(с . 3)...) применяется два списка (а в с ...) и (1 2 3 ...), хранящих имена и их значения на согласованных позициях. Обрабатываются эти два списка синхронно: оба удлиняются или сокращаются на одинаковое число элементов.
Можно переписать Eval-Apply с соответствующей коррекцией и определить функцию подстановки, заменяющую имена их значениями из синхронного списка.
Определение Eval-Apply особенно компактно в стиле p-списка. Иерархию определений можно организовать с помощью блоков Flet со списками определений для шаблонов (перем конст плюс равно) и отдельно для (пусто присвоить шаги если пока).
Важно обратить внимание на учет изменения контекста при последовательном выполнении шагов программы, а также на несовпадение порядка в тексте с очередностью выполнения композиций функций.
Формально операторы могут рассматриваться как функции, преобразующие полное состояние памяти V. Пусть функция E списочному представлению оператора сопоставляет эквивалентную ему Лисп-функцию, вызываемую в контексте (declare (special N)).
| C | (lambda (v)c) |
| (конст C) | |
| X | (lambda (v) (assoc-i X N v)) N - свободная переменная, задающая список имен, известных в программе |
| (перем X) | |
| (A1 + A2) | (lambda (v) (+(Е А1)(У А2))) |
| (плюс А1 А2) | |
| (A1 = A2) | (lambda (v)(=(Е А1)(У А2))) |
| (равно А1 А2) | |
| (пусто) | (lambda (v)v) Состояние памяти неизменно |
| x := a; | Замена происходит по указанному адресу (lambda (v)(replace N v X (E A))) |
| (присвоить X A) | |
| S1; S2; | (lambda (v) (E S2 (E S1 v))) |
| (шаги S1 S2) | |
| if e then ST else SF; | (lambda (v) (funcall (cond (((E P)v) (E S1)) (T(E S2)) ) v) |
| (если P ST SF) | |
| while e do S; | Циклу соответствует безымянная функция, строящая внутренний контекст: (lambda (W) ((lambda (v) (cond (((E P)v)(w ((E S)v))) (T v))) (lambda (v) (cond (((E P)v) (w ((E S)v))) (T v))) )) |
| (пока P S) |
все аргументы убраны из стека;результат выражения записан в стек.
(defun compile-(s)(append (comp- s Nil)"(Ap Stop)))
(defun comp- (S N)(cond
((atom S) (list "LD (adr S N)))
((eq (car S)"QUOTE) (list "LDC (cadr S))) ((eq (car S)"CONS) (append (comp-(caddr S)N) (comp-(cadr S)N) "CONS)) ((eq (car S)"CAR) (append (comp-(cadr S)N) "CAR)) ((eq (car S)"+) (append (comp-(cadr S)N) (comp-(caddr S)N) "ADD))
((eq (car S)"IF) (let ( (then (list (comp-(caddr S)N) "(JOIN))) (else (list (comp-(cadddr S)N) "(JOIN)))) (append (comp-(cadr S)N) (list "SEL then else))))
((eq (car S)"LAMBDA) (list "LDF (comp-(caddr S) (append (cadr S) N)) "RTN))
((eq (car S)"LET) (let* ((args (value (cddr S))) (mem (cons (var (cddr S)) N)) (body (append (comp-(cadr S)mem) "RTN))) ((append (map #"(lambda(x)(comp- x N)) args) (list body 'AP)))))
((eq (car S)"LABEL) (let* ((args (value (cddr S))) (mem (cons (var (cddr S)) N)) (body (append (comp-(cadr S)mem) "RTN))) ((append "(DUM) (map #"(lambda(x)(comp- x mem)) args) (list "LDF body "RAP)))))
(T (append (map #"(lambda(x)(comp- x N)) (cdr S)) (list body "AP)) ) ))
Листинг 13.3. Определение Лисп-компилятора на Лиспе
Современные методы организации компиляторов и систем программирования претерпевают значительные изменения под давлением изменяющихся условия эксплуатации ИС в сетях, на суперкомпьютерах и в мобильных устройствах. Возрастает роль компиляции "на лету" и организации высокопроизводительных вычислений на многопроцессорных комплексах.
Компилятор и требования к коду программы
Компиляция программ может рассматриваться как один из методов оптимизации процессов, осуществляемый как символьное преобразование - трансляция с исходного языка высокого уровня на язык низкого уровня, допускающий оптимизирующую кодогенерацию [[30],[40],[58],[60],[68],[69]].
Описанная ранее абстрактная машина SECD удобна для спецификации машинно-зависимых аспектов семантики Лиспа. Такой подход позволяет не загромождать определение компилятора, добиться его прозрачности, но главное, такое определение может быть машинно-независимым и переносимым [[23]].
В этом отношении следует отметить:
единое пространство функций, их аргументов и всех обозначений, роль которых определяется по контексту при интерпретации форм;разрешение функциональных переменных, значение которых конструируется (вычисляется) в процессе их интерпретации. Это позволяет вводить частичные определения, уточняемые по мере необходимости;самоопределение основных механизмов символьной обработки и, следовательно, открытый характер системы программирования, поддерживающей функциональное программирование;мягкость пространтственно-временных ограничений, без точных численных оценок по отдельным параметрам;поощрение рекурсивных определений;предельная уточняемость и детализируемость определений, управление временем их существования и выполнения.
Компилятор - это средство оптимизации, позволяющее программам работать во много раз быстрее, чем было бы при интерпретации.
Использование в системах программирования пары интепретатор-компилятор при написании большой программы позволяет отлаживать отдельные функции, используя интерпретатор, а компилировать только те из них, которые уже хорошо отлажены. Такая пара обладает большей гибкостью и универсальностью, чем традиционная пара отладчик-компилятор.
Программист получает следующие преимущества:
Нет необходимости компилировать все функции, которые используются лишь эпизодически. Интерпретатору доступны скомпилированные функции. Компилированные функции, использующие интерпретируемые функции, могут вычислять их непосредственно при счете.Порядок выполнения компиляции не имеет значения.
Даже нет необходимости определять все функции до тех пор, пока они не понадобятся при счете.Лишь в компилируемых функциях свободные переменные должны объявляться до компиляции функций.
Последнее требование проясняет роль типового контроля в стандартных, ориентированных на компиляцию без интерпретации, системах программирования. Компиляция всех объектов осуществляется без анализа фактических данных, а это и означает, что на момент компиляции переменные, как правило, являются свободными. Интерпретация располагает более полной информацией, связывающей необходимые для вычислений переменные с конкретными значениями, тип которых определен.
Когда переменная используется как свободная, это значит, что она должна быть связана на более высоком уровне. При интерпретации функций может быть обнаружена переменная, не связанная вообще, о чем система известит пользователя соответствующим диагностическим сообщением об ошибке.
При трансляции функций в подпрограммы переменные отображаются в адреса при распределении памяти, в которой размещаются значения аргументов. Для обычных переменных распределение памяти - это стек. Другие функции не могут знать адреса таких переменных, что и не позволяет рассматривать их как свободные.
Ленивые вычисления
Средства управления процессами изначально опираются на интуитивное представление о вычислении выражений, согласно которому функция применяется к полному списку заранее вычисленных аргументов.
Результат управления вычислениями проявляется в изменении некоторых оценок, например можно влиять на эффективность и надежность программ, обусловленную целостностью объемных, сложных данных, избыточностью вычислений, возможно, бесполезных выражений, необоснованной синхронизацией формально упорядоченных действий. Подобные источники неэффективности могут быть устранены достаточно простыми методами организации частичных вычислений с учетом дополнительных условий для их фактического выполнения, таких как достижимость или востребованность результата вычислений, что и обеспечивается моделью ленивых вычислений.
Любое очень объемное, сложное данное можно вычислять "по частям". Рассмотрим вычисление списка
(x1 x2 x3 ... )
Можно вычислить элемент x1 и построить структуру:
(x1 (рецепт вычисления остальных элементов))
Получается принципиальная экономия памяти ценой незначительного перерасхода времени на вспомогательное построение. Процесс вычислений начат, не ожидая полного списка аргументов. Рецепт - это ссылка на уже существующую программу, связанную с контекстом ее исполнения в момент построения рецепта. Рассмотрим как расширяется пространство реализационных решений в рамках модели ленивых вычислений с использованием рецептов.
(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M (ряд_цел (1+ M) N)))))
(defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( сумма (cdr X))))) )
Пример 13.1. Построение ряда целых от M до N с последующим их суммированием. Обычная формула
Введем специальные операции || - приостановка вычислений и @ - возобновление ранее отложенных вычислений. Избежать целостного представления ряда целых можно, изменив формулу:
(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M ( || (ряд_цел (1+ M) N))))))
(defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( @ ( сумма (cdr X))))) ))
Чтобы исключить повторное вычисление совпадающих рецептов, в его внутреннее представление вводится флаг, имеющий значение T - истина для уже выполненных рецептов, F - ложь для невыполненных.
Тогда в выражении (all (cons { 1 | 2 } || (цел 3 100 )) второй аргумент cons выполнится только для одного варианта, а для второго подставится готовый результат. Таким образом, рецепт имеет вид:
{ ( F e AL ) | ( T X ) },
где X = ( eval e AL ).
Это заодно позволяет распространить понятие данных на бесконечные, рекурсивно-вычислимые множества. Например, можно работать с рядом целых больших, чем N.
(defun цел (M) (cons M ( || (цел (1+ M) ))))
Можно из организованного таким образом списка выбирать нужное количество элементов, например первые K элементов можно получить по формуле:
(defun первые (K Int) (cond ((= Int Nil) Nil) ((= K 0) Nil) (T (cons (car Int)( первые ( @ (cdr Int))) )) ))
Эффект таких приостанавливаемых и возобновляемых вычислений получается путем следующей реализации операций || и @:
||e = > (lambda () e ) @e = > (e ),
что при интерпретации приводит к связыванию функционального аргумента с ассоциативным списком для операции || и к вызову функции EVAL для операции @.
Обычно в языках программирования различают вызовы по значению, по имени и по ссылке. Техника приостановки и возобновления функций при ленивых вычислениях может быть названа вызовом по необходимости.
В некоторых языках программирования, таких как язык SAIL и Hope - lazy evaluation основная модель вычислений.
Более подробно о тонкостях определения ленивых вычислений рассказано в книге Хендерсона [[23]].
Оптимизация программ
Оптимизирующая компиляция - традиционная область применения формальных методов преобразования программ и процессов, большинство которых по существу сводятся к перестановке тех или иных конструкций в тексте или коде программы. Образно говоря, при оптимизации программы анализируется серия ее функциональных эквивалентов, из которых следует выбрать наилучший по заданным критериям, набор которых зависит от условий применения программы. Компиляция и распараллеливание программ для их эффективного исполнения в сетях или на суперкомпьютерах - примеры таких оптимизаций. Оптимизационное программирование - предмет данной лекции.
Рассматривается эффективное обобщение процесса информационной обработки, вытекающее из возможности отложенных действий (lazy evaluation). Анализируются резервы производительности обобщенных процессов и методы динамической оптимизации вычислений, приводящие к смешанным и параллельным вычислениям.
с последующим их суммированием. Обычная
|
(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M (ряд_цел (1+ M) N))))) (defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( сумма (cdr X))))) ) |
| Пример 13.1. Построение ряда целых от M до N с последующим их суммированием. Обычная формула |
| Закрыть окно |
| X * 0 = 0 car (A …) = A X*1 = X ;; при любом X X-X = 0 X/X = 1 |
| Пример 13.2. |
| Закрыть окно |
|
(defun compile-(s)(append (comp- s Nil)"(Ap Stop))) ( defun comp- (S N)(cond ((atom S) (list "LD (adr S N))) ((eq (car S)"QUOTE) (list "LDC (cadr S))) ((eq (car S)"CONS) (append (comp-(caddr S)N) (comp-(cadr S)N) "CONS)) ((eq (car S)"CAR) (append (comp-(cadr S)N) "CAR)) ((eq (car S)"+) (append (comp-(cadr S)N) (comp-(caddr S)N) "ADD)) ((eq (car S)"IF) (let ( (then (list (comp-(caddr S)N) "(JOIN))) (else (list (comp-(cadddr S)N) "(JOIN)))) (append (comp-(cadr S)N) (list "SEL then else)))) ((eq (car S)"LAMBDA) (list "LDF (comp-(caddr S) (append (cadr S) N)) "RTN)) ((eq (car S)"LET) (let* ((args (value (cddr S))) (mem (cons (var (cddr S)) N)) (body (append (comp-(cadr S)mem) "RTN))) ((append (map #"(lambda(x)(comp- x N)) args) (list body 'AP))))) ((eq (car S)"LABEL) (let* ((args (value (cddr S))) (mem (cons (var (cddr S)) N)) (body (append (comp-(cadr S)mem) "RTN))) ((append "(DUM) (map #"(lambda(x)(comp- x mem)) args) (list "LDF body "RAP))))) (T (append (map #"(lambda(x)(comp- x N)) (cdr S)) (list body "AP)) ) )) |
| Листинг 13.3. Определение Лисп-компилятора на Лиспе |
| Закрыть окно |
Смешанные вычисления
Идея смешанных вычислений с точки зрения реализации близка технике ленивых вычислений, но сложилась концептуально из несколько иных предпосылок, и именно из опыта разработки оптимизирующих трансляторов для языков высокого уровня [[39]]. Рассматривается пара Программа-Данные при недостаточных данных, отображаемая в так называемую остаточную программу, которая может дать нужный результат, если дать недостающие данные. Для определения такого отображения понадобилась разметка действий программы на исполнимые и задерживаемые. Если такую разметку не связывать с отсутствием данных, то получается модель, практически подобная вычислениям с задержками и возобновлением.
Не всегда неопределенность части данных мешает организовать вычисление. Рассмотрим
(If (< X Y) Z T)
или эквивалент
if X < Y then Z else T
Если X и Y не определены, но известно, что X лежит в интервале [1, 4], а Y в интервале [5, 6], то логическое выражение X<Y определено, и можно сделать вывод относительно выбора ветви условного выражения и, возможно, получить его значение.
Изучение смешанных вычислений может исходить из разных толкований понятия частичности, т.е. функций, определенных не на всей области их существования.
Первые работы Lombardi в этой области посвящены частичным вычислениям, т.е. обработке частично определенных выражений над числами. Реализация такой обработки на Лиспе осуществляла выполнимые операции и строила из полученных частичных результатов и невыполнимых операций некоторый промежуточный результат - выражение, доопределив которое, можно получить полный результат.
В работах по семантике стандартных языков программирования принято сведение к неопределенности значений любых операций, зависящих от неопределенных данных.
Это приводит на практике к необоснованным потерям части определенной информации и результатов.
A_1+...+A_100_000_000_000 + неопределенность -> неопределенность
Можно обратить внимание, что невелика практическая разница в уровне определенности данных вида (A …) и (A F), где F - рецепт вычисления, про который не всегда известно, приведет ли он к получению результата.
Поэтому лучше было бы неопределенные данные "накрывать" рецептами, использующими специальные функции, нацеленные на раскрытие неопределенностей.
Например, роль такой функции может сыграть запрос у пользователя дополнительной информации:
(A …) => (A . ||(read))
В определении интерпретатора обработка неопределенностей сосредоточена в функции ERROR.
(defun eval (e AL) … ((assoc e AL)(cdr (assoc e AL))) (T(ERROR '"неопределенная переменная")) … )
Определение функции ERROR можно доопределить обращением к READ, обрамленным сообщением о ситуации с информацией о контексте.
(defun apply (f args AL) … ((assoc f AL)(apply (cdr (assoc f AL))(evlis args AL)AL)) (T (ERROR '"неопределенная функция")) … )
При отладке сложных комплексов часто неразработанные определения замещают временными "заглушками", которые помогают разобраться в будущей программе по частям. Такую работу можно стандартизировать заданием предварительных определений функций в виде отображения типа аргументов в тип результата. Соответственно, исполнение предопределенной таким образом функции можно интерпретировать как проверку аргументов на соответствие типу аргументов и выдачу в качестве результата вариантов значения, принадлежащего типу результата.
При небольшом числе значений заданного типа, например, истинностные значения, может быть целесообразным полный перебор таких значений с последующим выбором реальной альтернативы пользователем.
(cond (e r)(T g)) => (assoc e (list (cons T (eval r AL)) (cons Nil (eval g AL))) )
Таким образом выполнятся обе ветви, их результаты ассоциируются с различными значениями заданного типа, что позволяет получить нужный результат, как только будет определено ранее не определенное значение. Это позволяет избежать повторного выполнения предшествующих вычислений, если их объем достаточно велик.
Применение библиотечных процедур, зависящих от слишком большого числа параметров, можно упростить для пользователя построением проекций на типовые комплекты трудно задаваемых параметров, понимаемых как определение режима работы процедуры.
(defun f (x y z a b c … v t u) (g …)) (defun Fi (x y z ) (f x y z ai bi ci … vi ti ui))
Примерно это и делает необязательный параметр вида &optional.
Такое построение можно рассматривать как декомпозицию, разделение, сортировку на выполнимые и невыполнимые действия, при которой выполнимые действия в тексте определения замещаются их результатом, а невыполнимые преобразуются в остаточные, что все вместе образует проекцию процедуры на заданную часть ее параметров.
Многие выражения по смыслу используемых в них операций иногда определены при частичной определенности их операндов, что часто используется при оптимизации кода программ.
X * 0 = 0 car (A …) = A X*1 = X ;; при любом X X-X = 0 X/X = 1
Пример 13.2.
Представление функции в некоторых точках при отладке можно задать ассоциативной таблицей:
(setq f '((a1 . r1)(a2 . r2)(a3 . r3) …)) (defun f (x) (assoc x f))
Пример 13.3.
В такое точечное определение легко добавлять недостающие пары, соответствующие нужным демонстрационным тестам при макетировании программ для согласования их функций на начальных этапах разработки.
Возможны и другие, обеспечивающие оптимизацию, компиляцию, предвычисления, макрогенерацию текста программы, что в перспективе может покрыть полное пространство обработки программ в рамках единой методики. Например, основой единого подхода может быть так называемый трансформационный подход, заключающийся в сведении смешанных вычислений к преобразованию программ посредством набора базовых трансформаций.
Динамика представлений программ
Рассматривая программы и программные системы как формы представления знаний, трудно удержаться от попытки исследования динамики представления знаний на основе аналогии с развитием программ и программных систем.
Движущими силами этого развития является возникающая в разных видах деятельности потребность в уточнении представления знаний и установления новой информации, которая раньше не попадала в поле зрения или не было готовности ее понять. Динамика представления знаний сводится к переходу от одного представления к другому.
Успешность деятельности ограничена "пропускной способностью" поля зрения. Это ограничение систематически преодолевается посредством обобщения, приводящего к представлениям более высокого порядка - представлениям более мощным, более организованным, например, к процедурам, функциям, фреймам, шаблонам, макросам. Последовательность шагов обобщения можно называть индуктивным развитием представления знаний. В методике программирования индуктивное развитие соответствует восходящим методам, "снизу вверх". Как правило, индуктивное развитие имеет некоторые пределы. Такие пределы при возрастании меры информативности используемых средств рассматриваются Д. Скоттом [[26]]. Интересен случай, когда пределом является теория, достаточная для порождения всей достоверной информации, установленной на данный момент времени. При разработке программ роль такого предела играет система программирования.
В результате индуктивного развития представления знаний наблюдается тенденция к возрастанию доли средств декларативного характера (таких как описания, отношения, формирователи, типы данных, фреймы, семантические сети, иерархии понятий, аксиоматические системы) в сравнении с долей средств процедурного характера (таких как действия, операции, операторы, процедуры, интерпретаторы, задания). Эта тенденция обуславливает рост популярности дедуктивных методов и может рассматриваться как стимул к переходу от индуктивного развития к дедуктивному. Дедуктивный вывод осуществляет переход от потенциальных знаний к актуальным.
Традиционно для этих целей в системах искусственного интеллекта используется метод резолюций, системы продукций и другие средства. Чередование стадий индуктивного и дедуктивного развития можно рассматривать как обоснование выбора метода программирования в зависимости от уровня развития знаний о решаемой задаче (зрелость, уровень изученности).
Применение развиваемых таким образом представлений может потребовать возврата к менее структурированным средствам (например, для упрощения обратной связи с областью, породившей решаемые задачи или для более тонкой детализации реализационных решений). Такой переход является конкретизацией представления знаний. В методике программирования конкретизация соответствует нисходящим методам "сверху вниз". (Вопреки лингвистической ассоциации нет причин нисходящие методы считать обратными восходящим.)
Независимо осуществляемое развитие приводит к задаче установления эквивалентности между различными системами представления знаний. При решении этой задачи возникают предпосылки для выравнивания потенциала систем (вводятся недостающие понятия, выполняются аналогичные построения, реализуются подобные инструменты). Таким образом, выделено четыре типа переходов: индуктивное и дедуктивное развитие, конкретизация и выравнивание. Эта классификация сопоставима с классификацией трансформаций программ в теории смешанных вычислений, предложенной А.П. Ершовым. [[39]]
Макеты и прототипы
При разработке больших программ, особенно по нисходящей методике, необходимость в тестировании и отладке возникает раньше, чем подготовлен текст программы. Макет программы - это некоторый предварительный ее текст, допускающий уточнение - доопределение.
Простейший макет может быть создан из небольшой коллекции тестов, иллюстрирующих поведение программы в наиболее важных точках. Выбор таких точек - необходимая работа, результаты которой многократно используются на всех фазах жизненного цикла программы: при конструировании алгоритмов, автономном тестировании компонентов программы, комплексной отладке программы, демонстрации программы всем заинтересованным лицам, при ее эксплуатации и развитии. Функционирование простых макетов особенно легко реализуется в языках, обладающих унификацией структур данных и функциональных объектов, таких как Lisp и Setl [[75],[49]].
Setl - язык сверхвысокого уровня, представляет собой попытку активного использования теоретико-множественных понятий в практике программирования [[49]].
Согласно концепции этого языка, понятие "функция" обладает двойственной природой. Функция может быть представлена в алгоритмическом стиле - определением процедуры, выполнение которой сопоставляет результат допустимому аргументу. Но столь же правомерно представление функции в виде графика, отображающего аргументы в результаты. Оба представления могут существовать одновременно - это всего лишь две реализации одной функции. Графическое понимание функции включает в себя и табличную реализацию подобно математическим таблицам Брадиса. Кроме того график функции не обязан быть линией - это может быть фигура произвольных очертаний. Следовательно, аргументу может соответствовать множество результатов, лежащих на пересечении вертикали с этой фигурой - графиком функции. При такой трактовке нет ничего удивительного в постепенном накоплении или построении графика функции. Можно задать небольшое множество точек графика, а потом постепенно его пополнять.
По замыслу Дж. Шварца, автора языка SETL, такая методика может выполнять роль оптимизации особо сложных вычислений.
Более формальный макет может быть построен из спецификаций функций в виде типовых выражений, задающих описание типов аргументов и результатов. Такой макет может работать как "заглушка" для нереализованных компонентов. Вместо них может работать универсальная функция, проверяющая соответствие фактических аргументов предписанному типу данных и вырабатывающая в качестве результата произвольное данное, соответствующее описанию результата. Этот механизм будет более эффективен в паре с простым макетом из тестов, если результат выбирать из коллекции тестов.
Накопление результатов
Не менее ценные следствия из унификации структурных значений и функциональных объектов дает накопительный, кумулятивный эффект ряда сеансов обработки рекурсивных программ, содержащих общие компоненты. Допустимость совместного хранения функциональных определений и тестов для их проверки в общей структуре, например в списке свойств атома, именующего функцию, позволяет строить технологические макеты с множественными определениями, коллекциями тестов и спецификаций, а также с документацией. Такие макеты пригодны для поддержки полного жизненного цикла программы. Они позволяют организовывать оперативное сравнение результатов при обновлении системы функций. На такой основе возможно автоматическое тестирование программ. С практической точки зрения технологические макеты - универсальный инструмент динамической оптимизации прикладных систем.
Представим, что вычисление каждой рекурсивной функции сопровождается сохранением пары <аргумент, результат>. После этого можно запустить в дело слегка измененное правило интерпретации функций. Изменение заключается в следующем: прежде чем применять функцию к фактическому аргументу, выполняется проверка, нет ли для этого аргумента уже вычисленного результата. Готовый результат и есть результат функции, а в противном случае все работает как обычно. Механизм сохранения насчитанных результатов функций назван "мемо-функции" [[64]]. Естественно, основанием для его применения является достаточная сложность и частота обработки [[45]]. Примечательная особенность данного метода - любая сложность очень частых вычислений стремится со временем к линейной.
Ряд особенностей такого инструментария выходит за привычные рамки стандартного программирования и обладает заметной трудоемкостью при расширении ряда используемых языков программирования.
Разработка программ
Сейчас, при бурном распространении пользовательских интерфейсов, нелишне вспомнить, что принципиальная разница в средствах и методах информационной обработки лежит на уровне семантики процессов. Семантическое макетирование в функциональном стиле многое дает для упорядочения и сравнительного анализа компонент информационных систем, работающих с данными разной природы. В качестве примеров рассмотрим семантические модели основных механизмов систем программирования.
Существенна возможность введения частично определенных функций, варьируемых и уточняемых определений, а также специализации интерпретатора программ с целью учета уровня достоверности определений. Рассмотрим построение прототипов систем, опережающее детальную разработку алгоритмов и отладку программ. Основой является процесс уточнения информации о решаемой задаче, продемонстрированный на отдельных примерах и схемах с привлечением частичных функций на доступных типах данных с доведением до полных функций, приспособленных к обработке произвольных данных.
Теоретический каркас
Принимая аксиоматическую теорию множеств за образец грамотно устроенной гибкой теории, попробуем сопоставить с нею доказательные положения, полезные при обосновании и выполнении программистских проектов. Базовые построения в теории множеств выполнены над кумулятивной иерархией множеств, инициированной рядом объектов немножественной природы и пустого множества посредством операции объединения множеств. Кроме того, над множествами определены операции пересечения, дополнения, равенства, вхождения и включения, удовлетворяющие небольшому набору аксиом разной сложности, начина с ассоциативности, коммутативности и т.п., обеспечивающих преобразования и комбинаторику формул.
Аналогично, такие структуры как списки, выстроены над атомами, не разлагаемыми на компоненты, и пустого списка NIL, посредством операции CONS - консолидации. Над списками определены операции, позволяющие разбирать структуры на компоненты, сравнивать и анализировать структуры, отличать атомы от структур и пустой список от других данных. Элементарные операции подчинены аксиомам, обеспечивающим обратимость информационной обработки. Техника программирования на уровне строгих функций поддерживает прозрачность определений и скорость отладки.
Трудоемкость технологий
Устойчивость слабо предсказуемых трудностей программирования достаточно высока. Так, Ф.П. Брукс почти 30 лет назад отмечал неизбежность повторного программирования, морального устаревания результата за время его получения и влияния структуры программистской группы на эффективность трудозатрат. [[6],[7]] Впечатления от трудного опыта разработки OS IBM 360 Ф. Брукса можно характеризовать следующими цитатами из его знаменитой книги [[6]]:
"Система начинает работать как следует только после создания нескольких вариантов, последовавших за первым"
"Неполнота и противоречивость новых идей становится ясной только в процессе реализации"
"На практике оказывается, что все этапы могут начинаться одновременно и проходить параллельно"
"Вторая система - самая опасная из всех, которые проектирует человек"
"Диалоговые интерпретаторы обеспечили наиболее фундаментальные преимущества в отладке"
"Нам не удалось воспитать в программистах походящее отношение к документации"
Логическая ясность идей грамотного программирования Д. Кнута не помогла преодолеть неприязнь программистов к документации [[48]].
При повторном издании (через четверть века!) своей книги [[7]] Ф. Брукс отметил, что основные трудности практического программирования для сложных систем почти не изменились. Современные подходы к разработке ИС скорее являются методами "уклонения от сложностей".
В этом плане отмеченный Бруксом "эффект второй системы" можно избежать погружением разработки первых двух систем на уровень обучения программиста или привлечением напарников, миновавших область действия этого эффекта. [[27]]
Технология экстремального программирования нейтрализуют проблему документирования методикой парной разработки. [[12],[46]]
Концептуальное единство разрабатываемых ИС может обеспечиваться методами ФП с помощью стандартных интерфейсов и визуальных методов, маскирующих эклектику внутренних решений. [[20]]
Функциональное программирование и методика рефакторинга ИС нацелены на оттачивание улучшаемых вариантов типовых компонентов, по сложности как правило не превышающих среднюю олимпиадную задачу и требующих на реализацию от полудня до недели. [[27],[33]]
В начале 70-х годов Дж.М. Вейнберг обратил внимание на частичность понимания целей работы программиста (особенно в сложных проектах), опасность невнимания менеджеров к естественным взаимосвязям в коллективе, разнообразие способностей, необходимых программисту для успешной работы. В основополагающей монографии "Психология программирования" [[77]] Дж. Вейнберг акцентирует внимание на человеческих факторах программирования и показывает, что решение любых сложных проблем начинается с анализа их социально-этической реализуемости. Техническое решение осуществимо, лишь если ясно, кто и почему способен сложную проблему решить.
Э. Дейкстра отмечал ненадежность программирования и связывал это с усложненностью преждевременно программируемых решений задач, обуславливающей ошибки как в реализации, так и в применении таких решений. Провозглашенная им дисциплина программирования нацелена на принцип "сверху вниз", с очевидным обоснованием решений на каждом уровне, с наглядным структурированием программ и со стандартизацией изобразительных средств [[9]].
М.М. Леман указывал на возрастание стоимости сопровождения больших программ и объективность эволюции активно используемых программ [[14]]. Внимание к завершенности фаз ЖЦ программ помогают четко выделить ближайшую цель, концентрировать усилия на ее достижении и тем самым минимизировать перенос трудозатрат с периода разработки на период сопровождения.
А.Л. Фуксман выделил проблему разложения на модули таких программ, как трансляторы, и обеспечения оперативной обратной связи программирования со сферой приложения программ, предложил методику вертикального сложения программ (на основе функциональной структуры) и проверки частичных результатов в реальной обстановке [[67]].
По мнению Э. Йодена [[12]], истинное предназначение программирования - это трудно выполнимые миссии, т.е. проекты, выполняемые при недостаточных условиях, что активизирует творческий потенциал программистов, заставляет быстро находить эффективные и надежные решения.
Эту мысль убедительно подтверждает практика разработки игровых программ. В пользу этого говорит и оценка трудоемкости проектов по классическим схемам ЖЦ программ. Как правило такие оценки завышены во много раз в сравнении с реальными трудозатратами.
Сторонники экстремального программирования (XP) [[46]] выражают претензии программистским авторитетам:
"С самыми лучшими намерениями сформулирован и авторитетно насаждается ряд очень плохих тезисов, из которых были сделаны ошибочные выводы, что привело к беспомощной практике программирования."
Их решение - использовать известный педагогам "парный эффект", освобождающий программиста от изоляции, автоматически дающий "живую документацию", активно использующий интуитивные механизмы самоконтроля в процессе программистского творчества, дающий обратную связь: уточнение правильного пути по ходу программирования. Техника исполнения - игра в планирование, парное программирование, рефакторинг неоднократно используемых фрагментов, простой дизайн, коллективное владение кодом, непрерывная интеграция системы и отказ от перегрузки рабочей недели.
Согласно XP самый удобный и достоверный вид документации - это тесты. Традиционный документ - это обещание, а тест - точная отметка о частичном выполнении задания. XP ставит под сомнение многие традиционные гипотезы о том, каким образом должны разрабатываться ИС, и признает, что люди совершают ошибки. Программиста ошибки не смущают: его работа в том и заключается, что он их в конце концов обнаруживает и исправляет, - это убеждает его в правильности того, что делается. Основной помехой программированию является предрасположенность людей делать усложненные вещи - так легче считать себя умнее.
Сторонники функционально-ориентированной разработки (FDD) ИС дорожат накопленным разнообразием языков для передачи информации компьютеру. [[54]] Соглашаясь с Вейнбергом, что программирование - это, прежде всего, уточнение мысленных моделей в партнерах, учитывают и мнение Джефа де Лука: "ИТ - это 80% психологии и 20% технологии".
Программирование методом добавления функции за функцией позволяет минимизировать интервал между анализом задачи и тестированием ее частичных решений, что сводит задачу разработки ИС до легко контролируемых задач в рамках поддающегося оценке регулярного процесса. Подобно XP, FDD тяготится составлением рабочих отчетов, которые либо являются неточными, из-за чего становятся бесполезными, либо отбирают у проекта драгоценное время: "Нам платят за результаты а не за отчеты! Красивая презентация означает, что руководители потратили время и средства на нее вместо обеспечения целевых работ".
Роль рефакторинга здесь выполняет функциональная декомпозиция, которую доверяют главным программистам. Высоко ценится понимание программистами границ своих знаний: "Лучше сказать, что ответ неизвестен, чем гадать и оказаться неправым. Специалисты по предметной области не виноваты в отступлениях от здравого смысла, принятых в этих областях. Нужно задавать вопросы. Непонятное одному скорее всего непонятно и другим".
Жизненный цикл
Проблема трудоемкости программирования ждет своего решения с давних пор. Ее сложность проявляется по мере накопления опыта обеспечения критических характеристик ИС, таких как надежность и производительность. Полезно совмещение восходящих и нисходящих методов разработки компонентов. Главное - пространство для маневра, возможность согласованного уточнения решений на всех уровнях определения компонентов.
Можно заметить, что основные трудности практического программирования связаны с неполнотой учета структуры ЖЦ программ, а предлагаемые пути являются разными формами наследования успешного опыта. Путь к надежному программированию лежит через достижение многократности использования важных решений, принимаемых на протяжении полного ЖЦ, а не только в процессе программирования [[12],[14],[22],[46],[48],[54],[61]]. Длительность ЖЦ программ зависит от его модели и связана с методами повышения уровня изученности решаемых задач.
Подробный обзор классических моделей жизненного цикла (ЖЦ) программ приведен в [[61]], где отражено соответствие детализации абстрактного пространства, в котором осуществляется управление проектами, сложности решаемых задач. Начиная с грубого упорядочения произвольной деятельности до весьма витиеватой спирали, позволяющей зрительно представлять эволюционные витки и версии развития ИС, менеджер может в принципе понять и на деле осуществить процесс постановки неочевидных вопросов, определяющих и усложняющих разработку информационных систем.
Практический выбор модели ЖЦ проектируемой программы требует конкретных оценок трудоемкости предлагаемых подходов, ее зависимости от доступной информации и квалификации программистов. Для обоснования таких оценок рассмотрим наиболее типичные особенности процесса разработки ИС и их компонентов. Обычно разработка ИС развивается примерно следующим чередом.
Требуется организовать обработку множества определенных данных. Обработка понимается как класс процессов, порождаемый программами, соответствующими предварительно подготовленному проекту, спецификации, требованиям.Пишется версия программы и предпринимается ряд попыток с ее помощью осуществить отдельные процессы над небольшими образцами данных.Форсируется расширение программы, контролируемое тестированием на "представительном" наборе образцов.Демонстрируется работа с программой. Обнаруживается, что что-то необходимо доделать, пока не появится практичная версия.Практичная версия порождает более разнообразное применение программы. Время от времени предпринимается улучшение программы и возникают версии программы.
Вдруг оказывается, что очередное улучшение требует чрезмерных трудозатрат. Рост работоспособности программы исчерпан. Начинается новый виток с небольшими вариациями. Трудоемкость очередных витков возрастает, и восходящие линии в развитии ИС преимущественно обрываются. Эта картина смягчается (или затушевывается) вовлечением в процесс разработки программ вспомогательных СП и средств ведения проектов. Удобство, как критерий приемлемой трудоемкости, достигается ценой следующих уступок:
обрабатываются лишь данные, легко представимые входным ЯП;нужными считаются понятия и действия, удобно реализуемые в СП;полезными признаются процессы, организация которых не влечет больших трудозатрат.
Если уступки по каким-то причинам невозможны, то СП признается неподходящей для применения в соответствующем классе задач. Если уступки возможны, то успешность разработки ИС в значительной мере определяется умением прогнозировать развитие требований пользователя, своевременно улучшать программу или производить новые ее версии, убедительно демонстрируя возрастание качества ИС.
Опыт применения ЯП и их конструирования показывает, что представления программ и соответственно требования к ЯП подвержены единой динамике, связанной с проявлением общих объектов и процессов при решении расширяемых задач (уровень изученности). Каждый уровень изученности достижим при соответствующем уровне организованности процессов и объектов. Динамику требований к качеству ИС можно описать следующими уровнями изученности решаемых задач и областей применения их решений.
Концептуальный минимум. Достаточно любого демонстрационого образца с минимальной организованностью и работоспособностью, лишь бы он дал правильные ассоциации.Потенциальный максимум. Необходим максимальный уровень организованности и работоспособности без особых требований к производительности, так как главное - уяснить принципиальные возможности. Определяется максимально полный каркас будущей работы и фокусируется ее базис.Практичный компромисс. Допустим меньший уровень организованности, т.е. нужны не все возможные процессы, а лишь достаточно практичные. Возрастает потребность в эффективности, но не в ущерб удобству. Предельный баланс. Обнаруживается необходимость в организации некоторого класса процессов, даже если это потребует высоких трудозатрат. Требуемый уровень организованности может возрасти.
На каждом уровне изученности области применения ИС различны требования к дружелюбию интерфейса, его лексико-фразеологическому оформлению, к диагностичности, к полноте и улучшаемости реализованных решений и к другим свойствам. Можно параллельно реализовывать ИС, расширяя ее по мере готовности разработчиков и пользователей.
Переход от программ к компонентам позволяет фазы и модели ЖЦ сопоставить с характером изменения информации о компонентах. Такое сопоставление показывает истоки проблем организации разработки ИС. Классическим моделям ЖЦ присущи длинные интервалы локализованного уточнения информации на одном уровне, что затрудняет проверку отношений между уровнями. Подходы XP и FDD позволяют непрерывную проверку таких отношений - всегда существует обратная связь при развитии постановки задачи.
Исследование моделей ЖЦ компонентов дает перспективу единого подхода к развитию и согласованию разнородной информации о компонентах ИС и решаемых с их помощью задачах. Это может обеспечивать непрерывное согласование процессов разработки и сопровождения ИС.
Ряд практичных многоязыковых подходов к разработке программ предлагает Uml. [[86]] Хочется отметить следующее:
инструментарий обратного проектирования,множественность представлений программ с разных точек зрения,сочетание образных диаграмм с языковыми средствами,возможность пошаговой детализации разносортных структур данных и управления.
Тенденция к многоязыковости отражает актуальность интеграции средств и методов, используемых на разных фазах ЖЦ программ, что ведет к парадигме полного жизненного цикла эволюционирующих компонент информационных систем.
Анализ функционирования
Проектировщик РИС безусловно нуждается в возможности прогнозировать эксплуатационные характеристики и производительность независимо создаваемых компонентов, доступных на уровне проекта, но без их использования в приложении. Прогресс в решении этой задачи обычно достигается ценой сокращения усилий на прототипирование, например, благодаря автоматизированной генерации систем тестов. Тестирование прототипа придает очевидность пригодности проектируемой архитектуры приложения, но оно неэффективно при прогнозировании производительности.
Производительность зависит от следующих факторов:
поведение компонентов и их взаимодействие,частности реализации компонентной инфраструктуры,выбор конфигурационных установок,установка аттрибутов как для компонентов приложения, так и для компонентов инфраструктуры,одновременная загрузка запросов.
Это вынуждает повышать производительность ИК поиском определенной топологии соединений компонентов, обеспечением устойчивости сообщений и контролем потоков данных, что приводит к специальной компонентной технологии, дающей уверенность в достаточной надежности прогноза, более оперативного, чем прототипирование с тестированием.
Чтобы преодолеть усложненность анализа критических свойств РИС, нужен новый подход в контексте композируемости и повторного использования компонентного анализа при конструировании систем из компонентов. Такие свойства для систем должны выводиться из свойств подсистем или компонентов. Нужен механизм описания поведения компонентов при отказах по отношению ко всем возможным обстановкам.
Основная идея анализа поведения РИС - вся система однородна и исходный текст ее компонентов доступен для анализа. Это не соответсвует практике применения и создания компонентов по ряду причин:
некоторые компоненты доступны лишь в виде двоичного кода;результаты анализа компонентов представляют интерес, даже если целой программы еще не существует;с точки зрения расхода времени и ресурсов многократно повторяемый анализ всех компонентов программы не всегда обоснован, (например, анализ библиотечных модулей, присоединяемых к программе);рассмотрение программы как единой однородной сущности означает, что изменение любого компонента требует полного повторного анализа всей программы;чтобы достичь практичного времени анализа, он должен использовать аппроксимации, которые обычно редуцируют точность и полезность/выполнимость анализируемых решений.
Необходим альтернативный подход - анализ на уровне компонентов, при котором на входе вместо исходного текста завершенной программы анализируется исходный код отдельных компонентов, дополненный некоторой информацией о контексте применения этих компонентов. Такая дополнительная обобщенная информация об остальных, возможно недоступных и даже еще не существующих, компонентах выполняют роль консервирующих допущений, что позволяет ввести меру консервативности частичного определения ИС. Далее ставится задача, обойти ограничения полнопрограммного анализа:
анализ без исходного кода, по обобщеной информации - спецификации,анализ по консервирующим допущениям,многократное использование обощенной информации, чтобы избежать повторного анализа компонентов,сокращение работы при ручном изменении кода, поскольку можно не анализировать код, незатронутый изменениями.
Методика такого анализа технически подобна мемо-функциям в функциональном программировании.
Компонентное программирование
Ключевое направление развития парадигм программирования связано с тенденцией компонентного подхода к разработке программ, верификации свойств их компонент и межязыковой интеграции программных комплексов. Такой подход интенсивно развивается в проектах типа .Net [[22]].
Разработка компонентов программ отличается от первичного программирования учетом долговременных целей и критериев, таких как надежность, производительность и улучшаемость информационных систем (ИС). Эти цели выводят процессы разработки ИС на надъязыковый уровень крупноблочной сборки и автоматизированной настройки готовых компонентов на условия их применения. Если базовые элементы языков программирования (ЯП) представляют собой некий минимум средств для детального представления программистами решений достаточно общего класса задач, то компоненты ИС ориентированы на автоматизированную сборку, при которой детальность алгоритмических решений и их привязка к используемому ЯП отступают на второй план перед технологией конструирования средств доступа к данным и определения методов привязки систем и их компонентов к контексту их применения. На передний план выходят задачи отладки поведения комплексов и взаимосвязей их частей, а также верификации свойств улучшаемых версий и компонентов ИС, качество разработки которых зависит от выбора модели жизненного цикла ИС, его полноты и длительности. Не теряет актуальности давнее наблюдение, что разработка компонента ИС более трудоемка, чем разработка аналогичной по назначению автономной программы. [[6],[7],[76]]
Понятие "компонент" имеет глубокие корни и весьма широкое толкование в технологии разработки программ. Это и библиотечные процедуры, и раздельно компилируемые модули, и пользовательские интерфейсы, и макроопределения, и системы файлов, и документация, и шаблоны компиляции кода программ, и элементы структур данных, и наборы данных с методами их обработки, и иерархии классов объектов общего назначения, и комплекты ИС, встраиваемых в информационные комплексы.
Реально понятие "компонент" проявляется как взаимосвязь понятий "обьекты", из которых строится текст или код программы, и "процессы", возникающие при функционировании, взаимодействии и разработке ряда ИС. С одной стороны, компонентами называют конструкции, используемые в разных программах. С другой стороны, этим же термином называют части или элементы структурированных данных, включая системы файлов и информационные комплексы. Совмещение этих сторон в общем понятии соответствует пониманию программ как разновидности данных. Разноплановость подходов к выделению компонентов подобно различиям в рассмотрении структуры материи с точки зрения физики, химии, геологии, биологии и других наук. Оно обусловлено независимостью влияния отдельных аспектов изучения, проектирования, построения и функционирования ИС на характер их применения и результативность разработки. Эта независимость фактически признана в технологии UML, поддерживающией ряд автономно создаваемых, одновременно существующих форм представления и структуризации проектируемой программы (бизнес-логика, ООП, временные диаграммы и размещение компонентов) [[76],[86]].
Простые компоненты могут быть заданы непосредственно, а сложные обычно строятся пошаговым образом. Процесс уточнения, улучшения или расширения компонентов в XP называют "рефакторинг" [[12],[46]]. Начиная с некоторого первичного текста программного компонента, пошаговым образом формируется его новое частичное определение, которое в каком-то отношении лучше, чем предыдущее. Оно может полнее, точнее или эффективнее решать задачу, может стать более удобочитаемым, лучше приспособленным к отладке или сопровождению и т.д, и т.п.
Движущие силы рефакторинга - эволюция решаемых задач, развитие информационных сетей и совершенствование технологии системного программирования. Все это требует повышения уровня организованности программ, приведения монолитных форм к дистрибутивным формам распределенных ИС. Обычно при организации ИС из компонентов требуются атрибуты, задающие их наименование, значение, конструкцию и функционирование, причем, не единственным образом.
Возможны псевдонимы или синонимы наименования, примеры значений, варианты конструкций и версии функционирования. Любая часть определения компонентов может быть задана с помощью других компонентов, в свою очередь определяемых пошаговым образом. Может быть сложная реализация простых компонентов и технически простое производство содержательно сложных компонентов с помощью автоматов или генераторов. Пара из входного и выходного значений: аргумента и соответствующего ему результата - тест, может работать как вариант реализации компонента, рассматриваемого как функция.
Развитие компонентов осуществляется достаточно свободно, но подчинено некоторым интуитивным закономерностям ЖЦ, связанным с динамикой представления и накопления знаний человеком, пока не превышен некоторый приемлимый предел, достижение которого ставит границы в их развитии. После этого происходят шаги декомпозиии на более простые компоненты или обобщения до более факторизуемых форм. В этом процессе компоненты подвергаются систематическому анализу, параметризации, оптимизации, таким образом рефакторинг повышает качество и потенциал компонентов, их изученность, организованность, эфективность и надежность.
Перенос внимания с разработки программ на разработку их компонентов требует пересмотра моделей ЖЦ, охватывающих процессы разработки множества программ и их версий, в которых происходит накопление типовых компонентов и удостоверение их работоспособности. За 50 лет программирования доля изученных задач разработки ИС систематически возрастала, что и явилось основанием перехода к компонентному программированию. Функциональный подход способствует повышению уровня изученности задач, технологичное решение которых выходит за пределы стандартных парадигм программирования [[54]].
Компонент создается как последовательность предварительных, уточняемых определений, сходящихся к удачному определению, отвечающему ряду заранее заданных критериев. Все эти определения частично представляют решения одной и той же задачи. В число критериев входит соответствие постановке задачи, демонстрируемость решения на тестах, а также возможность встраивания компонента в некую ИС или его применения в рамках ИС.
Компоненты могут быть интегрированы в ИС при ее создании или применяться через специальный интерфейс и средства взаимодействия процессов.
Набор определений компонентова расширяется по мере необходимости в более хорошем (точном, детальном, удобном, качественном, компактном, наглядном и т.п.) функционировании разных систем, включащих этот компонент. Выбор предпринимаемых улучшений зависит от разнообразия ИС, организуемых на основе иерархии многократно используемых компонентов, обеспечивающих откат при версифицировании. Одинаково определенные компоненты в разных ИС могут обладать различиями в поведении, выполнять разные роли в процессах информационной обработки, по-разному реагировать на взаимодействия с другими компонентами.
Множество ИС, содержащих или использующих общий компонент, можно характеризовать постановкой задачи, для решения которой этот компонент предназначен. Роль компонента в функционировании ИС, использующей его, может быть представлена в виде описания некой подзадачи или рецепта по применению компонента в рамках заданной системы.
Зависимость функционирования ИС от качества реализации содержащихся в ней встроенных компонентов демонстрируется на коллекции тестов, прогон которых удостоверяет работоспособность и обеспечивает измерение характеристик эффективности и производительности ИС.
Таким образом, понятие "компонент" содержательно сводимо к представлению о пошаговых процессах создания неоднородных информационных структур, элементы которых подчинены определенному согласованию. Согласованность - основная гарантия качества компонента.
С практической точки зрения работоспособность компонентов можно оценивать по некоторой шкале "качественных скачков", сопровождающих их улучшение, определение и реализацию, проявляющихся в соответствующем повышении надежности построенных из него ИС. Например, при оценке качества компонентов можно пользоваться шкалой возрастания информации о проверенных требованиях к качеству ИС, построенных из компонентов.
Информации о соответствии компонента и его спецификации относительно ИС нет.Имеется тест, работающий соответственно спецификации в одном классе процессов, построенных с использованием ИС, включающей данный компонент.Есть некоторое множество тестов, границы которого не вполне определены .Имеется определенное множество тестов, такое, что в рамках определенного класса процессов, порожденных ИС, включающих данный компонент, результат соответствует спецификации.Имеются удовлетворяющие спецификации множество тестов и класс ИС, при которых удостоверено (доказано), что свойства компонента соответствует спецификации.Показано, что на любых тестах и в рамках любых ИС, включающих компонент, его проявление не противоречит спецификации и обладает "корректностью".
Моделирование парадигм программирования
Создание и использование коллекций изученных задач, решения которых представлены в виде готовых компонентов, накапливаемых в общей информационной среде, дают основание перехода от библиотек к языкам КП. Нужна лишь подходящая парадигма программирования, допускающая эволюцию не только области применения ИС, но и пространства реализационных решений по созданию самой ИС. Ведущие парадигмы структурированного и объектно-ориентированного программирования ограничивают такую эволюцию рамками стандартных вычислительных моделей [41]. При необходимости это ограничение преодолевают привлечением ФП, о чем свидетельствует рост рейтинга систем функционального программирования (СФП), используемых в самодеятельных проектах, доведенных до завершения. Выигрыш дает приспособленность СФП к быстрой отладке, верификации, лаконизм, гибкость и моделирующая сила. Все это позволяет рассматривать СФП как эффективную инструментально-методическую основу информационной среды обучения современному программированию [[8],[22], [23],[37],[54]].
Исторически практика программирования складывается, можно сказать кристаллизируется, вокруг мощных библиотек подпрограмм и коллекций типовых компонентов, разрабатываемых на базе сравнительно узкого круга языков и в рамках технологий программирования, сложившихся почти полвека назад. Эти полвека не прошли даром. Появились технические возможности, дающие новое звучание методам работы с данными, что открывает перспективу более комфортабельной организации труда для очередного поколения программистов, особенно на этапе обучения профессии.
Современные ИТ сделали доступным для практики богатейший материал, само обилие которого является серьезной проблемой для его освоения и применения [[82]]. Этот материал является базой для оттачивания профессионального мастерства по определению ИС из готовых компонентов. Работа с компонентами подразумевает многократность использования, вариативность реализации и повторность разработки. Это влечет необходимость учета разных критериев и требований, подвергающихся непредсказуемой эволюции.
Функциональный подход к компонентному программированию позволяет формализовать на метауровне особенности разных технологий программирования, что дает основания для методики активного обучения программированию и конструированию ИС из компонентов СФП.
Сборка программы из автономно развиваемых компонентов требует формулировки достигаемой ими цели, понимание которой гарантирует корректность полученного результата. Формулировать цели частей программы - процесс отнюдь не тривиальный. В его основе лежат разные, трудно сопоставимые, подходы к классификации понятий, отчасти преставимые как парадигмы программирования.
В данном ознакомительном курсе не рассмотрены такие парадигмы, как учебное и теоретическое программирование, программирование баз данных, сайтов, сервисов, языки разметки и ряд других, освоение которых происходит естественно на практике при начальном обучении программированию. В таблице 15.1. указаны курсы Интернет-Университета информационных технологий, дополняющие материал лекций данного курса.
| 1 | Многоликое программирование | Баженова И.Ю., Сухомлин В.А. Введение в программирование http://www.intuit.ru/department/pl/plintro/ Непейвода Н.Н. Стили и методы программирования http://www.intuit.ru/department/se/progstyles/ |
| 2 | Определение языков программирования | Вояковская Н.Н., Москаль А.Е., Булычев Д.Ю., Терехов А.А. Разработка компиляторов http://www.intuit.ru/department/sa/compilersdev/ |
| 3 | Ассемблер | Новиков Ю.В., Скоробогатов П.К. Основы микропроцессорной техники http://www.intuit.ru/department/hardware/mpbasics/6.2.1. Ассемблер MPASM |
| 4 | Машинно ориентированное программирование | Галатенко В.А. Программирование в стандарте POSIX http://www.intuit.ru/department/se/pposix/ Язык программирования C http://www.intuit.ru/department/pl/cpl/ Якушева Н.М. Visual Basic http://www.intuit.ru/department/pl/vb/ |
| 5 | Макрообработка текстов | Храмцов П.,Б., Брик С.А., Русак А.М., Сурин А.И. Введение в HTML http://www.intuit.ru/department/internet/htmlintro/ |
| 6 | Языки управления процесс | Курячий Г.В., Маслинский К.А. Операционная система Linux http://www.intuit.ru/department/os/linux/ Костромин В.А.Основы работы в ОС Linux http://www.intuit.ru/department/os/baselinuxwork/ Оболочка bash |
| 7 | Функциональное программирование | Городняя Л.В. Основы функционального программирования http://www.intuit.ru/department/pl/funcpl/ |
| 8 | Стандартное системное программирование | Страуструп Бьерн Язык программирования C++ для профессионалов http://www.intuit.ru/department/pl/cpp2/ Биллиг В.А. Основы программирования на C# http://www.intuit.ru/department/pl/csharp/ Андреева Т.А. http://www.intuit.ru/department/pl/plpascal/ Программирование на языке Pascal |
| 9 | Декларативное программирование | Алексеев В.Е., Таланов В.А. Структуры данных и модели вычислений http://www.intuit.ru/department/algorithms/dscm/ Шрайнер П.А. Основы программирования на языке Пролог http://www.intuit.ru/department/pl/plprolog/ |
| 10 | Объектно-ориентированное программирование | Мейер Бертран http://www.intuit.ru/department/se/oopbases/ Основы объектно-ориентированного программирования http://www.intuit.ru/department/se/ooad/Основы объектно-ориентированного проектирования |
| 11 | Языки параллельного программирования. | Барский А.Б. Параллельное программирование http://www.intuit.ru/department/se/parallprog/ |
| 12 | Функции высших порядков | Сузи Р.А. http://www.intuit.ru/department/pl/python/ Язык программирования Python Верещагин Н.К., Шень А.Х. Языки и исчисления http://www.intuit.ru/department/calculate/lancalc/ |
| 13 | Оптимизация программ. | Чеповский А.М., Макаров А.В. Скоробогатов С.Ю. Common Intermediate Language и системное программирование в Microsoft .NET http://www.intuit.ru/department/pl/cil/ |
| 14 | Разработка программ | Терехов А.Н. Введение в технологию программирования http://www.intuit.ru/department/se/introprogteach/ Леоненков А.В. Нотация и семантика языка UML http://www.intuit.ru/department/pl/umlbasics/ Котляров В.П. http://www.intuit.ru/department/se/testing/ Основы тестирования программного обеспечения |
| 15 | Перспективы парадигм программирования | Кулямин В.В. Компонентный подход в программировании http://www.intuit.ru/department/se/compprog/ |
Распределенные информационные системы
РИС представляет собой набор независимо функционирующих составляющих, выглядящих как единая система [[21]]. Специфика таких систем еще не нашла достаточно удобных языковых средств, что и обуславливает на ближайшее время одно из направлений развития парадигм программирования наряду с парадигмой компонентного программирования, которая заслуживает отдельного рассмотрения.
При обсуждении РИС обычно используют сетевые модели, отражающие взаимосвязи составляющих как связи между узлами сети. При этом характерны следующие свойства РИС:
скрыты малосущественные различия и связи между узлами,поддерживается расширение сети и массштабирование числа узлов,РИС существует постоянно, хотя части РИС могут выходить из строя,определен промежуточный уровень между оборудованием и приложениями.
Примеры:
компьютерная сеть с сервером, поддерживающим дневники, форумы, переписку и клиентские файлы,система обработки заказов, хранящая оперативно обновляемую информацию про билеты, гостиничные номера, товары и т.п.,электронная почта с базой данных адресов доставки и реальных серверов.
Типовые задачи РИС:
эксплуатация общих ресурсов,поддержка виртуальных коллективов,обеспечение безопасности и конфиденциальности отдельных процессов,специализированные настройки, информационные сервисы и поддержка пользователей.
Решение таких задач сопряжено с выполнением следующих требований:
прозрачность доступа к данным, их местоположения, переноса и перемещения, копирования, совместного доступа к блокам данных, отказа-восстановлений процесса обработки, оперативного хранения дублей компонент, обеспечивающих бесперебойное функционарование РИС;управление степенью открытости процесса разработки РИС, протокола взаимодействия компонент РИС, пользовательского интерфейса терминальных узлов РИС, информационных сервисов и технических служб;интероперабельность и переносимость, гибкость и массштабируемость компонент и комплексов, образующих РИС.
Естественный подход к выполнению таких требований - определение децентрализованных алгоритмов, таких что:
ни один узел не содержит всю полную информацию по системе,решения принимаются по локальной информации,сбой любого узла не нарушает ход выполнения алгоритма,нет единого времени - узлы функционируют асинхронно.
Чаще всего РИС реализуется на базе сетевой операционной системы, обеспечивающей доступ к совместно используемым ресурсам, позволяющей скрыть сложность и неоднородность используемого обрудования. Архитектура РИС концептуально близка проблематике сетевых баз данных и трехзвенных клиетн-серверных систем, но сопряжена с рядом дополнительных условий, связанных с практикой вертикального распределения звеньев при обработке приложений на разных машинах и горизонтальной реорганизации с целью выравнивания нагрузки посредством дублирования серверов.
Элементы РИС (ЭЛ) могут быть разделены на части Э1, Э2, размещаемые в разных логических зонах Р, связанных соответствующим протоколом П(Р).
ЭЛ/Р ( Э1 П(Р) Э2 )
Этим обеспечивается то, что концепция системы не зависит от физического размещения частей.
На концептуальном уровне для РИС характерны свойства:
разнородность используевых устройств,целостность (единство) системы,электронная связность,высокий уровень взаимодействия между элементами,свобода выбора конструктивных решений и их улучшения.
На уровне реализации принципиально важна надежность:
отказоустойчивость,защита транзакций при сбоях,предсказуемость времени реакции,настройка-отладка сложных подсистем,быстродействие диалога между узлами.
В настоящее время массово выполнимы требования к устройствам для реализации РИС, которые должны быть одновременно мощными (высокая пропускная способность) и недорогими (могут простаивать).
Критерии успешности разработки РИС:
оптимальные затраты на разработку,легкость расширения простым добавлением узлов или перераспределением зон,наличие методов определения неисправностей и технологии быстрого их устранения.
По существу РИС - эволюционирующий объект, разработка которого имеет непрерывный характер и продолжается в период эксплуатации.По этой причине язык представления РИС должен поддерживать в полной мере средства для решения проблем разработки и эксплуатации программ, что приводит к парадигме КП.
Рассматриваются тенденции современного программирования, еще
Рассматриваются тенденции современного программирования, еще не получившие языковой поддержки, такие как компонентное программирование и разработка РИС.
Интересно рассмотреть перспективы развития парадигм программирования, обусловленных изменением условий эксплуатации современных информационных систем, особенно связанных с повсеместным распространением сетевых технологий, меняющих критерии оценки качества программ и методы обеспечения надежности и производительности программирования. Две основные линии такого развития - разработка распределенных информационных систем (РИС) и компонентное программирование (КП).
