Лекции, страница 3

Другой пример: функциональная спецификация структурного типа «одномерный массив из пяти элементов вещественного типа, пронумерованных от 0 до 4», включает в себя возможные изображения значений этого структурного пша, (пятерки слов), возможные изображения значений его элементов (последовательность двух групп цифр, разделенных точкой, со знаком или без знака), интерпретацию любого такого изображения как числа с фиксированной точкой в позиционной системе счисления с основанием 10., поэлсментные операции и отношения (атрибуты вещественного тина), функцию доступа к значению 200 массива (поэлементный доступ по имени массива и индексу его элемента, причем индекс может принимать только значения О, 1, 2, 3 или 4), функцию модификации массива (модификация любого элемента массива как переменной вещественного типа приводит к модификации массива).

Логическое описание это отображение функциональной спецификапии на, средства выбранного языка программирования. При выполнении этого отображения могут быть две ситуации: 1) в выбранном языке программирования есть подходящий тип данных; 2) подходящий тип данных в языке не определен. В первом случае в программу включан>т описание объектов имеклцегося типа, в соответствии с синтаксическими правилами этого языка. Например, при необходимости описать объект Х как а~переменную целого типа» в раздел переменных Паскаль-программы следует включить предложение Х: 1пФеиег; а в модуль програ>имы на Си описатель 1пФ Х; так как и в тох>, и в другом языке программирования определен тип целый.

Во втором случае необходима декомпозиция объекта, на такие составные части, которые могут быть описаны как отдельные объекты программ>я средствами выбранного языка программирования, или программное моделирование требуемого для решения задачи типа данных. При таком моделировании следует использовать типы данных., определенные в языке как базовые, и реализовать необходимые операции и отношения процедурами и функциями.

Машина Тьюринга манипулирует только литерами, поэтому целый тип должен быть промодслирован работой со словами-изображениями, как это было сделано в первой части курса. В настоящее время трудно привести пример языка, .где совсем бы нс было чисел., но в первых версиях Лиепа, Снобола и Пролога это имело место. и приходилось соотве'Гс'Гвующие функции реализовь>ва"гь вру">ну>о, Например, если в языке программирования нет записей (Фортран), то их поля кодирун>тся как отдельные переменные, присваивания и сравнения реализук>тся группами соответствук>щих скалярных операций, а массивы записей - таблицы — - согласованными наборами неагрегированных векторов. Пусть требуется написать программу обработки таблицы из 100 строк, каждая из которых состоит из трех компонент.

И пусть первая компонента принимает целочисленные значения (табельный номер), вторая -" текстовые данные длиной не более 20 знаков (фамилия), а третья --. значения действительных чисел (доход). Если для реализации (в соответствии с приказом по министерству авиационной промышленности СССР!) надо использовать язык Фортран, то приходится учитывать, что в этом языке нет записей. Поэтому одним из вариантов реализации может быть декомпозиция обрабатываемого массива и описание его частей одномерными массивами Фортрана, согласованными между собой по порядку расгюложения элементов: 1ХТЕСЕК 1П (100) ЬОС1САЬ МАМЕ (2000) 201 ЕХТЕСЕВ.

!.ЕХ (100) КЕАЕ ВЛЕ.ЛК'г' (100) Здесь целый массив и1 является вектором из 100 компонент, причем 1-тый элемент содержит табельный номер г-того сотрудника. Доступ к тс кетовым данным в массиве папге (типа 1ои1са1, т. к. литерного типа в Фортране нет!) осуществляется с помощью простого вычисления индекса (п — 1) 20+ 1. В массиве Хоп (тоже из 100 компонент) на 1-тое место помещена длина фамилии сотрудника, поскольку в Фортране нет и строкового типа и приходится отмеривать строки-отрезки массива паше вручную.

