Основы программирования — Осенний семестр; Михалкович С.С.; 2008; IV

Подпрограммы

Вспомогательные алгоритмы

Вспомогательный алгоритм — это алгоритм, который используется для реализации другого алгоритма.

Вспомогательные алгоритмы имеют:

• имя
• список параметров

некоторые параметры являются входными, а некоторые — выходными

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

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

• процедуры
• функции

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

Процедуры

Пример.
Даны 3 пары положительных чисел.
Найти их среднее арифметическое и среднее геометрическое.

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

procedure CalcSrASrG(a, b: real; var SA, SG: real); 
begin
  SA := (a + b) / 2;
  SG := sqrt(a * b);
end;

Строка

procedure CalcSrASrG(a, b: real; var SA, SG: real);

называется заголовком процедуры.

Теперь можем многократно использовать описанную процедуру в основной программе:

begin   //основной программы
  for var i := 1 to 3 do
  begin
    var a, b: real;
    readln(a, b);
    var SA, SG: real;
    CalcSrASrG(a, b, SA, SG);
    writeln(SA, '|', SG);
  end;
end.

Оператор

CalcSrASrG(a, b, SA, SG);

называется оператором вызова процедуры.

<xh4> Синтаксис описания процедуры </xh4>

procedure <имя> [( <список формальных параметров> )];
<раздел описаний>
begin
  <операторы и внутриблочные переменные>
end;

<список формальных пар-ов> ::= <секция ф.п.> | <секция ф.п.>; <список ф.п.>
<секция ф.п.> ::= [var] <список имен>: <тип>

Замечание. Pascal допускает внутренне описание подпрограмм (вложенность подпрограмм)

<xh4> Синтаксис вызова процедуры </xh4>

<имя процедуры> [( [<список фактических параметров>] )]

<список фактических пар-ов> ::= <список выражений>
(<список выражений> ::= <выражение>{, <выражение>})

<xh4> Семантика вызова процедуры </xh4>

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

Входно-выходные параметры

Параметр x называется входно-выходным, если его значение необходимо в начале алгоритма, оно модифицируется алгоритмом и возвращается в вызывающую программу.
Входно-выходные параметры описываются с ключевым словом var, как и выходные.

Пример 1. Увеличение значения переменной на заданное число.

procedure Inc(var x: integer; n: integer);
begin
  x += n;
end;

Вызов процедуры:

var x: integer;   //неинициализированная переменная
x := 1;           //x инициализировано
Inc(x, 2);

Пример 2. Перемена местами значений двух переменных.

procedure Swap(var x, y: integer);
begin
  var v := x;
  x := y;
  y := v;
end;

begin
  var a := 5;
  var b := 3;
  Swap(a ,b);
end.

Функции

Функции являются другой разновидностью подпрограмм. Это подпрограмма, возвращающая одно значение особым образом так, что ее вызов можно использовать в выражении.
Точнее, — вызов процедуры является оператором, а вызов функции — выражением.

Пример. Функция sgn(x) — знак числа

function Sign(x: real): integer;
begin
  if x > 0 then
    Result := 1
  else if x < 0 then
    Result := -1
  else
    Result := 0;
end;

Строка

function Sign(x: real): integer;

называется заголовком функции, а integer — это тип возвращаемого значения.

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

Пример неправильной(!!!) функции.

function f(x: integer): integer;
begin
  if x > 0 then
    Result := 777;
end;

begin
  writeln(f(0));
end.

Выведется непредсказуемое значение, находящееся в этот момент в памяти, т.к. по ветке

x = 0 

переменная Result не инициализируется.

Пример. Считывание значения с клавиатуры.

function ReadInteger: integer;
begin
  read(Result);
end;

Сравнение использования процедуры и функции

процедура           функция
var x: integer;     var x := ReadInteger();
read(x);

Пример. Сумма первых N натуральных чисел.

function SumN(N: integer): integer;
begin
  Result := 0;
  for var i := 1 to N do
    Result += i;
end;

<xh4> Синтаксис описания функции </xh4>

function <имя>[( [<список формальных параметров>] )]: <тип возвращаемого значения>;
<раздел описаний>
begin
  <операторы и внутриблочные описания>
end;

<xh4> Синтаксис вызова функции </xh4>

