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

Определение языков программирования

Прежде чем анализировать конкретные парадигмы программирования, рассматривается задача определения систем программирования. Строится простейшее определение семантики языка программирования в виде интерпретатора, задающего операционную семантику на примере подмножества языка Лисп.
Обычно при разработке системы программирования различают три уровня: синтаксис, семантика и прагматика реализуемого языка. Разграничение уровней носит условный характер, но можно констатировать, что синтаксис определяет внешний вид программ, семантика задает класс процессов, порождаемых программами, а прагматика реализует процессы в рамках конкретных условий применения программ. При изучении парадигм программирования центральную роль играет семантика, а синтаксис и прагматика используются как вспомогательные построения на примерах. Венская методика определения языков программирования с помощью операционной семантики, использующей концепции программирования при спецификации систем программирования, удобна для сравнения парадигм программирования [[74]].
Венский метод (ВМ) определения языков программирования был разработан в 1968 году в Венской лаборатории IBM под руководством П. Лукаса на основе идей, восходящих к Дж. Маккарти [[74],[75]]. Благодаря хорошо разработанной концепции абстрактных объектов, позволяющей концентрировать внимание лишь на существенном и игнорировать второстепенные детали, Венский метод годится для описания и машин, и алгоритмов, и структур данных, особенно при обучении основам системного программирования. По мнению В.Ш. Кауфмана Венский метод вне конкуренции в области описания абстрактных процессов, в частности, процессов интерпретации программ на языках программирования. Согласно концепции абстрактных объектов (абстрактный синтаксис, абстрактная машина, абстрактные процессы) интерпретирующий автомат содержит в качестве компоненты состояния управляющую часть, содержимое которой может изменяться с помощью операций, подобно прочим данным, имеющимся в этом состоянии [[53]].

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

Определение языка программирования (ЯП) по Венской методике начинается с четкого отделения существа семантики от синтаксического разнообразия определяемого языка [[74]]. С этой целью задается отображение конкретного синтаксиса (КС) ЯП в абстрактный (АС), вид которого инвариантен для семейства эквивалентных языков.

Семантика ЯП определяется как универсальная интерпретирующая функция (ИФ), дающая смысл любой программе, представленной в терминах АС. Такая функция использует определенную языком схему команд - языково ориентированную абстрактную машину (АМ), позволяющую смысл программ формулировать без конкретики компьютерных архитектур.

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

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

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


Начнем с выбора абстрактного синтаксиса на примере определения небольшого, но функционально полного подмножества языка Лисп [[75]].

Конкретный синтаксис языков программирования принято представлять в виде простых БНФ (Формул Бекуса-Наура). Данные языка Лисп - это атомы, списки и более общие структуры из бинарных узлов - пар, строящихся из любых данных:

<атом> ::= <БУКВА> <конец_атома>

<конец_атома> ::= <пусто> | <БУКВА> <конец_атома> | <цифра> <конец_атома>

<данное> ::= <атом> | (<данное> ... ) -- список

Пример 2.1. Синтаксис данных языка Лисп

Это правило констатирует, что данные - это или атомы, или списки из данных.

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

Согласно такому правилу () есть допустимое данное. Оно в языке Лисп по соглашению эквивалентно атому Nil.

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

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

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

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


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

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

<идентификатор> ::= <атом>

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

<форма> ::= <константа> | <переменная> | (<функция> <аргумент> ... >) | (IF <предикат> <форма> <форма> )

<константа> ::= (QOUTE <данное>)

<переменная> ::= <идентификатор>

<аргумент> ::= <форма>

<предикат> ::= <форма>

Пример 2.2. Синтаксис выражений подмножества языка Лисп

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

Таким образом, класс форм - это объединение класса переменных и подкласса списков, начинающихся с QUOTE, IF или с представления некоторой функции.

Форма - это выражение, которое может быть вычислено.

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


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

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

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

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

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

<функция> ::= <название> | (LAMBDA <список_переменных> <форма>) | (LABEL <название> <функция>)


<список_переменных> ::= (<переменная> ... )

<название> = <идентификатор>

Пример 2.3. Синтаксис функций подмножества языка Лисп

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

Таким образом, класс функций - это объединение класса названий и подкласса трехэлементных списков, начинающихся с LAMBDA или LABEL.

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

Используемые в реальных Лисп-системах функции DEFUN или DEFINE, по существу, совмещает эффекты специальных функций LABEL и LAMBDA.

<форма> ::= <переменная> | (QOUTE <данное>) --- константа | (IF <предикат> <форма> <форма>) --- условное выражение | (<функция> <аргумент> ... <аргумент>) --- вызов функции

<предикат> ::= <форма> <аргумент> ::= <форма> <переменная> ::= <идентификатор>

<функция> ::= <название> --- ранее определенная функция | (LAMBDA <список_переменных> <форма>) --- безымянная функция | (LABEL <название> <функция>) --- рекурсивная функция

<список_переменных> ::= (<переменная> ... )

<название> ::= <идентификатор> <идентификатор> ::= <атом>

Листинг 2.1. Синтаксическая сводка подмножества языка Лисп

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


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

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

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

(atom e) --- переменная (eq (car e) 'QUOTE) --- константа (eq(car e) 'IF) --- условное выражение

(atom fn) --- название известной функция (eq(car fn)'LAMBDA) --- конструирование безымянной функции (eq (car fn) 'LABEL) --- конструирование рекурсивной функции

Следует отметить, что полученные БНФ могут рассматриваться лишь как семантический каркас функционального языка программирования. Отсутствует привязка к структурам данных Лиспа и средствам их обработки. Такая обработка обеспечивается набором встроенных базовых функций, смысл которых должен быть заранее определен. Для каждой такой функции интерпретатор должен иметь возможность вычислить результат применения функции к ее аргументам. Набор встроенных функций задает основную область применения языка. Для Лиспа это обработка списочных структур данных:

(eq fn 'CAR) --- вызов функции CAR (eq fn 'CDR) --- вызов функции CDR (eq fn 'CONS) --- вызов функции CONS (eq fn 'ATOM) --- вызов функции ATOM (eq fn 'EQ) --- вызов функции EQ

Селекторы основных позиций списочного представления программ P сводятся к композициям функций обработки списков:

(Car P ) (Cdr P ) (Caar P ) = (Car (Car P )) (Cadr P ) = (Car (Cdr P )) (Cdar P ) = (Cdr (Car P )) (Caddr P ) = (Car (Cdr (Cdr P )))

Синтаксическая сводка подмножества языка

<форма> ::= <переменная> | (QOUTE <данное>) --- константа | (IF <предикат> <форма> <форма>) --- условное выражение | (<функция> <аргумент> ... <аргумент>) --- вызов функции <предикат> ::= <форма> <аргумент> ::= <форма> <переменная> ::= <идентификатор> <функция> ::= <название> --- ранее определенная функция | (LAMBDA <список_переменных> <форма>) --- безымянная функция | (LABEL <название> <функция>) --- рекурсивная функция <список_переменных> ::= (<переменная> ... ) <название> ::= <идентификатор> <идентификатор> ::= <атом>

Листинг 2.1. Синтаксическая сводка подмножества языка Лисп

Закрыть окно

<форма> ::= <константа> | <переменная> | (<функция> <аргумент> ... >) | (IF <предикат> <форма> <форма> ) <константа> ::= (QOUTE <данное>) <переменная> ::= <идентификатор> <аргумент> ::= <форма> <предикат> ::= <форма>

Пример 2.2. Синтаксис выражений подмножества языка Лисп

Закрыть окно

<функция> ::= <название> | (LAMBDA <список_переменных> <форма>) | (LABEL <название> <функция>) <список_переменных> ::= (<переменная> ... ) <название> = <идентификатор>

Пример 2.3. Синтаксис функций подмножества языка Лисп

Закрыть окно

Универсальная функция

Интерпретация или универсальная функция - это функция, которая может вычислять значение любой формы, включая формы, сводимые к вычислению произвольной заданной функции, применяемой к аргументам, представленным в этой же форме, по доступному описанию данной функции. (Конечно, если функция, которой предстоит интерпретироваться, имеет бесконечную рекурсию, интерпретация будет повторяться бесконечно.)
Определим универсальную функцию eval от аргумента expr - выражения, являющегося произвольной вычислимой формой языка Лисп.
Универсальная функция должна предусматривать основные виды вычисляемых форм, задающих значения аргументов, а также представления функций, в соответствии со сводом приведенных выше правил языка. При интерпретации выражений учитывается следующее:

Атомарное выражение обычно понимается как переменная. Для него следует найти связанное с ним значение. Например, могут быть переменные вида "x", "elem", смысл которых зависит от контекста, в котором они вычисляются.

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

Условное выражение требует специального механизма для предварительного вычисления предиката и выбора нужной ветви. Например, интерпретация условного выражения:1)
(IF (ATOM x) x (first (CAR x) ) ) должна обеспечивать выбор ветви в зависимости от атомарности значения переменной.

Остальные формы выражений рассматриваются по общей схеме как список из функции и ее аргументов. Обычно аргументы вычисляются, а затем вычисленные значения передаются функции для интерпретации ее определения. Так обеспечивается возможность писать композиции функций. Например, в выражении (first (CAR x)) внутренняя функция CAR сначала получит в качестве своего аргумента значение переменной x, а потом свой результат передаст как аргумент более внешней функции first.

Если функция представлена своим названием, то среди названий различаются имена встроенных функций, такие как CAR, CDR, CONS и т.п., и имена функций, введенные в программе, например first.
Для встроенных функций интерпретация сама "знает", как найти их значение по заданным аргументам, а для введенных в программе функций - использует их определение, которое находит по имени.

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

