Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 84
Текст из файла (страница 84)
Рассмотрим используемое в языке Рааса! представление множества че роз битовые строки. Предположим, что максимальное количество элементов в множестве должно быть мс~ыпе, чем длина слова, обусловленная аппаратной частьнз компьютера. Предложите алгоритмы реализации операций объединения, пересечения и разности множеств и определения принадлежности к множеству (операция ~п) па основе слсдуюьцих встроенных в аппаратуру простейших операций: логическос И, логическое ИЛИ и логичсскос дополнение, применяемые к целым словам. 9.
При использовании хэш-кодирования для представления множеств в памя- ти разрешение конфликтных ситуаций реализуется с помощью методик как повторного хэширования, так и последоватслы шго сканирования. Если разрешено удаление алемептов из множества, возникают нскоторгяе сложности при использовании обеих методик. Объясните эти сложности. 10.
Выберите какой-нибудь язык программирования, в котором определен структурный тип данных. Перечислите атрибцты объектов данных этого типа. Перечислите операции, определенные в языке для объектов этого типа данных. Определите представление в памяти объектов данных этого типа в реализации языка на нашем компьютере. Имеется ли у этих объектов дескриптор во время выполнения программы? Какие атрибуты хранятся в этом дескрипторе? При использовании этого представления требуется ли при выполнении каких-либо операций выделение дополнительного объема или, наоборот, освобождение памяти? 11.
Выберите какой-нибудь язык программирования и структурный тип дан ных в псм. Определите, какие имен>тся операции выборки отдельных элементов или подструктур объекта данных э~ого типа. Для каждой операции вьи борки (или класса таких операций) ответьте на слсдуюшие вопросы: а) может ли существование выбранного компонента быль определено статически (то есть во время компиляции); 298 Глава Б. Инкапсуляция б) мажет ли тип данных выбранного компонента быть определсн статически? Если существование или тип данных не могут быть определенал статичсски, то как именно происходит динамичсская проверка во врсмя выполнения программы — является ли эта проверка обязанностью самого программиста или осуществляется автоматически, то есть предусмотрена реализацисй языка? Допустим, что у вас имеется модифицированная версия языка Разса!, в которой имена полей в записях (но вариантных) могут быть целыми числами, а при выборке полей можно вычислять цслые значения имсн полей, так что, например, для выборки ком понснта записи можно использовать выражение к, ( ! а 21.
+ Объясните, почему в такой версии представление записей в памяти, описапное в разделе 6.1.6, псрестанет быть адскватным? + Модифицируйтс это прсдставлснис так, чтобы опо могло функционировать в новой версии, и предложите формулу доступа (или алгоритм), который можно было бы использовать в этом новом представлении для выбора компонента и, к, гдс к — это вычисленное значение. 12. 13. Повторите задание 12, но для записей с вариантными полями, 14.
Для языка, в котором допускаются вариантныс записи бсз палей тегов 1сво бодное объсдинсние), как, например, в Рааса!, напишите процсдуру ргоселэге З1ЗЭ(!. ~пьедег. чаг Гс геа1 1 которая используст запись с двумя вариантами. Единственным назначени- ем этой процедуры является попытка сбить с толку систему проверки ти- пов. Процедура ь!Ю получает параметр ! целочисленного типа и возвраща- ет в качсстве рсзультата ту жс комбинацию битов, но как вещсствснное число к, при этом нс осуществляя фактичсского преобразования целого значения 1 к всществснному числу. ко эффсктивна инкапсуляция каждого из элементарных типов данных, Для этого нужно написать несколько тсстовых программ, с помощью которых, может быть, удастся опредслить некоторые свойства представления объекта данных каждого типа в памяти.
Чсм мсньшс ~аких свойств можно определить, том болсе эффсктивна инкапсуляция. + Массивы. Можете ли вы определить, какой способ развертывания использован в данном языке — по столбцам или по строкам? Можно ли определить, имеется ли дескриптор времспи выполнения и каковы его формат и содсржанис? + Записи, Можете ли вы определить, в каком порядкс хранятся компоненты записи? Использустся ли упакованная форма хрансния или расположение каждого компонента привязано к границам адрссуемых единиц памяти? 16. Выбсрше какой-либо язык программирования и опредслите в ием абстракт ный тип данных стек целых чисел и операции рэзп п рор, которые добавляют и извлекают элсмснты стека. Представьте, что вы входите в группу программистов, которая разрабатывает какую-нибудь большую программу, и в этой 15. Выберите какой-либо знакомый вам язык и постарайтссь выяснить, насколь- 0.7. Задачи и упражнения 299 программе часто используются стеки целых чисел.
Объясните, как наиболсс эффективно реализовать разработанный вами абстрактный тип данных (используя комбинацию ограничений языка и соглашений по пргяраьчмированию, которым должны следовать все разработчики группы при работе со стеками), чтобы представление стеков в памяти было полностью скрыто и манипулировать им можно было бы только при помощи операций рпзо и рор.
17. Для какой-либо недавно написанной вами программы приведите полную спецификацию параметров и результатов каждой подпрограммы. Не забудьтс также и о неявных параметрах и результатах, Есть ли в вашей программе какие-нибудь подпрограммы; 1) зависящие от предыстории их вызовов; 2) псопрсделе~ шые для некоторых параметров из области их залания? Для каждой подпрограммы приводите хотя бы один пример сокрытия информации, 18. Подпрограмма, которая компилируется в отдельную запись активации и от дельный сегмент кола, иногда называется пооулорно дгодимой, так как во время работы программы сс можно вызвать второй раз, до завершения сс первой активации. Таким образом, может существовать несколько активаций, совместно использующих один и тот же сегмент кода.
Для какого-либо знакомого вам язгяка определите, являнотся лн его подпрограммы повторно входимыми. Какое средство (или средства) языка позволяет запускать вторую активацию до того, как закончилась первая? 19. Для какого-либо знакомого вам языка определите, как в нем определена эк- вивалентность тинов — через эквивалентность имен или структурную эквивалентность? Рассмотритс каждый тип данных отдельно (поскольку способ определения эквивалентности для разных типов может быть разным) и точно объясните, когда две переменные соответствующего типа считаются имеющими одинаковый тип и когда переменная, представляющая фактический параметр, и формальный параметр подпрограммы считаются имсюп1ими одинаковый тип? Различаются лн способы определения эквивалентности для простейших типов данных и для определяемых программистом? 20.
!1редложите три различных способа определения эквивалентности типа для записей и два способа для векторов, основываясь на понятии структурной эквивалентности. 21. Функция ог0 определена следующим образом: се единственным аргументом является элемент некоторого перечисления, а результатом является порядковый номер этого элемента в пере шслснпи (О соответствует первому элементу перечисления, 1 — второму и т, д.), Однако фактически эта функция не выполняет никаких действий, поскольку элементы перечисления во время выполнения программы и так представлены целыми числами, соответствующимии расположению элементов в последовательности (перечислении), Например, если объект, принадлежащий типу перечисление, задан как С!азз = 1Ггеоо, 5оро. ооо~ог, 5еп~ог1 и переменная Х относится к типу С1з55, тооперация присваивания Х:= 5епоог фактически присваивает переменной Х значение 3 и соответственно резуль- зоо Глава 6. Инкапсуляция татом вычисления функции с й Х) будет целое число 3.
Таким образом, функция огЬ ( ) получает значение 3 и возвращает значение 3, то есть фактически не делает ничего полезного (и реализация языка Раэса1 совершенно безболезненно может изъять зту функцию из исполняемого объектного кода). Тем не менее эта функция играет определенную роль, но эффект ее выполнения проявляется во время компиляции.
+ Объясните, каково назначение функции огЬ. Почему Рааса!предоставляет эту функцию, когда она совсем нс имеет никакого эффекта во время выполнения программы? + Для переменной х, определенной выше, объясните действия, производимые во время выполнения следующих двух фрагментов: )Г Х = 5еюьг тпеп ъв огщХ) = 3 гкеп ..
+ Объясните действия, предпринимаемые во время компиляции для проверки типов в двух фрагментах, приведенных вьппе, и в третьем фрагменте: )Гх=згвеп. 22. Объекты сап и сонг ввода и вывода потока данных в Са-ь реализованы как эк земпляргя класса зггеаат Фактически считывание и запись данных происходят за счет перегрузки операций сдвига <( и».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
