Другие элементы меню 5 страница

Семантика присваивания рассматривалась в лекциях 3, 6, 7.

Каково следствие семантики вызова по значению? Если вы забыли указать ключевое слово ref или out для аргумента, фактически являющегося выходным, то к нему будет применяться вызов по значению. Даже если в теле метода происходит изменение значения этого аргумента, то оно действует только на время выполнения тела метода. Как только метод заканчивает свою работу (завершается блок) все локальные переменные (в том числе созданные для замены формальных аргументов) оканчивают свое существование, так что изменения не затронут фактических аргументов и они сохранят свое значение, бывшее у них до вызова. Отсюда вывод: все выходные аргументы, значения которых предполагается изменить в процессе работы, должны иметь ключевое слово ref или out. Еще один важный вывод: Ключевым словом ref полезно иногда снабжать и входные аргументы. Если известно, что фактический аргумент будет всегда представлен именем, а не сложным выражением, то в целях экономии памяти разумно для таких аргументов применять семантику вызова по ссылке. В этом случае не будет создаваться копия аргумента, это экономит память и время, что может быть важно при работе со сложными структурами.

Говоря о семантике вызова по ссылке и по значению, следует сделать одно важное уточнение. В объектном программировании, каковым является и программирование на C#, основную роль играют ссылочные типы – мы работаем с классами и объектами. Когда методу передается объект ссылочного типа, то все поля этого объекта могут в методе меняться самым беззастенчивым образом. И это несмотря на то, что объект формально не является выходным, не имеет ключевых слов ref или out, использует семантику вызова по значению. Сама ссылка на объект при этом, как и положено, остается неизменной, но состояние объекта, его поля могут полностью обновиться. Такая ситуация типична и представляет один из основных способов изменения состояния объектов. Именно поэтому ref или out не часто появляются при описании аргументов метода.

Что нужно знать о методах?

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

Почему у методов мало аргументов?

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

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

Поля класса или функции без аргументов?

Поля хранят информацию о состоянии объектов класса. Состояние объекта динамически изменяется в ходе вычислений – обновляются значения полей. Часто возникающая дилемма при проектировании класса: что лучше – создать ли поле, хранящее информацию, или создать функцию без аргументов, вычисляющую значение этого поля всякий раз, когда это значение понадобится. Решение дилеммы – это вечный для программистов выбор между памятью и временем, Если предпочесть поле, то это приводит к дополнительным расходам памяти. Они могут быть значительными, когда создается большое число объектов, ведь поле должен иметь каждый объект. Если предпочесть функцию, то это потребует временных затрат на вычисление значения, они могут быть значительными в сравнении с выбором текущего значения поля.

Если бы синтаксис описания метода допускал отсутствие скобок у функции (метода), в случае, когда список аргументов отсутствует, то клиент класса мог бы и не знать, обращается он к полю или к методу. Такой синтаксис принят, например, в языке Eiffel. Преимущество такого подхода в том, что изменение реализации никак не сказывается на клиентах класса. В языке C# это не так. Когда мы хотим получить длину строки, то пишем s.Length, точно зная, что Length – это поле, а не метод класса string. Если бы по каким-либо причинам разработчики класса string решили изменить реализацию и заменить поле Length соответствующей функцией, то ее вызов имел бы вид s.Length().

Пример: Две версии класса Account

Продемонстрируем рассмотренные выше вопросы на примере проектирования классов Account и Account1, описывающих такую абстракцию данных, как банковский счет. Определим на этих данных две основные операции – занесение денег на счет и снятие денег. В первом варианте – классе Account – будем активно использовать поля класса. Помимо двух основных полей credit и debit, хранящих приход и расход счета, введем поле balance, задающее текущее состояние счета и два поля, связанных с последней выполняемой операцией. Поле sum будет хранить сумму денег текущей операции, а поле result – результат выполнения операции. Полей у класса много, как следствие это приведет к тому, что у методов класса аргументов будет немного. Вот описание нашего класса:

/// <summary>

/// Класс Account определяет банковский счет.

/// простейший вариант с возможностью трех операций:

/// положить деньги на счет, снять со счета, узнать баланс.

/// Вариант с полями

/// </summary>

public class Account

