Готовый перевод Functional C / Функциональный C: Глава 2 - Функции и Числа

Функциональное программирование в SML и императивное программирование в C имеют много общего. Цель этой главы - показать, что когда уже есть SML решение проблемы, то решение проблемы на C может быть найдено без больших трудностей. Представленные здесь решения на C не обязательно будут лучшими с точки зрения их эффективности, но послужат хорошей отправной точкой для разъяснений в последующих главах. В настоящей главе мы подчёркиваем различия между вычислением с точки зрения математики и вычислением, выполняемым на компьютерах. Мы подкрепляем эту разницу вводя модель вычисления и мы иллюстрируем концепции решая ряд демонстрационных проблем.

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

2.1 Модель вычисления

Программист решает задачу через написание компьютерной программы. Тогда ответом на задачу будет являться результат, данный программой. Прежде всего программист должен понимать решаемую задачу. Также программист должен понимать каким образом работают компьютеры, поскольку программы - это всего лишь инструкции компьютеру, по которым компьютер выполняет определённые вычисления в определённом порядке. Без такого понимания программист может попытаться дать компьютеру инструкцию выполнить операции, которые нельзя выполнить не растратив данные ресурсы, или ещё хуже, программист может попытаться заставить компьютер выполнить невыполнимые операции. В сравнении с компьютерным мозгом, компьютеры чрезвычайно ограничены в том, что они могут сделать. С другой стороны, компьютер может выполнять некоторые операции быстрее и аккуратнее чем человеческий мозг. Вычислительная модель - это базовое понимание того, что компьютер может сделать и как он это делает. Мы сформулируем две такие модели, одна из них применима при написании SML программ, а другая применима для написания C программ.

2.1.1 Вычислительная модель для SML программ

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

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

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

Также SML программисту нужно знать как вычисляется выражение. Положим что выражение состоит из названия функции и списка аргументов значений, к которым применяется функция. Механизм, используемый в вычислении выражения, состоит из четырёх шагов:

Выполняется поиск именованной функции в списке известных определений функций.

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

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

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

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

Рассуждения о поведении программ - это важный аспект программирования, и вычислительная модель даёт программисту инструмент для выполнения подобных рассуждений.

2.1.2 Вычислительная модель C программ

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

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

В простой вычислительной модели, C программы - это список определений функций. Одна из функций должна обладать именем main. Эта функция играет ту же роль, что и главное выражение в SML программах. В простой модели выражения вычисляются как и в SML. Разница в том, что C функции состоят не из чистых выражений, а из операторов. Оператор - это операции над состоянием программы, через исполнение операторов в правильном порядке, программа достигает результата. В этой главе мы будем использовать только три оператора:

Оператор return завершает выполнение функции и возвращает значение результата.

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

Оператор if выполняет другие операторы в зависимости от условий.

В последующих главах, мы постепенно будем вводить остальные операторы C. В этой главе мы не будем использовать никаких состояний, концепция хранилища будет введена в Главе 3. Следующий код демонстрирует простую C программу:

/* Простая C программа, она печатает Hello World */
int main( void ) {
printf( "Hello world\n" ) ;
return 0 ;
}

Текст между "/*" и "*/" - это комментарий, он игнорируется компилятором C. Первый оператор функции main:

printf( "Hello world\n" ) ;

Этот оператор не возвращает полезное значение; всё его назначение - напечатать текст Hello world как побочный эффект. Второй оператор:

return 0 ;

Исполнение этого оператора приведёт к тому, что значение 0 будет передано как значение выражения main(). Вышеприведённая программа main показывает, что тело функции в C состоит из ряда операторов. Вычислительная модель предписывает, что эти операторы исполняются в том порядке, в котором они записаны.

2.1.3 Компиляция и исполнение C программ

После того как C программа будет написана, её нужно скомпилировать и выполнить. Здесь мы дадим минимальное введение в компилирование программы записанной в один файл. Компиляция программ, состоящих из нескольких файлов описана в Главе 8. В UNIX системах (или их эквивалентах, например, LINUX, AUX, AIX и т.д.), C программа должна быть сохранена в файл, название которого заканчивается на .c. Программа может быть скомпилирована вызовом C компилятора, cc:

cc -o monkey hello.c

Так будет скомпилирована программа hello.c. На экран будут выведены все сообщения об ошибках, и если работа компилятора завершится кодом, исполняемым файлом, то в этом случае будет создан файл monkey. Программу можно запустить напечатав monkey:

Hello world

Системы новее, такие как Макинтоши или PC позволяют пользоваться интергрированными средами, такими как Codewarrior или Borland C. В них программа может быть скомпилирована и выполнена из редактора. Здесь невозможно дать исчерпывающее описание этих систем, за сведениями о редактировании, компилировании и исполнении программ в этих системах обращайтесь в соответствующие руководства.

2.2 Простейшие функции

Теперь мы готовы изучить интересный алгоритм. Наибольший общий делитель (НОД - gcd) двух положительных целых чисел - это наибольшее целое число, на которое делятся эти оба числа. НОД 14 и 12 равен 2, в то время как НОД 14 и 11 равен 1. НОД двух чисел задан описанием:

Стандартный алгоритм вычисления НОД-а следует методу Евклида. Если, для двух положительных целых чисел m и n, мы имеем m>n, то НОД m и n определяется так:

Что можно прямо записать в SML:

(* euclid : int -> int -> int *)
fun euclid m n = if n > 0
then euclid n (m mod n)
else m ;

Следующие строки показывают результаты применения функции euclid к набору некоторых аргументов:

euclid 14 12
= 2 ;
euclid 14 11
= 1 ;
euclid 558 198 = 18 ;

Теперь мы дадим 'рецепт трансформации' для создания C функции из SML функции. Такой рецепт, позже мы его покажем, позволяет систематично трансформировать SML код в C. Его важность в том, что если мы начнём с испытанной и проверенной SML функции, то хорошая C функция будет результатом систематичной трансформации. В целом это означает, что программисту достаточно подумать над созданием функционального решения, после чего скрупулёзно выполнив требования рецепта он получит хорошую C реализацию.

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

(*схема SML функции*)
(*
:
 -> ...
 ->
 *)
fun 
 ... 
= if 
then
else  ;

Эта схема выглядит несколько усложнённой поскольку она пытается соответствовать как можно большему классу функций. В частности запись x1 ... xn обозначает как единственный x, так и n-ое число различных переменных x. Символы курсивом в схеме функции следует интерпретировать так:

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

Число n обозначает число аргументов функции f.

x1 ... xn - аргументы f.

t1 ... tn - это соответствующие типы аргументов x1 ... xn.

tr - тип результата функции.

Выражение p - некоторое условие для x1 ... xn.

Выражения g и h - это выражения, подразумевающие использование значений x1 ... xn.

Ниже показана C версия схемы функции, соответствующая вышеприведённой схеме SML функции:

Символы в этой схеме должны интерпретироваться также, как и прежде, но необходимо брать в расчёт некоторые синтаксические отличия между SML и C.

Идентификаторы в SML могут содержать некоторые символы, не допустимые в C. Эти символы должны быть заменены. Требования для идентификаторов C будут обсуждены позже на странице 13.

Базовые типы в SML те же, что и в C, но некоторые должны быть изменены. Например, real в SML соответствует double в C. Список базовых типов дан в конце этой главы.

Многие операторы, используемые в SML программах также могут быть использованы в C программах. Операторы C обсуждаются в Разделе 2.2.4.

В C не разрешены каррируемые функции, поэтому для всех функций необходимо предоставлять требуемые аргументы.

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

Создание C версии euclid теперь просто сводится к сбору информации с третьей колонки и подстановке этой информации в правильные места схемы C функции. Получится следующее:

Процесс трансформирования SML функции в C трудоёмок, но не труден. Часто мы будем молчаливо предполагать, что все шаги трансформации были выполнены и уже существует чистый результат трансформации.

Причина, по которой был выбран euclid, заключается в том, что его C реализация близка к математической и функциональной версиям. В виде завершённой программы C реализация euclid показана ниже.

Эта программа показывает следующие лексические соглашения C:

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

