лекции (2007), страница 6

- файлы

Со временем они упростились в

- массив

- запись

- класс

Массив

Массив - ф-ия , которая некоторому значению ставит ссылку на объект f(i) -> D&.

Различия в понятиях массива сводятся к различиям в определении индексирования: f(i) - что такое i? В Фортране операция индексирования – функция. Далее стали появляться квадратные скобки (Алгол).

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

length - размерность соответствующего декартового пр-я,

lbound(), ubound() -нижнее и верхнее значения.

Первый вариант Паскаля – array[real] of real – не смогли реализовать. В стандарте Паскаля введены дискретные типы и операции succ, pred, ord. Дискретные типы и являются основой массивов, т.к. например, для любого float succ и pred будут работать по-разному => нельзя.

Вопрос состоит лишь в том, какие дискретные ТД доступны в языке, и каково время связывания, ведь так как любой дискретный тип приводится в целый при помощи ord и int мы можем получить то, что нам надо.

Ада

тип  подтип

тип 1 -> только явное преобр-е -> тип 2

(неявн, (неявн,

контр) контр)

подтип

T2 is new T1[огр-е]

X: T1;

Y:T2;

X:=Y; - нельзя

X=T1(Y);

Допустимые типы объявления массива:

array(INDEX) of T;

type ARR1 is array (0..n) of integer;

В общем случае синтаксис такой:

type A is array (index) range (L..R) of T; (если L=0 и R=0 - статические атрибуты типа, то массивы будут разные)

type A1 is array (integer range <> ) of real;

X:A;

Y:A1; -ошибка, так как он неограниченный

function SCAL(x,y:a1) returns real; - можно, т.к. предполагаем, что передаются подтипы

Можем объявить:

Y:A1 range 0..20;

X:A1 range 1..21;

Z:A1 range 0..10;

B:T range L..R;

X’LENGTH – атрибутная ф-ия, возвращает длину массива

X’RANGE – возвращает L..R

Пример процедуры sub:

int :real=0;

begin

for i in X'RANGE loop

int:=int+A(i);

end loop

return int;

end sub

type A2 is new A1 range 0..20;

XX:A2;

A:A1;

X=XX; - нельзя, только если явно объявить или сделать подтип:

subtype A3 is A1 range 1..21;

В языке Ада есть одно послабление, ведь существуют динамические массивы. Динамические массивы - это квазистатические массивы. Массивы в C# и Java - динамические. А в Аде - нет.

«Динамические» массивы

В языке Модула2 введена функция high(a), она возвращает максимальный номер n-1. Таким образом длина массива high(a)+1. Формальному параметру «открытый массив» передается адрес и число элементов. Считается, что индексация идет от 0 до high(a). Операция a[i] для любого массива является контролируемой. Все как в Паскале, контроль основывается на динамической границе. В Обероне все то же самое, только понятие открытого массива распространено на многомерные массивы.

var a:array 0,0;

В обероне, как и в Модуле2 длина массива - статический атрибут типа, за исключением открытого массива. Функция high определена для любого массива, она либо статическая, либо динамическая.

Существенно все упростилось, так как диапазон типа, перечислимые типы - все это отпадает.

Массивы имеют в основном ссылочную природу, все они являются динамическими.

Инициализация массива - указание его типа и длины. a[] - динамический, но так же и квазистатический, потому что как только мы отвели элементы, он продолжает быть массивом длины n.

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

Procedure P(N:integer) is

A: array(range 0..N) of integer;

begin

A[I]:=…

end

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

К чему эффективнее доступ, к динамическому или статическому? Доступ к динамическим массивам эффективнее, чем к статическим.

Если мы допускаем, что массивы имеют переменную длину, то переменные, которые хранятся после нее имеют переменный адрес.

В стандарте C уже разрешено иметь такие массивы. Они необходимы, например, в численных расчетах.

В современных ЯП происходит упрощения понятия массива. Любой массив динамический, и диапазоны индексов целочисленные.

Многомерные массивы

int a[]

int b[][] – ошибка; правильно: int b[][n], int c[][N1][N2] – многомерные массивы

C#:

int []a = new int [N1][N2]

int [][]b = new int [][N1]

b[0] = new int [25]

b[1] = new int [10]

Вырезки

A(N1,N2)

A(*,1) – первый столбец

A(2,*) – вторая строчка

A(2..5,*)

A(1..2,1..2)

Базис

Станд. библиотеки

C++ - почти выполнено, кроме dynamic_cast<T &>(e) (bad_cast из SDL)

Java – нельзя реализовать свой класс string, т.к. нельзя, например, перегрузить операцию «+» (для a+b)

C# - -||- Java, т.к. нельзя выполнить некоторые преобразования (Int32int)

Записи

В отличие от массива, у которого основная операция – индексирование [ ], у элементов записи есть операция name.id, которая применима слева к объекту типа «запись», а справа – к имени поля. Синтаксис записи во всех языках практически одинаков. Если мы заключаем набор объявлений переменных в скобки, то эта совокупность объявлений считается локализованной в записи, и доступ к ним может быть только по имени записи.

Записи с вариантами (объединения)

Есть в Ст. Паскале, Ада, С, С++, Модула 2.

record

[список полей] - постоянная часть

переменная часть:

case [имя]:тип of

v1: часть 1

v2: часть 2

v3: часть 3

end

Бывают размеченные и неразмеченные.

C: struct C