{

//закрытые поля класса

int debit=0, credit=0, balance =0;

int sum =0, result=0;

/// <summary>

/// Зачисление на счет с проверкой

/// </summary>

/// <param name="sum"> зачисляемая сумма </param>

public void putMoney(int sum)

{

this. sum = sum;

if (sum >0)

{

credit += sum; balance = credit - debit; result =1;

}

else result = -1;

Mes();

}// putMoney

/// <summary>

/// Снятие со счета с проверкой

/// </summary>

/// <param name="sum"> снимаемая сумма </param>

public void getMoney(int sum)

{

this. sum = sum;

if (sum <= balance)

{

debit += sum; balance = credit - debit; result =2;

}

else result = -2;

Mes();

}// getMoney

/// <summary>

/// Уведомление о выполнении операции

/// </summary>

void Mes()

{

switch (result)

{

case 1:

Console.WriteLine("Операция зачисления денег прошла успешно!");

Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",

sum,balance);

break;

case 2:

Console.WriteLine("Операция снятия денег прошла успешно!");

Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",

sum,balance);

break;

case -1:

Console.WriteLine("Операция зачисления денег не выполнена!");

Console.WriteLine("Сумма должна быть больше нуля!");

Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",

sum,balance);

break;

case -2:

Console.WriteLine("Операция снятия денег не выполнена!");

Console.WriteLine("Сумма должна быть не больше баланса!");

Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",

sum,balance);

break;

default:

Console.WriteLine("Неизвестная операция!");

break;

}

}

}// Account

Как можно видеть, только у методов getMoney и putMoney имеется один входной аргумент. Это тот аргумент, который нужен по сути дела, поскольку только клиент может решить какую сумму он хочет снять или положить на счет. Других аргументов у методов класса нет, вся информация передается через поля класса. Уменьшение числа аргументов приводит к повышению эффективности работы с методами, так как исчезают затраты на передачу фактических аргументов. Но за все надо платить. В данном случае усложняются сами операции работы со вкладом, поскольку нужно в момент выполнения операции обновлять значения многих полей класса. Закрытый метод Mes вызывается после выполнения каждой операции, сообщая о том, как прошла операция и информируя клиента о текущем состоянии его баланса.

А теперь спроектируем аналогичный класс Account1, отличающийся только тем, что у него будет меньше полей. Вместо поля balance в классе появится соответствующая функция с этим же именем, вместо полей sum и resultпоявятся аргументы у методов, обеспечивающие необходимую передачу информации. Вот как выглядит этот класс:

/// <summary>

/// Класс Account1 определяет банковский счет.

/// Вариант с аргументами и функциями

/// </summary>

public class Account1

{

//закрытые поля класса

int debit=0, credit=0;

/// <summary>

/// Зачисление на счет с проверкой

/// </summary>

/// <param name="sum"> зачисляемая сумма </param>

public void putMoney(int sum)

{

int res =1;

if (sum >0)credit += sum;

else res = -1;

Mes(res,sum);

}// putMoney

/// <summary>

/// Снятие со счета с проверкой

/// </summary>

/// <param name="sum"> снимаемая сумма </param>

public void getMoney(int sum)

{

int res=2;

if (sum <= balance())debit += sum;

else res = -2;

balance();

Mes(res, sum);

}// getMoney

/// <summary>

/// вычисление баланса

/// </summary>

/// <returns> текущий баланс </returns>

int balance()

{

return (credit - debit);

}

/// <summary>

/// Уведомление о выполнении операции

/// </summary>

void Mes(int result, int sum)

{

switch (result)

{

case 1:

Console.WriteLine("Операция зачисления денег прошла успешно!");

Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",

sum,balance());

break;

case 2:

Console.WriteLine("Операция снятия денег прошла успешно!");

Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",

sum,balance());

break;

case -1:

Console.WriteLine("Операция зачисления денег не выполнена!");

Console.WriteLine("Сумма должна быть больше нуля!");

Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",

sum,balance());

break;

case -2:

Console.WriteLine("Операция снятия денег не выполнена!");

Console.WriteLine("Сумма должна быть не больше баланса!");

Console.WriteLine("Cумма={0}, Ваш текущий баланс={1}",

sum,balance());

break;

default:

Console.WriteLine("Неизвестная операция!");

break;

}

}

}// Account1

