Учебное пособие 800529
.pdfбыть смоделирована на любом языке программирования, в котором содержатся условные операторы и операторы цикла.
Секрет вычислительной «мощи» МТ заключается в том, что если какие-то алгоритмы А и В реализуются на МТ, то и их различные композиции также реализуются. Кроме того, под литерой можно понимать все: от знака до страницы текста и т.п. И доказательство реализуемости состоит в нахождении способа построения анализирующей программы в виде композиции известных алгоритмов А и В. При этом руководствуются «тезисом Тьюринга»: всякий алгоритм может быть реализован МТ. Этот тезис рассматривается без доказательства, ибо его нельзя доказать. Его можно только обосновать, представляя различные известные алгоритмы в виде программ МТ.
В 1954 г. советский математик А.А.Марков предложил алгоритмическую схему, в которой, как и в МТ, преобразуется слово, но на основе других принципов. В схеме Маркова нет понятия ЛЕНТЫ и подразумевается непосредственный доступ к различным частям преобразуемого слова. А.А.Марков назвал эту схему нормальным алгоритмом. Позже было доказано, что он эквивалентен алгоритму Тьюринга. При этом модель А.А.Маркова в большей степени соответствует понятию программы ЭВМ как явной последовательности выполняемых команд.
Алгоритмы Тьюринга и Маркова используются для целей теоретического характера – обеспечить принципиальную возможность представления любых алгоритмов для доказательства алгоритмической неразрешимости отдельных задач. Для этого используются наиболее простые (элементарные) действия, не подозреваемые в двусмысленности. Из-за этого программа МТ является чрезвычайно громоздкой. Для обеспечения формализованного общения человека в ЭВМ нужны более мощные средства – так называемые алгоритмические языки высокого уровня, являющиеся многоуровневыми.
За нижний уровень языка, называемого аппаратным машинным языком, принимается язык (управления электронных схем!), обеспечивающий выполнение следующих операций: считывание с регистра (ленты Тьюринга!), запись в регистр, пересылка из реги-
111
стра в регистр и сопоставление кодов с образцом или между собой. Регистры, как многоразрядные электронные устройства, обеспечивают прием, выдачу и хранение цепочки битов, их сложение, вычитание, деление, сравнение, инвертирование, тем самым аппаратно обеспечивается реализация арифметических и логических операций в двоичном коде {0, 1}. То есть любое вычисление (на компьютере) – это некий физический процесс (Наука и жизнь, № 2, 2001г.), лишенный интеллектуальной составляющей.
Но такое представление, хотя и «далеко от Тьюринга», но также очень громоздко. Поэтому необходимо укрупнение, которое обеспечивается ассемблированием.
Ассемблер присваивает всем элементам аппаратуры (регистрам, устройствам внешней памяти и др.), всем элементарным операциям мнемонические имена (ADD, R, и т.д.), а громоздкие дво-
ичные числа аппаратно переводит в компактные шестнадца-
теричные. Кроме того, ассемблер избавляет программиста от работы с абсолютными адресами, заменяя их смещением относительно исходного. Из-за этого программа на ассемблере делается кардинально компактнее, сохраняя при этом связь с «железом» компьютера (то есть с его аппаратным устройством). Последнее положение настолько важно, что все операционные системы как программные средства, обеспечивающие совместную работу всех устройств компьютера, а также программы хакеров и вирусы пишутся на языке ассемблера, то есть действуют в «подбрюшье» языков программирования высокого уровня. Поэтому специалисты по защите информации должны владеть ассемблером.
Третий шаг укрупнения языка программирования заключается в использовании синтаксических правил для оперирования с мнемоническими именами ассемблера. То есть язык усложняется (укрупняется) введением договорных знаковых систем, которые (как вы уже знаете – фил. осн. ЗИ) способны сжать представление в 105 – 1011 раз! Получаются языки программирования высокого уровня (их около 2000), которые на 99 % отличаются друг от друга только синтаксисом! Ассемблирование программ, написанных на таких языках, осуществляется специальной программой, называемой ТРАНСЛЯТОРОМ.
112
Синтаксически – знаковое расширение языка программиро-
вания в пределе имеет возможности ЕСТЕСТВЕННОГО ЯЗЫКА. Основное свойство естественного языка состоит в том, что с его помощью можно сказать то, что нужно и, притом, компактным образом, то есть без какого-то дополнительного поиска, пересылки данных и пр. Но основная проблема состоит в трудности формализации того, что «нужно сказать», ибо этот выбор осуществляется интеллектуальным инструментом – разумом субъекта,
вооруженным накопленной картиной мира, из которой ситуативно, по месту, почти без усилий формируется то, что нужно.
Но только (!!) в рамках сформированной картины мира, то есть накопленных знаний и опыта. Формальные системы таким свойством пока не обладают, и вся суть прогресса заключается в стремлении к этому путем разработки более мощных по выразительности структур, способных выразить (отобразить) все, что нужно, компактным образом с использованием алгоритма управления разрешимой (по Тьюрингу) сложности. То есть выразительная мощь структуры определяется двумя факторами: богатством (то есть количеством и разнообразием) выразительных элементов, набором и содержанием операций манипулирования с ними.
При работе с данными различают ТРИ ОСНОВНЫХ ДЕЙСТВИЯ: ПОСТРОЕНИЕ объекта данных и размещение в памяти, ВЫБОРКУ его элемента или всего компонента и ОБНОВЛЕНИЕ. Самой важной операцией (действием) с данными является операция выборки или ДОСТУПА к данным и ее виртуозность. Если элемент данных доступен целиком, то есть НЕДЕЛИМ на части, то такие типы данных называются простыми элементами данных. Если возможен доступ к частям элемента данных, то они называются структурированными элементами данных, имеющих различные структуры, то есть различные формы связи между их частями.
113
3.2.Простые элементы данных, формы их представления в памяти ЭВМ и операции с ними
К простым элементам данных относятся такие, которые недоступны по частям, а используются целиком. Хотя некоторые языки программирования допускают доступ к ним по частям. Физически это объясняется тем, что все данные хранятся в памяти ЭВМ, структурно представляемой последовательностью битов, разделенной с фиксированным шагом на адресуемые слова или биты. Поэтому для представления данных практически нет другого выбора, кроме последовательности битов, к которым (при необходимости) можно осуществить (организовать) доступ.
Однако последовательность битов - "вещь" безымянная; в нее можно разместить различные объекты счѐта: числа, символы, массивы. Чтобы представление данных в памяти сделать более однозначным, его делают состоящим из двух частей:
цепочки битов, кодирующих элемент данных; дескриптора, содержащего дополнительную идентифици-
рующую информацию для декодирования цепочки битов различных типов. (рис. 3.1, с. 57 для случаев 1) и 2)) )
) Здесь и далее в такой форме указывается ссылка на позицию в базовом учебном пособии: Т.Пратт. Языки программирования: разработка и реализация. М.: ―Мир‖, 1979, с.576 (64 тыс. экземпляров). При этом конкретное содержание рисунков рассматривается по книге на упражнениях.
114
|
Дескриптор |
Цепочка битов |
|
||||
1. Целые числа |
|
|
|
|
|
|
|
|
J |
|
|
|
|
||
|
|
|
|
|
|
||
тип данных |
|
|
|
|
|
|
|
|
|
|
|
|
целое число |
|
|
|
|
|
|
|
|
||
= int |
|
|
|
|
|
|
|
|
Дескриптор |
|
|
||||
2. Цепочка литер |
|
|
|
|
|
Цепочка битов |
|
|
С |
8 |
|
|
|
||
|
|
|
|
||||
|
|
|
|
|
|
|
|
тип данных
= char
восемь литер, закодированных в длина це- 8-ми битные байты
почки (в литерах)
|
|
|
|
|
Дескриптор |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Цепочка битов |
|
3. Векторы |
V |
J |
2 |
|
5 |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
тип данных |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= vector |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
верхняя граница |
четыре целых числа подряд |
|
тип элементов |
|
|
|
|
|
|
|
|
|
диапазона изме- |
|
|||
|
|
|
|
|
|
|
|
|
|
|||||
вектора = int |
|
|
|
|
|
|
|
|
|
нения индекса |
|
|||
нижняя граница диапазона изменения индекса
Рис. 3.2. Типичные структуры памяти для трех типов данных
Для данных со структурой дескриптор содержит большее число элементов, то есть несет больше информации. Но он всегда включает в себя индикатор типа данных, определяющий общий класс элементов данных, к которым принадлежат закодированные данные - числа с фиксированной или плавающей точкой, цепочка литер, символ и т.д. Дескриптор относится к категории данных, определяемых системой (а не программистом) и генерируется ав-
115
томатически.
При этом данные, определяемые программистом, состоят из элементов данных, которые программист явно определяет и манипулирует в своей программе. Данные, определяемые системой, обычно генерируются автоматически, когда в них возникает необходимость. К ним относятся: стеки точек возврата в подпрограммах, дескрипторы структур данных, среда ссылок, списки свободного пространства, буферы ввода-вывода и биты, управляющие сбором мусора. Далее это будет разъяснено более подробно.
Цепочку битов, кодирующую элемент данных, можно размещать в одном направленном блоке памяти, организуя их последовательное хранение, или разбивать на некоторое число "кусочков", хранящихся в разных блоках памяти и связываемых вместе указателями. Это так называемое связанное хранение, используемое наиболее широко.
Описание типов данных в программе задается в декларациях, представляющих транслятору информацию о свойствах данных, которыми они обладают во время выполнения программы. Декларация может содержать следующие сведения об элементе данных: тип, размер, имя, точку создания и уничтожения данных, список индексов для доступа, параметры выхода на ассемблер (ассемблерные вставки - для языка С++) и т.д.
А вообще тип данных задается именем, областью определения и совокупностью операций, при помощи которых данные обрабатываются. При этом существует одна операция, общая для всех типов данных. Это операция присваивания (:=), означающая, что значение переменной а (а:=n) должно быть заменено текущим значением переменной n. По другому говорят так: "переменная (а) связывается с переменной (n) и может позже использоваться в процессе выполнения программы".
При этом связывание и время связывания являются центральными понятиями в программировании. Мы можем говорить о связывании некоторого программного элемента с конкретной характеристикой или свойством как о выборе этого свойства из некоторого множества возможных. Момент времени, когда при составле-
116
нии или выполнении программы происходит этот выбор, называется временем связывания.
Можно выделить несколько основных классов времени связывания:
во время выполнения программы (при входе в блок в произвольных точках программы);
во время трансляции (время компиляции); при определении языка; при реализации языка.
Наиболее простые связывания осуществляются во время выполнения программы. Сюда относятся связывания переменных и их значений и … связывание структур данных и переменных с конкретными адресами памяти.
Во многих ЯзПр связывание некоторых важных классов выполняется во время трансляции. Эти связывания включают в себя определение типов переменных, типов и размеров структур данных, а часто и детальное описание структур данных и их связывание с конкретными адресами памяти. Во время последней фазы трансляции – загрузки – оттранслированные программы объединяются и загружаются в память в окончательной форме.
При определении языка сущность связывания состоит в задании набора альтернатив (вариантов связывания), которыми программист может пользоваться при написании программы.
При реализации языка содержание связывания конкретизируется свойствами конкретной машины.
Важную роль в сущности ЯзПр играет следующий факт: когда делается связывание – во время трансляции или во время выполнения программы. Ответ состоит в следующем: если требуется осуществить много связываний, то лучше их выполнить один раз во время трансляции, тогда программа будет выполняться быстро. И наоборот.
Рассмотрим очень кратко конкретные формы представления простых элементов данных.
3.2.1. Числа. Представление чисел в ЭВМ - это многомерный вопрос. Мы рассмотрим только некоторые из них, "структурно"
117
нужные нам, а именно связь представления чисел с дескрипторами.
В большинстве ЯзПр одно число не имеет внутренней структуры, кроме знака (за исключением случаев рациональных чисел, представляемых отношением 2х целых чисел и комплексных чисел, представляемых парой вещественных чисел). Для нас важна не внутренняя организация числа, а структура всего множества чисел, допускаемых в языке: факт их упорядоченности, границы диапазона конечно представляемых чисел, и их плотность в этом диапазоне. В ЯзПр наиболее распространены целые, вещественные, вещественные с двойной точностью, комплексные и рациональные числа.
Большинство ЭВМ имеют аппаратные средства для представления целых и вещественных чисел и вещественных чисел с двойной точностью. Как правило, при этом отсутствуют дескрипторы; числа изображаются простой (неоднозначной) цепочкой битов. Однако, для комплексных и рациональных чисел прямого аппаратного представления нет, они обрабатываются программноаппаратным методом с использованием микропрограмм, усложняющих выполняемые аппаратные операции.
Если во время выполнения программы для чисел требуются дескрипторы, которые аппаратно не представляются, то используют иное представление чисел с элементами программирования. (Представление чисел в памяти ЭВМ по рис. 3.2, с. 66 - 67)
118
Int (с фиксированной точкой), без дескриптора
Real (с плавающей точкой), без дескриптора
|
Тип данных |
|
|||
Real, |
|
|
|
|
|
|
|
R |
|
||
с дескриптором |
|
|
|
||
|
|
|
|
|
|
|
|
|
|||
|
|
Дескриптор, |
|||
|
|
хранящийся в |
|||
|
|
отдельном слове |
|||
Real с дескриптором, хра- |
|
|
|
|
|
нящимся в том же слове |
|
|
|
|
|
Знаковый бит
0 |
. . . . . . . . . |
1 0 1 1 1 |
|
|
|
Цепочка битов фиксированной длины, представляющая число в обратном коде
Знаковый бит порядка
Знаковый бит мантиссы
Подразумеваемое положение точки
1 0 1 . . . . . . . . . . 0
Порядок |
Мантисса |
Подразумеваемое положение точки
Указатель
Представление в виде числа с плавающей точкой, аналогичное вышеприведѐнному
|
|
R |
Знаковые биты и порядок |
Укороченная |
Тип |
|
мантисса |
данных |
Рис. 3.3. Представление целых и вещественных чисел в памяти ЭВМ
3.2.2. Литеры и цепочки литер Иногда одиночные литеры образуют отдельный тип данных,
но чаще таким типом данных является последовательность индивидуальных литер - цепочка литер. Можно выделить 3 разновидности этого типа данных.
1. Цепочка фиксированной длины, задаваемой в декларации. Допускаются только операции, не изменяющие длину цепочки, например, замена литеры. Операция присваивания переменной рассматриваемого типа некоторого значения того же типа сопро-
119
вождается изменением длины цепочки, компенсируемой путем усечения или добавления пробелов.
2.Цепочка переменной длины, предел которой задается в декларации путем указания max длины цепочки. Цепочка может изменяться по длине, но она обрезается, если длина превосходит заданный предел.
3.Цепочка неограниченной длины. Длина цепочки может быть произвольной и не декларируется. Память для хранения цепочки выделяется по мере необходимости.
Цепочки литер представляются в памяти ЭВМ аппаратно. Каждая литера представляется 6-ти или 8-ми битным кодом литеры, а вся цепочка представляется последовательностью таких кодов, хранящихся в последовательных байтах, или укладываемых в последовательные слова памяти. Цепочки фиксированной длины хранятся без дескрипторов, а для цепочек переменной длины дескрипторы необходимы. Дескриптор указывает длину цепочки в двоичном коде (см. рис. 3.4, с. 68).
120