OCaml - OCaml

OCaml
OCaml Logo.svg
Парадигма Мультипарадигма : функциональная , императивная , модульная , объектно-ориентированная
Семья ML
Разработано Ксавье Лерой , Жером Вуйон, Дамьен Долигес , Дидье Реми, Аскандер Суарес
Разработчик INRIA
Впервые появился 1996 ; 25 лет назад ( 1996 )
Стабильный выпуск
4.12.0  Отредактируйте это в Викиданных / 24 февраля 2021 г . ; 6 месяцев назад ( 24 февраля 2021 г. )
Печатная дисциплина Предполагаемый , статический , прочный , структурный
Язык реализации OCaml, C
Платформа IA-32 , x86-64 , питание , SPARC , ARM 32-64
Операционные системы Кроссплатформенность : Unix , macOS , Windows
Лицензия LGPLv2.1
Расширения имени файла .ml, .mli
Веб-сайт ocaml .org
Под влиянием
C , Caml , Modula-3 , Паскаль , Стандартный ML
Под влиянием
ATS , Coq , Elm , F # , F * , Haxe , Opa , Rust , Scala

OCaml ( / к æ м əl / OH- КАМ -əl , ранее цель Caml ) является универсальным , мульти-парадигма языка программирования , который расширяет Ca диалекте ML с объектно-ориентированных функциями. OCaml был создан в 1996 году Ксавье Лерой , Жеромом Вуйоном, Дамьеном Долигесом , Дидье Реми, Аскандером Суаресом и другими.

Набор инструментов OCaml включает интерактивный интерпретатор верхнего уровня , компилятор байт-кода , оптимизирующий компилятор машинного кода , обратимый отладчик и диспетчер пакетов (OPAM). Первоначально OCaml был разработан в контексте автоматизированного доказательства теорем и широко используется в программном обеспечении для статического анализа и формальных методов . Помимо этих областей, он нашел серьезное применение в системном программировании , веб-разработке и финансовом инжиниринге , а также в других областях приложений.

Аббревиатура CAML первоначально расшифровывалась как язык категориальных абстрактных машин , но OCaml опускает эту абстрактную машину . OCaml - это бесплатный проект программного обеспечения с открытым исходным кодом, управляемый и в основном поддерживаемый Французским институтом исследований в области компьютерных наук и автоматизации (INRIA). В начале 2000-х годов элементы OCaml были приняты многими языками, особенно F # и Scala .

Философия

Языки, производные от ML , наиболее известны своими системами статических типов и компиляторами вывода типов . OCaml объединяет функциональное , императивное и объектно-ориентированное программирование в систему типов, подобную ML. Таким образом, программистам не нужно хорошо знать парадигму чисто функционального языка, чтобы использовать OCaml.

Требуя от программиста работы в рамках ограничений своей системы статических типов, OCaml устраняет многие связанные с типами проблемы времени выполнения, связанные с динамически типизированными языками. Кроме того, компилятор определения типа OCaml значительно снижает потребность в ручных аннотациях типов, которые требуются для большинства языков со статической типизацией. Например, тип данных переменных и сигнатуры функций обычно не нужно объявлять явно, как это делается в таких языках, как Java и C # , потому что они могут быть выведены из операторов и других функций, которые применяются к переменным и другим значениям. в коде. Эффективное использование системы типов OCaml может потребовать от программиста некоторой сложности, но эта дисциплина вознаграждается надежным и высокопроизводительным программным обеспечением.

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

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

Ксавье Лерой заявил, что «OCaml обеспечивает не менее 50% производительности достойного компилятора C», хотя прямое сравнение невозможно. Некоторые функции в стандартной библиотеке OCaml реализованы с помощью более быстрых алгоритмов, чем эквивалентные функции в стандартных библиотеках других языков. Например, реализация объединения наборов в стандартной библиотеке OCaml в теории асимптотически быстрее, чем эквивалентная функция в стандартных библиотеках императивных языков (например, C ++, Java), потому что реализация OCaml использует неизменность наборов для повторного использования частей ввода. устанавливает в выводе (см. постоянную структуру данных ).

Функции