Сравнивая этот класс с классом Account, можно видеть, что число полей сократилось с 5 до двух, упростились основные методы getMoney и putMoney. Но в качестве платы у класса появился дополнительный метод balance(), многократно вызываемый, у метода Mes теперь появились два аргумента. Какой класс лучше? Однозначно сказать нельзя, все зависит от контекста, приоритетов, заданных при создании конкретной системы.

Приведу процедуру класса Testing, тестирующую работу с классами Account и Account1:

public void TestAccounts()

{

Account myAccount = new Account();

myAccount.putMoney(6000);

myAccount.getMoney(2500);

myAccount.putMoney(1000);

myAccount.getMoney(4000);

myAccount.getMoney(1000);

//Аналогичная работа с классом Account1

Console.WriteLine("Новый класс и новый счет!");

Account1 myAccount1 = new Account1();

myAccount1.putMoney(6000);

myAccount1.getMoney(2500);

myAccount1.putMoney(1000);

myAccount1.getMoney(4000);

myAccount1.getMoney(1000);

}

На рис. 9.1 показаны результаты работы этой процедуры.

Рис. 9.1. Тестирование классов Account и Account1

Функции с побочным эффектом

Функция называется функцией с побочным эффектом, если помимо результата, вычисляемого функцией и возвращаемого ей в операторе return, она имеет выходные аргументы с ключевыми словами ref и out. В языках C/C++ функции с побочным эффектом применяются сплошь и рядом. Хороший стиль ОО-программирования не рекомендует использование таких функций. Выражения, использующие функции с побочным эффектом, могут потерять свои прекрасные свойства, присущие им в математике. Если f(a) – функция с побочным эффектом, то a+f(a) может быть не равно f(a) +a, так что теряется коммутативность операции сложения.

Примером такой функции является функция f, приведенная выше. Вот тест, демонстрирующий потерю коммутативности сложения при работе с этой функцией:

/// <summary>

/// тестирование побочного эффекта

/// </summary>

public void TestSideEffect()

{

int a = 0, b=0, c=0;

a =1; b = a + f(ref a);

a =1; c = f(ref a)+ a;

Console.WriteLine("a={0}, b={1}, c={2}",a,b,c);

}

На рис. 9.2 показаны результаты работы этого метода.

Рис. 9.2. Демонстрация вызова функции с побочным эффектом

Обратите внимание на полезность указания ключевого слова ref в момент вызова. Его появление хоть как-то оправдывает некоммутативность сложения.

Методы. Перегрузка

Должно ли быть уникальным имя метода в классе? Нет, это не требуется. Более того, проектирование методов с одним и тем же именем является частью стиля программирования на С++ и стиля C#. Существование в классе методов с одним и тем же именем называется перегрузкой, а сами одноименные методы называются перегруженными.

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

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

О перегрузке операций при определении класса будет подробно сказано в лекции???, посвященной классам.

Перегрузка требует уточнения семантики вызова метода. Когда встречается вызов не перегруженного метода, то имя метода в вызове однозначно определяет, тело какого метода должно выполняться в точке вызова. Когда же метод перегружен, то знания имени недостаточно – оно не уникально. Уникальной характеристикой перегруженных методов является их сигнатура. Перегруженные методы, имея одинаковое имя, должны отличаться либо числом аргументов, либо их типами, либо ключевыми словами (заметьте, с точки зрения сигнатуры ключевые слова ref и out не отличаются). Уникальность сигнатуры позволяет вызвать требуемый перегруженный метод.

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

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

Насколько полезна перегрузка методов? Здесь нет экономии кода, поскольку каждую реализацию нужно задавать явно, нет выигрыша по времени, скорее требуются определенные затраты на поиск подходящей реализации, который может приводить к конфликтам, к счастью обнаруживаемых на этапе компиляции. В нашем примере вполне разумно иметь четыре метода с разными именами, и осознанно вызывать метод, применимый к данным аргументам. Все-таки есть ситуации, где перегрузка полезна, недаром она широко используется при построении библиотеки FCL. Возьмем, например класс Convert, у которого 16 методов с разными именами, зависящими от целевого типа преобразования. Каждый из этих 16 методов перегружен и в свою очередь имеет 16 реализаций в зависимости от типа источника. Согласитесь, что-то неразумное было бы иметь в классе Convert 256 методов вместо 16 перегруженных методов. Впрочем, также неразумно было бы иметь один перегруженный метод, имеющий 256 реализаций. Перегрузка – это инструмент, которым следует пользоваться с осторожностью и обоснованно.

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

