ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
Парадигматическая характеристика Pure Lisp Параметр Описание Эксплуатационная прагматика ЯП 7 Язык учебного назначения, созданный специально для изучения методов функционального программирования на языке Lisp, успешно применяется при решении задач с исследовательским компонентом, требующих быстрой отладки. Особенности системы понятий Все понятия сведены к разным категориям понятия «функция», унифицированы представления функций и значений, выполнение программы рассматривается как отображение списка аргументов в результат. Перечень понятий, распознаваемых на уровне абстрактного синтаксиса Символьное выражение (S-выражение), атом, вычислимая форма, переменная, константа, ветвление, элементарные функции, определение функции, именование функции, применение функции, аргумент функции, значение. Базовые средства ЯП NIL, CONS, CAR, CDR, ATOM, EQ, QUOTE, EVAL, COND, LAMBDA, DEFUN. 7 Уровень языка, его ниша в полном жизненном цикле программ, соответствующая технология. 55 Семантические расширения 8 Работа с числами и строками рассматривается как вспомогательная семантика. Ввод и вывод данных считаются псевдо-функциями, обслуживающими отладку. Отдельное расширение языка поддерживает функции с пост-вычислением аргументов – специальные функции. Регистры абстрактной машины Стеки для хранения результатов, локальных значений переменных, вычисляемой формы и дампа, обеспечивающего защиту контекста вычислений (S E C D) Категории команд абстрактной машины Засылки в стек, вычисления над стеком, пересылки из стека, ветвления, применение функции, выходы из ветвлений и функций, восстановление контекста, поддержка рекурсии. Реализационная прагматика 9 Списки из бинарных узлов, содержащих пару тэгированных указателей. Тэг показывает тип данного, адресуемого указателем. Автоматизировано освобождение памяти служебной программой «Сборщик мусора». Парадигматическая специфика 10 Исторически основополагающий классический язык, поддерживающий функциональное программирование в полном объѐме. Ещѐ один пример такой же компактной парадигматической характеристики. Т а б л и ц а 1 2 Парадигматическая характеристика ядра языка Pascal, поддерживающего методику структурного программирования Параметр Конкретика Эксплуатационная прагматика ЯП Язык учебного назначения, созданный для обучения студентов методам программирования решений задач, готовых для эффективной реализации при поддержке автоматным моделированием. Особенности системы понятий Программа и данные – раздельные сущности. Выполнение программы сводится к шагам изменения состояний памяти, хранящей данные. Используемые в программе идентификаторы подчинены иерархии 8 Вспомогательные семантики, их описание относительно концептуальных языков. 9 Структуры данных и традиционно подразумеваемые механизмы реализации 10 Роль языка в формировании поддерживаемой им парадигмы и/или перечень поддерживаемых парадигм. 56 областей видимости, задаваемых вложенностью определений процедур и функций. Процедуры и типы данных не являются значениями. Возможно конструирование новых типов данных и приведение типа данных к заданному. Перечень понятий, распознаваемых на уровне абстрактного синтаксиса. Скаляр, вектор, значение, ключевые слова, константа, переменная, тип данных, операция, выражение, операнд, элемент вектора, сравнение, действие, последовательность действий, ветвление, цикл, определение процедуры/функции, вызов процедуры/функции. Базовые средства ЯП. TRUE, FALSE, перечислимые значения, :=, a[i ], IF, WHILE, PROCEDURE, st1 ; st2 . Семантические расширения Разные виды чисел, записи, множества, указатели, метки, передачи управления, функции, переключатели, конструирование типов данных, ввод- вывод, файлы, строки, библиотеки. Регистры абстрактной машины Стеки промежуточных результатов, локальных переменных и параметров, выполняемой процедуры и вектор памяти (S E C M). Категории команд абстрактной машины Засылки в стек, вычисления над стеком и памятью, пересылки из стека и локальных переменных, ветвления, передачи управления, вызовы процедур. Реализационная прагматика Память распределяется статически по блокам заданного размера, обработка векторов использует вычисление смещений от базового адреса и подразумевает контроль границ отведенной под вектор памяти, при необходимости привлекаются библиотеки, поддерживающие ввод-вывод, работу с файлами и динамической памятью. Парадигматическая специфика Прецедент строго определения языка программирования, обладающего не слишком высокой сложностью в реализации, поддерживающего методику результативного структурного программирования. Может выполнять роль эталонного монопарадигматического языка при сравнительном анализе языков и определении их парадигматической характеристики. Средства и методы программирования складывались на фоне быстрого расширения сферы применения компьютерных технологий и стремительного взлѐта эффективности элементной базы. Наряду с 57 расслоением парадигм программирования в зависимости от глубины и общности технических решений по организации процессов обработки данных происходит их интеграция в рамках новых языков программирования, всѐ более полно поддерживающих жизненный цикл программ. В результате обнаружились явные сложности классификации языков программирования и определения их принадлежности конкретной парадигме программирования. Рассмотрение технических особенностей языков и систем программирования через их парадигматическую характеристику может дать достаточно лаконичные формы их определения относительно ряда простых концептуальных языков. 58 ЛЕКЦИЯ 3. ЯЗЫКИ НИЗКОГО УРОВНЯ Методика парадигматической характеристики ЯП иллюстрируется на материале языков низкого уровня (ЯНУ). Программирование или кодирование на ЯНУ ассоциируется с одноуровневыми структурами данных, обусловленными архитектурой и оборудованием 11 . При хранении данных и программ используется общая глобальная память с произвольным доступом. В принципе достижима предельная эффективность программ, но их отладка осложнена сочетанием «низкий старт – высокий финиш». Иными словами, легко достичь успеха в первых упражнениях, но трудно создать программный продукт и обеспечить его квалифицированное сопровождение. Для ЯНУ характерна однозначность соответствия между программой и процессом, порождаемым при ее реализации. Поэтому анализ операционной семантики ЯНУ можно выполнить на уровне абстрактной машины (АМ), вполне определяющей свойства программ и процессов, подготовленных с помощью ЯНУ. Как правило, при определении абстрактной машины ЯНУ достаточно трех регистров, назначение которых соответствует реализации понятий «результат», «программа», «память» или «результат», «контекст», «программа». Традиционно к ЯНУ относят машинно-зависимые языки ассемблера, макропроцессоры, машинно-ориентированные языки, языки управления процессами. Для таких ЯНУ характерно, что все действия в программе выражены явно. Программа – произвольная смесь команд, соседство которых практически не ограничивается. Доступны любые фрагменты данных и программ. Предопределены все базовые средства по представлению значений и структур данных в памяти и схема управления их обработкой, что позволяет четко относить ЯНУ к конкретной парадигме. Представляют интерес и другие подходы к машинно-ориентированному эффективному программированию. Язык Forth – пример организации вычислений над стеком. Его можно рассматривать как язык-ядро с возможностью практически неограниченного проблемно-ориентированного расширения. Операционная семантика ЯНУ обычно содержит целочисленную арифметику, ограниченную разрядностью адресов или машинных слов, использует работу с общими, глобальными идентификаторами, поддерживает последовательное управление вычислениями и осуществляет организацию структур данных по принципу соседства элементов, 11 Ассемблер «Эльбрус» и автокод «Инженер» – контрпримеры, показывающие недостаточность чисто приаппаратной оценки уровня языка [14]. 59 расположенных в памяти (вектора, строки, стеки, очереди, файлы). Можно рассчитывать, что так определена базовая часть учебного концентра (элементарного уровня) любого ЯП. Другие вспомогательные семантики языков ассемблера, макропроцессора, вычислений над стеком и управления процессами, машинно-зависимых и машинно-независимых машинно- ориентированных ЯП могут рассматриваться как расширения такой базовой части. Здесь не рассмотрены СУБД, языки работы с сайтами и ряд других средств создания распределѐнных систем. 3.1. Императивное программирование на ассемблере Обработка данных с помощью программ, представленных на языке ассемблера, сводится к императивной машинно-ориентированной модели управления процессом выполнения действий, порожденных программой. В центре внимания – конфигурация оборудования, состояние памяти, система команд, передачи управления, очередность событий, исключения и неожиданности, время реакции устройств и успешность процессов обработки информации, нацеленных на свободный доступ к любым возможностям оборудования. Кодирование алгоритма осуществляется на фоне применения дополнительных средств, таких как блок-схемы и документирование, отчасти компенсирующих отсутствие в языке ассемблера понятий уровня программистской фразеологии, а в естественных языках – понятий, возникающих при такой «сверхточной» детализации программ на языке ассемблера. Результативность представления программ обеспечивает макротехника или автоматный подход к реализации алгоритмов – методика автоматного программирования, поддерживающая выделение шагов модели программы независимо от базовых средств ЯНУ. Автоматное программирование возникло до появления ЯВУ. Для языков ассемблера в дополнение к общей семантике элементарного уровня ЯНУ характерно наличие команд над вещественными числами и обработки кодов. Работа с идентификаторами реализуется аппаратными возможностями адресации памяти, обычно обеспечивающей доступ практически к любому хранимому в памяти данному или команде. Управление вычислениями может учитывать результаты промежуточных вычислений (ветвления и переключатели), выполнять итерирование участков повторяемости (циклы) и вызовы подпрограмм, а также обрабатывать внутренние и внешние прерывания. В качестве поддержки структур данных можно рассматривать пересылки блоков заданной длины, 60 а также средства работы с текстом программы. В качестве опорных языков рассмотрены ассемблеры MIX, MSX, P-код, RISC-машина, byte-код (muLisp и Java), MASM и БЭМШ. Традиционно ассемблер реализуют как упрощенный компилятор. Учитывая повышенную нагрузку низкоуровневого программирования на отладку программ, иногда включают в систему программирования дизассемблер и интерпретатор ассемблера, обеспечивающие кроме удобства отладки широкий спектр преобразования программ на ассемблере, их оптимизации и адаптации к развитию аппаратуры. Интерпретирующий автомат для ассемблера устроен проще, чем автомат для абстрактной машины SECD, благодаря встроенной реализации команд – языка конкретной машины и отсутствию локализации имен и их областей действия. Процесс перевода программы с языка ассемблера в язык машинных команд называют ассемблированием. Язык ассемблера оперирует такими данными, как адреса и значения. Нередко для наглядности в записи операндов команд вводится внешнее различие @адресов и #значений с помощью префиксных символов. Возможны специальные формы записи для блоков данных и литералов. При ассемблировании текст программы отображается в частично адресуемый код программы, исполнение которого обычно сводится к поячеечному изменению состояния памяти: ассемблер = (Текст → {Код | Адрес}): Пам [ячейка] → Пам Число слов, отводимое ассемблером под одну символическую команду, зависит не только от собственно кода команды, но и от метода адресации операндов, а возможно, и от других аспектов кодирования программ и данных, обсуждение которых здесь не предполагается. Достаточно констатировать, что программа при ассемблировании распадается на конечные последовательности команд K1 ... Kn, которым сопоставляются конечные интервалы машинных слов W1 ... Wm(a) в зависимости от а – системы аспектов кодирования: [K1 ... Kn] → [W1 ... Wm(a)] Фактически, операндная часть команды – это адреса, специальные регистры, сумматоры, значения в общей памяти, шкала прерываний и состояний или что-то другое, специфичное для конкретной архитектуры. Парадигма низкоуровневого кодирования на ассемблере нацелена на учет любых особенностей компьютерных архитектур. Архитектура 61 компьютера часто определяется как множество ресурсов, доступных пользователю. Это система команд, общие регистры, слово состояния процессора и адресное пространство. Процесс ассемблирования заключается в следующем: – резервирование памяти для последовательности команд, образующих ассемблируемую программу; – сопоставление используемых в программе идентификаторов с адресами в памяти; – отображение ассемблерных команд и идентификаторов в их машинные эквиваленты. Для реализации такого процесса требуется счетчик адресов и таблица идентификаторов. Программист не знает абсолютных адресов ячеек памяти, занятых для хранения констант, команд и промежуточных результатов вычислений, но обычно предполагается, что последовательно написанные команды будут расположены в последовательных ячейках памяти. Язык ассемблера обычно различает следующие категории команд: – вычисления с результатом в сумматоре, для которых следующая команда расположена по соседству; – изменение части состояния общей памяти, при котором следующая команда расположена по соседству; – обработка текста программы без генерации нового кода; – управление со своими правилами выбора следующей команды. При записи команд на ассемблере принято структурировать строки на поля, предназначенные для последовательного размещения метки, кода команды, операндов и комментария. Наибольшее разнообразие возможных решений связано с формами адресации операндов на уровне машинного языка. В зависимости от команды используются разные методы адресации операндов. Обычно система команд ассемблера, кроме команд арифметических вычислений и передач управления, содержит команды манипулирования данными, их ввода-вывода через буфер обмена, возможно, доступный через механизм прерываний. При этом используется код состояния процесса, отражающий свойства текущей выполняемой команды, такие как выработка нулевого или ненулевого кода, отрицательного или положительного числа, переноса разряда за границы машинного слова и др. Имеются команды условного перехода, возвратный вызов процедуры с использованием регистра возврата и передача управления со счетчиком числа циклов. Встречаются и другие команды, разнообразие которых не 62 влияет на особенности ассемблирования и применения ассемблеров в системах программирования. Именно язык ассемблера традиционно выступает в системах программирования в роли конкретной машины (КМ) при компиляции программ. Программирование на ассемблере подразумевает знание специфики системы команд процессора, методов обслуживания устройств и обработки прерываний. Система команд может быть расширена микропрограммами и системными вызовами в зависимости от комплектации оборудования и операционной системы. Это влияет на решения по адресации памяти и коммутации комплекта доступных устройств. Но есть и достаточно общие соглашения о представлении и реализации средств обработки информации на уровне машинного кода. Обычно ассемблер обеспечивает средства управления распределением памяти и управления компиляцией кода независимо от системы команд, что позволяет программисту принимать достаточно точные решения на уровне машинного языка. Существуют средства отладочного исполнения и распечатки листингов. Управление ассемблированием обычно обеспечивает средства авторизации, взаимодействия с отладчиком, текстовым редактором, операционной системой и средствами приаппаратного уровня, доступными через операционную систему и аппаратные средства ввода- вывода (BIOS). По тексту программы при ассемблировании формируется код программы, выполняющий пошаговое преобразование памяти. Программирование на ассемблере требует знания особенностей применяемых команд, их операндов и результатов. Большинство команд изменяют один регистр, если не считать счѐтчик команд. Некоторые команды могут изменять более одного регистра. Например, умножение вещественных чисел может формировать регистр младших разрядов для вычислений с повышенной точностью, деление целых чисел может формировать регистр с остатком от деления, пересылка меняет содержимое целого ряда машинных слов. Спецификация команд абстрактной машины ассемблера может быть задана над тройкой Приведѐм пример системы команд. 63 Т аблица 13 Пример системы команд ассемблера Обознач ение команды Описание команды 12 Примечание LDC Засылка адреса в сумматор. Подготовка операндов LDM Засылка адресуемого слова в сумматор. LDS Косвенная засылка слова в сумматор. RV Пересылка из сумматора в память. 13 Сохранение результата RVS Пересылка слова по адресу из сумматора в память. GO Безусловная передача управления. GS0 Условная передача управления по нулевому значению сумматора. Ветвление GS1 Условная передача управления по ненулевому значению сумматора. GSUB Передача управления с запоминанием адреса возврата в сумматоре. Подпрограмма DEC Вычитание 1 из содержимого сумматора. Арифметические операции INC Прибавить 1 к содержимому сумматора. ADD Прибавление адреса к содержимому сумматора. SUM Суммирование адресуемого слова и содержимого сумматора. Т аблица 14 Пример спецификации команд ассемблера RA RA’ Примечание s (LDC Adr . c) m → (s:=Adr) c m Операнд из команды s (LDM Adr . c) m → (s:=[Adr]) c m Операнд из памяти (s:Adr) (LDS . c) m → (s:=[Adr]) c m Операнд по адресу в сумматоре s (RV Adr . c) m → s c (m|m.Adr:=[s]) Результат из сумматора (s:Adrs) (RVS Adr . c) m → s c (m|m.Adr:=[Adrs]) Результат по адресу s (GO Adr . c) m → s Adr m 12 Следующая команда расположена по соседству или задана командой передачи управления 13 Пересылки – это изменение части состояния общей памяти. 64 (s:0) (GS0 Adr . c) m → s Adr m (s:1) (GS1 Adr . c) m → s Adr m s (GSUB Adr . c) m → @c Adr m Укрупнение действий s (DEC . c) m → (s-1) c m s (INC . c) m → (s+1) c m s (ADD Adr . c) m → (s+Adr) c m s (SUM Adr . c) m → (s+[Adr]) c m Применение ассемблера для разработки многократно используемых модулей налагает определѐнные ограничения на структуру кода программы и его свойства: – перемещаемость. Свойство удобно, когда код программы устроен так, что его можно расположить по любому абсолютному адресу; – листание страниц памяти. Соотношение между адресуемой и реально доступной памятью может требовать пересмотра в процессе выполнения программы; – зависимость от данных. Программа должна учитывать готовность данных и вероятность их обновления, особенно в случае обмена информацией через порты или буферы устройств; – динамика размещения. Программа может размещаться в памяти пошаговым образом, методом раскрутки, с использованием динамической оптимизации, учитывающей статистику реального использования ее составляющих. Примеры программ решения типовых задач средствами ассемблера: Фрагмент программы Примечание LD HL, ADR 1 откуда LD DE, ADR 2 куда LD BC, 2048 сколько LDIR Установить регистр HL Установить регистр DE Установить регистр BC Переместить данные в соответствии с содержимым регистров HL, DE, BC Пример 1. Пример из ассемблера MSX: пересылка блока (ТД не имеет значения) Ассемблер отличается от компилятора меньшей сложностью исходного языка, перевод с которого в машинный язык можно выполнить «один-в- один». Ассемблер часто сопровождается возможностью дизассемблирования, что отличает его от большинства других языков программирования. Изучить язык ассемблера проще, чем любой язык 65 высокого уровня. Знание ассемблера помогает понимать код программы, подготовленной на других языках. Основной механизм укрупнения действий – передача управления подпрограмме. При необходимости уровень языка может быть повышен с помощью макросов. Императивный стиль программирования наследуется большинством ЯВУ, поддерживающих процедурно-императивное и объектно- ориентированное программирование. Т аблица 15 |