Rstykt

Objective Caml
Семантика	мультипарадигмальный: функциональный, объектно-ориентированный, императивный
Класс языка	объектно-ориентированный язык программирования, язык функционального программирования, мультипарадигмальный язык программирования, императивный язык программирования[d] и язык программирования
Появился в	1996
Автор	INRIA
Разработчик	INRIA
Расширение файлов	.ml, .mli
Выпуск	4.04.0 (4 ноября 2016)[1]
Система типов	строгая, статическая
Диалекты	F#, JoCaml, MetaOCaml, OcamlP3l
Испытал влияние	Standard ML, Caml Light
Лицензия	LGPL
Сайт	ocaml.org

OCaml (Objective Caml) — современный объектно-ориентированный язык функционального программирования общего назначения, который был разработан с учётом безопасности исполнения и надёжности программ. Этот язык имеет высокую степень выразительности, что позволяет его легко выучить и использовать. Язык CaML поддерживает функциональную, императивную и объектно-ориентированную парадигмы программирования. Был разработан в 1985 году во французском институте INRIA, который занимается исследованиями в области информатики. Самый распространённый в практической работе диалект языка ML.

Инструментарий OCaml включает в себя интерпретатор, компилятор в байткод и оптимизирующий компилятор в машинный код, сравнимый по эффективности с Java и лишь немного уступающий по быстродействию C и C++^[2].

На языке OCaml, в частности, написан рендеринг формул Википедии, использующих тег <math>, файлообменный клиент MLDonkey, стек управления гипервизором Xen xapi (является частью Xen Server/Xen Cloud Platform), язык программирования Haxe.

О языке |

Место и роль в информатике |

Язык OCaml является языком программирования общего назначения, но при этом имеет свои сложившиеся области применения^[3].

Во-первых, это — создание «безопасных» (не только в смысле информационной безопасности) приложений. В языке используется сборка мусора, а большинство типов данных являются ссылочными (англ. boxed), что означает предотвращение переполнения буферов во время исполнения программы. Кроме того, статическая типизация и проверки времени компиляции делают невозможными некоторые другие классы ошибок, такие, как ошибки приведения типов в силу отсутствия автоматического приведения типов. Кроме того, код может быть формально верифицирован. Имеются утилиты автоматического доказательства типовой корректности кода, превосходящие таковые для большинства языков программирования. И что немаловажно, меры безопасности не влияют на эффективность исполняемого кода^[3].

Другой областью успешного применения OCaml являются приложения, управляемые данными (data-driven). К этой области относится обработка текста, а также написание компиляторов. OCaml имеет не только средства для текстовой обработки (какими славится, например, Perl или AWK), но и инструменты для глубокого семантического анализа и преобразования текста, что делает OCaml применимым в задачах интеллектуального анализа данных (англ. data mining)^[3].

Разумеется, OCaml, как и другие диалекты ML, используются в исследовательских задачах и задачах верификации, при котором основной код пишется на некотором языке программирования, а затем формально верифицируется и анализируется программой на OCaml^[3]. Например, на OCaml написана система интерактивного доказательства теорем Coq.

Основные свойства |

OCaml занимает особое место среди языков программирования благодаря сочетанию эффективности, выразительности и практичности. Среди особенностей языка, развивавшихся в течение более чем 40 лет, со времени создания ML, можно выделить^[4]:

• Статическая проверка типов


• Параметрический полиморфизм


• Функции первого класса


• 
  Алгебраические типы данных и сопоставление с образцом
  


• Поддержка программирования с неизменяемыми структурами данных (англ. immutable programming)


• Автоматическая сборка мусора
  


• Эффективный компилятор в машинный код, без применения JIT-компиляции
  

История |

OCaml ведёт своё происхождение от ML (англ. meta language), который был реализован на диалекте Лиспа Робином Милнером в 1972 году в качестве программного средства для доказательства теорем, как метаязык логики вычислимых функций (LCF, англ. logic for computable functions). Позднее был сделан компилятор, а к 1980 году ML стал полноценной системой программирования^[5].

Ги Кузино (Guy Cousineau) добавил в язык алгебраические типы данных и сопоставление с образцом и определил ML в виде категориальной абстрактной машины (CAM). Таким образом, CAM-ML мог быть описан, верифицирован и оптимизирован, что явилось шагом вперёд для ML^[6].

