Functional C / Функциональный C: Глава 1 - Введение

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

Charlz_Klug 25.12.15 в 05:38

1.1 Функциональная и императивная парадигмы

Charlz_Klug 25.12.15 в 05:47

Функциональная и императивная парадигмы действуют с различных точек зрения. Функциональная парадигма основывается на вычислении выражений и привязке переменных к значениям. Базовая программная фраза - это выражение; цель вычисления выражения заключается в получении значения. Порядок в котором вычисляются подвыражения не влияет на результирующие значения.

Charlz_Klug 25.12.15 в 05:52

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

Charlz_Klug 25.12.15 в 05:58

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

Charlz_Klug 25.12.15 в 06:06

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

Charlz_Klug 25.12.15 в 06:12

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

Charlz_Klug 25.12.15 в 06:14

int functional_random( int seed ) {
return 22 * seed % 37 ;
}

Charlz_Klug 26.12.15 в 19:55

Функциональную реализацию следует читать таким образом: первая строка вводит функцию под названием functional_random. Эта функция принимает целочисленный аргумент названный как seed и возвращает также целочисленное значение. Тело функции (окружённое фигурными скобками { и }) содержит единственный оператор возврата. Аргумент оператора возврата представляет выражение, умножающее значение seed на 22 и возвращающее остаток от деления полученного результата на 37.

Charlz_Klug 26.12.15 в 20:04

Для использования функции functional_random, следует выбрать подходящее стартовое значение для seed, например 1, и затем циклично применять функцию functional_random. Таким образом можно получить последовательные псевдо случайные значения. Рассмотрим следующий фрагмент программы на C:

Charlz_Klug 26.12.15 в 20:08

int first = functional_random( 1 ) ;
int second = functional_random( first ) ;
int third = functional_random( second ) ;

Charlz_Klug 26.12.15 в 20:08

Значением переменной first будет 22; значением переменной second будет 3, (поскольку 22*22 = 13*37 + 3) и значение third будет равно 29.

Charlz_Klug 26.12.15 в 20:10

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

Charlz_Klug 26.12.15 в 20:16

Также генератор псевдо случайных чисел может быть написан в императивном стиле:

Charlz_Klug 26.12.15 в 20:18

int seed = 1 ;
int imperative_random( void ) {
seed = 22 * seed % 37 ;
return seed ;
}

Charlz_Klug 26.12.15 в 20:18

Императивную реализацию следует читать так: первая строка определяет глобальную переменную, названную как seed, хранящее начальное значение. Начальное значение равно 1. Следующая строка вводит функцию под названием imperative_random. Функция не имеет аргументов, что обозначается словом void. Функция изменяет значение seed и возвращает это значение после изменения. Модификация хранилища являет собой побочный эффект, поскольку этот эффект был дополнительным к возвращению псевдо случайного числа.

Charlz_Klug 26.12.15 в 20:38

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

Charlz_Klug 26.12.15 в 20:46

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

Charlz_Klug 27.12.15 в 09:20

1.1.1 Преимущество состояния

Charlz_Klug 27.12.15 в 09:22

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

Charlz_Klug 27.12.15 в 09:26

int imperative_dice( void ) {
return imperative_random() % 6 + 1 ;
}

Charlz_Klug 27.12.15 в 09:26

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

Charlz_Klug 27.12.15 в 09:32

1.1.2 Преимущества чистых функций

Charlz_Klug 27.12.15 в 09:45

Хранение состояния в каком либо скрытом месте приводит к неудобству: усложняется создание функций, используемых в качестве строительных блоков. В качестве примера предположим, что нам нужно одновременно бросать две игральные кости. Теория генераторов случайных чисел говорит, что будет некорректным использовать одно число от одного генератора случайных чисел для генерации значений двух игральных костей [5]. Вместо этого следует использовать два независимых генератора случайных чисел.

Charlz_Klug 27.12.15 в 09:52

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

Charlz_Klug 27.12.15 в 09:57

