Определение языков программирования
Прежде чем анализировать конкретные парадигмы программирования, рассматривается задача определения систем программирования. Строится простейшее определение семантики языка программирования в виде интерпретатора, задающего операционную семантику на примере подмножества языка Лисп.
Обычно при разработке системы программирования различают три уровня: синтаксис, семантика и прагматика реализуемого языка. Разграничение уровней носит условный характер, но можно констатировать, что синтаксис определяет внешний вид программ, семантика задает класс процессов, порождаемых программами, а прагматика реализует процессы в рамках конкретных условий применения программ. При изучении парадигм программирования центральную роль играет семантика, а синтаксис и прагматика используются как вспомогательные построения на примерах. Венская методика определения языков программирования с помощью операционной семантики, использующей концепции программирования при спецификации систем программирования, удобна для сравнения парадигм программирования [[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))
Методы верификации программ активно используют структурную и рекурсивную индукцию (Мак-Карти) при доказательстве таких свойств рекурсивно определенных функций, как эквивалентность.
Поэтому операционная семантика языка программирования, заданная над списочными структурами и поддерживающая все уровни определения языка от текста до кода, включая моделирование средств различных парадигм программирования, образует технологичную основу для решения актуальных проблем разработки надежных информационных систем.
В дальнейших лекциях будут рассмотрены наиболее известные модели различных парадигм программирования. Начиная с низкоуровневого программирования на ассемблере дойдем до суперпрограммирования на языках сверх высокого уровня.
Условные выражения такого вида были введены в математическую теорию вычислений Маккарти (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. Принятые в нем решения представляют интерес как эксперимент по разработке многоуровневых систем программирования.
Круглыми скобками выделена схема изменения стека
й разряд записать 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, <UN~1>; $opp, R; => UNR
Пример 5.4. Использование блокировок в макроопределениях GPM
if A=B then C else D
$A, $Def, A , <D>; $def, B, <C>;;
Пример 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. Представление зависимости от процесса формирования текста
В общем случае интерпретирующие автоматы для макропроцессоров характеризуются возможностью многократной обработки данных, до тех пор пока не будет получен результат без макровызовов. Соответствующая универсальная функция построения результата макрообработки получается реализационно не очень простой.
Подобные механизмы макрообработки текстов используются препроцессорами в стандартных системах программирования и текстовых процессорах. Иногда встречаются и более специализированные средства, использующие счетчиковые переменные, конструкторы уникальных имен, моделирующие иерархию модулей или параметризующие зависимость вариантов программы от целевых архитектур.
Концептуально макротехника близка продукционному стилю программирования, языкам разметки и системам переписывания текстов, в настоящее время активно развивающимся как языки гипертекстов для разработки сайтов и информационных сервисов.
Символ $ набран вместо параграфа
Пример ряд = | <сч = 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, <UN~1>; $opp, R; => UNR |
| Пример 5.4. Использование блокировок в макроопределениях GPM |
| Закрыть окно |
|
if A=B then C else D $A, $Def, A , <D>; $def, B, <C>;; |
| Пример 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]].
Примечание. Эквивалентность с точностью до побочного эффекта
Функциональное программирование
Рассматриваются общие формы представления информации символьными выражениями и анализируются требования к полноте и эффективности методов их обработки. Вводятся базовые понятия. (Списки и атомы. Данные, значения, функции.) Списки и их обработка. Базовые операции и их свойства. Унификация структур данных при реализации. Накапливающие параметры. Связывание имен. Функциональные аргументы и отображения. Корректность обработки формул. Универсальная функция. Устройство параметризованного интерпретатора функционального языка.
Идея функционального программирования опирается на интуитивное представление о функциях как о достаточно общем механизме представления и анализа решений сложных задач с активным использованием рекурсии [[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. Новая функция "премьер" выбирает первый атом из любого данного |
| Закрыть окно |