Дальнейшим развитием был созданный к 1987 году Аскандером Суарецом (Ascánder Suárez) и продолженный Пьером Вейсом (Pierre Weis) и Мичелом Мони (Michel Mauny) язык Caml (переигранное CAM-ML)^[5][6].

В 1990 году Ксавье Лерой (Xavier Leroy) и Дамьен Долигез (Damien Doligez) выпустили новую реализацию, названную Caml Light. В этой реализации на Си использовался интерпретатор байт-кода и быстрый сборщик мусора. С написанием библиотек язык стал использоваться в образовании и исследовательских институтах^[5][6].

В 1995 году увидел свет Caml Special Light, развиваемый К. Лероем. Система программирования получила компилятор в машинные коды, что поставило эффективность исполняемого кода в один ряд с другими компилируемыми языками. В то же время была разработана система модулей, идея которой была заимствована из Standard ML^[5].

В современном виде OCaml появился в 1996 году, когда Дидье Реми (Didier Rémy) и Джером Вуйон (Jérôme Vouillon) реализовали для языка стройную и эффективную поддержку объектов. Эта объектная система позволяет на этапе компиляции в типобезопасной манере использовать идиомы объектно-ориентированного программирования, без свойственных C++ и Java проверок времени выполнения^[5].

В 2000-х годах язык плавно развивался, одновременно получая всё большее признание в коммерческих проектах и образовании. Среди разработанного в это время можно отметить полиморфные методы и вариантный типы, именованные и необязательные параметры, модули первого класса, обобщённые алгебраические типы данных (GADT). Язык стал поддерживать несколько аппаратных платформ (X86, ARM, SPARC, PowerPC)^[5][6].

Базовая семантика |

Модель вычислений OCaml как языка функционального программирования строится на трёх основных конструкциях лямбда-исчисления: переменных.mw-parser-output .ts-Переход img{margin-left:.285714em}^[⇨], определениях функций^[⇨] и применении функции к аргументам^[7].

Переменные |

Переменная — идентификатор, значение которого связано с определённой величиной. Имена переменных начинаются со строчной буквы или подчёркивания. Привязка обычно выполняется с помощью ключевого слова let, как в следующем примере в интерактивной оболочке^[8]:

let v = 1;;

Переменные имеют область видимости. Например, в интерактивной оболочке переменную можно использовать в следующих за её привязкой командах. Аналогично, переменную, определённую в модуле, можно использовать после определения в данном модуле^[8].

Привязка переменной может быть осуществлена и в области видимости, заданной конструкцией 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, в котором вводится другая переменная, которая может «затенить» первую^[8].

Функции |

Для определения функций в OCaml есть несколько синтаксических конструкций.

Функции можно определить с помощью ключевого слова function. Выражение для функции выглядит следующим образом^[9]:

function x -> x + 1

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

(function x -> x + 1) 5

Типом этой функции является int -> int, то есть, функция принимает целое и возвращает целое.

Функция может иметь несколько аргументов^[10]:

function (x, y) -> x - y

В этом примере её тип: int * int -> int, то есть, на входе функции — пара^[⇨], а на выходе — целое.

Есть и другой подход представления функций нескольких аргументов — преобразование N-арной функции в N функций одного аргумента — каррирование. Следующие два вида записи функции, вычисляющей произведение целочисленных аргументов, эквивалентны^[10]:

function x -> function y -> x * y

fun x y -> x * y

Именованные функции можно получить, связав переменную с функцией^[9]. Определение именованной функции настолько частая операция, что имеет отдельную синтаксическую поддержку. Следующие три записи — эквивалентные способы определить функцию (в интерактивной оболочке):

# 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>

Функции двух аргументов можно определить для использования инфиксной записи^[9]:

# 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^[9]:

# let rec fac n =

    match n with 

    | 0 -> 1

    | x -> x * fac (x - 1)

  ;;

В этом же примере вычисления факториала применено сопоставление с образцом (конструкция match-with).

Аргументы функции можно определить как именованные. Именованные аргументы можно указывать в любом порядке^[9]:

# 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), если имя параметра и переменной совпадают^[9]:

# let x = 4 in

  let y = 3 in

  divmod ~x ~y ;;

- : int * int = (1, 1)

Выражения |

Ассоциативность операций в выражениях OCaml определяется префиксом, распространяясь таким образом на операции, определённые пользователем. Знак - работает как префиксная, так и инфиксная операция, причём при необходимости использовать в качестве префикса совместно с применением функции параметр нужно заключить в скобки^[11].

Система типов |

Примитивные типы |

Язык OCaml имеет несколько примитивных типов: числовые типы (целый и числа с плавающей запятой), символьный, строки символов, булевский^[12].

Целый тип представляет целые числа из интервала [−2³⁰, 2³⁰ − 1] и [−2⁶², 2⁶² − 1] для 32- и 64-битных архитектур соответственно. С целыми числами можно производить обычные операции сложения, вычитания, умножения, деления, взятия остатка от деления: +, -, *, /, mod. В случае выхода результата за допустимый интервал ошибки не происходит, а результат вычисляется по модулю границы интервала^[13].

Числа с плавающей запятой представляются 53-битной мантиссой и порядком из интервала [−1022, 1023], следуя стандарту IEEE 754 для чисел с двойной точностью. В операциях эти числа нельзя смешивать с целыми. Кроме того, операции над числами с плавающей запятой синтаксически отличаются от целочисленных операций: +., -., *., /.. Также имеется операция возведения в степень: **. Для преобразования целых чисел в числа с плавающей запятой и обратно доступны функции: float_of_int и int_of_float^[13].

Для чисел с плавающей запятой имеются и другие математические функции: тригонометрические (sin, cos, tan, asin, acos, atan), округления (ceil, floor), экспоненциальная (exp), логарифмические (log, log10), а также извлечение квадратного корня (sqrt)^[13]. Для числовых типов имеются и полиморфные операции сравнения^[13].

Символьный тип — char — соответствует представлению символа с кодом от 0 до 255 (первые 128 символов совпадают с ASCII). Строчный тип — string — последовательность символов (максимальная длина: 2²⁴ — 6)^[14]. Пример с использованием функции преобразования целого к строке и операции конкатенации:

# "Example " ^ string_of_int(2) ;;

- : string = "Example 2"

Булевский тип имеет два значения: true (истина) и false (ложь). Операции над величинами булевского типа: унарная not (отрицание), бинарные: && (и), || (или). Бинарные операции вычисляют сначала левый аргумент, а правый — только если требуется^[15].

Булевские значения получаются в результате сравнений: = (структурное равенство), == (тождество), <> (отрицание структурного равенства), != (отрицание тождества), <, >, <=, >=. Для примитивных типов кроме строк и чисел с плавающей точкой структурное равенство и тождество совпадают, для других типов тождественными считаются значения, располагающиеся по одному адресу в памяти, а при структурном сравнении значения проверяются покомпонентно^[15].

Кроме того, а OCaml имеется специальный тип unit, который имеет всего одно значение — ()^[15].

Списки |

В OCaml список — конечная неизменяемая последовательность элементов одного типа, реализованная как односвязный список. Следующий пример демонстрирует синтаксис списка^[16]:

# ['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. Запись представляет собой набор хранимых вместе значений, при котором каждый элемент значения-записи доступен по своему имени — имени поля записи. Пример описания типа, связывания записи с переменной и доступ к полю записи^[17]:

# 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 был установлен компилятором автоматически.

Как и в случае с другими типами, тип может быть параметризован. Другие возможности записей^[17]:

• сопоставление с образцом (irrefutable)


• синтаксические уплотнение полей (field punning) записи в случае совпадения имён полей и переменных


• повторное использование полей и разрешение неоднозначности с помощью модулей


• функциональное обновление (functional update) записи


• изменяемые (mutable) поля


• fieldslib и поле записи как объект первого класса
  


• итераторы полей

Вариантный тип |

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

# 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). С другой стороны, преимущества объектов проявляются при использовании системы классов. В отличие от модулей, классы поддерживают позднее связывание, что позволяет ссылаться на методы объекта без статически заданной реализации и использовать открытую рекурсию (в случае с модулями можно использовать функции и функторы, но синтаксически такие описания требуют написания большего количества кода)^[19].