OCaml включает систему статических типов , вывод типов , параметрический полиморфизм , хвостовую рекурсию , сопоставление с образцом , лексические замыкания первого класса , функторы (параметрические модули) , обработку исключений и автоматическую сборку мусора с возрастающим порождением .

OCaml примечателен расширением вывода типов в стиле ML на объектную систему в языке общего назначения. Это позволяет создавать структурные подтипы , когда типы объектов совместимы, если их сигнатуры методов совместимы, независимо от их объявленного наследования (необычная функция в статически типизированных языках).

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

Дистрибутив OCaml содержит:

Компилятор собственного кода доступен для многих платформ, включая Unix , Microsoft Windows и Apple macOS . Переносимость достигается за счет поддержки генерации собственного кода для основных архитектур: IA-32 , X86-64 (AMD64), Power , RISC-V , ARM и ARM64 .

Байт-код OCaml и программы с машинным кодом могут быть написаны в многопоточном стиле с упреждающим переключением контекста. Однако, поскольку сборщик мусора системы INRIA OCaml (который является единственной доступной в настоящее время полной реализацией языка) не предназначен для параллелизма, симметричная многопроцессорная обработка не поддерживается. Потоки OCaml в одном процессе выполняются только с разделением времени. Однако существует несколько библиотек для распределенных вычислений, таких как Functory и ocamlnet / Plasma .

Среда разработки

С 2011 года в среду разработки OCaml было добавлено множество новых инструментов и библиотек:

  • Инструменты разработки
    • opam - это менеджер пакетов для OCaml.
    • Merlin предоставляет IDE-подобную функциональность для нескольких редакторов, включая возврат типа, переход к определению и автозаполнение.
    • Dune - это составная сборочная система для OCaml.
    • OCamlformat - это средство автоматического форматирования для OCaml.
    • ocaml-lsp-server - это протокол языкового сервера для интеграции OCaml IDE .
  • Веб-сайты:
  • Альтернативные компиляторы для OCaml:
    • js_of_ocaml, разработанный командой Ocsigen , представляет собой оптимизирующий компилятор от OCaml до JavaScript .
    • BuckleScript , который также нацелен на JavaScript , с упором на создание удобочитаемого идиоматического вывода JavaScript.
    • ocamlcc - это компилятор от OCaml до C, дополняющий компилятор машинного кода для неподдерживаемых платформ.
    • OCamlJava, разработанный INRIA, представляет собой компилятор OCaml для виртуальной машины Java (JVM).
    • OCaPic, разработанный Lip6, представляет собой компилятор OCaml для микроконтроллеров PIC .

Примеры кода

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

$ ocaml
     Objective Caml version 3.09.0
#

После этого можно ввести код в ответ на подсказку «#». Например, чтобы вычислить 1 + 2 * 3:

# 1 + 2 * 3;;
- : int = 7

OCaml определяет тип выражения как «int» ( целое число с машинной точностью ) и возвращает результат «7».

Привет, мир

Следующая программа "hello.ml":

print_endline "Hello World!"

может быть скомпилирован в исполняемый файл байт-кода:

$ ocamlc hello.ml -o hello

или скомпилирован в оптимизированный исполняемый файл с машинным кодом:

$ ocamlopt hello.ml -o hello

и выполнено:

$ ./hello
Hello World!
$

Первый аргумент ocamlc, «hello.ml», указывает исходный файл для компиляции, а флаг «-o hello» указывает выходной файл.

Суммирование списка целых чисел

Списки - один из основных типов данных в OCaml. В следующем примере кода определяется рекурсивная функция sum, которая принимает один аргумент, целые числа , который должен быть списком целых чисел. Обратите внимание на ключевое слово, recкоторое означает, что функция рекурсивна. Функция рекурсивно выполняет итерацию по заданному списку целых чисел и предоставляет сумму элементов. Оператор match имеет сходство с элементом switch в языке C , хотя и носит гораздо более общий характер.

