Курс за второй семестр. Абстрактные типы данных

Вид материала

Содержание

Представление сложных типов.
Проблемы реализации ввода-вывода.
Реализация процедур
Реализация структур управления.
Путь наверх.
Передача параметров.
Сохранение и восстановление значений.

Подобный материал:

1 2 3 4 5 6 7 8

Мини-Паскаль.

(Паскаль, из которого выброшено всё лишнее).

Данные и сами программы хранятся в памяти. Реально существует много типов памяти: внешняя память (файлы) и оперативная, которая, в свою очередь, имеет много подтипов.

Память со случайным доступом,

Регистровая память и т.д.

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

Bit=0..1;

Byte=array[0..7] of bit;

Word=byte;

Математические языки не содержат явных описаний, но лишь действия по выделению памяти, которые мы можем трактовать логически как применение оператора new, а реализовать пропуском участка памяти.

Goto begin

память

под

переменные

begin

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

Замечание: На практике программист на машинном языке очень редко использует абсолютные адреса (отсчёт от начала памяти), но относительные адреса (смещение, отсчёт от некоторого фиксированного адреса, который называется базовым).

базовый

смещение

Это даёт возможность операционной системе разместить программу в любом свободном на этот момент участке памяти.

С точки зрения ЭВМ, вне зависимости от носителя любая информация есть последовательность слов (bye). Единственным типом нашего языка будет то, что раньше мы называли ячейками памяти – последовательности или одномерные массивы машинных слов. Этот тип мы будем называть двоичным полем. Поля задаются адресом начала поля и его длиной.

начало длина

///////////////////////////

Память в целом, конечно, - тоже двоичное поле.

{var Mem:field}

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

Близкие к машинным языкам языки ассемблера разрешают использование символьных имён полей и символьных кодировок команд (то есть язык ассемблера – ориентированная на человека форма машинного языка). В отличие от Паскаля и других языков высокого уровня имеется однозначное соответствие между командами машинного и языка ассемблера.

Конечно, все переменные – это подполе основного поля.

Пример синтаксиса: А[10] – десять машинных слов, лежащих по адресу А.

Может ли наш единственный тип заменить все типы данных? В принципиальном плане (в теории), если игнорировать конечность памяти, то, конечно, да!

Двоичный тип универсален. Любой другой тип можно смоделировать (реализовать) в нём, по крайней мере, хотя бы одним способом. На деле таких способов много. Они называются форматами (представление данных и команд).

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

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

Записью числа в k-ичной системе счисления называется последовательность кодов от 0 до k-1.

m n

n=∑ a_ikⁱ (n=∑ a_i2ⁱ – для двоичной)

i=0 i=0

Упражнение. Написать алгоритм перевода числа из k-ичной в «нормальную» (десятеричную) и обратно.

0 1 0 1=5

1*2⁰+0*2¹+1*2²+0*2³=5

В зависимости от того, занимает ли число фиксированное или переменное количество слов, существуют фиксированные и переменные форматы. Для указания формата фиксированной длины достаточно лишь указания адреса.

Для простоты будем считать, что мы будем использовать форматьы только фиксированной длины и знать значения констант: cSizeOfInteger, cSizeOfChar, cSizeOfReal и так далее, которые измеряются в байтах.

Понятие формата определено не только для данных, но и для команд, причём для каждого формата, например, числового, имеются свои операции.

Представление сложных типов.

Адресная арифметика.

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

P

ole Pole+i

i

Такие адреса называют относительными, число I – смещением, адрес поля – базой.

Пусть поле содержит n значений некоторого типа с длиной cSize Of T.

Pole+i*cSizeOfT

P

ole j

a₀a₁a₂ a₃

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

A[1]→A

A[2]→A+cSize Of T

A[3]→A+z*cSize Of T

A[i]-?

Решение – адресная переменная или ссылка. Запись адреса вида p называется в машинных языках неявной или косвенной.

Пример: Суммирование элементов последовательности. Известно, что поле А содержит 10 числовых значений в формате длины 4.

S:=S+p;

S:=0;

p:=addr(A);

p:=1;

while I<10 do

begin

S:=S+p;

i:=i+1;

p:=p+cSizeOfT;

end;

Реализация записи аналогична реализации массивов.

cSize Of T₁ cSize Of T₂

R p₁ p₂ p₃ …

R+cSize Of T₁+cSize Of T₂+…+cSize Of T_i-1; - указатель на i-е поле записи

Проблемы реализации ввода-вывода.

Идея буферизации.

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

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

Физическая организация - помимо специфичных для каждого устройства особенностей, центральной проблемой ввода-вывода – существенно более низкая скорость обмена данными внешней памяти по сравнению с внутренней (оперативной). Пути решения этой проблемы за счёт распараллеливания обработки внутренних и внешних данных рассмотрим на примере стандартного Паскаля. В стандартном Паскале read и write – не операторы, но процедуры, реализованные с помощью операторов get и put. С каждым именем файла автоматически связывается переменная со стандартным именем f, называемая буфером и имеющая для файла file of T тип T, для текстового – char. Оператор get(f) считывает очередную компоненту файла в переменную f, put(f) записывает в файл содержимое буферной переменной.

Get(f)~read(f,f);

Put(f)~write(f,f);

Реализация процедур read и write.

Read(f,x) ~ x:=f; get(f);

Write(f,e) ~ f:=e; put(f);

Кроме того, с обработкой буфера связаны операторы: reset(f), который считывает первую компоненту файла (если есть), close(f) – выводит содержимое буфера в файл.

