OCaml

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Objective Caml
Caml.128x58.gif
Семантика:

мультипарадигменный: функциональный, объектно-ориентированный, императивный

Автор:

INRIA

Выпуск:

4.02.1 (14 октября 2014)

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

строгая, статическая

Диалекты:

F#, JoCaml, MetaOCaml, OcamlP3l

Испытал влияние:

Standard ML, Caml Light

Лицензия:

публичная лицензия Q

Сайт:

ocaml.org

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

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

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

О языке[править | править вики-текст]

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

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

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

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

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

Основные свойства[править | править вики-текст]

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

История[править | править вики-текст]

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

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

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

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

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

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

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

Базовая семантика[править | править вики-текст]

Модель вычислений OCaml как языка функционального программирования строится на трёх основных конструкциях лямбда-исчисления: переменных[⇨], определениях функций [⇨] и применении функции к аргументам[6].

Переменные[править | править вики-текст]

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

let v = 1;;

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

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

Функции[править | править вики-текст]

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

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

function x -> x + 1

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

(function x -> x + 1) 5

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

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

function (x, y) -> x - y

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

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

function x -> function y -> x * y
fun x y -> x * y

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

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

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

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

# let rec fac n =
    match n with 
    | 0 -> 1
    | x -> x * fac (x - 1)
  ;;

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

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

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

# let x = 4 in
  let y = 3 in
  divmod x y ;;
- : int * int = (1, 1)

Выражения[править | править вики-текст]

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

Префикс операции Ассоциативность
! ? ~ Префикс
. .( .[ .{
применение функции, конструктора, метки, assert, lazy Левая
- -. Префикс
** lsl lsr asr Правая
* / % mod land lor lxor Левая
+ - Левая
:: Правая
@ ^ Правая
& $ != Левая
& && Правая
or || Правая
,
<- := Правая
if
; Правая
let match fun function try

Система типов[править | править вики-текст]

Примитивные типы[править | править вики-текст]

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

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

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

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

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

# "Example " ^ string_of_int(2) ;;
- : string = "Example 2"

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

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

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

Списки[править | править вики-текст]

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

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

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

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

  • сопоставление с образцом (irrefutable)
  • синтаксические уплотнение полей (field punning) записи в случае совпадения имён полей и переменных
  • повторное использование полей и разрешение неоднозначности с помощью модулей
  • функциональное обновление (functional update) записи
  • изменяемые (mutable) поля
  • fieldslib и поле записи как объект первого класса
  • итераторы полей

Вариантный тип[править | править вики-текст]

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

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

Вывод типов[править | править вики-текст]

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

# let odd x = x mod 2 <> 0 ;;
val odd : int -> bool = <fun>

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

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

Следующий пример напечатает на стандартном выводе (это — побочный эффект функции 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|]

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

Крупномасштабное программирование[править | править вики-текст]

Модульность[править | править вики-текст]

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

Функторы[править | править вики-текст]

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

Примеры программ[править | править вики-текст]

Запуск интерпретатора 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!
$

Быстрая сортировка[править | править вики-текст]

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

 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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

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

Ссылки[править | править вики-текст]