И.Г. Головин - Конспект лекций по курсу Языки программирования (1161120), страница 13
Текст из файла (страница 13)
Сокращение архитектурНапример: исчез диапазонСТРУКТУРНЫЙ БАЗИС ИМПЕРАТИВНЫХ ЯПСТРУКТУРНЫЕ ТИПЫМассивыРассмотрим такие структурный ТД, как одномерные и многомерные массивы и записи. Вязыке Фортран есть только массивы, что правда не критично – на базе массива можносмоделировать и запись.Какой множество значений и операций представляет массив? Рассмотрим одномерныймассив:Пример (C)T a[50] // покажем некрасивость СT b[50];a = b; //запрещеноЭквивалентноT* const a;//+распределение памятиT* const b;//+распределение памятиa = b;//запрещеноЕсли внешний объект или формальный параметр, то распределятьпамять не нужно!T* pa;70pa = a; //можноЕсли есть внешний объект или формальный параметр, то распределять память не нужно!T* pa; pa = a; //можноОперация сравнения:В хороших языках программирования существуют операторы:?=/=(АДА: если массивы одной длины и одинаковый тип – их можно сравнивать)Операция индексрования []Множество значений нужно определить, например, чтобы отличить массивы от коллекций(набор элементов с прямым доступом и последовательным доступом).
Коллекция обобщаетпонятие массива. чем отличается коллекция от массива? В коллекцию можно добавить илиизъять элемент. Массив – низкоуровневое понятие; последовательность элементовфиксированной длины. Массив непрерывен! Непрерывность – ключевое слово в понятиимассива.Атрибуты массива: базовый тип (Т), длина (length), левая и правая границы (L..R), диапазон(Diap).[]: A,Diap ->T&X:T;T:A;Y[i] = X;X = Y[i]; – и то, и другое допустимоИ так в любом языке (кроме С – в нем нет ссылок). Переходя от С к С++, в базисе изменилисьтолько ссылки (еще enum – тип, bool, но это косметика).
Нельзя полноценно реализоватьоперацию индексирования без ссылок, поэтому Страуструп и ввел ссылки.В массивах T и Diap – чисто статические во всех языках. В языках C, C++, Java, Python типдиапазона зафиксирован. В языке Оберон:L ≡ 0, R ≡ Length -1 => TYPE ARR = ARRAY N OF T;Length, L..R – статические (например, язык стандартный Pascal, C, особенно C89) иликвазистатические.В стандартном Паскале невозможно написать процедуру обработки массива(недемонстрационную).
А почему? Атрибут Length статический и принадлежит ТД, аследовательно, этот атрибут наследуется всеми ОД этого типа. Это означает, что длину мысвязываем с типом данных. Эта длина не может у нас поменяться. Как следствие встандартном Паскале нельзя было написать процедуру скалярного произведенияпроизвольных векторов. Полезная процедура, которая в ряде проблемных областейвычисляется очень часто. Процедуру такого рода написать никак нельзя потому, что мы71обязаны именовать соответствующие формальные параметры, приписывать им тип данных,это очевидно тип данных массив. Атрибут длина статический, следовательно, этапроцедура будет считать скалярное произведение только для массивов фиксированнойдлины.
Для массивов другого типа нужно переписывать соответствующую процедуру. Этосамый большой недостаток языка Паскаль. Ведь массив – это базисная структура для любыхвидов программирования.Type Arr = array[0..N-1] of char;1..N – никак, другой тип =>ни одной полезной обработки процедуры не описать.А в С нет типа массива, поэтому нет этого недостатка. Передаём указатель и длину (каквторой параметр).var X,Y,Z:Arr;X[i], Y[i], Z[i] можно вычислить оптимальным образом, т.к.
известно распределениепамяти.X[i] ≡ адрес X + sizeof(T) + (i-L)X[RX] транслируется в любом языке АссемблераВ Аде, Модуле-2 и Обероне все распределение памяти под массивы – статическое, аиспользование – квазистатическое.Пример (Модула2):TYPE ARR = ARAY [L..R] OF T;Тип и значение тих переменных должны быть известны во времятрансляции.VAR X,Y: ARR;Появляется понятие – открытый массив – только физическийпараметр некой процедуры или функции.ARRAY OF T;PROCEDURE SCAL (VAR X,Y: ARRAY OF REAL) : REALBEGINCNT := 0;FOR I:=0 TO HIGH(X) STEP 1 DOCNT := CNT + X[I]*Y[I]ENDRETURN CNTEND SCALФактическим параметром может быть любой массив типа REAL. HIGH(X) выдаетмаксимальное значение диапазона.72VAR A: ARRAY[0..N-1] OF REALB: ARRAY[1..N] OF REALSCAL(A,B); – работает.Есть еще язык Модула-3 с исключениями, динамическим распределением памяти и многимдругим.
В Фортране начиналось с 1 диапазона (математический). Начиная с языка С и вовсех современных языках диапазон начинается с 0. В Модуле-2 и Обероне отклонение отстатики только в формальных параметрах. АДА же более выразительна.Тип/подтипПонятие неограниченного ТД:Неограниченные ТД: Type BaseArr is Array INTEGER range <> of T;Ограниченные ТД: Type Arr is Array INTEGER range 0..N-1 of T;У ограниченного типа все характеристики статические. У неограниченного типа длинавообще не определена. Неограниченный тип нужен для введения подтипов.X,Y: BASE ARR range 0..N-1;C:Arr;SUBTYPE BA1 is BaseArr range 0..N-1SUBTYPE BA2 is BaseArr range 1..ND:BaseArr – нельзя, будет ошибкаA: BA1; переменная типа BaseArrB: BA2; переменная типа BaseArrBa1,BA2 – подтипX := Y – корректноX := A – корректноX := B – корректно, т.к.
длина совпадает N-1 = N – 1X := C – нельзя, разные типы данныхC := X – нельзя, разные типы данныхA’LENGTH – длинаA’LEFT – левая границаA’RIGHT – правая границаA’RANGE – диапазонПример (Ада)73Type A is array integer range <> of float;Function “*”(A,B:Arr) return float isi:integer;beginif A’length != B’LENGTH thenraise Index_out_of_Range;endif;for i in A’RANGE loopres := res +A(i)*B(i);end loop;return res;end “*”;Как происходит в современных ЯП (например, Java):Tint0..N-1N – квазистатический атрибут(как только массив порожден, то N – статический)T[] a; a – ссылка на массив элементов типа TДлина не является статическим атрибутом.
Конкретно массив появляется при выполненииnew: a = new T[N]; => уже статическийa.Length (на C# с большой буквы)Внутри коллекции всегда есть метод toArray(). Коллекции вообще говоря некоторыеприкладные классы, имеющие набор интерфейсов.Старые ЯП имеют «нашлёпку» - динамические массивы (например, языки АДА, С99). Это насамом деле не динамические массивы, т.к. память для них отводится на стеке, они могутбыть только локальными.
Так что правильней их было бы назвать квазистатическими илилокальными.Пример (Ада):procedure P(N:integer) isA:array range 1..N of real;Begin<Обычная работа с А>endPПример (С)74void f(float* p,int n){float A[n];…}При этом описывать такие массивы, как аргументы нельзя. Эти массивы менее удобны –даже адрес базы надо вычислять через суммирование.Delphi – гибридный язык. С одной стороны он похож на Модулу2, однако имеет широкуюобъектную модель. Здесь специально введено понятие динамического массива. Setlengthведет себя как realloc. Диапазон от 0 до N-1.Многомерные массивыС/С++:T a[N][M]; // выделяется N*M*sizeof(T) памятиN строк, M столбцовПример (Java, C#)int []b;int [][]a;b = new int[10];a = new int[][20];//каждый из 20 элементов ссылкаfor (int i = 0; i<20; i++)a[i] = new int [i+1];В Java все массивы ступенчатые.T [,] b = new T[20,30]b[i,j] b[i][j]– форма обращения не важнаint []a = new int[]{1,2,3};– то есть {{1,2,3},{1,2,3},{1,2,3}}Без «танцев с бубном» можно работать с многомерными массивами в функциях (в отличиеот С/С++).В С# добавлено [,] для работы со старыми массивами.
В Java такого нет, а если хотитеиспользовать, то сами пишите отдельный класс.ЗаписиМассив: D* … * D(n раз)Запись: D1*…*DnОперации с записями751. Присваивание2. Операция точка(.)a.nameЗаписи впервые предложил (появились уже в COBOL’е, но были очень кривыми) Чарльз Хаарна конференции НАТО, затем перешло в Паскаль.Используется fieldname, значит необходимо смещение.Записи обобщены понятием класса. В современных языках программирования их почти неосталось.
Зато записи есть, например, в.C#Рассмотрим точки – у них есть координаты X,YPoint []P;X = new Point[1000];foreach (point p in X)p = new int(0,0)Добавлены структуры из соображения эффективности:Struct X{<описания полей и методов>}Структуры – обрезанные классы, их нельзя наследовать, они ни от кого не наследуются.Для всех типов значений существует класс Wrapper – обёртка (оболочка).Unboxing (распаковка), AutoBoxing (неявная упаковка), Boxing (упаковка).Объединение типовТип – роль данных. Единственна ли эта роль? Почему это важно? Роль определяетповедение объекта.
Поведение – набор методов. Единственная роль – единственный типданных.Особого смысла придумывать новые языки – нет. 1980г. Ада – вершина процессапридумывания.Любой объект данных принадлежит единственному типу данных. Один и тот же объектданных может выступать в нескольких ролях.Объектные языки избавили от аксиомы единственности типа данных. Пример: построениеинтерфейса пользователя (ИП).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
