Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 72
Текст из файла (страница 72)
Алгоритм маркировки для сборки мусора и процесс подсчета ссылок могут реализовываться значительно эффективнее при использовании циклического сдвига указателей и операций скольжения, описанных Сузуки (Бцлц(с(, 1982). 26а Глава б. Типы данных заедки переменного рахчерж Управление динамической памятью с ячейками переменноазчера сопряжено с теми же трудностями. что и управление динамической памятью с ° =эками постоянного размера, и кроме этого возникают дополнительные проблемы. но, к +хтению, ячейки переменного размера требуются в большинстве языков программиро: -ия. Дополнительные проблемы. характерные лля ячеек переменного размера, зависят от .-ода. используемого для управления динамической памятью.
При использовании метода рки мусора эти проблемы можно сформулировать следующим образом. ° Трудно установить индикаторы ячеек в положение. указывающее, что они содержат мусор. Поскольку ячейки имеют переменный размер, их просмотр становится проблемой. Одно из решений этой проблемы заключается в требовании наличия в каждой ячейке переменного размера первого поля, в котором указан ее размер. После этого может выполняться просмотр ячеек, правда. он занимает немного больше памяти и времени. чем его эквивалент для ячеек постоянных размеров.
° Процесс маркировки ячеек нетривиален. Как можно пройтн цепочку, начавшуюся с указателя, если заранее не определено положение указателя в целевой ячейке". Другой проблемой являются ячейки, не содержащие указателей. Конечно. можно ввести системный указатель для каждой ячейки, но такие указатели лолжны поддерживаться параллельно с пользовательскими указателями. Такой подхол снижает эффективность с точки зрения памяти и времени, затрачиваемых на выполнение программы. ° Поддерживается список доступной памяти. Вначале этот список может состоять из олной ячейки.
солержашей всю доступную память. Запросы на сегменты памяти просто уменьшают размер этого блока. Освобожденные ячейки добавляются в список. Проблема же заключается в том. что через некоторое время список превращается в перечень блоков, или сегментов. переменной длины. Это замелляет процесс размещения переменных в памяти, поскольку в ответ на запрос должен выполняться поиск блока достаточного размера. По прошествии некоторого времени список может состоять из большого числа очень маленьких блоков, недостаточных для уловлетворения большинства запросов. В этот момент может потребоваться объединение смежных блоков в блоки больших размеров.
Возможна альтернатива; использование первого достаточно большого блока в списке, что сократит поиск, но потребует упорядочения списка по размерам блока. В любом случае нужны дополнительные расходы на поддержание списка. Если в качестве метода управления динамической памятью используются счетчики ссылок, то из трех перечисленных проблем остается только последняя. Стиль и использование языка программирования во многом определяется его типами данных, которые вместе с управляющими структурами формируют ядро языка. В число элементарных типов данных л~ногих языков входят числовые.
символьные и булевские типы. Числовые типы данных довольно часто поддерживаются непосрелственно аппаратным обеспечением. Определяемые пользователем перечислимые и ограниченные типы удобны. а их использование повышает читабельность и надежность программ. 269 Резюме Другой частью большинства языков программирования являются массивы. Связь между ссылкой иа элемент массива и адресом этого элемента в памяти предоставляется функцией доступа.
которая прелставляет собой реализацию отображения. Массивы могут быть статическими (как в языке ГОКТйА)Ч 77); фиксированными автоматическими (как в процедурах языка Рааса(); автоматическими (как в блоках языка Аг(а) или динамическими (как в массивах Аг 7.0САТАВ(.Е языка ГОКТКА)Ч 90). В большинстве языков су шествует только ограниченное число операций с массивами, как с единым целым. В большинство современных языков вошел такой тип данных, как записи. Поля записей задаются разнообразными способами. В языках СОВОГО и Р1Л, например, ссьшаться на них можно.
не указывая всех внешних блоков, хотя реализация этой возможности беспорядочна, а читабельность программ при этом ухудшается. В таких объектно-ориентированных языках программирования, как )ача, записи поддерживаются конструкцией класса. Объединения — это ячейки памяти, которые могут содержать различные типы значений в различные периоды выполнения программы.
Размеченные объединения содержат метку для записи значения текушего типа. Свободным объелинением называется объединение без метки. Большинство объединений современных языков имеют небезопасную структуру, исключением является только язык Ада. Часто бывает улобно и относительно просто реализовать множества данных.
Впрочем. задачи, лля выполнения которых обычно используются множества, мокнут практически с той же легкостью решаться и с помощью других типов. Целью использования указателей является достижение гибкой адресации и управление динамической памятью. Однако при использовании указателей возникает проблема висячих указателей, которую трулно обойти, и проблема мусора, который трудно собрать. Управление динамической памятью без опасностей, характерных лля указателей, обеспечивают ссылки, подобные сушествуюшим в языке )ача.
На то, какие типы будут включены в язык, значительное влияние оказывает уровень сложности реализации различных типов данных. Перечислимые типы, ограниченные типы и записи реализовать довольно просто. Реализация массивов также не вызывает затруднений, хотя для массивов.
имеюших несколько инлексов, доступ к элементу может оказаться неэффективным. Это объясняется тем, что функция доступа к элементу массива требует на каждый индекс по одной операции сложения и умножения. Другим неэффективным процессом является реализация указателей, если они предназначены для управления динамической памятью и если принимаются какие-нибудь меры для решения проблемы висячих указателей. Если ячейки памяти имеют одинаковый размер, то управление динамической памятью выполняется относительно легко, но тот же процесс значительно усложняется при использовании ячеек переменного размера. 3 ° ° Сушествует множество литературы по компьютерным наукам, в которой освешаются вопросы структуры типов данных, их использования и реализации. Одно из первых семантических описаний структурных типов дает Хоар в книге (Оап! е! а(., 1972).
Сравнение типов структур языков АЬООЬ68 и Рааса( проволится Тененбаумом (ТепепЬашп, 1978). сравнение языков С и Рааса!, в том числе и структур типов, проводится Фоером и Гехани (Гецег апд Оейап), 1982). Обсуждение ненадежных моментов в структуре типов данных языка Рааса( рассмотрено в книге (Фе!зп е! а(., 1977). Обший обзор разнообразных типов данных дается в книге (С(еаче(апд, 1986).
2УО Глава 5. Типы данных -гром и Ле Бланком (Р1зйег апд ЬеВ)апс, 1980) рассмотрена проверка времени выполнения возможных ненадежных моментов в типах данных языка Рааса). В большинстве книг по разработке компиляторов, например (Г1ьйег апд 1еВ!апс, 1988) и (Айо ег а1.), а также прочих книгах по языкам программирования — (Ргап, 1984) и (ОЬехх! апд 1агауег1, 1987) — описываются методы реализации типов данных. Подробное обсужлечне проблемы управления динамической памятью можно найти в книге (ТепепЬаит ег з1.. !990). Методы сборки мусора разработаны Шорром и Уайтом (Бсйогг апд %айе, 1967), а также Дойчем и Бобровым (Оешзсй апд ВоЬгот, ! 976). Всестороннее обсчжленпе алгоритмов сборки мусора можно найти в работе (Сойеп,! 981).
° ° Что такое "дескриптор"? Назовите достоинства и недостатки десятичных типов ланных. Назовите вопросы разработки, характерные для символьной строки. Сформулируйте три варианта выбора длины строки. Дайте определения порядковых типов, перечислииых типов и ограниченных типов.
В чем заключаются достоинства перечислимых типов. опрелеляемых полиювателем? Назовите вопросы разработки, характерные лля массивов. Дайте определения фиксированных авточатическик, автонатических и динамических массивов. В чем достоинства каждого из них? 9. Какое свойство инициализации массива доступно в языке Ада и не доступно в лругих распространенных императивных языках программирования". 1О. Что такое константное.иножество? 11. Какие операции с массивами заданы только д)!я одномерных массивов языка Ада? 12.
В чем различие между сечениями языков ГОКТЙАХ 90 и Ада? 13. Дайте определения записи по строкам и записи па столбцам. 14. Что такое функция доступа к.массиву? 15. Какие позиции требуются в дескрипторах массивов языка Рааса! и когда они должны записываться в память (во время компиляции или во время выполнения)". 16. Для чего в записях языка СОВОК нужны номера уровней? 17. Дайте опрелеление полностью определенной и эллиптической ссытки на поле записи.
18. Дайте определение объединения, свободного объединения иразнеченного обьединения. 19. Назовите вопросы разработки, характерные для обьединений. 20. В чем заключаются две проблемы использования объединений языка Рааса!? 21. Чем объединения языка Ада безопаснее обьединений языка Рааса!? 2У1 Вопросы Почему в реализациях языка Рааса! значительно ограничивается размер множеств? Назовите вопросы разработки, характерные для указателей. Назовите две обшие проблемы, связанные с использованием указателей. Назовите две причины большей надежности указателей Ада по сравнению с указа- телями языка Рааса! 22. 23. 24. 25.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
