Cтраница 3
Если во время выполнения программы требуется наличие дескрипторов для чисел, как в языках Лисп и Снобол 4, необходимо другое представление, поскольку аппаратных дескрипторов нет. В Лиспе вещественное число должно храниться в виде цепочки битов вместе с индикатором типа данных, указывающим, что эта цепочка битов является закодированным вещественным числом. Поскольку программное моделирование арифметики обычно очень неэффективно, желательно применять арифметические операции, имеющиеся в аппаратуре. Можно использовать аппаратное представление числа в виде цепочки битов и, поскольку цепочка битов, скорее всего, занимает полное слово памяти, разместить дескриптор в отдельном слове где-либо в памяти вместе с указателем на слово, содержащее эту цепочку битов. [31]
Обычно структура памяти проста - эта одна длинная последовательность битов, разделенная с фиксированным шагом на адресуемые слова или байты. Для представления элемента данных практически нет другого выбора, кроме последовательности битов. Например, число может быть представлено одной последовательностью битов, указатель - более короткой последовательностью, а массив чисел - более длинной последовательностью. Ясно, что такие представления неоднозначны - одна и та же цепочка битов в зависимости от используемого представления ( кодирования) может изображать любой из возможных элементов данных или совокупность элементов данных. Вследствие этой неоднозначности обычно считают, что представление элемента данных в памяти состоит из: ( 1) позиции памяти, содержащей ( 2) цепочку битов ( в случае двоичной машины), представляющую закодированные данные, и ( 3) дескриптора ( или допвектора), содержащего дополнительную информацию, необходимую для декодирования этой цепочки битов. [32]
Если во время выполнения программы требуется наличие дескрипторов для чисел, как в языках Лисп и Снобол 4, необходимо другое представление, поскольку аппаратных дескрипторов нет. В Лиспе вещественное число должно храниться в виде цепочки битов вместе с индикатором типа данных, указывающим, что эта цепочка битов является закодированным вещественным числом. Поскольку программное моделирование арифметики обычно очень неэффективно, желательно применять арифметические операции, имеющиеся в аппаратуре. Можно использовать аппаратное представление числа в виде цепочки битов и, поскольку цепочка битов, скорее всего, занимает полное слово памяти, разместить дескриптор в отдельном слове где-либо в памяти вместе с указателем на слово, содержащее эту цепочку битов. [33]
Допустим, мы хотим создать новую картинку с помощью графического редактора Paint. В процессе работы создаваемое изображение фиксируется лишь в памяти машины в виде цепочек битов. В этих битах кодируется информация о цвете каждой точки картинки. [34]
Какое представление в памяти подходит для линейного массива, элементы которого могут динамически менять свою длину во время выполнения программы. Ясно, что простое последовательное представление, применявшееся для линейных массивов до сих пор, не годится, поскольку каждое новое присваивание может потребовать, чтобы более длинная цепочка битов заняла место более короткой, что привело бы к перестановке других элементов массива. Отметим, что число элементов в массиве постоянно в течение всего времени выполнения программы; может изменяться только длина индивидуальных элементов. В этих условиях удобно следующее представление: представим массив вектором указателей на значе ния и будем хранить цепочки битов, представляющие значения, в каком-то другом месте памяти. Вектор указателей может тогда храниться ноеледовательно, поскольку размер каждого указателя является постоянной величиной и не зависит от типа значения, на которое он указывает. [35]
Если во время выполнения программы требуется наличие дескрипторов для чисел, как в языках Лисп и Снобол 4, необходимо другое представление, поскольку аппаратных дескрипторов нет. В Лиспе вещественное число должно храниться в виде цепочки битов вместе с индикатором типа данных, указывающим, что эта цепочка битов является закодированным вещественным числом. Поскольку программное моделирование арифметики обычно очень неэффективно, желательно применять арифметические операции, имеющиеся в аппаратуре. Можно использовать аппаратное представление числа в виде цепочки битов и, поскольку цепочка битов, скорее всего, занимает полное слово памяти, разместить дескриптор в отдельном слове где-либо в памяти вместе с указателем на слово, содержащее эту цепочку битов. [36]
Машинный язык вычислительной машины представляет собой на-юр последовательностей ( цепочек) битов, которые воспринимаются машиной как команды; действия, выполняемые каждой машинной командой, определяются электронными схемами вычислительной машины. Язык ассемблера - это символический язык, являющийся программным инструментом. Программы, написанные на этом языке, могут непосредственно транслироваться на машинный язык с помощью системной программы, называемой ассемблером. Результатом работы программы ассемблера является объектный модуль, содержащий цепочки битов ( совокупность которых составляет программу на машинном языке), а также информацию, которая указывает программе загрузчика, в какую область памяти вычислительной маши - - ны поместить эти цепочки битов. [37]
Обычно структура памяти проста - эта одна длинная последовательность битов, разделенная с фиксированным шагом на адресуемые слова или байты. Для представления элемента данных практически нет другого выбора, кроме последовательности битов. Например, число может быть представлено одной последовательностью битов, указатель - более короткой последовательностью, а массив чисел - более длинной последовательностью. Ясно, что такие представления неоднозначны - одна и та же цепочка битов в зависимости от используемого представления ( кодирования) может изображать любой из возможных элементов данных или совокупность элементов данных. Вследствие этой неоднозначности обычно считают, что представление элемента данных в памяти состоит из: ( 1) позиции памяти, содержащей ( 2) цепочку битов ( в случае двоичной машины), представляющую закодированные данные, и ( 3) дескриптора ( или допвектора), содержащего дополнительную информацию, необходимую для декодирования этой цепочки битов. [38]
Машинный язык вычислительной машины представляет собой на-юр последовательностей ( цепочек) битов, которые воспринимаются машиной как команды; действия, выполняемые каждой машинной командой, определяются электронными схемами вычислительной машины. Язык ассемблера - это символический язык, являющийся программным инструментом. Программы, написанные на этом языке, могут непосредственно транслироваться на машинный язык с помощью системной программы, называемой ассемблером. Результатом работы программы ассемблера является объектный модуль, содержащий цепочки битов ( совокупность которых составляет программу на машинном языке), а также информацию, которая указывает программе загрузчика, в какую область памяти вычислительной маши - - ны поместить эти цепочки битов. [39]
Обычно структура памяти проста - эта одна длинная последовательность битов, разделенная с фиксированным шагом на адресуемые слова или байты. Для представления элемента данных практически нет другого выбора, кроме последовательности битов. Например, число может быть представлено одной последовательностью битов, указатель - более короткой последовательностью, а массив чисел - более длинной последовательностью. Ясно, что такие представления неоднозначны - одна и та же цепочка битов в зависимости от используемого представления ( кодирования) может изображать любой из возможных элементов данных или совокупность элементов данных. Вследствие этой неоднозначности обычно считают, что представление элемента данных в памяти состоит из: ( 1) позиции памяти, содержащей ( 2) цепочку битов ( в случае двоичной машины), представляющую закодированные данные, и ( 3) дескриптора ( или допвектора), содержащего дополнительную информацию, необходимую для декодирования этой цепочки битов. [40]
Хеширование является основным методом хранения множества, когда совокупность возможных элементов множества велика. Когда она мала, применимо более простое представление, использующее одну цепочку битов. Предположим, что совокупность содержит N элементов. Тогда множество элементов совокупности можно представить битовой цепочкой длины JV, где t - й бит цепочки равен 1, если et принадлежит множеству, и 0, если не принадлежит. Эта битовая цепочка является характеристической функцией множества. При таком представлении включение элемента в множество сводится к присваиванию единичного значения соответствующему биту, исключение - в присваивании соответствующему биту нулевого значения, а принадлежность определяется простым опросом соответствующего бита, В большинстве машин имеются операции логического умножения ( и) и логического сложения ( или) над битовыми цепочками, позволяющие прямое и эффективное выполнение операций над множеством. Такие средства в аппаратуре являются серьезным аргументом в пользу представления множеств с помощью цепочки битов. [41]