Вывод типов |

Хотя OCaml является языком программирования с сильной типизацией, система вывода типов (англ. type inference) позволяет определять тип выражения на основе имеющейся информации о его компонентах. В следующем примере функции проверки числа на чётность не указано ни одной декларации типа, и тем не менее у компилятора языка есть полная информация о типе функции^[20]:

# let odd x = x mod 2 <> 0 ;;

val odd : int -> bool = <fun>

Императивное программирование и функции с побочными эффектами |

Хотя бо́льшая часть кода может быть выполнена на OCaml в чистом функциональном стиле, язык позволяет программировать императивно, используя побочные эффекты, а также алгоритмические конструкции вроде циклов^[21].

Следующий пример напечатает на стандартном выводе (это — побочный эффект функции printf) 11 строк:

for i = 0 to 10 do 

  Printf.printf "i =%dn" 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|]

Хотя результатов вычислений можно достичь и чисто функциональными средствами, побочные эффекты позволяют оптимизировать вычисления. Например, они позволяются организовать ленивые вычисления и мемоизацию^[21].

Крупномасштабное программирование |

Модульность |

OCaml можно представить себе как состоящий из двух языков: язык ядра со значениями и типами и язык модулей и их сигнатур. Эти языки образуют два слоя в том смысле, что модули могут содержать типы и значения, а обычные значения не могут содержать модулей и модулей-типов. Тем не менее, OCaml предлагает механизм модулей первого класса, которые могут быть значениями и при необходимости преобразуются в обычные модули и обратно^[22].

Функторы |

Система модулей OCaml не ограничивается модульной организацией кода и интерфейсами. Одними из важных инструментов обобщённого программирования являются функторы. Упрощённо говоря, функторы являются функцией из модуля в модули, что позволяет реализовать следующие механизмы^[23]:

• 
  Внедрение зависимости (англ. dependency injection)


• Авторасширение модулей (англ. autoextension of modules)


• Создание экземпляра (англ. instantiation) модуля с некоторым состоянием

Примеры программ |

Запуск интерпретатора OCaml |

Для запуска интерпретатора языка OCaml необходимо в консоли ввести следующую команду:

$ ocaml

       Objective Caml version 3.09.0

#

Теперь можно вводить различные выражения, которые интерпретатор будет считывать, вычислять и выводить результат на экран:

# 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!

$

Быстрая сортировка |

В следующем примере приведён алгоритм быстрой сортировки, который сортирует список в порядке возрастания:

1 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

См. также |

• MLton

Примечания |

Литература |

Список книг, доступных онлайн (недоступная ссылка)

• 
  Minsky, Y. and Madhavapeddy, A. and Hickey, J. Real World OCaml: Functional Programming for the Masses. — O'Reilly Media, 2013. — 510 p. — ISBN 9781449324766.
  
  • Перевод на русский язык: Мински, Ярон; Мадхавапедди, Анил; Хикки, Джейсон. Программирование на языке OCaml = Real World OCaml: Functional Programming for the Masses. — ДМК, 2014. — 536 с. — (Функциональное программирование). — ISBN 978-5-97060-102-0.
    
  
  

• Joshua B. Smith. Practical OCaml. — Apress, 2006. — 488 с. — ISBN 9781590596203.


• Yaron Minsky. OCaml for the Masses // ACM Queue: Programming Languages. — 2011. — Т. 9, № 9.


• Chailloux, Manoury, Pagano. Developing Applications With Objective Caml. — 2007.


• Харрисон Дж. Введение в Функциональное Программирование = http://www.cl.cam.ac.uk/Teaching/Lectures/funprog-jrh-1996/. — 1997. Архивировано 11 января 2015 года.

Ссылки |

• 
  Официальный сайт языка OCaml (англ.)
  


• 
  Сайт OCaml Community (англ.)
  


• 
  Сайт Gerd Stolpmann’a, посвящённый OCaml (англ.)
  


• Перевод документации на русский язык


• Перевод на русский язык книги O’Reilly DAOC


• Emmanuel Chailloux, Pascal Manoury and Bruno Pagano Developing Applications With Objective Caml (англ.)