Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 50

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 50)

Задачи и упражнения 179 11. Используя определения для логических пес, апо' ног через).-выражения, покажите, что: апщХ.У) - алв(У,Х) и аиа(асп(Х,У),7) = аМ(Х,асЬ5(У,7)) 17, Рассмотрим аксиомы для стеков нз раздела 4.2,5, Если интерпретировать их 18. Покажите эквивалентность следующих объектов: 12. 13. 14. 15.

16. + ((пот А) В) = истина тогда нтолько тогда, когдаА = истина и В = истина; + ((огЯ) В) - истина тогда и только тогда, когдаА = истина или В = истина. То есть нужно показать, что опрелеления функций ап(( и ог через А-выражения соответствуют обычной интерпретации этих логических операций. Используя определения целых чисел через А.-выражения, покажите, что 2 ч- 3 = 5. В тексте главы в том примере, где стеки иллюстрируют алгебраические типы данных, предполагается, что стеки неограниченны. Конструктор рь Ф можно применять к любому стеку. Но реально длина любого стека конечна. Перепишите аксиомы для стеков для случая, когда существует некий максимальный размер стека Мах5гасХ.

Создайте аксиомы для других типов данных, например для очередей и множеств. Какие нужны операции для определения этих типов? Реализуйте стеки, очереди или множества в языке Сч-н и покажите, что в вашей реализации выполнены все соответствующие аксиомы. Рассмотрим следующие аксиомы сложения (зцсс означает зпссеззог, то есть функцию, добавляющую единицу к предыдущему значению): аМО.Х) - Х аса(аисс(Х),У) = ансс(аащХ,У)) Используя только эти две аксиомы, докажите при помощи индукции типов данных, что как правила языка Рго1о)5 то многие алгебраические свойства можно реализовать как программы на этом языке. Разработайте набор правил языка Рго1оя, преобразующих последовательность операций рнзп и рор в более простую последовательность, состоящую только из операций роФ (то есть речь идет о том, чтобы привести эту последовательность к нормальной форме). Например, рор(рнФ(5.

! ) ) приводится к 5, а риФ(рор(риФ(рор(рцФ(5, ! ) ), Л ) . К) преобразуется в ризи(5, К). + конечного автомата и регулярных языков; + автомата с магазинной памятью и контекстно-свободных языков; + линейно-ограниченного автомата и контекстно-зависимых языков. Линейно-ограниченный автомат — это машина Тьюринга, в которой лента содержит только входные данные (следовательно, ее длина возрастает соответственно количеству вводимых данных, хоть и не может быть неограниченной); + машины Тьюринга и языков с фразовой структурой. 1ВО Глава 4.

Моделирование свойств языка 19. Покажите зквивалентность илн ее отсутствие между детерминированной и недетерминированной моделями: + для конечного автомата; + для автомата с магазинной памятью; + для линейно-ограниченного автомата; + для машины Тьюринга. Первая и последняя задачи сравнительно простые, вторая несколько труднее.

Тем же, кто решит третьк> задачу, обеспечено немедленное получение докторской степени и широкая известность в академических кругах. Эта не решенная до сих пор задача связана с задачей НП-полноты (см. раздел 4.1.3). Глава 5. Элементарные типы данных Любая программа, в сушности, представляет собой набор операций, которые применяются к определенным данным в определенной последовательности. Основные различия между язьпгами программирования сводятся к тому, каковы допустимыее типы данных и операций и какие механизмы используются для управления последовательностью применения операций к данным.

Эти три области — данные, операции и механизмы управления — составляют основу для сравнения языков программирования, которые обсуждаются в нашей книге. В этой главе мы рассмотрим данные, типы и операции, которые обычно встроены непосредственно в язык; в главе 6 обсуждается понятие абстракции — так называется расширение встроенных типов данных за счет добавления новых типов, определяемых самим программистом.

5.1. Свойства типов и объектов Сначала мга исследуем свойства, которые определяют объекты данных в языках программирования. Затем мы обсудим стандартные для большинства языков типы данных с точки зрения способов их реализации в аппаратной части компьютера (то есть элементарные типы данных).

В главе 6 мы рассмотрим такие типы данных, которые обычно моделируются при помоши программного обеспечения (то есть структурные типы данных). 5.1.1. Объекты данных, переменные и константы Области хранения данных в аппаратной части компьютера (память, регистры и внешние запоминаюшие устройства) обычно имеют довольно простую структуру в виде последовательности битов, сгруппированных в байты или слова. Однако хранение данных в виртуальном компьютере, как правило, организовано более сложным образом — в различные моменты выполнения программы используются такие формы хранения данных, как стеки, массивы, числа, символьные строки и некоторые другие.

Один или несколько однотипных элементов данных, объединенных в одно целое в виртуальном компьютере в некоторый момент выполнения программы, принято называть обьектом данных В течение времени выполнения программы существует множество обьектов данных различных типов. Более того, в отличие от сравнительно неизменной статической организации храпения данных в аппа- 182 Глава 5. Элементарные типы данных ратной части компьютера объекты данных и отношения между ними динамически меняются в процессе выполнения программы.

А; 1ООО1 Значения: комбинация битов, используемая для представления числа 17, когда оно встречается в программе Объект данных: область памяти с именем А Связанная переменная: объект данных, связанный со значением 17 Рис. 5.1. Пример объекта данных — простая переменная со значением 17 Некоторые объекты данных определяются ирограммиспгом (например, переменные, константы, массивы, файлы и т, д.); программист создает эти объекты и управляет ими явным образом при помощи объявлений и операторов в программе, Другие об ьекты данных определяются системой (то есть автоматически создаются по мере необходимости виртуальным компькттером во время работы программы как вспомогательные, предназначенные для выполнения служебных функций). К таким объектам данных (например, к стекам, записям активации подпрограмм, файловым буферам и спискам свободной памяти) у программиста нет непосредственного доступа.

Объект данных представляет собо й контейнер для хранения зничений данных— то есть то место, где эти значения хранятся и откуда они затем извлекаются. Объект данных характеризуется набором плгрибуглов, самым важным из которых является тил данных. Атрибуты определяют количество и тип значений, которые могут содержаться в объекте данных, а также определяют логическую организацию этих значений. Значение данных может представлять собой отдельное число, символ или указатель на другой объект данных.

Значение обычно представлено конкретной комбинацией битов в памяти компьютера. До сих пор мы предполагали, что два значения совпадают, если представляющие их в памяти компьютера комбинации битов идентичны. Но для более сложных типов данныхтакого простого определения недостаточно. Различие между объектами и значениями данных во многих языках недостаточно отчетливо и их довольно легко перепутать. Пожалуй, наиболее ярко это различие проявляется в реализации: объект данных представлен некоторой областью в памяти компьютера, а значение данных представлено комбинацией битов. Если мы говорим, что объект данных А содержит значение В, то имеется в виду следующее: в области памяти компьютера, представляющей обьект А, расположена определенная комбинация битов, соответствующая значению В (рис.

5.1). Если мы пронаблюдаем за работой программы, мы заметим, что одни объекты данных существуют с самого начала выполнения программы, а другие создаются динамически в процессе ее выполнения. Одни объекты данных в какой-то момент уничтожаются, а другие сохраняются до конца работы программы. Таким образом, у каждого объекта данных имеется определенное время жизни, в тече- 5.1.

Свойства типов и объектов 183 ние которого он может быть использован для хранения значений данных. Объект данных нааывается элементарным, если содержащееся в нем значение всегда фигурирует в программе как единое целое. Если же этот объект представляет собой совокупность некоторых других объектов, то он называется структурой данных. Любой объект данных за время своей жизни участвует в нескольких связываниях. Хотя атрибуты объекта данных инвариантны в течение его времени жизни, связывания могут динамически изменяться.

Ниже перечислены наиболее важные атрибуты и связывания. 1. Тип. Этот атрибут ассоциирует обьект данных со множеством значений, которые могут содержаться в этом объекте данных. 2. Местоположение. Связывание объекта данных с определенным местоположением (областью памяти) обычно задается и контролируется специальными вспомогательными программами управления памятью, которые предусмотрены в виртуальном компьютере н недоступны непосредственно для программиста. 3.

Значение. Это связывание обычно является результатом операции присваивания. 4. Имя, Связывание объекта данных с одним нли несколькими именами, по которым к нему происходят обращения во время работы программы, обычно осуществляется при помощи объявлений и может модифицироваться при входе и выходе из подпрограмм (подробнее см.

Характеристики

Список файлов книги