Идентификаторы в C состоят из последовательности букв (важен регистр букв), нижнего подчёркивания ("_") и цифр. Первым символом идентификатора должна быть либо буква, либо нижнее подчёркивание. Примеры корректных идентификаторов: monkey, Monkey, ___123 или an_id_13.

C версия программы euclid начинается с директивы включения (include):

Эта директива говорит компилятору о необходимости включить текст из файла stdio.h в это место. Это необходимо для того, чтобы программа могла использовать возможности ввода и вывода. Директива include и многие другие будут обсуждаться в Главе 8 (в модулях); а сейчас эта директива просто будет использоваться в каждой нашей программе.

После директивы include определены две функции: euclid и main. Каждая функция состоит из заголовка функции, определяющего тип результата функции и имя и тип аргументов функции, тело функции, заключённое в фигурные скобки, определяет поведение функции. Ниже мы обсудим заголовки функций, тело функции и их исполнение в C программах.

2.2.1 Заголовок C функции, типы и идентификаторы

Заголовок первой C функции в программе следующий:

int euclid( int m, int n )

Определение функции euclid начинается с определения типа значения, которое возвратит функция. В этом случае int - это сокращение для типа целых чисел. SML эквивалент для этого типа - также int.

После типа функции, определено имя функции (euclid) после чего, между скобками, даны типы и имена аргументов функции. В этой функции есть два аргумента. Для первого аргумента типом является int и имя m, для второго аргумента (после запятой) снова тип int, а имя n. Имена аргументов m и n нужны для того, чтобы сослаться на первый и второй аргумент в теле функции.

Определение main такое:

int main( void )

Заголовок указывает, что функция с именем main вернёт значение с типом int. Список аргумента определён как void, что означает что функция main не имеет аргументов.

В C каждая функция должна быть определена до её использования. Поскольку функция main ссылается на euclid, то euclid должен быть определён до main. Определение функций в другом порядке также может сработать (если компилятор C поддерживает корректное определение типов функций), но это нехорошая практика и лучше не полагаться на неё.

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

int euclid( int m, int n ) ;
int main( void ) ;

В большинстве функциональных языках программирования, типы автоматически выводятся компилятором. Хорошим функциональным стилем программирования является обязательное определение типов функций, так компилятор может проверить что тип определённый пользователем совпадает с выведенным типом. Любое несоответствие будет обозначено как ошибка в программе. В C программист должен определять все типы.

2.2.2 Тело C функции и её поведение

После определения типов функции и её аргументов определяется код функции. В императивном языке этот код состоит из последовательности операторов. Оператор - это команда, выполняющая некоторую разновидность операции. Как это показано в деталях в Разделе 2.2.3, функция вычисляется с помощью поочерёдного вычисления каждого оператора.

В C каждый оператор заканчивается точкой с запятой. Несколько операторов логически представляющих один оператор могут быть сгруппированы с помощью фигурных скобок. Тело функции - это группа операторов, заключённых в фигурные скобки. Функция euclid содержит две разновидности операторов: оператор return и оператор if.

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

Оператор if имеет следующую общую форму:

Что можно читать так: если условное выражение p вычисляется в истину, то исполнить операторы T, иначе исполнить операторы F. Для обозначения мест, где могут быть вставлены операторы мы обычно используем заглавные курсивные буквы. В вышеприведённом операторе if вместо T или F могут быть вставлены любые операторы. Также оператор if может использоваться без необязательной else части:

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

Выражения в C подобны функциональным выражениям, с единственным исключением: они используют несколько отличный синтаксис. Например, аргументы функции должны быть отделены запятыми и заключены в скобки. Таким образом, выражение записываемое в функциональном языке как f x y в C будет записано как f(x, y). Также отличается синтаксис операторов: например, x mod y в C будет записан как x%y. Большинство других операторов остаются неизменными и обладают своими обычными значениями (краткое описание полного списка дано в Разделе 2.2.4). Этой информации достаточно для интерпретации тела функции euclid:

Если n больше нуля, исполняется часть then:

Иначе, если n не больше нуля, исполняется часть else:

Первая из этих двух операторов обозначает возврат функции, если говорить более точно, то значение выражения euclid(n, m%n) возвращается в виде значения, возвращаемого функцией. Второй оператор обозначает возврат значения m (в этом случае значение n равно 0).

Ключевое слово else в операторе if в данной частичной функции избыточно. Рассмотрим два оператора:

Первый из них, оператор if, исполнит нижележащий оператор если n больше чем нуль:

Если выполнен return, то функция завершится без выполнения любых других операторов. Так второй оператор, return m, исполнится только тогда, когда n равен нулю. Мы вернёмся к избыточному оператору else в следующем разделе.

Тело функции main содержит 4 оператора. Первый оператор:

Вызов функции printf. Этот вызов содержит два аргумента: первый аргумент - это строка "%d\n" и второй аргумент - это значение, возвращаемое после вызова euclid с аргументами 14 и 12. Как мы видим, этот вызов printf печатает значение euclid(14, 12)

Два других оператора в теле main подобны первому: второй оператор печатает наибольший общий делитель чисел 14 и 11, и третий печатает наибольший общий делитель чисел 558 и 198. Последний оператор возвращает значение 0 в вызывающую среду программы. Этот вопрос будет более подробно рассмотрен в следующих параграфах.

2.2.3 Исполнение C программы

Исполнение каждой C программы начинается с вызова функции с именем main. Таким образом, каждая C программа должна иметь функцию с именем main. Помимо имени особняком стоит тип аргументов и тип возвращаемого значения main. Main всегда должен возвращать int, и если для main существуют аргументы, то они должны следовать синтаксису, обсуждение которого приводится в Главе 8, посвящённой работе со средой. На данный момент все функции main будут без аргументов и всегда будут возвращать значение 0. Это значение будет интерпретироваться средой как 'всё в порядке, программа завершилась удовлетворительно'.

При исполнении main должен выполниться первый оператор программы. В случае с демонстрационной программой, этим оператором является вызов printf. Язык C требует чтобы все аргументы функции были вычислены до вызова функции, подобно строгому вычислению в SML. После этого значения аргументов будут переданы в функцию. Этот механизм известен как вызов по значению. Другим способом передачи аргументов является вызов по ссылке, обсуждаемый в Главе 4.

Первый аргумент переданный в printf, строка "%d\n", - является константой, поэтому для него нет нужды в вычислении. Второй аргумент - выражение:

Выражение представляет вызов функции, которая будет вычисляться первой. Однако, до того как будет выполнен euclid, будут вычислены его аргументы. Эти аргументы - константы (целые числа 14 и 12), поэтому euclid будет вычислен непосредственно, с m обладающим значением 14 и n обладающим значением 12. В итоге, когда euclid вернёт значение, будет вызван printf.

Первый оператор euclid-а проверяет является ли n больше чем 0. Поскольку это истинно, то выполняется оператор then. Это приведёт к тому, что будет вызвана функция euclid с аргументами 12 и 14%12, что равно 2. Следовательно, euclid будет вызван снова с m равным 12 и n равным 2.

Первый оператор euclid-а опять проверяет, является ли n большим чем 0. Это истинно, поэтому будет выполнен оператор then. Это приведёт к тому, что функция euclid будет вызвана с аргументами 2 и 12%2, что равно 0. Таким образом, euclid будет вызван с m равным 2 и n равным 0.

Первый оператор euclid-а опять проверяет, является ли n большим чем 0. Поскольку это не истинно, то будет выполнен оператор else, который приведёт к тому, что выполнится return m функции, что в свою очередь вернёт значение 2. Это значение будет возвращаться каждым предыдущим вызовом euclid, до тех пор, пока не дойдёт до функции main в котором аргументы printf, будучи полностью вычисленными, дадут:

Вызывается функция printf, она будет печатать первый аргумент в поток вывода; однако; она особым образом обрабатывает знак процента. Каждый раз, когда printf встречает %d, она заменяет %d десятеричным отображением целого числа, полученного из списка аргументов. В этом примере, печатаемым значением является 2, которое только что было вычислено. Переход на новую строку, как и в SML обозначается как \n. Следовательно, получившийся вывод:

Так завершается исполнение первого оператора main. После завершения работы первого оператора, исполняется следующий оператор main. Опять это вызов printf. Первый аргумент этой функции - строка константа, и следующий аргумент - опять вызов функции euclid, на этот раз с аргументами 14 и 11. Euclid вызван с m равным 14 и n равным 11. Вместо того, чтобы долго описывать вызов одной функции из другой функции, мы опишем трассировку вызовов функций таким образом:

Цепочка вызовов вернёт значение 1, что и напечатается главной программой.

Упражнение 2.1 Сколько раз будет вызвана функция euclid при исполнении третьего оператора main?

2.2.4 Целые числа

Пример euclid работает с целыми числами которые относятся к C типу int. Существует много способов описания целочисленных констант в C. Самой общей формой является использование десятичного представления, как это было использовано до этого. 13 обозначает целое число 13. Знак минуса может использоваться для обозначения отрицательных значений, пример -13. Вторая форма - это определение чисел с различной основой, либо 8, либо 16. Шестнадцатеричные значения (использующие основу 16) могут записываться после букв 0x. Так 0x2C и 44 оба относятся к одному и тому же числу. Восьмеричные числа (с основой 8) должны начинаться с цифры 0. Так 0377, 0xFF и 255 все определяют одно и то же число.

Операторы, которые можно применять к целым числам, описаны ниже вместе с математическими и SML эквивалентами.

Унарный плюс
Унарный минус
Побитовое отрицание
Унарные

Умножение
Деление
Остаток
Сложение
Вычитание
Побитовый сдвиг влево
Побитовый сдвиг вправо
Побитовое И
Побитовое ИЛИ
Побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ

Есть одна группа операторов, которые не имеют SML эквивалента: битовые операции. Битовые операции используют двухсоставную бинарную интерпретацию целочисленных значений. Оператор ~ инвертирует все биты, операторы &, | и ^ выполняют побитовое И, ИЛИ и ИСКЛЮЧАЮЩЕЕ ИЛИ для двух битовых наборов. Всё нижеследующее истинно:

Операции << и >> сдвигают битовый набор на заданное число позиций: x<<i - сдвигает x на i позиций влево, и y>>j - сдвигает y на j позиций вправо. Некоторые примеры:

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

Тип int - это только один из нескольких C типов которые можно применять для работы с целыми числами. Прежде всего, C поддерживает тип unsigned int. Ключевое слово unsigned обозначает, что все значения этого типа не могут быть отрицательными. Самым важным свойством типа unsigned int являются математические операции с гарантированной модульной арифметикой. Таким образом, если результат некоторой операции превысит ограничения, накладываемые типом, то в качестве ответа будет использоваться модуль некоторой большей степени двойки. Повторно прибавляя единицу к unsigned int на машине с 32-х битовым целым числом мы получим серию 0, 1, 2, ..., 4294967294, 4294967295, 0, 1, .... Модульная арифметика удобна в случаях, когда нужна более длинная арифметика (например, 128-битное число). В Разделе 2.3.3 будут кратко описаны другие типы целых чисел.

2.2.5 Логические операторы

Язык C не содержит отдельного типа для булевых значений, в качестве булевых значений используются целые числа. Операторы сравнения, перечисленные ниже, возвращают целые числа 1 или 0; 1 обозначает истину, а 0 - обозначает ложь.

Значение
Меньше чем
Меньше чем или равно
Больше чем или равно
Больше чем
Равно
Не равно

C предоставляет три традиционных логических оператора. Операндами и результатом являются целые числа:

Значение
Логическое отрицание, !0==1, !x==0 (если x!=0)
Логическое И
Логическое ИЛИ

Оператор ! выполняет операцию логическое отрицание (НЕ), !0 - это 1, и !1 - это 0. Дополнение: оператор отрицания в C расценивает истинным любое не нулевое значение, поэтому !153 - это 0.

Оператор && обозначает логическую конъюнкцию (И), а оператор || обозначает логическую дизъюнкцию. Примеры некоторых истинных отношений этих операторов:

Логические && и ||, как и оператор !, оба считают истинным любое ненулевое значение. Производимые операции операторов && и || идентичны их SML эквивалентам, но отличаются от их аналогов в некоторых других императивных языках. Рассмотрим следующее выражение:

В этом выражении вначале проверяется равенство нулю переменной x. Если x равно нулю, то остальная часть выражения не вычисляется (поскольку 0&&... равно 0). Неравенство y/x < 20 будет вычисляться только тогда, когда x не равно нулю. Это поведение называется семантикой сокращённого вычисления. В Паскале подобное сравнение может выглядеть так:

Семантика Паскаля такова, что данное выражение приведёт к ошибке если x равно нулю, поскольку (y/x < 20) вычисляется вне зависимости от того равен x нулю или нет.

Не путайте операторы &&, || и == с их непарными эквивалентами - &, | и =. Операторы & и | - это битовые операторы, и единственный знак равенства, =, ведёт себя отлично от ==. Эта тема будет обсуждена в следующей главе. Случайное использование = вместо == может привести к тому, что синтаксически корректная программа может вести себя не так, как ожидалось. Иногда довольно сложно обнаружить эту ошибку.

Последний логический оператор, поддерживаемый C - это тернарный оператор if-then-else, обозначаемый знаком вопроса и двоеточием: c?d:e обозначает следующее: если c вычисляется в не-нулевое значение, то выбирается значение d, в противном случае будет выбрано значение e.

2.2.6 Определение Булевых типов, typedef и enum

Официальный способ обозначения истинных значений в C - это 0 и 1, но для того, чтобы у программы, использующей логические операции, была аккуратная структура часто для удобства вводят новый тип для булевых значений. Следующая строка в начале программы заботится об этом:

Эта строка состоит из двух логических частей. Внешняя часть

Ключевое слово typedef ассоциирует тип T с именем типа, в данном случае с bool. Тип может быть любым встроенным типом (например, int), или типом, созданным пользователем, таким как enum{false=0, true=1}. Ключевое слово enum используется для определения перечисляемого типа. В нашем случае - два элемента, false и true, где false содержит числовое значение 0 и true содержит числовое значение 1. Общая форма перечисляемых типов такая:

Здесь i0, i1, i2, ... - нужные нам идентификаторы. Идентификаторы представлены как целые числа. Идентификаторы могут быть привязаны к определённым целым числовым значениям, как это было показано в определении типа bool. У комбинации typedef с enum есть свой аналог в SML:

В следующем C фрагменте определён перечисляемый тип language:

Это эквивалент следующего SML определения:

2.3 Символы, сопоставление с образцом, частичные функции

Уже достаточно долго мы обсуждали целочисленные и булевы типы данных, теперь рассмотрим другой полезный тип данных, символ. Символ - это стандартный скалярный тип данных входящий во многие языки включая C. Интересный факт: символ - это не стандартный тип данных в SML. Вместо этого в качестве базового типа данных в SML предлагается строка. Во всех языках предлагающих символ в качестве базового типа данных строки рассматриваются как структурный тип данных, то есть, типы данных строятся из более простых типов данных. Структурные типы данных в деталях будут рассмотрены в Главе 4 и последующих главах. Для того, чтобы преодолеть некоторое неудобство SML мы положим, что строка SML содержит ровно один элемент - символ. Тогда SML тип char можно определить так:

В качестве примера функции, работающей с символами, рассмотрим спецификацию для вычисления выражений. Возьмём выражение, которое состоит из трёх целых чисел и двух операторов (+ и *), подлежащее вычислению. Правила, описывающие приоритет операторов (умножение имеет больший приоритет над сложением) даны ниже. Здесь множество A представляет все возможные символы.

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

Функция eval принимает 5 аргументов: 3 целых числа и 2 символа. Целые числа представлены как значения x, y и z, а два символа определяют выполняемые операции. Сопоставление с образцом используется для того, чтобы определить какой из четырёх альтернатив следует выбрать. Сопоставление с образцом позволяет писать чистые и лаконичные программы и, как общее правило, следует придерживаться этого стиля программирования. Однако, C не поддерживает сопоставления с образцом, вместо этого сопоставление с образцом реализуется через использование операторов if.

