2020-04-07
149
Самым простым является пустой оператор, который ничего не делает. Изображается он точкой с запятой.
Элементарным с точки зрения управления является выражение, предположительно имеющее побочный эффект, поскольку собственно результат выражения игнорируется. Типичным примером таких выражений являются присваивания и вызовы функций. Выражение превращается в оператор, когда за ним ставится точка с запятой.
Блоки нужны, во-первых, для того, чтобы из нескольких последовательно выполняющихся операторов сделать один, поскольку некоторые синтаксические конструкции требуют в качестве составной части только один оператор, и, во-вторых, дают возможность описать переменные, доступные только в этом блоке. Таким образом мы можем написать, например, следующий оператор, эффект которого пуст, поскольку он состоит из только пустых операторов и операций с локальными переменными:
{ int x=1; {;} x=1; {int x; x;} }
Отметим, что точка с запятой именно завершает оператор, а не разделяет операторы в последовательности, как это принято, скажем, в языке Паскаль. Поэтому блок {;} содержит единственный пустой оператор, а после закрывающей скобки ставить точку с запятой не нужно, хотя и можно, но в этом случае она будет обозначать ещё один пустой оператор.
|
|
|
Метки и goto
Каждый оператор может быть помечен одной или несколькими метками, изображаемыми идентификаторами. Метки используются для того, чтобы можно было передать на помеченный оператор управление с помощью оператора goto. Так, простейшая зацикливающаяся программа имеет вид
l: goto l;
Поскольку программа размещается в памяти (возможно, в специальной области), то можно считать, что у каждой команды есть адрес, а метка - не более, чем литеральное изображение адреса команды. Эти соображения позволяют рассматривать метки команд как отдельный тип данных, как это сделано, например, в языке GNU C - диалекте языка C. Типом метки считается указатель на void, и, следовательно, переменная такого типа может быть описана, как
void * lab;
Для того, чтобы по идентификатору метки получить значение типа метки используется унарная операция &&. С полученным значением можно делать всё, что позволяет язык: сохранять его в структурах данных, передавать в качестве параметра, использовать в альтернативах условных выражений, сравнивать с другими метками и т.п. Например, мы можем присвоить его в переменную lab:
lab = &&l;
В конечном итоге, значение типа метки может быть использовано для передачи управления с помощью разновидности оператора goto *:
goto * lab;
Возможности, которые предоставляют вычисляемые метки, настолько неконтролируемы и опасны, что даже в описании языка GNU C предписывается использовать их лишь в тех случаях, когда ничто другое принципиально не подходит. В нашем случае мы ненадолго введём вычисляемые метки для описания семантики других управляющих конструкций, после чего внесём их в "чёрный список".
|
|
|
Указанных управляющих возможностей достаточно для написания следующей программы:
void * next[] = {&&l1, &&l2, &&l1, &&l3};
goto * next[(n>0) | ((n&1)<<1)];
l3: y*=x; goto * next[n>1];
l2: x*=x; goto * next[1 | ((n>>=1)&1)<<1];
l1:
в которой достаточно сложно узнать программу вычисления xn, рассматривавшуюся ранее:
while (n > 0)
{
if (n%2)
y = y*x;
x = x*x;
n = n / 2;
}
Помимо того, что мы использовали совмещенные присваивания и использовали сдвиги вместо операций взятия по модулю и деления нацело на 2, всё управление спрятано в массиве меток next. Младший бит индекса этого массива соответствует положительности n, а второй - нечётности n. Кроме этого, программа была оптимизирована содержательно на основе следующих наблюдений:
1. если n положительно и нечётно, то после вычитания 1 оно обязательно будет чётно;
2. если n положительно и чётно, то после деления на 2 оно обязательно будет положительно.
Таким образом, удалось избежать избыточных проверок.
Возможно, что эта программа и более эффективна, чем исходная, но читать и понимать её совершенно невозможно. Для каждого помеченного оператора необходимо просмотреть весь фрагмент, чтобы понять откуда на него может быть передано управление. А в случае вычисляемых меток приходится решать и обратную задачу: для каждого оператора goto приходится выяснять, куда именно он может передавать управление. На фундаментальном уровне это выражается ещё более серъёзной проблемой: становится невозможным задать семантику программы путём композиции, как мы это делали при описании денотационной и аксиоматической семантики.
Переменные-метки и переходы по вычисляемым меткам не является изобретением языка GNU C. Ещё в языке Фортран были сходные конструкции, называемые переключателями. Приведём для примера пару фрагментов, реализующих одно и то же:
t = X – (X/6)*6 +1
GOTO (0,1,2,3,3,3) t
0 CONTINUE
2 X = X+2
3 X = X+1
GO TO 100
X = 0
100
и
t = X – (X/6)*6
ASSIGN 3 TO L
IF (t.EQ.0) ASSIGN 0 TO L
IF (t.EQ.1) ASSIGN 1 TO L
IF (t.EQ.2) ASSIGN 2 TO L
GOTO L, (0,1,2,3)
0 CONTINUE
2 X = X+2
3 X = X+1
GO TO 100
1 X = 0
100
Смысл оператора ASSIGN и различных форм GOTO можно легко предположить. Заметим, что Фортран всё-таки не допускал тех вольностей, которые допускает GNU C: для каждого оператора goto указан список возможных меток, на которые он может передать управление, и этот список не может меняться в процессе исполнения.
Поскольку для меток используются имена, следует сказать об области действия этих имен. В языке C (по-крайней мере в стандарте) нет явного объявления меток, и метка считается видимой во всей охватывающей функции. Таким образом допускается переход внутрь блока, как, например
goto l;
for (int i=0; i<n; i++)
{
if (i>0)
{
int x = 2;
l: printf("%d", x*i);
}
}
что приводит к непредсказуемым последствиям. Язык Паскаль требует объявления меток, но они также относятся к функциям и не согласуются с блочной структурой.
Ветвления
В языке C имеется две конструкции, реализующие выбор одной из ветвей в зависимости от значения выражения - условный if и переключатель switch. Их синтакис задаётся следующим образом:
| ветвления: | 
|
Условный оператор if имеется в том или ином виде во всех императивных языках программирования. Его семантика заключается в вычислении условия и выполнении одной из двух альтернатив в зависимости от истинности условия: то-части, следующей непосредственно за условием, или иначе-части, следующей за ключевым словом else. Если иначе-часть не указана, то она полагается равной пустому оператору. Таким образом, оператор
|
|
|
if (условие) то-часть else иначе-часть
эквивалентен
goto (условие? lThen: lElse);
lThen: то-часть; goto lDone;
lElse: иначе-часть;
lDone:
Мы уже говорили о том, что зачастую условные операторы являются вложенными, как в
if (условие 1)
вариант 1
else if (условие 2)
вариант 2
...
else if (условиеn)
вариантn
else
вариантelse
Конечно, это можно рассматривать как ветвление с более чем двумя альтернативами, но описанная выше семантика предписывает, что условия вычисляются последовательно до первого истинного.
Выбор из произвольного числа альтернатив реализуется переключателем switch. Описанный выше синтаксис говорит о том, что помечать операторы можно не только идентификаторами, но и метками вида case выр и default, которые допустимы только внутри переключателя. Выражение, следующее за case должно быть константным. Выполнение переключателя начинается с вычисления выражения, указанного в скобках. Если значение равно i, то управление передаётся на оператор, помеченный меткой case i, а если такого оператора нет, то на оператор, помеченный меткой default. Если же и default отсутствует, то на оператор, следующий за switch. Оператор break; внутри переключателя также завершает его выполнение.
Рассмотрим, например, оператор
switch (x % 6)
{
case 0:
case 2:
x += 2;
default:
x += 1;
break;
case 1:
x = 0;
break;
}
Он может быть реализован как
void * sw[] = { &&l0, &&l1, &&l2, &&lElse, &&lElse, &&lElse };
goto * sw[x % 6];
l0: l2: x += 2;
lElse: x+=1; goto lDone;
l1: x = 0; goto lDone;
lDone:...
Отметим некоторые свойства переключателя:
· Значение выражения в переключателе (x%6 данном примере) вычисляется один раз;
· Выбор метки может быть реализован разными способами:
1. в виде массива меток (как в данном примере), если известен их диапазон и он достаточно небольшой;
2. двоичным поиском (дихотомией), если альтернатив достаточно много и при этом имеется разброс значений;
3. последовательным перебором, если значений совсем немного;
4. оптимальным деревом поиска, если предварительно собрана статистика о частоте выполнения альтернатив и т.п.
· Завершение выполнения альтернативы, если она не заканчивается оператором break; не означает завершения выполнения всего переключателя. Так, в данном примере после выполнения x+=2; управление перейдёт к x+=1;. На практике это свойство переключателя является источником ошибок, поскольку break; чаще всего отстуствует не намеренно. Конечно, можно привести примеры, когда такое поведение позволяет либо не дублировать код, либо избежать использования goto, но в целом вреда больше, чем пользы.
|
|
|
В общем, переключатель в языке C недалеко ушёл от перехода по вычисляемой метке и позволяет писать плохо структурировнные программы, включая переход внутрь блока, как в следующем примере:
int i = 1;
switch (i%2)
if (i>0)
case 0:
{
i++;
if (i%2)
case 1:
i--;
else
break;
}
При вложенных переключаетелях как метки case и default, так и оператор break; относятся к ближайшему охватывающему переключателю.
На практике в большинстве случаев переключатель соответствует следующему синтаксису, который принят в языке C#:
что, видимо, можно рекомендовать и для использования в языке C.
Вариации
Условые операторы практические одинаковы во всех императивных языках программирования, если не принимать во внимание синтаксические различия, связанные c else if и условного с отрицанием unless. Редким исключением является язык Фортран, где помимо логического условного имеется также и арифметический, который основывается не на истинности выражения, а на его знаке. Рассмотрим, например, фрагмент программы двоичного поиска:
int m = (low + high)/2;
if (A[m] == x)
; // нашли!
else if (A[m] > x)
high = m-1;
else
low = m+1;
Выбор одной из трёх альтернатив зависит от знака выражения(A[m]-x) и в языке Фортран такое ветвление может быть записано как
IF (A[m]-x) 10, 20, 30
где метки 10, 20, 30 соответствуют случаям "меньше нуля", "равно нулю" и "больше нуля" соответственно.[25] В языке C такое ветвление можно записать как
switch (sign(A[m]-x))
{
case 0: break; // нашли!
case 1: high = m-1; break;
case -1: low = m+1; break;
}
что может быть несколько нагляднее, чем исходная версия, поскольку выносит в заголовок суть выбора, и эффективнее, поскольку здесь меньше обращений к массиву A.
Некоторые языки программирования допускают использование интервалов в качестве меток переключателя. Так, в языке Паскаль допустим следующий оператор:
case ch of
'A'..'Z', 'a'..'z': WriteLn('Буква');
'0'..'9' : WriteLn('Цифра');
'+', '-', '*', '/': WriteLn('Операция');
else
WriteLn('Спецсимвол')
end
Конечно, интервал можно было бы вручную "раскрыть", перечислив все его значения. Однако, при этом теряется наглядность и появляется риск пропустить некоторое значение. К тому же, если в качестве типа меток используется перечисление enum, то при добавлении нового элемента к этому типу придётся исправлять и все места, где он используется.
Язык C требует, чтобы метки переключателя были целого типа (включая, естественно, тип char и enum), но не допускает строки. В том же Паскаль допустим следующий переключатель:
case lowercase(s) of
'huge', 'large', 'big': FontSize=18;
'normal', 'medium': FontSize=12;
'small', 'little', 'tiny',: FontSize=8;
else
FontSize=12;
end
Для такого переключателя не подойдёт реализация в виде массива меток, но он также может быть реализован более эффективно, нежели последовательность сравнений строк. Например, можно на уровне трансляции построить регулярное выражение и соответствующий конечный автомат, который будет находить нужную альтернативу за один проход по строке.
В некоторых языках, например в Visual Basic, нет требования, чтобы метки были константами. Если бы то же было и в языке С, то рассмотренный выше фрагмент программы двоичного поиска можно было бы реализовать следующим образом:
switch (1)
{
case A[m]==x: break; // нашли!
case A[m]>x: high = m-1; break;
case A[m]<x: low = m+1; break;
}
В данном примере можно гарантировать, что будет истинно ровно одно из условий, однако, в общем случае невозможно ни определить диапазон значений, ни проверить то, что все метки различны. Поэтому накладывается требование, чтобы проверки осуществлялись последовательно, что семантически сводит переключатель switch к последовательности вложенных условных операторов.
Аналогичные проблемы возникают и в случае, если язык допускает в переключателе не только сравнения на равенство, а, например, сопоставление строки с шаблоном или регулярным выражением.
Циклы
Циклы предназначены для многократного повторения некоторой совокупности действий. В языке C есть три вида оператора цикла и два оператора, связанных с циклами, - break; и continue;, синтаксис которых определяется следующей диаграммой:
| циклы: | 
|
Семантику циклов начнём описывать с оператора for. Если init, condition и step - выражения, а body - оператор, то конструкция
for (init; condition; step)
body
эквивалентна
init;
lLoop:
if (! condition) goto lDone;
body
lStep:
step;
goto lLoop;
lDone:;
Если условие condition отусутствует, то оно полагается тождественно истинным, то есть условный оператор можно опустить. В этом случае тело цикла body будет выполняться бесконечно много раз, если только в нём не содержится оператор перехода вне цикла.
Выражения инициализации init и шага цикла step имеют смысл, только если они содержат побочный эффект. Типичное их использование состоит в задании начального значания и изменении переменной цикла, как например,
for (i=0; i<N-1; i++)
A[i] = A[i+1];
В отличие от многих языков программирования, где переменная цикла, границы и шаг её изменения задаются явными синтаксическими конструкциями, язык C предоставляет большую гибкость. Так, возможно в заголовке цикла задать несколько переменных не обязательно целого типа. Например, тот же цикл можно реализовать более эффективно:
for (q=(p=A)+1,i=N-1; i; p=q++,i--)
*p = *q;
где переменные p и q указывают на очередной и следующий элементы массива A, соответственно, и не участвуют в условии цикла, а переменная i используется, чтобы обеспечить количество итераций равным N-1.
Операторы break; и continue;, называемые структурными переходами, означают передачу управления на lDone и lStep, соответственно. То есть break; завершает выполнение цикла, а continue; переходит к следующей итерации.
Циклы while и do...while можно рассматривать как синтаксический сахар: их легко выразить через цикл for. Оператор
while (condition) body
эквивалентен
for (;;)
{
if (! condition) break;
body
}
а оператор
do body while (condition);
эквивалентен
for (;;)
{
body
if (! condition) break;
}
То есть обе эти формы цикла выполняются пока истинно условие, но в первом случае проверка производится перед очередной итерацией, а во втором - после.
Вариации
Во многих языках программирования есть вариант цикла, условие которого определяет не продолжение, а завершение цикла. Так в Паскаль цикл
repeat... until condition
будет выполняться до тех пор, пока x не станет меньше 0.01. По каким-то причинам в Паскаль условие завершения можно указывать только в конце цикла, а условие продолжения - только в начале. В языке Visual Basic имеется полный набор комбинаций:
Do While condition
...
Loop
Do Until condition
...
Loop
Do
...
Loop While condition
Do
...
Loop Until condition
Все эти формы цикла легко выражаются в языке C, поскольку условие завершения есть просто отрицание условия продолжения.
На практике очень часто встречается ситуация, когда надо некоторое действие повторить определённое количество раз. В языке Альфа-6 (диалекте Алгол-60) для этой цели введена особая форма цикла
N раз...
Конечно, она может быть реализована в языке C как
for (k=N; k--;) …
но менее наглядно и с необходимостью явно вводить дополнительную переменную.
Иногда необходимо выполнить цикл для заданного множества значений переменной цикла. Так, язык Алгол-60 позволяет оператор
for i=1,2,-3,4,10 do …
В языке C это может быть реализовано путём введения вспомогательного массива, хранящего это множество значений:
{
int values[] = {1,2,-3,4,10};
for (k=0; i=values[k], k<5; k++)
…
}
Опять же это менее наглядно и требует дополнительного блока, чтобы расположить описание массива ближе к его единственному использованию.
Обобщением цикла по перечню значений является цикл по структуре данных, элементы которой могут быть перечислены: массива, списка, строки и т.п. Так, например, в языке Visual Basic для массива A можно написать цикл
Dim A(1 To N) As Integer
For Each x In A
… x …
Next x
Заметим, что здесь переменная x не является синонимом очередного значения массива, и присваивание ей не будет менять состояние A. Далее обобщение цикла можно развить на основе понятия итератора - объекта, из которого можно получить очередной элемент обрабатываемой последовательности, если она ещё не исчерпана.
По другому пути пошло обобщение в языке Алгол-60. Он рассматривает каждое из перечисленных значений как отдельный заголовок цикла, описывающий единственное значение, а в общем случае заголовком может быть и перечисление с использование while, until, step и т.п. Такое обобщение позволяет написать, например, следующий цикл с тремя заголовками
for i:=1,
4 while x>0.01,
N step -1 until 10 do
…
где переменная i на первой итерации будет равна 1, затем выполнится какое-то количество итераций при i равном 4 до тех пор, пока x не станет меньше или равным 0.01, а затем i будет пробегать в обратном порядке значения от N до 10.
На практике весьма редко возникаются ситуации, требующие несколько заголовков цикла, помимо рассмотренного выше случая, когда все заголовки являются отдельными значениями. Рассмотрим, например, цикл, в котором надо удвоить все элементы массива, за исключением k-го:
for i:= 1 step 1 until k-1, k+1 step 1 until N do
A[i]:=* * 2;
Реализация цикла со многими заголовками весьма нетривиальна. Можно заменить этот цикл несколькими, в каждом из которых будет один заголовок. Но при этом придётся раскопировать тело цикла, что нежелательно, если оно достаточно сложное. Другой способ заключается в организации внешнего цикла, который будет перебирать заголовки, а переходы, организующие внутренний цикл, заменить на переходы по вычисляемой метке. В языке C такая реализация может выглядеть как
void * lInit[] = { &&lInit1, &&lInit2 };
void * lStep[] = { &&lStep1, &&lStep2 };
int l;
for (l=0; l<2; l++) // цикл по заголовкам
{
goto* lInit[l];
lInit1: i=1; goto lLoop1;
lInit2: i=k+1; goto lLoop2;
lLoop1:
if (i>k-1) continue; // переход к следующему заголовку цикла
goto lBody;
lLoop2:
if (i>N) continue; // переход к следующему заголовку цикла
goto lBody;
lBody:
A[i] *= 2; // тело исходного цикла
goto* lStep[l];
lStep1: i++; goto lLoop1;
lStep2: i++; goto lLoop2;
}
Заметим, во-первых, что здесь не пришлось копировать тело цикла, а во-вторых, что при такой реализации в каждом внутреннем цикле нет дополнительных накладных расходов, за исключением перехода по вычисляемой метке
goto* lStep[l];
Однако, общая организация цикла достаточно сложна и в данном конкретном случае не даёт особого выигрыша по сравнению с
for i:= 1 step 1 until N do
if (i^=k) A[i]:=* * 2;
где на каждой итерации делается одна дополнительная проверка. Кроме того, она явно уступает рассмотренной выше реализации для случая, когда все заголовки цикла - константы.
Таким образом, можно сделать вывод, что стремление к обобщению не всегда является продуктивным и лучше иметь несколько частных конструкций с эффективной реализацией, чем одну - со сложной и, возможно, не самой эффективной.
Необходимо сделать несколько замечаний о переменной и границах цикла. Как мы уже отметили, в языке C такого понятия в явном виде нет, что, с одной стороны, предоставляет большую гибкость, а, с другой, - лишает возможности дополнительного контроля. В языке Паскаль цикл for явно указывает переменную цикла и её границы, как, например, в
for i:=1 to Length(s) do
if (s[i] = " ") Inc(cnt);
При этом гарантируется, что границы цикла будут вычисляться только один раз. Это может оказаться существенным с точки зрения как семантики, так и эффективности. Например, в аналогичным цикле на языке C
for (i=0; i<strlen(s); i++)
if (s[i] == ' ') cnt++;
сложность будет пропорциональна не длине строки, а квадрату длины, поскольку strlen(s) вычисляется на каждой итерации и требует просмотра всей строки.
Очень нехорошей является идея изменять переменную и границы внутри тела цикла. Например, в Паскаль до появления в нём оператора break; для прерывания цикла использовался следующий приём: переменной цикла присваивалось значение, большее верхней границы. Так, например, следующий цикл прерывает выполнение, если очередной элемент массива А оказывается нулевым:
for i:=1 to N do
if A[i] = 0 then i = N+1;
Язык Алгол-68 вообще считает переменную цикла константой, объявленной в заголовке: присваивание ей в теле цикла приведёт к синтаксической ошибке, а значение переменной цикла после его завершения неопределено.
Рассмотрим теперь подробнее операторы структурного перехода: break; и continue;. С ними возникает проблема, когда они используются во вложенных циклах. Так, continue; относится к ближайшему охватывающему циклу, а break; - к циклу или оператору switch, где break; имеет свой смысл. В частности, это означает, что если телом цикла является оператор switch, то невозможно использовать break; для того, чтобы прервать цикл.
for (i=0; i<N-1; i++)
switch (s)
{
case '0':
....
continue; // относится к for
default:
....
break; // относится к switch
}
Аналогично, при вложенности циклов невозможно прервать охватывающий цикл. Пусть, например, требуется найти первую строку матрицы с нулевым элементом. Следующий фрагмент будет делать это неправильно:
int found = -1;
for (i=0; i<N; i++)
for (j=0; j<N; j++)
if (A[i][j] == 0)
{
found = i;
break;
}
поскольку после нахождения нулевого элемента, будут проигнорированы оставшиеся элемены в текущей строке, после чего управление перейдёт к следующей итерации внешнего цикла. В результате будет найдена не первая, а последняя строка, содержащая нулевой элемент. Для того, чтобы исправить эту ошибку, можно завести дополнительную логическую переменную, которую сделать истинной в момент прерывания внутреннего цикла, а сразу после этого цикла, прервать и внешний, если эта переменная истинна:
int found = -1;
for (i=0; i<N; i++)
{
int do_break = 0;
for (j=0; j<N; j++)
if (A[i][j] == 0)
{
found = i;
do_break = 1;
break;
}
if (do_break)
break;
}
Конечно, таким образом удалось сохранить структурированность программы, но за счёт дополнительных накладных расходов, потери наглядности и надёжности, то есть всего того, для чего структурированность и предназначена.
Проблема, очевидно, заключается в том, что в структурном переходе break; невозможно указать, к какому именно оператору он относится. Некоторые языки, например Java, решают эту проблему введением понятия структурных меток, которыми могут быть помечены циклы или другие составные операторы. Тогда тот же фрагмент можно вернуть практически к исходному виду:
int found=-1;
iloop:
for (i=0; i<n; i++)
for (j=0;j<N;j++)
if (A[i][j]==0)
{
found = i;
break iloop;
}
В языке C такие ситуации относятся к тем редким случаям, когда оправдано применение оператора goto.
Процедуры и функции
Процедуры и функции позволяют описать некоторую параметризованную совокупность действий, которую затем можно многократно вызвать в разных местах программы. Различие между функциями и процедурами состоит в том, что первые предназначены для вычисления значения результата и их вызов является выражением, а вторые - исключительно для изменения состояния памяти и, соотвественно, их вызов является оператором. Поскольку в С, как и во многих других языках программирования, включая Паскаль, Алгол и т.д., функции тоже могут иметь побочный эффект, в языке оставлено только понятие функции, а процедуры считаются их частным случаем с результатом типа void.
Описание функций
Синтаксис описания функции в языке С имеет следующий вид:
| функция: | 
|
В нём отражается несколько, вообще говоря, самостоятельных аспектов:
1. описание типа функции, которая включает тип результата, с которого начинается описание, а также типы и имена формальных параметров, задаваемые описателями. Если список формальных параметров завершается многоточием, то это означает, что функция может иметь дополнительные параметры;
2. имя функции;
3. тело функции - блок, определяющий последовательность выполняемых действий с указанием того, что является результатом.
Вызов функции
Функции в языке C являются значениями, хотя и не вполне равноправными. Единственная операция, которая к ним применима, - это вызов функции. Однако имя функции, если оно используется не в вызове, трактуется как указатель на функцию, который уже может быть присвоен переменной соответствующей типа, передан в качестве параметра другой функции и т.п. Таким образом, вызываемая функция может быть получена не только указанием имени, но и применением разыменования к выражению, вычисляющему указатель на функцию.
Синтаксис вызова функции имеет следующий вид
что включается в общий синтаксис выражения. Начинается вызов с выражения, вычисляющего функцию, а затем в скобках указываются выражения, вычисляющие фактические параметры. Количество фактических параметров в вызове функции должно совпадать с количеством формальных, если только это не функция с переменным количеством параметров. Типы фактических параметров должны быть приводимы, как при присваивании, к типу соответствующих формальных.
Для того, чтобы из вызова функции сделать оператор, например, если эта функция является процедурой, достаточно, как и для любого другого выражения, поставить после вызова точку с запятой.
Приведём несколько примеров вызова функции:
ToPolar(x, y, &alpha, &ro)
* (shift? sin: cos) (n * pi / 3)
(* F[i])(x > 0? 1: x=-x, -1)
Ack(m-1, Ack(m,n-1))
WriteLn()
Первый вызов - пример самого распространённого случая, когда явно указывается имя вызываемой функции. Во втором вызове будет вызываться либо sin, либо cos в зависимости от значения переменной shift, но аргумент будет один и тот же. В третьем случае F - массив указателей на функции, и будет вызван один из его элементов. Четвёртый вызов демонстрирует, что фактическим параметром также может быть вызов функции. Наконец, последняя строка - вызов функции WriteLn без параметров. Типичной ошибкой является попытка вызова функций без скобок:
WriteLn;
как это принято в таких языках, как Паскаль или Visual Basic. К сожалению, в языке C это является вполне законной конструкцией, вычисляющей функцию как значение и тут же игнорируюей его, но не приводящей к ее вызову.
Вызов функции – шаги исполнения:
1. вычисляется вызываемая функция;
2. создаются локальные объекты: формальные параметры, локальные объекты тела функции;
3. вычисляются фактические параметры, значения которых копируются в соответствующие локальные объекты;
4. выполняется тело функции;
5. удаляются локальные объекты;
6. возвращается результат.
Возвращаемое функцией значение указывается в операторе return со следующим синтаксисом:
Выражение должно пристуствовать тогда и только тогда, когда тип возвращаемого значения отличен от void. Кроме этого, оператор return завершает исполнение процедуры, то есть переходит к шагу 4. Точнее говоря, корректное исполнения функции, которая не является процедурой, обязано завершаться оператором return.
Каждая программа должна содержать главную функцию, называемую main, следующего типа:
int main(int argc, char * argv[])
Система программирования вызывает эту функцию, подготовив всё необходимое окружение. В частности, в качестве фактических параметров передаётся массив argv из аргументов командной строки и их количество argc.
Семантику исполнения функций мы будем демонстрировать на примере программы вычисления полинома:
float poly(float coef[], int n, float x)
{
float sum = 0f;
for (int i=0; i<=n; i++)
sum += coef[i] * power(i,x);
return sum;
}
float power(int n, float x)
{
return n==0? 1: x*power(n-1,x);
}
void main()
{
float binom[] = {1,2,1};
printf(“%d”, poly(binom,2,10.0));
}
В этой программе определены три функции:
1. main - главная функция:
2. poly - функция вычисления полинома, получающая в качестве параметров массив коэффициентов coef, степень полинома и значение переменной. Длина массиав coef равна n+1;
3. power - функция вычисления x в степени n.
Рекурсия
Особенностью функции power в рассматриваемой программе является то, что при некоторых условиях она может вызывать сама себя, что соответствует рекуррентному математическому определению степенной функции:
Такие функции называются рекурсивыми. Это определение может быть истолковано разными способами и требует более формального подхода. Рассмотрим граф вызовов программы. Вершинами этого графа являются функции, а дуга проводится от одной функции к другой, если в первой есть вызов второй. Дуга помечается этим вызовом. Для рассматриваемой программы граф вызовов имеет вид:
| main() |
| poly(binom, 2, 10.0) |
| float poly(float coef[], int n, float x) |
| float power(int n, float x) |
| power(i,x) |
| power(n-1,x) |
Тогда функцию можно назвать рекурсивной, если в графе вызовов через эту функцию проходит хотя бы один цикл.
Однако, такое определение является статическим, поскольку опирается исключительно на текст программы и не вполне отражает реальное исполнение. Действительно, может оказаться, что при конкретных данных данный цикл в графе вызовов не реализуется. Более того, может оказаться, что ни один цикл, проходящий через данную вершину не реализуется ни при одном исполнении. Динамическое поведение программы отражает понятие дерева вызовов, вершинами которого являются выполненные в ходе исполнения программы вызовы с указанием значений фактических параметров, а дуга проводится, если один вызов привёл к другому. Дуги упорядочены согласно порядку исполнения. Корнем дерева является вызов главной функции main. Для рассматриваемой программы дерево вызовов имеет следующий вид:
| main() |
| poly(binom,2,10.0) |
| power(0, 10.0) |
| power(1, 10.0) |
| power(2, 10.0) |
| power(0, 10.0) |
| power(1, 10.0) |
| power(0, 10.0) |
Тогда функцию можно считать рекурсивной, если она встречается по крайней мере дважды на некотором пути от корня к листу. Глубиной рекурсии для вызова некоторой функции называется количество вершин в дереве вызовов, соответствующих той же функции, на пути от данного вызова до корня. Например, глубина рекурсии последнего вызова функции power равна 3.
Рекурсия может приводить к зацикливанию программы и бесконечному дереву вызовов. Простейшим примером является функция
void infinite() { infinite(); }
Есть несколько условий, которые позволяют избежать зацикливания в функциях:
1. в функции должен быть хотя бы один путь, не приводящий к рекурсивному вызову. В случае функции power такой путь обеспечивается условием n==0;
2. должна быть некоторая дискретная величина, которая монотонно убывает при каждом рекурсивном вызове и ограничена снизу. В случае power такой величиной является значение параметра n.
В общем случае не только бесконечность рекурсии, но и сама рекурсивность функции в "динамическом" смысле является алгоритмически неразрешимым свойством. Что же касается "статической", то есть основанной на графе вызовов рекурсивности, то её легко определить, но только в случае, если вызываемые функции всегда указываются явно своими именеми. Иначе для каждого выражения, вычисляющего функцию, необходимо определить множество её возможных значений, что, во-первых, требует глобального анализа программы и, во-вторых, в общем случае можно сделать лишь приблизительно.
Если происходит рекурсивный вызов функции, т.е. функция вызывается, когда предыдущий её вызов еще не закончился, то согласно описанному методу исполнения вызова функции создаются новые локальные объекты, когда старые ещё не удалены. В результате для каждого локального объекта возникают несколько одновременно существующих поколений, но каждый вызов "знает" с каким именно поколением он работает.
Рекурсия в языках программирования долгое время вызывала много споров, связанных прежде всего с неэффективностью её реализации. Во-первых, собственно вызов функции является дорогостоящей операцией, связанной с пересылкой значений фактических параметров в локальные объекты, организацией возврата управления и т.д. Во-вторых, для рекурсивных процедур требуется дополнительная память, размер которой пропорционален дереву вызовов. Наконец, рекурсия сильно затрудняет статический анализ программ, что зачастую делает невозможными многие оптимизирующие преобразования.
С другой стороны, все эти недостатки перекрываются тем, что рекурсия позволяет естественно реализовать по существу рекурсивные алгоритмы, такие как полный перебор, метод ветвей и границ, метод "разделяй-и-властвуй" и др.
Реализация функций
Семантику функций мы будем описывать, используя трансформационный подход, постепенно преобразуя программу ко всё более простому виду. На каждом шаге будут использоваться преобразования, смысл, применимость и корректность которых очевидна, что гарантирует, что семантика программы в целом не меняется.
На первом шаге мы упростим выражения, разбив их на последовательность операторов, возможно, с использованием вспомогательных переменных так, чтобы любой вызов функции, не являющейся процедурой, встречался только как левая часть присваивания
t = f(...);
Для этого может потребоваться, в частности, преобразовать условные выражения в условные операторы. Так, например, оператор
return n==0? 1: x*power(n-1,x);
преобразуется в
if (n==0)
return 1;
else
{
float t = power(n-1,x);
return x * t;
}
На втором шаге преобразуем все функции в процедуры. Для этого к каждой функции добавим дополнительный формальный параметр result типа указателя на исходный тип результата функции. Все операторы вида
return e;
заменим на присваивание переменной, на которую указывает result и return
* result = e;
return;
Присваивание, в котором правой частью является вызов функции
t = f (e 1,..., e n);
заменим на вызов процедуры, последним параметром которой будет адрес получателя исходного присваивания:
f (e 1,..., e n, & t);
В результате этого преобразования функция power примет следующий вид:
void power(int n, float x, float * result)
{
if (n==0)
*result = 1;
else
{
float t;
power(n-1,x ,&t);
*result = x * t;
}
}
На третьем шаге мы добъёмся того, что все процедуры будут иметь единственный параметр - указатель на структуру, называемую фреймом, в которой собраны все формальные параметры исходной процедуры и локальные переменные тела функции. Для каждой функции будет свой тип фрейма. Позже мы в эту структуру добавим дополнительную информацию. Фрейм создаётся перед вызовом процедуры и в него присваиваются значения, соответствующие фактическим параметрам. В теле процедуры обращения к локальным объектам заменяются на обращения к полям фрейма. Наконец, по завершении вызова процедуры фрейм удаляется.
Для создания и удаления фрейма будем использовать специальные конструкции frame_new и frame_dispose, реализацию которых обсудим ниже.
Таким образом, процедура power приобретает следующий вид:
struct frame_power
{
int n;
float x;
float * result;
float t;
}
void power(struct frame_power *f)
{
if (f-> n==0)
*(f-> res) = 1;
else
{
struct frame_power *a;
frame_new(a);
a-> n = f-> n-1;
a-> x = f-> x;
a-> result = &(f-> t);
power(a);
frame_dispose(a);
*(f-> result) = f-> x * f-> t;
}
}
Головную функцию main оставим вне рассмотрения - она требует специальной обработки, поскольку мы не можем менять её тип.
На четвёртом шаге мы избавимся от параметров вообще. Заметим, что к этому моменту у каждой процедуры есть доступ только к одному фрейму. Заведём глобальную переменную f, которая будет хранить ссылку на текущий фрейм. Посколько фреймы бывают разных типов, то переменная f будет описана просто как указатель
void * f;
а чтобы при каждом использовании f не делать явного приведения типов, заведём также глобальные типизированные указательные переменные для каждого типа фрейма - f_power, f_poly и т.д. - в которые будем присваивать значение f в начале соответствующей процедур.
В каждом фрейме будем сохранять указатель на фрейм вызвавшей процедуры, который тоже должен быть описан как нетипизированный, поскольку данная процедура может вызываться из разных мест. Переменной f присваивается новое значение перед вызовом процедуры и восстанавливается старое после вызова
struct frame_power
{
void * parent;
int n;
float x;
float * result;
float t;
} * f_power;
void power()
{
f_power = f;
if (f_power->n==0)
*(f_power->res) = 1;
else
{
struct frame_power *a;
frame_new(a);
a->n = (f_power ->n)-1;
a->x = f_power ->x;
a->res = &(f_power ->t);
a->parent = f;
f = a;
power ();
f = a->parent;
frame_dispose(a);
* (f_power ->result) = f_power ->x * f_power ->t;
}
}
На последнем, пятом шаге мы избавимся от процедур вообще. В результате получится одна большая процедура main, в которую будут включены тела всех процедур. К настоящему моменту из всех действий, связанных с вызовом процедуры, остался только переход к выполнению тела процедуры, что может быть реализовано оператором goto на метку, которую поставим в начале тела процедуры.
Проблема только в реализации возврата, т.е. в том, куда передать управление при достижении конца процедуры или оператора return. Для этого поставим после каждого вызова уникальную метку и запомним перед переходом к выполнению тела процедуры указатель на неё в ещё одном дополнительном поле фрейма. Тогда оператор return можно заметить на переход по вычисляемой метке goto*.
void * f;
struct frame_power
{
void * f_parent;
void * return_label;
int n;
float x;
float * res;
float t;
} * f_power;
struct frame_poly
{
...
} * f_poly;
void main()
{
...
poly:
f_poly = f;
...
for (...)
{
...
struct frame_power *a;
frame_new(a);
a->n = f_poly->i;
a->x = f_poly->x;
a->res = &(f_poly->t);
a->parent = f;
a->return_label = &&l_power1;
f = a;
goto power;
l_power1:
(f_poly)->sum += (f_poly->coef)[i] * f_poly->t;
}
...
power:
f_power = f;
if (f->n==0)
*(f->res) = 1;
else
{
struct frame_power *a;
frame_new(a);
a->n = (f_power->n)-1;
a->x = f_power->x;
a->res = &(f_power->t);
a->parent = f;
a->return_label = && l_power2;
f = a;
goto power;
l_power2:
f = a->parent;
frame_dispose(a);
* (f_power->res) = f_power->x * f_power->t;
}
goto * (f_power->return_label);
}
Если у процедуры есть единственный вызов (и других никогда не будет), то можно не хранить метку и переход по вычисляемой метке заменить не безусловный переход в точку возврата.
Если теперь нужно вообще избавиться от переходов по вычисляемой метке и вернуться к стандарту С, то можно пронумеровать все возможные точки возврата,
Enum return_power
{
e_power1,
e_power2,
}
во фрейме вместо указателя на метку хранить значение этого типа
struct frame_power
{
...
enum return_power return_label;
...
}
...
a->return_label = e_power1;
...
a->return_label = e_power2;
...
а переход по вычисляемой метке заменить на переключатель:
switch (f_power->return_label)
{
case e_power1: goto l_power1;
case e_power1: goto l_power1;
}
Таким образом мы преобразовали рекурсивную программу в итеративную, сведя тем самым семантику процедур к базовым управляющим конструкциям. Отметим следующие аспекты проделанных преобразований:
3. Все преобразования носят универсальный характер, т.е. не используют знаний о том, что именно делает программа. Это значит, что мы можем проделать то же самое с любой другой программой.
4. Полученная программа гораздо сложнее воспринимается и анализируется, нежели исходная. Но именно так нам пришлось бы программировать, если бы в языке не было бы рекурсивных процедур, а решаемая задача была бы существенно[26] рекурсивной, что ещё раз свидетельствует о достоинствах рекурсивных процедур, по крайней мере для опередлённого класса задач.
Хвостовая рекурсия
Преобразования не являются оптимизирующими, то есть полученная программа выполняет те же действия, что и исходная. Более того, вполне возможно, что умный транслятор сможет реализовать исходную программу даже более эффективно, чем полученную, за счёт использования специальных машинных инструкций для доступа к локальным объектам и возврата из процедур, а также ввиду неспособности анализировать сложное управление с использованием переходов по вычисляемым меткам.
Некоторые программы могут быть переведены в итеративную форму, не требующую создания многих поколений локальных объектов. В частности, это возможно, если все процедуры используют только так называемую хвостовую рекурсию, при которой любой вызов процедуры является последним действием вызывающей процедуры, не имеющим доступа к локальным объектам вызывающей процедуры. В некоторых случаях процедура может быть преобразована к хвостовой рекурсии путём введения накопительных параметров. Рассмотрим этот приём на примере той же функции возведения в степень, которая уже была предварительно преобразована в процедуру:
void power(int n, float x, float * result)
{
if (n==0)
*result = 1;
else
{
float t;
power(n-1,x,&t);
*result = x * t;
}
}
Заметим, что она не удовлетворяет требованию хвостовой рекурсии, поскольку, во-первых, после вызова power ещё выполняется присваивание результату, и, во-вторых, вызову передаётся ссылка на локальную переменную t, которая внутри вызова может быть изменена и на самом деле меняется присваиванием *result.
Заведём дополнительный параметр total, который будет накапливать то значение, которое нужно выдать в качестве результата по завершению рекурсии. При первом вызове в качестве этого параметра должно быть передано значение 1. После этого станет ненужной локальная переменная t, поскольку результат сразу можно записывать по назначению.
void power(int n, float x, float total, float * result)
{
if (n==0)
*result = total;
else
power(n-1,x, x*total, result);
}
Свойства хвостовой рекурсии обеспечивают возможность не создавать новый фрейм перед рекурсивным вызовом, а использовать текущий, изменив в нём поля, соответствующие формальным параметрам, на значения фактических, и передать управление на начало процедуры. Кроме этого, формальный параметр total можно сделать локальной переменной с соответствующей инициализацией:
void power(int n, float x, float * result)
{
float total = 1;
entry:
if (n==0)
*result = total;
else
{
n = n-1;
total = x * total;
goto entry;
}
}
Легко заметить, что тело цикла можно преобразовать в цикл for:
void power(int n, float x, float * result)
{
float total;
for (float = 1; n!= 0; total*=x, n--);
*result = total;
}
Вложенные процедуры
Вернёмся к программе вычисления полинома. Можно заметить, что параметр x, передавемый в вызове power в функции poly дальше передаётся без изменений в рекурсивные вызовы. В результате все поколения переменной x имеют одно и то же не изменяемое значение. Оно копируется в каждом фрейме, что требует как времени, так и памяти. Однако, функция power не может обратиться непосредственно к параметру x функции poly ввиду ограничения на видимость объектов. Конечно, можно было бы сделать переменную x глобальной, но тогда она будет существовать всё время выполнения программы, и её смогут изменить и другие процедуры. Выход из этого положения дают вложенные процедуры, которые имеются во многих языках программирования, например, в Паскаль и в некоторых расширениях языка C. В данном примере описание функции power помещается внутрь описания функции poly:
float poly(float coef[], n,float x)
{
Float power(int n)
{
return n==0?1:x*power(n-1);
}
float sum = 0f;
for (int i=0; i<=n; i++)
sum += coef[i]*power(i);
return sum;
}
Согласно правилам видимости типерь использование x внутри power обращается объекту в ближайшем охватывающем блоке, в котором описано x, т.е. к параметру функции poly. Конечно, в результате функция power становится недоступной вне функции poly.
На первый взгляд, мы добились желаемого результата, однако, побочным эффектом такого преобразования является то, что становится неверным предположение о том, что любая функция имеет доступ только к глобальным переменным и своим локальным объектам. Теперь при обращении к x внутри power необходим текущий фрейм функции poly. Это можно сделать разными способами. Например, можно в каждом фрейме в качестве первого поля завести признак, определяющий функцию, к которой он относится, и в тот момент, когда потребовалась переменная или параметр охватывающей процедуры, пробежать по ссылкам на охватывающий фрейм до тех пор, пока не будет найден требуемый. Понятно, что сложность доступа при такой реализации может быть пропорциональна глубине рекурсии, что во многих случаях неприемлемо. Другой подход заключается в том, чтобы для каждой процедуры поддерживать ссылку на фрейм, содержащий последнее поколение локальных объектов. Так или иначе, вложенные процедуры облегчают собственно вызов процедуры, но достаточно существенно затрудняют доступ к локальным объектам.
К достоинствам вложенных процедур можно отнести и то, что они облегчают процесс свёртки. Допустим, мы обнаружили, что некоторый фрагмент кода нужно выполнить ещё в нескольких местах и для этого его нужно офоримить в виде процедуры. Если язык не поддерживает вложенных процедур, то все локальные объекты, которые используются в данном фрагменте кода, придётся сделать формальными параметрами и передавать их при вызове, а если их достаточно много, то это опять же скажется на эффективности. Большинство современных языков программирования в том или ином виде поддерживают вложенность процедур и функций.
Оптимизации
Если уж мы заговорили об оптимизации, то рассмотрим наш пример на основе анализа сложности вычислений. Использованные ниже методы достаточно характерны при оптимизации программ. Будем оценивать сложность в количестве выполненных операций умножения. В тексте она встречается дважды: один раз в функции poly и один - в power. Поскольку всё управление в обеих функциях полностью определяется параметром n, мы можем сопоставить каждой функции другую функцию, которая вычисляет сложность: Tpoly и Tpower. Для исходной программы c рекурсивной реализацией power несложно показать, что
Очевидно, что Tpower (n) = n, и следовательно,
Что касается ёмкостной сложности, то она определяется максимальной глубиной в дереве вызова, которая равна n. Преобразование функции power путём приведения её к хвостовой рекурсии не изменяет количество операций, но уменьшает ёмкостную сложность до константы.
Большинство умножений происходит в функции power. Следуя принципу оптимизации наиболее горячих точек, займёмся ею в первую очередь. Можно попытаться реализовать функцию power за счёт использования стандартных функций, например, как
float power(int n, float x)
{
return exp(log(x)*i);
}
но так мы просто прячем от себя сложность, оставляя в функции единственное умножение, игнорируя при этом неизвестное и явно не малое количество умножений, выполняемых при вычислении экспоненты и логарифма.
Мы уже рассматривали способ возведения в степень, который может быть записан как
float power(int n, float x)
{
float y = 1;
while (n) n&1? (y*=x,--n): (x*=x,n/=2);
return y;
}
Оставим в качестве упражнения доказательство с использованием аксиоматической семантики того, что количество умножений здесь не превосходит 2*log(n +1), и тогда
Сумму логарифмов можно оценить, используя формулу Стирлинга,
то есть
и асимптотически
Теперь заметим, что на каждой итерации цикла в функции poly результат функции power отличается от предыдущего в x раз. Это даёт возможность вообще исключить функцию power, введя вместо неё вспомогательную переменную:
float poly(float coef[], int n, float x)
{
float sum = 0f;
float power;
int i;
for (i=0,power=1f; i<=n; power*=x,i++)
sum += coef[i] * power;
return sum;
}
Это приводит к тому, что количество умножений становится равно
.
Наконец, вспоминая из школьной программы схему Горнера, мы можем реализовать вычисление полинома как
float poly(float coef[], int n, float x)
{
float sum = coef[n];
for (i=n-1; i>=0; i--)
sum = sum * x + coef[i];
return sum;
}
где требуется лишь n умножений.
Таким образом, наибольший эффект достигается использованием эффективных методов. Однако и систематическая оптимизация, такая как нахождение индуктивных переменных, замена рекурсивных программ итеративными и т.д. может привести к существенному повышению эффективности. Нельзя рассчитывать на то, что всё это за нас сделает транслятор.
