Надъязыковый подход к изучению языков программирования (стр. 5 )

lОперация присваивания определена в любом классе по умолчанию как поэлементное копирование.

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

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

lЧтобы сохранить семантику присваивания, операция-функция должна возвращать ссылку на объект, для которого она вызвана, и принимать в качестве параметра единственный аргумент — ссылку на присваиваемый объект.

Семантика средств описания действий

Разработка программ

lОсновная задача, стоящая перед каждым программистом, — получение правильной программы.

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

lЭтот способ реализуется в два этапа:

nпроведение декомпозиции общей задачи на точно определенные подзадачи и доказательство того, что если каждая подзадача решена корректно и полученные решения связаны друг с другом определенным образом, то задача будет решена корректно;

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

lЧтобы доказать корректность программы, необходимо формально описать семантику операторов языка.

Основные понятия

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

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

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

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

lТекущий оператор

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

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

lЯзык программирования предоставляет как простые операторы — операторы действия, так и средства композиции — операторы управления, которые позволяют формировать составные операторы из других простых или составных.

Правила вывода

lДля описания семантики языка необходимо иметь правила вывода, позволяющие определить

nэффект воздействия простого оператора на состояние вычислений

nсвойства составного оператора, исходя из свойств его компонент.

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

lИменно это свойство дает возможность в достаточно простой форме описывать действия любого оператора или программы.

Спецификация программы

lПусть S — какой-нибудь оператор или программа, Р и Q — предикаты, описывающие состояние вычислений. Тогда семантика S описывается следующим образом:

{P} S {Q}

lЭто — спецификация программы, означающая: если предикат Р истинен перед выполнением S, то предикат Q будет истинен после завершения выполнения S.

lПредикат Р называется предусловием S, а предикат Q — постусловием S.

Свойства спецификаций программ

lДля любых S и Р всегда найдется некоторый предикат Q (например, true), который будет постусловием S, если Р — предусловие S

lДля любого S и любого Q всегда найдется некоторый предикат Р (например, false), который будет предусловием S, если Q — постусловие S.

lДля любых Р и Q всегда найдется программа S (например, while true do; end do;), для которой Р будет предусловием, a Q — постусловием.

lЗадача программиста — найти такую программу S, которая завершается и для которой Р является предусловием, a Q — постусловием.

Частичная и полная корректность программы

lЕсли S — программа, корректность которой мы хотим установить, то соотношение {Р} S {Q} — это то, что мы должны доказать, где Р — условие, которому должны удовлетворять начальные значения переменных, a Q — условие, которому должны удовлетворять конечные значения переменных.

lСоотношение {Р} S {Q} определяет только частичную корректность S.

lПрограмма, в которой гарантируется получение требуемого результата при условии ее завершения, частично корректна.

lЕсли дополнительно можно показать, что программа завершается при всех исходных данных, удовлетворяющих Р, то программа полностью корректна.

lЧтобы доказать завершимость программы, необходим анализ циклов.

Процесс разработки программы

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

nпостроение спецификации программы {Р} S {Q}, т. е. ясное и недвусмысленное определение того, как программа должна использоваться (предусловие Р) и какие результаты (постусловие Q) должны быть получены;

nопределение на каждом этапе декомпозиции спецификаций {Pj} Sj {Qj} для компонент Sj программы;

nразработка программы и ее компонент одновременно с доказательством корректности указанных спецификаций.

Запись предикатов

lПри записи предикатов Р и Q могут быть использованы следующие средства:

nИмена переменных, арифметические операции, операции сравнения.

nМатематические символы и функции.

nЛогические операции: конъюнкция,
дизъюнкция, отрицание и т. д.

