лекция 15 (Языки программирования (лекции) (2008))

2019-09-19СтудИзба

Описание файла

Файл "лекция 15" внутри архива находится в папке "Языки программирования (лекции) (2008)". Документ из архива "Языки программирования (лекции) (2008)", который расположен в категории "". Всё это находится в предмете "языки программирования" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Онлайн просмотр документа "лекция 15"

Текст из документа "лекция 15"

Языки программирования. Лекция 15.

Понятие абстрактного типа данных(АТД). Как АТД реализуются в модульных яп: Модула-2, Ада, Оберон (либо мы полностью открываем тип, либо полностью его закрываем). Как реализуется инкапсуляция в ООЯП.

АТД=Мн-во операций, причем это множество должно быть явно перечислено с указанием типа.

Модульные яп:

1) Модула-2

Здесь есть так называемые прозрачные типы данных (opaque):

TYPE T; ~ прозрачный тд, только в модуле определений.

Это аналог абстрактного типа данных, т.к.:

- Тут есть явные операции (в модуле определений), которые аргументом имеют тип данных Т, операции присваивания и сравнение на равенство/неравенство (=/#), операция передачи через параметр--> только явные операции.

- Мы не знаем о его структуре, а можем оперировать только с помощью явных операций.

Проблема:

В Модуле-2 все библиотечные модули делятся на модули объявлений и модули реализации. Они физически раздельны и для трансляции программы нужен только модуль определений. Модуль реализации нужен для сборки программы.

FROM M IMPORT T; другой модуль импортирует тип Т

VAR X;

X := Y; ? устройство тд

IF X = Y THEN ... (X=Y- ? устройство тд)

Для трансляции этого кода нужен только модуль определений. Но как он узнает устройство типа данных Т и его размер? Ведь объявления типа TYPE T=... надо смотреть в модуле реализации.

Поэтому накладываются ограничения:

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

Пример:

стек-->атд:

  • список- реализуется указателем--> ок

  • массива--> должен быть динамическим

TYPE STACK;

должны быть операции типа:

Init();

Destroy();

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

При переходе от одного способа реализации к другому, изменится только модуль реализации.

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

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

2) Ада

В языке Ада есть 2 понятия:

-приватные типы данных

-ограниченные приватные типы данных (это в чистом виде абстрактные типы данных).

приватный тд:

package Stacks is

type Stack is private

procedure Push (S:inout Stack; X:integer); -процедура, т.к. первый параметр- входной/выходной

procedure Pop(S:inout Stack; X: out integer);

function Peak(S:in Stack) return integer;

Язык Ада требует, что если появился один приватный тип данных, то в спецификации пакета должно быть полное описание приватных типов данных, в приватной части, к которой воспользоваться может только компилятор:

private

...

type Stack is record

body: array (1..100) of integer;

top:integer := 1; тривиальная константная инициализация первого элемента

end record

Компилятор знает размер тд, и при размещении в памяти будет произведена инициализация.

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

Альтернативная реализация стека через указатели:

type Stack is access;/отмечаем, что это будет указатель, но какой пока не известно, определение дается в следующих строчках.

type link is record

next: Stack;

body: integer;

end record

type Stack is access link;

end Stacks;

Меняется реализация - следовательно, меняется и спецификация, и компилятор будет перекомпилировать нужные модули- увеличиваются накладные расходы.

К приватным типам данных применимы операции(мы знаем структуру тд):

- присваивания

- сравнения на равенство/неравенство + любые другие сравнения (например: применимы к записи, если такие операции применимы к элементам записи).

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

Ограниченный приватный тип данных:

type T is limited private;

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

--> Т- настоящий атд.

3) Оберон

Оберон упростил подход Модулы-2 В нём допускается частичная видимость данных:

Нет прозрачного тд.

*- экспортируется

TYPE Stack* = RECORD

body: ARRAY N of INTEGER;

top: INTEGER;

END;

Стэк - абстрактный тип данных, его структура не экспортируется--> клиентские модули ничего не знают о его структуре.

Применимы:

PROCEDURE PUSH*(...)-экспортируемые тд.

Как и в Модуле-2, применима операция присваивания.

В языке Оберон-2 есть хорошее приближение к понятию абстрактного типа данных, нет чистого атд , т.к. мы не можем запретить операцию присваивания.

Мы находим простоту, но теряем на перекомпиляциях.

Пример:

изменения в файле на Delphi :

-implementation приводит к перетрансляции модуля. unit перетрансляция

- проверка побайтно старой версии и новой версии interface после перетрансляции unit'a, совпадение -перетрансляции нет, иначе перетрансляция(комментарии не меняют interface)

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

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

Язык Дельфи с одной стороны похож на Модулу-2, но с другой стороны это язык с классами. Инкапсуляция работает не на уровне модулей, а на уровне классов.