/// <summary>

/// Тестирование перегруженных методов A()

/// </summary>

public void TestLoadMethods()

{

long u=0; double v =0;

A(out u, 7); A(out v, 7.5);

Console.WriteLine ("u= {0}, v= {1}", u,v);

A(out v,7);

Console.WriteLine("v= {0}",v);

A(out u, 7,11,13);

A(out v, 7.5, Math.Sin(11.5)+Math.Cos(13.5), 15.5);

Console.WriteLine ("u= {0}, v= {1}", u,v);

}// TestLoadMethods

На рис. 9.3 показаны результаты этого тестирования.

Рис. 9.3. Тестирование перегрузки методов

Вариант 1

22. Метод можно описать на уровне:

q класса;

q пространства имен;

q проекта;

q решения.

23. Отметьте истинные высказывания:

q только функции являются методами класса;

q число формальных и фактических аргументов метода должно совпадать;

q если формальный аргумент объявлен с ключевым словом ref, то в теле метода ему должно присваиваться значение;

q перегруженными называются методы с большим числом аргументов.

q функции с побочным эффектом в языке C# не допускаются.

24. В каких вызовах возникнет ошибка, если задано описание
int x=1; int z=0; int p(int x, out int y){…}

q x=p(77,z);

q x=p(77+z, z);

q p(77+z, z);

q x= p(77, 77+z);

Вариант 2

25. Чем отличаются процедуры от функций:

q оператор return можно задавать только в функциях;

q функция не может возвращать значение void;

q функцию нельзя вызывать как оператор;

q процедуру нельзя вызывать в выражениях.

26. Отметьте истинные высказывания:

q только процедуры являются методами класса;

q формальный аргумент метода может быть выражением;

q ключевые слова ref и out являются частью сигнатуры метода.

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

27. Функция с побочным эффектом:

q возвращает значение void;

q записывает результат в файл или печатает его;

q изменяет значения входных аргументов;

q имеет выходные аргументы с ключевыми словами ref или out;

q вызывается как оператор.

Вариант 3

25. При вызове аргумента «по значению»:

q формальный аргумент должен снабжаться ключевым словом ref;

q создается копия фактического аргумента;

q значение фактического аргумента не меняется в результате вызова;

q фактический аргумент не может быть именем;

q для формального аргумента задается его значение.

26. Отметьте истинные высказывания:

q только процедуры и функции с атрибутом public являются методами класса;

q фактический аргумент метода может быть выражением;

q если формальный аргумент объявлен с ключевым словом out, то в теле метода ему должно присваиваться значение;

q сигнатуры перегруженных методов должны совпадать.

27. Какие высказывания верны для полей класса:

q если поле статическое, то его можно использовать только в статическом методе;

q если метод статический, то он может использовать только статические поля;

q поля класса используются для передачи информации в методы класса;

q поле класса всегда можно заменить функцией без аргументов;

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

Лекция 10. Корректность методов. Рекурсия

Корректность метода. Спецификации. Триады Хоара. Предусловие метода. Постусловие метода. Корректность метода по отношению к предусловию и постусловию. Частичная корректность. Завершаемость. Полная корректность. Инвариант цикла. Вариант цикла. Подходящий инвариант. Корректность циклов. Рекурсия. Прямая и косвенная рекурсия. Стратегия «разделяй и властвуй». Сложность рекурсивных алгоритмов. Задача «Ханойские башни». Быстрая сортировка Хоара.

Ключевые слова: корректность; частичная корректность; полная корректность; доказательство корректности; инвариант; вариант цикла; корректность цикла; рекурсия; рекурсивный метод.

Корректность методов

Написать метод, задающий ту или иную функциональность, нетрудно. Это может сделать каждый. Значительно сложнее написать метод, корректно решающий поставленную задачу. Корректность метода – это не внутреннее понятие, подлежащее определению в терминах самого метода. Корректность определяется по отношению к внешним спецификациям метода. Если нет спецификаций, то говорить о корректности некорректно.