2.3.1 Реализация сопоставления с образцом в C

В качестве подготовки к реализации eval в C, рассмотрим как реализовать эту функцию в SML через условные операторы. Это не трудно, поскольку выше функция уже была реализована с помощью сопоставления с образцом.

Последний оператор else raise Match; чётко определяет что должно случиться если eval будет применён к паре операторов отличающихся от "+" и "*". Спецификация eval, и сопоставление с образцом eval должны явно обрабатывать этот случай. В последнем примере обработка ошибочной ситуации заключается в генерировании исключения Match, но это выполняется неявно. Мы отложили решение этой проблемы на последний момент для того чтобы показать что теперь мы вынуждены думать об отсутствующей части спецификации: просто опустив оператор else raise Match; мы получим синтаксическую ошибку. Спецификация проблемы только частично определяет решение. Функция eval является частичной функцией - функцией, неопределённой для некоторых его аргументов.

Эта, использующая условия, версия eval может быть трансформирована в C программу, используя схему тем же способом, которым была трансформирована функция euclid. Однако, нам нужна новая схема, поскольку функция eval содержит вложенные условия, в то время когда схема функции из Раздела 2.2 поддерживает только единственное условие. Разработка этой схемы будет темой нижеследующего Упражнения 2.2. Ну а сейчас, мы просто дадим C версию eval.

В C тип char включает в себя все значения символов. Константы символов записываются между одинарными кавычками. Код ниже не завершён поскольку мы ещё разобрались с /* raise Match */. Окончательное решение мы отложим до Раздела 2.3.2, ну а пока удовлетворимся только структурой eval.

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

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

Упражнение 2.2. Схема функции из Раздела 2.2 поддерживает только одно условие. Обобщите эту схему так, чтобы поддерживать вложенные условия, использованные в последних вариантах SML и C версий eval.

Упражнение 2.3. Дайте таблицу соответствия для eval, с использованием схемы функции из Упражнения 2.2.

Как было оговорено ранее, в данном случае else-ы избыточны поскольку каждая ветка возвращается немедленно. Исправим это положение другой эквивалентной программой:

В процессе выполнения вышеприведённой формы eval четыре оператора if будут выполняться один за другим до тех пор, пока не будет достигнуто совпадение с одним из операторов. Что выбрать: конструкции else if или последовательные if операторы - это дело вкуса. Первая форма более элегантна поскольку она не полагается на оператор return завершающий функцию. Поэтому мы выберем эту форму.

Последовательность операторов if не эффективна. Допустим, что o1 равен '*', а o2 равен '+'. Первые два if оператора отпадают (поскольку o1 не равен '+'). Обнаруживается совпадение с третьим if оператором, поэтому будет возвращено значение (x*y)+z. Для o1 выполняется две проверки: двойное сравнение с символом '+', где достаточно одного сравнения. Для того, чтобы убрать вторую проверку из кода надо реструктурировать программу. Вначале нужно выполнить проверку первого оператора. Если он равен '+', то вложенные if операторы будут использованы для определения, какое из двух альтернатив следует вычислить. Аналогично, требуется ещё один оператор if для проверки на равенство первого оператора и '*'. В этой ситуации вложенные операторы if будут определять какой из оставшихся двух альтернатив следует выбрать. Что даёт нам следующее определение eval:

Упражнение 2.4. Можете ли вы разработать схему трансляции между сопоставлением с образцом SML кода и C кода, использующего вложенные if-then-else? Если нет, то в чём проблема?

Приведённая программа имеет функциональный эквивалент, не настолько удобный для чтения даже несмотря на то, что мы ввели две вспомогательные функции xymul и xyadd для облегчения понимания.

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

2.3.2 Частичные функции

Функции, использующие сопоставление с образцом или условия часто определены частично. Это означает что функция не определена для всей задачи: есть аргументы, для которых функция не определена. Мы увидели, что версия eval c сопоставлением с образцом определена только для операторов из множества {+, *}. Попытка вызвать SML функцию eval 6 "/" 3 "+" 4 в версии с сопоставлением с образцом приведёт к ошибке времени исполнения. Программа прервётся, поскольку ни одно из определений eval не соответствует вызову.

Если бы мы могли оставить неоконченное определение else /*raise Match*/ из нашей C версии eval, то вызов eval(6, /, 3, +, 4) в C реализации привёл бы к результату из неопределённого значения. Поскольку заданным аргументам не соответствует ни один if оператор, то конец функции будет достигнут без исполнения оператора возврата. После чего функция вернёт некоторое произвольное, неизвестное значение. Продолжение вычислений на основе этого неизвестного значения не имеет смысла, поэтому хорошей практикой будет предотвращение этого случая. Решением будет вызов функции abort(), доступной из stdlib.h:

Вызов abort() приводит к тому, что C программа немедленно прекращает работу, рапортует об ошибке времени исполнения, и часто вызывает отладчик или оставляет дамп памяти. После чего программист может исследовать упущенные случаи. Часто среда позволяет программисту определить причину прерывания программы, но хорошей практикой является вызов printf непосредственно до прерывания программы:

Exit - функция, родственная abort-у. Вызов функции exit завершит программу. В отличие от abort-а, функция exit вызовет корректное завершение работы программы: abort используется для подачи сигнала о программной ошибке (например, об отсутствующем варианте), exit используется для подачи сигнала о пользовательской ошибке, или просто останавливает программу. Функция exit имеет целочисленный параметр. Значение 0 обозначает что программа сработала удачно, любое другое значение обозначает что что-то пошло не так. Это число играет ту же роль, что и число возвращаемое в качестве значения от main-а при нормальном завершении работы программы.

2.3.3 Различия и схожести между символами и целыми числами

Константы символов обозначаются между одинарными кавычками: константы * и + уже были нами рассмотрены. Таким образом можно обозначить большинство символов, но для некоторых символов требуется экранирующий обратный слэш как в SML. Например, для обозначения одной одинарной кавычки требуется написать \. Наиболее важными обратными кавычками являются следующие:

\a Звуковой сигнал (тревога)
\b Backspace (удаление одного левого символа)
\f Прогон страницы (новая страница или очистка экрана)
\n Новая строка
\r Возврат каретки (начать заново с той же строки)
\t Табуляция (переход к следующей позиции табуляции)
\v Вертикальная Табуляция (переход к следующей вертикальной позиции табуляции)
\\ Обратная косая черта (\)
\ Одинарная кавычка " "
\" Двойная кавычка """
\0 NULL-символ (значение 0)
\ddd ddd должно быть трёхзначным восьмеричным числом
\xdd dd должно быть двухзначным шестнадцатеричным числом

Тип char считается отдельным типом, но на самом деле этот тип является частью семейства целых чисел. В C символы кодируются их целочисленными эквивалентами. Это означает, что символ 'q' и целочисленное значение 113 на деле равноценны (полагаем что используется кодировка ASCII). Обозначение что аргумент принадлежит к типу char означает что аргумент - малая целочисленная константа. Тип char покрывает все целые числа необходимые для кодирования набора символов.

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

Однако, следующие (не)равенства тоже истинны:

В C следует проявлять осторожность при использовании операций сравнения между символами и целыми числами.

Для печати символа функция printf поддерживает формат %c. В качестве примера, следующее выражение выведет на печать букву q:

Ничего нельзя утверждать о знаке значений символов. Символы хранятся в малых целых числах, но решение о том, какие целые числа (со знаком или без знака) будут использоваться зависит только от системы. В следствии этого сравнение двух символов c>d может отличаться от проверки c-d>0 (поскольку при использовании без знаковой арифметики последнее значение будет ложным только если c равен d). Больше о символах, в частности о том, как считать символы с входных данных можно узнать из Главы 7.

Упражнение 2.5 В данном упражнении символ 'q' кодируется машиной как 113, а символ '0' через 48, каким будет вывод следующей программы?

Для того, чтобы эффективно работать с различными наборами символов, в C поддерживается ряд стандартных предикатов для классифицирования символов. Например, предикат isdigit можно использовать для определения символов, обозначающих цифры 0, 1, ..., 9. Самыми важными являются следующие предикаты:

isdigit(c) Возвращает истину если c - цифра
isalpha(c) Возвращает истину если c - буква
isupper(c) Возвращает истину если c - буква в верхнем регистре
islower(c) Возвращает истину если c - буква в нижнем регистре
isspace(c) Возвращает истину если c - пробел (новая строка, табуляция, пробел)
isprint(c) Возвращает истину если c - печатаемый символ

Дополнительно, две стандартные функции toupper и tolower преобразуют буквы в нижнем регистре в верхний и буквы в верхнем регистре в нижний соответственно. Для использования этих функций нужно включить в программу файл ctype.h с помощью директивы include:

Обсуждение деталей директивы include можно найти в Главе 8. Примером использования этих функций является функция конвертирования символов в нижнем регистре в буквы верхнего регистра, и символы в верхнем регистре в символы нижнего регистра. Аналог в SML:

Заметьте, что реализация предполагает, что буквы верхнего и нижнего регистра последовательно упорядочены. C версия замены проверяет символы с помощью некоторых стандартных предикатов, но структура функции та же, что и в SML:

2.4 Вещественные числа

Символов и целых чисел достаточно для решения задач символьной природы. Часто для решения задач с числами предпочтительно использовать вещественные числа. Для объяснения использования вещественных чисел в C мы обсудим алгоритм, вычисляющий r^p. В этом примере в качестве r может выступать любое вещественное число, но p должно быть не отрицательным целым числом. Определение оператора возведения в степень следующее:

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

Есть p умножений, сгруппированных в две группы по p div 2 умножений, и, если p нечётно, ещё одно умножение. Группа в p div 2 умножений сокращается в выражение r^(p div 2), что даёт нам следующее рекурсивное определение оператора возведения в степень:

Читается так: любое число в степени 0 равно 1; любое число в степени нечётное-число равно число умноженное на число, возведённое в степень нечётное-число-минус-1; любое число в степени чётное-число равно квадрату числа в степени чётное-число-разделённое-на-2.

Упражнение 2.6 Исходное определение r^p (2.3) будет требовать 127 умножений для вычисления r^128. Сколько умножений потребуется выполнить для выполнения второго определения (2.4)?

Упражнение * 2.7 Докажите индукцией для p, что два определения возведения в степень, (2.4) и (2.3) эквивалентны.

Уравнение (2.4), определяющее возведение в степень и его вспомогательные функции square и odd, можно сформулировать в SML с помощью условий следующим образом:

Следующая таблица даёт ответы, получаемые после применения функции power к демонстрационному набору аргументов:

C эквиваленты этих функций и три демонстрационных вычисления показаны ниже как завершённая C программа. Была использована общая функциональная схема Упражнения 2.2 для трансформации SML функций в C.

Программа возведения в степень содержит 4 функции: square, odd, power и main. Тип bool был объявлен также, как и в Разделе 2.2.6, поэтому функция odd типизирована правильно.

Функция square возвращает значение в типе double, являющимся аббревиатурой для чисел двойной точности с плавающей запятой. Числа с плавающей запятой могут хранить дробные числа и, в целом, более широкий диапазон чисел чем целые числа. Обычные арифметические операции +, -, * и / могут выполняться в типе double. Детали чисел с плавающей запятой будут обсуждаться позже в этой главе. Для печати числа с плавающей запятой нужно соответствующим образом информировать printf. Для этого в строку формата нужно добавить %f. Функция printf не осуществляет проверки соответствия типа в строке формата с типами аргументов. Если от printf запрошена печать чего-либо в виде числа с плавающей запятой (через формат %f), но передан целочисленный аргумент, то в лучшем случае программа напечатает какое-либо непредсказуемое число, а в худшем аварийно прекратит работу.

Исполнение программы power происходит так же, как и исполнение предыдущей программы. Она начинается с main, вызывающего power до вызова printf для печати результата.

Упражнение 2.8 Сколько раз вызываются функции square и power при выполнении третьего выражения в main?

2.4.1 Приведение целых чисел и чисел с плавающей запятой

Константы, принадлежащие типу double обозначаются в научной записи с десятичной запятой и e обозначает показатель степени. Например, 3.14159 - значение пи длиной в 6 цифр. Скорость света в метрах в секунду равна 2.9979e8. Константы с плавающей запятой и целочисленные константы отличаются наличием десятичной запятой и/или показателем степени. Константа 12 обозначает целочисленную двенадцать, но 12.0, 12e0 и 1.2e1 обозначают двенадцать как число с плавающей запятой.

В C десятичные дроби и целые числа при условии соответствия конвертируются друг в друга прозрачно. Это называется приведением. Арифметические операторы перегружены: при их использовании с двумя десятичными дробями эти операторы вернут десятичную дробь число; при использовании их с двумя целочисленными значениями ответом будет целое число и если применить оператор к одному целому числу и одной десятичной дроби, то целое число будет приведено к десятичной дроби, а результат также будет десятичной дробью. И хотя такое поведение оказывается удобным во многих случаях (когда это необходимо, константа 2, принадлежащая типу int, приводится к константе 2.0 из типа double), возможны неожиданные сюрпризы. Вот несколько стандартных примеров:

И в C и в SML, значением выражения будет 3.5. В C выражение будет принадлежать к типу double; аналог в SML - real. То же самое выражение, с целым числом 5 вместо вещественного 5.0:

Если рассматривать это выражение в C, то результатом будет double 3.5. Поскольку в этом случае одним из аргументов операции деления является 2.0 - десятичная дробь - то другой аргумент будет приведён к десятичной дроби. Это означает что нужно использовать деление с плавающей запятой, а не целочисленное деление. Таким образом, перегрузка оператора деления приводит к делению с плавающей точкой. Результат деления, 2.5, складывается с 1.0 и даёт 3.5 как конечный результат всего выражения. SML не примет это выражение, поскольку в SML оператор деления / работает только для вещественных чисел. Система SML-а выдаст ошибку о конфликте типов между аргументами 2.0, 5 и оператором /.

При интерпретации выражения в C, результатом вычисления будет double 3.0. Оператор деления применяется к двум целым числам, поэтому результатом деления будет целочисленное 2. Поскольку один из операндов сложения - 1.0, то целочисленное 2 будет приведено к double 2.0, поэтому окончательным результатом выражения будет double 3.0. При интерпретации этого выражения в SML мы получим ту же ошибку, что и в предыдущем примере.

Как и в предыдущем случае оператор / применённый к двум целым числам будет интерпретирован в C как целочисленное деление. Таким образом, результатом целочисленного деления будет 2. Операнды сложения являются целыми числами, поэтому значением выражения будет целочисленное 3. При интерпретации этого выражения в SML мы получим ту же ошибку, что и в предыдущих двух случаях, на этот раз мы можем исправить положение применив оператор div.

Под капотом, числа с плавающей запятой состоят из двух частей: дробная часть (или мантисса) и экспонента. Если их соответственно обозначить как m и e, то значение числа с плавающей запятой можно определить как m*2^e. Например, число 0.375 сохраняется как мантисса 0.75 и экспонента -1. Количество бит, предназначенных для хранения экспоненты и мантиссы, - ограничено. Для примера рассмотрим расположение числа с плавающей запятой в слове из 8 бит. Для экспоненты мы выделили 3 бита и пять бит для мантиссы. Это схематичное расположение (на самом деле представление чисел с плавающей запятой выглядит по другому, для полного представления картины обратитесь к книге об архитектуре компьютера):

экспонента

мантисса

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

Мы полагаем, что экспонента хранит в себе двухсоставные числа. Битовым шаблоном для -1 является 111. Мантисса расположена так, что самый значащий бит m4 обозначает половины, следующий бит m3 обозначает четверти и так далее. Таким образом, битовым шаблоном для 0.75 будет 11000. Отсюда представление 0.375 в виде 8-битного числа с плавающей запятой будет выглядеть так:

экспонента

мантисса

Обычно, диапазон экспоненты равен 10^+-300, а точность мантиссы составляет 15 цифр. Из ограниченной точности мантиссы вытекает следствие: числа с плавающей запятой являются подмножеством вещественных чисел. Таким образом, в C можно найти два числа с плавающей запятой, скажем x и y, такие, что x не равно y и между ними не существует число с плавающей запятой. В качестве примера, в одной реализации C не существует числа с плавающей запятой между:

и

или между

и

Числа с плавающей запятой проходят через вещественные числа, хоть и маленькими шагами. Точная величина шага зависит от машины и компилятора. Такое поведение в шаге приводит к нескольким следствиям. Первое, многие числа невозможно точно представить таким образом. В качестве примера: многие компьютерные системы не могут точно представить число 0.1. Например, ближайшими числами являются следующие числа:

и

Поэтому числа с плавающей запятой нужно использовать с осторожностью: 0.1*10 не обязательно равно 1.0. В некоторых системах результат больше, чем 1; в других - результат меньше чем 1. Тест на равенство чисел с плавающей запятой, например a == 0.1, вероятно, не даст ожидаемый результат.

2.5 Функции как аргументы

До сих пор обсуждаемые функции оперировали такими базовыми значениями, как целые числа, числа с плавающей запятой или символы. Также функции могут получать в качестве аргументов другие функции. Функции, работающие с другими функциями в качестве аргументов, называются высокоуровневыми функциями (как противоположность функциям первого уровня оперирующими с базовыми значениями). Высокоуровневые функции - это мощный инструмент функционального программиста. Их также можно использовать в C, хотя это и потребует несколько больших усилий в плане программирования.

2.5.1 Суммы

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

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

Интересно взглянуть на отличия и схожести этих сумм. Разница в том, что они могут иметь другие начальные и конечные значения отличные от 1 и n (несмотря на то, что в наших двух примерах оба суммирования происходили в промежутке от 1 до n) и отличные выражения с использованием i. Схожесть в том, что значение i используется в прогрессии чисел, тем самым порождая последовательность выражений, в каждом из которых используется другое значение i. Значения этих выражений складываются для получения результата. Схожесть в этих шаблонах вычислений может быть захвачена в высокоуровневой функции. Разница в этих шаблонах вычисления захвачена аргументами высокоуровневой функции. Здесь мы встречаемся с применением важного принципа процедурной абстракции: поиск общих черт поведения и их захват в процедуру или функцию, что улучшает их гибкость через использование аргументов. Показанная ниже функция sum должна рассматриваться как SML эквивалент математического оператора сигма:

Функция sum в качестве аргументов получает начальное значение (аргумент i) и конечное значение (аргумент n). Оба являются целыми числами. В качестве третьего аргумента мы подставляем функцию f, получающую целое число (из прогрессии) и возвращающую вещественное значение, которое следует сложить.

Сумма арифметической прогрессии вычисляется SML функцией terminal представленной ниже. Она использует sum для выполнения суммирования. Версия f на данный момент - это функция int2real. Это функция, конвертирующая целое число в вещественное число, так что типы функции sum и её аргументов остаются прежними.

Для того, чтобы увидеть, что эта функция на самом деле вычисляет сумму арифметической прогрессии мы можем испытать её на некотором тестовом значении n. Лучший способ понять механизмы используемые в работе функции - это расширить определение sum через подстановку функции int2real в f. Получим следующее:

В качестве примера мы теперь можем 'вручную' вычислить terminal 3. Это потребует серию шагов для вычисления ответа 6, в соответствии с вычислительной моделью SML:

После таких приготовлений мы готовы транслировать наши функции sum и terminal в C. Вот C версия функции sum:

Функция sum использует функцию f как третий аргумент через следующий синтаксис:

Смысл конструкции в том, что аргумент f сам является функцией, возвращающей значение из типа double и использующий целочисленное значение как аргумент. (Строго говоря f - это указатель на функцию, на данном этапе разницу можно игнорировать; указатели обсуждаются в Главе 4.) Аргумент f используется sum-ом как функция для подсчёта значения f(i). Общий синтаксис для определения функционального аргумента функции следующий:

Здесь tr задаёт тип возвращаемого значения, и t1, ..., tn - типы аргументов функции. (В свою очередь каждый из t1, ..., tn может быть типом функции.) SML эквивалент типа этой высокоуровневой функции:

В C синоним типа для функциональных типов может определяться с помощью использования механизма typedef. В качестве примера определим:

Представляет тип с именем int_to_double_funcs, включающий все функции, которые получают int как аргумент и возвращают результат как значение double. В SML такой синоним типа можно декларировать так:

Упражнение 2.9 Напишите таблицу соответствия для трансформации SML версии sum в C версию. Используйте функциональную схему с начала этой главы.

При трансформации terminal в C возникает маленькая проблема. С не позволяет определять такие локальные функции, как функция int2real. Вместо этого int2real должен быть определён до terminal-а. Было бы лучше, если бы вспомогательную функцию int2real можно было определять локально в terminal, поскольку функция int2real используется только в terminal. Большинство других языков программирования позволяют выполнить этот приём, пример: Pascal или Modula-2.

Для того, чтобы быть ближе к SML версии, функция int2real использует явный вывод типа: выражение (double) i преобразовывает выражение i в тип double. В общем, (type) expr преобразовывает expr в указанный тип. Поскольку вывод типа крайне нежелателен в C (подробнее в следующих главах), будет лучше просто написать return i, и оставить преобразование компилятору.

Упражнение 2.10 Используйте Уравнение (2.6) для определения SML функции square. Затем трансформируйте эту функцию в C.

Упражнение 2.11 Значение пи (3.14159) можно приблизительно вычислить с помощью следующей формулы:

Напишите SML функцию nearly_pi которая вычисляет приближённое значение пи с помощью суммирования первых 2*n терм последовательности, заданной в (2.7). Передайте n как аргумент nearly_pi. Трансформируйте вашу функцию в C.

2.5.2 Произведения

Функции, использованные в предыдущем разделе все были определены в терминах сумм. Подобные функции можно определить в терминах произведений. Вот функция product в SML:

С помощью этой новой функции product, мы можем определить функцию factorial тем же способом, каким был определён terminal с помощью sum:

Упражнение 2.12 Дайте C версию приведённых выше функций product и factorial.

Упражнение 2.13 Значение e (~ 2.71828) можно приближённо вычислить используя следующую формулу (! - функция факториала):

Дайте SML функцию nearly_e, которая вычисляет приближённое значение e используя сумму первых n термов последовательности, заданной с помощью (2.8), где n - это аргумент nearly_e. Трансформируйте вашу функцию в C.

Вообще функции sum и product подобны. Обе имеют различные названия. Функция product отличается от функции sum только в двух аспектах:

1. Функция product перемножает выражения, в то время, когда функция sum складывает выражения.

2. Функция product использует в качестве простейшего элемента 1.0 для перемножения, в то время когда sum использует простейший элемент 0.0 для сложения.

Функции sum и product настолько похожи, что попытка дальнейшего их обобщения выглядит хорошей идеей. Общим поведением sum и product является повторное применение некоторой функции. Повторяющееся поведение требует базового значения (0.0 для sum и 1.0 для product) и метода комбинирования результатов (+ для sum и * для product). Общее поведение может быть захвачено в более параметризованной SML функции repeat:

Функция repeat имеет два функциональных аргумента, combine и f. Лучший способ понять как это работает - это дать пример использования repeat. Переопределим функцию sum в терминах repeat:

Краткий способ описать путь, которым repeat определяет sum - это наблюдение, что следующие функции эквивалентны:

Мы опустили аргументы i, n и f поскольку они одинаковы для обеих сторон. С repeat мы получили в своё распоряжение функцию высокого уровня, захватывающую повторяющееся поведение sum, product и многих других функций. Мощь функции repeat заключается в широком диапазоне функций и значений, которые можно передавать в качестве её пяти аргументов.

Упражнение 2.14 Переопределите SML функцию product в терминах repeat.

Упражнение 2.15 Трансформируйте repeat и переопределённую версию sum в C функции.

Упражнение 2.16 Вместо использования сложения или умножения мы можем рассмотреть деление как метод комбинирования результатов от повторяющейся функции. Этот подход можно использовать для вычисления так называемых цепных дробей. Золотое сечение, в математической прозе известное как число ф (~ 1.61803), можно вычислить следующим образом:

Напишите SML функцию nearly_phi использующую функцию repeat для подсчёта приближения к phi. Вы должны использовать первые n элементов цепной дроби (2.9); используйте n как аргумент nearly_phi. Трансформируйте вашу функцию в C.

2.5.3 Расширенный пример высокоуровневых функций: бисекция

Метод бисекции - интересный алгоритм, который можно реализовать с помощью функций высокого уровня. Бисекция - это процесс разделения большой задачи на малые задачи до тех пор, пока задача не станет настолько малой, что её решение будет тривиальным (это пример важного класса алгоритмов разделяй и властвуй). Метод бисекции можно использовать для поиска некоторой приблизительной информации в некотором массиве данных. В данном примере, мы используем бисекцию для нахождения корня функции, значения x, при котором значение функции будет равным 0.

Прежде чем мы представим детали метода бисекции, рассмотрим её графическую интерпретацию. Рисунок ниже показывает график функции f(x). Эта функция пересекает ось X в точке между линией, обозначенной как l0 (l - обозначает "низкий") и h0 (h - обозначает "высокий"). Эти две точки формируют границы интервала оси X, содержащий корень. Интервал достаточно большой, поэтому он не является хорошим приближением корня. Мы можем уменьшить интервал и тем самым получим улучшенное приближение для корня. Метод бисекции вычисляет последовательность приближений, где каждое следующее приближение лучше чем предыдущее. Процесс прекратится тогда, когда мы окажемся достаточно близко к корню.

Ось X

Когда даны две начальные границы l0 и h0, метод бисекции вычисляет новую точку m (обозначает середину) точно между l0 и h0. Далее выполняется проверка где расположен корень: справа или слева от точки m. Если корень расположен слева от m, то правая часть исходного интервала между l0 и h0 отбрасывается и процесс продолжается с новыми интервалами между l0 и h1 = m. Этот новый интервал равен половине длины исходного интервала. Если корень лежит справа от m, то отбрасывается левая часть и процесс продолжается с интервалом между l1 = m и h0. Этот интервал также равен половине длины исходного интервала. Процесс отсечения половины текущего интервала продолжается до тех пор, пока он не будет сочтён достаточно малым для того, чтобы служить в качестве приближения корня. Графически процесс отсечения половины будет выглядеть так:

Подытоживая, при некоторых начальных приблизительных l0 и h0, метод бисекции находит две точки ln и hn, которые близки настолько, насколько это возможно к обеим сторонам точки пересечения. Достижение результата осуществляется за max(m, n) шагов.

Для того, чтобы более точно обозначить 'близко настолько, насколько это возможно', мы используем немного математической нотации. Для корректной работы метода бисекции должны быть две заданные точки, l и h, такие, что f(l) < 0 < f(h). Если f - непрерывная функция, то корень f должен находится между l и h. Метод бисекции пытается найти подобный корень вычисляя арифметическое значение l и h как m = (l + h) / 2. В полученном частичном наборе значений l < m < h, существуют три возможных случая:

Если f(m) ~ 0, то корень найден (по крайней мере мы достаточно близки к корню).

Если f(m) положительно, то нам нужном сдвинуться влево и продолжить использование m как новое значение h.

Если f(m) отрицательное число, мы продолжаем использовать m как новое значение l.

Таким образом метод бисекции приближается к корню, либо сдвигая l вверх, либо сдвигая h вниз. Метод заботится о том, чтобы эти значения не пропустили корень. В математической нотации мы запишем:

Для того, чтобы выразить что мы достаточно близки к корню, метод бисекции использует два предела, e и d. Мы говорим, что мы достаточно близки к нулю либо когда результат функции близок к 0, |F(m)| < e, или если корень находится между двумя достаточно близкими границами, |h - l| < d. Это визуализировано ниже:

Мы можем выбрать e и d так, что корень будет вычисляться с достаточной точностью. Учтите, что возникнет проблема если их обеих установить в ноль. Вне зависимости от того насколько близки l и h, они на самом деле никогда не встретятся. Каждый шаг делает их ближе разделяя на пополам длину их интервала. Только бесконечное множество шагов могут свести их вместе. Второе, как было показано в предыдущем разделе, компьютеры работают только с арифметикой ограниченной точности. Это может стать причиной неожиданных проблем в реализации чисел с плавающей запятой. Принятие границы допустимой погрешности позволяет обойти обе эти проблемы.

Вышеприведённая версия метода бисекции требует, чтобы f была возрастающей функцией, f(l) < 0 < f(h); она не работает для убывающей функции.

Математику (2.10) можно прямо трансформировать в SML функцию. Здесь константы eps и delta представляют наш выбор для e и d. Повышение одного из них (или обеих) уменьшает точность метода, но также убыстряет нахождение приближения корня. И наоборот, уменьшение значений замедляет процесс, но делает результат более точным.

Нижеприведённая функция bisection следует структуре математики. Для придания некоторой гибкости мы передаём bisection три аргумента. Первый аргумент - это функция f, корень которой мы ищем. Остальные два аргумента - это вещественные границы l и h, представляющие текущую нижнюю и верхнюю границы интервала в котором нужно найти корень.

Локальные определения для m и f_m позволяют быть уверенными в том, что вычисления не будут выполнены более чем один раз. Такой подход делает функцию bisection более эффективной чем буквальная трансляция математики. Функция absolute определена так:

В качестве примера использования функции bisection, вычислим корень функции parabola, приведённой ниже.

Следующая таблица демонстрирует корни функции parabola при её вычислении с различными начальными границами. Выбранное значение eps - 0.001 и выбранное значение для delta - 0.0001. В каждом из данных случаев parabola l < 0 < parabola h.

Все три ответа блики к вещественному ответу корень из двух ~ 1.41421356... . Ответы не одни и те же поскольку bisection вычисляет приближение к ответу.

Завершённая C программа реализующая и использующая метод бисекции дана ниже:

Для метода бисекции в C программу входят определения eps и delta с типом double:

Это выражение определяет две глобальные константы, то есть, константы, доступные для всех функций, определённых в текущем модуле. Заметьте, что два определения с одним типом double можно располагать в одной строке. Две локальные константы определены в теле функции bisection:

Эти локальные константы видимы только в теле функции bisection. Как и все определения в C каждая константа должна быть определена до того, как это значение будет использоваться. Поскольку определение f_m использует значение m, то определение f_m должно идти после определения m, таким образом становится возможным использовать m для вычисления f_m.

Упражнение 2.17 Обобщите функциональную схему из Упражнения 2.2 для поддержки произвольного числа локальных определений как каскада условий.

Упражнение 2.18 Вывод программы bisection состоит из трёх различных приближений корня. Отследите первые два вызова через printf для того чтобы увидеть почему приближения различаются.

Упражнение 2.19 Переформулируйте (2.10) так, чтобы она работала для функции с отрицательным градиентом. Разработайте обобщённую функцию бисекции автоматически осуществляющей выбор между версией работающей только для положительного градиента и версию, также работающую для отрицательного градиента.

2.6 Итог

Мы ввели следующие C конструкции:

Функции Общая форма объявления C функций следующая:

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

Определение константы Константа c с типом t и значением e определяется следующим образом:

Выражения Были обсуждены три формы выражений, выражение return, выражение if и выражение вызова функции. Выражение return имеет следующую форму:

Оно завершает исполнение текущей функции и возвращает значение выражения e как значение возвращаемое функцией. Тип выражения должен соответствовать результирующему типу функции. Выражение if существует в двух формах, первая с двумя ветками, и вторая с единственной веткой then:

В зависимости от значения условного выражения p, будет выполнена первая или вторая (если она существует) последовательность выражений, T или F. Третье выражение, обсуждаемое здесь, это просто конструкция, завершаемая точкой с запятой. Это выражение вычисляет конструкцию и отбрасывает полученный результат. Это может быть полезным, поскольку конструкция может иметь побочный эффект. Например, вызов функции printf напечатает вывод.

Печать вывода Функция printf требует в качестве первого аргумента строку, печатает её подставляя для %-аббревиатур соответствующие аргументы следующим образом:

