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

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

В более сложных языках (например, С++, в котором появляется понятие конструктора и деструктора) вопрос об управлении временными данными более касается программиста.

Пример временных данных в С++:

T f (T x1, T x2) - здесь нужны временные данные;

void f (T x), где Т - некий класс;

T(int) - конструктор преобразования (отводит временный объект типа Т по объекту типа int). Он может быть описан явно (explicit) либо неявно (implicit).

Пусть f(5); тогда f(T(5)) - создается временный объект типа Т (программист им не управляет).

Семантикой (созданием и разрушением) временных объектов управляет только компилятор. В данном примере работают 2 конструктора - преобразования и копирования.

В оптимальных компиляторах работает 1 конструктор - преобразования, но это вопрос оптимизации. В стандарте языка С++ сказано, что программа не должна зависеть от того, сколько конструкторов вызвано. Конструктор не должен давать побочный эффект (например, i++ - увеличение на 1 глобальной переменной).

Встает вопрос, когда будут вызываться деструкторы ( в компиляторе Microsoft Visual C++ - когда объекты становятся не нужны, в компиляторах фирмы Borland - при выходе из всего блока).

Пункт 1.

Запись активации (ЗА).

Процедура – некоторая абстрактная операция, которая определяет некоторое действие. В ходе этого действия нужны данные: локальные и временные.

Есть понятия: определение процедуры и ее активация (вызов - call).

Подпрограммы вызываются с помощью call; активация (activation) - более общий термин.

Есть два вида программ - подпрограммы и сопрограммы.

Пусть есть объект данных - i; определение объекта: int i;

активация объекта: i=l; x=i;

В определение процедуры входит ее код.

Общий код процедуры состоит из пролога, операторов процедуры и эпилога. Пролог и эпилог мы не программируем - это добавляет компилятор.

Запись активации – особое место (область памяти), где хранятся локальные и временные данные, вспомогательная информация о контексте (например, адрес возврата), необходимая для организации вызова и возврата. Конкретный вид записи активации зависит от самого языка.

Пример

int f(int a, double b)

{

int i;

...

}

Пример записи активации этой процедуры на языке Си:

Заметим, что при активации подпрограммы всегда создается запись активации.

Пролог для языка Си - это инициализация записи активации.

Например, ЯП с блочной структурой были сконструированы так:

блок:{[описание переменных;] операторы} (Алгол, С, Паскаль).

Описание переменных шло до операторов для упрощения процесса компиляции и понимания.

В эпилог для языка Си входят действия по уничтожению записи активации и передача возвращаемого значения.

В пролог С++ входит вызов конструкторов, в эпилог - всегда вызов деструкторов.

Всегда ли конструкторы локальных объектов можно вызвать в прологе? Это зависит от того, где встретился локальный объект. Именно потому, что в языке С++ описания переменных и операторы можно смешивать, мы не можем гарантировать, что каждый локальный объект будет инициализирован.

Почему в С++ редко (по сравнению с Си) используется goto?

Пример:

T a;

……….

{if(B){ goto end;}

T b;

end: …

}

Компилятор С++ выдаст предупреждение, что вызов деструктора объекта b будет проигнорирован. Здесь поведение компилятора не определено.

Т.о., определение процедуры включает запись активации. Одному определению соответствует несколько записей активации.

-- ЗА1 - запись активации 1

определение --- -- ЗА2 - запись активации 2 последовательные вызовы.

-- ЗА3 - запись активации 3

…………..

Пункт 2

Управление последовательностью подпрограмм.

Самый простой способ управления последовательностью подпрограмм - управление посредством копирования (вставка кода, макрорасширение)

Здесь активация - вставка кода (только для простых языков).

Это inline процедуры в С++ (процедуры, которые управляются копированием).

Что необходимо для того, чтобы была возможна вставка кода?

• отсутствие рекурсии (в первых языках рекурсии не было, но для многих алгоритмов рекурсия служит наиболее естественным способом записи);

