ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
«Синтаксический сахар»: Можно определить ключевые слова для рамочных конструкций; IF (I > 0) THEN BEGIN A = 1; B = 2 END затем написать текст, похожий на Pascal-программу. #DEFINE MAX(A, B) ((A) > (B) ? (A) : (B)) Макрос: Такое определение обеспечивает функцию «максимум», которая реализуется как последовательный код, а не вызов функции. X = MAX(P+Q, R+S); Макровызов: 78 При правильном объявлении аргументов такой макрос будет работать с любыми типами данных. X = ((P+Q) > (R+S) ? (P+Q) : (R+S)); Результат макроподстановки: Нет необходимости в различных видах MAX для данных разных типов, как это было бы с функциями Пример 11. Пример макросов языка C Определения Примечание (defun MF (NF AF BF) (list ‟DEFUN NF AF BF) ) Макрос (eval (MF MNF (A B) (cons B A))) Макровызов (MNF 1 2) Применение результата Пример 12. Пример макротехники на языке Lisp Основные отличия АМ макрогенератора от АМ ассемблера и стековой машины связаны с переходом от обработки простых значений, размещаемых в словах фиксированного размера, к открытой обработке строк произвольной длины и с использованием программируемых определений, расширяющих исходную систему команд и поддерживающих локализацию переменных. Т аблица 21 Парадигматическая характеристика макропроцессора Параметр Конкретика Эксплуатационная прагматика ЯП Главное предназначение макросов в системах программирования – достижение гибкости и переносимости текстов программ, применяемых в разных условиях. В системах программирования макротехника применяется на двух уровнях: препроцессоры обычно формируют входной текст для компилятора; макроассемблеры выполняют сборку кода на уровне генерации ассемблерной программы или еѐ объектного 79 кода. Регистры абстрактной машины E C E – вектор определений и параметров. C – программа, модифицируемая согласно макровызовам. Результат работы макрогенератора – новая форма текста программы. Категории команд абстрактной машины Засылка определений. Сцепление фрагментов в строку. Копирование параметров. Применение определения. Реализационная прагматика Открытая подстановка без контроля границ стыковки фрагментов. Парадигматическая специфика Макротехника близка продукционному стилю программирования, языкам разметки и системам переписывания текстов, в настоящее время активно развивающимся как языки гипертекстов для разработки сайтов и информационных сервисов. Макротехника характерна для ЯВУ, поддерживающих открытую подстановку параметров, вызовы по необходимости при организации отложенных вычислений и специальных функций, использующих пост-обработку параметров. 3.4. Языки управления процессами Рассмотрим базовые средства для решения проблем обработки информации на уровне функционирования операционных систем (ОС), исполнения отдельных задач и разработки информационных систем, активно использующих понятие «файл». Нередко представление процессов и файлов может быть унифицировано, что видно по сопоставлению команд по обработке файлов и манипулированию процессами. 80 Т аблица 22 Параллель между командами над файлами и процессами Действие Файлы Процессы Вывести список Ls Ps Сменить статус Chmod Bg Fg Удалить Rm Kill Сцепить последовательно Cat | конвейер Показать контекст/задания Env Jobs Создать файл/процесс Cp – в новый файл Fork Сменить директорию/процесс Cd Exec Проверить/Ждать Test Wait Переход к результату Echo Eval Формат файла/процесса Таблица строк/записей Список команд с параметрами Описание процесса начинается с определения класса событий, представляющих интерес для участвующих в нем объектов. Множество имен событий, используемых при описании процесса или объекта, обычно предопределено. Первая абстракция при моделировании процессов – исключение времени, т. е. отказ от ответов на вопрос, происходят ли события строго одно за другим. Это обеспечивается следующими договоренностями: – элементарные действия исполняются мгновенно; – протяженное действие: всегда пара событий – начало и конец; – нет точной привязки действий к моменту времени; – определены отношения «раньше – позже», «одновременно», «независимо»; – совместность событий понимается как отношение «синхронизация»; – одно событие из независимых возникает в любом порядке, без причинно-следственной связи. На уровне операционной системы (ОС) информационная обработка выглядит как семейство взаимодействующих процессов, выполняемых по отдельным программам – заданиям или сценариям, размещенным в файлах. Языки для ОС работают с очередями, которые могут быть представлены как строки или файлы. В памяти хранится контекст задания и его сценарий. 81 Контекст содержит перечень доступных файлов. При управлении процессами выполнения заданий используются условия готовности и вырабатываются сигналы, символизирующие успех выполнения действий. Сигналы также хранятся в контексте. Действия могут быть организованы в конвейеры или последовательности и обусловлены успехом предшествующих действий. Очередь может быть пополнена. Функционирование ОС обеспечивает следующие явления и критерии: – порождение новых файлов и процессов по ходу дела; – время жизни файлов и процессов произвольно – нет гарантий; – неограниченная динамика событий; – содержание может быть незавершенным; – изменение содержания и состава; – очередь процессов с условиями готовности. Построение модели языка управления заданиями требует дополнительных операций по работе с очередями, что может быть устроено как «ленивый» список, в конец которого можно встраивать новые элементы функцией Conc. В качестве опорного языка рассмотрен Bash, абстрактная машина которого может быть определена как E – контекст_процесса – вектор записей Имя: Данные + stdin stdout; C – текущий_процесс – строка из команд; D – очередь_отложенных_процессов – вектор записей Имя: Данные. Команды интерпретатора ОС выполняют обмен данными между процессами и контекстом, обработку очереди, файлов и контекста, проверку ряда условий над данными, контекстом и очередью, выработку сигналов, включая установку сигнала о завершении процесса. Т аблица 23 Типичный набор команд языка управления процессами SCQ Описание команды Примечание ECHO Вывод аргументов Визуализация PWD Выводит название текущего рабочего каталога LS Список файлов в текущей директории CAT | MORE Просмотр содержимого текстового файла CD Сменить директорию Манипуляции с файлами CP Копировать файлы 82 MV Переместить или переименовать файл RM Удалить файлы LN Создать символическую ссылку EVAL Конструирование команды на лету и ее выполнение Вычисления EXEC Вызов другого процесса LET Вычисление выражений READ Ввод значения переменной Установка значений SET Изменяет значения внутренних переменных скрипта TEST Проверка условия TRUE Возвращает код успешного завершения = ноль FALSE Возвращает код завершения, свидетельствующий о неудаче Контроль процессов PS (print status) список текущих процессов с их IDs (PID) Визуализация FG Активизировать фоновый или приостановленный процесс Управление активностью процессов. BG Сделать процесс фоновым. Обратная функция от fg. WAIT Ждет выхода из дочернего процесса KILL «Убить» процесс. PID «убиваемого» процесса даѐт PS Обозначения: stdin – стандартный ввод. То, что набирает пользователь в консоли. stdout – стандартный вывод программы. stderr – стандартный вывод ошибок. (Expr) – результат вычисления выражения или успех выполнения процесса. $ – переменная для кода успеха/результата процесса. $* – все аргументы переданные скрипту(выводятся в строку). $! – PID последнего запущенного в фоне процесса. $$ – PID самого скрипта. NN(d) – список номеров и имѐн элементов очереди [ – очереди процессов. NULL – пустой файл. H(d) – голова очереди, точнее – процесс с наивысшим приоритетом. T(d) – хвост очереди, остаток после удаления головы. d = H(d) • T(d). PN – имя текущего процесса. 83 Т аблица 24 Спецификация команд управления процессами RQ RQ’ Примечание e (ECHO String . c) d → (e[stdout] | String) e c d Вывод на стандартное устройство (e[PWD]=DName) (PWD . c) d → (e[stdout] | DName) c d (e[PWD]=DName) (LS . c) d → (e[stdout] | [DName]) c d e (CAT Fname . c) d → (e[stdout] | [Fname]) c d e (CD New. c) d → (e[PWD] := New) c d Установка переменной (e[F1]=Datum) (cp F1 F2. c) d → (e[F1]=Datum; e[F2]=Datum) c d Ссылка на копию файла (e[Fname]=Datum) (RM Fname . c) d → (e[Fname]=NULL) c d Ссылка на пустой файл e (EVAL T1 ... TK . c) d → e (T1 | ... | TK . c) d = e ($* . c) d Выполнение скрипта e (EXEC Fname . c) d → e ([Fname] c) d Выполнение файла e (TEST Expr . c) d → (e[$] := (Expr) ) c d Проверка успешности e (TRUE . c) d → (e[$] := 0 ) c d Установка признака успешности e (FALSE . c) d → (e[$] := 1 ) c d e[stdin=Text] (READ X . c) d → (e[X] := Text ) c d Прием текста e (PS . c) d → (e[stdout] | NN(d)) c d Номера процессов e (BG . c) d → e H(d) (T(d) | <$$, e[PN], c >) Смена статуса процесса e (FG Num . c) (d[Num]=Text) → e (Text | c) (d[Num]:=NULL) e (KILL Num . c) (d[Num]=Text) → e c (d[Num]:=NULL) Поддержаны рамочные конструкции для построения многоярусных условий и циклов. Более подробно со средствами управления процессами на уровне ОС можно ознакомиться в книгах по ОС. 84 Фрагменты Примечание $ ls doc[c-d] $ set 0 noclobber $ cat newletter1 newletter2 >! Oldletters $ at 8:15 jobs Перечень файлов с именами, соответствующими маске Установка системной переменной Управление потоком данных Назначение времени запуска работ Пример 13. Пример программы управления заданиями Внешне языки управления процессами выглядят как нечто среднее между макроассемблерами и языками высокого уровня. Различие проявляется в понимании данных, подвергаемых обработке, и командах, к которым сводятся процессы обработки: – роль данных выполняют файлы – объекты, обладающие собственным поведением и подверженные влиянию внешнего мира. Существование файлов в период обработки не всегда очевидно. Файлы могут участвовать одновременно в разных процессах; – выполнение команды рассматривается как событие, которое может быть как успешным, так и неудачным. Кроме того, существуют внешние события; – реакция на событие программируется как обработчик события, выполняемый независимо от других обработчиков (это отдельный процесс); – программа процесса может быть нацелена не на получение результата за конечное время, а на обеспечение непрерывного обслуживания заданий на обработку объектов; – процесс может быть активным или отложенным; – процессы могут конкурировать за общие объекты; – возможна синхронизация процессов и порождение подчиненных процессов; – программа процесса выглядит как объект и создается как элемент данных, а потом может применяться равноправно с командами; – последовательное расположение команд в программе не считается основанием для их выполнения в точно том же порядке. Выполнение команды может занимать ряд интервалов времени, между которыми выполняются другие команды. 85 На уровне ОС основная работа сводится к управлению заданиями, нацеленными на эффективную загрузку общего оборудования и других ресурсов. Доступ к общим ресурсам обычно регулируется с помощью очередей запросов на обслуживание имеющихся устройств и ресурсов, не только процессора. Обслуживание носит асинхронный характер. Основной критерий качества – возможность продолжить выполнение заданий без принципиальных потерь информации. Любая программа при разработке и отладке выполняется на фоне операционной системы, управляющей процессами ввода-вывода данных ради демонстрации хода обработки данных. Поэтому минимальный контекст отлаживаемой программы – стандартный ввод-вывод, доступный по умолчанию. На уровне языка управления процессами активно используются умолчания, раскрываемые в терминах текущих значений или системных переменных. Основное отличие – укрупнение данных, переход от ячеек и строк к долгоживущим файлам. Кроме того, смягчается зависимость от последовательности вызова процессов, времени их инициирования. Переход к проблемам управления процессами влечѐт радикальное изменение понятия «результат». Это не более чем код успеха/провала завершѐнного процесса. Возможен учѐт приоритетов отложенных процессов. Появляются имена, локализованные внутри скриптов. 86 Т аблица 25 Парадигматическая характеристика языков управления процессами Параметр Конкретика Эксплуатационная прагматика ЯП Абстрагирование от аппаратуры, обслуживание запросов от программных инструментов, обеспечение бесперебойной эксплуатации и функционирования оборудования. Регистры абстрактной машины E C D E – контекст_процесса; C – текущий_процесс; D – очередь_отложенных_процессов. Результатом является код успеха или неудачи завершения процесса. Категории команд абстрактной машины Копирование файлов. Изменение статуса файла или его места в иерархии файлов. Установка или ввод значений переменных. Проверка условий. Запуск процесса. Вычисление выражений. Конструирование команд «на лету». Управление активностью процесса. Ожидание при взаимодействии процессов. Реализационная прагматика Автомат управления процессами требует реализации структуры данных для очередей, регулирующих доступ к объектам. Чаще всего используются две модели – супервизор, контролирующий взаимодействие семейства процессов, или автомат, способный тиражировать себя при ветвлении процессов. И в том и в другом случае функционирование автомата сводится к бесконечному циклу анализа происходящих событий, появление которых влечет включение обработчиков, соответствующих событиям. Проблема остановки решается вне языка на уровне базовых средств или внешним образом через прерывания. Парадигматическая специфика Любая программа при разработке и отладке выполняется на фоне операционной системы, управляющей процессами ввода-вывода данных ради демонстрации хода обработки данных. Поэтому минимальный контекст отлаживаемой программы – стандартный ввод-вывод, доступный по умолчанию. 87 Определение парадигм для ЯНУ не вызывает затруднений – в них явно видна ключевая идея, а семантические системы сравнительно изолированы в определении языка. Основные различия сосредоточены на конкретизации понятия «значение» и спектра средств укрупнения осмысленных единиц при подготовке программы. Функциональные модели ЯНУ достаточно просты. По уровню сложности они проще SECD или SECM, т.к. не гарантируют защиту контекста. Реализационная семантика ЯНУ, как правило, требует введения дополнительных понятий (очередь, логика, словарь, точка возврата, позиция в стеке, шкала прерываний и т.п.), возникающих на уровне схем программ и программисткой терминологии. Механизмы представления и обработки данных, накопленные в ЯНУ, в значительной мере унаследованы методами реализации ЯВУ, что позволяет локализовать изучение таких механизмов. Практика программирования на ЯНУ имеет образовательное значение. Ценящие подготовку высококвалифицированных программистов вузы, готовящие победителей международных чемпионатов по программированию, включают в начальное обучение программирование на ассемблере и управление процессами на Linux. 88 Т аблица 26 Наследование методов ЯНУ парадигмами ЯВУ Механизм Парадигма Примечание Ассемблер ИП ООП Императивный стиль программирования, как на ассемблере, можно устроить на любом процедурно-императивном или объектно-ориентированном языке, ограничив их средства по сложности выражений и исключив иерархию структур данных и классов объектов Стековая машина ЯВУ Стековые машины служат в большинстве ЯВУ основным механизмом поддержки выражений, функций и процедур с вычисляемыми параметрами Макротехника ЛП ФП препроцесс оры Продукционное программирование в стиле макротехники унаследовано логическим программированием, функциональное программирование переносит еѐ на уровень работы со структурами данных. Многие системы программирования на ЯВУ используют такую технику в препроцессорах и как внутренний инструмент при кодогенерации. Управление процессами ООП Механизм управления процессами наследуется парадигмой ООП, использующей взаимодействия объектов с помощью сообщений. Он существенно используется и парадигмой параллельного программирования для описания асинхронных процессов 89 ЯЗЫКИ ВЫСОКОГО УРОВНЯ ЛЕКЦИЯ 4. ИМПЕРАТИВНО-ПРОЦЕДУРНОЕ ПРОГРАММИРОВАНИЕ Стандартное императивно-процедурное программирование (ИП) рассматривает процесс обработки информации как конечную последовательность локальных изменений состояния памяти (императивно- процедурный стиль). Для ИП характерно четкое разделение понятий «программа» и «данные» с учѐтом статических методов контроля типов данных и оптимизации программ при компиляции. Общий механизм интерпретации стандартной программы естественно представить как автомат с отдельными таблицами имен для переменных, значения которых подвержены изменениям, и для меток и процедур, определения которых неизменны. При трансляции программ обычно планируется распределение памяти для значений переменных в зависимости от их типов данных, включая размещение локальных данных в стеке. Выполняется частичный контроль доступа к переменным и совместимости операций и операндов по типам данных с вычислением значений константных выражений (констант, переменных, элементов структур данных, результатов операций и вызовов функций), возможны оптимизирующие манипуляции по управлению вычислениями: СП = (Текст → {Код | Адрес}): Пам [Переменная] → Пам 4.1. Особенности представления программ на C Самый популярный язык программирования C содержит низкоуровневое подмножество, что провоцирует рассматривать его как ЯНУ. Но приспособленность C к представлению обработки иерархии структур данных с помощью программируемых функций дает основания относить его к ЯВУ. Язык C предполагает, что программа собирается из набора файлов, содержащих фрагменты программы и библиотеки функций, подготовленные, возможно, независимо. При этом компилируемая программа представляет собой одноуровневую конструкцию из равноправных определений структур данных и функций. Это означает, что любая функция имеет доступ к любому элементу любой структуры данных и может изменять его значение. Учитывая, что результат программы формируется как последовательность шагов изменения данных, 90 размещѐнных по конкретным адресам, программист вынужден детально и тщательно изучать все тонкости побочных эффектов как своего, так и смежных фрагментов программы. Это оказалось серьѐзным препятствием к повышению производительности труда. –При конструировании кода программы C-компилятор распределяет память для глобальных и локальных данных в статической памяти или в стеке, соответственно. – Встраиваются вызовы библиотечных функций создания-удаления для динамических структур данных и обмена данными, включая ввод-вывод. – Данные бывают константами или переменными, идентифицируемыми с помощью идентификаторов. – Типы данных разделены на основные и производные, созданные с помощью специальных операций, включая создание неоднородных структур данных. – Над типами данных определѐн конкретный набор операций, с помощью которых строятся вычислимые выражения, и схем операторов управления и описания, используемых при конструировании функций. – Многократно используемые функции объединяются в специализированные библиотеки, часть которых включена в системы программирования на языке C. – Компилятору для эффективности кодирования нужна информация о типах данных переменных и результатов функций, но допустимо умолчание в случае типа int. – Возможна спецификация вида используемой памяти, но она носит рекомендательный характер – компилятор учитывает еѐ в меру возможности. – Определения функций обладают некоторой свободой в конкретизации списка параметров на уровне вызова функции, что позволяет программировать функции произвольного числа параметров. – Реализация арифметических операций обладает вариантами, зависящими от основного типа обрабатываемых скаляров в соответствии с разнообразием аппаратной поддержке этих операций. Абстрактная машина (АМ) языка C может рассматриваться как развитие и обобщение АМ для ассемблера, обеспечивающее возможность использовать более сложные структуры данных в качестве регистров. 91 Определение мало отличается от АМ подмножества языка Pascal (см. Лекция 2): s e c m → s‟ e‟ c‟ m‟ Сумматор расширяется до стека промежуточных значений, и появляется дополнительный регистр «Локалы» для локализации хранимых объектов: <Стек_ значений, Локалы, Текущая_Команда, Память > Регистр «Локалы» может быть устроен подобно регистру «E» из SECD- машины Лендина, только хранит он не любые значения, а скаляры или ссылки на значения в «Памяти». Начальное состояние памяти – вектор глобальных переменных, адресуемых подпрограмм и меток. «Локалы» и «Память» образуют контекст исполнения программы. АМ различает следующие категории команд: – засылка значений из памяти в стек; – вычисления над безымянными операндами в стеке при обработке выражений; – пересылка значений из стека непосредственно в память или в регистр Локалы; – организация переходов по метке в программе; – организация ветвлений и циклов; – организация вызовов функций с сохранением/восстановлением локального контекста. Определение Примечание Main (argc, argv, envp) Int argc; Char **argv; Char **envp; { For (i=0; i < argc; i++) Printf (”arg%i:%s\n”, i, argv [i]); For (p=0; *p != (char*)0; p++) Printf (”%s\n”, *p); } Заголовок функции. Описания параметров функции: – число аргументов, – вектор аргументов, – вектор системных переменных. Цикл вывода аргументов командной строки. Пример 14. Программа распечатки параметров командной строки и переменных среды на языке Си. 92 4.2 Структурное программирование Прагматика стандартного программирования не требует подробного описания – она общеизвестна и подробно исследована во многих работах. Тем не менее, следует отметить ряд моментов, связанных со структурным и функциональным программированием. Сложность разработки больших программ, функционирующих в стиле локальных изменений состояния памяти, привела к идеям структурного программирования, налагающим на стиль представления программ ряд ограничений, способствующих удобству отладки программ и приближающих технику стандартного программирования к функциональному программированию: – дисциплина логики управления с избеганием переходов по меткам (goto_less_style); – минимизация использования глобальных переменных в пользу формальных параметров процедур (global_variable_harmful); – полнота условий в ветвлениях, отказ от отсутствия ветви ―else‖; – однотипность результатов, полученных при прохождении через разные пути. Существует большое число чисто теоретических работ, исследовавших соотношения между потенциалом императивного и функционального подходов и пришедших к заключению о формальной сводимости в обе стороны при некоторых непринципиальных ограничениях на технику программирования. Методика сведения императивных программ в функциональные заключается в определении правил разметки или переписывания схемы программы в функциональные формы. Переход от функциональных программ к императивным технически сложнее – используется интерпретация формул над некоторой специально устроенной абстрактной машиной. На практике переложение функциональных программ в императивные выполнить проще, чем наоборот – может не хватать близких понятий. 4.3.Функциональная модель ИП С практической точки зрения любые конструкции стандартных языков программирования могут быть введены как функции, дополняющие исходную систему программирования, что делает их вполне легальными средствами в рамках функционального подхода. Необходимо лишь четко уяснить цену такого дополнения и его преимущества, которая обычно 93 связывается с наследованием решений и привлечением пользователей. В первых реализациях Lisp-а были сразу предложены специальные формы и структуры данных, служащие мостом между разными стилями программирования, а заодно смягчающие недостатки исходной, слишком идеализированной, схемы интерпретации S-выражений, выстроенной для учебных и исследовательских целей. Важнейшее средство такого рода, выдержавшее испытание временем – prog-форма |