В массиве ва1агу содержатся вещественные числа — значения третьих компонент элементов исходных данных. Их порядок должен строго соответствовать расположению целых чисел в векторе Ы Другой вариант реализации обработки исходного массива с помощью языка Фортран может быть основан па использовании описателя ес1шха1епсе, аналогичного вариантной заггиси. При выборе языка Паскаль для реализации решения той же задачи не требуется декомпозиции исходной таблицы па векторы-столбцы, так как этот язык позволяет использовать массив записей, каждая запись которого состоит из именованных полей, а каждое поле записи может иметь свой тип и длину: маг со1!аЬогаСога: аггау(Е ..100! оЕ' гесогс1 01: ЕпСеиег; пап1е:аггау[1..201 оГ сЕгаг; за!агу: геа1 епс1; Физическое представление -- это конкретное отображение на память машины обьектов программы в соответствии с логическим описанием.

Такое отображение всегда связано с линеаризацией структуры ~51, так как ггамять машины обычно состоит из некоторых едипьщ (слов или байтов), пронумерованных последовательными целыми числами, начиная с пуля. Используя многомерный массив па языке программирования, иногда необходимо знать принцип его липеаризации, и учитывать его при ручной навигации по массиву. Например, двумерный массив (матрица) в Фортране липеаризуется «по столбцам» (наследие архитектуры !ВМ-709, на которой впервые был реализован Фортран), а в языке Паскаль — «по строкам (естественный порядок чтения слева направо и сверху вниз; в некоторых культурах читают по столбпам (иероглифы) или справа, налево (семитские письменности)). Поэтому при передаче матрицы из Паскаль-программы в Фортрановскую библиотечную подпрограмму ес необходимо транспонировать.

Если перодается массив регулируемого размера, то необходимо помнить, что его линеаризация не является главно- диагональным кусочком матрицы, а его элементы просто будут размещены в строчном или столбцовом лексикографическом порядке. Конструктивные особенности памяти как последовательности слов с произвольным доступом обуславливают два вида физического представления объектов в памяти машины: сплотпое и цепное. Сплоилное представление это представление, при котором объект размещается в памяти машины в непрерывной последовательности единиц хранения. Например, переменная целого типа представляется на физическом уровне одним машинным словом, состоящим из двух, четырех или восьми байтов с последовательными адресами.

При этом адрес 202 н(,рВОГО байта ДОлжсн был'еэ кра'!'е(еэ!хл лВум, чс "Гыр(.'м и:Еи ВОсьми сОО'!" ЛЕетс'!'Вее(ЛЕО, и Он считается адресом всего слова. Этого требует конструкция устройства памяти, выдающего не отдельные байты, а, целые слова. В противном случае придется тратить два такта устройства на выборку одного СЕ!Ива.

Для всех простых об"ьектов используется сплошное представление. Оно часто применяется для таких структур данных, как массив, очередь, стек, дек (вспомните, что при доказательстве тезиса Тьиеринга-Черча массив был первоначально пост1еоен как Отрезок ленть! Машины '1'ькЕре(нга!). Спло(иное п1Еедставлсние Имеет эфф(ективнуке аппаратнук! по;едержку, поскольку для доступа к эл(ментам требует((я п1еостос индексное вычисление (номер слова — 1) х длина слова с фиксированной малой ценой доступа 0(1).

Для внешних электромеханических устройств, основанных на последовательном движении носителя, сплошное представление является единственно возможным, поскольку скачкообразное движение к произвольному элементу не предусмотрено конструкцией. 1(ее!!(ое е(редстаелее(еее - это такое представление, при котором значение объекта, разбивается на отдельные части, которые могут быть расположены в разных участках памяти машины (необязательно подряд), причем эти участки тем или иным способом связаны «в цепочку» с помощью указателей, т. е. они содержат ссылки па следующие части объекта.

Цепное представление используется, как правило, для динамических структурных объектов (списки, деревья, очереди, стеки и деки). Если об ьект имеет статически заданный конкретный размер или такой размер можно задать, исходя из каких-либо разумных соображений, сознательно ограниче(езая тем са; мым максимальный размер такого обьекта (например, задать наибольший допустимый размер очереди), то щее.п(очтительнее сплошное представление; при этом уе(рощается доступ к значению объекта и к его компонентам. В щютивном случае используется цепное представление.