• немедленный вызов (т.е. как только встретилось требование об активации, эта активация выполняется немедленно).

Это механизм макрорасширения.

Чем отличается inline от define?

Inline – это структура компилятора, а define – препроцессора.

Inline - это функция - более защищенная конструкция; define - это не функция, нет средств контроля. Т.о., inline – более защищенная абстракция, чем define

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

Еще для возможности вставки кода должна быть явно определенная точка активации - это значит, что можно в тексте программы указать, где активируется процедура.

Примеры:

f(a,b);//требует немедленной активации и описана явно.

Для обработчиков прерываний точка активации явно не определена.

Catch (T е) {...} - обработчик исключений - ведет себя как процедура (без имени, но с одним параметром). Явной точки вызова для обработчика исключений не существует.

Эти три условия должны быть для вставки кода.

Где и когда размещать записи активации?

Структура записи активации не меняется от одной активации к другой. Утверждается, что в каждый момент времени для каждой процедуры активна всего одна запись активации.

Запись активации можно добавлять в конец кода, и она будет частью самого кода.

Например, в языке Фортран запись активации была частью самого кода. Код всегда был статически настроен на соответствующую запись активации.

Рассмотрим, как управление записью активации реализовано в традиционных языках.

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

4 требование - статическое связывание (по записи активации вызова мы знаем, какая процедура должна быть активирована). В общем случае это не так. Например, виртуальные методы в С++ и Java.

f.p(); - вызов функции в языке Java

Пусть f - метод класса F.

A p -> B p -> F p - цепочка наследования. Если в каждом экземпляре есть функция p(), мы не знаем какая, функция будет вызвана.

В классе Object реализуется функция clone(), которая дает побитовую копию объекта.

Object -> A clone -> B clone -> F

Если функция переопределена, то мы не знаем, из какого класса будет вызвана функция clone(). Это и есть динамическое связывание - в этом случае вставка кода не пройдет (если компилятор не знает, какой экземпляр функции вызван, он не знает, какой код вставить; поэтому тут нужно статическое связывание).

5 требование - схема возврата (вызов возврата: call- return)

A -> P – вызывается процедура А, и она вызывает процедуру Р. Прежде, чем произойдет return из А, должен произойти return из Р.

Return – это уничтожение записи активации.

ЗА для А существует дольше, чем ЗА для Р. Сначала уничтожается ЗА Р, а затем ЗА А.

В общем случае, записи активации ведут себя как стек.

Как реализуются ЗА?

В современных архитектурах стек реализован аппаратно, т.е. есть машинные команды, которые явно манипулируют со стеком (в INTEL есть регистр SP, который отвечает за стек),

Это команды:

PUSH

POP

SP - указатель на вершину стека.

CALL

RET (urn)

В архитектуре IBM 360 – понятия машинного стека не было. В этом случае чаще всего ЗА реализовывались как линейный список, т.е. там стек реализовался программно.

Сейчас стек является частью реализации любой архитектуры.

Например, классическая реализация языка Си содержит:

Как правило, такой реализации достаточно для реализации рекурсивных процедур.

В стеке хранится информация о записи активации.

Важна также внутренняя архитектура процессора (набор микрокоманд)- есть ли кэш.

Кэш обрушивают длинные команды перехода (jump) и любые команды call.

Короткие команды перехода не обрушивают кэш.

Получается, что накладные расходы на call - return могут быть достаточно большие.

Например, есть класс

class X {

private:

int i;

…

}

Мы хотим предоставить доступ на чтение для i, а на запись не хотим.

В языке Оберон Н. Вирт ввел понятие экспорта только на чтение i*- .

Вместо этого Страуструп предложил:

int getI() {return i;}

X=p.getI(); // inline-реализация.

X=p.i;

p.i=X; // это недопустимо

