Основы алгоритмики. Библиотеки функций. Раздел 1. Общие правила

1.

А. Г. Епифанский
Основы Алгоритмики
Кафедра программного обеспечения систем
радиоэлектронной аппаратуры
Тема VIII
Библиотеки функций
Раздел 1. Общие правила
Семестр — первый

2.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Сегодня мы начинаем новую тему: библиотеки функций. В техгологии
программирования бибилиотеки функций играют центральную роль. Дело в
том, что большая часть каждой программы в значительной части состоит из
вызовов уже когда-то разработанных функций.
В математике большинство решений задач представляются в виде одной
или набора функций. При подстановке начальных или граничных значений
(условий) в качестве аргументов в функции получается числовое решение
задачи. В этом вся математика. Правила решения определенных задач —
алгоритмы последовательности вызова функций, решающих поставленную
задачу, - называются теоремами. Утверждается, что любая программа есть
доказанная теорема. Формулировка условия теоремы — техническое
задание для программы — совпадают, в результате применения программы
или теоремы получаем решение в численном представлении.
В приведенном выше определении программы, как и теоремы, ключевую
роль играет подстановка начальных или граничных условий в решение.

3.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Если решается не задача, а ищется решение уравнения, это другой тип
математических задач. И здесь аналогии между программами и теоремами
нет — отсутствует постановка задачи, и как результат, отсутствует числовое
решение. Решение одного уравнения или системы уравнений имеет
аналогию с описанием программы но не есть результат работы программы.
Конечно аналогии всегда страдают «натяжками», клторые скрываются в
деталях. Тем не менее, каждая программа состоит из вычисления
выражений, большую часть которых составляют вызовы функций. Что
представляют здесь функции? Процедуру вычисления! Обращение к
функции по имени с заданием аргументов сокращает запись выражения.
Таким образом, функции введены вматематике для сокращения записи
алгоритмов вычислений. Функция есть число — будучи подставленна в
выражение, она заменяет собой число, возможно еще не известное на
момент напизания выражения.

4.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Как видно из предыдущего текста, функция основа записи выражений. С
другой стороны, функция сама собой замещает выражение, точнее какую-то
часть выражения. Причем, если часто встречающееся выражение заменяется
просто некоторым именем, а числовые значения параметров этого
выражения параметрами вызова этого имени, то мы получаем функцию.
Часто говорят, что функция определяет зависимость между параметрами и
результатом. Это совершенно правильно и не противоречит приведенным
выше рассуждениям. Более того, функция остается быть числом, как только
становятся известны параметры функции.
В технологии программирования на языке C/C++, как, впрочем и на других я
языках, имеются функции без параметров, что не нарушает общности
приведенных рассуждений. Подобные функции в некоторых случаях
называются процедурами. Это сделано в тех языках, где отсутствует понятие
пустой список (пустой список параметров), например Fortran, Basic и др.
К вопроу о том, что возвращает функция без аргумента мы вернемся.

5.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Выше мы рассматривали функции, которые возвращают числовое значение.
А может ли функция возвращать другие значения? Да может.
Рассмотрим это вопрос подробнее. Как мы говорили ранее, в
программировании идет речь об эволюции объекта, причем объект может
быть часто представлен не просто числом, а некоторой структурой, т. е.
набором объектов разного типа. Кроме того, в качестве параметра в функцию
может быть передано значение (числовое) адреса некоторого объекта. В этом
случае этот объект может эволюционировать (состояние объекта может
изменяться). Как при этом будет возвращено новое состояние объекта.
В случае, когда вместо объекта в функцию передается адрес, его эволюция
происходит с экземпляром объекта, находящимся по переданному адресу.
Возвращаемое функцией значение может быть использовано для
вспомогательных целей, например для указания на то, был ли вызов
функции успешен, объект «занял» новое допустимое состояние или нет. Или,
поскольку в языке C/C++ процедуры и функции не различаются, вызов может
не сопровождаться никаким возвращаемым значением.