ООЯП:

Здесь управление доступом!(см. прошлую лекцию)

1) Си++

Почленный доступ

Есть три уровня доступа:

- public

- private

- protected

Такая простая структура видимости уже является слишком ограничительной. По умолчанию, если не указан модификатор доступа, то предполагается private для классов и public для структур.

Рассмотрим класс:

class Matrix

Все ли операции с этим классом имеет смысл реализовывать через его методы?

Как перекрыть сложение двух матриц?

Можно перекрывать её как функцию-член:

Matrix &operator + (Matrix & M); // Возвращает по ссылке .

А можно перекрыть и так:

Matrix operator + (Matrix &M1, Matrix &M2); // возвращает по значению, лучше для атд,т.к. оба операнда равнозначны.

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

чисто двуместные операции лучше как внешние ф-ии, а операторы типа += ф-ми -членами.

Доступна только одна из этих двух форм, иначе их просто нельзя будет отличить.

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

Для этого ввели понятие "друг класса"- внешняя ф-ия (класс, член класса), имеющая права , такие же как и у членов этого класса. Понятие друга декларируется самим классом (друзей не навязывают), понятие друга не является транзитивным, друзья не передаются по наследству.

class Matrix{

friend Matrix operator + (Matrix &M1, Matrix &M2);

Matrix &operator += (Matrix &M);

}

class X{

friend class Y;// все ф-ии класса y имеют доступ к ф-ям класса x

}

class Y {

friend class Z; все ф-ии класса z имеют доступ к ф-м класса y, но не имеют доступ к ф-м класса x

}

А как в других ЯП?

В других ЯП был осознан факт, что функции бывают несимметричными.

Когда мы программируем класс, у нас есть сам класс, проект (та часть проекта, которую программирует автор класса) и всё остальное.

В Си++ есть только класс, друзья и недруги.

2) Java

В языке Java есть:

- public - класс доступен всем (как для классов из пакета, так и для классов из других проектов);

- private - с точностью до наоборот - недоступно никому кроме функций-членов своего класса, друзей тут нет!"

- protected - только функциям - членам класса и производным от этого класса

(внутренне-пакетный доступ).

Пакет -некоторая совокупность классов, единица контекста. Пакет- часть проекта.

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

Отличие - модификатор ставится перед каждым членом класса! Отсутствие модификатора означает внутренне-пакетный доступ.

Друзьями можно назначить любой класс из нашего пакета (внутренне-пакетная видимость, пакетный доступ). отгородится с помощью private и protected( применимы только к членам, а не к классам! Зачем нужен класс, недоступный никому.).

Перед классом имеет смысл ставить либо public (доступен всем), либо вообще ничего не ставить (пакетный доступ).

Пакет в языке Java не одно и тоже, что и пакет Ada -полноценный модуль.

3) Си#

Всё то же самое, но вместо пакетного доступа есть модификатор internal( явное ключевое слово). Но вместо пакетов используются пространства имён. По умолчанию, если отсутствует модификатор доступа, то подразумевается private, нелогично для классов, т.к. если перед классом ничего не стоит, то - internal.

Есть ещё модификатор protected internal - доступно только для производных классов, но внутри данного пространства имён.

namespace S {

public class X {

public void f() {...}

protected void g() {...}

protected internal void h() {..}

}

class D:X {

void my() { h(); f(); g();//ок

}

}

using S;/ / в другом пр-ве имен имена из s, которые public(классы, перечислимые типы)

class Y:X {

void my() {

f(); // ok

g(); // ok

h(); // error!, так как там указан модификатор для внутреннего доступа (internal)

}

}

Delphi

В языке Delphi пространством имён служит unit.

-public

-private

-protected

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

type X = class

i:integer; // внутренний член

public:

protected:

end;

( Java , C# рефлексия есть только, если классы подключаются динамически)

Применительно к классовым ЯП абстрактный тип данных - это класс, в котором публичными являются только операции.

В языке Оберон при наследовании:

TYPE T* = // * means that T is public

RECORD

X*:INTEGER;

Y:REAL;// private

В этом примере переменная Х доступна всем.

Чистого private нет.--> существенный недостаток

Y очень похожа на internal.

В этих языках абстрактный тип данных - некоторый публичный класс, в котором публичные только методы. Пример на C# или Java:

public class APP {

public op1 {}

public op2 {}

private int i;

public abstract void f(); // абстрактные функции не имеют тело, тело должно быть определено в производных классах!

АК-класс, у которого есть хотя бы одна абстрактная ф-ия(не имеет тела)

Ещё раз напоминаем, что АТД и АК - ортогональные понятия!

7


Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5224
Авторов
на СтудИзбе
426
Средний доход
с одного платного файла
Обучение Подробнее