<имя>[( [<список формальных параметров>] )];

<xh4> Семантика </xh4> Замечание. Формальные параметры функции не рекомендуется делать параметрами-переменными.

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

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

Оператор exit

Оператор exit — оператор досрочного завершения подпрограммы.

Пример. Поиск числа k среди n введенных.

function Find(n: integer; k: integer): boolean;
begin
  for var i := 1 to n do
  begin
    var x := ReadInteger;
    if x = k then
    begin
      Result := true;
      exit;
    end;
  end;
  Result := false;
end;

Замечание. Оператор exit, в отличие от break, позволяет завершить подпрограмму и выйти сразу из нескольких вложенных циклов. При вызове его в теле основной программы программа завершается.

Локальные и глобальные переменные

var
  n: integer;
  m: integer;

procedure p(x: integer);
var n: integer;
begin
  writeln(n);
  writeln(m);
  n := 5;
end;

Замечание. Локальная переменная, описанная в процедуре или функции, может иметь то же имя, что и глобальная переменная.
Если глобальная описана ранее, то её имя внутри процедуры становится недоступным.

Глобальные переменные по умолчанию инициализируются 0, а локальные по умолчанию не инициализируются.
Локальная переменная Result в функции по умолчанию также не инициализируется.

В данном примере:

writeln(n) выведет непредсказуемый результат;

writeln(m) выведет 0;

Пространство имен

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

Различают:

• глобальное пространство имен
• пространство имен каждой п/п

Формальные параметры п/п являются локальными по отношению к эти п/п.

Примеры допустимых и недопустимых описаний:

procedure p(p: integer);        //Можно

function Result: integer;       //Можно

procedure p(i: integer);        //НЕЛЬЗЯ
var i: integer;

function f(Result: real): real; //НЕЛЬЗЯ

Лекция 10

Область видимости и время жизни объекта

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

• для глобальных переменных это время работы программы
• для локальных — с момента описания до конца работы блока, где они описаны

Область видимости переменной — область в программе, в которой можно обратиться к переменной по имени.

Побочный эффект

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

Пример.

var n: integer;
procedure p;
begin
  n += 1;
end;

begin
  n := 5;
  p;
  write(p);
end.

Замечание. Если подпрограмма желает изменить глобальную переменную, то в большинстве случаев эту переменную следует передать как параметр.

Принцип локальности

Рассмотрим пример:

var n: integer;

procedure p;
begin
  <много кода; n не используется>
end;

procedure p1;
begin
  <еще больше кода; n не используется>
end;

begin
  <10 операторов>
  n := 1;
  <еще операторы>
end.

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

Обычно входные и выходные данные описываются, как глобальные переменные, после всех подпрограмм (если эти подпрограммы их не используют). В начале текста программы обычно используются переменные и константы, инициализируемые каким-то значением, которое легко поменять при следующих запусках этой подпрограммы.

Пример. Вычислить произведениe целых чисел от a до b. Решение 1.

var 
  p := 1;
  a, b: integer;
  i: integer;
begin
  read(a, b);
  for i:=a to b do
    p *= i;
  writeln(p);
  writeln(i); //от компилятора зависит, будет i = b или (b + 1)
end.

Внесем изменения:

• опишем i в заголовке цикла

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

• инициализируем p непосредственно перед циклом, вычисляющим произведение

Решение 2.

var 
  p: integer;
  a, b: integer;
begin
  read(a, b);
  p := 1;
  for var i:=a to b do
    p *= i;
  writeln(p);
end.

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

Внутренний механизм передачи параметра-переменной

procedure MyInc(var a: real; n: integer);
begin
  a += n;
end;

var
  b: real;
  i: integer;
begin
  b := ReadReal;
  i := ReadInteger;
  MyInc(b, i);
  writeln(b);
end.

Здесь

b, i: фактические параметры при вызове MyInc

a, n: формальные параметры (a — параметр-переменная; n — параметр-значение)

При передаче параметра-значения i в соответствующий формальный параметр копируется значение i. А вот механизм передачи параметра-переменной называется передачей по ссылке.

Ссылкой обычно называют другое имя некоторого объекта.

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

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

MyInc(var a: real; i: integer);
          |
         @b (адрес b)