6.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Рассмотрим случай передачи функции значения в виде самой структуры.
Например имеем следующий код:
struct Try try;
int foo(struct Try);
Что в этом случае будет передано в функцию? В этом случе в стек будет
записан сам объект, имеющий структуру Try. Другими словами, в стеке
оказался новый экземпляр объекта try. Все операции с этим объектом, а
точнее, с параметрами структуры, будут проделаны над новым объектом.
При возврате из этой функции все изменения над новым экземпляром
объекта исчезнут, т. к. после возврата стек освобождается, а изменения
присутствовали только в стеке. Для сохранения изменений необходимо
другое определение (декларация) функции и другая форма вызова:
struct Try foo(struct Try);
try = foo(try);
Теперь все в порядке: новый объект будет передан в качестве значения
старому.

7.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Остановимся на совершенно экзотическом случае — процедуры без
параметров. Действительно, возможно ли это? Снова, если ограничивать
наше рассмотрение языком C/C++, то да. Другими словами возможна
функция типа
void foo(void);
Что подобная функция делает? Во-первых такая функция может
оперировать только с глобальными объектами, т. е. находящимися в
статической памяти. Новое состояние объекта будет записано на том же
месте. По этой причине, нет необходимости возвращать значение, если
завершение операции подразумевается всегда успешным, а условие
перехода от предыдущего в новое состояние неизменно.
Заметим, что здесь мы использовали новый тип void. Этот тип можно
интерпретировать как «ничто». Этот тип используется, когда:
а) тип неизвестен (это в случае передачи значения указателя) и
б) никакое значение не передается и не возвращается.

8.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Теперь мы знаем про передачу параметров при вызове функции
практически все. Осталось уточнить, а что при вызове функции можно НЕ
передавать, а когда нельзя. Знание этого правила чрезвычайно важно при
создании функций различной направленности.
Для выполнения своих внутренних потребностей в функции декларируются
локальные переменные или объекты. Все значения локальных объектов
утрачиваются безвозвратно при окончании работы функции, т. е. при
возврате управления вызывающему функцию коду.
Поэтому, для того, чтобы от работы функции остался след, необходимо либо
передать этот «след» через возвращаемое значение, либо через адрес
объекта. Как сказано выше, при передаче в функцию адреса объекта, новый
экземпляр не создается и все изменения сохраняются по адресу «старого».
Можно, конечно в функции создать новый объект вызовом функции malloc(.)
и вернуть его адрес. Этот тип вызова достаточно широко используется в
C/C++ для создания новых объектов.

9.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Нельзя создавать в функции новые объекты и без освобождения
занимаемой этим объектом памяти завершать работу функции, если только
адрес объекта не передается в качестве возвращаемого значения. В случае,
когда функция не возвращает адреса созданного объекта в вызывающий
код, память, занимаемая объектом останется занятой, но адрес объекта
будет утрачен.
Правда, есть существенная оговорка — если значение адреса не будет
присвоено глобальной переменной. В этом случае при новом вызове
функции этот адрес снова будет доступен.
Кроме того, с этим связан один очень интересный прием (trick) — таким образом
можно создать объект, доступ к которому будет известен только в пространстве
кода модуля. Для этого достаточно в модуле определить статическую переменную
в глобальной памяти. Очевидно всем функциям модуля доступ к таким образом
определенному объекту будет обеспечен, никакие другие программные
компоненты доступ к указанному объекту не получат иначе, как через вызов
функций этого модуля. Мы этим трюком вскоре воспользуемся при разработке
библиотеки функций разбора командной строки.

10.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Теперь перейдем к вопросу о создании библиотек функций. Библиотеки
функций это тот инструмент, который позволяет воспользоваться золотым
правилом программирования: «один раз пишешь, пользуешься везде» (write
once use anywhere).
Но, к большому сожалению, не все функции могут быть помещены в
библиотеку. Для того, чтобы функции из библиотеки можно было, как
написано, «использовать везде», необходимо соблюдение ряда условий.
Следует заметить, что в библиотеку функций можно вставить любые
функции. Но каков будет результат зависит от того, на сколько функция
универсальна. Это означает, что функцию или функции, выполняя какие
либо действия не зависят от прикладной задачи.
Вообще говоря, каждая функция зависит от той задачи, для решения
которой она создавалась. Но, если, например, несколько функций
выполняют команды ввода/вывода, то их можно использовать в любой
задаче, где требуется их функциональность.

