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

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

Charlz_Klug 10.01.16 в 20:09

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

Charlz_Klug 10.01.16 в 20:32

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

Charlz_Klug 10.01.16 в 20:34

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

Charlz_Klug 10.01.16 в 20:54

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

Charlz_Klug 11.01.16 в 10:05

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

Charlz_Klug 11.01.16 в 10:12

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

Charlz_Klug 11.01.16 в 10:14

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

Charlz_Klug 11.01.16 в 10:33

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

Charlz_Klug 11.01.16 в 10:37

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

Charlz_Klug 11.01.16 в 10:39

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

Charlz_Klug 11.01.16 в 10:41

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

Charlz_Klug 11.01.16 в 10:45

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

Charlz_Klug 11.01.16 в 10:47

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

Charlz_Klug 11.01.16 в 12:19

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

Charlz_Klug 12.01.16 в 06:07

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

Charlz_Klug 12.01.16 в 06:12

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

Charlz_Klug 12.01.16 в 06:21

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

Charlz_Klug 12.01.16 в 06:26

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

Charlz_Klug 12.01.16 в 06:36

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

Charlz_Klug 12.01.16 в 06:37

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

Charlz_Klug 12.01.16 в 06:50

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

Charlz_Klug 12.01.16 в 06:50

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

Charlz_Klug 12.01.16 в 06:53

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

Charlz_Klug 12.01.16 в 06:54

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

Charlz_Klug 12.01.16 в 06:56

printf( "Hello world\n" ) ;

Charlz_Klug 12.01.16 в 06:56

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

Charlz_Klug 13.01.16 в 17:05

return 0 ;

Charlz_Klug 13.01.16 в 17:05

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

Charlz_Klug 13.01.16 в 17:10

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

Charlz_Klug 13.01.16 в 17:15

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

Charlz_Klug 13.01.16 в 17:21

cc -o monkey hello.c

Charlz_Klug 13.01.16 в 17:21

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

Charlz_Klug 13.01.16 в 17:25

Hello world

Charlz_Klug 13.01.16 в 17:25

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

Charlz_Klug 13.01.16 в 17:31

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

Charlz_Klug 13.01.16 в 17:49

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

Charlz_Klug 13.01.16 в 17:52

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

Charlz_Klug 13.01.16 в 18:01

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

Charlz_Klug 18.01.16 в 14:43

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

Charlz_Klug 18.01.16 в 14:43

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

Charlz_Klug 18.01.16 в 14:44

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

Charlz_Klug 18.01.16 в 14:44

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

Charlz_Klug 18.01.16 в 14:54

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

Charlz_Klug 18.01.16 в 15:00

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

Charlz_Klug 18.01.16 в 15:00

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

Charlz_Klug 18.01.16 в 15:26

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

Charlz_Klug 18.01.16 в 15:27

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

Charlz_Klug 18.01.16 в 15:28

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

Charlz_Klug 18.01.16 в 15:28

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

Charlz_Klug 18.01.16 в 15:30