{

поле1;

поле2;

union{

v_chast1;

v_chast2;

} var;

}

Записей с вариантами нет в Обероне, C#, Java.

Запись в современных ЯП мигрирует в понятие «класс». Но у класса могут быть еще и методы. Класс носит не только ф-ию типа данных, но и модуля. Вместо механизма объединения типов есть наследование классов. Пустой базовый класс не является ошибкой. Далее каждый конкретный класс выводит из базового класса свои необходимые поля.

2 точки зрения:

В Java понятие записи вообще убирается. Структура отличается от класса в С++. Умолчание правил доступа. В классе наследование и доступ по умолчанию приватные, в структуре - публичные). Имена классов обязаны быть уникальными, а имя структуры - нет (если класс описан при помощи структуры).

В C# понятие записи совершенно другое. Есть понятие value type и reference type структур - нереференциальные типы данных.

точка - point x,y

Быстрее инициализировать массив point нежели массив ссылок на структуры point.

Структуры - недокласс в C#. Структура не может наследовать и наследоваться. Не существует виртуальных методов структуры, как любой класс может содержать ф-ии-члены. У структуры нельзя переопределять конструктор умолчания (конструктор без параметров), так как в C# любой объект без начального значения.

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

Остальные составные ТД

Паскаль – множество set of T;  [0..N-1] -> N бит

В разных реализациях Паскаля – разный максимальный размер мн-ва (например, 256).

Операции над мн-вом: X in S, +, -, * =

Incl(X,S) ~ S:=S+[X] добавление эл-та в мн-во

Excl(X,S) ~ S:S-[X] удаление эл-та из мн-ва

Модула2: SET of T;

специальный ТД:BITSET;

BITSET ~ SET of [0..N-1]

S: BITSET;

INCL(S,l)

Оберон: SET ~ BITSET в Модуле2

Таблица

(K,V); K - ключ

Операции: Lookup; Incl(K,V); Excl(K,V)

Строка

s tring string не наследует от vector

vector

ЯП Ada

Особенности:

1. работа с асинхронными процессами на уровне языка

2. модульность

Ada - уникальное объединение неуникальных средств и возможностей.

Асинхронные процессы.

Все процессы выполняются внутри одной программы. Управление процессами при помощи fork и пр. основано на концепции внешней дисциплины.

Процесс должен сам позаботиться о работе с семафорами и пр. Ada предлагает другую концепцию, что те ресурсы, которыми пользуется процесс, сами являются умными. Процессу становится намного легче работать. Становится возможным заботиться о содержательных вещах. Основная идея Ады – язык должен помогать писать надежные программы. Все делается на основе статического контроля.

В Аде существуют программные модули, позволяющие описать асинхронные процессы. Этот модуль называется задачей.

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

Определение, запуск процесса.

procedure Main is

task T1 is ... end T1

task T2 is ... end T2

task body T1 is ... end T1

task body T2 is

task T3 is .. end

begin

end T2

begin … Main //запустятся все процессы, описанные в задачах main T1 T2 T3

end Main //тут Main стоит и ждет, пока не завершатся все запущенные им процессы

//задача – тип, можно описать тип, в котором есть ссылка на задачу.

task T is

entry E1,

entry E2(X: in out Some Type)

end T;

task body T is

var: some_type;

begin

....

accept E2(x: in out Some_type) do

Var :x;

end E2;

accept E1;

.....

accept E1 do ... end E1;

end

task T1

entry E1(X: Some_Type);

end T1

task body T1 is

var1: some_type;

begin

....

accept E1(X: Some_type) do

var1:=x;

end E1;

T2.E2;

end T1;

task T2 is

entry E2

end T2;

task body T2 is

var2: SOme_type;

begin

.....

T1.E1(var2);

.....

accept E2;

.....

end T2;

СООБЩЕНИЕ->АНАЛИЗ->СИНТЕЗ->ВЕРНУТЬ ОТВЕТ ВО ВНЕШНЮЮ СРЕДУ

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

Пусть сообщения поступают с частотой Т, обрабатываются Т-Е

E<<T

cp. T=E1

E1<<T

max=3T

Нам нужна возможность передавать и принимать результаты, мы не хотим заниматься реализацией.

package Анализ-Синтез is

type Сообщение is

type Ответ is new Сообщение;

task Анализ is

entry Принят(X: in Сообщение);

end Анализ;

task Синтез

entry Выдать(X: out Сообщение);

end Синтез;

end Анализ-Синтез;

package Генератор_Сообщений is

task Генератор

entry Start;

end;

end;

package Потребитель_Сообщений is

task Потребитель

entry Start;

end;

end;

with Генератор_Сообщений;

with Потребитель_Сообщений;

procedure Main is

Генератор_Сообщений.Генератор.Start;

Потребитель_Сообщений.Потребитель.Start;

………

end Main;

with Анализ-Синтез;

package body Генератор_Сообщений is

task body Генератор is

Message: Анализ-Синтез Сообщения;

begin

accept Start;

loop

Message:=…;

Анализ-Синтез.Анализ.Принять(Message);

end loop;

end;

end;

…)->АНАЛИЗ СИНТЕЗ->(…

разбор разбор

БУФЕР

package body Анализ-Синтез is

type Разбор is new Сообщение;

task Буфер is

entry Положить (X: Разбор);

entry Взять (X: out Разбор);

end Буфер;

task body Анализ is