Замечание 1. В 32-битных ОС размер адреса — 4 байта, это позволяет адресовать примерно 4 Гб операционной памяти.
Замечание 2. Размер адреса не зависит от размера переменной, поэтому при передаче параметров большого размера их предпочитают передавать по ссылке.

Перегрузка имен подпрограмм

Предположим, у нас описана процедура:

procedure Swap(a, b: integer);
begin
  var t := a;
  a := b;
  b := t;
end;

Возможно ли описать процедуру с таким же именем, параметры которой были бы вещественными? Да, возможно:

procedure Swap(a, b: integer);
begin
  var t := a;
  a := b;
  b := t;
end;

procedure Swap(a, b: real); 
begin
  var t := a;
  a := b;
  b := t;
end;

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

Замечание 1. Тип возвращаемого значения функции не участвует в операции разрешения перегрузки.

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

Замечание 2. Разрешить перегрузку можно не всегда.
Пример.

procedure p(i: integer; r: real);
...

procedure p(r: real; c: char);
...

procedure p(r: real; i: integer);
...

begin
  p(1, 2); //неоднозначность
end.

Замечание 3. В процессе разрешения перегрузки происходит неявное преобразование типов. Лекция 11

Параметры по умолчанию

procedure DoOp(a, b: integer; var res: integer; op: char := '+');
begin
  case op of
    '+': res := a + b;
    '-': res := a - b;
    '*': res := a * b;
  end;
end;
...
DoOp(1,2, res, '-'); // res = -1
DoOp(3,4, res1);     // res1 = 7

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

Замечание. Параметры по умолчанию корректно сочетаются с перегрузкой.

Предварительное объявление подпрограмм

procedure p;
begin
  q;
end;

procedure q;
begin
  ...
end;

Такое описание вызовет ошибку компиляции, т.к. в p используется еще не известная процедура. Чтобы таких ошибок не возникало, нужно использовать предварительное объявление подпрограммы:

procedure q; forward;

procedure p;
begin
  q;
end;

procedure q;
  ...

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

Процедурные переменные

Процедурный тип и переменные

var pr: procedure(a, b: real; var res: real);

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

type
  BinOpType = procedure(a, b: real; var res: real);

var
  pr: BinOpType;

procedure AddOp(a, b: real; var res: real);
begin
  res := a + b;
end;
procedure MultOp(a, b: real; var res: real);
begin
  res := a * b;
end;

begin
  pr := AddOp;
  var r: real;
  pr(1,2, r);   //вызов процедуры через процедурную переменную

  pr := MultOp;
  pr(3,4, r);
end.

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

<имя процедурной переменной>( <список параметров> );

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

Замечание. До первого присваивания процедурная переменная имеет тип nil. В этот момент вызывать процедуру через переменную нельзя — будет ошибка выполнения.

Функции обратного вызова (callback)

type ActionType = procedure;

procedure DoActions(Action1, Action2, Action3: ActionType);
begin
  Action1;
  Action2;
  Action3;
end;

procedure Eat;
begin
  writeln('Студент ест');
end;
procedure Think;
begin
  writeln('Студент думает');
end;
procedure Sleep;
begin
  writeln('Студент спит');
end;

begin
  DoActions(Sleep, Eat, Sleep);   // Первый алгоритм подготовки к сессии
  DoActions(Think, Eat, Sleep);   // Второй алгоритм подготовки к сессии
  DoActions(Sleep, Sleep, Think); // Третий алгоритм подготовки к сессии
end.

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

Такой вызов называется обратным вызовом (callback).
Примечание. Прямой вызов — это передача процедуры в качестве параметра.

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

type func = function(x: real): real;
function Integral(a, b: real; N: integer; f: func);
begin
  assert(a < b);
  var h := (b - a) / N;
  result := 0;
  var x := a;
  for var i:=0 to N-1 do
  begin
    result += f(x);
    x += h;
  end;
  result *= h;
end;

Вызов нескольких процедур через процедурную переменную

type ActionType = procedure;

procedure Eat;
begin
  ...
end;
procedure Think;
begin
  ...
end;
procedure Sleep;
begin
  ...
end;

var pr: ActionType;
begin
  pr += Sleep;
  pr += Eat;
  pr += Think;
  pr;
  pr -= Eat;
  pr;
end.