11.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Действительно, библиотеки функций ввода/вывода появились одними их
первых. Правда, с начала были разработаны библиотеки стандартных
математических функций. Это было еще на «заре» компьютеризации. В те
«легендарные» времена ЭВМ были медленными с небольшими объемами
памяти. Поэтому создатели компьютеров были озабочены потребительскими
свойствами своих изделий и уделяли большое внимание наличию библиотек
общего пользования, которые занимали как можно мало памяти и при этом
были эффективны в использовании — быстро вычисляли и имели
достаточную точность результата.
Вообще говоря, для математических функций точность результата —
решающий фактор.
Очевидно, что стандартные математические функции при их вызове требуют,
как правило один или несколько параметров, как, например, atan2(.,.). Эта
функция вычисляет арктангенс от отношения двух аргументов (см. man).

12.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Но вернемся к функциям ввода/вывода.
Для указания «направления» ввода/вывода требуется определить канал
обмена данными. Для блочных устройств достаточно указать идентификатор
устройства, для потоковых устройств требуется создать структуру, в которой
отображается состояние канала.
Для блочных устройств в качестве идентификатора используется тип
short int.
Потоковые каналы управляются структурой FILE.
В обоих случаях требуются функции открытия канала, возвращающие
идентификатор канала или адрес структуры управления каналом. Канал
открывается функцией open(…) или fopen(…). Сейчас не будем уточнять
параметры, нас интересует общие правила управления.
Итак в случае блочного канала функция открытия возвращает число, для
потокового — адрес структуры. Очевидно, что в обоих случаях функции
возвращают численное значение.

13.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Как видим, все что мы говорили о значениях, возвращаемых функциями,
справедливо для функций ввода/вывода.
В языке C/C++ программа, запускаемая из командной строки имеет открытыми
три потоковых канала управляемые структурами типа FILE и определены
указатели на них: FILE * stdin, * stdout, * stderr;
которые могут быть закрыты только перенаправлением их на «нуль
устройство»: /dev/null. Если попытаться закрыть какой либо из этих каналов, то
он будет открыт снова.
Для выполнения различных функций ввода/вывода через каналы необходимо
передать в функцию идентификатор или адрес структуры управления.
Подчеркнем, что функция открытия потокового канала возвращает адрес
структуры управления, а функции исполнения операций ввода/вывода
принимают в качестве параметра этот адрес. Функция fclose(FILE *) освобождает
память занимавшуюся соответствующий структурой управления.

14.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
Выше мы рассмотрели организацию использования функций. На примере
вызова функций ввода/вывода смогли понять правила передачи параметра,
связанного с файлом ввода/вывода. Как правило, параметр вызова,
идентифицирующий канал, является первым параметром. Часть функций
работы с отдельными символами или строками имеют параметр,
идентифицирующий канал, последним параметром.
Студентам предлагается самим рассмотреть страницы утилиты man(3)
для уточнения последовательности и количества параметров вызова в
различных функциях управления потоковыми каналами.
Еще раз отметим, что не смотря на то, что функции ввода/вывода
взаимодействуют через посредство связи с ядром, идентификатор канала,
связанный с файлом им передается в параметрах.
И второе. Вся информация, которая необходима для отображения состояния
канала, находится в памяти пользовательской программы. Функция никаких
значений, необходимых для нового (повторного) вызова не содержит.

15.

Основы Алгоритмики
Тема VIII — Библиотеки функций
1. общие правила
К следующей лекции студентам необходимо самостоятельно ознакомиться
(или повторить знакомство) с разделом учебника, где рассматриваются
правила определения (выделения память) под переменные и объекты. В
частности вспомнить что значит глобальная, локальная и статическая
переменные и, соответственно, память.
В следующем разделе данной темы мы будем широко использовать
указанные выше термины, применительно к переменным и объектам.
Дальнейший разбор темы мы будем проводить на примере решения
конкретной задачи — составление библиотеки функций анализа командной
строки и использовании в программе полученной информации. Вам
предстоит построить такую библиотеку функций, а затем вы будете в
следующих заданиях применять эти функции для управления вашими
программами.

16.

Основы Алгоритмики
Тема Тема
VII - Алгоритм
VIII — Библиотеки
построения
функций
программ
1. общие правила
СПАСИБО
ЗА ВНИМАНИЕ
ПРОШУ ЗАДАВАТЬ ВОПРОСЫ