Начало
Учебные материалы
Абстракция и разработка программ
Декомпозиция и абстракция Методы абстрагирования Виды абстракций Абстрактный тип данных Классификация АТД
Виды абстракций
* процедурная абстракция, добавляющая новую операцию в виртуальную машину (язык программирования);
* абстракция данных, добавляющая новый тип данных;
* абстракция итерации, позволяющая обрабатывать элементы некоторого набора данных
без привязки к последовательности обработки.
--
Процедура выполняет преобразование входных аргументов в выходные. Для написания программы,
использующей процедурную абстракцию, программисту нужно знать только её поведение, а не подробности её реализации.
Если реализация такой абстракции изменяется, но ее параметры и спецификация при этом остается прежней, то эти изменения не повлияют
на остальную часть программы.
--
Процедуры могут быть частичными и общими.
Частичные процедуры не так безопасны, как общие, поскольку они требуют от пользователя выполнения
требований. Если эти требования не удовлетворены, то поведение процедуры становится неопределенным (undefined behavoir, UB),
что может привести к неверной работе программы.
С другой стороны, частичные процедуры могут оказаться более эффективными в реализации, чем общие.
--
*Устойчивая программа* - это программа, которая ведет себя корректно даже в случае ошибки.
Метод, гарантирующий устойчивость, заключается в использовании процедур, заданных на всей области определения.
Если процедура не способна выполнить действие для некоторого аргумента, она должна
оповестить вызывающую программу об ошибке, а та может что-то предпринять, чтобы избежать последствий ошибки.
Проверка входных параметров на принадлежность допустимому подмножеству требует времени, поэтому есть искушение не делать
эти проверки или выполнять их только при отладке и выключать в рабочей системе.
--
Для оповещения об ошибке обычно используются исключительные ситуации, которые являются вариантом результата процедуры,
поэтому раздел спецификаций "действие" должен описывать, какие исключительные ситуации возвращаются и по какой причине.
Некоторые фреймворки выводят не перехваченные исключения пользователю. Этого следует избегать, так как исключения --
это механизм взаимодействия подпрограмм, а не программы с пользователем.
--
Выбор правильных структур данных играет решающую роль для создания эффективной программы.
При отсутствии абстракций данных все структуры данных должны быть определены до начала реализации.
Но в этот момент, однако, структуры данных обычно еще не вполне ясны.
Следовательно, в выбранных структурах может отсутствовать необходимая информация или поведение или необходимые операции
могут быть реализованы неэффективно.
Вместо того чтобы явно задавать структуры данных, мы вводим абстрактный тип, перечисляя возможные операциями над ним, и
реализуем модули в терминах этого абстрактного типа. Когда способы использования данных станут для нас вполне понятными, мы сможем принять решение же относительно реализации этого типа.
--
Спецификации типа должна включать раздел, где тип описывается как целое, и раздел, содержащий спецификацию всех операций.
Важным свойством типа как целого является возможность изменения объекта.
Обычно неизменяемыми являются математические объекты, а изменяемыми -- модели реальных.
Неизменяемые типы более надежны, и для них проще выполнять распараллеливание вычислений, но чаще нужна сборка мусора. Изменяемые типы более эффективны (при использовании локально, в одном потоке).
Пример: String и StringBuilder в Java. Неизменяемые объекты можно включать как часть в другой объект, и он может являться частью нескольких объектов. Изменяемые объекты нужно копировать для включения в другие объекты, чтобы не допустить *структурной зависимости*.
--
Тип является полным, если он обеспечивает достаточно операций для того, чтобы все требуемые действия
могли быть проделаны с приемлемой эффективностью.
При реализации необходимо определить инвариант представления -- условие, которое должно оставаться истинным для
всех объектов этого типа. Инвариант представления должен сохраняться при выполнении всех операций.
Абстракция итерации в C++ реализуется как "синтаксический сахар" над оператором ``for``: конструкция `bb"for"("объявление переменной:выражение") \ "оператор"` превращается в
```c++
{
auto &&r=выражение;
for(auto b=begin(r), e=end(r); b!=e; ++b)
{ объявление переменной=*b;
оператор
}
}
```
При этом для типа *выражения* должны определены функции или методы ``begin`` и ``end``, возвращающие *итераторы*, для которых определены операции ``!=``, ``=``, ``++`` и ``*``.
В языке Lua используется более простой способ: конструкция `bb"for" \ v_1,...,v_n \ bb"in" \ "выражение" \ bb"do" \ "тело цикла" \ bb"end"` эквивалентна
```lua
fun,state,init,close=выражение
v1,...,vn=fun(state,init)
while v1 do
тело цикла
v1,...,vn=fun(state,v1)
end
if close then
close(v1)
end
```
`"выражение"` должно возвращать кортеж, состоящий как минимум из функции и состояния обхода. Функция получает два аргумента -- состояние и текущее или начальное значение индекса -- и возвращает очередное значение после `v_1` или `"nil"`, если набор закончился.
В "C++ syntax 2" ``for`` может быть применен только к набору и выглядит вызов функции ``ranges::for_each``, которой указывается в качестве второго аргумента анонимная функция: `bb"for" \ "выражение" \ bb"do" ( "параметр" ) \ "оператор"`, и может быть реализован как [внутренний итератор](11642-2.html), но транслируется в оператор for С++ по коллекции.
В языке CLU (один из предшественников C++, разработан Б.Лисков) итерация реализуется через сопрограммы (coroutine), которые в отличии от обычных функций могут последовательно возвращать несколько значений. Аналогичным образом сопрограммы могут быть использованы в Python. В С++23 такая возможность также была добавлена, но из-за преобразования в итератор менее эффективен, чем в CLU:
```c++
#include <generator>
#include <vector>
#include <print>
std::generator<std::vector<int>> permutation(int n) {
std::vector<int> v;
if(n<=0) co_return v;
for(auto v2:permutation(n-1)) {
for(int i=0;i<n;++i)
{ v=v2;
v.insert(v.begin()+i,n);
co_yield v;
}
}
}
int main() {
for(auto v: permutation(5))
std::println("{}",v);
}
```