Суть идеи буферизации – распараллелить обмен со внешними носителями на два независимо выполняемые отдельные исполнителя:

1) Быстрый обмен в оперативной памяти;

2) Обмен между буфером и физическим файлом. То есть параллельно с основной программой работает копирование из файла в буфер. Так работают ввод и вывод.

Реализация структур управления.

Оставим в нашем мини-Паскале два оператора: оператор присваивания и бинарное присваивание вида y:=[y]x, где  - одна из базовых операций, к которым мы отнесём арифметические операции: +, *, -, div.

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

Принцип сведения содержательных операций для нас не нов (пример – сложение столбиком). Очевидно, такого присваивания достаточно для пошагового вычисления любых арифметических выражений.

Все структуры управления реализуются с помощью оператора условного перехода:

if B then goto M, где М – метка (адрес команды), а В – базовый предикат (= или ).

Упражнение. Выяснить, являются ли необходимыми операции сравнения. (нет).

if B then S₁ else S₂

if B then goto M;

S₂; goto M₂

M: S₁

M₂:

S₁

S₂

while B do S

N: if not B then goto M; S; goto N;

M:

M

+

Все остальные циклы и структуры выражаются через while.

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

Упражнение^*. Запрограммировать на мини-Паскале программу вычисления суммы 10 чисел.

Упражнение^*. Написать алгоритм построения по любой блок-схеме последовательности операторов в мини-Паскале.

Задача сложения 10-ти чисел:

var a:array[1..10] of integer;

begin

s:=0; i:=1;

while i<=10 do

begin

s:=s+a[i];

i:=succ(i);

end;

write(s);

end.

goto prog;

prog: s:=0; i:= 0’

p:=addr(A);

i:=1;

N: if i>10 goto M;

s:=s+p;

p:=p+cSizeOfInteger;

goto N;

M;

write(s);

Замечание: Потеря эффективности. В случае непроцедурного программирования на мини-Паскале мы могли бы сэкономить память (переменная i) и время выполнения за счёт трактовки p как счётчика цикла: if p<10*cSizeOfInteger – типа того…

Путь наверх.

Реализация процедур-подпрограмм.

Понятие подпрограммы как выделенного фрагмента программы, реализующего некую операцию – первый в программировании пример структуризации, разделения логики и реализации. Первые языки высокого уровня – Fortran и Basic – базировались именно на идее языка программирования как набора стандартных подпрограмм.

Пример: вызов и возврат.

Рассмотрим частный случай процедуры без параметров.

Procedure proc;

begin

z:=x+y; proc

e

nd;

B
goto
egin

…

…. vozvrat1

End.

Vozvrat1

Goto proc

{подготовка возврата}

вызов возврат

Положить в vozvrat адрес следующей после goto команды:

Vozvrat:=ThisAddr+cLenGoto, где cLenGoto – длина команды goto.

{Выразить через бинарное присваивание}

{vozvrat:=ThisAddr;

vozvrat:=vozvrat+cLenGoto}

goto proc; {подпрограмма вызывается только явным образом – первой выполняется первая команда основной программы}

proc: {z:=x+y}

z:=x;

z:=z+y;

goto vozvrat;

proc: goto procvozvrat:=ThisAddr;

vozvrat:=vozvrat+cLenGoto; goto proc; {главная программа}

Передача параметров.

procedure Proc(x,y:integer;var z:integer);

begin

z:=x+y;

end;

{основная программа}

proc(a+1, 2, c);

{подготовка фактических параметров}

{подготовка возврата}

{вызов}

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

param

a+1 2 addr(c)

val(a+1)

pointer:=addr(param);

pointer:=a+1;

pointer:=pointer+cSizeOfInteger;

pointer:=2;

pointer:=pointer+cSizeOfInteger;

pointer:=addr(c);

Фактически единственным аргументом поля является некоторая стандартная переменная pParam, содержащая адрес списка параметров.

pParam:=addr(param);

Единственная информация, которой обладает подпрограмма – то, что в переменной pParam находится адрес списка параметров с известной структурой. Любая подпрограмма начинается с раскодирования списка параметров.

pointer:=pParam;

x:=pointer(cSizeOfInt);

pointer:=pointer+cSizeOfInt;

y:=pointer(cSizeOfInt);

pointer:=pointer+cSizeOfInt;

z:=pointer(cSizeOfInt);

z:=x;

z:=z+y;

goto vozvrat;

Сохранение и восстановление значений.

Соглашение о связях.

Смысл подпрограмм – отделить логику (функцию, операцию как математический объект высокого уровня абстракции) от реализации, определение этой функции на данном языке программирования. Это обязывает к тому, чтобы стандартизировать все детали, не относящиеся к логике. Таким образом, всё, кроме имени функции (адреса начала подпрограммы) и структуры параметров, должно быть общим для всех вызовов. В частности, стандартными должны быть имена vozvrat и pParam. Соответствующее требование носит название стандартного соглашения о связях. Наша схема пока не поддерживает соглашения о связях, а, следовательно, и кратных вызовов.

вызов1 вызов2

vozvrat vozvrat

вызов2 вызов1

восстановление

Второй вызов (точки определения адреса возврата в стандартной переменной vozvrat) портит её значение, поэтому возврат2 невозможен. Кратные же вызовы необходимы не только из соображений удобства программиста. В реальности любой вызов кратный, поскольку наши программы являются подпрограммами главной программы, постоянно работающей на компьютере, а именно ОС.

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

oldvozvrat:=vozvrat

vozvrat:=oldvozvrat

восстанавливает

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

Blog

Курс за второй семестр. Абстрактные типы данных

Содержание