Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 74
Текст из файла (страница 74)
Языки Р! У1, СОВО!. и Рааса! позволяют созлавать <(юрмы вариантных записей без определения полей тегов, а объявление объединений оп<оп языка С вообще не допускает создания тега. Реализация этих форм не позволяет осуществлять проверку наличия искомых компонентов. Варианю<ые записи также час~о называются обьвдинвиивм, поскольку каждый вариант записи можно рассматривать как отдельный класс объектов ланных типа запись, а общий для них тип записи получается затем как об ьедп пенис этих множеств объектов лаппых.
Если в гипс не определено поле тета (как в случае тина оп<оп в языке С), то это тнц со свободным обьвдиивниелп если же поле указано, то это тип с диффврвицирпоаиным (различоел<вы<) обьединвнивл<. Термин диффврвицирувмый указывает на то обстоятельство, что возможно (с помо<цью проверки поля тега) определить класс вариантов, к которому принадлежит каждый объект данных из их общего типа. Реализация. Реализовать вариантную запись проще, чем правильно ее использовать. Во время трансляции определяется количество памяти, необходимое для хранения всех компонентов каждого варианта, и отволится такое количество памяти, которое необходимо дзи хранения максимальиоао возможного варианта (рпс, 6.9).
Внутри этого блока памяти кажлый вариант описывает различную компоновку блоков в терминах количества и типов колшонентов. Поскольку размер выделенного блока достаточен, чтобы вместить самый большой вариант записи, то, естественно, во время выполнения программы в нем сможет разместиться любой вариант записи, но часть выделенной памяти не будет использоваться вариан- 264 Глава 6. Инкапсуляция тами меньших размеров. Компоновки различных вариантов определяются во время трансляции и используются лля вычисления смещен«я при выборе компонентов. Во время выполнения лля вариантной записи пе требуется никакого специального дескриптора, поскольку тег-компонент рассматривается просто как другой компонент записи.
Представление записи в случае РауС<азз = За<апе« Представление записи в случае РауС<авв в Нсвт<у Рис. 6,9. Представление в памяти вариантных записей Выбор компонента определенного варианта записи полностью аналогичен выбору компонента обычной записи, когда отсутствует всякая проверка типа. Во время трансляции вычисляется смещение искомого компонента относительно базового адреса, выделенного пол во<о запись блока памяти; во время выполнения программы это смещение добавляется к базовому адресу лля определения местоположения компонента в памяти.
Если компопс«т в данный момент выполнения программы не существует, то полученный адрес соответствует тому месту, где он находился бы, если бы существовал, и от а область памяти будет содержать значение («ли часть значения, или несколько значений), прелставляющее значение компонента текущего варианта записи. Присваиванис какого-либо значения не су<цествующему в данный момент компоненту (в отсутствие проверки) изменяет солержимос области памяти, в которой оп должен бьп бы находиться. Если в данный момент эта область используется как часть компоне<гга влекущего варианта записи, тогда могут произойти непредсказуемые изменения значения зтого компонента (с потенциально катастрофическими лля программы последствиями).
Если при выборе компонентов вариантной записи применяется динамическая проверка типов, то во время выполнения программы точно так же вычисляется значение суммы базового адреса и смещения лля определения местоположения компонента, но в первую очередь проверяется значение поля тега, чтобы убелиться, что в данный момент в памяти существует требуемый текущий вариант записи. бд. Структурированные типы данных 265 6.1.7.
Списки Структура данных, состоящая из упорялоченной последовательности структур данных, обычно называется снискал<. Спецификация и синтаксис. Списки похожи на векторы в том отношении, что они представляют собой упорядоченную последовательность объектов данных. Это означает, что можно определить первый элемент списка (который обычно называется головой списка), второй элемент и т.
д. Однако между списками и векторами есть некоторые существенные различия. 1. Списки редко имеют фиксированную длину. Они часто используются лля представления произвольных структур данных, и обычно их длина увеличивается и уменьшается в процессе выполнения программы. 2, Списки редко бывают однородными. Тип данных каждого элемента списка может отличаться от тина его соседей. 3. В тех языках, в которых используются списки, типы лап ных элементов списка объявляются неявным образом без явного задания атрибутов элементов списков. Синтаксис языка Е1ЯР представляет типичную списковую структуру; ~ганс«овна<ге 0аы) оа<а2 , вагап) Эта конструкция означает, что функция Гопсь<оо<чаь<е применяется последовательно к объектам 0а[а<, 0аЬаь ..., ОаЬа..
Большинство операций языка Е15Р в качестве ар<ументов получают список, и ре. зультатом их выполнения также является список значений, Например, операция своз в качестве аргументов использует цва списка н возвращает список, являющийся последовательным объединением двух исходных, то есть первый список добавляется в начало второго: (соот Ча Ь с) ЧО е Г)) = «а Ь с) О е С Этот пример показывает, что результатом операции сопз является список из четырех элементов, первым из которых служит список (а Ь с).
Четыре элемента полученного списка являются элементами не одного и то< о же типа: первый элемент сам является списком, а остальные являются элементарными объектами данныхх, или атомал<и. Этот пример также иллюстрирует одно характерное свойство языка Е1ЯР.
Сначала вычисляются все аргументы функции. Если бы это выражение было записано без апострофов: (своз (а Ь с) (О е т)) то 1.15Р сначала попытался бы вычислить функцию а с аргументами Ь и с, а затем — функцию <) с аргументами е и б Вероятно, это привело бы к ошибке. Функция (<)ноге х), или, проще, ' х, просто возвращает буквальное значение (1 значение) своего аргумента, позволяя тем самым избежать ненужных в данном случае вычислений.
В языке М1.такжеопрелелены списки. Ихсинтакснс таков; [а, Ь. с]. Вотличие от ПЯР в МЕ списки должны быть однородны, поэтому допускаются списки, состоящие из целых чисел (например, [1, 2, 3]), и списки, состоящие из строк (например, [ "аЬс", "оеГ', "0Ь) "]). 266 Глава б. Инкапсуляция Реализация. Динамическая природа большинства реализаций списков и тот факт, что злелтенты списка редко бывают однородными, означают, что регулярное управление распределением памяти, полезное для реализации векторов и массивов, не будет работать для списков.
В таких случаях, как правило, используется организация управлением памятью на основе связвнньп списков. Элемент списка является простейшим элементом и обычно представляет собой объект данных фиксированного размера. В языке ).(ВР для представления списка обычно необходимо три информационных поля; поле типа и два указателя списков. Если в поле типа задан атом, то остальные два поля являются дескрипторами, описывающими этот атом. Если в поле типа задан список, то первый указатель является головой ()теаг)) списка (его первым элементом), а второй у казател ь является хвостом ((а(() ситтска (его последующими элементами).
На рис. 6.10 изображена структура представления памяти для предыдущего примера: (сопл '(а П с) ' Ш е г)) .= ((а а с) В е т) СТРУКТУРА ДАННЫХ СПИСОК (СОМ5 (А В С) (О Е Е)) СТРУКТУРА ДАННЫХ, ПОЛУЧЕННАЯ В РЕЗУЛЬТАТЕ ОПЕРАЦИИ СОМ5 Рис. 6. )0. Представление списков е памяти 6.1. Структурированныетипыданиых 267 Сходство между средней и иижпсй структурами иа этом рисунке подтверждает эффективность выбранной реализации списков. 1. сопз.
Операция сопз, или 1о< и, реализуется так; создастся новый узел списка и первый аргумент операции сопз помещается в его головпое поле, а второй ее аргумент — в хвостовое поле. 2. Голови. Голови списка — это содержимое (г-зиачеиие) головного поля элемента списка. 3.
Хвост. Хвосп< списка — это содержимое хвостового поля элемсита списка. Язык В18Р был реализован в начале 60-х гг, иа компьютере 1ВМ 704, Это была машина с 36-битовым словом, иа которой два 18-битовых адреса могли храниться в одном 36-битовом регистре. Старшие 18 битов назывались адресным регистром, а младшис 18 битов — декрел<еяпп<ььи ре гис<лром. Сл еловател ь<ю, операция Пеа8 (голова) предо~валяла «содержимое адресного регистра«(сов<оп<а о1 <1<с а<1<1гезз гс8<з<сг, САЕ), а операция 1а<1 (хвост) — «содержимое дскремецтиого регистра» гсоп<еп<з о1<)<е <1ссгсшепг ге81з<сг, С1)К).
Эти аббревиатуры (САВ и С1)К) настолько укоренились в фольклоре, связанном с языком Б18Р, что блюстители чисто< ы этого языка иикогда ие назовут подобные операции пеай и 1а<1. Списки являются базовыми объектами данных в таких языках, как М1., 1.18Р и Рго!ой, цо це входят в определение обычных компилируемых язь<ков типа С, Рааса! или А<)а. Дииамическос управление памятью, псобходимое для представлеиия списков, противоречит принципу максимальной эффективиости регулярных структур управления памятью компилируемых языков. Тем ис мопсе в программе, написанной па каком-либо компилируемом языке, все жс могут использоваться списки, ио только как опредсляемый программистом тип дапиых.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