let rec sum integers =                   (* Keyword rec means 'recursive'. *)
  match integers with
  | [] -> 0                              (* Yield 0 if integers is the empty 
                                            list []. *)
  | first :: rest -> first + sum rest;;  (* Recursive call if integers is a non-
                                            empty list; first is the first 
                                            element of the list, and rest is a 
                                            list of the rest of the elements, 
                                            possibly []. *)
  # sum [1;2;3;4;5];;
  - : int = 15

Другой способ - использовать стандартную функцию сворачивания, которая работает со списками.

let sum integers =
  List.fold_left (fun accumulator x -> accumulator + x) 0 integers;;
  # sum [1;2;3;4;5];;
  - : int = 15

Поскольку анонимная функция - это просто приложение оператора +, ее можно сократить до:

let sum integers =
  List.fold_left (+) 0 integers

Кроме того, можно опустить аргумент списка, используя частичное приложение :

let sum =
  List.fold_left (+) 0

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

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

 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

Проблема дня рождения

Следующая программа вычисляет наименьшее количество людей в комнате, для которых вероятность полностью уникальных дней рождения составляет менее 50% ( задача дня рождения , где для 1 человека вероятность составляет 365/365 (или 100%), для 2 - это 364/365, для 3 это 364/365 × 363/365 и т. Д.) (Ответ = 23).

let year_size = 365.

let rec birthday_paradox prob people =
  let prob = (year_size -. float people) /. year_size *. prob  in
  if prob < 0.5 then
    Printf.printf "answer = %d\n" (people+1)
  else
    birthday_paradox prob (people+1)
;;

birthday_paradox 1.0 1

Церковные цифры

Следующий код определяет кодировку Church из натуральных чисел , с преемником (Succ) и добавлением (ADD). Церковь , позиция nявляется функцией высшего порядка , которая принимает функцию fи значение xи применяется fк xточно nраз. Чтобы преобразовать число Чёрча из функционального значения в строку, мы передаем ему функцию, которая добавляет строку "S"к его входу и константной строке "0".

let zero f x = x
let succ n f x = f (n f x)
let one = succ zero
let two = succ (succ zero)
let add n1 n2 f x = n1 f (n2 f x)
let to_string n = n (fun k -> "S" ^ k) "0"
let _ = to_string (add (succ two) two)

Факториальная функция произвольной точности (библиотеки)

Различные библиотеки доступны напрямую из OCaml. Например, в OCaml есть встроенная библиотека для арифметики произвольной точности . Поскольку факториальная функция растет очень быстро, она быстро выходит за пределы чисел машинной точности (обычно 32- или 64-битных). Таким образом, факториал является подходящим кандидатом для арифметики произвольной точности.

В OCaml модуль Num (теперь замененный модулем ZArith) обеспечивает арифметику произвольной точности и может быть загружен в работающий верхний уровень, используя:

# #use "topfind";;
# #require "num";;
# open Num;;

Затем факториальную функцию можно записать с использованием числовых операторов произвольной точности = / , * / и - /  :

# let rec fact n =
    if n =/ Int 0 then Int 1 else n */ fact(n -/ Int 1);;
val fact : Num.num -> Num.num = <fun>

Эта функция может вычислять факториалы гораздо большего размера, например 120 !:

# string_of_num (fact (Int 120));;
- : string =
"6689502913449127057588118054090372586752746333138029810295671352301633
55724496298936687416527198498130815763789321409055253440858940812185989
8481114389650005964960521256960000000000000000000000000000"

Треугольник (графика)

Следующая программа отображает вращающийся треугольник в 2D с помощью OpenGL :

