Первый язык функционального программирования LISP появился в конце 1950, в тот же момент, что и Fortran – один из первых императивных языков. Оба этих языка существуют и по сей день, хотя они немало изменились. Область их применения: вычислительные задачи для Фортрана и символьные (symbolic) для Lisp. Интерес к функциональному программированию состоит в простоте написания программ, где под программой подразумевается функция, примененная к аргументам. Она вычисляет результат, который возвращается как вывод программы. Таким образом можно с легкостью комбинировать программы: вывод одной, становится входным аргументом для другой.
Функциональное программирование основывается на простой модели вычислений, состоящей из трех конструкций: переменные, определение функции и ее применение к какому–либо аргументу. Эта модель, называемая λ–исчисление, была введена Alonzo Church в 1932, еще до появления первых компьютеров. В λ–исчислении любая функция является переменной, так что она может быть использована как входной параметр другой функции, или возвращена как результат другой. Теория λ-исчисления утверждает что все то, что вычисляемо может быть представлено этим формализмом. Однако, синтаксис этой теории слишком ограничен, чтобы его можно было использовать его как язык программирования. В связи с этим к λ-исчислению были добавлены базовые типы (например, целые числа или строки символов), операторы для этих типов, управляющие структуры и объявление позволяющие именовать переменные или функции, и в частности рекурсивные функции.
Существует разные классификации языков функционального программирования. Мы будем различать их по двум характеристикам, которые нам кажутся наиболее важными:
В этой главе представлены базовые элементы функциональной части языка Objective CAML, а именно: синтаксис, типы и механизм исключений. После этого вводного курса мы сможем написать нашу первую программу.
В первоm разделе описаны основы языка, начиная с базовых типов и функций. Затем мы рассмотрим структурные и функциональные типы. После этого мы рассмотрим управляющие структуры, а также локальные и глобальные объявления. Во втором разделе мы обсудим определение типов для создания структур и механизм сопоставления с образцом, который используется для доступа к этим структурам. В третьем разделе рассматривается выводимый тип функций и область их применения, после чего следует описание механизма исключений. Четвертый раздел объединяет введенные понятия в простой пример программы-калькулятора.
Как любой другой язык функционального программирования, Objective CAML — это язык выражений, состоящий в основном из создания функций и их применения. Результатом вычисления одного из таких выражений является значение данного языка (value in the language) и выполнение программы заключается в вычислении всех выражений из которых она состоит.
В Objective CAML определены следующие типы: целые числа, числа с плавающей запятой, символьный, строковый и логический.
Различают целые int и числа с плавающей запятой float. Objective CAML следует спецификации IEEE 754 для представления чисел с плавающей запятой двойной точности. Операции с этими числами описаны в таблице 1.1. Если результат целочисленной операции выходит за интервал значений типа int, то это не приведет к ошибке. Результат будет находиться в интервале целых чисел, то есть все действия над целыми ограниченны операцией modulo с границами интервала.
целые плавающие + сложение +. сложение - вычитание и унарный минус -. вычитание и унарный минус * умножение *. умножение / деление /. деление mod остаток целочисленного деления ** exponentiation
# 1 ;; # 2.0 ;; - : int = 1 - : float = 2 # 1 + 2 ;; # 1.1 +. 2.2 ;; - : int = 3 - : float = 3.3 # 9 / 2 ;; # 9.1 /. 2.2 ;; - : int = 4 - : float = 4.13636363636 # 11 mod 3 ;; # 1. /. 0. ;; - : int = 2 - : float = Inf (* лимит представления *) (* лимит представления *) (* целых чисел *) (* с плавающей запятой *) # 2147483650 ;; # 222222222222.11111 ;; - : int = 2 - : float = 222222222222
Table 1.1: Операции над числами
Значения разных типов, таких как float и int, не могут сравниваться между собой напрямую. Для этого существует функции перевода одного типа в другой (float_of_int и int_of_float).
Аналогично, операции над целыми числами и числами с плавающей запятой различны:
Неопределенный результат, например получаемый при делении на ноль, приведет к возникновению исключения (см. 1.3, стр. ??), которое остановит вычисление. Числа с плавающей запятой имеют специальные значения для бесконечных величин (Inf) и для не определенного результата (NaN1). Основные операции над этими числами приведены в таблице 1.2
ф-ии над числами с плавающей запятой тригонометрические функции: ceil cos косинус floor sin синус sqrt - квадратный корень tan тангенс exp - экспонента acos арккосинус log - натуральный логарифм asin арксинус log10 - логарифм по базе 10 atan арктангенс
# ceil 3.4 ;; # sin 1.57078 ;; - : float = 4 - : float = 0.999999999867 # floor 3.4 ;; # sin (asin 0.707) ;; - : float = 3 - : float = 0.707 # ceil (-.3.4) ;; # acos 0.0 ;; - : float = -3 - : float = 1.57079632679 # floor (-.3.4) ;; # asin 3.14 ;; - : float = -4 - : float = NaN
Table 1.2: Функции над числами с плавающей запятой
Символы, тип char, соответствуют целым числам в интервале от 0 до 255, первые 128 значений соответствуют кодам ASCII. Функция char_of_int и int_of_char преобразуют один тип в другой. Строки, тип string — это последовательность символов определенной длинны (не длиннее 224−6). Оператором объединения строк (конкатенации) является шапка '^'. Следующие функции необходимы для перевода типов int_of_string, string_of_int, string_of_float и float_of_string.
Если строка состоит из цифр, то мы не сможем использовать ее в численных операциях, не выполнив явного преобразования.
В модуле String собрано много функций для работы со строками (стр. 7.3.2)
Значение типа boolean принадлежит множеству состоящему из двух элементов: true и false. Основные операторы описаны в таблице 1.3. По историческим причинам операторы and и or имеют две формы.
Операторы && и || или их синонимы, вычисляют аргумент слева и в зависимости от его значения, вычисляют правый аргумент. Они могут быть переписаны в виде условной структуры (см. 1.1.2 стр. ??).
Операторы сравнения и равенства описаны в таблице 1.4. Это полиморфные операторы, то есть они применимы как для сравнения двух целых, так и двух строк. Единственно ограничение это то что операнды должны быть одного типа (см. 1.1.5 стр. ??).
Структурное равенство, при проверке двух переменных, сравнивает значение полей структуры, тогда как физическое равенство проверяет занимают ли эти переменные одно и то же место в памяти. Оба оператора возвращают одинаковый результат для простых типов: boolean, char, int и константные конструкторы (см. 1.2.4 стр. ??).
Warning
числа с плавающей запятой и строки рассматриваются как
структурные типы.
Тип unit определяет множество из всего одного элемента, значение которого: ()
Это значение будет широко использоваться в императивных программах (см. 2 стр. ??), в функциях с побочным эффектом. Функции, результат которых равен (), соответствуют понятию процедуры, которое отсутствует в Objective CAML, так же как и аналог типа void в языке C.
Значения разных типов могут быть сгруппированы в кортежи. Значения из которых состоит кортеж разделяются запятой. Для конструкции кортежа, используется символ *. int*string есть кортеж, в котором первый элемент целое число и второй строка.
v
Иногда мы можем использовать более простую форму записи.
Функции fst и snd дают доступ первому и второму элементу соответственно.
Эти обе функции полиморфные, входной аргумент может быть любого типа.
Тип int*char*string — это триплет, в котором первый элемент типа int, второй char, а третий — string.
Warning
Если аргумент функций fst и snd не пара, а другой
n–кортеж, то мы получим ошибку.
Существует разница между парой и триплетом: тип int*int*int отличен от (int*int)*int и int*(int*int). Методы доступа к элементам триплета (и других кортежей) не определены в стандартной библиотеке. В случае необходимости мы используем сопоставление с образцом (см. 1.2.1).
Значения одного и того же типа могут быть объединены в списки. Список может быть либо пустым, либо содержать однотипные элементы.
Для того чтобы добавить элемент в начало списка существует следующая функция в виде инфиксного оператора :: — аналог cons в Caml.
Для объединения (конкатенации) списков существует инфиксный оператор: @.
Остальные функции манипуляции списками определены в библиотеке List. Функции hd и tl дают доступ к первому и последнему элементу списка.
В последнем примере получить первый элемент пустого списка действительно “сложно”, поэтому возбуждается исключение (см. 1.3.1).
Одна из структур контроля необходимая в каждом языка программирования — условный оператор.
Синтаксис:
Тип выражения expr1 равен bool. Выражения expr2 и expr3 должны быть одного и того же типа.
Условное выражение, как и любое другое, возвращает значение.
Замечание
Ветка else может быть опущена, в этом случае будет подставлено
значение по умолчанию равное else (), в соответствии с этим выражение
expr2 должно быть типа unit (см. 2.3
стр. ??).
Определение связывает имя со значением. Различают глобальные и локальные определения. В первом случае, объявленные имена видны во всех выражениях, следуют за ним, во втором — имена доступны только в текущем выражении. Мы также можем одновременно объявить несколько пар имя-значение.
Синтаксис:
Глобальное объявление определяет связь имени nom со значением выражения expr, которое будет доступно всем следующим выражениям.
Синтаксис:
При одновременном объявлении переменные будут известны только к концу всех объявлений.
Можно сгруппировать несколько глобальных объявлений в одной фразе, вывод типов и значений произойдет к концу фразы, отмеченной “;;”. В данном случае объявления будут вычислены по порядку.
Глобальное объявление может быть скрыто локальным с тем же именем (см. 1.1.4 стр. ??).
Синтаксис:
Имя nom связанное с выражением expr1 известно только для вычисления expr2.
Локальное объявление, которое связывает xl со значением 3, существует только в ходе вычисления xl*xl.
Локальное объявление скрывает любое глобальные с тем же именем, но как только мы выходим из блока в котором была оно определено, мы находим старое значение связанное с этим именем.
Локальное объявление — это обычное выражение, соответственно оно может быть использовано для построения других выражений.
Локальные объявления так же могут быть одновременными.
Функциональное выражение состоит из параметра и тела. Формальный параметр — это имя переменной, а тело — это выражение. Обычно говорят что формальный параметр является абстрактным, по этой причине функциональное выражение тоже называется абстракцией.
Синтаксис:
Таким образом функция возведения в квадрат будет выглядеть так:
Objective CAML сам определяет тип. Функциональный тип int->int это функция с параметром типа int, возвращающая значение типа int.
Функция с одним аргументом пишется как функция и аргумент следующий за ней.
Вычисление функции состоит в вычисление ее тела, в данном случае x*x, где формальный параметр x, заменен значением аргумента (эффективным параметром), здесь он равен 5.
При конструкции функционального выражения expr может быть любым выражением, в частности функциональным.
Скобки не обязательны, мы можем писать просто:
В простом случае мы скажем, что функция ожидает два аргумента целого типа на входе и возвращает значение целого типа. Но когда речь идет о функциональном языке, таком как Objective CAML, то скорее это соответствует типу функции с входным аргументом типа int и возвращающая функциональное значение типа int->int:
Естественно, мы можем применить это функциональное выражение к двум аргументам. Для этого напишем:
Когда мы пишем f a b, подразумевается применение (f a) к b.
Давайте подробно рассмотрим выражение
Для того чтобы вычислить это выражение, необходимо сначала вычислить значение
что есть функциональное выражение равное
в котором x заменен на 4 в выражении 3*x+y. Применяя это значение (являющееся функцией) к 5, мы получаем конечное значение 3*4+5=17:
Арностью функции называется число аргументов функции. По правилам, унаследованным из математики, аргументы функции задаются в скобках после имени функции. Мы пишем: f(4,5). Как было указанно ранее, в Objective CAML мы чаще используем следующий синтаксис: f 4 5. Естественно, можно написать функциональное выражение применимое к (4,5):
Но в данном случае, функция ожидает не два аргумента, а один; тип которого пара целых. Попытка применить два аргумента к функции ожидающей пару или наоборот, передать пару функции для двух аргументов приведет к ошибке:
Существует более компактная форма записи функций с несколькими аргументами, которая дошла к нам из старых версий Caml. Выглядит она так:
Синтаксис
Это позволяет не повторять слово function и стрелки. Данная запись эквивалентна
Эту форму можно часто встретить в библиотеках идущих в поставку с Objective CAML.
Objective CAML рассматривает функциональное выражение также как любое другое. Значение возвращаемое функциональным выражением называется замыканием. Каждое выражение Objective CAML вычисляется в окружении состоящем из соответствий имя–значение, которые были объявлены до вычисляемого выражения. Замыкание может быть описано как триплет, состоящий из имени формального параметра, тела функции и окружения выражения. Нам необходимо хранить это окружение, поскольку в теле функции кроме формальных параметров могут использоваться другие переменные. В функциональном выражении эти переменные называются свободными, нам понадобится их значение в момент применения функционального выражения.
В случае когда применение замыкания к аргументу возвращает новое замыкание, оно (новое замыкание) получает в свое окружение все необходимые связи для следующего применения. Раздел 1.1.4 подробно рассматривает эти понятия. В главе 3, а так же в главе 11 мы вернемся к тому как замыкание представляется в памяти.
До сих пор рассмотренные функциональные выражения были анонимными, однако мы можем дать им имя.
Функциональное значение объявляется так же как и другие, при помощи конструктора let
Для упрощения записи, можно использовать следующий синтаксис:
что эквивалентно:
Следующие объявления succ и g эквивалентны предыдущим:
В следующем примере демонстрируется функциональная сторона Objective CAML, где функция h1 получена применением g к аргументу. В данном случае мы имеем дело с частичным применением.
С помощью g мы можем определить другую функцию h2 фиксируя значение второго параметра (y):
Некоторые бинарные функции могут быть использованы в инфиксной форме. Например при сложении двух целых мы пишем 3+5 для применения + к 3 и 5. Для того чтобы использовать символ + как классическое функциональное значение, необходимо указать это, окружая символ скобками (op).
В следующем примере определяется функция succ используя (+):
Таким образом мы можем определить новые операторы, что мы и сделаем определив ++ для сложения двух пар целых.
Существуют однако ограничения на определение новых операторов, они должны содержать только символы (такие как *,+,$, etc.), исключая буквы и цифры. Следующие функции являются исключением:
Функциональное значение (замыкание) может быть возвращено как результат, а так же передано как аргумент функции. Такие функции, берущие на входе или возвращающие функциональные значения, называются функциями высшего порядка.
Замечание
Выражения группируются справа налево, но функциональные типы объединяются
слева направо. Таким образом тип функции h может быть написан:
При помощи функций высшего порядка можно элегантно обрабатывать списки. К примеру функция List.map применяет какую-нибудь функцию ко всем элементам списка и возвращает список результатов.
Другой пример — функция List.for_all проверяет соответствуют ли элементы списка определенному критерию.
Для вычисления выражения, необходимо чтобы все используемые им переменные были определены, как, например, выражение e в определении
Переменная p не известна в этом выражении, она может быть использована только в случае если p была объявлена ранее.
В Objective CAML переменные связаны статически. При применении замыкания используется окружение в момент ее (замыкания) объявления (статическая видимость), а не в момент ее применения (динамическая видимость)
В функции k имеется свободная переменная p, которая была определена в глобальном окружении, поэтому определение k принято. Связь между именем p и значением 10 в окружении замыкания k статическая, то есть не зависит от последнего определения p.
Объявление переменной называется рекурсивным, если оно использует свой собственный идентификатор в своем определении. Эта возможность часто используется для определения рекурсивных функций. Как мы видели ранее, let не позволяет делать это, поэтому необходимо использовать специальный синтаксис:
Другой способ записи для функции с аргументами:
Определим функцию sigma вычисляющую сумму целых от 0 до значения указанного аргументом:
Как заметил читатель, эта функция рискует “не закончиться” если входной аргумент меньше 0.
Обычно, рекурсивное значение — это функция, компилятор не принимает некоторые рекурсивные объявления, значения которых не функциональные.
Как мы увидим позднее, такие определения все таки возможны в некоторых случаях (см. 1.2.10 стр. ??).
Объявление let rec может быть скомбинировано с and. В этом случае функции определенные на одном и том же уровне, видны всем остальным. Это может быть полезно при декларации взаимно рекурсивных функций.
По тому же принципу, локальные функции могут быть рекурсивными. Новое определение функции sigma проверяет корректность входного аргумента, перед тем как посчитать сумму локальной функцией sigma_rec.
Замечание
Мы вынужденны были определить возвращаемый тип как string,
поскольку необходимо чтобы он был один и тот же, независимо от входного аргумента,
отрицательного или положительного. Какое значение должна вернуть
sigma если аргумент больше нуля? Далее, мы увидим правильный способ
решения этой проблемы (см. 1.3
стр. ??).
Некоторые функции выполняют одни и те же инструкции независимо от типа аргументов. К примеру, для создание пары из двух значений нет смысла определять функции для каждого известного типа. Другой пример, доступ к первому полю пары не зависит от того, какого типа это поле.
Функция, для которой не нужно указывать тип входного аргумента или возвращаемого значения называется полиморфной. Синтезатор типов, включенный в компилятор Objective CAML находит наиболее общий тип для каждого выражения. В этом случае Objective CAML использует переменные, здесь они обозначены как 'a и 'b, для указания общих типов. Эти переменные конкретизируются типом аргумента в момент применения функции.
При помощи полиморфных функций, мы получаем возможность написания универсального кода для любого типа переменных, сохраняя при этом надежность статической типизации. Действительно, несмотря на то что make_paire полиморфная, значение созданное (make_paire '6' 65) имеет строго определенный тип, который отличен от (make_paire "paire" 451). Проверка типов реализуется в момент компиляции, таким образом универсальность кода никак не сказывается на эффективности программы.
В следующем примере приведена полиморфная функция с входным параметром функционального типа.
Мы можем применить ее к функции impaire, которая была определена ранее.
Функция тождества (id) возвращает полученный аргумент.
Следующая функция, compose принимает на входе две функции и еще один аргумент, к которому применяет две первые.
Как мы видим, тип результата возвращаемого g должен быть таким же как и тип входного аргумента f.
Не только функциональные значения могут быть полиморфными, проиллюстрируем это на примере пустого списка.
Следующий пример иллюстрирует тот факт, что создание типов основывается на разрешении ограничений, накладываемых применением функций, а вовсе не на значениях, полученных в процессе выполнения.
Здесь тип равен List.tl 'a list->'a list, то есть эта функция применяется к списку целых и возвращает список целых. Тот факт что в момент выполнения возвращен пустой список, не влияет на его тип.
Objective CAML создает параметризованные типы для каждой функции, которые не зависят от ее аргументов. Этот вид полиморфизма называется параметрическим полиморфизмом.2
Синтезатор типа Objective CAML образует самый общий тип и иногда бывает необходимо уточнить тип выражения.
Синтаксис ограничения типа следующий:
В этом случае синтезатор типа воспользуется этим ограничением при конструкции типа выражения. Использование ограничения типа позволяет
Рассмотрим использование ограничения типа.
Это ограничение полиморфизма позволяет лучше контролировать тип выражений, тем самым ограничивая тип определенный системой. В таких выражениях можно использовать любой определенный тип.
llint является списком списков любого типа.
В данном случае подразумевается ограничение типа, а не явная типизация заменяющая тип, который определил Objective CAML. В частности, мы не можем обобщить тип, более чем это позволяет вывод типов Objective CAML.
Ограничения типа будут использованы в интерфейсах модулей 13, а так же в декларации классов 14
В этом параграфе мы приведем несколько примеров функций. Большинство из них уже определены в Objective CAML, мы делаем это только в “педагогических” целях.
Тест остановки рекурсивных функций реализован при помощи проверки, имеющей стиль более близкий к Lisp. Мы увидим как это сделать в стиле ML (см. 1.2.1 стр. ??).
Начнем с функции проверяющей пустой список или нет.
Определим функцию size вычисления размера списка (т.е. число элементов).
Функция size проверяет список: если он пуст возвращает 0, иначе прибавляет 1 к длине остатка списка.
Выражение iterate n f вычисляет fn, соответствующее применение функции f n раз.
Функция iterate проверяет аргумент n на равенство нулю, если аргумент равен, то возвращаем функцию идентичности, иначе возвращаем композицию f с итерацией f n-1 раз.
Используя iterate можно определить операцию возведения в степень, как итерацию умножения.
# let power i n = let i_times = (*) i in iterate n i_times 1;; val power : int -> int -> int = <fun> # power 2 8 ;; - : int = 256
Функция power повторяет n раз функциональное выражение i_times, затем применяет этот результат к 1, таким образом мы получаем n-ю степень целого числа.
Напишем функцию multab, которая вычисляет ряд таблицы умножения соответствующую целому числу переданному в аргументе.
Для начала определим функцию apply_fun_list. Пусть f_list список функций, тогда вызов apply_fun_list x f_list возвращает список результатов применения каждого элемента списка f_list к x.
Функция mk_mult_fun_list возвращает список функций умножающих их аргумент на i, 0<=i<=n.
Подсчитаем ряд для 7
Вызов функции fold_left f a[e1;e2;…;en] возвращает f…(f (f a e1) e2) …en, значит получаем n применений.
С помощью функции fold_left можно компактно определить функцию вычисления суммы элементов списка целых чисел.
Или, например конкатенация элементов списка строк.
С помощью типов определеных в Objective CAML мы можем определять структурные типы, при помощи кортежей или списков. Но в некоторых случаях бывает необходимо определить новые типы для описания специальных структур. В Objective CAML, объявления типов рекурсивны и могут быть параметризованы переменными типа, как в случае 'a list который мы уже обсуждали. Вывод типов принимает во внимание новые объявления для определения типов выражений. Конструкция значений новых типов использует конструктор описанный определением типа. Особой возможностью языков семейства ML является сопоставление с образцом, которое обеспечивает простой метод доступа к компонентам (полям) структур данных. Определение функции соответствует чаще всего сопоставлению с образцом по одному из ее параметров, что позволяет определять функции для различных случаев.
Для начала, продемонстрируем механизм сопоставления на существующих типах и затем опишем различные объявления структурных типов, конструкций таких переменных и доступ к компонентам по сопоставлению с образцом.
Образец (по английски pattern) строго говоря не совсем выражение Objective CAML. Речь скорее идет о корректной компоновке (синтаксической и с точки зрения типов) элементов, таких как константы базовых типов (int, bool, char…), переменные, конструкторы и символ _, называемый универсальным образцом. Другие символы служат для записи шаблона, которые мы опишем по ходу.
Сопоставление с образцом применяется к значениям, оно служит для распознания формы этих значений и позволяет определять порядок вычислений. С каждым образцом связано выражение для вычисления.
Синтаксис:
Выражение expr последовательно сопоставляется (фильтруется) с разными образцами p1…,pn. Если один из образцов (например pi) соответствует значению expr, то соответствующее ответвление будет вычислено (expri). Образцы pi одинакового типа, так же как и expri. Вертикальная черта перед первым образцом не обязательна.
Приведем два способа, при помощи сопоставления с образцом, определения функции imply типа (bool * bool)->bool, реализующую логическую импликацию. Образец для пар — (,).
Первая версия перечисляет все возможности, как таблица истинности.
Используя переменные группирующие несколько случаев, мы получаем более компактное определение.
Обе версии imply выполняют одну и ту же функцию, то есть они возвращают одинаковые значения, для одинаковых входных аргументов.
Образец обязательно должен быть линейным, то есть определенная переменная не может быть использована дважды. Мы могли бы написать:
Но для этого компилятор должен уметь реализовывать тесты на равенство, что приводит к множеству проблем. Если мы ограничимся физическим значением переменных, то мы получим слишком “слабую” систему, не в состоянии, например, распознать равенство между двумя списками [1; 2]. Если же мы будет проверять на структурное равенство, то рискуем бесконечно проверять циклические структуры. Рекурсивные функции, например, это циклические структуры, но мы так же можем определить рекурсивные значения не являющиеся функциями (см. 1.2.10 стр. ??).
Символ _ совпадает со всеми возможными значениями — он называется универсальным. Этот образец может быть использован для сопоставления сложных типов. Воспользуемся им для определения еще одной версии функции imply:
Сопоставление должно обрабатывать все случаи, иначе компилятор выводит сообщение:
В случае если аргумент не равен 0, функция не знает какое значение должно быть возвращено. Для исправления добавим универсальный образец:
Если во время выполнения ни один образец не выбран, возбуждается исключение:
Исключение Match_Failure возбуждено при вызове f 4 и если оно не обработано, то вычисление останавливается (см. 1.3 стр. ??).
Комбинация образцов позволяет получить новый образец, который может разложить значение в соответствии с одним или другим из начальных шаблонов.
Синтаксис
Эта форма создает новый образец из комбинации мотивов p1,…,pn, с единственным ограничением — каждый из этих образцов должен содержать константные значения либо универсальный образец.
Следующий пример показывает как проверить является ли входной символ гласной буквой.
Параметризованное сопоставление используется в основном для определения функций выбора. Для облегчения записи подобных определений, конструктор function разрешает следующее сопоставление одного параметра.
Синтаксис
Вертикальная черта перед первым образцом не обязательна. Каждый раз при определении функции, мы используем сопоставление с образцом. Действительно, конструкция function x -> expression является определением сопоставления по уникальному образцу одной переменной. Можно использовать эту особенность в простых шаблонах:
Форма
эквивалентна
Используя схожесть определения на (см. 1.1.4 стр. ??), мы бы написали:
Но подобная запись возможна лишь в случае если фильтруемое значение принадлежит к типу с единственным конструктором, иначе сопоставление не является исчерпывающим:
Иногда при сопоставлении с образцом, бывает необходимо дать имя всему образцу или лишь его части. Следующая синтаксическая форма вводит ключевое слово as, которое ассоциирует имя образцу.
Синтаксис
Это бывает полезно когда необходимо разбить значение на части, сохраняя при этом его целостность. В следующем примере функция возвращает наименьшее рациональное число из пары. Каждое рациональное число представлено числителем и знаменателем.
Для сравнения двух рациональных чисел, необходимо разбить их для именования числителя и знаменателя (n1, n2, d1 и d2), но так же для собирания в одно целое начальные пары (r1 или r2). Конструкция позволяет дать имена частям значения — это избавляет от реконструкции рационального числа при возвращении результата.
Сопоставление с ограничением соответствует вычислению условного выражения сразу после сопоставления с образцом. Если это выражение возвращает значение true, то выражение соответствующее этому образцу будет вычислено, иначе сопоставление будет продолжаться дальше.
Синтаксис:
В следующем примере используется два ограничения для проверки равенства двух рациональных чисел.
Если при фильтрации четвертого образца ограничение не выполнится, то сопоставление продолжится по пятому образцу.
Warning
При проверке исчерпываемости сопоставления Objective CAML предполагает
что условное выражение может быть ложным. В следствии, верификатор не
учитывает этот образец, так как не возможно знать до выполнения сработает
ограничение или нет. Исчерпываемость следующего фильтра не может быть
определена.
При сопоставлении символов, неудобно описывать комбинацию всех образцов, которая соответствует интервалу символов. Действительно, для того чтобы проверить является ли символ буквой, необходимо написать как минимум 26 образцов и скомбинировать их. Для символьного типа разрешается запись следующего шаблона:
Синтаксис
что соответствует 'c1' | 'c2' | ...| 'cn'
К примеру образец
соответствует образу
Первая форма быстрее и проще воспринимается при чтении.
Warning
Это особенность является расширением языка и может
измениться в следующих версиях.
Используя комбинированные образцы и интервалы, напишем функцию по определению символа по нескольким критериям.
Заметим, что порядок образцов важен, второе множество содержит первое, но оно проверяется только после неудачи первого теста.
Как мы уже видели список может быть:
Обе эти записи могут быть использованы в образце при фильтрации списка.
Перепишем раннее показанный пример (см. 1.1.6 стр. ??) используя сопоставление с образом для итерации списков.
Объявление значений само по себе использует сопоставление. let x=18 сопоставляет образцы x со значением 18. Любой образец принимается как фильтр объявления, переменные образца ассоциируются со значениями которые они сопоставляют.
Видимость переменных фильтра та же самая что у локальных переменных. Здесь c ассоциировано с 'A'.
Как и любой фильтр, определение значения может быть не исчерпывающим.
Принимается любой образец, включая конструктор, универсальный и комбинированный.
Последний пример мало интересен для функционального программирования, поскольку значение 3.14 не именовано, и соответственно будет потерянно.
Объявление типа — это одна из других возможных фраз синтаксиса Objective CAML. Она позволяет определить новые типы соответствующие обычным структурам данных используемым в программах. Существует два больших семейства типов: тип–произведение для кортежей или записей или тип–сумма для union.
Синтаксис:
В отличии от объявления переменных, объявление типов по умолчанию рекурсивно. То есть объявления типов, когда они скомбинированы, могут объявлять взаимно рекурсивные типы.
Синтаксис:
Объявления типов могут быть параметризованы переменной типа. Имя переменной типа начинается всегда с апострофа (символ ').
Синтаксис
В случае когда таких переменных несколько, параметры типа декларируются как кортеж перед именем типа.
Синтаксис
Только те параметры, которые определены в левой части декларации, могут появится в ее правой части.
Замечание
Во время вывода на экран Objective CAML переименует параметры типа,
первый в 'a, второй в 'b и так далее.
Мы всегда можем объявить новый тип используя ранее объявленные типы.
Синтаксис:
Это полезно в том случае, когда мы хотим ограничить слишком общий тип:
Без ограничения, выводится наиболее общий тип:
Но мы можем использовать ограничитель типа для того, чтобы получить желаемое имя:
Запись — это кортеж, в котором каждому полю присваивается имя на подобии record в Pascal или struct в C. Запись всегда соответствует объявлению нового типа. Для определения записи необходимо указать ее имя, а так же имя и тип для каждого поля записи.
Синтаксис:
Определим тип комплексного числа следующим образом.
Для того чтобы создать значение типа запись, нужно присвоить каждому полю значение (в каком угодно порядке).
Синтаксис:
В следующем примере мы создадим комплексное число, в котором реальная часть равна 2 и мнимая 3:
В случае если не хватает некоторых полей, произойдет следующая ошибка:
Доступ к полям возможен двумя способами: синтаксис с точкой, либо сопоставлением некоторых полей.
Синтаксис с точкой заключается в следующем:
Синтаксис:
Выражение expr должно иметь тип “запись с полем nom”.
Сопоставление записи позволяет получить значение связанное с определенным полям. Синтаксис образца для записи следующий.
Синтаксис
Образцы находятся справа от символа = (pi, ..., pj). Необязательно перечислять все поля записи в образце.
Функция add_complex обращается к полям с помощью “точки”, тогда как функция mult_complex обращается при помощи фильтра.
Преимущество записей, по сравнению с кортежами как минимум двойное:
При сопоставлении с образцом не обязательно перечислять все поля записи, тип будет вычислен по последней описанной записи, которая содержит указанные поля.
Существует конструкция позволяющая создать идентичную запись, с разницей в несколько полей, что удобно для записей с большим числом полей.
Синтаксис:
Новая копия значения b отличается только лишь значением поля x1.
Warning
Это особенность является расширением языка и может
измениться в следующих версиях.
В отличии от кортежей или записей, которые соответствуют декартовому произведению, тип сумма соответствует объединению множеств (union). В один тип мы группируем несколько разных типов (например, целые числа и строки). Различные члены суммы определяются конструкторами, которые с одной стороны позволяют сконструировать значение этого типа и с другой получить доступ к компонентам этих значений при помощи сопоставления с образцом. Применить конструктор к аргументу, значит указать что возвращаемое значение будет этого нового типа.
Тип сумма описывается указыванием имени конструкторов и типа их возможного аргумента.
Синтаксис:
Имя конструктора это специальный идентификатор.
Замечание
Имя конструктора должно всегда начинаться с заглавной буквы.
Мы называем константным, конструктор без аргументов. Такие конструктора могут затем использоваться как значения языка, в качестве констант.
(Орел Решка)
Тип может быть определен подобным образом.
Конструктора могут иметь аргументы, ключевое слово of указывает тип аргумента. Это позволяет сгруппировать под одним типом объекты разных типов, имеющих разные конструктора. Определим типы couleur и carte следующим образом.
N.B.
Создание значения типа carte получается применением конструктора к значению с нужным типом.
Следующая функция, toutes_les_cartes, создает список всех карт цвета указанного аргументом.
Для манипуляции значений типа сумма, мы используем сопоставление с образцом. В следующем примере опишем функцию преобразующую значения типа couleur и типа carte в строку (тип string):
Конструктор Petite_carte бинарный, для сопоставления такого значения мы должны дать имя обоим компонентам.
Чтобы не давать имя каждой компоненте конструктора, обьявим его с одним аргументом, заключив в скобки тип ассоциированного кортежа. Сопоставление двух следующих конструкторов отличается.
Определение рекурсивного типа необходимо в любом языке программирования, с его помощью мы можем определить такие типы как список, стек, дерево и так далее. В отличии от объявления let, type всегда рекурсивный в Objective CAML.
Типу список, определенному в Objective CAML, необходим один единственный аргумент. Для того чтобы хранить значения двух разных типов, как например int или char мы напишем:
Мы также можем определить тип с параметрами, что позволит нам обобщить предыдущий список для двух любых типов.
Естественно, оба параметра 'a и 'b могут быть одного типа:
Как в предыдущем примере, мы можем использовать тип list2 чтобы пометить четные и нечетные числа. Что бы создать обычный список, достаточно извлечь под–список четных чисел.
Определение этой функции ничего не говорит о свойстве значений хранящихся в структуре, по этой причине ее тип параметризован.
На имена конструкторов распространяются те же правила, что и на глобальные объявления. Переопределение скрывает своего предшественника. Скрытые значения всегда существуют, они никуда не делись. Однако цикл не сможет различить эти оба типа, поэтому мы получим не совсем понятное сообщение об ошибке.
В следующем примере, константный конструктор Nil типа int_of_char скрывается объявлением конструктора ('a, 'b) list2.
Во втором примере мы получим совсем бестолковое сообщение, по крайней мере на первый взгляд. Пусть мы имеем следующую программу:
Затем переопределим тип t1:
Теперь если мы применим функцию empty_t1 к значению с новым типом t1, то получим следующее сообщение.
Первое упоминание типа t1 соответствует ранее определенному типу, тогда как второе — последнему.
Тип аргумента конструктора может быть каким угодно, и в частности он может быть функциональным. Следующий тип создает список состоящий из функциональных значений, кроме последнего элемента.
Поскольку функциональные значения входят во множество значений которые обрабатываются языком, то мы можем создать значения типа listf:
функция сопоставляющая подобные значения:
Деревья — одна из часто встречающихся структур в программировании. Рекурсивные типы позволяют с легкостью определять подобные вещи. В этой части мы приведем два примера с такими структурами.
Определим дерево, в котором узлы обозначены значениями одного и того же типа:
Этой структурой мы воспользуемся в программе сортировки бинарных деревьев. Бинарное дерево имеет следующее свойство: значение левого дочернего узла меньше корневого и всех значений правых дочерних узлов.
Извлечем значения узлов в виде сортированного списка при помощи инфиксного просмотра следующей функцией:
Для того чтобы получить из списка бинарное дерево, определим функцию:
Функция трансформирующая список в бинарное дерево может быть получена использованием функции ajout
Тогда функция сортировки это всего–навсего композиция функций arbre_of_list и list_of_arbre.
3
Воспользуемся функцией определенной в модуле List (см. 7 стр. ??):
Общее планарное дерево — это дерево в котором нет ограничения на число дочерних узлов: каждому узлу ассоциируем список дочерних узлов и длина этого списка не ограничена.
Пустое дерево представлено значением Empty, лист — это узел без дочерних узлов формы Node(х,[]) или Node(x, [Empty;Empty;..]). Таким образом достаточно просто написать функции, манипулирующие подобными деревьями такие как принадлежность элемента дереву или вычисление высоты дерева.
Для проверки принадлежности элемента e воспользуемся следующим алгоритмом: если дерево пустое, тогда элемент e не принадлежит этому дереву, в противном случае e принадлежит дереву только если он равен значению корня дерева или принадлежит дочерним узлам.
Для вычисления высоты дерева, напишем следующую функцию: высота пустого дерева равна 0, в противном случае его высота равна высоте самого большого под–дерева плюс 1.
Рекурсивное объявление не функциональных значений позволяет конструировать циклические структуры данных.
Следующее объявление создает циклический список одного элемента.
Применение рекурсивной функции к подобному списку приведет к переполнению памяти.
Структурное равенство таких списков может быть проверенно лишь в случае, когда физическое равенство верно.
В случае, если мы определим такой же новый список, не стоит использовать проверку на структурное равенство, под угрозой зацикливания программы. Таким образом следующая инструкция не рекомендуется.
Однако, физическое равенство остается возможным.
Предикат == сравнивает непосредственно значение или разделения структурного объекта (одним словом равенство по адресу). Мы воспользуемся этим тестом для того чтобы при просмотре списка, не проверять уже просмотренные под-списки. Сначала, определим функцию memq которая проверяет присутствие элемента в списке при помощи физического равенства. В это же время функция mem проверяет равенство структурное. Обе функции принадлежат модулю List.
Функция вычисляющая размер списка определена при помощи списка уже проверенных списков и останавливается при встрече списка второй раз.
Вычисленный тип функции принадлежит подмножеству множества в котором она определена. Если входной аргумент функции типа int, это не значит что она сможет быть выполнена для любого переданного ей целого числа. Таких случаях мы используем механизм исключений Objective CAML. Запуск исключения провоцирует остановку вычислений, которое может быть выявлено и обработано. Для этого необходимо установить обработчик исключения, до того как исключение может быть возбуждено.
Область определения функции соответствует множеству значений которыми функция манипулирует. Существует множество математических частичных функций, таких как например, деление или натуральный логарифм. Проблемы возникают в том случае, когда функция манипулирует более сложными структурами данных. Действительно, каков будет результат функции определяющей первый элемент списка, если список пуст. Аналогично, вычисление факториала для отрицательного числа приводит к бесконечному вычислению.
Определенное число исключительных ситуаций может произойти во время выполнения программы, как например деление на ноль. Попытка деления на ноль может привести в лучшем случае к остановке программы и в худшем к неправильному (некоэрантному) состоянию машины. Безопасность языка программирования заключается в гарантии того, что такие случаи не возникнут. Исключение есть один из способов такой гарантии.
Деление 1 на 0 провоцирует запуск специального исключения:
Сообщение Uncaught exception: Division_by_zero указывает во первых на то, что исключение Division_by_zero возбуждено и во вторых, что оно не было обработано.
Часто, тип функции не соответствует области ее определения в том случае когда сопоставление с образцом не является полным, то есть когда он не отслеживает все возможные случаи. Чтобы избежать такой ситуации, Objective CAML выводит следующее сообщение.
Однако, если программист все таки настаивает на своей версии, то Objective CAML воспользуется механизмом исключения в случае неправильного вызова частичной функции.
Мы уже встречали другое исключение определенное в Objective CAML: Failure, с входным аргументом типа string. Запустить это исключение можно функцией failwith. Воспользуемся этим и дополним определение функции tete.
В Objective CAML, тип исключений — exn. Это особенный тип — расширяемая сумма: мы можем увеличить множество значений этого типа объявляя новые конструкторы. Такая особенность позволяет программисту определять свои собственные исключения.
Синтаксис объявления следующий:
Синтаксис:
Синтаксис:
Вот несколько примеров объявления исключений.
Имена исключений являются конструкторами — это значит они должны начинаться с заглавной буквы.
Warning
Исключения мономорфны, при объявлении типа аргумента мы не можем указать
параметризующий тип.
Полиморфное исключение позволило бы определение функций, возвращающих результат любого типа. Подобный пример мы рассмотрим далее на стр. ??.
raise — функциональный примитив языка Objective CAML, ее входной аргумент есть исключение, а возвращает он полиморфный тип.
В Objective CAML нет возможности написать функцию raise, она должна быть определена системой.
Весь интерес возбуждения исключений содержится в возможности их обработать и изменить выполнение программы в зависимости от этого исключения. В этом случае, порядок вычисления выражения имеет значение для того чтобы определить какое исключения было запущенно. Таким образом мы выходим из рамок чисто функционального программирования, потому как порядок вычисления аргументов может изменить результат. Об этом мы поговорим в следующей главе (стр. ??)
Следующая конструкция, вычисляющая значение какого–то выражения, отлавливает исключение, возбужденого во время этого вычисления.
Синтаксис:
Если вычисление expr не возбудит исключения, то тип результата будет типом подсчитываемым этим выражением. Иначе, в приведенном выше сопоставлении будет искаться ответвление соответствующее этому исключению и будет возвращено значение следующего за ним выражения.
Если ни одно ответвление не соответствует исключению, то оно будет переправлено до следующего обработчика try–with установленного в программе. Таким образом сопоставление исключения всегда исчерпывающий. Подразумевается что последний фильтр |e->raise e. Если ни одного обработчика не найдено в программе, система сама займется обработкой этого исключения и остановит программу с выводом сообщения об ошибке.
Важно понимать разницу между вычислением исключения (то есть значение типа exn) и его обработкой, которое приостанавливает вычисления. Исключение, как и любой другой тип, может быть возвращено функцией.
Как вы наверно заметили, функция declencher (запустить) не возвращает значение типа exn, тогда как rendre (вернуть) возвращает.
Кроме обработки не желаемых значений, исключения можно использовать для оптимизации. Следующий пример реализует произведение всех элементов списка целых чисел. Мы воспользуемся исключением для остановки просмотра списка если обнаружим 0, который мы вернем как результат функции.
Оставшиеся вычисления, то есть произведения элементов после встреченного нуля, не выполняются. После встречи raise, вычисление вновь продолжится с with.
Полиморфизм Objective CAML позволяет определить функции, тип возвращаемого выражения которых конкретно не определен. Например:
Однако, возвращаемый тип id зависит от типа аргумента. Таким образом, если мы применим функцию id к какому-нибудь аргументу, то механизм вывода (определения) типа сможет реализовать переменную типа 'a. Для каждого частного использования тип функции id может быть определен.
Иначе, использование жесткой статической типизации, которая обеспечивает правильность выполнения, не будет иметь смысла. Функция с полностью неопределенным типом как 'a->'b, разрешит какое попало преобразование типа, что привело бы к ошибке выполнения, так как физическое представление значений не одно и то же.
Мы можем определить функции, которые возвращают значение, тип которого не соответствует типу аргументов. Рассмотрим несколько примеров и проанализируем почему это не противоречит жесткой статической типизации.
Вот первый пример:
Эта функция конструирует полиморфные значения из любого типа.
Однако, полученное значение не совсем является не определенным — подразумевается список. Таким образом она не может использоваться где попало.
Вот три примера функций типа 'a -> 'b :
Эти функции не являются “опасными” в отношении правильности выполнения программы, так как их невозможно использовать для конструкции значений: первая зацикливается, две последние запускают исключение, которые останавливают выполнение программы.
Чтобы не было возможности определить функции типа 'a -> 'b, новые конструкторы исключений не должны иметь аргументы типы которых содержат переменную.
Если бы могли объявить полиморфное исключение Poly_exn типа 'a -> exn, то тогда следующая функция была бы возможна:
Таким образом, тип функции f это int->int и тип Poly_exn это 'a -> exn, теперь напишем следующее:
Это правильно типизированная функция (поскольку аргумент Poly_exn может быть каким угодно) и вызов g 0 попытается сложить целое с булевым значением!
Для того чтобы понять как организуются программы на Objective CAML, необходимо самим реализовать такую программу. Напишем калькулятор манипулирующий целыми числами при помощи 4 стандартных операций.
Для начала, определим тип key, для представления кнопки калькулятора. Всего таких кнопок будет 15: по одной для каждой операции, для каждой цифры и для кнопки равно.
Заметим, что цифровые кнопки сгруппированы под одним конструктором Digit с аргументом целого типа. Таким образом, некоторые значения типа key не являются на самом деле кнопкой. Например, (Digit 32) есть значение типа key, но не представляет ни одну кнопку калькулятора.
Напишем функцию valid которая проверяет входной аргумент на принадлежность к типу key. Тип функции key->bool.
На первом этапе определим функцию проверяющую что число принадлежит интервалу 0-9. Объявим ее с именем is_digit.
Теперь функция valid фильтрующая свой аргумент тип которого key:
Первый фильтр применяется в случае если входной аргумент построен конструктором Digit, в этом случае он проверяется функцией is_digit. Второй фильтр применяется в любом другом случае. Напомним, что благодаря фильтру, тип фильтруемого значения обязательно будет key.
Перед тем как начать реализовывать алгоритм калькулятора, определим модель формально описывающую реакцию на нажатие кнопок. Мы подразумеваем что калькулятор располагает памятью в которой хранится результат последней операции, последняя нажатая кнопка, последний использованный оператор и число выведенное на экран. Все эти 4 значения назовем состоянием калькулятора, оно изменяется каждый раз при нажатии на одну из кнопок. Это изменение называется транзицией, а теория управляющая подобным механизмом есть теория автоматов.
Состояние представлено следующим типом:
В таблице 1.5 приведен пример состояний калькулятора.
Нам нужна функция evaluate с тремя аргументами: двумя операндами и оператором, она возвращает результат операции. Для этого функция фильтрует входной аргумент типа key:
Дадим определение транзиций, перечисляя все возможные случаи. Предположим, что текущее состояние есть квадри-плет (a,b,A,d):
Для того чтобы написать функцию transition, достаточно дословно перевести в Objective CAML предыдущее описание при помощи сопоставления входного аргумента. Кнопку с двумя сначениями обработаем локальной функцией digit_transition при помощи сопоставления.
Эта функция из state и key считает новое состояние state.
Протестируем теперь программу:
Мы можем сделать тоже самое, передав список транзиций.
В этой главе мы изучили основы функционального программирования и параметризованный полиморфизм, что вместе являются основными характеристиками Objective CAML. Также мы описали синтаксис функциональной части ядра и типов. Это дало нам возможность написать первые программы. Так же мы подчеркнули глубокую разницу между типом функции и областью ее применения. Механизм исключений позволяет решить эту проблему, и в то же время вводит новый стиль программирования, где мы явно указываем манеру вычисления.