nКванторы всеобщности ("), существования ($) и количества (N). Каждое вхождение переменной X в логическое выражение, которое не связано квантором, называется свободным, а X — свободной переменной.

Подстановки

nПусть Р — логическое выражение. Обозначение (1) используется для выражения, которое получается в результате подстановки выражения у вместо всех свободных вхождений переменной х в Р.

nАналогично (2) обозначает одновременную подстановку вместо всех свободных вхождений любой переменной хi в Р cоответствующего выражения уi Вхождения xi в уj не замещаются. Переменные х1,х2,… должны быть различными.

Правила вывода

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

lЕсли Н1,Н2,…,Нn — истинные утверждения, то Н — также истинное утверждение. Если входных условий нет (т. е. n=0), то правило вывода будем записывать просто в виде H

Простейшие правила вывода

lПервое утверждает, что если выполнение программы S обеспечивает истинность утверждения R, то оно также обеспечивает истинность каждого утверждения, которое следует из R.

lВторое правило утверждает, что если R — известное предусловие программы S, приводящей к результату Q после завершения своего выполнения, то это же относится к любому другому утверждению, из которого следует R.

lЭти два правила называются правилами консеквенции.

Правила тавтологии

lПравила тавтологии выводятся непосредственно из определения спецификации программы

lДля любых P, Q, S

n{P} S {true}

n{false} S {Q}

Правила замены

lДля доказательства правил достаточно рассмотреть два случая:

nP=true:

(Р=>{R}S{Q}) = ({R}S{Q}) = ({Р&R}S{Q})

nP=false:

(Р =>{R}S{Q}) = true = ({false} S {Q}) =

=({P&R}S{Q})

Выражения

lВыражения - простейшие средства описания действий, которые вычисляют единственное значение, не изменяя состояния вычислений.

lОсобенность вычисления выражений с логическими операциями

n - если первый операнд в выражении (A and В) ложен, то и значение всего выражения ложно независимо от значения второго операнда.

n - если первый операнд в выражении (A оr В) истинен, то и значение всего выражения истинно независимо от значения второго операнда.

lСледовательно, вычислять значение второго операнда в этих случаях не надо.

Операторы действия

lОператоры действия — это средства языка, позволяющие изменять в процессе выполнения программы состояние вычислений.

lСамый простой оператор действия — оператор присваивания:

Х:=Е;

lгде X — переменная или другой допустимый объект данных, а Е — выражение соответствующего типа.

Правило вывода для оператора присваивания

lЗдесь утверждается, что если Р истинно для подстановки Е вместо X перед выполнением присваивания, то Р должно быть истинно после присваивания переменной X ее нового значения Е.

Примеры использования правила вывода для оператора присваивания

 

Операторы управления

lОператоры управления — это средства языка, позволяющие управлять ходом выполнения программы.

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

lОператоры управления служат для выражения этих структур на языке программирования.

Оператор последовательного выполнения

lПростейшее средство управления — последовательное расположение операторов в тексте программы, что определяет последовательное выполнение их в порядке расположения.

Достаточно иметь правило для N=2

 

 

Условные операторы

lУсловные операторы позволяют выбирать для выполнения те или иные части программы в зависимости от некоторых условий.

lПусть В — логическое выражение (т. е. выражение, тип значения которого есть boolean), S1 , S2 — последовательности операторов (в крайнем случае один оператор). Тогда оператор

if В then

Si

else

S2

end if;

lозначает следующее: вычисляется В; если его значение истинно (true), то выполняется S, в противном случае — S2.

Правило вывода для условного оператора

lПостроим правило вывода для условного оператора. Если требуется установить истинность спецификации

{P} if В then S1 else S2 end if; {Q}

lто необходимо доказать два утверждения:

nЕсли В истинно, то выполняется S1. Так как Р
справедливо перед выполнением if, делаем вывод, что в
этом случае Р & В справедливо перед выполнением S1. Если Q справедливо после выполнения if, то должно быть
справедливо и {Р & В} S1{Q}. Итак, мы должны доказать {Р & В} S1 {Q} .

n2. Если В ложно, то выполняется S2. Так как Р
справедливо перед выполнением if, делаем вывод, что в
этом случае Р & not В справедливо перед выполнением S2. Если Q справедливо после выполнения if, то должно быть справедливо и {Р & not В} S2 {Q} Итак, мы должны доказать {Р & not B> S2 {Q} .

lЕсли мы доказали истинность {P&B}S1{Q} и {Р & not В} S2 {Q}, то можно утверждать, что если Р справедливо перед выполнением if, то Q будет справедли­во по окончании его выполнения независимо от того, какой оператор (S1 или S2) был выбран для выполнения.

 

Операторы цикла

lОператоры цикла позволяют повторять выполнение отдельных частей программы. Оператор вида

while В do

S end do;

lназывается оператором цикла while do, логическое выражение В — условием цикла, а последовательность операторов S — телом цикла.

lЦикл while do означает повторное выполнение S, пока В истинно:

nсначала вычисляется В; если его значение ложно (false), то выполнение цикла заканчивается, в противном случае выполняется S;

nпосле чего снова вычисляется значение В и т. д.

nТаким образом, если В ложно с самого начала, то S не будет выполняться ни разу.

Правило вывода для оператора while do

lПусть существует такой предикат Р, что

{Р & В} S {Р}

lПусть этот предикат истинен перед выполнением цикла. Тогда если в тот же момент истинно и В, то перед выполнением S будет истинным и Р & В. Но тогда после выполнения S опять будет истинным Р. Если при этом В снова истинно, то получаем еще раз истинным Р & В перед новым выполнением S и т. д. Иными словами, Р остается истинным после каждой итерации, поэтому он называется инвариантом цикла.

lПредикат Р остается истинным и при завершении цикла, когда становится ложным В.

 

Оператор цикла for

lПусть S(X) — последовательность операторов, при выполнении которых используется значение переменной X (и оно не изменяется). Часто необходимо выполнить S(X) для всех возможных значений X, например для всех элементов заданного массива. Для этого используется оператор цикла for:

for X: тип do

S(X) end do;

lМножество значений указанного типа должно быть конечно. В качестве типа переменной X может быть указан анонимный подтип, например

for X: integer range 1..10 do

S(X) end do;

lДопустимы также сокращения вида

for X: do

S(X) end do;

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

lПоэтому приведенный оператор пол­ностью эквивалентен следующей последовательности:

lS(v1) S(v2) ... S(vn)

lгде v1,v2,…,vn - множество значений указанного типа.

lВо многих случаях важен порядок перечисления этих значений. Обычно полагается, что v’тип'SUCC(vi-1) для i=2,3,...,n (т. е. тип должен быть целым или перечислимым) и V1=тип' FIRST, Vn=тип' LAST.

Получение правила вывода

 

 

Правило вывода для цикла for

Пример доказательства программ с последовательным выполнением операторов

Рассмотрим программу

X:=X+2;

X:=X*2;

Докажем ее правильность

Для этого нужно доказать, что после выполнения программы X = (X+2)*2;

На начальное значение X не накладывается ограничений.

Значит

Предусловие программы P = {X=a};

Постусловие программы Q = {X=(a+2)*2}

Программа S = (X:=X+2;X:=X*2)

Обозначим

S1 = (X :=X+2)

S2 = (X :=X*2)

и воспользуемся правилом вывода для оператора последовательного выполнения

 

2

2 семестр

Объектно-ориентированное программирование

Основные вопросы

lОсновные понятия объектно-ориентированного программирования

lОбъектно-ориентированное программирование на C++

lДополнительные средства создания классов в С++

nМножественное наследование

nШаблоны классов

Поколения языков

lПервое поколение - языки с минимальными возможностями типизации

nПредоставляют лишь средства для описания переменных простых типов и массивов; никаких новых типов вводить нельзя.

nФортран, Алгол-60.

lВторое поколение – языки, предоставляющие программисту основные конструкторы типов: массивы, записи, объединения

nПЛ/1, Алгол-68, Паскаль, С

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

nВсе операции над типами данных предопределенные — определяемые языком, а не программистом.

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

lТретье поколение – языки, предоставляющие программисту средства определения абстрактных типов данных

nС++, C#, Java

nТипы понимаются как множества с операциями.

Понятие абстракции

lАбстракция — это суждение или представление о некотором объекте, которое содержит только свойства, являющиеся существенными в данном контексте.

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

lВнутри группы нужно изучать лишь те свойства, которые отличают ее отдельные элементы друг от друга. Это значительно упрощает элементы группы.

lПри необходимости детального изучения объектов нужно рассматривать их менее абстрактные представления.

lАбстракция — это эффективное средство против сложности программирования, поскольку оно позволяет программисту сосредоточиться на существенных свойствах объектов и проигнорировать менее важные свойства.

Определение абстрактного типа данных

lАбстрактный тип данных — это способ определения некоторого понятия в виде класса объектов с некоторыми свойствами и операциями.

lТак как свойства обычно выражаются в терминах операций, то абстрактный тип данных часто отождествляют с соответствующим множеством операций.

lНапример:

nопределение понятия стека в терминах операций " втолкнуть элемент в стек", " создать новый стек", "выдать верхний элемент" и т. д.

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

lПонятие абстрактного типа данных — это, по существу, аналог определения в математике, где новые понятия образуются из некоторых исходных объединением их в одно целое, имеющее новый статус, новое имя.

Объектно-ориентированное программирование

lИдея абстрактных типов данных является основой объектно-ориентированного программирования (ООП).

nОсновные принципы ООП были разработаны еще в языках Simula-67 и Smaltalk, но в то время не получили распространения из-за сложности освоения и низкой эффективности реализации.

nВ С++ концепции ООП реализованы эффективно и непротиворечиво, что явилось основой успешного распространения как языка, так и концепции ООП.

lООП – не просто набор новых средств, добавленных в язык

nНапример, на С++ можно писать программы и без использования ООП, и наоборот, можно написать объектную по сути программу на языке не содержащим специальных средств поддержки объектов.

lООП – новая парадигма программирования

Понятие парадигмы ООП

lТермин «парадигма» - означает набор теорий, стандартов и методов, которые совместно представляют собой способ организации знаний, способ видения мира.

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

lОбъектно-ориентированная программа строится в терминах объектов и их взаимосвязей.

Выбор степени абстракции

lВыбор степени абстракции определяется типом задачи, которую требуется решить.

lНе имеет смысла использовать сложные технологии для решения простых задач, но попытка «по-простому» справиться со сложной проблемой обречена на провал.

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

Абстрактные типы данных и ООП

lПеременные абстрактного типа данных называются «объектами» или «экземплярами» данного типа данных (применительно к С++ «экземплярами класса»).

lОбъекты взаимодействуют между собой посылая и получая сообщения.

lСообщение – это запрос на выполнения некоторого действия, содержащий необходимые параметры.

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

Основные свойства ООП

lИнкапсуляция

lНаследование

lПолиморфизм

Инкапсуляция

lИнкапсуляция – объединение данных с функциями их обработки в сочетании с сокрытием деталей реализации.

lИнкапсуляция заключается в том, что совокупность операций и объектов, определяющих тип данных, группируется в единую конструкцию — капсулу, причем доступ извне разрешается лишь к их спецификации, а реализация скрыта от пользователя, недоступна ему.

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

lПример инкапсуляции из жизни – автомобиль.

Наследование

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

lИмеющиеся свойства повторно не описываются, что сокращает объем программы.

lВыделение общих черт различных типов данных в один тип данных - предок является мощным механизмом абстракции.

lИерархия типов данных представляется в виде древовидной структуры в которой более общие типы располагаются ближе к корню, а более специализированные – на ветвях и листьях.

Пример иерархии типов данных

Полиморфизм

lПолиморфизм – свойство объекта принадлежать одновременно к нескольким типам данных иерархии.

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

Пример полиморфизма

Объявим переменную X типа «Аналитик».

Объект X является как экземпляром класса «Аналитик» так и экземпляром

классов «Сотрудник ФСБ», «Военнослужащий», «Гражданин»

Преимущества и недостатки ООП

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

lПроектирование объектно-ориентированной программы представляет собой сложную задачу, т. к. в процесс разработки программы добавляется важный этап – разработка иерархии классов.

lПлохо спроектированная иерархия приводит к созданию сложных и запутанных программ.

ООП в С++

lАбстрактные типы данных в С++ создаются с помощи синтаксической конструкции называемой «классом».

lКлассы позволяют программисту на С++ воспользоваться всеми свойствами ООП (инкапсуляция, наследование и полиморфизм)

Инкапсуляция в С++

lСпецификация класса в С++

class имя_класса{

модификатор_доступа:

[атрибуты]

[методы]

модификатор_доступа:

[атрибуты]

[методы]

…

};

lМодификаторы доступа

nprivate

npublic

nprotected

Пример использования класса для реализации понятия даты

class date{

private:

int month, day, year;

public:

void set(int, int, int);

void get(int*, int*, int*);

void next();

void print();

};

Простое наследование в C++

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

lВозможность обращения к элементам этого класса регулируется с помощью ключей доступа private, protected и public

class имя:

[private|protected|public] базовый_класс

{

тело класса

};

lПо умолчанию для классов используется ключ доступа private

lПростым называется наследование, при котором производный класс имеет одного родителя.

Доступ к элементам базового класса

Ключ доступа	Спецификатор в базовом классе	Доступ в производном классе
private	private protected public	нет
private private
protected	private protected public	нет protected protected
public	private protected public	нет protected public

Пример простого наследования

class date{

private:

int month, day, year;

public:

void set(int, int, int);

void get(int*, int*, int*);

void next();

void print();

};

…

date d;

d. day = 15; // Ошибка!

d. set(2006,1,1);

d. print();

date *pd = new date;

pd->set(2006,1,1);

pd->print();

delete pd;

Наследование и конструкторы

lКонструкторы не наследуются, поэтому производный класс должен иметь собственные конструкторы. Порядок вызова конструкторов определяется приведенными ниже правилами.

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

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

Пример вызовов конструкторов

class A {

public:

A();

X x;

…

};

class B : public A {

public:

B();

Y y;

…

};

class C : public B {

public:

C();

Z z;

…

};

class D : public B {

public:

D();

…

};

class X {

public:

X();

…

};

class Y {

public:

Y();

…

};

class Z {

public:

Z();

…

};

При создании экземпляра класса С вызов конструкторов будет происходить в следующей последовательности:

С с;

или

С *с = new c;

Наследование деструкторов

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

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

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

Последовательность вызовов деструкторов при вызове

delete c;

lЕсли в классе С определен деструктор, то выполняется его тело.

lВыполняется деструктор для объекта z.

lВыполняется деструктор для базового класса B

lЕсли в классе B определен деструктор, то выполняется его тело.

lВыполняется деструктор для объекта Y.

lВыполняется деструктор для базового класса A.

lЕсли в классе A определен деструктор, то выполняется его тело.

lВыполняется деструктор для объекта X.

Операция присваивания

lОперация присваивания не наследуется.

lТребуется явное определение операции присваивания в производном классе.

Пример использования операции присваивания (1)

class man{

private:

char *fio;

…

public:

const man & operator=(man &m){

if(fio!= NULL) delete fio;

if(m. fio!= NULL){

fio = new char[strlen(m. fio)+1];

strcpy(fio, m.fio);

}

else

fio = NULL;

return *this;

}

};

Пример использования операции присваивания (2)

class business_man: public man{

private:

unsigned long int many;

…

public:

const business_man & operator=(business_man &m){

many = m. many;

man::operator=(m);

return *this;

}

};

Полиморфизм и виртуальные методы

lРабота с объектами чаще всего производится через указатели.

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

lНапример:

class A {};

class B : public A{};

A *pointer;

pointer = new B;

lВ каждом из классов опишем по методу с одинаковым названием.

class A {

public:

void metod1();

…

};

class B : public A{

public:

void metod1();

…

};

Вызов методов объекта происходит в соответствии с типом указателя, а не фактическим типом объекта, на который он ссылается, поэтому при выполнении оператора, например,

A *pointer = new B;

pointer->metod1();

будет вызван метод класса A, а не класса B, поскольку ссылки на методы разрешаются во время компоновки программы.

Этот процесс называется ранним связыванием.

Чтобы вызвать метод класса B, можно использовать явное преобразование типа указателя:

((B *)pointer)->metod1();

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

Например:

l Функция, параметром которой является указатель на объект базового класса. На его место во время выполнения программы может быть передан указатель на любой производный класс.

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

lВ C++ реализован механизм позднего связывания, когда разрешение ссылок на метод происходит на этапе выполнения программы в зависимости от конкретного типа объекта, вызвавшего метод.