int x = functional_random( r ) ;
int y = functional_random( s ) ;
int dice = x%6 + 1 + y%6 + 1 ;

Charlz_Klug 27.12.15 в 09:58

Этого невозможно получить с помощью императивной версии, поскольку есть только одна переменная seed хранящая начальное значение.

Charlz_Klug 27.12.15 в 09:59

1.1.3 Построение блоков характерное для C

Charlz_Klug 27.12.15 в 15:31

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

Charlz_Klug 27.12.15 в 15:38

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

Charlz_Klug 29.12.15 в 00:14

1.2 Руководство по книге

Charlz_Klug 29.12.15 в 00:20

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

Charlz_Klug 29.12.15 в 00:26

В Главе 3 обсуждается итерация. Функциональные языки осуществляют итерацию через структуры данных с помощью прямой рекурсии или косвенной рекурсии посредством таких высокоуровненвых функций, как map и foldl. C предлагает конструкции, которые выполняют итерацию без рекурсии с помощью циклично исполняемых определённых частей программного кода. В Главе 3 мы создаём эффективный код в C стиле для большинства примеров программ Главы 2. Это будет выполнено с помощью определённого числа систематических, но неформальных схем трансформации программ.

Charlz_Klug 29.12.15 в 00:34

В Главе 4 обсуждаются конструкторы типов C, необходимых для создания (не рекурсивных) алгебраических типов данных. Эти конструкторы называются структурами или объединениями. В главе обсуждается вопрос создания составных типов и заканчивается темой деструктивных обновлений этих структур данных (с помощью указателей).

Charlz_Klug 29.12.15 в 00:40

В первых четырёх главах обсуждаются базовые типы данных и их C представления. Более сложные типы данных могут хранить последовательности данных. Для хранения последовательностей есть некоторое число представлений. В функциональных языках популярны списки; массивы используются для эффективного доступа к случайным элементам. Списки менее популярны в C поскольку управление списками в C более трудоёмко чем управление списками в функциональных языках. Последовательности, массивы, списки и потоки обсуждаются в Главах 5 и 7.

Charlz_Klug 29.12.15 в 00:46

Глава 5 представляет базовые принципы последовательностей и реализацию массивов. Массивы в C являются низкоуровневыми, но они показаны как создаваемые высокоуровневые структуры в функциональных языках. Списки обсуждаются в Главе 6. Реализация списков требует явного управления памятью; это одна из причин. по которой использование списков менее удобно в C чем в SML. Поток, список элементов используемых или записываемых последовательно (как Ввод/Вывод (I/O)), является темой Главы 7.

Charlz_Klug 29.12.15 в 00:54

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

Charlz_Klug 29.12.15 в 01:01

В Главе 9, последней главе, показаны три обучающих примера элементарной графики. Первый пример полностью проработан, он показывает как использовать систему X-window для рисования фрактала для множества Мандельброта. Второй обучающий пример проработан частично, он описывает систему для платформно независимой графики. Большую часть примера предстоит реализовать читателю. В третьем примере разрабатывается реализация простого графического языка. Описан алгоритм и даны наброски структур данных, реализация этого примера оставлена читателю.

Charlz_Klug 29.12.15 в 01:09

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

Charlz_Klug 29.12.15 в 18:11

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

Charlz_Klug 29.12.15 в 18:16

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

Charlz_Klug 29.12.15 в 18:21

Последнее Приложение D даёт полный синтаксис ISO-C с помощью синтаксических диаграмм. Это интуитивно понятней чем альтернативная БНФ нотация для синтаксиса. Синтаксическая диаграмма представлена как справочное пособие.

Charlz_Klug 29.12.15 в 18:25

Эта книга не является полноценным справочным материалом. Читатель найдёт полезным обратиться к справочному материалу ISO-C [7]. Он содержит все детали, которые могут понадобится опытному C программисту, а также вводный материал не упомянутый в этой книге.

Charlz_Klug 29.12.15 в 18:29