Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 110
Текст из файла (страница 110)
Обьясннте, как обнаруживается ссылка на нелокальную переменную при исполь- зовании индикаторов. Как представляются ссылки на переменные при использовании метода статических цепочек и метода индикаторов? Какие изменения нужно внести в индикатор при вызове подпрограммы (при усло- вии, что параметры по имени не передаются и не могут быть подпрограммами)? Сравните эффективность методов статических цепочек и индикаторов для доступа к локальным переменным, доступа к нелокальным переменным. при возвратах нз подпрограмм и в целом.
Опишите два метала реализации блоков. Опишите метод глубокого доступа при реализации динамического обзора. Опишите метод теневого доступа при реализации динамического обзора. Назовите два основных различия между методом глубокого доступа к нелокаль- ным переменным в языках с динамическим обзором данных и методом статиче- ских цепочек в языках со статическим обзором данных. Сравните эффективность методов глубокого и теневого доступа с точки зрения выполнения вызовов и обеспечения доступа к нелокальным переменным.
Опишите метод реализации параметров, являющихся подпрограммами, с помощью подхода, основанного на реализации метода статических цепочек. Опишите метод реализации параметров, являющихся подпрограммами, с помощью подхода, основанного на реализации метода индикаторов. Всегда ли ближайший экземпляр предка, находящийся в данный момент в стеке, является правильным экземпляром активационной записи статического предка в языках, допускающих передачу подпрограмм в качестве параметров? Напишите алгоритм реализации индикатора, требуемого при входе в подпрограм- му, на языке, использующем статический обзор данных и всегда позволяющем пе- редавать подпрограммы в качестве параметров.
Напишите алгоритм реализации индикатора, требуемого при выходе из подпро- граммы, на языке, использующем статический обзор данных и всегда позволяю- щем передавать подпрограммы в качестве параметров. 3. Покажите состояние стека со всеми экземплярами активационных записей. включая статические н динамические связи, когда выполнение следуюшей скелетной программы достигает точки ! (при условии, что уровень подпрограммы В1ГЯ )В равен 1). ргосес(игв В16Я()В1 ргосес(иге А; ргосесиге В; Ьедзл ( В ) <- 1 еЬ (В! ргосвсигв С; Ьедхп ( С впс(1 ( С Ьвдап ( А епйг ( А Ьедхп ( В1СЯОВ епеЬ ( В1ЯЯ1В ) 4.
Для скелетной программы в задаче 3 покажите индикатор, который является активным в точке ! вместе с экземплярами активационных записей в стеке. 5. Покажите стек со всеми экземплярами актнвационных записей. включая статические и лпнамические цепочки, в момент, когда выполнение следующей скелетной программы достигает точки ! (прн условии, что уровень подпрограммы В16ЯВВ равен !). ргосеиигв В1680В1 ргосес(иге С; Еогнагс(г ргосес(иге А(11ад: Ьоо1еап)1 ргосес(иге В; А(1а1ве) епс1; ( В Ьвдзл ( А Н 11ад сцеп В в1вв С епс11 ( А ) ргосег1иге Сг ргосесЗигв Вп Упражнения 427 епс1; ( Э ) епс11 ( С ) й ', сгце); епс) ' ( В -Б,г( Последовательность вызовов.
которые следует выполнить в этой подпрограмме, лля з ого чзобы дос ~ ичь оператора В. закова: В ВВУВ вызывает В В вызывает В В вызывает Д В вызывает С С вызывает В Для скелетной программы из упражнения 5 покажите состояние индикатора, кото- рый является активным в точке 1 вместе с экземплярами активационных записей в сзеке. Несмотря на то что локальные псрелшнные в процедурах на языке Разса) динами- чески размегцаются в памяти в начале каждой нх активации. укажите, при каких условиях значение локальной переменной в конкретной акзивации сохраняет зна- чение, оставшееся ог прежней акзивацип.
1О. 11. 12. Глава 9. Реализация подпрограмм 428 В данной главе угверждается, что при доступе к недокальной переменной с помощью динамической цепочки в языке с динамическим обзором данных имена переменных должны размещаться в активационных записях вместе с их значениями. Если эго дсйш вительно так, то ка клок обращение к нслокальной переменной может потребовать выполнения последовазелыюсгн довольно затратных сравнений строк, представляющих собой имена переменных.
Разработайте альтернативу этому сравнению. которая работала бы быстрее. В языке Рааса! допускается использование операторов доьо с нелоканьными целями. Как можно обработать такой оператор. если для нелокального доступа исполюуются статические цепочки? Подслнзки: рассмотрите способ. с помощью которого обнаруживается правильный экземпляр актнвацнонной записи статического предка вновь создаваемой процедуры (см раз зсл 9.3.4.1). Повторите уира;кненпе 9, используя индикаторы вместо статических цепочек. Как ьюжно молнфнцировать механизм индикаторов, описанный в данной главе.
для з ого чтобы обеспечить доступ к локальным переменным без косвенной адресации? Метод статических цепочек можно слегка расширить с помощью двух статических связей в кажлом экземпляре активационных записей, в которых вторая связь указывала бы на полпрограмму. являющуюся статическим предком по отношению к статическому предку экземпляра записи активации. Как это повлияет на время установления связи между подпрограммами и скорость дос гула к нелокальным ссылкам".
10.1. Понятие абстракции 10.2. Инкапсуляция 10.3. Введение в абстракцию данных 10.4. Вопросы разработки типов 10.$. Примеры абстракции данных в разных языках 10.0. Параметризованные абстрактные типы данных Оле-Йохан Дал (01е-допел 0вЫ) : ге-Йохан Дал и Кристен Нвйгазсд (КпзГеп Нуаазгб), рвботав- ге в Норвежском вычислитель-зм центре, в основном заминались компьютерным моделировз-гем Руководствуясь своими за-=осами, они разработали и рев-изовали языки моделирования 6~М~~.Д в З964 году и 6~МЦГА бт з 1967 году 429 Абстрактные типы донных этой главе исследуется поддержка абстракции данных в языках программирова- В, ния, начиная с ее истоков в языке 61М1Л.А 67 и заканчивая ее формами в современных языках.
Среди новых илей, возникших в области методологии программирования и разработки языков программирования за последние 25 лет, абстракция данных является одной из самых значительных. Вначале рассмотрим общее понятие абстракции в программировании и языках программирования. Затем обсудим инкапсуляцию в языках программирования. Далее дается определение абстракции данных, подкрепленное конкретным примером. После этого приводится краткое описание частичной полдержки абстракции данных в языке 81М01.А 67. Полная поддержка языками программирования абстракции данных обсуждается в терминах двух конкретных языков: Ада и С++. Показана реализация одного и того же примера абстракции данных в каждом из этих языков.
Это позволяет выделить как общие черты, так и различия в разработке языковых средств поддержки абстракции данных. В качестве альтернативы языку Ада кратко описана поддержка абстракции данных в языке программирования Моди!а-2, а поддержка абстракции данных в языке )ата рассматривается как альтернатива языку С++. В заключение показаны возможности создания параметризованных абстрактных типов в языках Ада и С++.
Заметим, что в этой книге фразы "абстракция данных" и "абстрактные типы данных" означают одно и то же. 10.1. Понятие абстракции Абстракция — зто суждение нли представление о некотором объекте, которое содержит только свойства, являющиеся существенными в данном контексте. Абстракция позволяет объединять экземпляры объектов в группы, внутри которых общие свойства объектов можно не рассматривать, т.е. абстрагироваться от них.
Тогда внутри группы нужно изучать лишь те свойства, которые отличают ее отдельные элементы друг от друга. Зто значительно упрощает элементы группы. При необходимости летального изучения объектов нужно рассматривать их менее абстрактные представления. Абстракция— это эффективное средство против сложности программирования, поскольку оно позволяет программисту сосредоточиться на существенных свойствах объектов и проигнорировать менее важные свойства.
В современных языках программирования есть два основных вида абстракции: абстракция процесса н абстракция данных. Понятие абстракции процесса — одно из наиболее старых понятий в области разработки языков программирования. Даже язык Р!апЫк01 поддерживал абстракцию процесса. Все подпрограммы являются абстракциями процессов, поскольку они определяют способ, с помощью которого программа устанавливает, что необходимо выполнить некоторый процесс, без уточнения деталей того, как именно это следует сделать (по крайней мере, в вызывающей программе). Например, если а программе нужно упорядочить массив числовых данных некоторого типа, обычно используется подпрограмма, выполняющая сортировку. В той точке программы, в которой следует выполнить сортировку, помещается оператор следующего вида: вогс 1пс(11ас,11вс 1еп) 430 Глава 10. Абстрактные типы данных Этот вызов является абстракцией реального процесса сортировки, алгоритм которого -".
определен. Вызов не зависит от алгоритма, который реализуется в вызываемой под-то~рамме. Единственными существенными свойствами подпрограммы аогс 1пс являются имя - рядочиваемого массива, тип его элементов и тот факт. что вызов подпрограммы зпс приводит к сортировке массива. Какой именно алгоритм выполняет г - "= зпс, для пользователя не существенно. Абстракция процесса — ключевое понятие в программировании. Возможность абст-згироваться от многочисленных деталей алгоритма, который выполняется подпрограм° .
и. позволяет создавать, читать и понимать большие программы. Напомним, что больй в настоящее время считается программа, содержащая, по крайней мере, несколько -ь сяч строк кода. Все подпрограммы, включая параллельные подпрограммы (рассматриваемые в глазе 1Э) и обработку исключительных ситуаций (описанную в главе 13), являются абстракаями процессов. Эволюция абстракции данных сопровождается эволюцией абстракции процесса. по- :кольку неотьемлемой и главной частью любой абстракции данных являются операции, - вторые определяются как абстракции процессов. 10.2. Инкаасуляция Инкапсуляция предшествует абстрактным типам данных и поддерживает их. Когда размер программы достигает нескольких тысяч строк, возникают две практнчеьне проблемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