(LAMBDA (x) (IF (ATOM x) x (first (CAR x) )) ) зависит от одного аргумента, значение которого должно быть связано с переменной x. В определении используется свободная функциональная переменная first, которая должна быть определена в более внешнем контексте.

Если представление функции начинается с LABEL, то понадобится сохранить имя функции с соответствующим ее определением так, чтобы корректно выполнялись рекурсивные вызовы функции. Например, предыдущее LAMBDA-определение безымянной функции становится рекурсивным, если его сделать вторым аргументом специальной функции LABEL, первый аргумент которой - fisrt, имя новой функции.

(LABEL first (LAMBDA (x) (IF (ATOM x) x (first (CAR x) )) ))

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

обработка структур данных (cons, car, cdr, atom, eq);

конструирование функциональных объектов (lambda, label);

идентификация объектов в контексте (имена переменных и названия функций);

управление логикой вычислений и границей вычислимости (композиции, quote, if, eval).

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

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


(DEFUN pairlis (x y al) (IF (null x) al (CONS (CONS (CAR x) ( CAR Y) ) (pairlis (CDR x) (CDR y) al) ))

(pairlis '(A B C) '(u t v) '((D . y)(E . y))) = ((A . u)(B . t)(C . v)(D . y)(E . y))

ASSOC - функция двух аргументов, x и al. Если al - ассоциативный список, подобный тому, что формирует функция pairlis, то assoc выбирает из него первую пару, начинающуюся с x. Таким образом, это функция поиска определения или значения в контексте, реализованном как ассоциативный список.

(DEFUN assoc (x al) (IF (equal x (CAAR al)) (CAR al) (assoc x (CDR al)) )

Частичная функция - рассчитана на наличие ассоциации.

(assoc 'B '((A . (m n)) (B . (CAR x)) (C . w) (B . (QUOTE T)))) = (B . (CAR x))

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

(eval '(fn arg1 ... argK)) = результат применения fn к аргументам arg1, ..., argK.

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

(eval '((LAMBDA (x y) (CONS (CAR x) y)) '(A B) '(C D) )) = (A C D)

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

Вернемся к синтаксической сводке вычислимых форм в примере 2.1.

Каждой ветви этой сводки соответствует ветвь универсальной функции:

(DEFUN eval (e) (evl e '((Nil . Nil) (T . T))))

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


(DEFUN evl(e a) (COND ( (atom e) (cdr(assoc e a)) ) ( (eq (car e) 'QUOTE) (cadr e)) ( (eq(car e) 'IF) (evcon(cdr e) a)) ( T (apply (car e) (evlis(cdr e) a) a) )) )

(defun apply (fn x a) (COND ((atom fn)(cond ((eq fn 'CAR) (caar x)) ((eq fn 'CDR) (cdar x)) ((eq fn 'CONS) (cons (car x)(cadr x)) ) ((eq fn 'ATOM)(atom (car x)) ) ((eq fn 'EQ) (eq (car x)(cadr x)) ) (T (apply (evl fn a) x a)) ) ) ) ((eq(car fn)'LAMBDA) (eval (caddr fn) (pairlis (cadr fn) x a) )) ((eq (car fn) 'LABEL) (apply (caddr fn) x (cons (cons (cadr fn)(caddr fn)) a)))))

(DEFUN evcon (c a) (COND ((evl (car c) a) (evl (cadr c) a) ) ( T (evl (caddr c) a) ) ))

(DEFUN evlis (m a) (COND ((null m) Nil ) ( T (cons(evl (car m) a) (evlis(cdr m) a) )) )

Поясним ряд пунктов этих определений.

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

Если CAR от формы - QUOTE, то она представляет собой константу, значение которой выбирается селектором CADR от нее самой.

Если CAR от формы - IF, то форма - условное выражение. Вводим вспомогательную функцию EVCON, которая обеспечивает вычисление предиката и выбор формы, соответствующей значению предиката. Эта форма передается EVL для дальнейших вычислений.

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

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

Первый аргумент apply - функция. Если она - атом, то существует две возможности. Атом может представлять одну из элементарных функций (car cdr cons atom eq). В таком случае соответствующая ветвь вычисляет значение этой функции на заданных аргументах. В противном случае, этот атом - имя ранее заданного определения, которое можно найти в ассоциативном списке, подобно вычислению переменной.

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


Если функция начинается с LABEL, то ее название и определение соединяются в пару, и полученная пара размещается в ассоциативном списке, чтобы имя функции стало определенным при дальнейших вычислениях. Они произойдут как рекурсивный вызов apply, которая вместо имени функции теперь работает с ее определением при более полном ассоциативном списке - в нем уже размещено определение имени функции. Поскольку определение размещается "наверху" стека, оно становится доступным для всех последующих переопределений, то есть работает как локальный объект.

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

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

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

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

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


Составляющие этой формальной системы следующие:

Множество символов, называемых списками.

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

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

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

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

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

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

APPEND - функция двух аргументов x и y, сцепляющая два списка в один.

(DEFUN append (x y) (IF (null x) y (CONS (CAR x) (append (CDR x) y) )))

INSERT - вставка z перед вхождением ключа x в список al.

(DEFUN insert (al x z) (COND ((null al) Nil) ((equal (CAR al) x) (CONS z al)) ((QUOTE T) (CONS (CAR al) (insert (CDR al) x z))) ))

(insert '(a b c) 'b 's) = (a s b c)

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

(DEFUN assign (x v al) (COND ((Null al) (CONS (CONS x v) Nil )) ((equal x (CAAR al))(CONS (CONS x v) (CDR al))) ((QUOTE T) (CONS (CAR al) (assign x v (CDR al)))) ))

(assign 'a 111 '((a . 1)(b . 2)(a . 3))) = ((a . 111)(b . 2)(a . 3)) (assign 'a 111 '((c . 1)(b . 2)(a . 3))) = ((c . 1)(b . 2)(a . 111)) (assign 'a 111 '((c . 1)(d . 3))) = ((c . 1)(d . 3) (a . 111))

Методы верификации программ активно используют структурную и рекурсивную индукцию (Мак-Карти) при доказательстве таких свойств рекурсивно определенных функций, как эквивалентность.


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

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

  1)

  Условные выражения такого вида были введены в математическую теорию вычислений Маккарти (1963)

  2)

  Defun - зависит от трех аргументов, первый - название описываемой функции, второй - список аргументов описываемой функции, третий - форма, при вычислении которой получается результат функциию

  3)

  (if pr tr fl) эквивалентно (cond (pr tr) (T fl)) , где T - тождественная истина.

  4)

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

Ассемблер

Низкоуровневое программирование успешно при детальном знакомстве с архитектурой компьютера, что в конечном счете приводит к ее пониманию. Принципы и способы программирования в общем не зависят от языка. Главным требованием является умение мыслить логически.
Ассемблер отличается от компилятора меньшей сложностью исходного языка, перевод с которого в машинный язык можно выполнить "один-в-один". Ассемблер часто сопровождается возможностью дизассемблирования, что отличает его от большинства других языков программирования. Изучить язык ассемблера проще, чем любой язык высокого уровня. Знание ассемблера помогает понимать код программы, подготовленной на других языках.
Архитектура компьютера часто определяется как множество ресурсов, доступных пользователю. Это система команд, общие регистры, слово состояния процессора и адресное пространство. Процесс перевода программы с языка ассемблера в язык машинных команд называют ассемблированием.
Процесс ассемблирования заключается в следующим:

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

Сопоставление используемых идентификаторов с адресами в памяти.

Отображение ассемблерных команд и идентификаторов в их машинные эквиваленты.

Для реализации такого процесса требуется счетчик адресов и таблица идентификаторов.
Программист не знает абсолютных адресов ячеек памяти, занятых для хранения констант, команд и промежуточных результатов вычислений, но обычно предполагается, что последовательно написанные команды будут расположены в последовательных ячейках памяти.
Кроме символических представлений команд ассемблерная программа содержит описания распределяемой памяти и директивы управления ассемблированием. Обычно выделена точка входа в программу из операционной системы.
Программирование на ассемблере подразумевает знание специфики системы команд процессора, методов обслуживания устройств и обработки прерываний. Система команд может быть расширена микропрограммами и системными вызовами в зависимости от комплектации оборудования и операционной системы. Это влияет на решения по адресации памяти и коммутации комплекта доступных устройств. Но есть и достаточно общие соглашения о представлении и реализации средств обработки информации на уровне машинного кода [[1],[20],[36],[55],[56],[71],[72]].
Структура кода программы и его свойства:

Перемещаемость. Удобно, чтобы код программы был устроен так, что его можно расположить по любому абсолютному адресу.

Листание страниц памяти. Соотношение между адресуемой и реально доступной памятью может требовать пересмотра в процессе выполнения программы.

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

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

Обычно независимо от системы команд ассемблер обеспечивает средства управления распределением памяти и управления компиляцией кода, что позволяет программисту принимать точные решения на уровне машинного языка. Имеются средства отладочного исполнения и распечатки листингов. При необходимости уровень языка может быть повышен с помощью макросов.
Язык ассемблера оперирует такими данными как адреса и значения. Нередко для наглядности в записи операндов команд вводится внешнее различие @адресов и #значений с помощью префиксных символов. Возможны специальные формы записи для блоков данных и литералов.
При записи команд на ассемблере принято структурировать строки на поля, предназначенные для последовательного размещения метки, кода команды, операндов и комментария. Наибольшее разнообразие возможных решений связано с формами адресации операндов на уровне машинного языка, о которых будет речь далее.
Число слов, отводимое ассемблером под одну символическую команду, зависит не только от собственно кода команды, но и от метода адресации операндов, а возможно и от других аспектов кодирования программ и данных, обсуждение которых здесь не предусмотрено. Достаточно констатировать, что программа при ассемблировании распадается на конечные последовательности команд K1 ... Kn, которым сопоставляются конечные интервалы машинных слов W1 ... Wm(a) в зависимости от а - системы аспектов кодирования.
[K1 ... Kn] [W1 ... Wm(a)]
Фактически операндная часть команды - это адреса, специальные регистры, сумматоры, значения в общей памяти, шкала прерываний и состояний или что-нибудь другое, специфичное для конкретной архитектуры.
В зависимости от команды используются разные методы адресации операндов:

неявная - команда сама "знает", где и что она обрабатывает, где берет данные и куда разместит результат;

непосредственная - операнд расположен непосредственно в команде;

прямые адреса - код адреса размещен в поле операнда;

индексируемые адреса - один из операндов используется как индекс при вычислении адреса других операндов;

базируемых (по регистру) - указан базовый регистр для пересчета адресов операндов;

относительные (по текущей позиции) - адресация учитывает адрес размещения команды;

косвенные (через промежуточное слово) - операнд указывает на слово, хранящее адрес значения;

модифициуемые (по значению-регистру) - один операнд указывает на слово, хранящее значение, модифицирующее адрес другого операнда;

стек - операнд, доступ к которому подчинен дисциплине стека - "первый пришел - последний ушел".

Управление ассемблированием обычно обеспечивает средства авторизации, взаимодействия с отладчиком, выдачей листинга, текстовым редактором, операционной системой и средствами приаппаратного уровня, доступными через BIOS.
START - типичная метка входа в программу из операционной системы, во многих языках ассемблера символизирующая начальный адрес исполнения кода программы.
Код может быть сформирован в рассчете на использование специальной программы "загрузчик", обеспечивающей применение программы как модуля совместно с независимо подготовленными объектами.
Обычно система команд кроме команд арифметических вычислений и передач управления содержит команды манипулирования данными, их ввода-вывода через буфер обмена, возможно доступный через механизм прерываний. При этом используется код состояния процесса, отражающий свойства текущей выполняемой команды, такие как выработка нулевого или ненулевого кода, отрицательного или положительного числа, переноса разряда за границы машинного слова и другое.
Имеются команды перехода по прерыванию, возвратный вызов процедуры с использованием регистра возврата и передача управления со счетчиком числа циклов. Встречаются и другие команды, разнообразие которых не влияет на особенности ассемблирования и применения ассемблеров в системах программирования. Именно язык ассемблера выступает в системах программирования в роли конкретной машины (КМ) при компиляции программ.
Встраиваемые в ядро интерпретатора операции соответствуют стандартным правилам доступа к параметрам и размещения выработанного результата. Таким же правилам должен подчиняться и компилируемый код. Это позволяет формально считать равноправными встроенные и программируемые функции. Компилятор по исходному тексту программы строит эквивалентный ему код программы. Особенности процесса компиляции достаточно сложны даже для простых языков, поэтому характеристика результата компиляции часто задается в терминах языково-ориентированных абстрактных машин. Такой подход полезен для решения ряда технологических проблем разработки программных систем (мобильность, надежность, независимость от архитектур и т.п.)
При сравнении императивного и функционального подходов к программированию, П.Лэндин (P.J.Landin) предложил абстрактную машину SECD для спецификации машинно-зависимых аспектов семантики Лиспа. Подробное описание этой машины можно найти в книгах по функциональному программированию [[23],[64]]. Рассмотрим технику ассемблерного программирования на примере программ для абстрактной машины (АМ), удобной для определения операционной семантики языка программирования, - машины SECD. Это автомат, работающий над четырьмя структурными регистрами: стек для промежуточных результатов, контекст для размещения именованных значений, управляющая вычислениями программа, резервная память (Stack, Environment, Control list, Dump). Регистры приспособлены к хранению выражений в форме атомов или списков. Состояние машины полностью определяется содержимым этих регистров. Поэтому функционирование машины можно описать достаточно точно в терминах изменения содержимого регистров при выполнении команд, что выражается следующим образом:
s e c d s' e' c' d' - переход от старого состояния к новому.
Для характеристики встроенных команд Лисп-интепретатора и результата компиляции программ базового Лиспа понадобятся следующие команды:
LD - ввод данного из контекста в стек; LDC - ввод константы из программы в стек; LDF - ввод определения функции в стек; AP - применение функции, определение которой уже в стеке; RTN - возврат из определения функции к вызвавшей ее программе; SEL - ветвление в зависимости от активного (верхнего) значения стека; JOIN - переход к общей точке после ветвления; CAR - первый элемент из активного значения стека; CDR - без первого элемента активное значение стека; CONS - формирование узла по двум верхним значениям стека; ATOM - неделимость (атомарность) верхнего элемента стека; EQ - равенство двух верхних значений стека; SUB1 - вычитание 1 из верхнего элемента стека; ADD1 - прибавление 1 к верхнему элементу стека; STOP - останов.
Стек устроен традиционно по схеме "первый пришел, последний ушел". Каждая команда абстрактной машины "знает" число используемых при ее работе элементов стека, которые она удаляет из стека и вместо них размещает выработанный результат. Исполняются команды по очереди, начиная с первой в регистре управляющей программы. Машина прекращает работу при выполнении команды "останов", которая формально характеризуется отсутствием изменений в состоянии машины:
s e (STOP ) d s e (STOP ) d
Следуя Хендерсону, для четкого отделения обрабатываемых элементов от остальной части списка будем использовать следующие обозначения: (x . l ) - первый элемент списка - x, остальные в списке l. (x y . l ) - первый элемент списка - x, второй элемент списка - y, остальные в списке l и т.д. Теперь мы можем методично описать эффекты всех перечисленных выше команд.
s e (LDC q . c) d (q . s) e c d (a . s) e (ADD1 . c) d (a+1 . s) e c d (a . s) e (SUB1 . c) d (a-1 . s) e c d (a b . s) e (CONS . c) d ((a . b) . s) e c d ((a . b) . s) e (CAR . c) d (a . s) e c d ((a . b) . s) e (CDR . c) d (b . s) e c d (a . s) e (ATOM . c) d (t . s) e c d (a b . s) e (EQ . c) d (t . s) e c d
где t - логическое значение.
Для доступа к значениям, расположенным в контексте, можно определить специальную функцию N-th, выделяющую из списка элемент с заданным номером N в предположении, что длина списка превосходит заданный адрес.
(DEFUN N-th (n list ) (IF (EQ n 0 )(CAR list ) (N-th (SUB1 n ) (CDR list ) )) )
Продолжаем описание команд Лисп-машины.
s e (LD n . c) d (x . s) e c d , где x - это значение (N-th n e )
При реализации ветвлений управляющая программа соответствует следующему шаблону:
( ... SEL ( ... JOIN ) ( ... JOIN ) ... )
Ветви размещены в подсписках с завершителем JOIN, после которых следует общая часть вычислений. Для большей надежности на время выполнения ветви общая часть сохраняется в дампе - резервной памяти, а по завершении ветви - восстанавливается в регистре управляющей памяти.
(t . s) e (SEL c1 c0 . c) d s e ct (c . d)
s e (JOIN ) (c . d) s e c d
где ct - это c1 или c0 в зависимости от истинностного значения t.
Организация вызова процедур требует защиты контекста от локальных изменений, происходящих при интерпретации тела определения. Для этого при вводе определения функции в стек создается специальная структура, содержащая код определения функции и копию текущего состояния контекста. До этого в стеке должны быть размещены фактические параметры процедуры. Завершается процедура командой RTN, восстанавливающей регистры и размещающей в стеке результат процедуры.
s e (LDF f . c) d > ((f . e) . s) e c d ((f . ef) vf . s) e (AP . c) d > NIL (vf . ef) f (s e c . d) (x) e (RTN ) (s e c . d) > (x . s) e c d
где f - тело определения, ef - контекст в момент вызова функции, vf - фактические параметры для вызова функции, x - результат функции.
Упражнение 3.1. Программа c имеет вид:
c = (LD 3 ADD1 LDC 128 EQ STOP)
Пусть e = (101 102 103 104 105). Напишите последовательность состояний стека s при работе программы и сформулируйте, что она делает.
Ответ: Данная программа проверяет, меньше ли на 1 значение, хранящееся в контексте e по адресу 3, чем заданная в программе константа 128. При ее работе стек s проходит следующие состояния:
NIL (104 ) (105 ) (128 105 ) (NIL )
Упражнение 3.2. Напишите управляющую программу, дающую результат, эквивалентный следующим выражениям:
(CADR e ) (EQ (CAR e) 'QUOTE ) (COND ((EQ n 0 )(CAR l )) (T (CONS (SUB1 n ) (CDR l ) )) ))
(Адреса значений e, n, l можно обозначить как @e, @n, @l, соответственно.)
Ответ:
( LD @e CDR CAR ) ( LD @e CAR LDC QUOTE EQ ) ( LD @n LDc 0 EQ SEL (LD @l CAR JOIN ) (LD @n SUB1 LD @l CDR CONS JOIN ))
Упражнение 3.3. Напишите спецификацию команды SET, сохраняющей активное значение стека в контексте по заданному в программе адресу в предположении, что длина списка превосходит заданный адрес.
Выполнение упражнение 3.3: Нужна функция, заменяющая в списке указанный старый элемент новым.
(DEFUN ASS (e n list ) (IF (EQ n 0 )(CONS e (CDR l )) (CONS (CAR l )(ASS e (SUB1 n ) (CDR l ) ))) )
Тогда можно описать команду SET следующим образом:
(x . s) e (SET n . c) d s xne c d
где xne = (ASS x n e) - новое состояние контекста.
В рассмотренных упражнениях виден уровень проблем, решаемых программистом при работе на ассемблере. Познакомившись с примерами низкоуровневого программирования с помощью абстрактной машины SECD, можно более детально определить ряд технических аспектов, иллюстрирующих операционную семантику машинного языка (см. курс "Основы функционального программирования. Лекция 7.").
Традиционно ассемблер реализуют как упрощенный компилятор. Учитывая повышенную нагрузку низкоуровневого программирования на отладку программ, иногда включают в систему программирования интерпретатор ассемблера, обеспечивающий кроме удобства отладки широкий спектр преобразования программ на ассемблере, их оптимизации и адаптации к развитию аппаратуры. Интерпретирующий автомат для ассемблера устроен реализационно проще, чем автомат для абстрактной машины SECD, благодаря отсутствию локализации имен с их областями действия и встроенной реализации команд - языка конкретной машины.
Зависимость ассемблера от конкретной машины или архитектуры создает значительные трудности при переносе программ на новые компьютерные системы. Дальнейшие лекции посвящены методам преодоления такой зависимости, подходам к повышению эффективности программ в тех случаях, когда ценой независимости является избыточный расход памяти или времени, и средствам достижения высокой производительности программирования.

Машинно ориентированное программирование

Рассматривается два подхода к машинно независимому эффективному программированию. Язык Forth - пример организации вычислений над стеком. Можно рассматривать как язык-ядро с возможностью практически неограниченного проблемно-ориентированного расширения. Язык Little - пример традиционной организации вычислений над структурированными битовыми строками. Основные конструкции аналогичны фортрановским, но с учетом современных решений, упрощающих реализацию компилятора. Оба языка допускают порождение эффективного кода "хорошо" написанных программ [[3],[32]].
Появление в 70-х годах микропроцессорных средств с малым объемом памяти и сравнительно невысоким быстродействием вызвало очевидные трудности в применении привычных языков высокого уровня. Не удивительно, что поиск подходящих средств программирования сменил приоритеты в оценке свойств языков и систем программирования. На передний план вышли машинно-ориентированные языки-оболочки, поддерживающие достижение эффективности и компактности программ при достаточном уровне абстрагирования от конкретики процессоров, сравнимом с абстрагированием в языках высокого уровня. Особо ярким явлением в эти годы стал язык Forth, сохранивший многочисленных приверженцев и в наши дни, когда пресс технических характеристик изрядно помягчал [[6]]. Little приведен как пример альтернативного подходе к решению проблемы машинно ориентированного программирования.
Наиболее убедительное применение Forth получил как средство разработки специализированных систем, создаваемых по методике раскрутки, начиная с тщательно минимизированного ядра с рядом последовательных шагов расширения в рамках единой оболочки. Сам язык устроен по такому же принципу, так что такая технология пошагового программирования впитывается при изучении идей и средств системы программирования на базе Forth-а. Кроме общеизвестных примеров про системы управления астрономическими телескопами и лазерами, следует упомянуть IBMCAD - аналог системы инженерного AutoCAD и систему автоматизации издательского дела МРАМОР.
Для последней именно на Форте была создана предельно компактная операционная система объемом около 4 килобайт. Форт был успешно применен при реализации языка PostScript, до сих пор используется при разработке видеоигр и систем начальной загрузки ОС, чувствительных к скорости срабатывания. При значительном внешнем несходстве Форт обладает концептуальным родством с языком Лисп, что побудило в 80-е годы к разработке языка ФоЛи, объединяющего достоинства обоих языков.

Программирование на Форте требует вдумчивости и аккуратности. Достижимость лаконичных форм дается ценой нестандартных индивидуальных решений, мало приспособленных к передаче программ в чужие руки. Лозунги "Программируйте все сами!" и "Не бойтесь все переписывать заново!" правильно отражают подход к программированию на Форте. Успех достигается явным максимализмом в тщательной отладке и способностью видеть задачу программирования в развитии.

Язык Форт предложен Чарльзом Маури в 1968 году. К середине 70-х Форт стал третьим по популярности после Бейсика и Паскаля, завоевавшим свои позиции при освоении микропроцессоных средств. По технике программирования Форт весьма похож на макроассемблер, только вместо системы команд над машинными словами в нем используется система операций на стеком.

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

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


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

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

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

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

Традиционно отмечаемые недостатки Форта:

сложность записи программ для новичков;

необходимость понимания всех процессов исполнения программы;

трудность отчуждения программы от системы программирования;

нестандартность языка, это не типовой язык программирования;

строго последовательное исполнение потока операция;

слабый контроль ограничений на оперативную память;

неполный цикл разработки не приспособлен к производству.

Активный популяризатор Форта Мур отметил: "Форт не уравнитель, а усилитель!"

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

Имеются константы TRUE и FALSE, символизирующие логические значения.


Заключение в кавычки "строка" означает вариант со счетчиком и ограничитель - 0

Состояние системы программирования можно исследовать на уровне системных переменных. Различается состояние компиляции (создание кода программы) и интерпретации (непосредственное исполнение программы). Если STATE = 0, то система ведет исполнение программы.

Системная переменная BASE задает систему счисления.

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

DROP (X --)1) = сбросить из стека DUP (X -- X X) = скопировать вверх NIP (X1 X2 -- X2) = сбростиь предпоследний OVER (X1 X2 -- X1 X2 X1) = предпоследний наверх PICK (XN ... X0 N -- XN ... X0 XN) = выборка из середины стека ROLL (XN ... X0 N -- XN-1 ... X0 XN) = перестановка на заданную глубину ROT (X1 X2 X3 -- X2 X3 X1) = перестановка трех верхних элементов SWAP (X1 X2 -- X2 X1) = обмен местами TUCK (X1 X2 -- X2 X1 X2) = копирование под вершину DEPTH (-- N) = глубина ?DUP (X -- X X\=0) = ? истина

Кроме обычных арифметических операций имеются эффективно реализуемые:

1+ 1- 2+ 2- 2/ половина

Слово стека занимает 16 разрядов, но имеются операции над двойными словами - в 32 разряда:

2drop 2dup 2over 2rot 2swap

Есть вариант умножения чисел без потери точности - результат пишется в двойное слово:

UM* (a,b cc)

Система программирования использует при работе ряд стеков:

R - стек возвратов C - стек компиляции F - стек чисел S - стек словарей

Имеются операции, работающие с адресами и памятью:

@ (adr -- x) чтение - разыменование ! (x adr --) запись

ALLOCATE выделить память FREE освободить память RESIZE заменить размер IOR код завершения операции

ALLOT (N -- адр) резервирование памяти в словах HERE (-- А) адрес слова , компиляция со стека UNUSED (-- N) остаток памяти

Операции заполнения памяти предусматривают следующие вариции кодов росписи:

FILL char ERASE 0 BLANC пробел

Возможно пересылка блоков памяти:

CMOVE CMOVE> MOVE

Арифметические операции:

+ - * / (n1 n2 -- n3)


*/ (n1 n2 n3 -- n4) n1 * n2/n3 "рабочая лошадка", эффективно выполняющая часто встречающееся сочетание операций.

* OVER - SWAP DUP *

Пример 4.1. Программа для подсчета по формуле (x,y,z -> x**2 + y * z - x)

Новые слова можно вводить в форме:

: имя опр;:SQ DUP (-- A,B,B) * SWAP (B**2, A) DOP * (B**2, A**2) +; (B**2 + A**2)

Пример 4.2. Введение нового слова SQ для подсчета суммы квадратов (A,B -> A**2 + B**2)

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

Средства размещения слов в словарь:

IMMIDIATE (--) немедленное исполнение в любом состоянии FORGET убрать из словаря

Обозначение систем счисления:

DECIMAL HEX LITERAL

Моделирование переменных и констант:

VARIABLE имя - переменная в словарь знач имя ! - присвоить = запись в переменную имя @ (a -- x) - чтение в стек из переменной знач CONSTANT имя (X --) - создание константы по стеку имя (-- x) - конст стек знач VALUE имя (X --) - переименование

Богато представлена логика и операции сравнения:

and or xor not < = > <> :<= :>= :<> 0< 0= 0>

Средства управление процессами - ветвления: условное выражение и переключатель.

усл IF часть-то THEN усл IF часть-то ELSE часть-иначе THEN

зн-0 CASE зн-1 OF ветвь1 ENDOF --- ---

[ветвь-иначе] ENDCASE

Моделирование циклов:

кон-зн нач-зн DO тело-цикла LOOP кон-зн нач-зн DO тело-цикла шаг +LOOP ?DO - м.б. ни разу

I - текущее значение счетчика J - внешний цикл

UNLOOP сброс счетчика LEAVE выход из цикла

... BEGIN ... AGAIN бесконечный цикл ... усл WHILE ... REPEAT ... !ложь______! ... BEGIN ... усл UNTIL !ист________!

Манипулирование стеками:

n STACK s новый стек S размера N ws PUSH запись в стек S POP перенос в стек данных s POP s ST@ скопировать s ST! сброс стека

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


Системы программирования на Форте содержат препроцессор CREATE, средства работы со статическими динамическими метками, объявления отношений, связывания имен, подключения альтернативных словарей и использования системных вызовов. Возможно работа на уровне обычного ассемблера:

CODE ... ENDCODE

KEY ввод с клавиатуры KEY? есть ли символ? ACCERT [=EXPECT ] ввод строки PARSE адр слова в буфере и его длина

При работе со словарем, рассматриваемым как список слов, можно применять отношение порядка:

ORDER - в порядке поиска

Имеются средства работы с событиями, исключениями (0 - успех) и прерываниями:

CATCH - THROW

Можно создавать метаопределения:

CREATE DOED>

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

В отличие от языка Forth предложенный Дж.Шварцем машинно независимый машинно ориентированный язык программирования Little включает средства обработки битовых строк в привычную языковую схему языка Фортран. Сохраняется обычная система подготовки и понимания программ, меняются лишь операции по обработке данных и набор встроенных типов данных. Данные - это битовые строки произвольной длины, а операции обеспечивают манипулирование битовыми строками как на уровне отдельных подстрок и битов, так и на уровне крупных, совместно используемых блоков и структур данных. [[32]]

X = 23 .f. 1,10, a (2) = 44 /* в поле с 1 по 10-й разряд записать 44 */ .ch. 5, text = 'A' /* в 5-й символ текста записать 'A' */

Листинг 4.1. Примеры операторов присваивания в языке Little

subr START; /* Разбор оператора присваивания языка Little */ size SYM (48); call SCAN (SYM); /* Чтение первого символа */ call ASSIGN; return; end;

subr ASSIGN; /* Разбор оператора присваивания, первый символ которого уже прочитан процедурой SYM */

if TC(SYM).EQ. TC ( '.' ) go to ASS; if TC(SYM).EQ. TC (NAME) go to NAME1; ERROR;

/ASS/ call SCAN (SYM); /* левая часть*/ IF TC (SYM).ne. TC (PREF) ERROR; call SCAN (SYM);

IF TC (SYM).ne.


TC ( '.' ) ERROR; call SCAN (SYM); call SCAN (PREF); /* f, s, e, ch */ /* выделение поля из левой части */ call SCAN (SYM);

IF TC (SYM).ne. TC (NAME) ERROR; go to NAME1;

/NAME1/ call SCAN (SYM); if TC(SYM).EQ. TC ( '=' ) go to NAME2; if TC(SYM).EQ. TC ( '(' ) go to RI-PAR; ERROR;

/RI-PAR/ call SCAN (SYM); IF TC (SYM).ne. TC (EXPR) ERROR; call SCAN (SYM); IF TC (SYM).ne. TC ( ')' ) ERROR; Call SCAN (SYM); IF TC (SYM).ne. TC ( '=' ) ERROR; go to NAME2;

/NAME2/ call SCAN (SYM); IF TC (SYM).ne. TC (NAME) ERROR; return;

/NO/ end;

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

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

  1)

  Круглыми скобками выделена схема изменения стека

й разряд записать 44

X = 23 .f. 1,10, a (2) = 44 /* в поле с 1 по 10- й разряд записать 44 */ .ch. 5, text = 'A' /* в 5-й символ текста записать 'A' */

Листинг 4.1. Примеры операторов присваивания в языке Little

Закрыть окно

subr START; /* Разбор оператора присваивания языка Little */ size SYM (48); call SCAN (SYM); /* Чтение первого символа */ call ASSIGN; return; end; subr ASSIGN; /* Разбор оператора присваивания, первый символ которого уже прочитан процедурой SYM */ if TC(SYM).EQ. TC ( '.' ) go to ASS; if TC(SYM).EQ. TC (NAME) go to NAME1; ERROR; /ASS/ call SCAN (SYM); /* левая часть*/ IF TC (SYM).ne. TC (PREF) ERROR; call SCAN (SYM); IF TC (SYM).ne. TC ( '.' ) ERROR; call SCAN (SYM); call SCAN (PREF); /* f, s, e, ch */ /* выделение поля из левой части */ call SCAN (SYM); IF TC (SYM).ne. TC (NAME) ERROR; go to NAME1; /NAME1/ call SCAN (SYM); if TC(SYM).EQ. TC ( '=' ) go to NAME2; if TC(SYM).EQ. TC ( '(' ) go to RI-PAR; ERROR; /RI-PAR/ call SCAN (SYM); IF TC (SYM).ne. TC (EXPR) ERROR; call SCAN (SYM); IF TC (SYM).ne. TC ( ')' ) ERROR; Call SCAN (SYM); IF TC (SYM).ne. TC ( '=' ) ERROR; go to NAME2; /NAME2/ call SCAN (SYM); IF TC (SYM).ne. TC (NAME) ERROR; return; /NO/ end;

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

Закрыть окно

Языки макрообработки текстов

Изучается устройство ряда макропроцессоров, используемых при обеспечении гибкости кода программ. Кроме достаточно известных GPM и Trac, ассемблерной макротехники и препроцессоров систем программирования [[4],[28]], рассматриваются макропроцессоры нестандартных языков программирования, применявшиеся при факторизации текстов программ, разрабатываемых одновременно на разные архитектуры.
Макропроцессоры - мощный инструмент повышения емкости действий, образующих процессы информационной обработки. Главное предназначение макросов в системах программирования - достижение гибкости и переносимости текстов программ, применяемых в разных условиях. Многие трудности такого применения макротехники связаны с проблемой контроля типов данных на уровне текста программы. Исследования систем переписывания термов и разметки текстов пока не дали практичных решений в этой области. Современные информационные системы как правило содержат макропроцессоры как инструмент настройки на различные стандарты подготовки и обработки данных.
Начнем с классификации макропреобразований по мощности допустимых воздействий на обрабатываемые данные, предложенной в 1973 году А.А. Берсом:

чисто текстовая подстановка, обеспечивающая подготовку текстов по шаблонам и формулярам;

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

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

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

Для автономных макропроцессоров характерны специальные механизмы регулярного конструирования различимых текстов:

управляющие символы;

счетчики;

генераторы уникальных значений;

блоки активности (разметка);

встроенные функции;

управление вводом-выводом.

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

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

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

макрос меняет текст программы,

подпрограмма меняет данные программы и логику процесса исполнения программы.

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

Большинство макропроцессоров допускают переменные макропериода - глобальные и локальные макропеременные.

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

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

ряд = | <сч = 0> -> [ 0 ] | | | [ ( | сч | + 1] | | | ряд [ сч - 1 ] | | | [ ) ] |______________________


ряд (6) = (6+ (5+ (4+ (3+ (2+ (1+0))))))

Пример 5.1.

Макротехника результативна не только на текстах, но и на геометрических фигурах, графах и кодах. Например, макросами можно описать всем известное пентамино, оптимизацию и кодогенерацию программ.

Техника строковой обработки обычно поддерживается операциями вычисления длины строки, выделения подстроки и конкатенации строк.

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

Подстановка аргументов

Использование библиотек

Допущение переменных и структур данных

Присвоение значений переменных

Ветвления и переходы

Циклы, иерархия и рекурсия

Динамика обработки и создания новых макросов

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

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

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

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


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

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

$ mak, a1, a2, ... aN; - вызов макроса1)

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

~0 ~1 ~2 ... ~N - описание не нужно

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

< S > - блокировка подстановок в S

Достаточно всего одной встроенной функции DEF, выполняющей введение макропределений.

$ DEF, mak, опр;

Пример 5.2. Введение новых макроопределений GPM

$ Def, size, 6; $ size; => 6 x ($size, $size) => x(6,6) size$size => size6

Пример 5.3. Использование макроопределений GPM

$Def, opp, UN~1; $opp, R; => ОШ - нет аргумента

$Def, opp, ; $opp, R; => UNR

Пример 5.4. Использование блокировок в макроопределениях GPM

if A=B then C else D

$A, $Def, A , ; $def, B, ;;

Пример 5.5. Моделирование ветвлений макроопределенем GPM

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

Совершенно иначе выглядит макротехника в не менее лаконичном языке макропроцессора TRAC. Все сводится к макровызовам функций, встроенных и определяемых.

# (F, s1,s2,...,sN)

Встроенные функции:

ds - опр. строки cl - call ss - выделить сегмент rs - чтение строки

#(DS,ПРИМЕР, собака сидит на ковре) #(ss,ПРИМЕР,собака,ковре) #(cl,ПРИМЕР,кошка,кресле) = кошка сидит на кресле

Пример 5.6. Работа с шаблонами на языке Trac

Два интересных механизма макротехники были реализованы в проекте языка Setl при попытке его эффективной реализации посредством языка Little [[49],[32]].

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


Значения флагов можно было инициировать, наращивать или редуцировать и обнулять.

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

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

zxN => N + I --- в строке размещается значение счетчика

zyN = N' => N' (zyN := N') --- задание значения спецпеременной

zaN => A(N+i) --- в строке размещается имя "а", сцепленное со значением счетчика

Пример 5.7. Представление зависимости от процесса формирования текста

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

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

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

  1)

  Символ $ набран вместо параграфа

Пример ряд = | <сч = 0> ->

ряд = | <сч = 0> -> [ 0 ] | | | [ ( | сч | + 1] | | | ряд [ сч - 1 ] | | | [ ) ] |______________________ ряд (6) = (6+ (5+ (4+ (3+ (2+ (1+0))))))

Пример 5.1.

Закрыть окно

$ DEF, mak, опр;

Пример 5.2. Введение новых макроопределений GPM

Закрыть окно

$ Def, size, 6; $ size; => 6 x ($size, $size) => x(6,6) size$size => size6

Пример 5.3. Использование макроопределений GPM

Закрыть окно

$Def, opp, UN~1; $opp, R; => ОШ - нет аргумента $Def, opp, ; $opp, R; => UNR

Пример 5.4. Использование блокировок в макроопределениях GPM

Закрыть окно

if A=B then C else D $A, $Def, A , ; $def, B, ;;

Пример 5.5. Моделирование ветвлений макроопределенем GPM

Закрыть окно

#(DS,ПРИМЕР, собака сидит на ковре) #(ss,ПРИМЕР,собака,ковре) #(cl,ПРИМЕР,кошка,кресле) = кошка сидит на кресле

Пример 5.6. Работа с шаблонами на языке Trac

Закрыть окно

zxN => N + I --- в строке размещается значение счетчика zyN = N' => N' (zyN := N') --- задание значения спецпеременной zaN => A(N+i) --- в строке размещается имя "а", сцепленное со значением счетчика

Пример 5.7. Представление зависимости от процесса формирования текста

Закрыть окно

Базовые понятия

Сложность перехода от навыков программирования обычных последовательных процессов к организации параллелльных процессов в значительной мере обусловлена системой обучения, привычкой все упорядочивать, выстраивать в однозначные, безвариантые структуры, не замечая зависимости принятых решений от выбора структур и последовательности действий по их обработке.
По мнению Т.Хоара "Параллельная композиция действий внешне не сложнее последовательного сочетания строк в языке программирования" [[25]]. Функциональное программирование на Лиспе и других языках благодаря необычности (не смягчившейся за 40 с лишним лет) и более гибкой модели организации вычислений позволяет предоставить простые примеры для показа непривычных идей параллелизма, интуитивное понимание которых не требует напряжения [[8]].
Теория взаимодействия процессов богата разнообразием схем, что образует естественный полигон для научного творчества профессионального математика, особенно математика, знакомого с информационными технологиями.
При обсуждении тонкостей сложных проблем параллелизма принято привлекать шуточные и игровые сюжеты, такие как притча про пять философов, читатели-писатели, банкир, торговые автоматы, точное понимание которых не требует математической символики. Кажущаяся простота таких примеров помогает без затруднений воспринять сложность идей параллелизма [[25]].
Ряд моделей параллельных процессов концептуально сродни недетерминизму. Многие из них строятся как коллективное поведение объектов - автоматов с состояниями, изменение которых рассматривается как вычислительный процесс.
Термин "процесс" используется для обозначения поведения "объекта".
Описание процесса начинается с определения класса событий, представляющих интерес для участвуюущих в нем объектов. Множество имен событий, используемых при описании процесса или объекта, называют алфавитом.
Первая абстракция при моделировании процессов - исключение времени, т.е. отказ от ответов на вопрос происходят ли события строго одно за другим.
Это обеспечивается следующими договоренностями:

элементарные действия исполняются мгновенно,

протяженное действие: всегда пара событий - начало и конец,

нет точной привязки действий к моменту времени,

определены отношения "раньше-позже", "одновременно", "независимо",

совместность событий понимается как отношение "синхронизация",

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

Если известно, что процесс P может произойти вслед за событием x, влекущим этот процесс, то событие x называют префиксом процесса P.

x -> P -- P за x

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

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

Пример 6.1. Рассмотрим автомат, установленный в здании НГУ на 4-ом этаже, продающий кофе.

Торговый автомат: {деньги, кофе} (деньги => ( кофе => автомат ) )

- нет кофе без денег - нет двойных порций

сломанный автомат - нет кофе

(деньги => СТОП )

- нет действий = нет событий

Пример 6.2. [25] Рассмотрим простые задачи типа перемещения фишки на клетчатой доске по свободным позициям.

X
O		X

На данной доске фишка может двигаться лишь вправо или вверх. При множестве событий - { враво, вверх } правильный процесс можно специфицировать как:

( враво вверх вправо => СТОП )

Пример 6.3. [25] Простейшая модель часов - типовой пример рекурсивного описания процессов.

Часы: { тик-так }

(тик-так - часы) - рекурсия

Пример 6.4. [25] Небольшое изменение разрешенных позиций на клетчатой доске показывает возможность выбора вариантов хода событий при выполнении процессов. Появляется понятие "меню".

	X
O

( вверх => СТОП | вправо вправо вверх СТОП )

| - представление вариантов в меню процесса


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

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

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

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

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

Языки управления процессами

Приводится обзор технических проблем управления процессами. Рассматриваются базовые средства для решения таких проблем на уровне функционирования операционных систем (ОС), исполнения отдельных задач и разработки информационных систем. Языки реализации ОС.
Внешне языки управления процессами выглядят как нечто среднее между макроассемблерами и языками высокого уровня. Различие проявляется в понимании данных, подвергаемых обработке, и командах, к которым сводятся процессы обработки:

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

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

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

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

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

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

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

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

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

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

Реализация процессов

Следуя Хоару представим, что события можно реализовать как атомы языка Лисп, а процессы определять как функции, задающие реакции на события. Структуры данных стандартных языков программирования, таких как Паскаль-Си даже при ООП-расширении менее удобны для расширяемой реализации, полезной при обсуждении понятий.
В таком случае реализация процесса - это функция, определяющая ход процесса по начальному событию. Таким событием может быть в частности готовность входных данных. Функциональная модель представления процессов позволяет легко описывать и взаимодействие процессов в виде функционалов, т.е. функций над процессами, представленными как функциональные переменые.
При определении взаимодействий используется понятие "протокол". Протокол - это последовательность символов, обозначающих произошедшие события.
< вправо вверх вправо >
Обычные операции над списками обеспечивают основные манипуляции с протоколами, возникающими при определении взаимодействий:
Конкатенация списков сужение - пересечение голова-хвост * - все конечные протоколы порядок по префиксам длина замена символа чередование индекс обратный порядок выборка-вырезка композиция
Особый интерес представляют монотонные функции над протоколами, допускающие аналитику прогнозирования поведения и доказательные построения. Важное направление анализа - проверка соответствия объектов спецификации процесса.

Взаимодействие параллельных процессов

Разнообразие схем взаимодействия процессов требует особой заботы об экономии концепций, понятий и их представлений. Функциональны подход к програмированию ценен именно возможностью унификации понятий, различие которых мало существенно с точки зрения их реализации. В этом плане можно не придавать значения разнице между процессами, объектами, системами и их окружениями. Все это определенные процессы с заданной схемой взаимодействия и разными преписанными ролями в более общем процессе информационной обработки.
Взаимодействие - это события, в которых требуется участие ряда процессов. При необходимости взаимодействие процессов может быть пошагово синхронизовано. Представляя процессы функциями, взаимодействия процессов естественно могут быть заданы как взаимосвязанные рекурсивные функции.
Именование и пометка процессов дают основания для удобной связи символики представления процессов с текстами программ, порождающих процессы.
Дальнейшее развитие базовых понятий, используемых при организации параллельных процессов связано с привлечением недетерминизма и общих разделяемых ресурсов, к обсуждению которых мы еще вернемся в лекции 9.
В качестве примеров, показывающих типовые схемы взаимодействия, принятые в основных областях задач параллельного программирования рекомендуется рассмотреть однородные вычисления, такие как задачи на шахматной доске или обработка векторов или матриц, асинхронные процессы, такие как задачи про философов и читателей-писателей, а также приемы синхронизации и оптимизации, описанные в книге Хоара [[25]]. Некоторые примеры будут рассмотрены в лекции 11, посвященной языкам параллельного программирования и высокопроизводительных вычислений.
Учебная демонстрация проблем программирования взаимодействующих процессов показана на примере исполнителя "Машинист" языка начального обучения программирвоанию Робик [[43]].
Роль параллелизма в современном программировании распределенных систем подробна рассмотрена [[21]]
Покажем простейший пример автоматизированного перехода от последовательных процессов к параллельным.

Пример 6.5. Распараллеливание. Параллельная реализация ветвления.

Условный оператор	Эквивалентное выражение, приспособленное к распараллеливанию
if X then Y else Z	(x * y) + (~x * z)

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

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

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

Более подробно со средствами управления процессами на уровне ОС можно ознакомиться в книге [[13]] и курсах по операционным системам, например, "Основы работы в ОС Linux. Лекция 5 : Оболочка bash".

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

Данные и программы

Рассмотрим на примере языка Лисп подход к представлению данных и программ в языках функционального программирования.
Любые структуры данных начинаются с элементарных значений. Следуя Лиспу, в функциональном программировании такие значения называют атомами или символами. Одинаково выглядящие атомы не различимы по своим свойствам, хотя проявления этих свойств могут быть обусловлены контекстом использования атомов. Каждый атом имеет список свойств. Когда атом читается (вводится) впервые, тогда для него и создается список свойств. Список свойств характеризуется специальной структурой, подобной записям в Паскале, но указатели в такой записи сопровождаются тэгами, символизирующими тип хранимой информации. Первый элемент этой структуры расположен по адресу, который задан в указателе. Остальные элементы доступны по этому же указателю с помощью ряда специальных функций. Элементы структуры содержат различные свойства атома. Каждое свойство помечается атомом, называемым индикатором, или расположено в фиксированном поле структуры.
Функция CONS строит структуры данных из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, - в правой.
Функция CAR обеспечивает доступ к первому элементу списка - его "голове", а функция CDR - к укороченному на один элемент списку - его "хвосту", т.е. к тому, что остается после удаления головы.
Функция ATOM позволяет различать составные и атомарные объекты: на атомах ее значение "истина", а на структурированных объектах - "ложь".
Функция EQ выполняет проверку атомарных объектов на равенство.
Различие истинностных значений в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение "ложь" - это всегда Nil.
Любая структура данных может быть построено из атомов с помощью CONS, и любая его часть может быть выделена с помощью CAR-CDR.

Атом Nil, рассматриваемый как представление пустого списка (), играет роль ограничителя в любом списке.

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

Самая простая форма выражения - это переменная. Она может быть представлена как атом.

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

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

Соответствие между именем функции и ее определением можно задать с помощью специального конструктора функций. Вместо конструктора LABEL, описанного в лекции 1, в реальные системы программирования включают ряд средств с разными особенностями подготовки, реализации и применения определений функций. Common Lisp включает в себя конструктор функций DEFUN, первый аргумент которого - имя функции, второй - список аргументов функции, а третий - тело определения функции. Формальным результатом DEFUN является ее первый аргумент, который меняет свой статус - теперь это имя новой функции. Определение функции строится с помощью неявного LAMBDA-конструктора, объединяющего список аргументов функции и тело ее определения.

Пример 7.1. Новая функция "третий".

Определение функцииКомментарии

(DEFUN третий (x) (CAR (CDR (CDR x))) ) ; Атом "третий" связан ;с выражением " ( LAMBDA (x ) (CAR (CDR (CDR x ))) ) "	имя новой функции параметры функции тело функции

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


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

Композиции функций можно строить с помощью вложенных скобок.

(функция1 (функция2 аргумент21 аргумент22 ... ) аргумент2 ... )

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

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

(QUOTE (A B C) ) - константа (A B C) объявлена

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

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


(COND (p1 e1) (p2 e2) ... (pk ek) ) | |_______|__________|_______ ветви условного выражения |_______|___________|__________ предикаты для выбора ветви

Каждый предикат pi или ветвь ei может быть любой формы: переменная, константа, вызов функции, композиция функций, условное выражение.

Специальные функции QUOTE, COND, LAMBDA и DEFUN существенно отличаются от обычных функций CAR, CDR, CONS, ATOM, EQ правилом обработки аргументов. Обычно функции получают значения аргументов, предварительно вычисленные системой программирования по формулам фактических параметров функции. Специальные функции не требуют такой предварительной обработки параметров. Они сами могут выполнять все необходимое, используя представление фактических параметров в виде списков.

Определения могут быть рекурсивными.

(DEFUN премьер (x)(COND ((ATOM x) x) (T (премьер (CAR x ))) ))

Пример 7.2. Новая функция "премьер" выбирает первый атом из любого данного

Собственно механизм связывания пока определен не был.

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

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

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

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

Пример 7.7. Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn:

(defun map-comp (fn al vl); fn покомпонентно применить ; к соотвественным элементам AL и VL (cond (xl (cons (funcall fn (car al) (car vl)) ; Вызов данного FN как функции от элементов двух списков (map-comp (cdr al) (cdr vl)) ) ) ) )

Теперь покомпонентные действия над векторами, представленными с помощью списков, полностью в наших руках. Вот списки и сумм, и произведений, и пар, и результатов проверки на совпадение:


(map-comp #'+ '(1 2 3) '(4 6 9)) ; = (5 8 12 ) Суммы (map-comp #'* '(1 2 3) '(4 6 9)) ; = (4 12 27 ) Произведения (map-comp #'cons '(1 2 3) '(4 6 9)) ; = ((1 . 4)(2 . 6)(3 . 9)) Пары (map-comp #'eq '(4 2 3 ) '(4 6 9)) ; = (T NIL NIL ) Сравнения

Достаточно уяснить, что надо делать с элементами списка, остальное довершит функционал map-comp, отображающий этот список в список результатов заданной функции.

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

(defun mapf (fl el) (cond ; Пока первый аргумент не пуст, (fl (cons (funcall (car fl) el ) ; применяем очередную функцию ; ко второму аргументу

(mapf (cdr fl) el) ; и переходим к остальным функциям, ) ) ) ) ; собирая их результаты в общий список

(mapf '(length car cdr) '(a b c d )) ; = (4 a (b c d ))

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

Возможны средства управления областями действия имен и их определений.

На практике сложилась традиция в систему функционального программирования включать специальные функции, обеспечивающие иерархию контекстов, в которых переменные обладают определенным значением. Для Clisp это LET и LET* [[73]].

Let сопоставляет локальным переменным независимые выражения. С ее помощью можно вынести из сложного определения любые совпадающие подвыражения. Пример:

(defun UNION- (x y) (let ( (a-x (CAR x)) (d-x (CDR x)) )

(COND ((NULL x) y) ((MEMBER a-x y) (UNION d-x y) ) (T (CONS a-x (UNION d-x y)) ) ) ))

Let -1) сопоставляет локальным переменным взаимосвязанные выражения. Она позволяет дозировать сложность именуемых подвыражений. Пример:

(defun ( (member (a x) (let* ( (n-x (null x)) (a-x (car x)) (d-x (cdr x)) (e-car (eq a a-x)) )

(COND (N-X Nil) (E-CAR T) (T (MEMBER A D-X))) ) ))

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


Flet - специальная функция, позволяющая вводить локальные нерекурсивные функции.

defun - позволяет вводить новые определения на текущем уровне.

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

В качестве примера повышения гибкости определений приведено упрощенное определение Лисп-интерпретатора на Лиспе, полученное из М-выражения, приведенного Дж. Мак-Карти в описании Lisp 1.5 [[75]]. Уменьшена диагностичность, нет предвычислений и формы Prog.

В сравнении с определением в лекции 1 уточнена работа с функциональными аргументами:

(DEFUN EVAL (e al ) (COND ((EQ e NIL ) NIL ) ((ATOM e ) ((LAMBDA (v ) (COND (v (CDR v ) ) (T (ERROR 'undefvalue )) ) ) (ASSOC e al ) ) )

((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) ) ((EQ (CAR e) 'FUNCTION ) (LIST 'FUNARG (CADR fn ) al ) ) ((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) ) (T (apply (CAR e) (evlis (CDR e) al ) al ) ) ) ) (DEFUN APPLY (fn args al ) (COND

((EQ e NIL ) NIL ) ((ATOM fn ) (COND

((MEMBER fn '(CAR CDR CONS ATOM EQ )) (SUBR fn agrs al )) (T (APPLY (EVAL fn al ) args al )) ) )

((EQ (CAR fn ) 'LABEL ) (APPLY (CADDR fn ) args (CONS (CONS (CADR fn ) (CADDR fn )) al ) ) )

((EQ (CAR fn ) 'FUNARG ) (APPLY (CDR fn ) args (CADDR fn)) ) ((EQ (CAR fn ) 'LAMBDA ) (EVAL (CADDR fn ) (APPEND (PAIR (CADR fn ) args ) al )) (T (APPLY (EVAL fn al ) args al )) ) )

Пример 7.1.

Определения assoc, append, pair, list - стандартны.

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

ERROR - Функция, выдающая сообщения об ошибках и сведения о контексте вычислений, способствующие поиску источника ошибки.

С другими расширениями и вариантами Лисп-интерпретатора можно ознакомиться в курсах Интернет-Университета ИТ, посвященных функциональному программированию и языку Лисп [[8]].


Расширение системы функционального программирования осуществляется простым введением/удалением соответствующих свойств атомов и функций.

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

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

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

Функциональные языки программирования достаточно разнообразны. Существует и активно применяется более трехсот диалектов Лиспа и родственных ему языков: Interlisp, muLisp, Clisp, Sheame, ML, Cmucl, Logo, Hope, Sisal, Haskell, Miranda и др. При сравнении языков и парадигм программирования часто классифицируют функциональные языки по следующим критериям: "ленивый" или аппликативный, последовательный и параллельный. Например, ML является аппликативным и последовательным, Erlang - аппликативным и параллельным, Haskell - "ленивым" и последовательным, а Clean - параллельным и "ленивым".


CMUCL - свободно- распространяемая реализация стандарта common lisp с эффективной компиляцией, осуществляемой как в объектный код, так и в байт-код[[34]]. По сравнению с CLISP CMUCL работает на меньшем количестве платформ и более требователен к памяти. CLISP обладает более мощной поддержкой многоязыковости. Поддерживает Unicode. Так как CMUCL компилируется в объектный код, то программы исполняются быстрее по сравнению с программами на CLISP. Несмотря на это математические примитивы в CLISP очень хорошо реализованы, кроме того, CLISP поддерживает вещественную арифметику с произвольной точностью [[79]].

Рефал. В отличие от ЛИСПа, основу РЕФАЛа составляет сопоставление с образцом. Благодаря этому типовая программа на РЕФАЛе вдвое-втрое короче по объему, чем аналогичная программа на языке ЛИСП, и гораздо более читаема. От ПРОЛОГа РЕФАЛ отличает концептуальная простота. Его сопоставление с образцом работает в прямом направлении, а не в обратном (начиная от цели), как в ПРОЛОГе. Это более естественный подход к написанию алгоритмов, что делает их более легкими для тестирования и отладки.

ML (Meta Language, изначальное предназначение - метаязык для представления систем автоматизации доказательств) имеет важную особенность: полиморфную систему типов данных, разработанную Робином Милнером. Подобная система была раньше предложена Роджером Хиндли и сейчас часто называется системой типов Хиндли-Милнера. Наличие механизма вывода типов позволило избавить программиста от необходимости явно описывать типы функций и в то же время производить строгий контроль типов. ML не чисто функциональный язык, он включает и императивные инструкции. ML развивался и включил в себя многие особенности других функциональных языков. Появилось несколько диалектов, наиболее известные из которых StandardML, CAML и чисто функциональный LazyML.

Haskell. В конце 80-х не было стандарта на чисто функциональный, ленивый язык. Haskell был создан с целью занять эту нишу. Haskell "ленивый", чисто функциональный язык.


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

Dylan. Dylan является попыткой компромисса между функциональным и ОО-подходом. Вследствие чего центральным объектом являются обобщенные функции (generic functions). Язык обладает предопределенной библиотекой, включающей в себя систему исключений, набор функций высшего порядка, средства самоанализа и др [[81]].

Erlang. Создан отделением компании Erricson, однако, является продуктом с открытым кодом. Этот функциональный язык специально создан для поддержки распределенной обработки, параллельности и обработки ошибок. Язык предназначен для систем реального времени и активно используется Erricson при создании телекоммуникационных систем [[80]].

В рамках проекта .Net выполнено большое число реализаций весьма различных функциональных языков программирования, в их числе Haskell, Sml, Scheme, Mondrian, Mercury, Perl, Oberon, Component Pascal, разрабатывается F# - новый язык ФП [[22]]. Еще большее разнообразие предлагает проект DotGNU, пытающийся отстоять приоритет в области разработки переносимого ПО. Развиваются линии учебного и любительского программирования и методично осваивается техника выстраивания иерархии абстрактных машин при определении языков программирования [[82]].

Разработка ЯФП и приспособленность средств ФП к быстрой отладке, верификации, их лаконизм, гибкость, конструктивность и моделирующая сила позволяют рассматривать ФП как основу информационной среды обучения современного программирования на всех уровнях проблематики от алгоритмизации до включения в социальный контекст приложений разрабатываемых ИС. Документация по GNU Clisp, xLisp, CMUCL и другим реализациям языка Lisp доступна на сайтах любителей ФП, а также на многих сайтах [[78],[79],[80],[81],[82]].

  1)

  Примечание. Эквивалентность с точностью до побочного эффекта

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

Рассматриваются общие формы представления информации символьными выражениями и анализируются требования к полноте и эффективности методов их обработки. Вводятся базовые понятия. (Списки и атомы. Данные, значения, функции.) Списки и их обработка. Базовые операции и их свойства. Унификация структур данных при реализации. Накапливающие параметры. Связывание имен. Функциональные аргументы и отображения. Корректность обработки формул. Универсальная функция. Устройство параметризованного интерпретатора функционального языка.
Идея функционального программирования опирается на интуитивное представление о функциях как о достаточно общем механизме представления и анализа решений сложных задач с активным использованием рекурсии [[2]].
Для реализации функций в программах характерен отказ от необоснованного использования присваиваний и низкоуровневого управления вычислениями в терминах передачи управления. Такие функции удобны при отладке и тестировании благодаря независимости от контекста описания и предпочтения явно выделенного чистого результата. Трудоемкость отладки композиций из хорошо определенных функций растет аддитивно, а не мультипликативно [[54]].
Кроме обычных функций, аргументы которых вычисляются предварительно, в ряде случаев можно рассматривать и реализовывать специальные функции, способные обрабатывать аргументы нестандартным способом по любой заданной схеме. В качестве результата функции допускаются варианты значений, равноправно выбираемые из конечного множества значений, подобно псевдослучайным числам.
Организация управления, достаточного для оптимизации и программирования параллельных процессов, реализуется с помощью так называемых "замедленных" или "ленивых" вычислений (lazy evaluation) рецептов, каждый вычисляется не более чем один раз, если его результат действительно нужен [[23],[39]].
Здание функционального программирования получает логическое завершение на уровне определения функций высших порядков, удобных для синтаксически управляемого конструирования программ на основе спецификаций, типов данных, визуальных диаграмм, формул и т.п. [[23],[44],[66]]

Систематическое применение функционального программирования впервые достаточно ярко было продемонстрировано Джоном Мак-Карти и его учениками в методах реализации языка Лисп и программирования на этом языке [[75],[64],[23]]. Наиболее очевидные из этих методов были успешно ассимилированы другими языками и системами программирования. Концептуально близкие идеи "структурного программирования" были сформулированы лишь более чем через десять лет [[9],[11],[70]].

Минимальный набор обозначений, к которым можно свести все правильные, т.е. вычислимые формулы системы, играет роль базиса системы, реализация которого является минимальной версией всей системы. Так, например, базис Лиспа (см. лекцию 2) предельно лаконичен - атомы и структуры из простейших бинарных узлов плюс несколько базовых функций и функционалов. Базис содержит встроенные (примитивные) функции, которые анализируют, строят и разбирают любые структурные значения (atom, eq, cons, car, cdr), и встроенные специальные функции и функционалы, которые управляют обработкой структур, представляющих вычисляемые выражения (quote, cond, lambda, label, eval). Над базисом строятся предельно простые формулы в виде круглоскобочных списков, где первый элемент - функция, остальные - ее аргументы, в том числе переменные, реализуемые с помощью разных вариантов стека или ассоциативного списка. Синтаксис Лиспа не требует особых ресурсов для запоминания разделителей и/или ограничителей и напряженного внимания на распознавание синтаксических позиций в разных рамочных конструкциях. Универсальный разделитель - пробел, ограничители - круглые скобки. В скобки заключается представление функции с ее аргументами. Все остальное - вариации в зависимости от категории функций, определенности атомов и вычислимости выражений, типов значений и структур данных. Функционалы - это одна из категорий функций, используемая при организации управления вычислениями.

Джон Мак-Карти предложил проект языка Лисп в качестве средства исследования границ применимости компьютеров, в частности, методом решения задач искусственного интеллекта.


Лисп послужил эффективным инструментом экспериментальной поддержки теории программирования и развития сферы его применения.

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

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

Функциональное программирование отличается от большинства подходов к программированию тремя важными принципами:

Природа данных

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

Самоописание обработки символьных выражений

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

Подобие машинным языкам

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

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

CAR CDR CONS ATOM EQ

(DEFUN EVAL (e al ) (COND ((EQ e NIL ) NIL ) ((ATOM e ) ((LAMBDA (v ) (COND (v (CDR v ) ) (T (ERROR 'undefvalue )) ) ) (ASSOC e al ) ) ) ((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) ) ((EQ (CAR e) 'FUNCTION ) (LIST 'FUNARG (CADR fn ) al ) ) ((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) ) (T (apply (CAR e) (evlis (CDR e) al ) al ) ) ) ) (DEFUN APPLY (fn args al ) (COND ((EQ e NIL ) NIL ) ((ATOM fn ) (COND ((MEMBER fn '( CAR CDR CONS ATOM EQ )) (SUBR fn agrs al )) (T (APPLY (EVAL fn al ) args al )) ) ) ((EQ (CAR fn ) 'LABEL ) (APPLY (CADDR fn ) args (CONS (CONS (CADR fn ) (CADDR fn )) al ) ) ) ((EQ (CAR fn ) 'FUNARG ) (APPLY (CDR fn ) args (CADDR fn)) ) ((EQ (CAR fn ) 'LAMBDA ) (EVAL (CADDR fn ) (APPEND (PAIR (CADR fn ) args ) al )) (T (APPLY (EVAL fn al ) args al )) ) )

Пример 7.1.

Закрыть окно

(DEFUN премьер (x)(COND ((ATOM x) x) (T (премьер (CAR x ))) ))

Пример 7.2. Новая функция "премьер" выбирает первый атом из любого данного

Закрыть окно

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

  1)

  Примечание. Стилизация примера от МакКарти [[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]].
В результате достигнуто синтаксическое подобие определения грамматики и программы построенного распознавателя. Это значит, что определение можно автоматически отобразить в такой распознаватель. Отображение - функция высокого порядка, вырабатывающая в качестве результата распознаватель языка, порождаемого исходной грамматикой.

Таблица 12.1. Определение распознавателя языка, синтаксически подобное грамматики языка.

Грамматика	<слог> ::= <в-гр> <а-гр> | <а-гр> <в-гр> | <в-гр> <а-гр> <в-гр>
Распознаватель	(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, то необходим набор распознавателей, выявляющих эти понятия, и селекторов, выделяющих их характеристики.
Селекторы имеют смысл лишь при истинности соответствующего распознавателя.

Использование списочных форм в качестве абстрактного синтаксиса позволяет все распознаватели свести к анализу головы списка

Таблица 13.1. Абстрактный синтаксис операторовАбстрактная формаКонкретная форма

(перем 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;

Все селекторы сводятся к композиции car-cdr, выполняемой после соответствующего распознавателя. Так, в приведенных выше формах поля X, C, A1, S1, P можно выделить селектором, определенным как (lambda (fm) (car(cdr fm))) - выделение второго элемента списка, а поля A2, S2, ST, S, расположенные третьими в списках - как (lambda (fm) (car(cdr(cdr fm)))), поле SF - как (lambda (fm) (car(cdr(cdr(cdr fm))))). Такие определения практически не требуют отладки, работают с первого предъявления.

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

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

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

Определение Eval-Apply особенно компактно в стиле p-списка. Иерархию определений можно организовать с помощью блоков Flet со списками определений для шаблонов (перем конст плюс равно) и отдельно для (пусто присвоить шаги если пока).


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

Формально операторы могут рассматриваться как функции, преобразующие полное состояние памяти V. Пусть функция E списочному представлению оператора сопоставляет эквивалентную ему Лисп-функцию, вызываемую в контексте (declare (special N)).

Таблица 13.2. Примеры функциональной реализации операторов и выраженийОператорФункциональный эквивалентАбстрактный синтаксис оператора

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

Таблица 15.1. Материалы Интернет-Университета, дополняющие лекции курса.№Тема лекцииАвторы, название курса и URL

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 )

Этим обеспечивается то, что концепция системы не зависит от физического размещения частей.

На концептуальном уровне для РИС характерны свойства:

разнородность используевых устройств,

целостность (единство) системы,

электронная связность,

высокий уровень взаимодействия между элементами,

свобода выбора конструктивных решений и их улучшения.

На уровне реализации принципиально важна надежность:

отказоустойчивость,

защита транзакций при сбоях,

предсказуемость времени реакции,

настройка-отладка сложных подсистем,

быстродействие диалога между узлами.

В настоящее время массово выполнимы требования к устройствам для реализации РИС, которые должны быть одновременно мощными (высокая пропускная способность) и недорогими (могут простаивать).

Критерии успешности разработки РИС:

оптимальные затраты на разработку,

легкость расширения простым добавлением узлов или перераспределением зон,

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

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

Рассматриваются тенденции современного программирования, еще

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



    Программирование: Языки - Технологии - Разработка

• Программирование
  
• Технологии программирования
  
• Разработка программ
  
• Работа с данными
  
• Методы программирования
  
  
• IDE интерфейс
  
• Графический интерфейс
  
• Программирование интерфейсов
  
• Отладка программ
  
• Тестирование программ
  
  
• Программирование на Delphi
  
• Программирование в ActionScript
  
• Assembler
  
• Basic
  
• Pascal
  
  
• Perl
  
• VBA
  
• VRML
  
• XML
  
• Ada
  
  
• Lisp
  
• Python
  
• UML
  
• Форт
  
• Языки программирования