let () =
  ignore (Glut.init Sys.argv);
  Glut.initDisplayMode ~double_buffer:true ();
  ignore (Glut.createWindow ~title:"OpenGL Demo");
  let angle t = 10. *. t *. t in
  let render () =
    GlClear.clear [ `color ];
    GlMat.load_identity ();
    GlMat.rotate ~angle: (angle (Sys.time ())) ~z:1. ();
    GlDraw.begins `triangles;
    List.iter GlDraw.vertex2 [-1., -1.; 0., 1.; 1., -1.];
    GlDraw.ends ();
    Glut.swapBuffers () in
  GlMat.mode `modelview;
  Glut.displayFunc ~cb:render;
  Glut.idleFunc ~cb:(Some Glut.postRedisplay);
  Glut.mainLoop ()

Привязки LablGL к OpenGL обязательны. Затем программа может быть скомпилирована в байт-код с помощью:

  $ ocamlc -I +lablGL lablglut.cma lablgl.cma simple.ml -o simple

или в собственный код с помощью:

  $ ocamlopt -I +lablGL lablglut.cmxa lablgl.cmxa simple.ml -o simple

или, проще говоря, с помощью команды сборки ocamlfind

  $ ocamlfind opt simple.ml -package lablgl.glut -linkpkg -o simple

и запустите:

  $ ./simple

В OCaml можно разрабатывать гораздо более сложные и высокопроизводительные графические программы в 2D и 3D. Благодаря использованию OpenGL и OCaml полученные программы могут быть кроссплатформенными и компилироваться без каких-либо изменений на многих основных платформах.

Последовательность Фибоначчи

Следующий код вычисляет последовательность Фибоначчи введенного числа n . Он использует хвостовую рекурсию и сопоставление с образцом.

let fib n =
  let rec fib_aux m a b =
    match m with
    | 0 -> a
    | _ -> fib_aux (m - 1) b (a + b)
  in fib_aux n 0 1

Функции высшего порядка

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

let twice (f : 'a -> 'a) = fun (x : 'a) -> f (f x);;
let inc (x : int) : int = x + 1;;
let add2 = twice inc;;
let inc_str (x : string) : string = x ^ " " ^ x;;
let add_str = twice(inc_str);;
  # add2 98;;
  - : int = 100
  # add_str "Test";;
  - : string = "Test Test Test Test"

Функция дважды использует переменную типа 'a, чтобы указать, что она может быть применена к любому отображению функции f из типа ' a в себя, а не только к функциям int-> int . В частности, дважды можно даже применить к себе.

  # let fourtimes f = (twice twice) f;;
  val fourtimes : ('a -> 'a) -> 'a -> 'a = <fun>
  # let add4 = fourtimes inc;;
  val add4 : int -> int = <fun>
  # add4 98;;
  - : int = 102

Производные языки

MetaOCaml

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

В качестве примера: если во время компиляции известно, что какая-то функция мощности требуется часто, но значение известно только во время выполнения, в MetaOCaml можно использовать двухэтапную функцию мощности: x -> x^nn

 let rec power n x =
   if n = 0
   then .<1>.
   else
     if even n
     then sqr (power (n/2) x)
     else .<.~x *. .~(power (n - 1) x)>.

Как только это nстанет известно во время выполнения, можно создать специализированную и очень быструю функцию мощности:

 .<fun x -> .~(power 5 .<x>.)>.

Результат:

 fun x_1 -> (x_1 *
     let y_3 = 
         let y_2 = (x_1 * 1)
         in (y_2 * y_2)
     in (y_3 * y_3))

Новая функция компилируется автоматически.

Другие производные языки

  • AtomCaml предоставляет примитив синхронизации для атомарного (транзакционного) выполнения кода.
  • Эмили (2006) - это подмножество OCaml 3.08, в котором используется верификатор правил проектирования для обеспечения соблюдения принципов безопасности модели объектных возможностей .
  • F # - это язык .NET Framework, основанный на OCaml.
  • Fresh OCaml упрощает работу с именами и привязками.
  • GCaml добавляет к OCaml экстенсиональный полиморфизм, что позволяет осуществлять перегрузку и маршалинг с безопасным типом.
  • JoCaml объединяет конструкции для разработки параллельных и распределенных программ.
  • OCamlDuce расширяет OCaml такими функциями, как выражения XML и типы регулярных выражений.
  • OCamlP3l - это система параллельного программирования , основанная на OCaml и языке P3L.
  • Хотя это не совсем отдельный язык, Reason - это альтернативный синтаксис OCaml и набор инструментов для OCaml, созданный в Facebook .

Программное обеспечение, написанное на OCaml

Пользователи

Несколько десятков компаний в той или иной степени используют OCaml. Известные примеры включают:

использованная литература

внешние ссылки