Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 66
Текст из файла (страница 66)
+ Определите, статический или динамический контроль типов применяется для проверки правильности каждого использования каждой операции, определенной для выбранного типа данных. Выберите какой-нибудь хорошо известный вам язык программирования и для какого-либо определенного в нем элементарного типа данных сделайте следующее. + Объясните разницу между типом, переменными этого типа и константами этого типа. + Приведите пример ситуации, возникающей в процессе выполнения программы, когда объект данных выбранного вами типа существует, но не является пи переменной, цп константой, + Объясните разницу между объектами данных этого типа и значениями, которые они могут содержать.
Выберите какой-нибудь хорошо известный вам язык программирования и приведите пример элементарной операции, которая: + имеет неявный аргумент; + приводит к побочным эффектам; + не определена для некоторых объектов данных из своей области определения; 5.6. Задачи и упражнения 233 4. Приведите формулу для определения максимазьного количество битов, необходимых для хранения любого целого числа из диапазона М...Х, где М и Ж вЂ” целые числа, причем М< Ю. 5. Приведите два примера конструкций из какого-либо хорошо знакомого вам языка программирования, в котором контроль типов происходит статически, которые не могут быть статически проверены.
Для каждой из них напишите тестовую программу, которая позволит вам выяснить, проверяются ли эти конструкции динамически или так и остаются непроверенными во время выполнения программы. 6. Приведите пример операции из какого-либо языка программирования, ко- торая: + реализована непосредственно через аппаратную часть компьютера; + реализована как подпрограмма; + реализована в виде встраиваемой последовательности кодов. 7. В языках, поддерживающих перечисляемый тип, существует проблема, свя занная с перегрузкой буквальных имен в перечислении.
При объявлении перечисляемого типа в большой программе вполне вероятна ситуация, когда одно и то же имя будет случайно использовано в различных перечислениях (например, имя )пп1ог может быть использовано в определении перечисления С1азз и затем в определении другого перечисления, ОГС1сег9гайе), В этом случае ссылка на литерал Спп1 ог будет неоднозначной, Предложите способ разрешения этой неопределенности, не запрещая перегрузку буквальных имен в перечислении. (Заметим, что в языке Ада такая форма перегрузки разрешена, см. приложение, раздел П.К) 8. Рис. 5.3 иллюстрирует два способа представления целых чисел с использо ванием дескриптора типа.
В одном случае используется дополнительный объем памяти, но имеется выигрьпп в скорости выполнения арифметических операций; в другом, наоборот, за счет увеличения компактности теряется скорость выполнения. Разработайте два аналогичных способа представления целых чисел для вашего компьютера в предположении, что подобный дескриптор занимает по меныпей мере 6 бит. Напишите программы для определения сложения, вычитания, умножения и деления чисел при разработанном вами представлении.
Сравните достоинства и недостатки этих двух способов представления. 9, а) Опишите элементарные типы данных, которые встроены в аппаратную часть вашего компьютера. Определите, имеются ли у этих типов данных дескрипторы. б) Разработайте полный набор дескрипторов типов для встроенных в аппаратуру типов данных. Каждый дескриптор должен содержать информацию, достаточную для определения местоположения, размера (то есть количество используемых битов) и формата данных, которые он описывает.
в) Разработайте структуру представления в памяти дескрипторов, логическая организация которых была установлена в предыдущем задании (6). 2З1 Глава В. Элементарные типы данных Чтобы не пришлось решать задачу определения дескрипторов для дескрипторов, сконструируйте эту структуру таким образом, чтобы дескрипторы сами себя описывали (то есть чтобы можно было однозначно определить длину и формат дескриптора только по заданному местоположению первого бита в этом дескрипторе без дополнительной информапии). 10.
Рассмотримоперациювыбораподстроки<зСГ1пд чэг1эЫе>(<Т1гэГ сйаг.роз.> : <1азг сйаг.роз >Б как она описана в разделе 5.3.1. Приведите два возможных определения смысла этой операции, когда подстрока используется и как источник, и как объект в операции присваивания: ьтап:л:= зтщг и При этом указанные подстроки могут перекрываться. 11. Конкатенация — это основная операция над строками символов.
+ Предположим, что строки имеют переменную длину, максимальное значение которой задано в объявлении (см. рис. 5.5). Разработайте для таких строк операцию конкатенации САТ1, которая вызывается с треви параметрами А, В и С, где А и  — это указатели на блоки памяти, содержащие строки, над которыми надо выполнить эту операцию, а С вЂ” результирующий блок, который исходно содержит некоторую другую строку символов. Строка, состоящая из символов строки А и строки В, помещается в блок С (разумеется, с соответствующим дескриптором). Блоки А и В не должны изменяться в результате действия этой операции.
+ Строки неограниченной длины также могут храниться последовательно, с использованием того же способа представления, но максимальная длина должна быть исключена из дескриптора. Разработайте соответствующую структуру представления в памяти таких строк в предположении, что символы могут быть упакованы по четыре в одном слове. Затем разработайте операцию конкатенации САТ2. У нее должны быть два параметра, А и  — объединяемые строки, а результатом ее выполнения является указатель на новый блок памяти, в котором содержится результирующая строка.
Предположим, что СЯТ2 вызывает функцию АЫ ОСАТЕ1М Б которая возвращает указатель на выделенный блок памяти длиной М слов. + Разработайте СЯТЗ вЂ” программу, которая объединяет строки, представленные связанными списками, аналогичными изображенным на рис.
5.5, 12. На языке программирования, в котором предусмотрены указатели для оп- ределяемых программистом объектов данных и операции пен и й зроэе, которые соответственно распределяют память для вновь созданных объектов и освобождают ее при уничтожении ненужных объектов, напишите фрагмент программы, который генерирует мусор (с точки зрения управления памятью).
Напишите фрагмент программы, который генерирует повисшие ссылки, Если какой-либо из этих фрагментов не может быть написан, объясните, почему. 13. Во многих реализациях языка $о(О ВОЕ4 множество строк символов, используемых в любой момент выполнения программы, хранится в так называе- 5.6, Задачи и упражнения 235 мой центральной таблице строк. Она организована как хэш-таблица, в которой каждый элемент является указателем на связанный список блоков памяти.
Чтобы проверить, принадлежит ли данная строка Х заданному множеству блоков, используется схема двойного хэширования. Х хэшируется дважды — как для получения хэш-адреса, который используется в качестве индекса в центральной табгнще для получения указателя на соответствующий связанный список блоков памяти, так и для получения порядкового номера блока. Каждый элемент в списке блоков состоит из порядкового номера блока и указателя на строку. Элементы заданного списка блоков у порядочены в соответствии с номерами блоков.
Для того чтобы определить, хранится ли строка Х в блоке, определяемом ее хзш-адресом, в связанном списке блоков ищется блок, порядковый номер которого совпадает или больше порядкового номера блока, содержащего Х. В последнем случае Х немедленно вставляется в список, а при совпадении порядковых номеров блоков осуществляется посимвольное сравнение Х со всеми другими строками в списке, имеющими тот же порядковый номер блока.
Запрограммируйте эту схему двойного хэширования, предполагая, что строки хранятся в последовательных блоках с дескриптором длины. Запрограммированная функция должна в качестве входного параметра получать указатель строки; отыскивать эту строку в таблице; вносить ее, если строка не обнаружена, и возвращать адрес найденного вхождения или адрес сформированного вхождения в таблицу. 14. Ввод файлов и проверка конца файла обычно осуществляются до того, как в программе потребуются данные из этого файла или результат проверки, поскольку ввод осуществляется через буфер в блоках, как показано парис. 5.6.
Для интерактивного ввода-вывода более подходящим является альтернативный способ ввода, так называемый отложенный анод. Ввод данных и проверка конца файла происходят, только когда поступает соответствующее требование из выполняемой программы. Разработайте операцию ч ген и г и предложите способ проверки достижения конца файла в случае отложенного ввода пз интерактивного файла. Пользователь должен иметь возможность вводить несколько значений за один раз, поэтому при реализации может потребоваться буфер. Глава 6. Инкапсуляция При написании больших программ программист почти неизбежно сталкивается с необходимостъю разработки и реализации новых типов данных. Например, при написании программы, которая регистрирует зачисленных в университет студентов и создает списки групп, один из первых этапов может заключаться в том, чтобы определить тип объекта данных, который соответствовал бы одной гр1упие какого-либо нурса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