%d Ожидает целочисленный аргумент, печатает в десятичной системе
%f Ожидает аргумент с плавающей запятой, печатает в десятичной системе
%c Ожидает аргумент символ, печатает в виде буквы
%% Печатает один знак процента

Выражения Выражения в C похожи на SML выражения, с тем исключением, что некоторые операторы слегка отличаются, перечислено в Разделах 2.2.4 и 2.2.5. Выражения типизированы, но есть несколько необычных типов: булевы значения и символы представлены целыми числами.

Типы Следующая таблица показывает отношения C типов к их эквивалентам в SML и математике:

Особое внимание нужно уделить применению символов (которые на самом деле являются целочисленными значениями, страница 27). Булевы значения также представлены целыми числами и должны быть определены явно, как это показано в Разделе 2.2.6.

Именование типов: Имя может быть ассоциировано с типом с помощью использования ключевого слова typedef:

Так идентификатор i будет привязан к типу t. Для некоторых типов, особенно для типов функций, i должен располагаться в середине t:

Так определяется тип функции с именем i идентичный SML типу:

Перечислимые типы Общая форма перечислимого типа следующая:

Enum определяет тип через точное перечисление всех возможных значений: i0, i1, ... . С помощью typedef перечислимый тип становится известным как t.

Main Каждая C программа должна иметь функцию main. Функция с именем main - это функция, которая вызывается при исполнении программы.

Самые главные принципы программирования, к которым мы обратились в этой главе, следующие:

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

* По возможности функция должна быть чистой. Это значит, что результат функции должен зависеть только от значения его аргумента. Введённый в этом разделе метод систематичной трансформации гарантирует что все C функции на самом деле чисты.

Функция должна быть обобщённой, это значит, что она должна учитывать все её случаи. Обычно SML компилятор определяет частичное определение функции. В C, если функция будет незавершённой, появится сообщение об ошибке времени исполнения или программа может вернуть случайный результат. При первом написании функции в SML мы получаем соответствующие предупреждения от компилятора и если все подобные предупреждения будут учтены, то наша C программа не будет сталкиваться с подобными проблемами. Язык C не содержит встроенной поддержки сопоставления с образцом, но цепочка из операторов if может быть использована для симуляции сопоставления с образцом.

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

Функции должны быть строго типизированы. Поскольку SML - это строго типизированный язык, то он вынуждает нас писать строго типизированные функции. Наш систематичный подход к трансформированию SML программ в C программы должен проходить через дисциплину типизации от SML кода в C код. Реализация полиморфических функций рассмотрена позже в Главах 4 и 8.

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

Один жизненно важный вопрос, который мы не рассмотрели в этой главе - это эффективность C реализаций. Этот вопрос - тема следующих глав.

2.7 Дальнейшие упражнения

Упражнение 2.20 Напишите программу, которая конвертирует температуру с Цельсия в Фаренгейт: 0 C = 32 F, и 10 C = 50 F. Проверьте её на 0, 28, 37 и 100 градусах по Цельсию.

Упражнение 2.21 Некоторые компьютеры поддерживают инструкцию 'число популяции' (или вес Хэмминга) для подсчёта количества бит равных 1 в целом числе; например, число популяции 7 равно 3 и число популяции 8 равно 1.

(a) Дайте спецификацию функции pop_count. Допустим, что заданное слово x представлено как последовательность n+1 бит в виде bnbn-1...b1b0, где каждый из bi E {0, 1}.

(b) Дайте SML функцию, вычисляющую число популяции для слова, где целое число использовано для представления слова.

(c) Используйте функциональную схему для трансформирования SML функции в эквивалентную C функцию.

(d) Пошагово покажите, что C код - это результат прямой трансформации из SML кода.

(e) Напишите главную функцию для вашей C функции вычисляющей число популяции. Главная функция должна вызывать pop_count с, по-крайней мере, тремя интересующими словами и печатать результат.

Упражнение 2.22 Ниббл - это группа из четырёх смежных битов. Контрольная сумма слова может быть вычислена сложением всех нибблов слова. Например, контрольная сумма 17 - это 2 и контрольная сумма 18 - это 3.

(a) Дайте спецификацию функции checksum. Допустим, что дано слово x представленное как последовательность k+1 нибблов: nknk-1...n1n0, где значение каждого из нибблов ni лежит в промежутке 0 ... 15.

(b) Дайте SML функцию для вычисления контрольной суммы слова, где целое число используется для представления слова. Проверьте вашу функцию.

(c) Используйте функциональную схему для трансформации SML функции в эквивалентную C функцию.

(d) Пошагово покажите, что C код - это результат прямой трансформации с SML кода.

(e) Напишите главную функцию, работающую с вашей C функцией checksum. Главная функция должна вызывать checksum с, по-крайней мере, тремя интересующими словами и печатать результат.

Упражнение 2.23 N-ое число Фибоначчи fn определено следующим рекуррентным соотношением:

Напишите SML функцию fib для вычисления n-го числа Фибоначчи. Затем дайте соответствующую C функцию и главную программу для проверки C версии fib на, по-крайней мере, трёх интересующих значениях n.

Упражнение 2.24 Число 'nFib' - это маленькая вариация числа Фибоначчи. Оно определяется следующим образом:

(a) Какова разница между последовательностью Фибоначчи и последовательностью nFib?

(b) Напишите SML функцию nfib для вычисления n-го числа nFib.

(c) Дайте C функцию, точно соответствующую SML версии nfib.

(d) Напишите главную функцию, вызывающую nfib и печатающую её результат. Проверьте C версию nfib на, по-крайней мере, трёх интересующих значениях n.

(e) Если вы внимательно изучите вышеприведённую формулу для fn, то вы подметите, что значение fn является числом вызовов функций выполненных вашей SML или C функцией для подсчёта fn. Замерьте время, затраченное SML для вычисления f30 и найдите количество вызовов функций в секунду для SML.

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

Упражнение 2.25 Напишите SML функцию power_of_power для вычисления n-го выражения следующей последовательности:

Здесь n обозначает число появлений m в выражении. Дайте C версию power_of_power и дайте главную программу для проверки C версии для, по-крайней мере, трёх интересующих значений m и n.

Упражнение 2.26 Метод Ньютона-Рафсона - это альтернативный бисекции метод для нахождения корней уравнения функции f(x). Он работает на основе следующего наблюдения: если есть значение xi, такое, что f(xi) приблизительно равен нулю, то более лучшее приближение корня xi+1 определено следующим образом:

Здесь, функция f'(x) - это производная f(x). Работа метода Ньютона-Рафсона схематически показана ниже. Дана функция f(x) и точка x0, проведена касательная к f(x0). Точка, где касательная пересекает ось X, x1, ближе к корню функции; таким образом, x1 - это более лучшее приближение к корню. Процесс повторяется с использованием x1. Проводится касательная к f(x1) и её пересечение с осью X даёт точку x2, которая ближе к корню функции чем x1. Процесс может быть повторён до тех пор, пока значение функции не станет (почти) нулём.

(a) Дана функция f(x), её производная f'(x) и начальное приближение x0, покажите математику вычисления корня.

(b) Дайте SML функцию newton_raphson, реализующую метод Ньютона-Рафсона на основе математики из вышеприведённого (a). Убедитесь, что аргументами захвачено как можно больше информации.

(с) Используйте вашу функцию Ньютона-Рафсона для вычисления корня функции parabola из Раздела 2.5.

(d) Трансформируйте SML функции из вышеприведённых (a) и (b) в C и сформируйте завершённую C программу для вычисления корней функции parabola.

(e) Проследите вычисление следующего C выражения:

(f) Метод Ньютона-Рафсона - это быстрый метод определения корня, но он не позволяет найти корень во всех случаях. В качестве примера: если попытаться найти корень f(x) = 1/x - 1, то корень можно найти при начальном значении x = 0.5, но не при начальном значении 3. Что произойдёт если алгоритм Ньютона-Рафсона был использован для определения корня 1/x - 1, начиная с x=3?

Переведено на Нотабеноиде
http://notabenoid.org/book/60709/295798

Переводчики: Charlz_Klug, akass