Необходимость встраиваемых участков кода связана с изъятием накладных расходов на call-return.

Современное состояние машинных архитектур таково, что управление записью активации с помощью стека не приводит к накладным расходам.

Откажемся от структуры call - return (она содержит не симметрию).

call - механизм активации;

return - механизм возврата (механизм подпрограмм).

Механизм подпрограмм (subroutines) - несимметричный механизм (пример не симметрии):

Здесь вызывающая Р1 знает, что вызывает Р2, но не знает куда вернется Р2. Возникает не симметрия механизма call – return : call всегда начинает с первой точки, а return возвращает в точку активации.

Механизм сопрограмм (co routines) - не имеет не симметрии. Пример:

Здесь записи активации могут образовывать линейный список (в случае рекурсий). Для рекурсивных вызовов с каждой записью активации должен храниться свой стек.

Механизм сопрограмм очень похож на механизм параллельных процессов, т.е. Р1 и Р2 работают как бы параллельно. Не случайно, что механизм сопрограмм реализовывался вначале именно как механизм реализации квазипараллельных процессов.

Интересно, что в Modula2 был низкоуровневый механизм реализации сопрограмм.

Там была специальная процедура

INIT PROCESS (P, COR, N) ,

где Р - адрес процедуры,

COR - ADDRESS (в Си и С++ аналог void *) - адрес области памяти, которая хранит текущую информацию о ЗА,

N - размер рабочей области процесса (или сопрограммы).

Запись активации должна быть активной все время, которое работает сопрограмма.

N – это размер области, которая отводится под запись активации.

Поэтому “N примерно = 100 обычно хватает” - это фактически размер стека для функционирования Р.

ЗА - это

• содержимое регистров процессов

• адрес возврата

• информация обо всех локальных данных

• ...

INITPROCESS:

1. отводит запись активации

2. инициализирует ее

3. передает управление на первый оператор Р.

TRANSFER (P1, P2) - это специальный немедленный вызов, где Р1 и Р2 - это адреса входа процессов Р1 и Р2.

В Р1 записывается контекст текущего процесса;

Р2 - контекст процесса сопрограммы, на который мы передаем управление подпрограмм.

IOTRANSFER (P1, P2, Vector) - это еще один механизм отложенного вызова подпрограмм, где Vector - вектор прерываний. Поэтому IOTRANSFER работает как же, как TRANSFER (P1,P2), но только в тот момент, когда приходит прерывание. И подпрограммы и сопрограммы являются структурными абстракциями (они имеют один вход и один выход - это требование структурного программирования).

ENTRY - альтернативный вход (в одну и ту же подпрограмму можно входить из разных точек – это противоречит принципам структурного программирования -> в современных ЯП от многих точек входа отказались).

Возврат из подпрограммы (в современных ЯП) всегда происходит в одну и ту же точку.

Фортран не удовлетворяет этому требованию. В нем можно описать подпрограмму

SUBROUTINE P (..., *,...,*,...),

которая содержит среди формальных параметров *.

RETURN 3 - это эквивалентно GOTO метка, которая соответствует третьей * в списке фактических параметров. Следовательно, у процедуры в Фортране могло быть несколько выходов, что противоречит требованиям структурного программирования.

В современных ЯП механизма сопрограмм нет. Понятие сопрограмм в современных ЯП заменило понятие потока - THREAD - это обобщение понятия сопрограмм. Сопрограммы пригодились для параллельного программирования, но они не прижились в ЯП.

Лекция 13.

Пункт 3.

Среды ссылок (СС).

Один из самых важных атрибутов объектов данных - это имя.

Каким образом по имени идентифицировать ОД?

Для каждого объекта данных есть одно определяющее вхождение и, как правило, достаточно много использующих вхождений.

Возникает ассоциация: идентификатор (имя) <= > ОД

Набор ассоциаций между идентификатором и определяющим его вхождением называется средой ссылок.

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

Список файлов лекций