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

       

Ассемблер


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

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

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

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

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

Для реализации такого процесса требуется счетчик адресов и таблица идентификаторов.

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

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

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

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


Содержание раздела