|
OCaml
OCaml (Objective Caml) — объектно-ориентированный язык функционального программирования общего назначения. Был разработан с учётом безопасности исполнения и надёжности программ. Поддерживает функциональную, императивную и объектно-ориентированную парадигмы программирования. Самый распространённый в практической работе диалект языка ML. Появился в 1996 году под названием Objective Caml, когда Дидье Реми (Didier Rémy) и Жером Вуйон (Jérôme Vouillon) реализовали поддержку объектно-ориентированного программирования для языка Caml, первоначально разработанного во французском институте INRIA. Официально переименован в OCaml в 2011 году[3]. Инструментарий OCaml включает в себя интерпретатор, компилятор в байткод и оптимизирующий компилятор в машинный код, сравнимый по эффективности с Java и лишь немного уступающий по быстродействию C и C++[4]. На языке, в частности, написан рендеринг формул Википедии, использующих тег <math>, файлообменный клиент MLDonkey, стек управления гипервизором Xen xapi (является частью Xen Server/Xen Cloud Platform), язык программирования Haxe. Роль в информатикеЯвляется языком программирования общего назначения, но при этом имеет свои сложившиеся области применения[5]. Во-первых, это — создание «безопасных» (не только в смысле информационной безопасности) приложений. В языке используется сборка мусора, а большинство типов данных является ссылочным (англ. boxed), что означает предотвращение переполнения буферов во время исполнения программы. Кроме того, статическая типизация и проверки времени компиляции делают невозможными некоторые другие классы ошибок, такие, как ошибки приведения типов в силу отсутствия автоматического приведения типов. Кроме того, код может быть формально верифицирован. Имеются утилиты автоматического доказательства типовой корректности кода, превосходящие таковые для большинства языков программирования. И что немаловажно, меры безопасности не влияют на эффективность исполняемого кода[5]. Другой областью успешного применения OCaml являются приложения, управляемые данными (data-driven). К этой области относится обработка текста, а также написание компиляторов. OCaml имеет не только средства для текстовой обработки (какими славится, например, Perl или AWK), но и инструменты для глубокого семантического анализа и преобразования текста, что делает OCaml применимым в задачах интеллектуального анализа данных (англ. data mining)[5]. OCaml, как и другие диалекты ML, используются в исследовательских задачах и задачах верификации, при котором основной код пишется на некотором языке программирования, а затем формально верифицируется и анализируется программой на OCaml[5]. Например, на OCaml написана система интерактивного доказательства теорем Coq. Занимает особое место среди языков программирования благодаря сочетанию эффективности, выразительности и практичности. Среди особенностей языка, развивавшихся в течение более чем 40 лет, со времени создания ML, выделяют следующие[6]:
ИсторияOCaml ведёт своё происхождение от ML (англ. meta language), который был реализован на диалекте Лиспа Робином Милнером в 1972 году в качестве программного средства для доказательства теорем, как метаязык логики вычислимых функций (LCF, англ. logic for computable functions). Позднее был сделан компилятор, а к 1980 году ML стал полноценной системой программирования[7]. Ги Кузино (Guy Cousineau) добавил в язык алгебраические типы данных и сопоставление с образцом и определил ML в виде категориальной абстрактной машины (CAM). Таким образом, CAM-ML мог быть описан, верифицирован и оптимизирован, что явилось шагом вперёд для ML[8]. Дальнейшим развитием был созданный к 1987 году Аскандером Суарецом (Ascánder Suárez) и продолженный Пьером Вейсом (Pierre Weis) и Мичелом Мони (Michel Mauny) язык Caml (переигранное CAM-ML)[7][8]. В 1990 году Ксавье Лерой (Xavier Leroy) и Дамьен Долигез (Damien Doligez) выпустили новую реализацию, названную Caml Light. В этой реализации на Си использовался интерпретатор байт-кода и быстрый сборщик мусора. С написанием библиотек язык стал использоваться в образовании и исследовательских институтах[7][8]. В 1995 году увидел свет Caml Special Light, развиваемый К. Лероем. Система программирования получила компилятор в машинные коды, что поставило эффективность исполняемого кода в один ряд с другими компилируемыми языками. В то же время была разработана система модулей, идея которой была заимствована из Standard ML[7]. В современном виде OCaml появился в 1996 году, когда Дидье Реми (Didier Rémy) и Джером Вуйон (Jérôme Vouillon) реализовали для языка стройную и эффективную поддержку объектов. Эта объектная система позволяет на этапе компиляции в типобезопасной манере использовать идиомы объектно-ориентированного программирования, без свойственных C++ и Java проверок времени выполнения[7]. В 2000-х годах язык плавно развивался, одновременно получая всё большее признание в коммерческих проектах и образовании. Среди разработанного в это время можно отметить полиморфные методы и вариантные типы, именованные и необязательные параметры, модули первого класса, обобщённые алгебраические типы данных (GADT). Язык стал поддерживать несколько аппаратных платформ (X86, ARM, SPARC, PowerPC)[7][8]. Базовая семантика
Модель вычислений OCaml как языка функционального программирования строится на трёх основных конструкциях лямбда-исчисления: переменных, определениях функций и применении функции к аргументам[9]. Переменные
Переменная — идентификатор, значение которого связано с определённой величиной. Имена переменных начинаются со строчной буквы или подчёркивания. Привязка обычно выполняется с помощью ключевого слова let v = 1 ;;
Переменные имеют область видимости. Например, в интерактивной оболочке переменную можно использовать в следующих за её привязкой командах. Аналогично, переменную, определённую в модуле, можно использовать после определения в данном модуле[10]. Привязка переменной может быть осуществлена и в области видимости, заданной конструкцией let-in, как в следующем примере по вычислению площади круга по радиусу: # let area radius =
let pi = 3.14 in
radius *. radius *. pi ;;
val area : float -> float = <fun>
# area 2.0 ;;
- : float = 12.56
В OCaml привязки переменных являются неизменяемыми (как в математических уравнениях), то есть, значение переменной «присваивается» только один раз (единичное присваивание). Другое дело, что внутри let-in может быть другой let-in, в котором вводится другая переменная, которая может «затенить» первую[10]. ФункцииДля определения функций в OCaml есть несколько синтаксических конструкций. Функции можно определить с помощью ключевого слова function x -> x + 1
В данном случае функция анонимная, и её можно использовать в качестве параметров других функций или применить к некоторому аргументу, например: (function x -> x + 1) 5
Типом этой функции является Функция может иметь несколько аргументов[12]: function (x, y) -> x - y
В этом примере её тип: Есть и другой подход представления функций нескольких аргументов — преобразование N-арной функции в N функций одного аргумента — каррирование. Следующие два вида записи функции, вычисляющей произведение целочисленных аргументов, эквивалентны[12]: function x -> function y -> x * y
fun x y -> x * y
Именованные функции можно получить, связав переменную с функцией[11]. Определение именованной функции настолько частая операция, что имеет отдельную синтаксическую поддержку. Следующие три записи — эквивалентные способы определить функцию (в интерактивной оболочке): # let prod = function x -> function y -> x * y ;;
val prod : int -> int -> int = <fun>
# let prod x y = x * y ;;
val prod : int -> int -> int = <fun>
# let prod = fun x y -> x * y ;;
val prod : int -> int -> int = <fun>
Функции двух аргументов можно определить для использования инфиксной записи[11]: # let (^^) x y = x**2.0 +. y**2.0 ;;
val ( ^^ ) : float -> float -> float = <fun>
# 2.0 ^^ 3.0 ;;
- : float = 13.
# (^^) 2.0 3.0 ;;
- : float = 13.
В этом примере определена функция Рекурсивные функции, то есть функции, ссылающиеся на своё же определение, можно задать с помощью # let rec fac n =
match n with
| 0 -> 1
| x -> x * fac (x - 1)
;;
В этом же примере вычисления факториала применено сопоставление с образцом (конструкция Аргументы функции можно определить как именованные. Именованные аргументы можно указывать в любом порядке[11]: # let divmod ~x ~y = (x / y, x mod y) ;;
val divmod : x:int -> y:int -> int * int = <fun>
# divmod ~x:4 ~y:3 ;;
- : int * int = (1, 1)
# divmod ~y:3 ~x:4 ;;
- : int * int = (1, 1)
В OCaml можно опускать значения, используя уплотнённую запись (англ. label punning), если имя параметра и переменной совпадают[11]: # let x = 4 in
let y = 3 in
divmod ~x ~y ;;
- : int * int = (1, 1)
Выражения
Ассоциативность операций в выражениях OCaml определяется префиксом, распространяясь таким образом на операции, определённые пользователем. Знак
Система типовПримитивные типыЯзык OCaml имеет несколько примитивных типов: числовые типы (целый и числа с плавающей запятой), символьный, строки символов, булевый[14]. Целый тип представляет целые числа из интервала [−230, 230 − 1] и [−262, 262 − 1] для 32- и 64-битных архитектур соответственно. С целыми числами можно производить обычные операции сложения, вычитания, умножения, деления, взятия остатка от деления: Числа с плавающей запятой представляются 53-битной мантиссой и порядком из интервала [−1022, 1023], следуя стандарту IEEE 754 для чисел с двойной точностью. В операциях эти числа нельзя смешивать с целыми. Кроме того, операции над числами с плавающей запятой синтаксически отличаются от целочисленных операций: Для чисел с плавающей запятой имеются и другие математические функции: тригонометрические (sin, cos, tan, asin, acos, atan), округления (ceil, floor), экспоненциальная (exp), логарифмические (log, log10), а также извлечение квадратного корня (sqrt)[15]. Для числовых типов имеются и полиморфные операции сравнения[15]. Символьный тип — char — соответствует представлению символа с кодом от 0 до 255 (первые 128 символов совпадают с ASCII). Строчный тип — string — последовательность символов (максимальная длина: 224 — 6)[16]. Пример с использованием функции преобразования целого к строке и операции конкатенации: # "Example " ^ string_of_int(2) ;;
- : string = "Example 2"
Булевый тип имеет два значения: Булевые значения получаются в результате сравнений: Кроме того, в OCaml имеется специальный тип unit, который имеет всего одно значение — СпискиВ OCaml список — конечная неизменяемая последовательность элементов одного типа, реализованная как односвязный список. Следующий пример демонстрирует синтаксис списка[18]: # ['a'; 'b'; 'c'] ;;
- : char list = ['a'; 'b'; 'c']
# 'a' :: ('b' :: ('c' :: [])) ;;
- : char list = ['a'; 'b'; 'c']
# 'a' :: 'b' :: 'c' :: [] ;;
- : char list = ['a'; 'b'; 'c']
# [] ;;
- : 'a list = []
Операция # let lst = [1; 2] ;;
val lst : int list = [1; 2]
# let lst1 = 0 :: lst ;;
val lst1 : int list = [0; 1; 2]
# lst ;;
- : int list = [1; 2]
# lst1 ;;
- : int list = [0; 1; 2]
Пример: вычисление суммы элементов спискаСписок является одним из основных типов данных в OCaml. Следующий пример кода определяет рекурсивную (обратите внимание на ключевое слово rec) функцию, которая перебирает элементы данного списка и возвращает их сумму: let rec sum xs =
match xs with
| [] -> 0
| x :: xs' -> x + sum xs'
# sum [1;2;3;4;5];; - : int = 15 Другой способ подсчёта суммы заключается в использовании функции свёртки: let sum xs =
List.fold_left (+) 0 xs
# sum [1;2;3;4;5];;
- : int = 15
ЗаписиЗаписи являются важным элементом в системе типов OCaml. Запись представляет собой набор хранимых вместе значений, при котором каждый элемент значения-записи доступен по своему имени — имени поля записи. Пример описания типа, связывания записи с переменной и доступ к полю записи[19]: # type user =
{ login : string;
password : string;
nick : string;
};;
# let usr = { login = "myuser"; password = "secret"; nick = "aka" ; } ;;
val usr : user = {login = "myuser"; password = "secret"; nick = "aka"}
# usr.nick ;;
- : string = "aka"
Следует заметить, что тип переменной usr был установлен компилятором автоматически. Как и в случае с другими типами, тип может быть параметризован. Другие возможности записей[19]:
Вариантный типВариантный тип представляет данные, которые могут принимать различные формы, определяемые явно заданными метками. В следующем примере определён тип для базовых цветов[20]: # type main_color = Red | Green | Blue ;;
# Blue ;;
- : main_color = Blue
# (Red, Blue) ;;
- : main_color * main_color = (Red, Blue)
В примере выше вариантный тип используется в качестве перечислимого типа. В OCaml вариантный тип, тем не менее, является более богатым, так как помимо меток позволяет задавать и данные, например: # type color_scheme = RGB of int * int * int | CMYK of float * float * float * float;;
type color_scheme =
RGB of int * int * int
| CMYK of float * float * float * float
При определении функций вариантный тип естественно сочетается с сопоставлением с образцом. ОбъектыВ OCaml объекты и их типы полностью отделены от системы классов. Классы используются для построения объектов и поддержки наследования, но не являются типами объектов. Объекты имеют собственные объектные типы (object types), и для работы с объектами классы применять необязательно. Объекты не так часто используются в OCaml (так, система модулей является более выразительной, чем объекты, так как модули могут включать типы, а классы и объекты — нет). Основным преимуществом объектов перед записями — они не требуют объявления типов и обладают большей гибкостью благодаря полиморфизму строчных переменных (англ. row polymorphism). С другой стороны, преимущества объектов проявляются при использовании системы классов. В отличие от модулей, классы поддерживают позднее связывание, что позволяет ссылаться на методы объекта без статически заданной реализации и использовать открытую рекурсию (в случае с модулями можно использовать функции и функторы, но синтаксически такие описания требуют написания большего количества кода)[21]. Вывод типовХотя OCaml является языком программирования с сильной типизацией, система вывода типов (англ. type inference) позволяет определять тип выражения на основе имеющейся информации о его компонентах. В следующем примере функции проверки числа на чётность не указано ни одной декларации типа, и тем не менее у компилятора языка есть полная информация о типе функции[22]: # let odd x = x mod 2 <> 0 ;;
val odd : int -> bool = <fun>
Императивное программирование и функции с побочными эффектамиПомимо функциональных, язык содержит средства императивного программирования: функции с побочными эффектами, изменяемые (mutable) данные, императивные синтаксические конструкции, в частности, явные циклы Следующий пример напечатает на стандартном выводе (это — побочный эффект функции printf) 11 строк: for i = 0 to 10 do
Printf.printf "i =%d\n" i
done;;
В следующем (довольно искусственном) примере элементы массива на месте увеличиваются на единицу в цикле с предусловием. Для индекса массива используется ссылка (ref), которая инкрементируется в теле цикла: # let incr_ar ar =
let i = ref 0 in
while !i < Array.length ar do
ar.(!i) <- ar.(!i) + 1;
incr i
done ;;
val incr_ar : int array -> unit = <fun>
# let nums = [|1;2;3;4;5|];;
val nums : int array = [|1; 2; 3; 4; 5|]
# incr_ar nums;;
- : unit = ()
# nums;;
- : int array = [|2; 3; 4; 5; 6|]
Побочные эффекты позволяют оптимизировать вычисления, в особенности, когда речь идёт о значительных преобразованиях на больших массивах данных. Также с их помощью реализуются ленивые вычисления и мемоизация[23]. Крупномасштабное программирование
Модульность
OCaml можно представить себе как состоящий из двух языков: язык ядра со значениями и типами и язык модулей и их сигнатур. Эти языки образуют два слоя в том смысле, что модули могут содержать типы и значения, а обычные значения не могут содержать модулей и модулей-типов. Тем не менее, OCaml предлагает механизм модулей первого класса, которые могут быть значениями и при необходимости преобразуются в обычные модули и обратно[24]. ФункторыСистема модулей OCaml не ограничивается модульной организацией кода и интерфейсами. Одними из важных инструментов обобщённого программирования являются функторы. Упрощённо говоря, функторы являются функцией из модуля в модули, что позволяет реализовать следующие механизмы[25]:
Примеры программЗапуск интерпретатора OCamlДля запуска интерпретатора языка OCaml необходимо в консоли ввести следующую команду: $ ocaml
OCaml version 4.08.1
#
Вычисления можно производить в интерактивном режиме, например: # 1 + 2 * 3;;
- : int = 7
Hello worldСледующая программа «hello.ml»: print_endline "Hello World!";;
может быть скомпилирована либо в байт-код: $ ocamlc hello.ml -o hello
либо в оптимизированный машинный код: $ ocamlopt hello.ml -o hello
и запущена: $ ./hello
Hello World!
$
Быстрая сортировкаВ следующем примере приведён алгоритм быстрой сортировки, который сортирует список в порядке возрастания: let rec qsort = function
| [] -> []
| pivot :: rest ->
let is_less x = x < pivot in
let left, right = List.partition is_less rest in
qsort left @ [pivot] @ qsort right
Последовательность Фибоначчиlet rec fib_aux n a b =
match n with
| 0 -> a
| _ -> fib_aux (n - 1) (a + b) a
let fib n = fib_aux n 0 1
См. такжеПримечания
Литература
Важно: некорректность перевода в русском издании Примечание — в книге используется перевод термина «first-class function» как «функция первого порядка». Но следует иметь в виду, что в многочисленных англоязычных источниках (по семантике языков вообще и по ML и Хиндли-Милнеру в частности) концептуально различается четыре понятия:
причём «first-class» — это «лучше», чем «second-class» (шире по возможностям, ближе к теории и выше по порогу вхождения (C. Strachey — Fundamental Concepts in Programming Languages)), но «first-order» примитивнее, чем «high-order». В частности, расширение языка модулей ML до уровня «first-class high-order» представляет собой существенно большую проблематику для исследователей, чем его расширение только до «first-class» или только до «high-order» (Rossberg A. Functors and runtime vs compile time. Дата обращения: 25 июня 2015. Архивировано из оригинала 26 июня 2015 года.).
Ссылки
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