Спецификации можно задавать по-разному. Мы определим их здесь через понятия предусловий и постусловий метода, используя символику триад Xoара, введенных Чарльзом Энтони Хоаром – выдающимся программистом и ученым, одну из знаменитых программ которого приведем чуть позже в этой лекции.

Пусть P(x,z) – программа P с входными аргументами x и выходными z. Пусть Q(y) – некоторое логическое условие (предикат) над переменными программы y. Язык для записи предикатов Q(y) формализовать не будем. Отметим только, что он может быть шире языка, на котором записываются условия в программах и включать, например, кванторы. Предусловием программы P(x,z) будем называть предикат Pre(x), заданный на входах программы. Постусловием программы P(x,z) будем называть предикат Post(x,z), связывающий входы и выходы программы. Для простоты будем полагать, что программа P не изменяет своих входов x в процессе своей работы. Теперь несколько определений:

Определение 1 (частичной корректности): Программа P(x,z) корректна (частично или условно) по отношению к предусловию Pre(x) и постусловию Post(x,z), если из истинности предиката Pre(x) следует, что для программы P(x,z), запущенной на входе x, гарантируется выполнение предиката Post(x,z) при условии завершения программы.

Условие частичной корректности записывается в виде триады Хоара, связывающей программу с ее предусловием и постусловием:

[ Pre(x) ]P(x,z)[ Post(x,z) ]

Определение 2 (полной корректности): Программа P(x,z) корректна (полностью или тотально) по отношению к предусловию Pre(x) и постусловию Post(x,z), если из истинности предиката Pre(x) следует, что для программы P(x,z), запущенной на входе x, гарантируется ее завершение и выполнение предиката Post(x,z).

Условие полной корректности записывается в виде триады Хоара, связывающей программу с ее предусловием и постусловием:

{ Pre(x) }P(x,z){ Post(x,z) }

Доказательство полной корректности обычно состоит из двух независимых этапов – доказательства частичной корректности и доказательства завершаемости программы. Заметьте, полностью корректная программа, запущенная на входе, не удовлетворяющему ее предусловию, вправе зацикливаться, вправе возвращать любой результат. Любая программа корректна по отношению к предусловию, заданному тождественно ложным предикатом False. Любая завершающаяся программа корректна по отношению к постусловию, заданному тождественно истинным предикатом True.

Корректная программа говорит своим клиентам, если вы хотите вызвать меня и ждете гарантии выполнения постусловия после моего завершения, то будьте добры гарантировать выполнение предусловия на входе. Задание предусловий и постусловий методов – это такая же важная часть работы программиста, как и написание самого метода. На языке C# пред и постусловия обычно задаются в теге summary, предшествующему методу, и являются частью XML-отчета. К сожалению, технология работы в Visual Studio не предусматривает возможности автоматической проверки предусловия перед вызовом метода и проверки постусловия после его завершения с выбрасыванием исключений в случае их невыполнения. Программисты, для которых требование корректности является важнейшим условием качества их работы, сами встраивают такую проверку в свои программы. Как правило, такая проверка обязательна на этапе отладки и может быть отключена в готовой системе, в корректности которой программист уверен. Проверку предусловий важно оставлять и в готовой системе, поскольку истинность предусловий должен гарантировать не разработчик метода, а клиент, вызывающий метод. Клиентам свойственно ошибаться и вызывать метод в неподходящих условиях.

Формальное доказательство корректности метода – задача ничуть не проще, чем написание корректной программы. Но вот парадокс. Чем сложнее метод, его алгоритм, а следовательно и само доказательство, тем важнее использовать в процессе разработки метода понятия предусловий и постусловий, понятия инвариантов циклов. Рассмотрение их параллельно с разработкой метода может существенно облегчить построение корректного метода. Этот подход будет продемонстрирован в этой лекции при рассмотрении метода QuickSort – быстрой сортировки массива.

Инварианты и варианты цикла

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

Init(x,z); while(B)S(x,z);

Здесь B – условие цикла while, S – его тело, а Init – группа предшествующих операторов, задающая инициализацию цикла. Реально ни один цикл не обходится без инициализирующей части. Синтаксически было бы правильно, чтобы Init являлся бы формальной частью оператора цикла. В операторе for эта частично сделано – инициализация счетчиков является частью цикла.

Дата добавления: 2014-12-25