Замечание 1. Такое возможно только в .NET;
Замечание 2. Подобный механизм не имеет смысла использовать для функций;

Лекция 12

Методы разработки подпрограмм

Пример. Вывести таблицу простых чисел <= 1000.

Метод разработки сверху вниз

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

Решение.

writeln(2);
var x := 3;
while x <= 1000 do
begin
  if IsPrime(x) then
    writeln(x);
  x += 2;
end;

После этого реализуем функцию IsPrime;

Этот метод используется, когда:

• основной алгоритм понят, и его можно сразу записать
• задача четко поставлена
• имеется ровно одна задача, которую необходимо решить

Замечание. В коде главной программы имеются вызовы других подпрограмм, которые реализуются позже (возможно, другими разработчиками);
На период, пока они не написаны, вместо них могут использоваться "заглушки" (подпрограммы с тривиальными телами)

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

Метод разработки снизу вверх

Вначале составляется "нижняя" подпрограмма, она всесторонне тестируется, и, потом, 
пишется основная программа или подпрограмма.

Метод используется, когда:

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

Замечание 1. Написание самых "нижних" подпрограмм позволяет лучше войти в предметную область;
Замечание 2. С какого-то момента разработка хотя бы упрощенного главного алгоритма становится необходимой;

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

Оператор goto

Синтаксис

goto <метка>
...
<метка>: <оператор>

Метка представляет собой идентификатор или целое положительное число.
Метка должна описываться в разделе описаний меток в виде:

label <метка1>, <метка2>...;

Семантические ограничения

• метка должна использоваться в той же подпрограмме, в которой описана;
• нельзя, используя goto, перейти внутрь какой-нибудь конструкции (цикла или условного оператора);

<xh4>Пример плохого кода</xh4>

label 1, 2, 3;
begin
   goto 1;
   <100 операторов>
2: write(2);
   goto 3;
   <100 операторов>
1: write(1);
   goto 2;
   <100 операторов>
3: write(3);
end.

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

Пример.

найти a, b, c:

a² + b² = c², 50 <= a,b,c <= 100

label fin;
var aa, bb, cc: integer;
var flag := false;

for var a:=50 to 100 do
for var b:=50 to 100 do
for var c:=50 to 100 do
  if a*a + b*b = c*c then
  begin
    flag := true;
    aa := a;
    bb := b;
    cc := c;
    goto fin;
  end;

fin: if flag then
       writeln(aa, bb, cc);

Вызов подпрограммы на этапе выполнения

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

<здесь будет рисунок>

При в ходе в подпрограмму в процессе выполнения, на программном стеке для нее выделяется специальный участок памяти, называемый записью активации (ЗА) этой подпрограммы.

Данный участок выделяется на вершине стека, после чего вершина стека top "поднимается на размер ЗА.
После окончания работы подпрограммы ее ЗА снимается со стека и вызывающая программа выполняется дальше.

Пример.

Устройство ЗА подпрограммы

Штриховкой отмечены поля, заполняемые до запуска п/п.

Алгоритм входа в подпрограмму

1. Увеличить top стека на размер ЗА п/п, вычесленного на этапе компиляции: top += r_ЗА
2. Вычислить адрес возврата (АВ) и адрес конца ЗА вызывающей п/п
3. Вычислить значения всех фактических параметров и подставить их на место формальных.
4. Перейти в коде программы на начало выполнения п/п

Алгоритм выхода из подпрограммы

1. Уменьшитьtop стека, переместив его на адрес конца ЗА вызывающей подпрограммы
2. В коде программы перейти по АВ

Лекция 13

Пример

<здесь будет рисунок>

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

При перемещении top на программном стеке накапливается мусор, потом в этот мусор опять записывается ЗА.
Коды top и current хранятся в специальных регистрах.

Вывод 1. Если подпрограмма — маленькая, то накладные расходы на её вызов могут существенно превысить время работы самой подпрограммы.
Вывод 2. Если локальные переменные или формальные параметры, передаваемые по значению имеют большой размер, то ЗА соответствующей подпрограммы будет большой. В результате при нескольких вложенных вызовах таких подпрограмм может произойти переполнение программного стека (Stack overflow), т.к. программный стек не увеличивается в размерах, а память под него выделяется один раз.

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

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